Birthday Attack

Cryptography · Axiom Academy

LESSON Birthday Attack on Hash Functions Understanding how the birthday paradox enables collision attacks on cryptographic hash functions The birthday paradox states that in a room of just 23 randomly chosen people, there is more than 50% probability that at least two share the same birthday. This counterintuitive result is the foundation of the birthday attack. Number of possible pairs: With n people, there are n(n-1)/2 comparisons. For 23 people, that's 253 pairs to check! Just as birthdays can collide with surprising frequency, hash outputs can collide when we hash many different inputs. The "birthday attack" searches for any two inputs that produce the same hash output. Generate random messages and compute their hashes Store each hash in a lookup table When a hash appears twice, you've found a collision! For a hash function with an n-bit output (2 n possible values), you only need to hash approximately (2 n ) = 2 n/2 random inputs to have a ~50% chance of finding a collision. The probability calculation follows the same pattern as the birthday problem. Let's derive the collision probability for a hash with N possible outputs. Setting P(collision) ≈ 0.5 and solving for k gives us k ≈ 1.177 N. For N = 2 n , this becomes k ≈ 1.177 × 2 n/2 . 4. Security Implications for Hash Design The birthday attack has critical implications for how we design and use cryptographic hash functions. MD5 (128-bit): Only 64-bit collision security → 2 64 operations (~10 19 ) - Broken!

This is the written version of the interactive lesson above. See the full Cryptography course.