Length Extension and Prefix-Free Message Encoding

A server issues a token whose content is the string user=guest followed by the SHA-256 of secret || user=guest, where secret is a fixed key the server never reveals. A client that holds the token and nothing else can produce a second, longer token that the server will also accept, with user=admin appended. The client never learns the secret and never needs to; it needs only the digest, which was handed to it. The construction that makes this possible is the same one that makes SHA-256 fast, and the fix is a framing rule rather than a different hash.

The digest is the state

In the Merkle-Damgård fold, the output is the chaining value after the last block: H(m) = H_k where each H_i = h(H_{i-1}, M_i). Nothing is discarded, encrypted, or truncated after the final compression call for a full-width digest. The published digest is literally the internal state that the next compression call would consume.

An attacker who knows H(m) therefore knows the chaining value to resume from. To compute H(m || suffix), the attacker needs to feed suffix through the same padding and iteration, starting at that chaining value. Padding is public and deterministic, so they can compute it. The unknown message m never has to be recovered.

The one piece of information the attacker needs beyond the digest is the length of m, because the padding depends on it. Lengths are usually leaked by the protocol: a token format has a predictable prefix, or the attacker can count characters, or the server reports an error that reveals it. Even a coarse estimate narrows the search to a handful of candidates, each cheap to test.

Executing the attack

Take a message authentication scheme of the form MAC = SHA256(secret || message). The secret is unknown, its length is L bytes. The attacker holds MAC for a message m of known length.

import struct

def sha256_padding(length_bytes: int) -> bytes:
    """The padding SHA-256 appends to a message of this length, per FIPS 180-4."""
    bit_len = length_bytes * 8
    zeros = (56 - (length_bytes + 1) % 64) % 64
    return b'\x80' + b'\x00' * zeros + struct.pack('>Q', bit_len)

def extend(secret_len: int, known_msg: bytes, append: bytes) -> bytes:
    """Assemble the forged message. Its digest is the digest of
    secret || known_msg || padding || append, obtained by resuming the
    compression function with the published digest as the chaining value."""
    glue = sha256_padding(secret_len + len(known_msg))
    return known_msg + glue + append

Producing the digest for that message is the part a stock library will not do, because hashlib and its equivalents expose no way to set the initial chaining value. An implementation that exposes a resumable context, or that calls the compression function directly, does it in a few lines: set the chaining value to the known digest, set the running length counter to secret_len + len(known_msg) + len(glue), then absorb append and finalise. The forged message is secret || known_msg || pad || append, and its MAC is valid because it is genuinely the hash of that byte string under the same key.

The attacker cannot choose append freely at the byte level if the protocol parses the result, because the padding bytes sit between m and append. For binary-safe formats that is irrelevant. For formats where \x80 and zero bytes are illegal, the attacker’s freedom is constrained but often not eliminated, since a parser that stops at a delimiter or that ignores trailing data will accept the concatenation anyway.

Why HMAC is shaped the way it is

HMAC is the standard answer, and its structure is a direct response to this attack. It computes H((K ⊕ opad) || H((K ⊕ ipad) || m)). The inner hash produces a fixed-width value, and the outer hash takes that value as its entire message. An attacker who holds the outer digest would have to continue from a state whose input was the inner digest, and appending to the message changes the inner digest rather than extending it. The inner digest is 32 bytes, so its padding is fixed and the outer message length is known and constant, which removes the length ambiguity the attack depends on.

Two design details matter. The inner and outer pads differ by a single bit, which prevents the two uses of the hash from colliding into the same computation. And keys longer than the block size are hashed first, which compresses them to n bits before use, so a long key does not turn into multiple compression blocks with a variable padding position.

The cost is three compression calls’ worth of overhead beyond the message itself: two for the key pads and one for the outer hash. For short messages that dominates, which is why truncated HMAC variants exist and why sponge-based MACs avoid the overhead entirely.

Prefix-free encodings as the general fix

HMAC is a specific construction. The general principle is that the hash input must be encoded so that no valid encoding is a prefix of another valid encoding. If that holds, then for any two distinct messages x and y, the padded encodings diverge before either ends, and the reduction to a compression-function collision goes through without the attacker being able to splice.

Several encodings achieve it.

Length-prefixing prepends or appends the message length outside the hash input, so H(len || m) and H(len' || m') cannot be confused. This is what SHA-2’s trailing length field does internally, and it is why the padding is injective. It does not stop extension, because the attacker can still compute the padded form; it only ensures distinct messages produce distinct padded strings.

A separator byte that cannot appear in the message is the simplest approach for structured data. If messages are sequences of fields that never contain 0x00, then a 0x00 separator makes the encoding prefix-free. The cost is a constraint on the message alphabet, which is often unacceptable for binary payloads.

Encoding the structure rather than the bytes is the more general fix: hash the number of fields, then each field’s length, then the field. A length-prefixed sequence is prefix-free by construction, and it also prevents field-boundary ambiguity, which is a separate class of attack where ("ab", "c") and ("a", "bc") produce the same concatenation.

Where the same mistake reappears

The pattern is not specific to MACs. Anywhere a hash is computed over a concatenation of values that an attacker can influence, the framing has to be checked.

Signature schemes that hash a structured message need domain separation so that a signature over one type of object cannot be replayed as a signature over another. A common failure is hashing H(prefix || data) where prefix is attacker-controlled and of variable length, which lets an attacker shift bytes across the boundary. Fixed-width or length-prefixed prefixes remove the freedom.

Commitment schemes have the same shape. A commitment H(value || nonce) must bind the nonce length, or a prover can claim a different split of the concatenation later. The standard repair is to hash a length-prefixed encoding of both parts.

Merkle tree nodes are the largest instance of this class, and they get their own treatment in domain separation in Merkle trees. The leaf-intermediate collision there is a second-preimage attack built on exactly the same confusion between a value and its encoding.

Constructions that are immune by structure

Sponge-based hashes do not expose their state, so a digest cannot be used as a chaining value. The capacity bits at the end of absorption are unknown to anyone who has only the output, and they feed the permutation on any continuation. That removes the attack at the structural level rather than by convention, as described in rate and capacity in the sponge.

Truncated digests are partially immune, in a way that depends on the truncation width. If a digest is truncated to t bits and the capacity or state is s bits, continuing requires guessing the remaining s - t bits, which is 2^(s-t) work. Truncating a SHA-256 digest to 128 bits leaves 128 bits of state unknown and makes extension cost 2^128, which is out of reach but is a security reduction rather than an impossibility. Truncation is a mitigation with a stated cost, not a fix.

The cleanest structural fix is to stop using a raw hash where a MAC is wanted. HMAC, KMAC, BLAKE3’s keyed mode, and the various tree-mode keyed variants all define a mode that is not vulnerable, and picking one of them removes the need to reason about framing at the call site. The remaining risk is a protocol that defines its own construction and gets the framing wrong, which is where the attack continues to appear.