Hash Collision Probability Calculator
Inputs
| Hash size | 128 |
|---|---|
| Number of items | 1,000,000 |
Hash Collision Probability Calculator
Estimate the probability of a birthday collision among a set of hash values, and find how many items are needed to reach a 50% collision chance for a given hash size.
Inputs
Hash Parameters
Results
Enter a value to see results.
Collision Probability
Hash Collision Probability
A hash function maps an input of arbitrary length to a fixed-length output called a digest. Ideally, no two distinct inputs produce the same digest — a property called collision resistance. In practice, because the output space is finite, collisions must exist; the question is how many inputs must be hashed before one is likely. This calculator quantifies that probability using the birthday approximation, named after the birthday paradox.
The Birthday Paradox
In a group of 23 people drawn uniformly at random from a 365-day year, there is already greater than 50% probability that two share a birthday. The probability is so much higher than intuition suggests because it counts any pair among the group, not a match to a specific target. The same asymmetry governs hash collisions: finding two inputs with the same hash (a collision) is far easier than finding an input that produces a specific target hash (a preimage).
Formula
For a hash function with bits of output, the search space has equally likely values. Given randomly hashed items, the exact collision probability is the complement of the probability that all outputs are distinct:
p=1−k=0∏n−1(1−2bk)For large and moderate , the birthday approximation gives a simpler closed form:
p≈1−e−n2/(2⋅2b)Solving for the number of items at which the probability reaches 50%:
n50%=2⋅2b⋅ln2Worked Example
For a 32-bit hash (such as CRC32 used in checksums):
n50%=2×232×ln2=2×4,294,967,296×0.6931≈5,954,124,768≈77,163With just 77,163 files in a repository, there is roughly a 50% chance that two share the same 32-bit CRC. Confirming with the approximation formula:
p=1−e−771632/(2×232)≈1−e−0.693≈0.50This is why CRC32 is unsuitable as a unique identifier in large collections, even though it is an excellent error-detection code over small data streams.
Security Implications
The birthday bound establishes that a hash function with bits provides only bits of collision resistance. An attacker needs approximately hash evaluations to find a collision — not . This is why cryptographic hash functions are designed with larger outputs than the target security level:
| Hash function | Output | Collision resistance |
|---|---|---|
| MD5 | 128 bits | ~ (broken in practice) |
| SHA-1 | 160 bits | ~ (broken in practice) |
| SHA-256 | 256 bits | ~ (current standard) |
| SHA-3-512 | 512 bits | ~ (high security) |
MD5 and SHA-1 are listed as "broken" not solely because of the birthday bound, but because researchers found algorithmic weaknesses that produce collisions far faster than operations. MD5 collisions can be computed on commodity hardware in a matter of minutes using published techniques.
For related analysis of password search spaces, see Password Entropy Calculator.
Frequently Asked Questions (FAQ)
What is the birthday paradox in cryptography?
The birthday paradox is the counterintuitive result that in a group of only 23 people, there is already a better than 50% chance that two share a birthday — despite there being 365 possible birthdays.
The same mathematics applies to hash functions: an attacker only needs roughly √(2^b) = 2^(b/2) hashed items to reach a 50% probability of finding two with the same output. This is the birthday attack. For a 128-bit hash like MD5, that threshold is about 2^64 ≈ 1.8 × 10¹⁹ items — far fewer than the full 2^128 combinations a preimage attack would require.
Why does a birthday attack require only half as many bits to break?
A preimage attack must find a specific hash output and therefore must search the full 2^b space. A birthday attack only needs any two inputs to collide, and by the birthday bound the probability of finding such a pair crosses 50% after approximately 2^(b/2) samples. This is why hash functions are typically designed with twice as many output bits as the desired security level: a 256-bit hash provides 128-bit collision resistance.
Why are MD5 and SHA-1 considered insecure?
MD5 (128 bits) and SHA-1 (160 bits) have been broken by practical collision attacks — not just birthday-bound probabilistic attacks, but algorithmic weaknesses that find collisions far more efficiently than the birthday bound predicts. In 2004, researchers demonstrated MD5 collisions; in 2017 Google's SHAttered project produced the first publicly known SHA-1 collision.
These functions are still safe for non-cryptographic uses such as checksums and content-addressing, but they should not be used where collision resistance matters, such as digital signatures or certificate authorities.
What is the difference between a collision and a preimage?
A collision means finding any two distinct inputs x and y such that hash(x) = hash(y). A preimage means finding an input x that hashes to a specific target value h — harder because you cannot choose both inputs freely. A second preimage means finding a different input y with the same hash as a known x.
These are listed in increasing order of difficulty: collision resistance is the weakest property, and second-preimage resistance is the strongest. Hash functions used in digital signatures must resist second-preimage attacks; those used in hash tables or Bloom filters need only weak collision resistance.