The Birthday Paradox · Sam Schlesinger

Pick people from a crowd, one at a time, and after each arrival ask: do any two people in the room share a birthday? The intuitive guess is something like one hundred and eighty-three, half of three hundred and sixty-five. The actual number is twenty-three.

This is the birthday paradox: not a paradox in the logical sense, just a violation of intuition. It is also the foundation of an entire family of attacks on cryptographic hash functions, and the reason a 256-bit hash gives only 128 bits of collision security.

The question

How many people do you need in a room before two of them share a birthday, with better than even odds?

The intuitive guess is huge, because your birthday only matches each other person with probability $1/365$ . But the question isn’t about you. It’s about any match in the entire room.

Five people

Imagine the room filling up. With five people in it, the chance of any two sharing a birthday is about 2.7%.

Ten people

At ten, it’s around 11.7%. The probability is rising faster than you’d guess: each new person adds a collision opportunity with everyone already in the room. Match candidates grow as $\binom{n}{2}$ , not $n$ .

Twenty-three

At twenty-three, the probability crosses one half. From a pool of 365 possible birthdays, twenty-three people are enough to make a match more likely than not.

Fifty

By fifty, the chance is 97%. Past sixty, you’d be unlucky to not find a match. The collisions, once they start, are everywhere.

The formula

The first person has any birthday. The second person must avoid the first: probability $364/365$ . The third must avoid two: $363/365$ . And so on. Multiply, then subtract from one: that’s the chance of at least one match.

Cryptography

The same calculation applies whenever you’re throwing samples into a finite space. A hash function maps inputs to one of $2^N$ outputs. An attacker hashing random inputs is filling a room with people; the “birthday” is the hash output; a “match” is a collision.

P (match) = 1 - k = 1 \prod n - 1 (1 - \frac{k}{365})

collisions after \approx 2^{N} = 2^{N /2} samples

The calculation, in full

Order the $n$ people $1, 2, \ldots, n$ . The first has any birthday. The second must avoid the first’s birthday: probability $364/365$ . The third must avoid the two existing birthdays: $363/365$ . Continuing, the probability that no two people share a birthday is

P(\text{no match}) \;=\; \prod_{k=1}^{n-1}\!\left(1 - \frac{k}{365}\right).

The probability of at least one match is the complement:

P(\text{match}) \;=\; 1 - \prod_{k=1}^{n-1}\!\left(1 - \frac{k}{365}\right).

Plug in $n = 23$ and you get $0.5073$ . Plug in $n = 50$ and you get $0.9704$ .

A cleaner approximation

For small $x$ , $\ln(1 - x) \approx -x$ . So

\ln P(\text{no match}) \;\approx\; -\sum_{k=1}^{n-1}\frac{k}{365} \;=\; -\frac{n(n-1)}{2 \cdot 365}.

The probability of at least one match crosses $1/2$ when $\,n(n-1)/(2 \cdot 365) \approx \ln 2$ , or $n \approx \sqrt{2 \cdot 365 \cdot \ln 2} \approx 22.5$ .

The general rule: in a uniform space of $N$ possibilities, expect a collision after roughly $\sqrt{N}$ samples, not $N$ .

Why cryptographers care

A hash function $H$ maps arbitrary inputs to one of $2^N$ outputs. If $H$ is well-designed, finding two distinct inputs $x \neq y$ with $H(x) = H(y)$ , a collision, should be hard. The birthday bound tells us how hard.

After $\sqrt{2^N} = 2^{N/2}$ random hash queries, an attacker expects to have seen a collision by pure coincidence. So an $N$ -bit hash function offers only $N/2$ bits of collision security, not $N$ .

This is why SHA-256 is the standard for “128 bits of security”: its 256-bit output gives $2^{128}$ birthday-attack resistance against collisions. It is also why SHA-1 (160 bits → 80 bits of collision security) was retired ahead of schedule when SHAttered showed an $\approx 2^{63}$ -cost attack was practical.

The same square-root rule shows up in Pollard’s $\rho$ for discrete logarithms, in distinguishability bounds for keyed PRFs under random sampling, and in the design of Merkle-tree commit schemes. Once you see the birthday in a crowd, you start seeing it everywhere.