= Hash compression function
{title2=$f(h,M)$}
A \b[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 is
$$
f:\{0,1\}^n\times\{0,1\}^b\longrightarrow\{0,1\}^n,
\qquad h_i=f(h_{i-1},M_i).
$$
A 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.<Secure Hash Standard by National Institute of Standards and Technology>[§§5.1.1–5.2.1, padding and blocks; §6.2.2, steps1–4, SHA-256 computation]{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 define
$$
f(h,(u,v))=(h+u+v)\bmod256.
$$
Starting 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.<Secure Hash Standard by National Institute of Standards and Technology>[§6.2.2, step4, intermediate hash value]{ref} A completed message digest also includes the effect of padding and is not generally the state after an unpadded payload fragment.
Back to article page
