The Birthday Attack

How many strangers do you need in a room before two of them share a birthday? Most people guess somewhere around 183 — half of 365. The real answer is just 23. That gap between intuition and reality is called the birthday paradox, and it is the most important piece of probability theory in all of cryptography.

A cryptographic hash function maps any input — a file, a password, a message — to a short, fixed-length fingerprint called a digest. If two different inputs produce the same digest, we call that a collision. Good hash functions make collisions hard to find on purpose: their security guarantee is that finding one should take as long as brute-forcing a safe.

The birthday attack turns that guarantee upside down. Instead of hunting for a specific output, it collects random inputs and watches for any two that match. The mathematics of random collisions means the attack succeeds far sooner than designers expect — in roughly $\sqrt{\text{output space}}$ tries, not the full output space. For a 128-bit hash that means $2^{64}$ operations, not $2^{128}$. For the once-ubiquitous MD5, with 128-bit output, that is catastrophically broken territory.

The attack is a proven lower bound on achievable security: no hash function with n-bit output can ever offer more than n/2 bits of collision resistance, regardless of how cleverly it is designed. It is not a flaw to be patched — it is arithmetic.

The demo below runs a birthday attack on a toy 16-bit hash (sum of char codes, mod 65536). The output space has 65 536 possible values — a naive brute-force search would need to try all of them to guarantee a collision. The birthday attack finds one in roughly $\sqrt{65536} \approx 256$ tries.

<p class="hint">{{hint}}</p>
<div class="stats-row">
  <div class="stat-box"><div class="stat-val" id="tries">0</div><div class="stat-label">{{label_tries}}</div></div>
  <div class="stat-box"><div class="stat-val" id="expected">~321</div><div class="stat-label">{{label_expected}}</div></div>
  <div class="stat-box"><div class="stat-val" id="space">65536</div><div class="stat-label">{{label_hash_space}}</div></div>
</div>
<div id="collision-box" class="collision-box hidden">
  <div class="coll-title">{{coll_title}}</div>
  <div class="coll-row"><span class="label">{{label_input_a}}</span><span id="ca" class="mono"></span></div>
  <div class="coll-row"><span class="label">{{label_input_b}}</span><span id="cb" class="mono"></span></div>
  <div class="coll-row"><span class="label">{{label_hash}}</span><span id="ch" class="mono hash-val"></span></div>
</div>
<div class="btns">
  <button id="start" type="button">{{btn_start}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<canvas id="chart" width="440" height="120"></canvas>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.stats-row { display: flex; gap: .5rem; margin-bottom: .75rem; }
.stat-box { flex: 1; background: #e8eef3; border-radius: 8px; padding: .4rem .6rem; text-align: center; }
.stat-val { font: 700 1.3rem ui-monospace, monospace; color: #1d3557; }
.stat-label { font-size: .72rem; color: #555; margin-top: 2px; }
.collision-box { background: #eafaf1; border: 1.5px solid #27ae60; border-radius: 10px;
                 padding: .6rem .85rem; margin-bottom: .75rem; }
.collision-box.hidden { display: none; }
.coll-title { font-weight: 700; color: #1a7a40; margin-bottom: .4rem; }
.coll-row { display: flex; gap: .5rem; align-items: baseline; margin-bottom: .15rem; font-size: .88rem; }
.label { color: #555; min-width: 62px; }
.mono { font-family: ui-monospace, monospace; word-break: break-all; }
.hash-val { color: #c92f3c; font-weight: 700; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .7rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }
canvas { width: 100%; height: 120px; display: block; border-radius: 6px;
         background: #f5f7f9; border: 1px solid #dde3ea; }

// Code not found

Press Start attack and watch the counter. Two inputs are randomly generated each step and added to a growing table. The moment any two share the same hash, a collision is found and the run stops. Notice how the collision typically appears long before the 65 536 mark — the birthday mathematics predicts the expected number of tries is about $\sqrt{\pi \cdot 65536 / 2} \approx 321$. For a real SHA-256 the same math gives $2^{128}$ — huge but exactly half the naive estimate.

How hard is finding a collision, really? The birthday bound gives the precise answer.

• Naive search: pick a target output T, generate inputs until one hashes to T — this requires $O(2^{n})$ tries for an n-bit hash. Totally impractical for $n \ge 128$.
• Birthday attack: generate random inputs and store their hashes. Stop when any two match. By the birthday bound, a collision appears with high probability after roughly $2^{n/2}$ tries. This needs $O(2^{n/2})$ time and memory.
• The lower bound is tight: it has been proven (Stinson 1994, generalized in many forms) that no algorithm can find collisions in a random oracle with fewer than $\Omega(2^{n/2})$ queries. The birthday attack is essentially optimal.
• Consequences for real hashes:
  • MD5 (128-bit output) → 64-bit collision security → broken. Wang & Yu demonstrated practical collisions in 2004 using differential attacks even faster than the birthday bound.
  • SHA-1 (160-bit output) → 80-bit collision security → broken since 2017 (SHAttered, Google/CWI).
  • SHA-256 (256-bit output) → 128-bit collision security — the security level of the hash is half its output width.
  • SHA-3-256 → same 128-bit collision security by the same reasoning.

This is why modern standards target at least 256-bit output when 128 bits of collision resistance are desired. The birthday bound is not a flaw in any particular algorithm — it is a fundamental limit shared by every hash function, proven for the random oracle model and conjectured to hold for all practical designs. Compare this to factoring, another one-way function whose hardness underpins cryptography, or the broader question of P vs NP that underlies all of it.

The birthday bound is not just a theoretical curiosity — it has shaped (and broken) real systems:

• Digital signature forgery: if you can find two documents with the same hash, you can get a signature on the harmless one and reuse it on the malicious one. MD5 collisions enabled exactly this attack against X.509 certificates in 2008 (Sotirov et al.).
• Protocol replay and HMAC length extension: birthday-style reasoning surfaces in MAC security, where an attacker collecting enough message–tag pairs will eventually find matching tags.
• Hash function deprecation: the birthday bound is why MD5 and SHA-1 are deprecated for collision-sensitive uses (signatures, certificates) even if preimage resistance still holds.
• Output length standards: NIST's recommendation that hash functions targeting k bits of security must produce at least 2k bits of output comes directly from the birthday bound.
• Password hashing: rainbow tables are a time–memory trade-off rooted in birthday-style collision chains — salting defeats them by making each chain independent.
• Blockchain Merkle trees: SHA-256's 128-bit collision resistance is why Bitcoin's double-SHA-256 construction is considered adequate against birthday attacks at current computational scales.

Understanding the birthday bound is prerequisite knowledge for designing secure protocols. Any system that relies on uniqueness of hashes — certificates, commit schemes, random nonces — must be sized with n/2 bits of security in mind, not n.

The birthday attack delivers one of the most important lessons in applied cryptography: security does not scale linearly with output size. Every n-bit hash, no matter how cleverly designed, provides at most n/2 bits of collision resistance — and the birthday bound proves that no hash function can do better.

This is why SHA-256 is described as offering 128-bit collision security, why MD5 was long ago retired from signatures, and why the SHA-3 competition required 256-bit output to meet a 128-bit security target. The paradox is not a bug in any algorithm; it is a mathematical fact about random collisions that designers must respect.

The next time you see a hash length quoted, halve it in your head — that is the collision security budget. And remember the birthday party: nature finds matches far sooner than intuition suggests.