Cryptographic Hash Functions

A hash function is a deterministic function $H : \{0,1\}^* \to \{0,1\}^n$ that maps a bit string of arbitrary length to a fixed-length output of $n$ bits, called the digest or hash value. Determinism means the same input always produces the same output; this is what makes hashes useful for verification — two parties who compute $H(m)$ independently on the same $m$ will always agree. Efficiency means $H$ must be computable in time roughly linear in the length of the input, since it will be run on every message, file, or transaction that flows through a system. What separates a cryptographic hash function from an ordinary hash function (the kind used in hash tables) is that it must resist an adversary who is actively trying to break specific security properties, not merely trying to avoid accidental collisions for well-behaved inputs. Three properties are standard:

• Preimage resistance (a "one-way" property): given a digest $y$, it should be infeasible to find any $m$ with $H(m) = y$.
• Second-preimage resistance: given a specific message $m_1$, it should be infeasible to find a different message $m_2 \neq m_1$ with $H(m_1) = H(m_2)$.
• Collision resistance: it should be infeasible to find any pair $m_1 \neq m_2$ with $H(m_1) = H(m_2)$, without either message being fixed in advance.

These are phrased as games against a computationally bounded adversary, and "infeasible" means no efficient algorithm succeeds with more than negligible probability, in the spirit of the Goals of Cryptography: Confidentiality, Integrity, Authenticity framing where security is defined relative to a threat model rather than absolute impossibility. Note collisions always exist: since the input space is infinite (or at least far larger than $2^n$) and the output space has only $2^n$ elements, $H$ cannot be injective, and by the pigeonhole principle many inputs must map to the same output. Collision resistance never claims collisions don't exist — only that they are hard to find.

A modern hash function is built in two layers: a fixed-size compression function $f$, and an iteration mode that extends $f$ to handle inputs of arbitrary length. The most classical iteration mode is Merkle–Damgård, used (with variations) in MD5, SHA-1, and SHA-2. The compression function $f : \{0,1\}^n \times \{0,1\}^b \to \{0,1\}^n$ takes a fixed-size chaining value of $n$ bits and a fixed-size message block of $b$ bits, and produces a new $n$-bit chaining value. The full hash function processes the message one block at a time, feeding the output chaining value of one step in as the input chaining value of the next — this is why it is called an iterated construction. Before iteration begins, the message must be padded so its length is an exact multiple of the block size $b$. Padding schemes append a `1` bit, then enough `0` bits, then (crucially) the original message length encoded in binary — this is called Merkle–Damgård strengthening and is essential to the security proof described below. ```text PSEUDOCODE: Generic Merkle–Damgård hash construction function PAD(M): L <- bit-length of M M' <- M || 1 // append a single 1 bit while (bit-length of M' + 64) mod b != 0: M' <- M' || 0 // pad with zero bits M' <- M' || encode_64bit(L) // append original length (strengthening) return M' // length of M' is now a multiple of b function HASH(M): M' <- PAD(M) split M' into blocks m_1, m_2, ..., m_k // each of length b bits h_0 <- IV // fixed public initialization vector for i in 1..k: h_i <- f(h_{i-1}, m_i) // apply compression function return h_k // final chaining value is the digest ``` Each call to `f` is a small, carefully engineered function (in SHA-256, roughly 64 rounds of bitwise rotations, XORs, and modular additions on 32-bit words). Its design goal is to behave, for security-analysis purposes, indistinguishably from a random function on its domain — this idealization is called the random oracle model, and while no real function is truly random, treating $f$ as if it were lets us reason cleanly about the three resistance properties and is borne out empirically by extensive cryptanalysis of the standardized designs. Newer designs such as SHA-3 use a different iteration mode called a sponge construction, which absorbs message blocks into a large internal state via a fixed permutation and then squeezes out output bits, avoiding some structural weaknesses of Merkle–Damgård (notably length-extension attacks) while offering the same three security properties.

Time complexity. Computing $H(M)$ for a message of length $|M| = L$ bits requires padding (an $O(L)$ operation) and $k = \lceil L / b \rceil$ invocations of the compression function $f$, each of which does $O(1)$ work (a fixed number of rounds on fixed-size words). Total time is therefore $O(L)$ — linear in the input size, which is essential since hash functions must scale to gigabyte-sized files and be usable inside tight loops such as per-packet integrity checks.

Space complexity. Only $O(n + b)$ space is needed at any moment: the current chaining value ($n$ bits) and the current message block ($b$ bits). The construction is inherently streaming: you never need to hold the whole message in memory, which is why hashing a terabyte file uses the same working memory as hashing a byte.

Correctness of the construction (the Merkle–Damgård theorem). The engineering claim underlying this design is: if the compression function $f$ is collision-resistant, then the full iterated hash $H$ is collision-resistant. The proof is a clean reduction, worth walking through because it demonstrates the standard technique used throughout cryptographic security proofs. Suppose an adversary finds a collision $M_1 \neq M_2$ with $H(M_1) = H(M_2)$. After padding (which encodes the true bit-length at the end of each padded message), consider the two padded messages and their block sequences $m_1, \dots, m_k$ and $m_1', \dots, m_k'$. Because the final blocks encode different lengths whenever $|M_1| \neq |M_2|$, and encode identical content whenever $|M_1| = |M_2|$ but $M_1 \neq M_2$, one can always walk backward from the final compression call:

• If the final chaining inputs to $f$ differ (i.e., $(h_{k-1}, m_k) \neq (h_{k-1}', m_k')$) but $f$ outputs are equal, we have exhibited a collision in $f$ itself — contradicting $f$'s assumed collision resistance.
• If the final chaining inputs are equal, then in particular $h_{k-1} = h_{k-1}'$, so we recurse one block earlier and repeat the argument.
• This process cannot continue all the way back to identical initial states, because the two original messages were assumed distinct (they must differ in content or length at some point), so at some step a genuine collision in $f$ is forced out.

Hence any collision-finder for $H$ can be converted, with only linear overhead, into a collision-finder for $f$. This is a reduction: security of the simple, fixed-size, heavily analyzed primitive $f$ transfers to security of the complex, variable-input primitive $H$. It is why cryptanalysts focus enormous effort on breaking compression functions and permutations directly, rather than the full iterated hash.

Honesty about limits. This proof only protects collision resistance — it does not automatically give preimage resistance against all attacks (Merkle–Damgård is famously vulnerable to length-extension attacks, where knowing $H(M)$ lets an attacker compute $H(M \| \text{pad} \| X)$ for a chosen suffix $X$ without knowing $M$, because the digest is the internal chaining state). This is precisely why protocols such as HMAC exist rather than naively hashing a secret key concatenated with a message, and why sponge-based designs like SHA-3 were introduced.

Generic bounds (independent of any specific design) come from brute-force adversary strategies and set the honest floor on security, foreshadowing The Birthday Attack in detail:

The collision bound follows from the birthday paradox: with $q$ hash evaluations landing in a space of size $2^n$, the expected number of colliding pairs is roughly $\binom{q}{2}/2^n$, which exceeds $1$ once $q \gtrsim 2^{n/2}$. This is why digest sizes for collision-resistant use (e.g., SHA-256's 256 bits, giving $2^{128}$ collision-resistance) must be roughly double the size needed for preimage resistance alone — a subtlety many system designs get wrong.

Real cryptographic hash outputs are dense hexadecimal strings with no exploitable internal structure — that opacity is the point — so to see the mechanics we trace a deliberately tiny toy hash function, small enough to compute by hand, while being explicit that it is for pedagogy only and offers no real security.

Toy setup. Let the digest size be $n = 8$ bits. Define a toy compression function over 8-bit chaining values and 8-bit message blocks:

where $\text{ROL}_3$ rotates the byte left by 3 bits and $\boxplus$ is addition mod 256. Let $IV = \texttt{0x5A}$. Suppose the message, after padding, splits into three one-byte blocks: $m_1 = \texttt{0x11}$, $m_2 = \texttt{0x22}$, $m_3 = \texttt{0x33}$.

(*mod 256 wraparound: `0xFA + 0x33 = 0x12D`, truncate to 8 bits → `0x2D`.) So $H(M) = \texttt{0x2D}$ for this specific 3-block message. Now watch what happens with second-preimage resistance in this toy: an attacker who wants a different message with the same digest must search over the $2^8 = 256$ possible final chaining states and block choices at the last step to make $f(h_2, m_3') = \texttt{0x2D}$ with $h_2 = \texttt{0x6C}$ fixed — an $8$-bit search space, i.e. about $2^8$ trials in the worst case, matching the generic bound above (here trivially small because $n=8$; real hash functions use $n = 256$ or more precisely to make this search infeasible, at $2^{256}$ trials). This toy also lets us see collision resistance breaking down at small scale: because $f$'s output space is only 256 values, if we evaluate $f$ on roughly $\sqrt{256} = 16$ random $(h,m)$ pairs, the birthday bound predicts a collision becomes likely — a concrete, hand-verifiable preview of why real digests need $n \geq 256$ for 128-bit collision security.

Cryptographic hash functions sit underneath nearly every layer of the security stack. TLS certificates are signed over a hash of their contents, not the raw bytes, because digital signature algorithms operate on fixed-size inputs — this is why collision resistance is critical for signature security: a collision would let an attacker get one message signed and silently substitute another. Git and other version-control systems identify every commit and file blob by its SHA-1 (moving to SHA-256) hash, giving a content-addressed storage system where identical content is automatically deduplicated. Blockchains such as Bitcoin chain blocks together via hash pointers, so altering any historical block would cascade and change every subsequent block's hash, making tampering detectable. Password storage systems run passwords through slow, memory-hard hash functions (bcrypt, Argon2 — deliberately not fast, general-purpose hashes like SHA-256) precisely to raise the cost of brute-force preimage search. Software distribution pipelines publish hash digests of installers so users can verify integrity after download. All of these depend, in different combinations, on the three properties developed here, and all of them are re-examined more rigorously when studying Collision Resistance as its own topic and the concrete numeric consequences captured by The Birthday Attack.

Ask the tutor: How exactly does the birthday bound argument generalize from finding collisions to breaking HMAC or digital signature schemes in practice?