If M_j represents the j th sub-block of the message (from 0 to 15), and <<<s represents a left circular shift of s bits, the four operations are:

FF(a,b,c,d,M_j,s,t_i) denotes a = b + ((a + F(b,c,d ) + M_j + t_i) <<< s)

GG(a,b,c,d,M_j,s,t_i) denotes a = b + ((a + G(b,c,d ) + M_j + t_i) <<< s)

HH(a,b,c,d,M_j,s,t_i) denotes a = b + ((a + H(b,c,d) + M_j + t_i) <<< s)

II(a,b,c,d,M_j,s,t_i) denotes a = b + ((a + I(b,c,d ) + M_j + t_i) <<< s)

Figure 18.6  One MD5 operation.

The four rounds (64 steps) look like:

Round 1:

FF (a, b, c, d, M₀, 7, 0xd76aa478)

FF (d, a, b, c, M₁, 12, 0xe8c7b756)

FF (c, d, a, b, M₂, 17, 0x242070db)

FF (b, c, d, a, M₃, 22, 0xc1bdceee)

FF (a, b, c, d, M₄, 7, 0xf57c0faf)

FF (d, a, b, c, M₅, 12, 0x4787c62a)

FF (c, d, a, b, M₆, 17, 0xa8304613)

FF (b, c, d, a, M₇, 22, 0xfd469501)

FF (a, b, c, d, M₈, 7, 0x698098d8)

FF (d, a, b, c, M₉, 12, 0x8b44f7af)

FF (c, d, a, b, M₁₀, 17, 0xffff5bb1)

FF (b, c, d, a, M₁₁, 22, 0x895cd7be)

FF (a, b, c, d, M₁₂, 7, 0x6b901122)

FF (d, a, b, c, M₁₃, 12, 0xfd987193)

FF (c, d, a, b, M₁₄, 17, 0xa679438e)

FF (b, c, d, a, M₁₅, 22, 0x49b40821)

Round 2:

GG (a, b, c, d, M₁, 5, 0xf61e2562)

GG (d, a, b, c, M₆, 9, 0xc040b340)

GG (c, d, a, b, M₁₁, 14, 0x265e5a51)

GG (b, c, d, a, M₀, 20, 0xe9b6c7aa)

GG (a, b, c, d, M₅, 5, 0xd62f105d)

GG (d, a, b, c, M₁₀, 9, 0x02441453)

GG (c, d, a, b, M₁₅, 14, 0xd8a1e681)

GG (b, c, d, a, M₄, 20, 0xe7d3fbc8)

GG (a, b, c, d, M₉, 5, 0x21e1cde6)

GG (d, a, b, c, M₁₄, 9, 0xc33707d6)

GG (c, d, a, b, M₃, 14, 0xf4d50d87)

GG (b, c, d, a, M₈, 20, 0x455a14ed)

GG (a, b, c, d, M₁₃, 5, 0xa9e3e905)

GG (d, a, b, c, M₂, 9, 0xfcefa3f8)

GG (c, d, a, b, M₇, 14, 0x676f02d9)

GG (b, c, d, a, M₁₂, 20, 0x8d2a4c8a)

Round 3:

HH (a, b, c, d, M₅, 4, 0xfffa3942)

HH (d, a, b, c, M₈, 11, 0x8771f681)

HH (c, d, a, b, M₁₁, 16, 0x6d9d6122)

HH (b, c, d, a, M₁₄, 23, 0xfde5380c)

HH (a, b, c, d, M₁, 4, 0xa4beea44)

HH (d, a, b, c, M₄, 11, 0x4bdecfa9)

HH (c, d, a, b, M₇, 16, 0xf6bb4b60)

HH (b, c, d, a, M₁₀, 23, 0xbebfbc70)

HH (a, b, c, d, M₁₃, 4, 0x289b7ec6)

HH (d, a, b, c, M₀, 11, 0xeaa127fa)

HH (c, d, a, b, M₃, 16, 0xd4ef3085)

HH (b, c, d, a, M₆, 23, 0x04881d05)

HH (a, b, c, d, M₉, 4, 0xd9d4d039)

HH (d, a, b, c, M₁₂, 11, 0xe6db99e5)

HH (c, d, a, b, M₁₅, 16, 0x1fa27cf8)

HH (b, c, d, a, M₂, 23, 0xc4ac5665)

Round 4:

II (a, b, c, d, M₀, 6, 0xf4292244)

II (d, a, b, c, M₇, 10, 0x432aff97)

II (c, d, a, b, M₁₄, 15, 0xab9423a7)

II (b, c, d, a, M₅, 21, 0xfc93a039)

II (a, b, c, d, M₁₂, 6, 0x655b59c3)

II (d, a, b, c, M₃, 10, 0x8f0ccc92)

II (c, d, a, b, M₁₀, 15, 0xffeff47d)

II (b, c, d, a, M₁, 21, 0x85845dd1)

II (a, b, c, d, M₈, 6, 0x6fa87e4f)

II (d, a, b, c, M₁₅, 10, 0xfe2ce6e0)

II (c, d, a, b, M₆, 15, 0xa3014314)

II (b, c, d, a, M₁₃, 21, 0x4e0811a1)

II (a, b, c, d, M₄, 6, 0xf7537e82)

II (d, a, b, c, M₁₁, 10, 0xbd3af235)

II (c, d, a, b, M₂, 15, 0x2ad7d2bb)

II (b, c, d, a, M₉, 21, 0xeb86d391)

Those constants, t_i, were chosen as follows:

In step i, t_i is the integer part of 2³²*abs(sin(i)), where i is in radians.

After all of this, a, b, c, and d are added to A, B, C, D, respectively, and the algorithm continues with the next block of data. The final output is the concatenation of A, B, C, and D.

Security of MD5

Ron Rivest outlined the improvements of MD5 over MD4 [1322]:

1.  A fourth round has been added.

2.  Each step now has a unique additive constant.

3.  The function G in round 2 was changed from ((X⊥ Y ) ⊦ (X⊥ Z ) ⊦ (Y⊥ Z )) to ((X⊥ Z ) ⊦ (Y⊥ ¬ Z )) to make G less symmetric.

4.  Each step now adds in the result of the previous step. This promotes a faster avalanche effect.

5.  The order in which message sub-blocks are accessed in rounds 2 and 3 is changed, to make these patterns less alike.

6.  The left circular shift amounts in each round have been approximately optimized, to yield a faster avalanche effect. The four shifts used in each round are different from the ones used in other rounds.

Tom Berson attempted to use differential cryptanalysis against a single round of MD5 [144], but his attack is ineffective against all four rounds. A more successful attack by den Boer and Bosselaers produces collisions using the compression function in MD5 [203, 1331, 1336]. This does not lend itself to attacks against MD5 in practical applications, and it does not affect the use of MD5 in Luby-Rackoff-like encryption algorithms (see Section 14.11). It does mean that one of the basic design principles of MD5—to design a collision-resistant compression function—has been violated. Although it is true that “there seems to be a weakness in the compression function, but it has no practical impact on the security of the hash function” [1336], I am wary of using MD5.

18.6 MD2

MD2 is another 128-bit one-way hash function designed by Ron Rivest [801, 1335]. It, along with MD5, is used in the PEM protocols (see Section 24.10). The security of MD2 is dependent on a random permutation of bytes. This permutation is fixed, and depends on the digits of π. S₀, S₁, S₂,..., S₂₅₅ is the permutation. To hash a message M:

(1)  Pad the message with i bytes of value i so that the resulting message is a multiple of 16 bytes long.

(2)  Append a 16-byte checksum to the message.

(3)  Initialize a 48-byte block: X₀, X₁, X₂,..., X₄₇. Set the first 16 bytes of X to be 0, the second 16 bytes of X to be the first 16 bytes of the message, and the third 16 bytes of X to be the XOR of the first 16 bytes of X and the second 16 bytes of X.

(4)  This is the compression function:

t = 0

For j = 0 to 17

For k = 0 to 47

t = X_k XOR S_t

X_k = t

t = (t + j ) mod 256

(5)  Set the second 16 bytes of X to be the second 16 bytes of the message, and the third 16 bytes of X to be the XOR of the first 16 bytes of X and the second 16 bytes of X. Do step (4). Repeat steps (5) and (4) with every 16 bytes of the message, in turn.

(6)  The output is the first 16 bytes of X.

Although no weaknesses in MD2 have been found (see [1262]), it is slower than most other suggested hash functions.