The Birthday Attack

Why the birthday attack matters

Almost every cryptographic promise you rely on — a signed software update, a TLS certificate, a Git commit hash, a blockchain block — is anchored to the claim that a hash function is collision resistant: it should be infeasible to find two inputs x ≠ y with H(x) = H(y). The birthday attack is the reason that promise costs only 2^n/2 to break, not 2ⁿ. It is a generic attack: it treats the hash as a black box and makes no assumption about its internals, so it works against a perfect random function and puts a hard ceiling on the security any hash of a given output length can offer.

The practical consequence is blunt. A 128-bit hash such as MD5 has a generic collision cost of just 2⁶⁴ — within reach of a determined organization even before you factor in the design flaws that made MD5's real cost a few seconds. That is why modern standards mandate 256-bit outputs when they want the industry-standard 128-bit security level. The "double the bits" rule of thumb is the birthday attack made concrete.

The birthday paradox, precisely

Ask how many people you need in a room before two share a birthday, and intuition says roughly half of 365. The real answer is 23. The trick is that a collision needs a pair, and 23 people form C(23, 2) = 253 distinct pairs — each pair a fresh chance to match one of 365 days. Probability accumulates over pairs, not people.

Formally, with N equally likely values and k independent draws, the chance that all draws are distinct is:

P(no collision) = ∏_{i=0}^{k-1} (1 − i/N)
               ≈ exp( − k(k−1) / (2N) )     for k ≪ N

Setting the collision probability 1 − P to 1/2 and solving gives the birthday bound:

k ≈ √(2 · ln 2 · N) ≈ 1.1774 · √N

With N = 365 that yields k ≈ 22.5, matching the famous 23. Swap the calendar for a hash and set N = 2n: the number of digests you must generate before a collision becomes likely is ≈ 1.18 · 2n/2. The expected number of hashes until the first collision (not just 50% odds) is the closely related √(πN/2) ≈ 1.253 · 2n/2. Both are Θ(2^n/2) — the square root of the output space.

How the attack works, step by step

The classic table-based birthday attack against an n-bit hash:

1. Generate candidates. Produce about 2n/2 messages — often innocuous variants of a target document (a swapped space, a synonym, an invisible field) so that any one is semantically acceptable.
2. Hash and store. Compute H(mᵢ) for each and insert (digest → message) into a hash table. Every insertion checks whether the digest is already present.
3. Detect the match. By the birthday bound, after ≈ 2^n/2 insertions two entries collide with probability > 1/2. Those two messages are a collision: H(x) = H(y), x ≠ y.

This costs Θ(2^n/2) time and Θ(2^n/2) memory. The memory is the bottleneck at scale — storing 2⁶⁴ digests is impossible. The standard fix is a memoryless cycle-finding search: iterate x → H(x) → H(H(x)) → … and use Pollard's rho (Floyd's or Brent's tortoise-and-hare cycle detection) to find where the sequence collides. It keeps the same expected Θ(2^n/2) time while using only O(1) memory. Parallel collision search (van Oorschot–Wiener, using distinguished points) then splits the work across many machines with near-linear speedup — the engine behind the real MD5 and SHA-1 breaks.

Collision vs. preimage: three different games

People conflate "the hash is broken," but hash security has three distinct properties with very different generic costs. The birthday attack only touches the first.

Property	What the attacker controls	Goal	Generic cost
Collision resistance	Both inputs	Any x ≠ y with H(x) = H(y)	2n/2 (birthday)
Second-preimage resistance	One free input	Given x, find y ≠ x with H(y) = H(x)	2n
Preimage resistance	Nothing (target fixed)	Given digest h, find x with H(x) = h	2n

The birthday speedup requires the attacker to freely choose both inputs, so it applies only to collisions. Preimage and second-preimage lack that freedom — you cannot make pairs collide with each other; you must hit one fixed target — so the birthday counting gives no advantage and they stay at 2ⁿ for an ideal hash. This is why MD5 and SHA-1 collide trivially today, yet no practical preimage attack on either is known: collisions are the weak flank of every Merkle–Damgård hash.

One subtle amplifier: in Merkle–Damgård constructions (MD5, SHA-1, SHA-256), collisions extend. If H(x) = H(y) for equal-length blocks, then H(x ‖ s) = H(y ‖ s) for any suffix s. A single collision becomes a template for endless colliding message pairs — which is exactly what makes chosen-prefix collisions so devastating for real file formats.

Worked example: forging a digital signature

Signatures don't sign the message — they sign H(message). So any two messages with the same hash share a single valid signature. The birthday attack turns that into a forgery recipe.

1. Draft a benign document the victim will happily sign ("I owe you $10"), and a fraudulent twin ("I owe you $10,000,000").
2. Generate ≈ 2^n/2 cosmetically different variants of each — different whitespace, synonyms, hidden markup — all semantically equivalent within their group.
3. By the birthday bound, with high probability some benign variant b* and some fraudulent variant f* satisfy H(b*) = H(f*).
4. Get the victim to sign b*. That signature verifies identically on f*. You now hold a validly "signed" fraudulent document.

This is a two-message (identical-prefix) attack. The far more dangerous chosen-prefix variant lets the two documents differ arbitrarily up front and still collide — this is what let researchers forge a rogue CA certificate against MD5 in 2008, and what SHAttered demonstrated for SHA-1 by producing two distinct PDFs with the same SHA-1 digest. The lesson for practice: a signer should always add unpredictable content the attacker cannot precompute (randomized hashing, or a construction like RSA-PSS), so the offline collision search has nothing to grind against.

Why 256-bit hashes for 128-bit security

Security levels are quoted as the log₂ of the best attack's work. Because the birthday attack finds collisions in 2^n/2, the collision-resistance security level of an n-bit hash is only n/2 bits — regardless of how perfect the hash is internally. To claim a given security level, you double the output.

Hash	Output n	Generic collision cost 2n/2	Collision security	Real-world status
MD5	128	264	64-bit	Broken — practical collisions (~218 today)
SHA-1	160	280	80-bit	Broken — SHAttered at ~263 (2017)
SHA-256	256	2128	128-bit	Secure — no collision known
SHA-512	512	2256	256-bit	Secure
SHA3-256	256	2128	128-bit	Secure (sponge, not Merkle–Damgård)

So "SHA-256 gives 128-bit security" is not a coincidence of naming — it is the birthday bound. The same logic reshapes design elsewhere: authenticated-encryption schemes worry about 2^n/2 block collisions (why AES-GCM caps data per key), and truncating a hash to t bits drops collision security to t/2, which is why short "checksum" tags are fine for accidental errors but useless against an adversary.

Implementation: a birthday collision finder in Python

To make the 2^n/2 square-root real, we truncate a real hash to a small number of bits so a collision is findable in milliseconds, then measure how many samples it took. Both the table method and the memoryless Pollard-rho method are shown.

import hashlib, os, math

def H(msg: bytes, bits: int) -> int:
    """Real SHA-256 truncated to `bits` bits — a toy n-bit hash."""
    d = hashlib.sha256(msg).digest()
    full = int.from_bytes(d, "big")
    return full & ((1 << bits) - 1)

# ---- Method 1: table-based birthday attack, O(2^(n/2)) time & memory ----
def birthday_collision(bits: int):
    seen = {}                       # digest -> message
    tries = 0
    while True:
        m = os.urandom(16)
        h = H(m, bits)
        tries += 1
        if h in seen and seen[h] != m:
            return seen[h], m, h, tries   # collision found
        seen[h] = m

# ---- Method 2: Pollard's rho, same O(2^(n/2)) time but O(1) memory ----
def rho_collision(bits: int, start: int = 12345):
    def f(x): return H(x.to_bytes(8, "big"), bits)   # iterate the hash
    # Phase 1: Floyd cycle detection — tortoise speed 1, hare speed 2.
    tortoise, hare = f(start), f(f(start))
    while tortoise != hare:                          # find a point on the cycle
        tortoise, hare = f(tortoise), f(f(hare))
    # Phase 2: reset tortoise to `start`, advance BOTH at speed 1. The two
    # distinct inputs that step into the shared meeting node collide.
    tortoise = start
    while f(tortoise) != f(hare):
        tortoise, hare = f(tortoise), f(hare)
    if tortoise != hare:
        return tortoise, hare   # two distinct preimages of one digest
    return rho_collision(bits, start + 1)   # rare tail-length-0 case: retry

if __name__ == "__main__":
    n = 32
    x, y, h, tries = birthday_collision(n)
    expected = 1.2533 * 2 ** (n / 2)          # sqrt(pi * N / 2)
    print(f"collision on {n}-bit hash after {tries} tries "
          f"(birthday estimate ~{expected:,.0f})")
    print(f"  H(x) = H(y) = {h:#x}")

Run it and the observed tries hovers near 1.25·216 ≈ 82,000 for a 32-bit hash — square-root behaviour, not 2³². Bump n to 64 and the table method exhausts RAM long before it finishes, which is exactly why the rho variant matters at cryptographic scale.

Common misconceptions and pitfalls

• "A 256-bit hash gives 256-bit collision security." No — 128-bit. Halve the output for collision resistance. Only preimage resistance keeps the full n bits.
• "MD5 was broken by a birthday attack." The birthday bound (2⁶⁴) set the ceiling, but Wang et al.'s 2004 differential cryptanalysis found MD5 collisions at ~2³⁷, far below it. Birthday cost is the worst case for a good hash; broken hashes fall much faster.
• "Adding a salt fixes it." A per-signature random salt the attacker cannot predict does defeat the offline collision search, but salting a fundamentally weak hash like SHA-1 does not restore its lost 160 → 80 bit margin. Output length is the real dial.
• "Collisions and preimages are the same weakness." They are not — see the table above. A hash can be collision-broken (MD5) yet still preimage-secure. Whether that matters depends entirely on your protocol.
• "Truncating a strong hash is safe." Truncating SHA-256 to 96 bits leaves only 48-bit collision security — a birthday attack away. Never truncate below 2× your target.
• "HMAC needs a collision-resistant hash." HMAC's security rests on the hash's PRF/keyed properties, not collision resistance, so HMAC-MD5 and HMAC-SHA-1 remained secure long after plain-hash collisions appeared. Use the right property for the right job.

A short history

The idea traces to Gideon Yuval's 1979 note "How to Swindle Rabin," which sketched the signature-forgery attack and named the square-root cost. For two decades it was a theoretical bound. Then in 2004 Xiaoyun Wang and collaborators shattered the assumption that real hashes meet only the generic bound, producing MD5 collisions cheaply; a 2008 team used a chosen-prefix MD5 collision to mint a rogue CA certificate, briefly holding a key that could impersonate any HTTPS site. SHA-1's turn came in 2017 when Google and CWI's SHAttered produced two distinct PDFs sharing a SHA-1 digest at ~2⁶³ work, and 2020's chosen-prefix SHA-1 attack dropped the cost enough to threaten PGP web-of-trust keys. Each break followed the same script the birthday attack wrote: collisions are where hashes die first.