Cryptographic hash functions are the workhorses of information integrity, digital signatures, blockchain consensus, and commitment schemes. A secure hash function must compress an arbitrary-length message (m in {0,1}^*) into a fixed-length digest (h in {0,1}^n) while maintaining three canonical security properties: preimage resistance, second-preimage resistance, and collision resistance. In this part, we examine the structural evolution from the classic Merkle-Damgård paradigm to the modern Sponge construction of Keccak (SHA-3).
1. Foundational Security Metrics & The Birthday Paradox
Let (H: {0,1}^* o {0,1}^n) be a cryptographic hash function. We demand:
- Preimage Resistance (One-Way): Given (y in {0,1}^n), it is computationally infeasible to find (x) such that (H(x) = y). Complexity target: (mathcal{O}(2^n)).
- Second-Preimage Resistance (Weak Collision): Given (x), it is infeasible to find (x’
eq x) such that (H(x’) = H(x)). Complexity target: (mathcal{O}(2^n)). - Collision Resistance (Strong Collision): It is infeasible to find any pair (x
eq x’) such that (H(x) = H(x’)). By the Birthday Paradox, a collision is expected after approximately (sqrt{2^n} = 2^{n/2}) evaluations. For 128-bit security, the hash digest must be at least (n = 256) bits.
2. The Merkle-Damgård Construction and Length-Extension Vulnerability
For decades, hash functions like MD5, SHA-1, and SHA-2 were built using the Merkle-Damgård Construction. A collision-resistant compression function (f: {0,1}^b imes {0,1}^n o {0,1}^n) processes message blocks iteratively:
[
h_0 = IV, quad h_i = f(m_i, h_{i-1}), quad H(m) = h_k
]
The Merkle-Damgård Theorem guarantees that if the underlying compression function (f) is collision-resistant, the iterated hash (H) is provably collision-resistant. However, because the final digest (H(m)) is literally the exact internal state of the generator after the final block, Merkle-Damgård suffers from a severe structural flaw: Length-Extension Attacks.
Given (H(m)) and the length of unknown message (m), an attacker can compute (H(m parallel ext{pad} parallel m’) = f(m’, H(m))) for any suffix (m’) without ever knowing (m). This vulnerability breaks naive message authentication codes like (MAC(k, m) = H(k parallel m)), requiring the complex nested structure of HMAC: (H((k oplus opad) parallel H((k oplus ipad) parallel m))).
3. The Sponge Construction and Keccak (SHA-3)
In 2012, NIST selected Keccak (designed by Bertoni, Daemen, Peeters, and Van Assche) as the official SHA-3 standard. Keccak abandoned compression functions in favor of the innovative Sponge Construction governed by a fixed unkeyed permutation (f: {0,1}^b o {0,1}^b).
The total state width (b = r + c = 1600) bits is divided into two parts:
- Bitrate (r): The rate of data throughput absorbed and squeezed per permutation step.
- Capacity (c): The security parameter hidden from the outside world. The provable collision resistance is strictly (2^{c/2}).
Execution proceeds in two phases:
- Absorbing Phase: Padded message blocks (P_i) of size (r) are XORed into the first (r) bits of the state, followed by evaluating the permutation: (S leftarrow f(S oplus (P_i parallel 0^c))).
- Squeezing Phase: The first (r) bits of the state are extracted as output blocks. If more bits are needed, (f) is evaluated repeatedly: (Z_j = ext{Trunc}_r(S); S leftarrow f(S)).
Because the capacity bits (c) are never exposed during squeezing, an attacker cannot learn the full internal state from the digest, rendering length-extension attacks mathematically impossible without requiring HMAC.
4. The Keccak-f[1600] Permutation
The internal state is organized as a (5 imes 5 imes 64) 3D array of bits. Each of the 24 rounds executes five linear and non-linear step mappings:
[
ext{Round} = iota circ chi circ pi circ
ho circ heta
]
where ( heta) mixes parity along vertical slices, (
ho) and (pi) rotate and transpose lane positions to provide rapid 3D diffusion, (chi) is the only non-linear layer applying bitwise operations (a oplus ((b oplus 1) wedge c)), and (iota) injects round constants to break symmetry. Its zero-overhead adaptability enables SHA-3 to function seamlessly as an extendable-output function (XOF, SHAKE128/256) and authenticated cipher.
