Birthday Paradox & Hash Collisions

Birthday Paradox and Hash Collisions

How many people must be in a room before two of them share a birthday? Surprisingly, only 23 people are needed for a >50% chance. This counter-intuitive result — the birthday paradox — directly determines the security of hash functions.

Birthday Attack on Hash Functions

If a hash function produces $n$-bit outputs ($2^n$ possible values), how many random inputs do we need before finding two with the same hash?

The birthday paradox gives us:

$P(\text{collision after } k \text{ hashes}) \approx 1 - e^{-k(k-1)/(2 \cdot 2^n)}$

For a 50% collision probability, the threshold is approximately:

$k \approx \sqrt{2 \cdot 2^n \cdot \ln 2} \approx 1.177 \cdot 2^{n/2}$

Implications for Hash Security

Rule of thumb: an $n$-bit hash provides only $n/2$ bits of collision resistance.

Your Task

Implement:

• birthday_probability(n, hash_bits) — probability of at least one collision among $n$ hashes of size hash_bits bits: $1 - e^{-n(n-1)/(2 \cdot 2^{\text{hash\_bits}})}$
• collision_threshold(hash_bits, probability=0.5) — minimum $n$ for collision probability $\geq p$: $\lceil \sqrt{2 \cdot 2^{\text{hash\_bits}} \cdot \ln(1/(1-p))} \rceil$

Use import math for math.exp, math.log, math.sqrt, math.ceil.