Course contentsShow
← Computer Science
Lesson 2425 of 2,87254. Cryptography FundamentalsFree lesson

The Birthday Paradox and Hash Collisions

Learning how probability theory affects collision resistance and why output size matters.

The Birthday Paradox and Hash Collisions

You'll learn why finding hash collisions is much easier than intuition suggests, and why hash output size is critical.

The Surprising Math of Collisions

The birthday paradox states that in a room of just 23 people, there's over a 50% chance two share the same birthday—far fewer people than the 365 days in a year would suggest. This counterintuitive result stems from comparing every pair of people, not each person to a specific date.

Hash functions face the same phenomenon. If a hash produces n possible outputs, you might think you'd need n tries to find a collision. Wrong! You only need approximately √n attempts to have a good chance of finding two inputs that hash to the same value.

Why Output Size Matters

This is why collision resistance demands large output spaces:

  • A hash function with 64-bit output (2⁶⁴ possible values) needs only about √(2⁶⁴) = 2³² attempts (~4 billion) to likely find a collision—feasible with modern computing power
  • A 128-bit hash requires roughly 2⁶⁴ attempts—much harder but still potentially vulnerable
  • SHA-256 (256-bit output) requires approximately 2¹²⁸ attempts—effectively impossible with current technology

Practical Implications

When evaluating hash function security, remember attackers don't need to find a collision with your specific document—just any two documents that collide. The birthday paradox makes this search space dramatically smaller than it first appears.

This is why deprecated algorithms like MD5 (128-bit output) and SHA-1 (160-bit output) have been broken: 2⁶⁴ and 2⁸⁰ operations respectively became achievable.

Key Takeaway: The birthday paradox shows collision attacks succeed with approximately √n attempts for n possible hash outputs, making large output sizes (256+ bits) essential for collision resistance.