It’s October (already?!?!) and–YIKES–I haven’t posted for two weeks.  I’m tapping away on a primer about e-discovery processing, a topic that’s received scant attention…ever.  One could be forgiven for thinking the legal profession doesn’t care what happens to all that lovely data when it goes off to be processed!  Yet, I know some readers share my passion for ESI and adore delving deeply into the depths of data processing.  So, here are a few paragraphs pulled from my draft addressing the well-worn topic of hashing in e-discovery where I attempt a foolhardy tilt at the competence windmill and seek to explain how hashing works and what those nutty numbers mean.  Be warned, me hearties, there be math ahead!  It’s still a draft, so feel free to push back and all criticism (constructive/destructive/dismissive) warmly welcomed.

My students at the  University of Texas School of Law and the Georgetown E-Discovery Training Academy spend considerable time learning that all ESI is just a bunch of numbers.  They muddle through readings and exercises about Base2 (binary), Base10 (decimal), Base16 (hexadecimal) and Base64; as well as about the difference between single-byte encoding schemes (ASCIII) and double-byte encoding schemes (Unicode).  It may seem like a wonky walk in the weeds; but the time is well spent when the students snap to the crucial connection between numeric encoding and our ability to use math to cull, filter and cluster data.  It’s a necessary precursor to their gaining Proustian “new eyes” for ESI.

Because ESI is just a bunch of numbers, we can use algorithms (mathematical formulas) to distill and compare those numbers.  Every student of electronic discovery learns about cryptographic hash functions and their usefulness as tools to digitally fingerprint files in support of identification, authentication, exclusion and deduplication.  When I teach law students about hashing, I tell them that hash functions are published, standard mathematical algorithms into which we input digital data of arbitrary size and the hash algorithm spits out a bit string (again, just a sequence of numbers) of fixed length called a “hash value.”  Hash values almost exclusively correspond to the digital data fed into the algorithm (termed “the message”) such that the chance of two different messages sharing the same hash value (called a “hash collision”) is exceptionally remote.  But because it’s possible, we can’t say each hash value is truly “unique.”

Using hash algorithms, any volume of data—from the tiniest file to the contents of entire hard drives and beyond—can be almost uniquely expressed as an alphanumeric sequence; in the case of the MD5 hash function, distilled to a value written as 32 hexadecimal characters (0-9 and A-F).  It’s hard to understand until you’ve figured out Base16; but, those 32 characters represent 340 trillion, trillion, trillion different possible values (2¹²⁸ or 16³²).

Hash functions are one-way calculations, meaning you can’t reverse (“invert”) a hash value and ascertain the data corresponding to the hash value in the same way that you can’t decode a human fingerprint to deduce an individual’s eye color or IQ.  It identifies, but it doesn’t reveal.  Another key feature of hashing is that, due to the so-called “avalanche effect” characteristic of a well-constructed cryptographic algorithm, when the data input changes even slightly, the hash value changes dramatically, meaning there’s no discernable relationship between inputs and outputs.  Similarity between hash values doesn’t signal any similarity in the data hashed.

There are lots of different hash algorithms and different hash algorithms generate different hash values for the same data.  That is, the hash value for the phrase “Mary had a little lamb” will be the following in each of the following hash algorithms:

MD5:       e946adb45d4299def2071880d30136d4

SHA-1:    bac9388d0498fb378e528d35abd05792291af182

SHA-256:efe473564cb63a7bf025dd691ef0ae0ac906c03ab408375b9094e326c2ad9a76

It’s identical data but it prompts different hashes using different algorithms.  Conversely, identical data will generate identical hash values when using the same hash function.  Freely published hash functions are available to all; so, if two people (or machines) anywhere use the same hash function against data and generate matching hash values, their data is identical.  If they get different hash values, they can be confident the data is different.  The differences may be trivial in practical terms, but any difference suffices to produce markedly different hash values.

I don’t dare go deeper in the classroom; but let’s dig down a bit here and explore the operations behind calculating an MD5 hash value.  If you really don’t care, just skip ahead.  It won’t hurt my feelings.

A widely used hash function is the Message Digest 5 (MD5) hash algorithm circulated in 1992 by MIT professor Ron Rivest as Requests for Comments 1321.  Requests for Comments or RFCs are a way the technology community circulates proposed standards and innovations generally relating to the Internet.  MD5 has been compromised in terms of its immunity to hash collisions in that’s it’s feasible to generate different inputs that produce matching MD5 hashes; however, MD5’s flaws minimally impact its use in e-discovery where it remains a practical and efficient way to identify, deduplicate and cull datasets.

When I earlier spoke of a hash algorithm generating a hash value of “fixed length,” that fixed length for MD5 hashes is 128 bits (16 bytes) or 128 ones and zeroes in binary or Base2 notation.  That’s a vast number space.  It’s 340,282,366,920,938,463,463,374,607,431,768,211,455 possibilities in our familiar decimal or Base10 notation.  It’s also unwieldy, so we shorten MD5 hash values to a 32-character Base16 or hexadecimal (“hex”) notation.  It’s the same numeric value, but conveniently expressed in a different base or “radix,” so it requires only one-fourth as many characters to write the number in hex notation than in binary notation.

That 32-character MD5 hash value is built from four 32-bit calculated values that are concatenated, that is, positioned end-to-end to form a 128-bit sequence or “string.”  Since we can write a 32-bit number as eight hexadecimal characters, we can write a 128-bit number as four concatenated 8-character hex values forming a single 32-character hexadecimal hash.  Each of those four 32-bit values are the product of 64 calculations (four rounds of 16 operations) performed on each 512-bit chunk of the data being hashed and by applying various specified constants.  After each round of calculations, the data shifts within the array in a practice called left bit rotation and a new round of calculations begins.  The entire hashing process starts by padding the message data to insure it neatly comprises 512-bit chunks and by initializing the four 32-bit variables to four default values.

For those wanting to see how this is done programmatically, here’s the notated MD5 pseudocode (from Wikipedia):

//Note: All variables are unsigned 32 bit and wrap modulo 2^32 when calculating
var int[64] s, K
var int i

//s specifies the per-round shift amounts
s[ 0..15] := { 7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22 }
s[16..31] := { 5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20 }
s[32..47] := { 4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23 }
s[48..63] := { 6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21 }

//Use binary integer part of the sines of integers (Radians) as constants:
for i from 0 to 63
K[i] := floor(2³² × abs(sin(i + 1)))
end for

//(Or just use the following precomputed table):
K[ 0.. 3] := { 0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee }
K[ 4.. 7] := { 0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501 }
K[ 8..11] := { 0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be }
K[12..15] := { 0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821 }
K[16..19] := { 0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa }
K[20..23] := { 0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8 }
K[24..27] := { 0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed }
K[28..31] := { 0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a }
K[32..35] := { 0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c }
K[36..39] := { 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70 }
K[40..43] := { 0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05 }
K[44..47] := { 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665 }
K[48..51] := { 0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039 }
K[52..55] := { 0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1 }
K[56..59] := { 0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1 }
K[60..63] := { 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391 }

//Initialize variables:
var int a0 := 0x67452301   //A
var int b0 := 0xefcdab89   //B
var int c0 := 0x98badcfe   //C
var int d0 := 0x10325476   //D

//Pre-processing: adding a single 1 bit
append “1” bit to message
// Notice: the input bytes are considered as bits strings,
//  where the first bit is the most significant bit of the byte.^[50]

//Pre-processing: padding with zeros
append “0” bit until message length in bits ≡ 448 (mod 512)
append original length in bits mod 2⁶⁴ to message

//Process the message in successive 512-bit chunks:
for each 512-bit chunk of padded message
break chunk into sixteen 32-bit words M[j], 0 ≤ j ≤ 15
    //Initialize hash value for this chunk:
var int A := a0
var int B := b0
var int C := c0
var int D := d0
    //Main loop:
for i from 0 to 63
var int F, g
if 0 ≤ i ≤ 15 then
F := (B and C) or ((not B) and D)
g := i
else if 16 ≤ i ≤ 31 then
F := (D and B) or ((not D) and C)
g := (5×i + 1) mod 16
else if 32 ≤ i ≤ 47 then
F := B xor C xor D
g := (3×i + 5) mod 16
else if 48 ≤ i ≤ 63 then
F := C xor (B or (not D))
g := (7×i) mod 16
      //Be wary of the below definitions of a,b,c,d
F := F + A + K[i] + M[g]
A := D
D := C
C := B
B := B + leftrotate(F, s[i])
end for
    //Add this chunk’s hash to result so far:
a0 := a0 + A
b0 := b0 + B
c0 := c0 + C
d0 := d0 + D
end for

var char digest[16] := a0 append b0 append c0 append d0 //(Output is in little-endian)

//leftrotate function definition
leftrotate (x, c)
return (x << c) binary or (x >> (32-c));

Still there?

Despite the complexity of these calculations, it’s possible to contrive hash collisions where different data generate matching MD5 hash values.  Accordingly, the cybersecurity community have moved away from MD5 in applications requiring collision resistance, such as digital signatures.

You may wonder why MD5 remains in wide use if it’s “broken” by engineered hash collisions.  Why not simply turn to more secure algorithms like SHA-256?  Some tools and vendors have done so, but a justification for MD5’s survival is that the additional calculations required to make alternate hash functions more secure consume more time and computing resources.  Too, most tasks in e-discovery built around hashing—e.g., deduplication and De-NISTing–don’t demand strict protection from engineered hash collisions.  For e-discovery, MD5 “ain’t broke,” so there’s little cause to fix it.