Skip to content
Tutorials Center
My learning

Topics

Lesson 12 of 40 ยท Hashing

Hash Attacks: Collisions, Length Extension and Birthday

Run a birthday collision search on a toy hash, learn how MD5 and SHA-1 were broken, and forge a message with a length-extension attack that HMAC prevents.

A hash function can be perfectly good at hiding its input and still be misused or broken. This lesson covers three kinds of failure. The birthday bound explains why collisions need only about the square root of the work that preimages need. The real-world breaks of MD5 and SHA-1 show what happens when cryptanalysis beats that bound. And length extension shows that even an unbroken hash such as SHA-256 is unsafe when you build a message authentication code the naive way, which is the reason HMAC exists.

You should know the three properties from cryptographic hash functions: preimage, second preimage and collision resistance.

The birthday bound

How many people must be in a room before two share a birthday with probability above one half? Only 23, far fewer than the 183 you might guess. The reason is that the number of pairs grows quadratically, so collisions appear long before the space is full.

For a hash with N = 2^n possible digests, the first collision is expected after about sqrt(N) = 2^(n/2) inputs. That is why a 128-bit digest gives only 64 bits of collision security, and why SHA-256 is chosen as a 256-bit hash to get 128 bits.

Python Collisions arrive early

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Compare this with the preimage search in the previous lesson: for 16 bits a preimage needed tens of thousands of guesses, while here a collision needs a few hundred. The cost of each additional digest bit is a factor of 2 for preimages but only a factor of about 1.4 for collisions.

The birthday bound is also why random identifiers have limits. If you generate random 96-bit nonces, you expect a repeat after roughly 248 values, and you want to stay far below that.

When hashes break: MD5 and SHA-1

A hash is broken when someone finds collisions faster than the birthday bound. History so far:

Function Digest Generic collision cost Status
MD5 128 bits 264 Collisions in seconds on a laptop since the mid-2000s; chosen-prefix collisions used to forge a certificate
SHA-1 160 bits 280 First public collision in 2017 (the SHAttered attack), with a cheaper chosen-prefix attack later
SHA-256, SHA-3, BLAKE2 256+ bits 2128 No known attacks

Why does a collision matter if the attacker cannot choose what it says? Because of chosen-prefix collisions: the attacker prepares two documents with different meanings, appends specially computed blocks, and obtains two files with the same digest. If a trusted party signs the digest of the harmless one, the signature also validates the malicious one. This is how researchers forged a CA certificate from an MD5-signed one.

MD5 and SHA-1 are still acceptable for non-adversarial uses, such as quickly detecting accidental corruption or as a cache key, but never where an attacker can influence the data: signatures, certificates, deduplication of untrusted files, or password handling.

Length extension

Most classic hashes (MD5, SHA-1, SHA-2) use the Merkle-Damgard construction. The message is padded, split into blocks and fed one at a time into a compression function that updates an internal state. The final digest is the final internal state.

That has a nasty consequence. If you know H(m) and the length of m, you can resume the computation from that state, feed extra blocks, and produce a valid digest of m || padding || extra without ever knowing m.

Now imagine a server that authenticates messages with a tag H(key || message). An attacker who sees one message and its tag can append data and compute a matching tag for the longer message, without the key.

flowchart LR
    S0["IV"] --> B1["block: key + msg"]
    B1 --> B2["block: padding"]
    B2 --> T["state = tag"]
    T -.->|"attacker resumes here"| E1["block: extra data"]
    E1 --> F["forged tag"]

The tag is the state after the padding block. The attacker starts a new run from that state and adds their own blocks.

To demonstrate this safely, here is a toy Merkle-Damgard hash with an 8-byte state and 8-byte blocks. It is built from SHA-256 only as a compression function; it is not secure, but its structure is the same as the real thing.

Python Forging a tag without the key

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The forged message looks odd: the padding bytes sit in the middle. Many parsers ignore garbage or let a later to= override an earlier one, and that is exactly what makes this exploitable. The same trick has been used against real web APIs that signed requests with SHA1(secret + params).

Defenses

  • Use HMAC, not H(key || message). HMAC hashes the message under an inner key and then hashes that result under an outer key, so the attacker never gets to continue an internal state.
  • Use a hash that is not vulnerable: SHA-3 is a sponge, whose digest does not expose the full internal state, and BLAKE2 has a keyed mode. Truncated SHA-2 variants (SHA-512/256, SHA-384) also resist, because the output hides part of the state.
  • Prefer a signature or a dedicated MAC over inventing your own construction.

Never forget that "just a hash" is not authentication: anyone can compute H(message). You need a secret key in a proper construction, which is the topic of MACs and HMAC.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Roughly how many random inputs does it take to find a collision in a 64-bit hash?

    By the birthday bound a collision is expected after about the square root of the number of digests, 2^(64/2) = 2^32.
  2. 2. What is a chosen-prefix collision attack useful for?

    The attacker picks two different prefixes and computes extra blocks that make the digests equal, so a signature on one document also covers the other.
  3. 3. Why is a tag computed as SHA-256(key || message) unsafe?

    SHA-256's digest is its internal state, so an attacker who knows a tag and the lengths can continue hashing from it.
  4. 4. Which is the right fix for the naive MAC?

    HMAC's nested construction prevents resuming from the tag. A keyed BLAKE2 mode or a signature also avoids the problem.

Summary

  • Collisions cost about 2^(n/2) work (the birthday bound), much less than the 2^n for preimages, so digests need to be twice as long as the security level you want.
  • MD5 and SHA-1 have practical collision attacks, including chosen-prefix ones that can forge certificates. Avoid them wherever an attacker can influence the input.
  • Merkle-Damgard hashes (MD5, SHA-1, SHA-2) are open to length extension when used as H(key || message).
  • Use HMAC or another keyed construction for authentication; SHA-3 and BLAKE2 also avoid length extension.

Next: XOR and the One-Time Pad.