The attacks

MD5, SHA-1 and length extension

The theory of collisions did not remain theoretical. Two historical functions, MD5 and SHA-1, were effectively broken, and the Merkle-Damgård construction itself suffers from an exploitable structural weakness.

MD5: broken since 2004

MD5 produces a 128-bit digest, that is only 64 bits of collision resistance. As early as 2004, Wang and her colleagues published a method producing collisions in a few hours of computation, far faster than the 2^64 expected.

The consequences were real: in 2012, the Flame malware forged a fake Microsoft certificate by exploiting an MD5 collision. MD5 is today forbidden for any security use.

SHA-1: the SHAttered attack (2017)

SHA-1 produces 160 bits, that is 80 bits of theoretical resistance. In 2017, Google and CWI carried out SHAttered: two different PDF files having the same SHA-1 digest, at the cost of about 2^63 computations. The collision was expensive, but it was effective. SHA-1 has since been banned from browsers and certificate authorities.

Remember the rule: MD5 and SHA-1 are broken and forbidden. We use SHA-256 (SHA-2) or SHA-3.

The length extension attack

Merkle-Damgård has a structural flaw independent of collisions. The final digest of a message is the complete internal state at the end of the chaining. An attacker who knows H(message) therefore knows the internal state, and can resume the chaining to add blocks — without knowing the original message.

   Le défenseur calcule :
   IV -> f -> f -> ... -> f -> H(message)
              (message secret)

   L'attaquant, sans connaître "message", repart de H(message) :
   H(message) -> f -> f -> H(message || padding || suffixe)
                     (suffixe choisi par l'attaquant)

He can thus produce the valid digest of message || padding || suffixe. This is dangerous for naive schemes of the type H(secret || données) used as an authenticator: the attacker lengthens the message and recomputes a valid authenticator.

The countermeasure on the MAC side is HMAC, which nests two hashes with the key (H(clé ⊕ a || H(clé ⊕ b || message))) and neutralizes the extension.

SHA-3 and the sponge construction

SHA-3 (Keccak, standardized in 2015) does not use Merkle-Damgård but a different construction, the sponge. The message is "absorbed" into a large state, then the digest is "squeezed" out — and the published digest reveals only a part of the internal state. The length extension attack therefore becomes impossible by construction. SHA-3 did not replace SHA-2 (still safe), but offers a fallback alternative based on an independent structure.

In summary