 Birthday probability for hash outputs

How soon should a hash collision appear? Specify the probability distribution of the outputs first. Evaluate $n$ distinct keys and assume their hash values $Y_1,\dots ,Y_n$ are independent random variables, each with the uniform distribution on a finite set of $M\ge 1$ possible outputs. The randomness may come from an idealized randomly chosen hash function; a fixed hash function and a fixed list of keys have a definite outcome. Sampling the same key twice creates a repeated hash value without creating a hash collision, so distinctness of the queried keys matters.

This is the existing birthday problem, with hash values in place of birthdays. Let $p_M(n)$ be the probability of at least one equal pair. The exact formula isThe empty product is $1$, so $p_M(0)=p_M(1)=0$. Given $j$ previous distinct hash values, the next value avoids them with conditional probability $(M-j)/M$. Multiply these conditional chances and subtract from $1$. Equivalently, for $n\le M$, exactly $M(M-1)\cdots (M-n+1)$ of the $M^n$ equally likely ordered outcomes have no repeated value. This derivation also explains why independence of all outputs, rather than merely uniform individual values, is required.^[ref]

For $M=256$, the exact hash collision probabilities are $p_{256}(19)\approx 0.495742$, $p_{256}(20)\approx 0.533167$, and $p_{256}(32)\approx 0.867643$. Thus only $20$ distinct queries already exceed a one-half chance of some pair matching. The striking feature is the number of opportunities: $n$ queries supply $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ pairs. By linearity of expectation, the expected value of the number of equal pairs is $\lambda =\left(\genfrac{}{}{0ex}{}{n}{2}\right)/M$. This expectation counts pairs, not the probability of at least one pair; three equal outputs contribute three pairs in one outcome. The union bound gives $p_M(n)\le \min (1,\lambda )$.

Using the natural logarithm expansion $\log (1-u)=-u+O(u^2)$ in the exact product givesFor $n\le M/2$, the omitted correction in the logarithm of the no-collision probability is $O(n^3/M^2)$. Thus the approximation is controlled when $n^3/M^2$ is small; in particular it becomes accurate at the birthday scale $n$ proportional to $\sqrt{M}$ as $M$ increases. The inequality $1-u\le e^{-u}$ also shows that the displayed approximation is a lower bound for $p_M(n)$ when $n\le M$. Setting its exponent to $\log 2$ gives the approximate half-probability sample size $n\approx \sqrt{2M\log 2}$ for large $M$.

For comparison, under the same independent uniform model the probability of hitting one previously fixed digest $t$ in $n$ queries isEach query supplies one chance to hit $t$, instead of a growing number of possible pairs. For $M=256$, $q_{256}(20)\approx 0.075293$, and the first integer $n$ with $q_{256}(n)\ge 1/2$ is $178$. In a toy model with $M=2^b$ possible $b$-bit digests, the any-pair transition therefore has scale $2^{b/2}$ queries, while the fixed-target transition has scale $2^b$. This explains the birthday-search distinction between collision resistance and preimage resistance.^[ref]

The assumptions are essential. Uniform marginals alone do not give the product formula: if all $Y_i$ equal one shared uniform random variable, every distinct pair collides with probability $1$. A universal hash family bounds each pair's hash collision probability, but that condition alone does not supply joint independence of every output. Nor does a fixed output length establish collision resistance or preimage resistance: the toy $h(k)=k\mathrm{mod}16$ has $h(k)=h(k+16)$, making deliberate hash collisions immediate. The curves describe the specified model and do not establish the security of a concrete cryptographic hash function.