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

Birthday Attacks and Hash Output Size

Learning how birthday paradox affects hash collision probability and determines minimum secure output sizes.

Birthday Attacks and Hash Output Size

You'll learn: Why hash functions need surprisingly large output sizes to resist birthday attacks.

The Birthday Paradox Strikes Again

Remember the birthday paradox from lesson 202? It showed that collisions happen far sooner than intuition suggests. In a birthday attack, an attacker doesn't need to break preimage resistance—they just need to find any two messages that hash to the same value.

Here's the critical insight: if a hash function outputs n bits, you might expect security up to 2^n operations. Wrong. Due to the birthday paradox, an attacker can find a collision in roughly 2^(n/2) attempts.

Why This Matters for Hash Output Size

Let's use concrete numbers:

  • 64-bit hash output: Collision after ~2^32 attempts (about 4 billion tries) — trivially breakable on modern hardware
  • 128-bit hash output: Collision after ~2^64 attempts — within reach of nation-states
  • 256-bit hash output (like SHA-256): Collision after ~2^128 attempts — currently secure

This is why MD5 (128-bit output) and SHA-1 (160-bit output) are considered broken for collision resistance, even though their preimage resistance might still hold up. Attackers exploited weaknesses and the birthday bound.

Security Rule of Thumb

For n-bit collision resistance security, you need a hash function with 2n-bit output. Want 128-bit security? Use a 256-bit hash. Want 256-bit security? Use a 512-bit hash (like SHA-512).

This exponential relationship is why cryptographic hash functions have such large outputs compared to checksums like CRC32.

Key Takeaway: Birthday attacks reduce collision resistance by the square root, requiring hash outputs twice as large as the desired security level—SHA-256's 256-bit output provides only ~128-bit collision resistance.