MD Family Hash Functions

The MD family is a line of hash functions designed by Ronald Rivest, comprising MD2, MD4 and MD5. MD4 and MD5 defined the design that the SHA family later followed.

All MD functions use 128 output bits by design. They all are broken now.

Merkle–Damgård Construction

Builds a hash of arbitrary length input from a fixed-size compression function $f$. Ralph Merkle and Ivan Damgård proved the construction independently in 1989.

• Padding
  Append a single 1 bit, then 0 bits, then the message length as a 64-bit integer, so the padded length is a multiple of the block size.
• Chaining
  Split the padded message into blocks $m_1, \ldots, m_t$ and start from a fixed initialization vector $h_0$. $$h_i = f(h_{i-1}, m_i), \quad H(m) = h_t$$

If $f$ is collision resistant, then $H$ is collision resistant. The length in the padding is required for this proof.

MD2

Designed in 1989 for 8-bit machines.

• Block size
  16 bytes, with a 16-byte checksum appended before hashing.
• Structure
  Byte-oriented compression using a substitution table derived from the digits of $\pi$.

Collisions in the compression function were found in 1997 and a full collision in 2004. A preimage attack of about $2^{73}$ work followed in 2008. It was retired by RFC 6149 in 2011.

MD4

Designed in 1990 as a fast hash for 32-bit machines.

• Block size
  512 bits.
• Structure
  3 rounds of 16 steps, each step using 32-bit word operations and a different nonlinear function.

The 3-round structure proved too weak. Den Boer and Bosselaers attacked reduced versions in 1991. Hans Dobbertin found full collisions in 1996. Wang et al. found collisions by hand in 2004. It is completely broken.

MD5

Designed in 1991 as a strengthened MD4, published as RFC 1321 in 1992.

• Block size
  512 bits.
• Structure
  4 rounds of 16 steps, so 64 steps in total. The 128-bit state is 4 words $A, B, C, D$, and each step adds a constant derived from the sine function.

MD5 was the dominant hash of the 1990s and was used in file checksums, digital certificates and password storage.

Timeline of attacks:

• 1993
  Den Boer and Bosselaers find pseudo-collisions, meaning collisions in the compression function with a chosen $h_0$.
• 1996
  Dobbertin finds a collision in the compression function with the real $h_0$. Cryptographers recommend moving away from MD5.
• 2004
  Wang et al. find full collisions in hours on ordinary hardware.
• 2007
  Stevens et al. give chosen-prefix collisions, where 2 messages with arbitrary different prefixes are extended into a collision.
• 2008
  Researchers use a chosen-prefix collision to forge a rogue certificate authority certificate.
• 2012
  The Flame malware uses an MD5 collision to forge a Microsoft code signing certificate.

MD5 must not be used where collision resistance matters. It remains acceptable only as a non-security checksum. RFC 6151 records the attacks.

Summary