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.

A function mapping messages of arbitrary length to fixed-length digests, designed to provide preimage resistance and collision resistance. In a digital signature protocol the digest also needs an encoding and security properties appropriate to that protocol.

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]

Place a proof of work gate before Tim performs the expensive private-key decryption in message 2. Binding the puzzle to the whole request prevents solving a cheap puzzle once and reusing it with different tickets.

For example, let $R$ be the exact encoding of message 2, including identities, Alice's cryptographic nonce and Bob's encrypted component. On receiving a proposed request, Tim does only cheap length and format checks and returns a fresh challenge $r$, an expiry time $t$, a difficulty $d$ and a cookieHere $s_T$ is Tim's cookie secret and the message authentication code prevents alteration of the challenge or difficulty. Tim need not retain large amounts of per-request state merely to issue the cookie.

The requester finds a suffix $w$ such thatUnder the usual unpredictable-hash-output model, this takes an expected $2^d$ trials; verifying a proposed suffix needs one cryptographic hash function evaluation after checking the request digest and cookie. Preimage resistance motivates search difficulty, but the exact $2^d$ estimate also uses that distribution assumption.

The requester returns $(R,r,t,d,\tau ,w)$. Before any expensive decryption, Tim verifies the cookie, expiry, work and request binding, and atomically records that this challenge has been consumed. Repeated submissions of a consumed challenge are rejected cheaply. Short expiry bounds the storage needed for spent challenges. A cookie alone is insufficient: without one-use enforcement, the attacker could replay a single valid solved request indefinitely.

To charge the work to the initiator rather than Bob, Bob can relay the challenge to Alice and forward her solution. The adversary's fake Alice must then solve each puzzle instead of making honest Bob do it. Tim must issue challenges and reject bad proofs with bounded inexpensive processing, and difficulty should be chosen so that many verified requests require substantial aggregate work. This mitigates the computational denial-of-service attack; it does not correct the separate authentication flaw.

The standard attack on this raw trapdoor construction chooses a candidate digital signature $s$ first, computes $y=g(pk,s)$, and uses a failure of preimage resistance to find $x$ with $h(x)=y$. Thenso $(x,s)$ verifies. The resulting message is selected by the inversion procedure, rather than being an arbitrary prescribed document. This is an existential forgery under a key-only signature attack whenever the inversion weakness applies with nonnegligible success to those sampled digests.

The phrase “fails to be preimage resistant” must be read with its target distribution. Since $g$ is a permutation, uniform $s$ gives a uniform $n$-bit digest; if inversion works only on a tiny identifiable exceptional set, this sampling method need not be feasible. Merely knowing a valid signed message and recovering that same message from its digest is not a new forgery. Producing a different message there requires a failure of second-preimage resistance. Part solution removes the coverage qualification by explicitly granting inversion at every digest.

Given a particular input $x$, finding a different input $x^{\prime }$ with the same digest should be computationally infeasible. Preimage resistance asks for any input matching a given digest; collision resistance allows choosing both colliding inputs. These are different security requirements.

SHA-2 is a family of cryptographic hash functions including SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224 and SHA-512/256. NIST specifies these algorithms in FIPS 180-4. Their digest lengths are respectively 224, 256, 384, 512, 224 and 256 bits; the algorithm name therefore matters as well as the output size.^[ref]

The SHA-224/SHA-256 branch uses 32-bit words and 512-bit message blocks. The SHA-384/SHA-512 branch and its specified truncation variants use 64-bit words and 1024-bit message blocks. Different initial values are part of the definitions. In particular, SHA-512/256 is not simply the first 256 bits of an ordinary SHA-512 digest.^[ref]

For a computed example, hashing the three ASCII bytes 61 62 63 with SHA-512/256 produces

53048e2681941ef99b2e29b76b4c7dabe4c2d0c634fc6d46e0e2f13107e7af23.

Taking the first 256 bits of the SHA-512 digest of those same bytes instead gives

ddaf35a193617abacc417349ae20413112e6fa4e89a97ea20a9eeee64b55d39a.

Both outputs occupy 32 bytes and require 64 hexadecimal digits, yet they differ. An interface identifying its hash only as a 256-bit digest leaves the selected algorithm ambiguous.

A digest is deterministic and does not conceal low-entropy inputs by itself. Nor does an unkeyed digest establish who supplied a message: a sender-authentication mechanism such as HMAC uses a cryptographic key and an appropriate security definition. Preimage resistance, second-preimage resistance and collision resistance are distinct properties; their meanings should not be replaced by the mere observation that two displayed examples have different outputs.