Hash Collision Probability Calculator

Background.

Hash two different values and you can, with bad luck, get the same digest back. This calculator works out how likely that is: give it a digest width and a number of values, and it returns the probability that at least two of them collide, the expected number of colliding pairs, and the point at which a collision becomes more likely than not.

It is the birthday problem with a bigger room. Twenty-three people give a better-than-even chance of a shared birthday because what matters is the number of pairs, not the number of people, and pairs grow as the square of the group. The same square shows up here: the expected number of colliding pairs among k values in a space of N digests is k(k−1)/(2N), and the probability of at least one is 1 − e^(−λ) where λ is that expectation. Setting that to a half gives the familiar birthday bound, √(2N ln 2) ≈ 1.1774 × 2^(n/2) — which is exactly why NIST SP 800-107 Rev. 1 states that an L-bit hash function has a collision resistance of L/2 bits, and why RFC 4270 puts the attacker's cost at 2^(L/2) attempts rather than 2^L.

The practical lesson lands hardest at the small end. A hundred thousand values in a 32-bit CRC space collide 68.8 % of the time, which is why CRC-32 is an error-detection checksum and not an identifier. A billion values in a 64-bit space collide about 2.7 % of the time — small, but not small enough to bet a primary key on, and 5.06 billion values in that space is a coin flip. Move to 128 bits and a trillion values give a probability around 1.5 × 10⁻¹⁵; move to SHA-256 and the numbers stop being meaningful in any physical sense.

One detail is worth getting right because almost everybody gets it wrong: a version 4 UUID is 128 bits long but only 122 of them are random. RFC 9562 specifies four bits for the version and two for the variant, so the usable space is 2¹²², not 2¹²⁸. Calculating with 128 understates the collision probability by a factor of 64. This calculator uses 122 for the UUID option and says so.

What the page models is an accidental collision between digests assumed to be uniformly and independently distributed — the case that matters when you are sizing a key, a shard identifier, a deduplication index or a short link. It does not model a deliberate collision constructed by an attacker. That is a different and much cheaper problem for a broken function: RFC 4270 records that every practical attack on MD5 and SHA-1 is a collision attack, and both fell far below their birthday bounds. If your threat model includes somebody who wants two colliding inputs, the number on this page is not the number you need.

Below the widget you will find the derivation from the exact product formula, a worked example computing the 64-bit case by hand, the reason the calculator switches between three different numerical methods depending on the size of λ, and guidance on which digest width to pick for a given number of values.

What is hash collision probability calculator?

A hash collision is two different inputs producing the same digest. Because a hash function maps an unlimited set of inputs onto a fixed-size output, collisions must exist; the only question is how likely you are to meet one. If the function spreads its outputs uniformly — which a good cryptographic hash approximates well — then hashing k values into a space of N = 2ⁿ digests is a balls-into-bins problem, and the answer is governed by the number of pairs rather than the number of values. There are k(k−1)/2 pairs, each of which collides with probability 1/N, so the expected number of colliding pairs is λ = k(k−1)/(2N), and the probability that at least one pair collides is very close to 1 − e^(−λ). This grows far faster than intuition suggests: the number of values needed for an even chance is around the square root of the space, not half of it. That square root is the birthday bound, and it is the reason NIST measures a hash function's collision resistance at half its output length — SHA-256 produces 256 bits and offers 128 bits of collision resistance. Two things fall outside this model. First, it assumes uniformity: a hash function with structural bias, or a non-cryptographic function fed adversarially chosen keys, collides more often than the arithmetic says. Second, it counts only accidental collisions. An attacker who wants two inputs with matching digests attacks the function itself, and against MD5 or SHA-1 that costs vastly less than the birthday bound implies.

How to use this calculator.

1. 01Choose the digest. If you are truncating a longer hash — storing the first 8 bytes of a SHA-256, for example — pick Custom and enter the truncated width, because the truncated width is what governs collisions.
2. 02For UUIDs, use the UUID version 4 option. It uses 122 bits, not 128, because six bits of a UUIDv4 are fixed by the specification.
3. 03Enter the number of values that share the space. For a database key this is the total you expect over the entire life of the system, including deleted rows if their identifiers are never reused — not the number live at any one moment.
4. 04Read the probability first, then the expected colliding pairs beside it. When that expectation is well below 1 the two numbers are nearly identical; when it climbs past about 40 a collision is a certainty and the probability pins at 1.
5. 05Use the 50 % point to size a future space. It is reported as a power of ten, so a value of 9 means a collision becomes more likely than not somewhere around a billion values.
6. 06Remember what the number does not cover: an attacker deliberately constructing a collision. For that, the relevant figure is the published attack cost against the specific function, which for MD5 and SHA-1 is far below the birthday bound.

The formula.

The exact probability of no collision among k values is the product (1 − 1/N)(1 − 2/N)…(1 − (k−1)/N): the second value must miss the first, the third must miss both, and so on. That product is exact and completely impractical — nobody is multiplying a billion terms. Applying the inequality 1 − u ≤ e^(−u) to each factor collapses it: the product is at most exp(−(1 + 2 + … + (k−1))/N) = exp(−k(k−1)/(2N)). Writing λ for that exponent gives p ≈ 1 − e^(−λ). Because the inequality runs one way, the result is a lower bound on the true probability, and the gap is invisible whenever k is much smaller than N.

λ has a meaning worth keeping in view: it is the expected number of colliding pairs, C(k,2)/N. There are k(k−1)/2 pairs, and each collides with probability 1/N. When λ is well below 1 the probability is essentially λ itself, which is why a tiny expectation and a tiny probability report the same number. When λ climbs past 40, e^(−λ) is smaller than 10⁻¹⁷ and the probability is 1 for any practical purpose.

Setting 1 − e^(−λ) = 0.5 gives λ = ln 2, and solving for k gives k₅₀ = √(2N ln 2) = 1.1774… × 2^(n/2). That constant of 1.1774 is why the birthday bound is usually quoted simply as 2^(n/2): the two differ by less than 18 %, which is nothing next to an exponential. NIST SP 800-107 Rev. 1 states the same fact as a security property — for an L-bit hash function the expected security strength for collision resistance is L/2 bits — and extends it to truncation: truncating an L-bit digest to λ bits reduces its collision resistance to λ/2 bits.

The implementation switches between three methods because no single expression survives the whole range. Above λ = 40 it returns 1 outright. Below λ = 0.001 it uses the Maclaurin series λ − λ²/2 + λ³/6 − λ⁴/24, because evaluating 1 − e^(−λ) directly there subtracts two numbers that agree to twenty digits and returns zero for probabilities that are genuinely 10⁻²⁰ or 10⁻²⁰⁰. In between it evaluates 1 − e^(−λ) in arbitrary precision, where the expression is well conditioned. The probability outputs are rounded to 12 significant digits rather than to a fixed decimal place, for the same reason.

A worked example.

Frequently asked questions.

References& sources.

1. [1]NIST SP 800-107 Revision 1, 'Recommendation for Applications Using Approved Hash Algorithms', §4, §4.1 and §5.2.2. Source of the collision-resistance rule used here, quoted verbatim: 'The expected collision-resistance strength of a hash function is half the length of the hash value produced by that hash function, i.e., for an L-bit hash function, the expected security strength for collision resistance is L/2 bits. For example, SHA-256 produces a (full-length) hash value of 256 bits; SHA-256 provides an expected collision resistance of 128 bits.' §5.2.2 extends the rule to truncated digests: truncating an L-bit output to λ bits reduces collision resistance to λ/2 bits. §4 also lists the FIPS 180-4 output lengths used for the SHA-1, SHA-256 and SHA-512 options (160, 256 and 512 bits).
2. [2]IETF RFC 4270, 'Attacks on Cryptographic Hashes in Internet Protocols', §2 and §2.1. Source of the birthday bound stated from the attacker's side — 'Finding a pair of messages M1 and M2 that have the same hash value takes 2^(L/2) attempts' — and of the distinction this page draws between accidental and deliberate collisions: 'All the currently known practical or almost-practical attacks on MD5 and SHA-1 are collision attacks.'
3. [3]IETF RFC 9562, 'Universally Unique IDentifiers (UUIDs)', §5.4 and §6.7. Source of the 122-bit figure used for the UUIDv4 option: an implementation 'MAY choose to randomly generate the exact required number of bits for random_a, random_b, and random_c (122 bits total)'. §6.7 'Collision Resistance' instructs implementers to evaluate the consequences of a collision for their own use case.
4. [4]IETF RFC 1321, 'The MD5 Message-Digest Algorithm', §1. Source of the 128-bit width used for the MD5 option: the algorithm 'takes as input a message of arbitrary length and produces as output a 128-bit "fingerprint" or "message digest" of the input'.
5. [5]NIST, Computer Security Resource Center Glossary — 'collision resistance'. 'An expected property of a cryptographic hash function whereby it is computationally infeasible to find a collision', sourced by NIST to SP 800-106 and SP 800-107 Rev. 1.
6. [6]NIST, Computer Security Resource Center Glossary — 'security strength'. 'A number associated with the amount of work (i.e., the number of operations) that is required to break a cryptographic algorithm', measured in bits, with roughly 2^S operations required at strength S. Used to relate the collision-resistance bits reported here to an attacker's workload.