Years ago I implemented MD5 in C language as a college assignment. It was fun to implement something complex yet very straight forward. You just go over the RFC and implement each step accurately. Only difficult part was debugging because even if you make a small mistake any where in the code the result is completely different and does not give any clue as to where the error is.
Years later I gave another look at the algorithm to get better understanding of the it. MD5 hash algorithm has three basic construction blocks.
1.
Encryption Function: Converts a fixed sized input to fixed sized output such that output is a random permutation of the input. Encryption function also takes a key which can alter the permutations generated by the function. Encryption function by definition is reversible i.e. there exists a Decryption function such that given the output in can produce original input. In case of MD5, the encryption function takes a 32bit key and 128 bit input and 128 bit output. MD5 uses following encyptions function
def encrypt(f:(List[Int])=>Int,T:Int,S:Int)(data:List[Int],key:Int) =
data(3) ::
data(1) + rotateLeft((data(0)+f(data)+key+T),S) ::
data(1) ::
data(2) :: Nil
as you can see encryption function is parameterized by f,T and S. MD5 uses 64 different variations of encrypt function.
2.
Compression Function: Compression Function takes a fixed sized input and converts it to a smaller fixed sized output. This function is one way i.e. there exists no function which can generate the input for a given output.Compression Functions are created using Encryption Function by applying it to a larger block again and again.
In case of MD5 the compression function takes 512 bits as input and generates 128 bits of output.
The 512 bit input is divided into 16 32 bit words. Each of these 32 bit words is used as key to the encryption function. This is repeated four times in four phases. In each phase a different permutation of 32 bit words is used. Thus, phases differ in two ways, first, the permutation of input and second, the encryption function used. Following function creates a four permutations, one for each phases and concatenates them. This results in 64 32 bit words.
def permute(f:(Int)=>Int)(data:List[Int]):List[Int]={
List.range(0,data.length).map((i)=>data(f(i)%data.length))
}
def permutations(chunk:List[Int]):List[Int]={
permute((x:Int)=>x)(chunk):::
permute((x:Int)=>(5*x+1))(chunk):::
permute((x:Int)=>(3*x+5))(chunk):::
permute((x:Int)=>(7*x))(chunk)
}
The permute function takes a function and generates a permutation of data List according to it. permutations function returns four permutations one for each phase of compression function.
Once we have input data ready, we need to generate 64 different encryption functions, 16 for each phase. For this we need values for f,T and S. MD5 Compression function uses four different values of f, one for each phase.
def F(x:Int,y:Int,z:Int) = x&y | ~(x)&z
def G(x:Int,y:Int,z:Int) = x&z | y&(~z )
def H(x:Int,y:Int,z:Int) = x ^ y ^ z
def I(x:Int,y:Int,z:Int) = y ^ ( x | ~z )
val fList = List(F _,G _,H _,I _).map(listyFy(_) _)
def listyFy(f:(Int,Int,Int)=>Int)(d:List[Int]) = f(d(1),d(2),d(3))
Above defines four different values of f. We also create a list these functions. listyFy function converts a function which takes three ints to a function which takes a list ints.
Following a list of functions which generate values for S for each phase.
val shiftfn=List(
(i:Int)=>5*i + 7, (i:Int)=>(i*i + 7*i +10)/2,
(i:Int)=>4 + 7*((i+1)/2) + 5*(i/2), (i:Int)=>(i*i + 7*i +10)/2 + 1
).map((f)=>(x:Int)=>f(x%4));
Now below is the code which generates 64 encryption functions, which are used in each step of compression function .
def Ts(i:Int)=
(math.floor(math.abs(math.sin(i+1))*(1L<<32)).toLong).toInt
val EList =
List.range(0,64).map((i:Int)=>encrypt(fList(i/16),
Ts(i),
shiftfn(i/16)(i)) _)
Here we create EList, a list of 64 encryption function, by passing appropriate value of f,T and S to the encrypt function, which returns an encryption function corresponding to these values.
Now we can use this list of encryption function and permutation to define our compression Function.
def compressMD5(state:List[Int],chunk:List[Byte]) = {
val newstate = permutations(asWords(chunk)).zip(EList).foldLeft(state)((x,y)=>y._2(x,y._1))
newstate.zip(state).map({ case (a,b)=>(a+b)})
}
compressMD5 takes a state, a list of four 32 bit words, and chunk, a list of 64 bytes. It converts 64 bytes in chunk to an array of 16, 32 bit words, using asWorkds utility function. It then creates permutations which results in 64 32 bit words, four permutation of 16 32 bit words. Then each of these words is applied as key to the corresponding encryption function in EList. The state variable is uses as initialization vector for this step which encrypted and then fed as data in to next encryption function.
Finally, IV and resulting state and added word by word.
3.
Hash Function: This is the final function which given input of any arbitrary length generates an output of fixed length. It usually uses merkel-damgard construction to apply a compression function to arbitrary large data.
This is the most straight forward step. It appends padding as required by merkelDamgard construction and divides resulting bytes in to chunks of 64 bytes which is equal to size of input of our compression function.
