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 cryptographic test vector is a specified collection of algorithm inputs, parameters and expected outputs used to check an implementation. Exact byte encodings are part of the vector: a key displayed in hexadecimal represents bytes, not necessarily the displayed characters. A known-answer test compares a computed result with the supplied answer. RFC 4231 provides such vectors for several HMAC instantiations.^[ref]

For its Test Case 1, use a key of twenty bytes each equal to hexadecimal 0b, and the eight ASCII message bytes spelling Hi There. HMAC with SHA-256 must produce

b0344c61d8db38535ca8afceaf0bf12b881dc200c9833da726e9376c2e32cff7.

The output has 64 hexadecimal digits, hence 32 bytes. The key has twenty bytes; using the forty ASCII characters obtained by writing 0b twenty times supplies a different key. Adding a newline to the message supplies different message bytes too.^[ref]

A good vector identifies the complete algorithm variant. An unkeyed SHA-256 digest of that message is not the expected HMAC result, and SHA-512/256 is a different hash operation despite its equal digest length. HKDF additionally needs its salt, initial material, context and requested output length; its primary specification supplies all those fields together with the expected extraction and expansion results.^[ref]

Passing a vector establishes agreement for those inputs. It does not prove collision resistance, key secrecy or a cryptographic protocol's security. Nor does one short input exercise every implementation path. Vectors covering long keys, truncation and boundary lengths can reveal mistakes that a single example misses; RFC 4231 includes separate cases for those behaviours.^[ref]

Feedforward in SHA-256 compression adds the incoming chaining state to the final working words after the 64 rounds of a message block. The addition is componentwise modulo $2^{32}$. It is a specified part of the hash compression function, separate from the round updates.^[ref]

Write $H^{(i-1)}=(H_0^{(i-1)},\dots ,H_7^{(i-1)})$ for the incoming state. Initialize the working words $(a,b,c,d,e,f,g,h)$ from that state, execute all 64 rounds with the block's message schedule, then formThe right-hand working words are their values after the rounds. These eight sums become the input state for the next block, or contribute to the final digest when the padded message is complete.^[ref]

For an original single-word arithmetic example, suppose an incoming word is hexadecimal fffffff0 and its final working word is 00000030. Their ordinary sum is 100000020; reducing modulo $2^{32}$ retains 00000020. The carry beyond the 32-bit word is discarded. This example illustrates the addition rule, not an actual round output for a chosen message.

Returning only the working words omits feedforward and computes a different function. Using the fixed initial constants after every block also changes the function: after the first block, feedforward uses the immediately incoming chaining state. Compliance with these operations is a correctness requirement; the existence of feedforward alone is not a proof of collision resistance.

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 compression function combines a fixed-size chaining state and one fixed-size message block to produce the next chaining state. For state width $n$ and block width $b$, a common interface isA complete iterative cryptographic hash function additionally specifies its hash initialization vector, message padding, block order and output rule. For SHA-256, the state has256bits and a block has512bits; the standard defines a64-word message schedule,64rounds and the additions producing the next eight-word state.^[ref]

Here compression is not reversible file compression. The function maps $2^{n+b}$ input pairs into only $2^n$ states. Averaged over output states, each state has $2^b$ preimages, counting zero-preimage states too. Collision resistance concerns the difficulty of finding suitable collisions, not their mathematical absence.

An original deliberately weak example makes the interface concrete. Let the state be one byte and the block be two bytes, and defineStarting from hexadecimal 6a, block 00 01 gives 6b; a following 00 02 gives 6d. But 01 00 also gives 6b from the same initial state. The interface and shrinking state size alone have supplied no cryptographic security. This toy is not an approximation to the SHA-256 round function.

The standard's feedforward in SHA-256 compression adds the incoming state words to the final working words modulo $2^{32}$. Omitting that step changes the compression function even if all64rounds were otherwise correct.^[ref] A completed message digest also includes the effect of padding and is not generally the state after an unpadded payload fragment.

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.

A failure of collision resistance supplies distinct messages $x,x^{\prime }$ withAsk the legitimate signer to sign $x$, obtaining $s=f(sk,h(x))$. Output $(x^{\prime },s)$ without ever requesting a digital signature on $x^{\prime }$. Its verification succeeds becauseThusThe adversary chooses the collision pair, but cannot in general insist that one member equal an independently specified target. A known-message signature attack would require the stronger ability to collide with an already signed message; finding an arbitrary collision alone does not provide that.

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.

SHA-256 is a SHA-2 cryptographic hash function producing a 256-bit digest. It processes a padded message in 512-bit blocks, with eight 32-bit state words and 64 processing rounds per block. The specified additions use modular arithmetic modulo $2^{32}$.^[ref]

Padding is part of the function. For input bit length $\ell <2^{64}$, append a one bit, then the smallest nonnegative number $k$ of zero bits satisfyingthen append the 64-bit representation of $\ell$. This makes the complete length a multiple of 512 bits.^[ref]

For an original byte-count example, the three ASCII bytes 61 62 63 have length 24 bits. Here $k=423$, andThe padded block consists of the original three bytes, byte 80, 52 zero bytes and an eight-byte length field representing 24. The padded input occupies 64 bytes; the final digest occupies 32 bytes. Computing SHA-256 gives

ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad.

Adding a newline changes the byte sequence and the digest. Displayed text, its character encoding and its line terminator must therefore be specified when comparing hash values.

The padding boundary is also visible without computing a digest. A 55-byte input fits its padding into one 64-byte block, whereas a 56-byte input requires two blocks because the length field no longer fits. Both still produce a 256-bit output. Digest length is not the padded-message length or a reversible compressed representation of the input.

Finite output size necessarily allows collisions over a larger input set; collision resistance concerns the difficulty of finding them. SHA-256 also supplies the hash operation used inside common HMAC and HKDF instantiations, whose keyed constructions and security properties differ from an ordinary unkeyed digest.

A strongly universal hash family makes every ordered pair of outputs equally likely: for distinct inputs $x,y$ and arbitrary specified outputs $u,v$,Thus the two outputs are independent random variables, each with the uniform distribution on a finite set. Adding the $q$ equal ordered pairs gives collision probability $q/q^2=1/q$, so the family is also a universal hash family.

Here is a completely enumerable example. In the finite field ${\mathbb{F}}_5$, take the affine functions $h_{a,b}(x)=ax+b$, using modular arithmetic modulo $5$. Choose $a$ and $b$ as independent random variables, each with the uniform distribution on a finite set of all five finite field elements $0,1,2,3,4$, including $a=0$. There are $25$ equally likely hash functions. For $x=0,y=1$, the ordered pair is $(b,a+b)$. For instance $(a,b)=(2,3)$ gives $(h(0),h(1))=(3,0)$; $(0,3)$ gives $(3,3)$. Every prescribed $(u,v)$ occurs exactly once, at $b=u,a=v-u$.

Each row contains five choices, so each individual output has probability $5/25=1/5$. Each cell has probability $1/25$, and the five diagonal cells give collision probability $5/25=1/5$. For any distinct $x,y$, the same conclusion follows from $a=(v-u)/(y-x)$ and $b=u-ax$: a nonzero finite field element has a unique inverse. This is the beauty of the construction: two small random coefficients provide exact pair balance without choosing five unrelated values.

The example uses equal-sized input and output sets to make every choice visible; it illustrates the family definitions rather than compression. In a larger input set, a hash function cannot avoid all collisions into five buckets. What a universal hash family controls is the fraction of its members that collide on each fixed pair, rather than the existence of any collision anywhere.

Restricting to $a\ne 0$ leaves $20$ permutations with zero collision probability for distinct inputs. Individual outputs remain uniform, but given $h(0)=u$, the four values other than $u$ each have conditional probability $1/4$ and $u$ has zero. Hence these outputs are not independent random variables: this is a universal hash family but not a strongly universal hash family. Finally, the full $25$-member example contains five constant functions, with immediately visible collisions. Its pair guarantee concerns a random choice of hash function, and makes no claim of cryptographic collision resistance.