The Birthday Bound

Symptom

You need a short ID for uploads. Eight hex characters feels generous, so you take the first 32 bits of a hash and move on.

At about 80,000 uploads, two files collide, and one of them silently overwrites the other, and the bug report says the customer’s invoice contains someone else’s line items.

Or: you generate a nonce per session with 64 bits of randomness. Nonces must never repeat. You reason that $2^{64}$ is astronomically large, and it is, and you will still see a repeat after about five billion sessions, which a busy service reaches.

Or the git version, which is the famous one: SHA-1 is 160 bits, and yet everyone agreed to migrate, and the reason was not that anyone had enumerated $2^{160}$ hashes.

Pigeonhole (T001) told you collisions exist. It said nothing about when. The answer is much sooner than anyone’s intuition, and the shape of the answer is a square root.

Statement

With $N$ equally likely values and $m$ items drawn uniformly at random, a collision becomes more likely than not once $m \approx 1.177\sqrt{N}$.

The name comes from the classroom version: in a room of 23 people, two share a birthday with probability above one half. $N = 365$, and $1.177\sqrt{365} \approx 22.5$.

The engineering form is the one to memorize:

The headline: an $n$-bit hash gives you $n/2$ bits of collision resistance. A 128-bit hash collides after about $2^{64}$ items. Half your bits are gone before you start, and this is why every collision-resistance number you have ever read is half the digest length.

Argument

Compute the probability that all $m$ items are distinct, which is easier, and subtract.

Draw items one at a time. The first lands anywhere. The second must avoid 1 of $N$ values, so it succeeds with probability $(N-1)/N$. The third must avoid 2, and so on. The $k$-th item must avoid $k-1$ occupied values:

$$P(\text{all distinct}) = \prod_{k=1}^{m-1}\left(1 - \frac{k}{N}\right)$$

Now use $1 - x \le e^{-x}$, which is the standard move and is tight for small $x$:

$$P(\text{all distinct}) \;\le\; \prod_{k=1}^{m-1} e^{-k/N} = \exp\left(-\frac{1}{N}\sum_{k=1}^{m-1} k\right) = \exp\left(-\frac{m(m-1)}{2N}\right)$$

So

$$P(\text{collision}) \;\ge\; 1 - e^{-m(m-1)/2N} \;\approx\; 1 - e^{-m^2/2N}$$

Set that to $1/2$ and solve: $m^2/2N = \ln 2$, giving $m = \sqrt{2\ln 2},\sqrt{N} \approx 1.177\sqrt{N}$. $\blacksquare$

Why the square root, in one sentence. Collisions are about pairs, not items. With $m$ items there are $\binom{m}{2} \approx m^2/2$ pairs, each colliding with probability $1/N$, so the expected number of collisions is $m^2/2N$ — and this is just linearity of expectation (T007), which needs no independence between the pairs even though the pairs plainly overlap. Set the expected count to 1 and you get $m \approx \sqrt{2N}$ directly. Intuition fails here because people count items and the mathematics counts pairs, and pairs grow quadratically.

A worked number, because the abstraction hides the shock. Take a 32-bit hash, $N = 2^{32} \approx 4.3 \times 10^9$. Naive intuition says you are safe for billions of items. The bound says $1.177\sqrt{2^{32}} \approx 77{,}000$. Seventy-seven thousand. That is a medium-sized S3 bucket, and it is the failure in the opening section. At the $2^{16} = 65{,}536$ mark you are already at roughly a 40% chance.

Digest	$N$	50% collision at
32-bit	$2^{32}$	$\approx 2^{16}$ = 77 thousand
64-bit	$2^{64}$	$\approx 2^{32}$ = 5 billion
128-bit (MD5, UUIDv4)	$2^{128}$	$\approx 2^{64}$
160-bit (SHA-1)	$2^{160}$	$\approx 2^{80}$
256-bit (SHA-256)	$2^{256}$	$\approx 2^{128}$

Forbids

Short hashes for content addressing. Any scheme where a collision means data loss needs $2 \times$ the bits you would naively pick. Git’s 160-bit SHA-1 gives 80 bits of collision resistance, which was comfortable in 2005 and is why the migration to SHA-256 happened.

Reusing a 64-bit nonce across a long-lived key. AES-GCM’s 96-bit nonce allows about $2^{48}$ messages before random selection becomes unsafe, which is exactly why the specification tells you to use a counter rather than random values when you can.

“We’ll truncate the hash to save space, it’s still random.” Truncating to $n$ bits caps collision resistance at $2^{n/2}$ regardless of how strong the underlying function is. The truncation, not the algorithm, sets the bound.

Trusting a 128-bit digest against a motivated adversary. $2^{64}$ operations is not out of reach for a well-funded attacker, which is why MD5 and SHA-1 are dead for signatures — and note that SHA-1 actually fell to a cryptanalytic attack cheaper than $2^{80}$, so the birthday bound is the ceiling on security, never a floor.

Assuming a “random enough” 53-bit float ID is safe. JavaScript’s Number.MAX_SAFE_INTEGER is $2^{53}$, so IDs generated as random doubles collide after about $2^{26.5} \approx 95$ million — reachable by a single large table. This is a live failure mode wherever an ID crosses a JSON boundary, because the 64-bit value the backend generated is not the value the frontend received.

Does not forbid

It does not mean UUIDv4 is unsafe, and this is where the theorem gets misused to justify real engineering waste. “The birthday bound says collisions happen at $\sqrt{N}$, so 122 random bits is only 61 bits of safety, so we need a central ID service” is an argument that has cost teams a database dependency they did not need. Run the number: 61 bits is $2^{61} \approx 2.3 \times 10^{18}$ UUIDs before a 50% chance. Generate a billion a second and you wait about 73 years. The bound is real, the halving is real, and the result is still comfortably beyond any application. The correct response to a factor of two in the exponent is to check the arithmetic, not to add a coordination point.

It does not apply to a counter. This is the most useful exemption in the post and the most often missed. The bound is about random selection. A monotonic counter, a database sequence, a Snowflake ID with a machine number and a timestamp, or an AES-GCM nonce driven by a counter never collides at all, by construction. If you can afford the coordination — and within one process you always can — you get $N$ values from $n$ bits instead of $\sqrt{N}$, which is a free doubling of your effective width. Reach for randomness only when you cannot coordinate.

It does not mean a collision is a security break. Collision resistance and preimage resistance are different properties with different bounds. Finding some pair that collides takes $2^{n/2}$; finding a message that hashes to a specific given value takes $2^n$, with no birthday speedup, because you are no longer free to choose both sides. So MD5 is thoroughly broken for certificates (where an attacker crafts both documents) and yet an MD5 preimage attack still does not exist. When someone says a hash is broken, ask which property.

It does not apply when the values are not uniform. The bound assumes uniform selection. Real hash functions on real data are close enough to uniform for the estimate to hold, but a bad hash — one with structure, like using the low bits of an auto-increment ID, or a hash the adversary can steer — collides very much sooner. Uniformity is the assumption that makes the square root a best case, not a worst case. Algorithmic complexity attacks work exactly by breaking it.

It does not say a collision has occurred, only when to expect one. This inverts pigeonhole’s failure mode and is worth keeping straight: T001 says a collision exists somewhere in the input space and is silent about probability; the birthday bound says nothing about existence and gives you the probability. Neither one tells you your specific dataset has collided. That takes checking.

Boundary

• Counters and coordination. Covered above and worth repeating as the first boundary because it eliminates the problem rather than pricing it. No randomness, no birthday bound.
• Widen the space. Every bit you add doubles $N$ and multiplies the collision threshold by $\sqrt{2}$. Bits are cheap; the standard advice to use 256 bits when you want 128 bits of security is this arithmetic and nothing more.
• Detect instead of avoid. Content-addressed stores can verify on write: if the digest is present, compare the bytes. Git does this. The collision becomes a detectable event rather than a silent corruption, which changes the failure from data loss to an error message.
• The other direction — deliberately colliding. Bloom filters and HyperLogLog want collisions and budget for them; the birthday arithmetic is what sizes the filter. Rainbow tables and Pollard’s rho use the square root as an attack, finding collisions in $O(\sqrt{N})$ time and constant memory via cycle detection, which is why the memory-free version of the bound is the one cryptographers quote.
• Where the square root is too pessimistic. Bernstein’s point in the reading below: a $2^{64}$ attack requires not just $2^{64}$ operations but the memory and communication to correlate them, and a parallel attacker’s real cost curve is worse than the operation count suggests. The bound is exact about probability and only an approximation of cost.

Read next