Merkle-Damgard & Length Extension

MD5, SHA-1 and the whole SHA-2 family are one design: the Merkle–Damgård construction, which turns a fixed-size compression function into a hash for arbitrary-length input by chaining. Understanding the chain buys you three things at once — why these hashes exist, why H(secret ‖ message) is a forgeable MAC (the bug HMAC was invented to fix), and why the industry spent two decades migrating off MD5 and SHA-1.

The construction #

Pad the message, split it into fixed-size blocks $M_1 \dots M_k$, and fold:

$$h_0 = IV, \qquad h_i = f(M_i,\ h_{i-1}), \qquad H(M) = h_k$$

flowchart LR
  IV --> f1["f"] --> f2["f"] --> f3["f"] --> H["H(M)"]
  M1["M1"] --> f1
  M2["M2"] --> f2
  M3["M3 ‖ padding ‖ len"] --> f3

Padding (Merkle–Damgård strengthening): append a single 1 bit, then zeros, so the last block has 64 bits left; write the original message length in bits there. For a 512-bit-block hash that means padding to $\equiv 448 \pmod{512}$. Always applied, even when the length already fits — two different-length messages must never pad to identical block sequences. Embedding the length is what makes the security proof work: a collision in $H$ implies a collision in $f$, so designers only have to build a collision-resistant compression function.

The concrete instances differ only in the state and the mangling inside $f$:

The lineage is literal: MD4 → MD5 ("improved MD4") → SHA-0 → SHA-1. The only change from SHA-0 to SHA-1 is that 1-bit rotate in the message expansion — NSA fixed a weakness without saying which; SHA-0 collisions were later found at $2^{39}$ cost, vindicating the tweak.

Length extension: the design's built-in trap #

The final chaining value is the output — Merkle–Damgård keeps no secret finalization. So given $H(m)$ and $|m|$ (not $m$ itself!), anyone can set the internal state to $H(m)$ and keep hashing:

$$H(m \,\|\, pad(m) \,\|\, suffix) \quad \text{computed from } H(m) \text{ alone.}$$

This breaks the tempting MAC construction $tag = H(secret \,\|\, message)$: an attacker who sees one valid $(message, tag)$ pair can forge a valid tag for $message \,\|\, pad \,\|\, anything$, without ever learning the secret. They only need to guess the secret's length (a small brute-force).

Defenses, in order of correctness:

• HMAC (RFC 2104): $H\big((K \oplus opad) \,\|\, H((K \oplus ipad) \,\|\, m)\big)$ — the outer application hides the inner chaining state. This is the answer for MACs; it remains secure even with MD5/SHA-1 inside (collision resistance is not what HMAC needs).
• Truncation: SHA-384 and SHA-512/256 output fewer bits than their internal state, so the attacker can't reconstruct the state. Immune by accident of design.
• A different construction: SHA-3 is a sponge — output is squeezed from a larger hidden state, no extension possible. BLAKE2/BLAKE3 finalize with a flag. For keyed hashing, BLAKE2 takes a native key parameter; SHA-3 offers KMAC.

The collision timeline #

Collision resistance is capped by the birthday bound at $2^{n/2}$; real cryptanalysis got far below it:

1. 2004 Wang et al. break MD5 collision resistance at ~$2^{39}$ work (against a $2^{64}$ birthday bound); within two years the attack is down to seconds on a single laptop.
2. 2008 Chosen-prefix MD5 collision forges a working rogue CA certificate against RapidSSL (Sotirov, Stevens et al., 200 PS3s).
3. 2012 Flame malware carries a state-sponsored, previously unknown chosen-prefix MD5 collision to forge a Microsoft code-signing cert and impersonate Windows Update.
4. 2017 SHAttered: first public SHA-1 collision (Google + CWI), ~$2^{63}$ work, two colliding PDFs; browsers drop SHA-1 certs.
5. 2020 SHA-1 is a Shambles: chosen-prefix SHA-1 collision at ~$2^{63.4}$ (down from $2^{67.1}$), demonstrated by forging a PGP key. The authors spent ~$75k on rented GPU time and estimated ~$45k at then-current prices — the point being that chosen-prefix SHA-1 collisions had moved into ordinary-budget range. Chosen-prefix is the practically dangerous kind: both messages can be meaningful.
6. 2022 NIST announces SHA-1 retirement across all uses by end of 2030; signatures were disallowed back in 2013.

Operational status today:

Source claims audit #

Seeded from a university lab manual (MD5, SHA-1, N-hash labs; MD5/N-hash material follows Applied Cryptography). Status of its load-bearing claims: