What is a birthday attack?
A birthday attack is a method of finding a hash collision: two different inputs that produce the same digest. It doesn't try to match one particular hash value. Instead the attacker generates huge numbers of candidate inputs and waits for any two of them to land on the same digest, which happens far sooner than intuition suggests. The name comes from the birthday paradox in probability, and the same arithmetic sets the practical limit on how collision-resistant any hash function, or any fixed-size value, can be.
The birthday paradox
In a group of just 23 people, the chance that at least two share a birthday is slightly over 50 percent, and with 70 people it passes 99.9 percent. The number of pairs grows much faster than the number of people: 23 people form 253 pairs, and every pair is another chance at a match. The general rule is that among N equally likely values, a repeat becomes likely after roughly the square root of N picks.
Why an n-bit hash gives only n/2 bits of collision resistance
A hash with an n-bit output has 2^n possible digests, so the square-root rule says a collision is expected after about 2^(n/2) hashes. Matching one specific digest, a second-preimage attack, still costs about 2^n attempts. Halving the exponent is the entire attack.
| Digest length | Example | Generic collision cost |
|---|---|---|
| 64 bits | Truncated hashes, legacy checksums | About 2^32, a few billion hashes |
| 128 bits | MD5 | About 2^64 |
| 160 bits | SHA-1 | About 2^80 |
| 256 bits | SHA-256, SHA3-256 | About 2^128 |
A worked number shows the scale. For a 64-bit value, even odds of a collision arrive after about 5 billion hashes, a modest job for ordinary hardware. For a 256-bit digest the same search needs around 2^128 hashes, beyond any foreseeable computing budget. MD5 and SHA-1 are worse off than their rows suggest, because cryptanalysis found collisions far below the birthday bound.
How an attacker uses a collision
The classic target is a digital signature, which covers a document's hash rather than the document itself. The attacker writes a harmless contract and a fraudulent one, then produces millions of invisible variations of each, with extra spaces, line breaks or hidden metadata, hashing every version. Once a harmless variant and a fraudulent variant share a digest, the attacker gets the victim to sign the harmless one, and the signature is just as valid on its fraudulent twin. Gideon Yuval described this technique in 1979.
The same math applies outside hashing. Ciphers with 64-bit blocks, such as 3DES and Blowfish, start producing repeated ciphertext blocks after about 2^32 blocks, roughly 32 GB under one key. The 2016 Sweet32 research used that bound to recover secrets such as session cookies from long-lived HTTPS and OpenVPN connections.
Defending against birthday attacks
- Use hash functions with at least 256-bit output, such as SHA-256, SHA-384 or SHA-3, for signatures, certificates and anything an adversary might target.
- Retire MD5 and SHA-1 wherever an attacker could influence the input.
- Use ciphers with 128-bit blocks, such as AES, and rekey long before the data limit for the block size.
- Add unpredictable content before signing, as public CAs do by placing at least 64 random bits in each certificate serial number, so an attacker can't prepare a matching pair in advance.
Birthday attack vs. brute force vs. rainbow table
A brute-force attack tries keys or passwords until one works against a specific target. A rainbow table is a precomputed lookup for reversing unsalted password hashes. A birthday attack has no particular target: it needs any two inputs that collide, and its cost depends on digest length, not on password strength. A salt defeats rainbow tables but does nothing against a birthday attack on a signature hash; only a longer, unbroken hash function does.
Birthday attack on the CompTIA Security+ exam
Birthday attacks are taught with hashing algorithms under SY0-801 objective 1.3, the cryptographic solutions objective, as the reason digest length matters, and weak hash algorithms count as cryptographic vulnerabilities under objective 2.4. Wording such as "the chance of a collision rises with the number of hashes generated" or "an attacker prepared two versions of a document with the same hash" points to a birthday attack, and the fix is a stronger hash with a longer output, such as SHA-256. Distractors include salting, key stretching and account lockout, which address password guessing rather than collisions, and encryption, which doesn't change a hash's collision resistance.