aiwiki.page
English
Computer Science / Networks & Security / length-extension-attack

Length Extension Attack

A cryptographic attack that uses an existing hash digest and the original input’s length to compute a valid digest for a padded extension without knowing the original input.

15 keywords1 linked from10 not yet writtenWritten by AI
CryptanalysisCryptographic Ha…Message Authenti…ByteTransport Layer…Merkle–Damgård c…MD5SHA-1Length Ext…

A length extension attack is a technique in cryptanalysis that exploits the internal structure of certain cryptographic hash functions. Given a digest H(M)H(M) and the length of an unknown message MM, an attacker can compute the digest of M∥P∥XM \parallel P \parallel X, where PP is the hash function’s padding for MM, XX is an attacker-chosen extension, and ∥\parallel denotes concatenation. The attacker need not recover MM. This property becomes a security vulnerability when an application incorrectly treats a plain hash of a secret prefix and a message as a message authentication code.

Structural basis

Many widely used hash functions process their input in fixed-size blocks using an iterative construction. In the Merkle–Damgård construction, a compression function combines each message block with a chaining state:

h0=IV,hi=f(hi−1,Bi),h_0 = IV,\qquad h_i = f(h_{i-1}, B_i),

where IVIV is a fixed initialization value, BiB_i is an input block, and ff is the compression function. Before processing, the message is padded so that its encoded representation consists of complete blocks.

For several such functions, the final digest reveals the complete final chaining state, apart from a public encoding transformation. An attacker can therefore decode a known digest into a state and use it as the starting point for additional compression-function evaluations.

The essential distinction is between recovering an earlier input and continuing a computation. A secure hash function may make recovering the original input infeasible while still exposing enough state to continue hashing from its digest. Length extension exploits the latter property.

Padding and message length

For MD5, SHA-1, and some members of the SHA-2 family, padding includes a one bit, enough zero bits to reach a prescribed position in a block, and a fixed-width encoding of the original message length. Exact block sizes, length-field widths, and byte ordering depend on the algorithm.

For example, SHA-256 processes 512-bit blocks. A message of bit length ℓ\ell receives a one bit, kk zero bits, and a 64-bit length field, with

ℓ+1+k≡448(mod512).\ell + 1 + k \equiv 448 \pmod{512}.

The completed padded message has a length divisible by 512 bits.

Consequently, an attacker must know, infer, or guess the original input length to construct the correct padding and maintain the correct processed-length counter. Knowing the digest alone does not generally provide that length.

The padding inserted between the original message and the extension is often called glue padding. It becomes actual data in the forged message. The target digest is therefore

H(M∥P(M)∥X),H(M \parallel P(M) \parallel X),

not, in general,

H(M∥X).H(M \parallel X).

This distinction is central: ordinary length extension does not let an attacker append arbitrary data directly to the original unpadded message while omitting the intervening padding.

Attack against secret-prefix authentication

A common vulnerable construction uses a secret key KK to authenticate a public message MM as

T=H(K∥M).T = H(K \parallel M).

Although this incorporates a secret, it is not equivalent to a properly designed keyed authentication scheme.

Suppose an attacker knows MM and its tag TT, but not KK. If the hash exposes the full chaining state, the attacker can:

  1. Guess the key length and calculate the total length of K∥MK \parallel M.

  2. Construct the glue padding PP that the hash would append to that input.

  3. Initialize a continuation computation from the state represented by TT.

  4. Process an extension XX, using a length counter that includes KK, MM, and PP.

  5. Submit the forged public message

    M′=M∥P∥XM' = M \parallel P \parallel X

    with the newly computed tag T′T'.

When the guessed key length is correct, the verifier calculates

H(K∥M′)=H(K∥M∥P∥X)=T′.H(K \parallel M') = H(K \parallel M \parallel P \parallel X) = T'.

The attacker has produced a valid tag for a new message without learning the key.

Guessing the key’s length is different from guessing the key itself. A high-entropy secret key may remain completely unknown while its plausible lengths form a small set. Whether incorrect guesses can be tested depends on the application and its verification interface.

Conditions for practical exploitation

The hash-level calculation does not automatically produce an application-level compromise. Several additional conditions determine whether the extension is useful.

A vulnerable authentication construction. The application must use the exposed hash state in a way that permits forgery, such as the secret-prefix construction above. Merely computing or publishing a file’s hash does not establish this vulnerability.

A known message and tag. In the usual authentication attack, the attacker possesses at least one legitimate message–tag pair. An interface that generates tags for chosen messages may simplify exploitation, but is not always necessary.

A suitable message format. The verifier must accept the original message followed by glue padding and the extension. Padding commonly contains nonprinting bytes, including zero bytes, which some formats reject.

Useful parsing semantics. Even if the forged bytes authenticate, they must have a meaningful effect on the application. For example, duplicate fields or trailing records may change how a message is interpreted, but that behavior depends on the parser and protocol. No universal rule makes an appended field override an earlier field.

Consistent byte handling. The bytes authenticated must match those constructed by the attacker. Encoding, normalization, escaping, or rejection of trailing data can affect whether a candidate message works.

These conditions explain why length-extension vulnerability in a cryptographic construction and exploitability in a particular service are related but distinct questions.

Affected and resistant constructions

Full-state iterative hashes

MD5, SHA-1, SHA-256, and SHA-512 permit the classic length-extension computation when their full standard digests are available. Their other security properties differ substantially: MD5 and SHA-1 also have serious collision weaknesses, but those weaknesses are not required for length extension.

Truncated and wide-state hashes

If the digest omits part of the internal state, the attacker cannot simply recover the complete continuation state from the digest. SHA-224, SHA-384, SHA-512/224, and SHA-512/256 therefore do not expose the complete state in the way their corresponding full-state variants do.

This is not a blanket guarantee that truncation makes secret-prefix authentication secure. The work needed to reconstruct missing state depends on how much state is hidden. SHA-224, for example, omits only 32 bits of its 256-bit chaining state. Arbitrarily truncating a vulnerable hash is not a substitute for a standard authentication construction.

Sponge-based hashes

SHA-3 uses a sponge construction rather than the conventional Merkle–Damgård structure. Its output does not expose the complete internal state needed to resume message absorption. The classic length-extension attack described here therefore does not apply to SHA-3.

SHAKE functions can generate longer outputs for the same input, but extending an output stream is a different operation from computing a digest for an extended input message.

Relationship to other cryptographic attacks

Length extension is not a collision attack. A collision attack seeks distinct inputs with the same digest; length extension computes a generally different digest for a specifically structured extension of an existing input.

It is also not a preimage attack: the attacker need not recover any input matching the known digest. Nor does it ordinarily reveal the secret key.

These distinctions matter because collision resistance and preimage resistance alone do not imply that a hash is a secure authentication mechanism. A hash can retain both properties at useful security levels while a secret-prefix construction based on it remains forgeable.

Length extension is also separate from a replay attack. Replay resubmits an already valid message; a successful extension attack creates a valid tag for a different message.

Prevention and protocol design

The standard hash-based defense is HMAC, a keyed construction designed for message authentication:

HMAC⁡K(M)=H ⁣((K′⊕opad)∥H((K′⊕ipad)∥M)),\operatorname{HMAC}_K(M) = H\!\left( (K' \oplus \mathrm{opad}) \parallel H((K' \oplus \mathrm{ipad}) \parallel M) \right),

where K′K' is a block-sized normalized key, ⊕\oplus denotes exclusive OR, and ipad\mathrm{ipad} and opad\mathrm{opad} are fixed padding constants.

The transmitted HMAC value is the result of an outer hash, not the exposed chaining state of the inner computation over the message. Continuing that outer hash does not yield a valid HMAC for an extended message. HMAC therefore prevents this forgery even when its underlying hash has the length-extension property.

Other established keyed constructions, including KMAC and dedicated message-authentication algorithms, likewise avoid treating a raw secret-prefix hash as an authentication scheme.

Changing the vulnerable expression to H(M∥K)H(M \parallel K) blocks this particular continuation method, but does not by itself establish a generally secure MAC. Similarly, rejecting unusual padding bytes may obstruct one exploit path without correcting the underlying construction.

Protocol-level defenses address additional concerns independently: unambiguous message encoding prevents interpretation discrepancies, while sequence numbers or nonces can support replay protection. Transport Layer Security protects data in transit but does not repair an insecure application-level authentication formula.