We use essential cookies to run the site (session, security, and your theme/language preferences). With your permission we also load embedded third-party content, such as YouTube videos. Cookie Policy
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 output space tries, not the full output space. For a 128-bit hash that means 264 operations, not 2128. 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.
Try It: Find a Collision
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 65536≈256 tries.
<p class="hint">A <b>toy 16-bit hash</b> (FNV-1a folded to 16 bits) maps each string to a value 0–65535. The birthday attack finds a collision in ~321 tries on average — not the 65536 a naive search would need.</p>
<div class="stats-row">
<div class="stat-box"><div class="stat-val" id="tries">0</div><div class="stat-label">Tries</div></div>
<div class="stat-box"><div class="stat-val" id="expected">~321</div><div class="stat-label">Expected</div></div>
<div class="stat-box"><div class="stat-val" id="space">65536</div><div class="stat-label">Hash space</div></div>
</div>
<div id="collision-box" class="collision-box hidden">
<div class="coll-title">Collision found!</div>
<div class="coll-row"><span class="label">Input A:</span><span id="ca" class="mono"></span></div>
<div class="coll-row"><span class="label">Input B:</span><span id="cb" class="mono"></span></div>
<div class="coll-row"><span class="label">Hash:</span><span id="ch" class="mono hash-val"></span></div>
</div>
<div class="btns">
<button id="start" type="button">Start attack</button>
<button id="reset" type="button" class="ghost">Reset</button>
</div>
<canvas id="chart" width="440" height="120"></canvas>
const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Toy 16-bit hash: FNV-1a (32-bit) folded to 16 bits by XOR of the two halves.
// This distributes 6-char alphanumeric strings uniformly across 0-65535, so
// the birthday attack needs ~sqrt(pi * 65536 / 2) ≈ 321 tries on average —
// exactly the birthday bound prediction for a 16-bit (2^16 = 65536) output.
const N = 65536;
const EXPECTED = Math.round(Math.sqrt(Math.PI * N / 2)); // ~321
function toyHash(s) {
let h = 0x811c9dc5; // FNV-1a offset basis (32-bit)
for (let i = 0; i < s.length; i++) {
h ^= s.charCodeAt(i);
// FNV prime multiplication (32-bit, unsigned)
h = (Math.imul(h, 0x01000193)) >>> 0;
}
// XOR-fold to 16 bits
return ((h >>> 16) ^ (h & 0xffff)) & 0xffff;
}
// Generate a random 6-char alphanumeric string
const CHARS = 'abcdefghijklmnopqrstuvwxyz0123456789';
function randStr() {
let s = '';
for (let i = 0; i < 6; i++) s += CHARS[Math.floor(Math.random() * CHARS.length)];
return s;
}
let running = false;
let raf = null;
let seen = new Map(); // hash -> input string
let tries = 0;
const MAX_CHART = 88; // chart x-axis sample points
const triesEl = document.getElementById('tries');
const collBox = document.getElementById('collision-box');
const caEl = document.getElementById('ca');
const cbEl = document.getElementById('cb');
const chEl = document.getElementById('ch');
const startBtn = document.getElementById('start');
const resetBtn = document.getElementById('reset');
const canvas = document.getElementById('chart');
const ctx = canvas.getContext('2d');
document.getElementById('expected').textContent = '~' + EXPECTED;
function drawChart() {
const W = canvas.width, H = canvas.height;
ctx.clearRect(0, 0, W, H);
const maxT = Math.max(tries + 50, EXPECTED * 2.5, 200);
// Draw theoretical birthday probability curve: P(k) = 1 - prod_{i=0}^{k-1}(N-i)/N
// Approximated as 1 - exp(-k*(k-1)/(2*N))
ctx.beginPath();
ctx.strokeStyle = '#1d3557';
ctx.lineWidth = 1.5;
ctx.setLineDash([4, 3]);
for (let x = 0; x <= MAX_CHART; x++) {
const k = Math.round((x / MAX_CHART) * maxT);
const p = 1 - Math.exp(-k * (k - 1) / (2 * N));
const px = (x / MAX_CHART) * W;
const py = H - 6 - p * (H - 16);
if (x === 0) ctx.moveTo(px, py); else ctx.lineTo(px, py);
}
ctx.stroke();
ctx.setLineDash([]);
// Vertical line at EXPECTED
const expPx = (EXPECTED / maxT) * W;
ctx.beginPath();
ctx.strokeStyle = '#e6394688';
ctx.lineWidth = 1;
ctx.setLineDash([3, 3]);
ctx.moveTo(expPx, 4);
ctx.lineTo(expPx, H - 4);
ctx.stroke();
ctx.setLineDash([]);
// Vertical line at actual tries (if collision found)
if (!running && tries > 0) {
const actualPx = Math.min((tries / maxT) * W, W - 2);
ctx.beginPath();
ctx.strokeStyle = '#27ae60';
ctx.lineWidth = 2;
ctx.moveTo(actualPx, 8);
ctx.lineTo(actualPx, H - 4);
ctx.stroke();
}
// Legend
ctx.font = '10px system-ui, sans-serif';
ctx.fillStyle = '#1d3557';
ctx.fillText('--- P(collision by try k)', 6, 14);
ctx.fillStyle = '#c92f3c';
ctx.fillText(fmt('| expected ~%EXPECTED%', { EXPECTED: EXPECTED }), 6, 26);
if (!running && tries > 0) {
ctx.fillStyle = '#1a7a40';
ctx.fillText(fmt('| actual: %tries%', { tries: tries }), 6, 38);
}
}
function runStep() {
if (!running) return;
// Run up to 20 tries per animation frame for responsive animation
for (let i = 0; i < 20 && running; i++) {
const s = randStr();
const h = toyHash(s);
tries++;
if (seen.has(h)) {
// Collision found!
running = false;
startBtn.disabled = false;
const prev = seen.get(h);
triesEl.textContent = tries;
caEl.textContent = prev;
cbEl.textContent = s;
chEl.textContent = '0x' + h.toString(16).toUpperCase().padStart(4, '0') + ' (' + h + ')';
collBox.classList.remove('hidden');
drawChart();
console.log('Collision found after', tries, fmt('tries (expected ~%EXPECTED%)', { EXPECTED: EXPECTED }));
console.log('Input A:', prev, '| Input B:', s, '| hash:', h);
console.log(fmt('Verify: hash(A)=%toyHash%, hash(B)=%toyHash2%', { toyHash: toyHash(prev), toyHash2: toyHash(s) }));
return;
}
seen.set(h, s);
}
triesEl.textContent = tries;
drawChart();
raf = requestAnimationFrame(runStep);
}
startBtn.addEventListener('click', () => {
if (running) return;
running = true;
startBtn.disabled = true;
collBox.classList.add('hidden');
raf = requestAnimationFrame(runStep);
});
resetBtn.addEventListener('click', () => {
running = false;
if (raf) cancelAnimationFrame(raf);
seen.clear();
tries = 0;
triesEl.textContent = '0';
collBox.classList.add('hidden');
startBtn.disabled = false;
ctx.clearRect(0, 0, canvas.width, canvas.height);
});
// Draw initial chart axes
drawChart();
Result
Console
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 π⋅65536/2≈321. For a real SHA-256 the same math gives 2128 — huge but exactly half the naive estimate.
The Real Complexity
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(2n) tries for an n-bit hash. Totally impractical for n≥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 2n/2 tries. This needs O(2n/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 Ω(2n/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-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.
Where It Matters
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.
Conclusion
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.
Comments
Loading comments...