Course contentsShow
← Security
Lesson 202 of 3,0525. Cryptographic Hashing and MACsFree lesson

The Birthday Paradox and Collision Probability

Understanding how birthday attacks reduce collision-finding complexity and implications for hash output size.

The Birthday Paradox and Collision Probability

You'll learn how the birthday paradox drastically lowers the number of hash attempts needed to find a collision, and why this forces us to use larger hash outputs.

The Surprising Math Behind Birthday Attacks

You've learned that collision resistance means it should be computationally infeasible to find two different inputs that produce the same hash output. But here's the twist: finding any collision is much easier than finding a collision with a specific target hash.

This is where the birthday paradox comes in. In a room of just 23 people, there's a 50% chance two share the same birthday—far fewer people than the 365 days in a year! Why? Because you're comparing everyone to everyone, not looking for one specific date.

How This Applies to Hash Functions

For a hash function producing n-bit outputs (meaning 2^n possible values):

  • Brute-force preimage attack: You'd need roughly 2^n attempts to find an input matching a specific hash
  • Birthday attack for collisions: You only need roughly 2^(n/2) attempts to find any two inputs that collide

This square-root relationship is devastating. A 128-bit hash seems secure with 2^128 possible outputs, but a birthday attack needs only about 2^64 attempts—potentially feasible with modern computing power.

Real-World Implications

This is why:

  • MD5 (128-bit) is broken: 2^64 operations are achievable
  • SHA-1 (160-bit) is deprecated: 2^80 is becoming reachable
  • SHA-256 is recommended: 2^128 collision resistance provides adequate security margin
  • SHA-512 offers even stronger protection: 2^256 collision resistance

The birthday paradox doesn't break hash functions by itself, but it cuts their effective security strength in half, forcing designers to double the output size.

Key Takeaway: The birthday paradox reduces collision-finding complexity from 2^n to 2^(n/2), which is why secure hash functions need at least 256-bit outputs to maintain 128-bit collision resistance against birthday attacks.