What is the birthday paradox, and how does it relate to collision attacks on hash functions?

With only 23 people in a room, there's a >50% chance two share a birthday — and with $\sqrt{n}$ elements, you expect a collision in a space of size n.

* The curve crosses 50% at 23 and ~90% at 40 — collisions appear far sooner than intuition expects. *

The math for birthdays:

• Probability that NO two people among $n$ share a birthday: $\bar{p} = \left(1 - \frac{1}{365}\right) \cdot \left(1 - \frac{2}{365}\right) \cdots \left(1 - \frac{n-1}{365}\right)$
• At $n = 23$: probability of a shared birthday exceeds 50%
• At $n = 40$: probability reaches ~90%

Generalization: In a space of $N$ elements, a collision becomes likely after approximately $\sqrt{N}$ random samples.

Application to hash functions:

• A hash with $n$-bit output has $N = 2^n$ possible values
• Collision expected after $\sqrt{2^n} = 2^{n/2}$ random hashes
• This is why a 128-bit hash only provides 64-bit collision security — far too weak!
• SHA2-256 gives $2^{128}$ collision resistance — still very secure

Tip: The birthday paradox is the theoretical foundation of the birthday attack on hash functions. It's also why the pigeonhole principle guarantees collisions exist — there are infinitely many inputs but only $2^n$ outputs.

Go deeper:

• Birthday problem (Wikipedia) — the full probability derivation and the counter-intuitive 23-people result.
• Birthday attack (Wikipedia) — how that maths becomes the $2^{n/2}$ collision-attack bound.