Birthday Bound
Collisions become likely after about √ of the hash space.
Formula
Variables
Example
64-bit hash: n ≈ 5×10⁹ before a collision is likely
How it works
The birthday bound estimates how many random hashes or identifiers you can generate before a collision becomes probable, with 50% chance occurring at about 1.177 times the square root of the total number of possible hash values. It comes from the birthday paradox: as you add items, the number of pairwise comparisons grows like n², so collision risk rises much faster than intuition suggests. Because a b-bit hash has 2^b possible outputs, the threshold scales as the square root of that space rather than the full space. This is why doubling hash length dramatically increases safety against accidental collisions.
When to use it
Use this when assessing collision risk for hash functions, random nonces, file fingerprints, UUID-like identifiers, or any system where many independent items are mapped into a fixed-size bit space. It is especially useful in security engineering and protocol design when you need to know whether a hash size is large enough for the expected number of stored or generated values.
Worked example, step by step
Suppose you use a 48-bit hash and want to know how many distinct items give about a 50% chance of at least one collision. n ≈ 1.177 × sqrt(2^b) b = 48 n ≈ 1.177 × sqrt(2^48) 2^48 = 281,474,976,710,656 sqrt(2^48) = 2^24 = 16,777,216 n ≈ 1.177 × 16,777,216 n ≈ 19,747,000 So after about 2.0 × 10^7 items, a collision is already likely.
Common mistakes to avoid
- Treating this as the point where a collision is guaranteed, rather than about a 50% chance
- Using the formula for deliberate attacks on hashes, where the birthday bound may not be the right security model
- Forgetting that the threshold grows with the square root of the hash space, so adding a few bits can greatly change the result
Did You Know?
The birthday paradox is why a 256-bit hash gives only 128 bits of collision resistance.
Share this formula
More in Cryptography & Security
View allModular Exponentiation
IntermediateCore operation of RSA encryption — raise a message to a power, modulo n.
RSA Decryption
AdvancedRecovers the message using the private exponent d.
Euler's Totient
IntermediateCounts integers below n coprime to it, for n = pq — used to make RSA keys.
Shannon Entropy
AdvancedAverage information content — and the theoretical strength of a random source.
Password Entropy
IntermediateBits of security from password length and character-set size.
Key Space Size
IntermediateNumber of possible keys for a b-bit key.