The Merkle-Damgård Construction and the Padding That Binds It

A hash function such as SHA-256 accepts an input of any length and returns 256 bits. No block cipher or permutation primitive behaves that way. The primitive at the bottom of SHA-256 consumes exactly 64 bytes per call and returns exactly 32, so something has to bridge the gap between “any length” and “fixed width”. For the SHA-2 family that bridge is the Merkle-Damgård construction, and it accounts for several behaviours that otherwise look arbitrary: why padding exists at all, why a 55-byte message and a 56-byte message require different numbers of compression calls, and why an iterated hash admits attacks that a random function of the same width would not.

The primitive is a fixed-width compression function

The compression function h takes a chaining value of n bits and a message block of b bits and returns n bits. For SHA-256, n is 256 and b is 512, so each call consumes 64 bytes of padded input. The function itself is 64 rounds of 32-bit word addition, rotation, and bitwise selection. It has no notion of message length; it sees one block and one state.

Iteration is a left fold. The initial chaining value is a constant, the initialisation vector, which for SHA-256 is derived from the fractional parts of the square roots of the first eight primes. Round constants come from cube roots of the first sixty-four primes. Neither set is secret, and their provenance exists so that nobody has to trust a hidden trapdoor in the starting state.

$$ H_0 = IV, \qquad H_i = h(H_{i-1}, M_i), \qquad \mathrm{digest} = H_k $$

Two consequences follow immediately. The digest is the chaining value, so its width equals n and cannot exceed it. And the digest of a message is a function of the state reached at the end of that message, which means anything that lets an attacker reconstruct or continue from that state is a lever against the whole construction.

Variants such as SHA-512/256 are sometimes described as truncations of SHA-512. They are not: FIPS 180-4 assigns them distinct initialisation vectors, generated by a separate derivation function, so SHA-512/256 and the first 256 bits of SHA-512 are unrelated functions. The distinction matters because a truncated 512-bit digest and a native 256-bit digest have different preimage behaviour even though their widths agree.

Padding turns every message into whole blocks

Before iteration, the message is padded deterministically. SHA-2 appends a single 1 bit, then the fewest 0 bits that bring the total length to 448 modulo 512, then the original message length in bits as a 64-bit big-endian integer. The result is a multiple of 512 bits, and every call to h gets a full block.

The padding is never zero bytes. It occupies between 9 and 72 bytes: one byte carrying the marker bit, up to 63 bytes of zeros, and eight bytes of length. A message whose length is 55 bytes modulo 64 gains exactly 9 bytes and fits in one block. A message of 56 bytes modulo 64 gains 72 bytes and needs two blocks, because the length field no longer fits in the first.

def pad(message: bytes) -> bytes:
    bit_length = len(message) * 8
    # the mandatory 1 bit, plus the seven zeros that complete this byte
    out = message + b'\x80'
    # zeros until eight bytes remain in the current 64-byte block
    out += b'\x00' * ((56 - len(out) % 64) % 64)
    return out + bit_length.to_bytes(8, 'big')

The length field is 64 bits wide, so the standard defines SHA-256 only for messages shorter than 2^64 bits, which is 2 exabytes. A conforming implementation is not obliged to do anything sensible beyond that bound; the encoding simply cannot represent it. Long-message hashing schemes that need to exceed the bound do so by hashing a chunk structure rather than a single stream, an approach taken up in parallel tree hashing.

What the length field buys

Two separate properties are often conflated here. The first is injectivity of the padded encoding: distinct messages must not pad to the same byte string. The marker bit alone secures that, because the last block always contains a 1 bit whose position identifies where the message ended. Zero-only padding would not secure it, since a message and the same message with trailing zeros appended would pad identically.

The second property is what the security reduction needs, and it comes from the length field. The argument that a collision in the iterated hash implies a collision in the compression function runs by comparing final blocks. If two padded messages end in different final blocks but produce the same digest, then h collided on the last call. If they end in the same final block, the comparison steps back one block and repeats. For that induction to terminate in a compression-function collision, the final blocks of distinct messages must differ whenever the message lengths differ. Encoding the length guarantees exactly that. Without it, a message could be extended with a padding-shaped suffix that leaves the final block unchanged, and the induction would terminate at the initialisation vector instead of at a collision, which is to say the attacker gets a collision in the hash for free.

This is Damgård’s and Merkle’s independent result from 1989, and it is the reason the construction is named for both. It is also a narrow theorem: it says collision resistance of h implies collision resistance of H, and says nothing about the converse or about preimage behaviour.

Where the iteration stops being sound

The reduction gives collision resistance at the birthday bound of the chaining value, which for SHA-256 is 2^128 compression-function calls, and no better. Two structural weaknesses follow from the fold itself rather than from the compression function.

Length extension is the direct one. Because the digest is the state after the last block, anyone holding H(m) and the length of m can compute H(m || pad(m) || x) for arbitrary x without knowing m. The attack is treated in length extension and prefix-free encodings; it is the reason constructions that hash a secret before a message need a wrapper.

Multicollisions are the subtler one. Joux showed that if an attacker finds one collision in the compression function, the colliding pair can be spliced into a message at will, so k independent compression-function collisions yield 2^k messages that all share one digest. The total cost is about k times the birthday cost, not the k-fold product of it. A 256-bit iterated hash therefore does not offer “256 bits of collision resistance per block”; it offers 128 bits of collision resistance and, at roughly the same price, an exponentially large family of colliding messages. Any protocol that treats a single hash value as evidence of uniqueness across many messages has to account for that, and cascaded constructions such as hashing a hash inherit the problem rather than fixing it.

Second-preimage resistance degrades with message length. Kelsey and Schneier described a generic attack that, for a target message of 2^k blocks, finds a second message with the same digest in roughly 2^(n-k) work, for k up to about n/2. The definition asks for 2^n. Long messages are therefore weaker than the definition suggests, and the weakness is a property of the iterated structure, not of SHA-256’s round function.

Design alternatives and what they cost

The obvious repair is to stop exposing the internal state. The sponge construction, standardised in FIPS 202 as SHA-3, keeps a capacity portion of the state that is never read out, so a digest does not determine the state needed to continue. Its trade-off is throughput: bytes absorbed per permutation fall as capacity grows, which is why the rate and capacity split makes SHA3-512 roughly half as fast as SHA3-256 on the same permutation.

The other repair is to keep the fold but change the finalisation, as HAIFA-style designs do by feeding a block counter and a finalisation flag into the compression function. That blocks length extension and the fixed-point attacks without abandoning the sequential structure, at the cost of a slightly wider compression input. Sequential structure remains the real constraint either way: an iterated hash cannot be parallelised within a single message, because block i+1 needs the state produced by block i.