MD5 Algorithm

Quickies


JavaScript is a horrible language for writing this sort of program, but it is still useful for passwords, so I will try.

The md5cycle() function will be called for every 64 bytes, and will transform them into a number suitable for addition to the md5 sum.

An MD5 message, before the transformation, is converted into groups of 32-bit, positive numbers, 16 in each group. For the string "hello," this translation looks like this:

hello = 68 65 6c 6c 6f
6c 6c 65 68,80 6f,0,0,0,0,0,0,0,0,0,0,0,0,28,0

Apparently, the bytes of the word are taken four at a time, and written backwards into each segment, i.e., 68 65 6c 6c = 6c 6c 65 68, and 6f = 00 00 00 6f.

Then the byte 80 is appended, as if it was part of the original string, i.e., 6f -> 6f 80 = 80 6f. (This is the effective result of appending a single bit, 1, in the form of a byte, but how it is I cannot see.)

Finally, the length in bits (bytes times eight) is appended in two four-byte numbers, the last first, i.e., hello = 5 * 8 = 40 -> toBase16 -> 00 28 = 28 00.


In C code it appears that four auxiliary functions are defined as such:

typedef unsigned int word;
word f(word x, word y, word z) { return x & y | ~x & z; }
word g(word x, word y, word z) { return x & z | y & ~z; }
word h(word x, word y, word z) { return x ^ y ^ z; }
word i(word x, word y, word z) { return y ^ (x | ~z); }

and

f(00001111, 00110011, 01010101) = 01010011;
g(00001111, 00110011, 01010101) = 00100111;
h(00001111, 00110011, 01010101) = 01101001;
i(00001111, 00110011, 01010101) = 10011100; // or -1100100 signed

Four primary functions are defined for each of the 16 word places X[0..15] in the cycles of MD5. Also used here are 64 elements from a sine table, T[i = 0..63] = int(4294967296 * abs(sin(i+1))).

word ff(word a, word b, word c, word d, word k, word s, word t) {
return b + ((a + f(b, c, d) + k + T[t]) << s);
}
word gg(word a, word b, word c, word d, word k, word s, word t) {
return b + ((a + g(b, c, d) + k + T[t]) << s);
}
word hh(word a, word b, word c, word d, word k, word s, word t) {
return b + ((a + h(b, c, d) + k + T[t]) << s);
}
word ii(word a, word b, word c, word d, word k, word s, word t) {
return b + ((a + i(b, c, d) + k + T[t]) << s);
}
/* Note that all are identical except the
 * choice of auxiliary function internally.
 * This would help JavaScript code.
 * Probably the auxiliary can be brought
 * inside of each function, or the function
 * combined into the auxiliary.
 */

Note to self: I love that wonderful person. [walk-for-life 'surveillance camera']

To perform the calculation, there are 64 steps.

void md5cycle(word state[4], word X[16]) {
word a=state[0], b=state[1], c=state[2], d=state[3];

/* They call this round 1. */
a = ff(a, b, c, d, X[0], 7, 1);
d = ff(d, a, b, c, X[1], 12, 2);
c = ff(c, d, a, b, X[2], 17, 3);
b = ff(b, c, d, a, X[3], 22, 4);

a = ff(a, b, c, d, X[4], 7, 5);
d = ff(d, a, b, c, X[5], 12, 6);
c = ff(c, d, a, b, X[6], 17, 7);
b = ff(b, c, d, a, X[7], 22, 8);

a = ff(a, b, c, d, X[8], 7, 9);
d = ff(d, a, b, c, X[9], 12, 10);
c = ff(c, d, a, b, X[10], 17, 11);
b = ff(b, c, d, a, X[11], 22, 12);

a = ff(a, b, c, d, X[12], 17, 13);
d = ff(d, a, b, c, X[13], 12, 14);
c = ff(c, d, a, b, X[14], 17, 15);
b = ff(b, c, d, a, X[15], 22, 16);



/* 2 */
a = gg(a, b, c, d, X[1], 5, 17);
d = gg(d, a, b, c, X[6], 9, 18);
c = gg(c, d, a, b, X[11], 14, 19);
b = gg(b, c, d, a, X[0], 20, 20);

a = gg(a, b, c, d, X[5], 5, 21);
d = gg(d, a, b, c, X[10], 9, 22);
c = gg(c, d, a, b, X[15], 14, 23);
b = gg(b, c, d, a, X[4], 20, 24);

a = gg(a, b, c, d, X[9], 5, 25);
d = gg(d, a, b, c, X[14], 9, 26);
c = gg(c, d, a, b, X[3], 14, 27);
b = gg(b, c, d, a, X[8], 20, 28);

a = gg(a, b, c, d, X[13], 5, 29);
d = gg(d, a, b, c, X[2], 9, 30);
c = gg(c, d, a, b, X[7], 14, 31);
b = gg(b, c, d, a, X[12], 20, 32);



/* 3 */
a = hh(a, b, c, d, X[5], 4, 33);
d = hh(d, a, b, c, X[8], 11, 34);
c = hh(c, d, a, b, X[11], 16, 35);
b = hh(b, c, d, a, X[14], 23, 36);

a = hh(a, b, c, d, X[1], 4, 37);
d = hh(d, a, b, c, X[4], 11, 38);
c = hh(c, d, a, b, X[7], 16, 39);
b = hh(b, c, d, a, X[10], 23, 40);

a = hh(a, b, c, d, X[13], 4, 41);
d = hh(d, a, b, c, X[0], 11, 42);
c = hh(c, d, a, b, X[3], 16, 43);
b = hh(b, c, d, a, X[6], 23, 44);

a = hh(a, b, c, d, X[9], 4, 45);
d = hh(d, a, b, c, X[12], 11, 46);
c = hh(c, d, a, b, X[15], 16, 47);
b = hh(b, c, d, a, X[2], 23, 48);


/* 4 */
a = ii(a, b, c, d, X[0], 6, 49);
d = ii(d, a, b, c, X[7], 10, 50);
c = ii(c, d, a, b, X[14], 15, 51);
b = ii(b, c, d, a, X[5], 21, 52);

a = ii(a, b, c, d, X[12], 6, 53);
d = ii(d, a, b, c, X[3], 10, 54);
c = ii(c, d, a, b, X[10], 15, 55);
b = ii(b, c, d, a, X[1], 21, 56);

a = ii(a, b, c, d, X[8], 6, 57);
d = ii(d, a, b, c, X[15], 10, 58);
c = ii(c, d, a, b, X[6], 15, 59);
b = ii(b, c, d, a, X[13], 21, 60);

a = ii(a, b, c, d, X[4], 6, 61);
d = ii(d, a, b, c, X[11], 10, 62);
c = ii(c, d, a, b, X[2], 15, 63);
b = ii(b, c, d, a, X[9], 21, 64);
}

To be faster, you can substitute the last expression in each step with the actual value from the sine table T (avoid the extra lookup each time).

At the end of each cycle, you add the new values of a, b, c, d.

state[0] += a;
state[1] += b;
state[2] += c;
state[3] += d;

Important: Note that all addition is unsigned, modulo 2^32.

In the reference, MD5 is introduced with the process of padding the message. However, in actual practice this is performed at the end.

The simplest way to incorporate the padding step is to allow the last < 16 "words" of the message to remain, and do

t = l>>2;
M[t] |= 0x80 << ((3 - (l%4))*8);

where M are the remaining words of the message and l is the number of remaining bytes.

Important: It is necessary to zeroize the bits of M past the end of the last actual byte (they may contain leftover random values). This step must actually be performed before the last step.

M[t] &= ~(0xFFFFFF >> ((l%4) -1)*8);

At this point you can reposition the data to the begining of M.

/* assume that i - 16 points to the first
 * unprocessed word of M.
 */
i -= 16;
for (t=0; t<i%16; t++)
M[t] = M[i+t];

Proceed to zeroize up to 32 words.

for (; t<32; t++)
M[t] = 0;

The last two words of M will hold a 64-bit number of the original bits in M. If the remaining length is < 56, we have enough room to fit them within the first 16 words. Otherwise, they will be placed as the 31st and 32nd.

/* assume s is the 64-bit total of original bytes in M */
s *= 8;
if (l > 55) {
M[30] = s & 0xFFFFFFFF;
M[31] = s >> 32;
/* cycle the two sets of 16 */
md5cycle(state, M);
md5cycle(state, &M[16]);
} else {
M[14] = s & 0xFFFFFFFF;
M[15] = s >> 32;
/* cycle the single set of 16 */
md5cycle(state, M);
}