Hash Collision Birthday Paradox Calculator

The birthday paradox states that in a group of just 23 people, there is a 50% chance two share a birthday.
Most people guess something near 183, half of 365, and they are out by a factor of eight. The same math applies to hash functions.

Why collisions matter. A collision occurs when two different inputs produce the same hash output. In hash tables, collisions degrade performance. In cryptography, they can completely break a scheme. The birthday paradox tells us how quickly collisions appear even with large hash spaces.

The probability of at least one collision:

P(collision) ≈ 1 - e^(-n(n-1) / (2 × 2^b))

For small n relative to 2^b, this simplifies to approximately n² / 2^(b+1).

where n is the number of values and b is the hash size in bits.

The 50% collision threshold:

n₅₀ ≈ 1.177 × 2^(b/2)

For a 32-bit hash: n₅₀ ≈ 77,000 values. For a 64-bit hash: n₅₀ ≈ 5.1 billion values. For a 128-bit hash: n₅₀ ≈ 2^64 values, which is out of reach for a generic search. For SHA-256 (256 bits): n₅₀ ≈ 2^128 values.

The practical lesson: a b-bit hash only provides b/2 bits of collision resistance, not b bits.

The birthday bound is a ceiling, not a promise

This is the part that gets misread, and it matters. The formula above tells you how much collision resistance a hash could have at best, assuming its output is indistinguishable from random. A broken hash falls below that line, sometimes catastrophically.

MD5 is the cautionary example. Its 128-bit output puts the birthday bound at 2^64, which nobody has ever needed to reach: Wang’s differential attack in 2004 dropped identical-prefix collisions to seconds on a laptop, and chosen-prefix collisions now cost around 2^39 work. SHA-1’s bound is 2^80 and the SHAttered collision in 2017 landed at about 2^63. In both cases the cryptanalysis beat the birthday bound by orders of magnitude, so quoting 2^64 as “why MD5 is broken” understates the break by roughly fifteen of them.

For a hash with no known structural weakness, SHA-256 among them, the birthday bound is the honest estimate. For a hash with a published break, it is only the number the hash was supposed to deliver.