MD5

MD5 (RFC 1321)

Terminology:

• word: 32 bit quantity
• byte: 8 bit quantity
• \(X <<< 3\): circularly rotating \(X\) by 3 times

MD5 Algorithm

To find the md5 for a message \(m\) of \(b\)-bits, where \(m\) can be visualized as

\[m_0 \, m_1 \, \cdots \, m_{b-1}\]

Step 1: Appending Padding Bits

The mesage is padded so that its length is congruent to \(448\), modulo \(512\). This means after padding the message length is 64 bits shy of being a multiple of 512. Formally:

\[m\_size \cong 448 \, (modulo \, 512)\]

Padding: to pad the message to the desired length, a single 1 bit is appended followed by 0 bits. At lease 1 bit (length \(447 \% %512\)) or at most 512 bit (already \(448\)).

Step 2: Append length

A 64-bit representation of \(b\) (length of the message before padding) is appeneded to the result of step 2. If \(b > 2^64\), only the lower 64 bits of b are used.

At this point the message is a multiple of \(512\) and multple of \(16\) (32 bit) words.

Now let the following denote the words of the resulting message where \(N\) is a multiple of 16

\[M[0,\, \cdots \,,N-1]\]

Step 3: Initialize MD Buffer

A buffer of four word (4 x 32 bit) \((A, B, C, D)\) is used to compute the MD5

\[word\, A:\, 01\, 23\, 45\, 67\] \[word\, B:\, 89\, ab\, cd\, ef\] \[word\, C:\, fe\, dc\, ba\, 98\] \[word\, D:\, 76\, 54\, 32\, 10\]

Step 4: Process Message in 16-Word Blocks (512 bits)

For every 512 bits, peform a set of complex operations on the buffer. These complex operations are bit wise parallel (see Step 4. Processing in 16-Word Blocks) for more information.

Step 5: Output

The final MD5 is just the concat the buffer DCBA