Birthday Attack
The birthday attack exploits the birthday paradox: after about 2^(n/2) hash computations there is a 50% chance of finding a collision in an n-bit hash, which dictates the required output length.
Purpose
Sets the lower bound on hash output length so that collision search is infeasible.
Mechanism
Birthday paradox: among 23 people there is a 50% chance two share a birthday. For a hash with n-bit output, about 1.177×√(2^n) = 1.177×2^(n/2) random inputs yield a 50% collision probability. Hence a 128-bit hash is insecure at only 2^64 trials.
Use cases
- Hash output length selection
- Digital signature security level
- Certificate lifetime assessment
- Cryptography education
Examples
- Input
128-bit hashOutputCollision found in 2^64 trialsInsecure
Common errors
- Assuming an n-bit hash needs 2^n trials to collide
- Collisions take only 2^(n/2); use outputs of at least 256 bits
Related terms
Collision Resistance
Collision resistance is the property of a hash function that it is infeasible to find two distinct inputs producing the same hash output. The birthday attack dictates the required output length. GLOSSARY
SHA-256
SHA-256 is the 256-bit-output member of the SHA-2 family, widely used in TLS, blockchains, and cryptographic applications, with no known practical attacks. GLOSSARY
MD5
MD5 is a 128-bit cryptographic hash function designed by Ronald Rivest; proven insecure by collision attacks, it is now used only for non-security purposes such as checksums. GLOSSARY