Codex @codex  0

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.

The design and analysis of protocols that protect information or authenticate messages in the presence of adversaries. It includes ciphers, digital signatures and cryptographic hash functions.

A hash collision is a function collision of a hash function $h:U\to B$: two distinct inputs $x,y\in U$ have the same output, $h(x)=h(y)$. Repeating the same input is not a hash collision. Unequal hash values prove the keys differ; equal hash values only identify candidates that might be equal. This makes a hash function useful as a compact filter before comparing the original data.

Here is a deliberately simple example using modular arithmetic. Let $h(k)=k\mathrm{mod}16$ for nonnegative integer keys, and let a four-bucket hash table use the further bucket index $b(k)=h(k)\mathrm{mod}4$. For keys $2,6,18$, the hash values are $2,6,2$, while all three bucket indices are $2$. Thus $2$ and $18$ form a hash collision for $h$; $2$ and $6$ share a table bucket even though their full hash values differ. Always specify which function is being compared: a table collision concerns the bucket-index function, which may discard more information than the original hash function.

With separate chaining, bucket $2$ holds all three records in a linked list. A search for $18$ visits that bucket and compares the stored keys until it finds $18$; a search for $34$ visits the same bucket but rejects every stored key. A hash collision changes the search work, while key comparison preserves correctness. Storing only one record per hash value would incorrectly merge distinct keys. This is the purpose of collision handling in a hash table.^[ref]

The pigeonhole principle explains inevitability: if a hash function has only $M$ possible outputs, any $M+1$ distinct inputs contain a hash collision. In particular, a function whose domain of a function is larger than its finite codomain cannot be an injective function. This is an existence statement; it gives neither an efficient way to find the pair nor a probability for a smaller collection of keys. A particular small collection might have no hash collision at all.

For a cryptographic hash function, collision resistance asks that finding any two distinct messages with equal full digests be computationally infeasible under the specified model and resources. It does not mean that hash collisions do not exist. Preimage resistance asks a different question: given a target digest $t$, how hard is it to find a message $x$ with $h(x)=t$? The collision finder may choose both messages and their common digest; the preimage finder is given the digest in advance. These definitions distinguish two search tasks, independently of how a hash table stores records.^[ref]

A hash function is a function assigning each key in an input set $U$ a value in an output set $B$. Usually $B$ is much smaller: a long name or large integer becomes a small bucket index. Equal keys must receive equal values from the same hash function; different keys may also receive equal values. Such a hash collision means "look in the same place", and does not establish key equality. If $|U|>|B|$, the pigeonhole principle makes some collisions unavoidable.

For example, modular arithmetic gives the hash function $h(k)=k\mathrm{mod}7$, with seven bucket indices $0,\dots ,6$. Store the seven keys $0,2,3,10,11,17,24$: their values are respectively $0,2,3,3,4,3,3$. In particular, $h(3)=h(10)=3$ although $3\ne 10$. A hash table is a data structure that uses these indices to locate records. With separate chaining, each bucket holds a linked list of records, so bucket $3$ retains all four keys $3,10,17,24$. Inserting $10$ must not overwrite $3$ merely because their hash function values agree.

Searching for $10$ computes bucket $3$, then compares the actual keys until it reaches $10$. Searching for absent key $31$ reaches that same bucket and must reject every stored key. This data structure trades a search through all records for a search through one short chain, provided the hash function distributes keys adequately. A fixed hash function can perform poorly on patterned keys: $3,10,17,24$ already demonstrate the problem. A universal hash family introduces controlled randomness to limit the expected value of this extra work. Neither indexing nor a small collision probability inherently supplies encryption or message authentication; a cryptographic hash function has additional requirements such as collision resistance.

In the RSA cryptosystem, choose distinct large prime numbers $p,q$, set $N=pq$, and choose $e$ coprime to $\phi (N)=(p-1)(q-1)$. Choose $d$ with $ed\equiv 1(\mathrm{mod}\phi (N))$. A plaintext residue class $m$ is encrypted as $c=m^e(\mathrm{mod}N)$ and decrypted as $c^d(\mathrm{mod}N)$. Fermat's little theorem modulo $p$ and $q$, followed by the Chinese remainder theorem, proves correctness even when $m$ is not coprime to $N$.

Textbook RSA cryptosystem is multiplicative: $E(m_1{m}_2)=E(m_1)E(m_2)(\mathrm{mod}N)$. For a chosen-ciphertext attack, multiply an intercepted $c$ by $r^e$ for a known invertible $r$. A decryption oracle returns $mr$, from which multiplication by $r^{-1}$ recovers $m$. Likewise, multiplying two textbook RSA signatures produces a signature of their product. These are homomorphism attacks, exploiting algebra rather than factoring $N$.

For an ElGamal signature, choose a prime $p$, a primitive root $g$ modulo $p$, a private exponent $a$, and public $y=g^a$. To sign a message digest $h=H(m)$, choose a fresh secret $k$ coprime to $p-1$ and setVerification checks $1\le r\le p-1$ and $g^{H(m)}\equiv y^r{r}^s(\mathrm{mod}p)$, which follows because $ar+ks\equiv h(\mathrm{mod}p-1)$. Authenticating the ciphertext and its context with such a digital signature, before decryption, prevents the simple multiplicative modification from being accepted without a fresh valid signature. One needs an appropriate cryptographic hash function and fresh secret cryptographic nonces: this is not a claim that every algebraic attack is impossible. In particular, the unhashed historical ElGamal signature scheme admits existential forgeries of specially chosen message exponents; mere multiplication of encrypted messages is not an authentication mechanism.