The birthday paradox breaks the internet

Breaking a 128-bit hash function does not take $2^{128}$ attempts. It takes about $2^{64}$ — the difference between 800 million times the age of the universe and about seven months on decent hardware. The gap between those two numbers is not a flaw in any particular algorithm. It is the birthday paradox — the same party trick that finds a shared birthday in a room of 23 people — scaled up until it snaps real cryptography. In this paper we derive the general rule behind the trick, watch it kill a hash function that once secured much of the internet, and see how it quietly dictates the key sizes protecting your bank login today.

I. 23 people, 253 chances

First, the party trick, in one paragraph. In the original article we showed that in a room of just 23 people, the probability that two share a birthday is 50.7%. The intuition repair is that matches live on pairs, not people: 23 people form $\binom{23}{2} = 253$ pairs, and each pair is a fresh $\frac{1}{365}$ lottery ticket. The number of pairs grows with the square of the group size, so coincidences arrive absurdly early.

Cryptographers looked at this and asked the productive question: what happens if the "days of the year" number is not 365 but $2^{128}$?

II. Why collisions arrive at the square root

Let us redo the birthday calculation for a general universe of $N$ equally likely values — think of $N$ boxes and $n$ balls thrown in at random. Following the same complementary-counting recipe as before, the probability that all $n$ balls land in distinct boxes is

$$P(\text{no collision}) = \left(1 - \frac{1}{N}\right)\left(1 - \frac{2}{N}\right)\cdots\left(1 - \frac{n-1}{N}\right)$$

Now one A-level approximation unlocks everything: for small $x$, $1 - x \approx e^{-x}$. Each factor becomes an exponential, and multiplying exponentials means adding the exponents — and the exponents sum to a triangle number:

$$P(\text{no collision}) \approx e^{-\frac{1}{N}(1 + 2 + \cdots + (n-1))} = e^{-\frac{n(n-1)}{2N}} \approx e^{-\frac{n^2}{2N}}$$

That exponent $\frac{n^2}{2N}$ is just our pairs picture in disguise: roughly $\frac{n^2}{2}$ pairs, each colliding with probability $\frac{1}{N}$. Setting the no-collision probability to one half and solving:

$$e^{-n^2/2N} = \frac{1}{2} \quad\Longrightarrow\quad n = \sqrt{2 \ln 2 \cdot N} \approx 1.1774 \sqrt{N}$$

This is the square-root rule: in a universe of $N$ possibilities, you need only about $1.18\sqrt{N}$ random samples for a 50% chance of a repeat. Sanity check against the party: $1.1774 \times \sqrt{365} \approx 22.5$ — round up and there is the famous 23, recovered from a formula that never mentioned birthdays.

The square root is the whole story. It means the effective size of any collision problem is not $N$ but $\sqrt{N}$ — and square-rooting a number halves its count of digits. A billion feels enormous; its square root is a modest 31,623. Any programmer who has assigned random 9-digit IDs has met this monster personally: with $N = 10^9$ possible IDs, the rule says a repeat becomes more likely than not after just $1.1774 \times \sqrt{10^9} \approx 37{,}000$ of them — the ID space felt a billion deep, but it behaves as if it were thirty-seven thousand deep. Halving digits, we are about to see, means halving security.

III. Why 128 bits is really 64

A cryptographic hash function takes any input — a password, a contract, the complete works of Shakespeare — and crunches it into a fixed-size fingerprint, say 128 bits. Two properties matter here: the output should look random, and it should be infeasible to find two different inputs with the same fingerprint. Such a pair is called a collision, and collisions are catastrophic: if two documents hash identically, a digital signature on one is a valid signature on the other.

How hard is it to find a collision in a 128-bit hash? There are $N = 2^{128}$ possible fingerprints, so intuition says on the order of $2^{128}$ attempts — about $3.4 \times 10^{38}$. At a trillion hashes per second that takes around $10^{19}$ years, roughly 800 million times the age of the universe. Safe forever, surely.

But the attacker is not trying to match one specific fingerprint — she needs any two inputs that agree, exactly as the room needs any two people to share a birthday, not someone matching yours. The square-root rule applies:

$$n \approx 1.1774 \times \sqrt{2^{128}} = 1.1774 \times 2^{64} \approx 2.2 \times 10^{19}$$

At the same trillion hashes per second, $2^{64}$ attempts take about seven months. The birthday paradox has converted "never" into "a research budget". This is the birthday attack, and note what it needed: no cleverness, no flaw in the algorithm — just patience and the mathematics of pairs. Every hash function ever designed offers at most half its output length in collision security, as a law of nature.

IV. How MD5 died

This is not theoretical. MD5, designed in 1991, was for a decade the internet's favourite fingerprint, with its 128-bit output and its implied $2^{64}$ birthday bound. Then, at the CRYPTO conference in August 2004, Xiaoyun Wang and colleagues stunned the field by presenting actual colliding pairs — two different inputs with identical MD5 fingerprints — found not by birthday brute force but by an analytic attack exploiting MD5's internal structure, at a cost far below the birthday bound [1]. The birthday bound is the ceiling mathematics guarantees any hash; Wang showed MD5 did not even reach its own ceiling.

The truly frightening demonstration came in December 2008. A team including Alexander Sotirov and Marc Stevens used a cluster of about 200 PlayStation 3 consoles to compute a chosen-prefix MD5 collision: two certificates with the same fingerprint, one an ordinary website certificate that a commercial certificate authority would happily sign, the other a rogue certificate-authority certificate [2]. The CA duly signed the harmless-looking one — and because the fingerprints matched, its signature was equally valid on the rogue twin, giving the team the power, in principle, to impersonate any secure website on the internet. They disclosed responsibly, and MD5 was finally evicted from certificate signing. Its 160-bit successor SHA-1 (birthday bound $2^{80}$) walked the same road: Google and CWI Amsterdam published the first real SHA-1 collision in 2017, two working PDF files with one fingerprint, at a cost of about $2^{63}$ operations — again under the birthday bound, again ending an era.

V. Why SHA-256 has 256 bits

Now the design logic of modern cryptography falls out in one line. If you want an attacker to face $2^{128}$ work — the modern gold standard of "not before the Sun burns out" — then, because birthday attacks halve everything, your hash output must be twice that: 256 bits. That is the entire reason SHA-256 is sized as it is; the name records the birthday paradox's toll. The same doubling rule echoes across the field:

• Hash outputs are twice the target security level: SHA-256 for 128-bit security, SHA-512 for 256-bit.
• Old 64-bit block ciphers such as Triple-DES fall to birthday collisions among their ciphertext blocks after only $2^{32}$ blocks — about 34 GB, a few hours of traffic on a busy connection. This is the real 2016 "Sweet32" attack [3], and it is why modern ciphers use 128-bit blocks.
• Random session tokens and IDs are sized so that even $\sqrt{N}$ stays out of reach — designers budget for the square root, never for $N$ itself.

For scale: a well-shuffled deck of cards has $52! \approx 2^{225.6}$ orderings — which is why every proper shuffle is a brand-new deck, comfortably beyond even the birthday-halved reach of any conceivable attacker. Nature has no trouble making spaces big enough; engineers just have to remember to square them.

VI. A ceiling, never a floor

One approximation, $1 - x \approx e^{-x}$, took us from a party trick to the design rules of the internet: in any universe of $N$ equally likely values, repeats arrive after about $1.18\sqrt{N}$ samples — 23 people for 365 birthdays, $2^{64}$ attempts for a 128-bit hash. The honest caveats cut in both directions. Our rule assumed perfectly uniform outputs; real hashes like MD5 fell even faster, because analytic attacks tunnelled below the birthday floor — the square-root rule is a guaranteed ceiling on security, never a floor. And a plain birthday attack finds some collision, not one involving a document of the attacker's choosing — which is why the 2008 team needed the cleverer, costlier chosen-prefix variant. But the headline stands: the mathematics that makes two classmates share a birthday is the same mathematics that decided, decades in advance, exactly how many bits your bank's certificate would need. The paradox scaled; the internet had to adjust.

---

References:

[1] Xiaoyun Wang and Hongbo Yu, "How to Break MD5 and Other Hash Functions," Advances in Cryptology — EUROCRYPT 2005 (Springer, 2005).

[2] Marc Stevens, Alexander Sotirov, Jacob Appelbaum, Arjen Lenstra, David Molnar, Dag Arne Osvik, and Benne de Weger, "Short Chosen-Prefix Collisions for MD5 and the Creation of a Rogue CA Certificate," Advances in Cryptology — CRYPTO 2009 (Springer, 2009).

[3] Karthikeyan Bhargavan and Gaëtan Leurent, "On the Practical (In-)Security of 64-bit Block Ciphers: Collision Attacks on HTTP over TLS and OpenVPN," ACM CCS 2016.

Note: Attack timings assume a trillion hash evaluations per second — roughly a modest GPU cluster today; dedicated hardware moves faster, which only strengthens the case for the 256-bit margin.