The Party Trick That Sized the Internet

Walk into a room with 23 strangers and bet the host that two of them share a birthday. Pay out if you're wrong. You will win 50.73 percent of the time [S1].

The arithmetic is one line. The probability that nobody matches is 365/365 × 364/365 × … × 343/365, which works out to roughly 0.4927, leaving a 0.5073 chance that at least one pair collides [S1]. Most people, asked to guess, name a number closer to 180 — half of 365, halfway to a guaranteed match. Intuition is off by an order of magnitude.

The reason is a counting trick the brain doesn't natively perform. Asked about birthdays, humans instinctively run a linear search: what are the odds that someone here shares MY birthday? Twenty-two other people, low odds. But the math is solving for the chance that any pair anywhere in the room collides, and 23 people contain C(23,2) = 253 distinct pairs [S1]. The opportunities for a coincidence grow quadratically with the size of the group while the people only grow linearly. The "paradox" is just the gap between those two growth rates, dressed up for a party.

That gap is also, quietly, the load-bearing constraint under every padlock on the internet.

The birthday bound

A cryptographic hash function chews any input into a fixed-length string of bits — 128, 160, 256 — and a "collision" is when two different inputs hash to the same string. Naively, you might assume that finding a collision in an N-bit hash takes about 2^N tries: pick an input, hash it, check whether it matches a specific target, repeat.

But an attacker who just wants ANY collision — two inputs, any two, that happen to land on the same output — is running the birthday problem at scale. They generate random inputs, write down the outputs, and wait for the first repeat. The output space has 2^N "birthdays." By the same pair-counting that doomed your 23-person bet, the first collision appears around 2^(N/2) tries, not 2^N [S2][S3]. This is the birthday bound, and it's why a 128-bit hash like MD5 offers only about 2^64 collision resistance, and a 160-bit hash like SHA-1 offers only about 2^80 [S2][S4].

SHA-256 doesn't exist because cryptographers worry that 128 bits of brute force is too easy; 2^128 operations would boil the oceans. SHA-256 exists because 2^128 is exactly what 256 output bits give you AFTER the eighth-grade probability problem on birthdays takes its square root.

SHAttered

On February 23, 2017, a team from Google and the Dutch research institute CWI published two PDF files. They were visibly different — different colored backgrounds, different content. They had the same SHA-1 hash [S2][S3].

The attack took roughly 2^63.1 evaluations of the SHA-1 compression function — about 9.22 quintillion operations [S2]. Quoted cost: 6,500 CPU-years and 110 GPU-years of compute, somewhere in the rough six-figure neighborhood of EC2 time [S2]. A generic brute-force collision search would have needed about 2^80 evaluations; the SHAttered team's project page notes their attack was "100,000 times faster than the brute force attack that relies on the birthday paradox" [S2].

That last sentence deserves a careful read. The birthday bound is not the difficulty of breaking a hash. The birthday bound is the EASY case — what an attacker with no cleverness at all can do by hashing random junk. SHAttered shaved another five orders of magnitude off that with structured cryptanalysis. The bound is a ceiling on attacker work, not a floor.

MD5 had gone the same way thirteen years earlier. On August 17, 2004, Xiaoyun Wang, Dengguo Feng, Xuejia Lai and Hongbo Yu announced collisions for the full MD5 function, found in about an hour on an IBM p690 cluster [S4]. The generic birthday bound for MD5 was 2^64 operations; Wang's differential attack came in far below it [S4]. By 2008, researchers had used MD5 collisions to forge a rogue Certificate Authority certificate, and the algorithm was a corpse anyone could pose with.

The pattern, across both algorithms, is identical: design a hash with N output bits, advertise something like 2^N security in the popular press, watch it broken at 2^(N/2) by the birthday bound and then at something even lower by actual cryptanalysis. The doubling rule for output length is the only thing keeping the second number, 2^(N/2), still out of reach for SHA-256.

The DNA database that confirmed the math

In 2001, an Arizona crime lab analyst named Kathryn Troyer was testing the state's CODIS database, which then held about 65,493 DNA profiles. She found a 9-locus match between two unrelated men, one white and one Black. The standard random-match probability for that profile was roughly 1 in 754 million [S5][S6].

The press treated it as a freak. The math didn't. A database of 65,493 profiles supports about 2.14 billion pairwise comparisons, and at one-in-754-million per pair the expected probability of at least one match is about 94 percent [S5][S6]. The coincidence was almost mandatory.

When the Arizona database was audited more carefully, Troyer found not one but 122 pairs matching at 9 loci, 20 pairs matching at 10 loci, one pair at 11 loci, and one pair — two brothers — at 12 [S5]. The numbers tracked the birthday-paradox prediction with embarrassing precision.

The forensic-statistics community has been arguing about it since: should juries hear the per-profile rarity (1 in 754 million, sounds damning) or the per-database probability of coincidence (94 percent, sounds like reasonable doubt) [S6]? The disagreement is not about the math. It's about which version of the math people are allowed to hear.

Square root of everything

The deeper move, once you see it: any system with N possible states and random sampling will start producing "coincidental" collisions around √N samples, not N. Hash tables in computer science wedge on it. Cryptographic signatures are sized around it. DNA databases hit it whether prosecutors want them to or not. The same √N curve that makes 23 birthdays collide is the curve that makes 2^80 SHA-1 hashes collide is the curve that makes 65,000 DNA profiles match.

Humans don't have a built-in sense for it because evolution selected for counting individuals, not pairs. We notice the person who looks like our cousin; we don't notice that a crowd of 200 contains 19,900 pairs of strangers, any one of whom MIGHT look like somebody's cousin. The world is fuller of coincidences than the brain budgets for, and almost every spooky "what are the odds" story is the birthday paradox in costume.

There is one historical wrinkle worth keeping. The problem is usually attributed to the British mathematician Harold Davenport, who circulated it as an undergraduate at Manchester around 1927, though the first published version was by Richard von Mises in 1939 [S1][S7]. Davenport himself refused to claim it, "because he could not believe that it had not been stated earlier" [S1][S7]. He had no proof, only a suspicion that a problem this clean must already exist somewhere. A fitting epitaph for the result: even its discoverer assumed someone had collided with it first.