The birthday problem, and why 64-bit hashes collide sooner than you think

Why 23 people are enough for a shared birthday, and why a 64-bit hash already collides after about 5 billion items.

Contents

Put $n$ people in a room. How large must $n$ be before two of them probably share a birthday? The answer, 23, surprises people because they compare $n$ to 365. The right comparison is the number of pairs, $\binom{n}{2}$, and that grows quadratically.

The exact probability #

Assume $d$ equally likely days.¹1 Real birthdays are not uniform. Unevenness only makes collisions more likely, so 23 people is enough in real rooms too.  Seat people one at a time; the $i$-th person avoids everyone before them with probability $1 - i/d$. So

$$\Pr[\text{no collision}] \;=\; \prod_{i=0}^{n-1} \left(1 - \frac{i}{d}\right). \tag{1}$$

Using the inequality $1 - x \le e^{-x}$, a consequence of convexity,²2 The function $e^{-x}$ is convex, and $1 - x$ is its tangent line at $x = 0$, so the line lies below the curve.  on each factor of (1) and summing the exponents gives a clean upper bound:

$$\Pr[\text{no collision}] \;\le\; \exp\!\left(-\frac{n(n-1)}{2d}\right). \tag{2}$$

When a collision becomes likely #

Theorem 1 (Square-root law). With $d$ equally likely values and $n(n-1) \ge 2d \ln 2$, two of the $n$ values coincide with probability at least $1/2$. In particular $n \approx \sqrt{2d \ln 2} \approx 1.18\sqrt{d}$ suffices.

Proof. By (2), $\Pr[\text{no collision}] \le \exp(-n(n-1)/2d) \le \exp(-\ln 2) = 1/2$. ∎

For $d = 365$ the condition reads $n(n-1) \ge 505.99\ldots$, and $n = 23$ is the first value that meets it, since $23 \cdot 22 = 506$.

Try it #

Drag the slider to 23 and notice that the curve crosses one half there, then drag it to 57: the probability is already above 99%.

People in the room

Why this matters for hashing #

Replace “birthdays” with “hash values”. A $b$-bit hash has $d = 2^b$ outputs, so by Theorem 1 a collision is more likely than not after about $1.18 \cdot 2^{b/2}$ items. A 64-bit hash, which sounds enormous, gets there after roughly $1.18 \cdot 2^{32} \approx 5$ billion items. That is a normal day for a large database.

import math

def items_until_likely_collision(bits: int) -> float:
    """Smallest n (as a real number) with n^2 >= 2 * 2**bits * ln 2."""
    return math.sqrt(2 * 2**bits * math.log(2))

print(f"{items_until_likely_collision(64):.3e}")  # 5.057e+09

The same square root explains why birthday attacks halve the security of a hash function, and why 128-bit identifiers are the usual choice when collisions must essentially never happen.

1. Real birthdays are not uniform. Unevenness only makes collisions more likely, so 23 people is enough in real rooms too. ↩

2. The function $e^{-x}$ is convex, and $1 - x$ is its tangent line at $x = 0$, so the line lies below the curve. ↩