Forging MACs with a Hash Length-Extension Attack

Forging MACs with a Hash Length-Extension Attack

Introduction

A message authentication code proves a message came from someone who holds a shared secret. A tempting way to build one is to hash the secret together with the message: tag = H(secret || message). The server keeps the secret, so an attacker who does not know it cannot compute the tag, or so the reasoning goes.

That reasoning is wrong for every hash with a Merkle-Damgard structure, which includes MD5, SHA-1, and SHA-256. A length-extension attack lets an attacker who knows the tag and the length of the secret append their own data to the message and compute a valid tag for the longer message, without ever learning the secret. This guide performs the attack on SHA-256, forges a privilege escalation, and shows why HMAC is the construction that actually works.

Table of Contents

• Where the Weakness Comes From
• The Attack
• The Glue Padding
• Interactive Visualizer
• A Worked Example
• Python Implementation
• Limitations
• Security Status
• FAQ
• References

Where the Weakness Comes From

A Merkle-Damgard hash processes its input in fixed-size blocks, carrying a running internal state from one block to the next. SHA-256 uses 64-byte blocks and a 256-bit state. It starts the state at a fixed constant, mixes in each block, and at the very end appends padding and a length field and mixes those in too. The final state, after the last block, is the digest. There is no extra finalization step that hides it.

That is the whole weakness. The digest an attacker sees is not just an output, it is the full internal state of the hash at the point it stopped. Anyone holding the digest can set a fresh hash’s state to those exact values and keep going, as if more data had followed. The hash cannot tell the difference between a state it reached itself and one that was handed to it.

The Attack

Suppose a server authenticates messages with tag = SHA-256(secret || message) and an attacker has intercepted one message and its tag. The attacker also knows, or can guess, the length of the secret. That is all they need.

1. Resume the state. The intercepted tag is the hash’s internal state after processing secret || message and its padding. Unpack the 32-byte tag into the eight 32-bit state words.
2. Account for the original padding. The original hash appended padding to bring secret || message up to a block boundary. The attacker can compute exactly those bytes, called the glue padding, from the known total length, even without the secret’s contents.
3. Extend. Set a fresh SHA-256 to the resumed state, tell it that secret || message || glue bytes have already been processed, and feed it the attacker’s chosen extension. The result is a valid tag for the forged message message || glue || extension.

The server, given the forged message, computes SHA-256(secret || message || glue || extension) and gets the identical tag. It accepts the forgery, because the math is exactly the same computation, just split across the attacker and the server.

The Glue Padding

The one visible artifact of the attack is the glue padding. It sits between the original message and the attacker’s extension, and it is the padding SHA-256 would have added to secret || message: a 0x80 byte, then zero bytes, then the 64-bit length. Those bytes are not printable, so the forged message contains a run of binary garbage in the middle.

In practice this rarely saves the defender. Many formats ignore unexpected bytes, and many parsers take the last value for a repeated field. A query string like user=alice&role=guest followed by glue and then &role=admin is read by a typical parser as role=admin, because the last assignment wins. The attacker appends their own trailing data and lets the parser do the rest.

Interactive Visualizer

The visualizer above plays both sides. The server holds a secret you never see and authenticates a message with tag = SHA-256(secret || message). The attacker, given only the message, the tag, and the length of the secret, chooses an extension to append. The attack forges a tag, and the visualizer checks it against what the server would compute for the forged message, with the secret. The two match every time.

Change the extension, or the assumed secret length, and watch the forged tag still verify when the length is right and fail when it is wrong. The secret itself never enters the attacker’s side of the computation.

A Worked Example

The server’s secret is s3cr3t-api-key-value, twenty bytes the attacker never sees. The message and its tag are intercepted:

intercepted message: user=alice&role=guest
intercepted tag:     57a2ac3c05c161e35936c42ad9cf190561532e1f689e42a3831b7f50d3c34794
secret length known: 20

Knowing only the length of the secret, the attacker appends &role=admin and forges a tag:

forged tag:          158c79ed9561d7550c581c27e5b63057b3fc4cbbc8c315b0025b27302c8297ee
server would accept:  158c79ed9561d7550c581c27e5b63057b3fc4cbbc8c315b0025b27302c8297ee
forgery valid:       True

The forged tag matches exactly what the server computes for the extended message, so the server accepts a request ending in &role=admin, which a query parser reads as an administrator role. The attacker never recovered the secret. They only needed its length, which is often fixed, documented, or quickly found by trying each value until a forgery verifies.

Python Implementation

The code is a from-scratch SHA-256 whose compression can be resumed from a given state, plus the attack itself. The resumable sha256 takes an optional starting state and a count of bytes already processed, which is exactly what length extension needs.

import hashlib, struct, os

# ---- SHA-256 from scratch, with a resumable compression ----
_K = [
    0x428a2f98,0x71374491,0xb5c0fbcf,0xe9b5dba5,0x3956c25b,0x59f111f1,0x923f82a4,0xab1c5ed5,
    0xd807aa98,0x12835b01,0x243185be,0x550c7dc3,0x72be5d74,0x80deb1fe,0x9bdc06a7,0xc19bf174,
    0xe49b69c1,0xefbe4786,0x0fc19dc6,0x240ca1cc,0x2de92c6f,0x4a7484aa,0x5cb0a9dc,0x76f988da,
    0x983e5152,0xa831c66d,0xb00327c8,0xbf597fc7,0xc6e00bf3,0xd5a79147,0x06ca6351,0x14292967,
    0x27b70a85,0x2e1b2138,0x4d2c6dfc,0x53380d13,0x650a7354,0x766a0abb,0x81c2c92e,0x92722c85,
    0xa2bfe8a1,0xa81a664b,0xc24b8b70,0xc76c51a3,0xd192e819,0xd6990624,0xf40e3585,0x106aa070,
    0x19a4c116,0x1e376c08,0x2748774c,0x34b0bcb5,0x391c0cb3,0x4ed8aa4a,0x5b9cca4f,0x682e6ff3,
    0x748f82ee,0x78a5636f,0x84c87814,0x8cc70208,0x90befffa,0xa4506ceb,0xbef9a3f7,0xc67178f2,
]
_H0 = [0x6a09e667,0xbb67ae85,0x3c6ef372,0xa54ff53a,0x510e527f,0x9b05688c,0x1f83d9ab,0x5be0cd19]
_M = 0xffffffff


def _rotr(x, n):
    return ((x >> n) | (x << (32 - n))) & _M


def _compress(h, block):
    w = list(struct.unpack(">16I", block))
    for i in range(16, 64):
        s0 = _rotr(w[i-15], 7) ^ _rotr(w[i-15], 18) ^ (w[i-15] >> 3)
        s1 = _rotr(w[i-2], 17) ^ _rotr(w[i-2], 19) ^ (w[i-2] >> 10)
        w.append((w[i-16] + s0 + w[i-7] + s1) & _M)
    a, b, c, d, e, f, g, hh = h
    for i in range(64):
        S1 = _rotr(e, 6) ^ _rotr(e, 11) ^ _rotr(e, 25)
        ch = (e & f) ^ (~e & g)
        t1 = (hh + S1 + ch + _K[i] + w[i]) & _M
        S0 = _rotr(a, 2) ^ _rotr(a, 13) ^ _rotr(a, 22)
        maj = (a & b) ^ (a & c) ^ (b & c)
        t2 = (S0 + maj) & _M
        a, b, c, d, e, f, g, hh = (t1 + t2) & _M, a, b, c, (d + t1) & _M, e, f, g
    return [(x + y) & _M for x, y in zip(h, [a, b, c, d, e, f, g, hh])]


def padding(msg_len_bytes):
    # the bytes SHA-256 appends: 0x80, zeros to 56 mod 64, then the 64-bit big-endian bit length
    bitlen = msg_len_bytes * 8
    pad = b"\x80" + b"\x00" * ((56 - (msg_len_bytes + 1) % 64) % 64)
    return pad + struct.pack(">Q", bitlen)


def sha256(data, h=None, already_len=0):
    # h and already_len let us RESUME from a known internal state (the length-extension trick)
    h = list(_H0) if h is None else list(h)
    total = already_len + len(data)
    data = data + padding(total)
    for i in range(0, len(data), 64):
        h = _compress(h, data[i:i + 64])
    return struct.pack(">8I", *h)


def digest_to_state(digest):
    return list(struct.unpack(">8I", digest))


# ---- the attack ----
def length_extension(original_digest, original_len, extension):
    # original_digest = H(secret || message); original_len = len(secret || message) in bytes.
    # Returns (glue, forged_digest) where the forged message is message || glue || extension and
    # forged_digest is H over secret || message || glue || extension, computed WITHOUT the secret.
    glue = padding(original_len)
    resumed_len = original_len + len(glue)          # a multiple of 64
    h = digest_to_state(original_digest)
    forged = sha256(extension, h=h, already_len=resumed_len)
    return glue, forged


if __name__ == "__main__":
    # sanity: our SHA-256 matches the library
    assert sha256(b"abc").hex() == hashlib.sha256(b"abc").hexdigest()
    assert sha256(b"").hex() == hashlib.sha256(b"").hexdigest()
    assert sha256(b"a" * 1000).hex() == hashlib.sha256(b"a" * 1000).hexdigest()
    print("SHA-256 matches hashlib: True")

    secret = b"s3cr3t-api-key-value"              # unknown to the attacker
    message = b"user=alice&role=guest"
    tag = sha256(secret + message)                 # the server's naive MAC = H(secret || message)
    print("intercepted message:", message.decode())
    print("intercepted tag:    ", tag.hex())
    print("secret length known:", len(secret))

    extension = b"&role=admin"
    glue, forged_tag = length_extension(tag, len(secret) + len(message), extension)

    forged_message = message + glue + extension
    # what the server computes for the forged message, WITH the secret:
    server_tag = sha256(secret + forged_message)
    print("forged tag:         ", forged_tag.hex())
    print("server would accept: ", server_tag.hex())
    print("forgery valid:      ", forged_tag == server_tag)
    print("forged message ends with:", forged_message[-11:])

Running it prints the worked example:

SHA-256 matches hashlib: True
intercepted message: user=alice&role=guest
intercepted tag:     57a2ac3c05c161e35936c42ad9cf190561532e1f689e42a3831b7f50d3c34794
secret length known: 20
forged tag:          158c79ed9561d7550c581c27e5b63057b3fc4cbbc8c315b0025b27302c8297ee
server would accept:  158c79ed9561d7550c581c27e5b63057b3fc4cbbc8c315b0025b27302c8297ee
forgery valid:       True
forged message ends with: b'&role=admin'

Limitations

This is a faithful demonstration of a real attack, with a few practical notes:

• It needs the secret’s length, not its value. The attack works for any one length. When the length is unknown, the attacker tries each candidate and keeps the one whose forgery verifies, which is cheap.
• The forged message carries glue bytes. The binary glue padding sits between the original message and the extension. The attack is only useful where the receiving format tolerates or ignores those bytes, which many do.
• It applies to Merkle-Damgard hashes used as raw MACs. MD5, SHA-1, SHA-256 and SHA-512 are vulnerable in the H(secret || message) construction. It does not apply to HMAC, to SHA-3, or to BLAKE2, which are built so the final state is not the whole story.

Security Status

• Never use H(secret || message) as a MAC. It is one of the most common homegrown-crypto mistakes, and it has broken real systems, including the Flickr API signature scheme in 2009.
• Use HMAC. HMAC wraps the hash as H(key xor opad || H(key xor ipad || message)), so the value an attacker sees is the output of an outer hash whose own input they cannot control. Length extension gives them nothing. The HMAC guide covers it.
• Or use a hash that resists extension. SHA-3 and BLAKE2 are designed so the digest is not the full internal state, so even H(secret || message) is not extendable with them. HMAC remains the standard, portable choice.

FAQ

Why does knowing the length of the secret matter?

The attacker has to reproduce the exact padding the original hash applied to secret || message, and that padding depends only on the total length. With the length, the glue bytes are determined; without it, the attacker guesses lengths until a forgery verifies.

Does the attacker ever learn the secret?

No, it never does. The attack never recovers or needs the secret’s contents. It only resumes the hash from the tag, which is why a long, high-entropy secret does not help: its length is all that is used.

Why isn’t HMAC vulnerable?

HMAC hashes twice, with the key mixed into both an inner and an outer hash. The tag is the output of the outer hash, and an attacker cannot extend it because they cannot control the outer hash’s input, which is itself a hash output. The construction is specifically designed to close this gap.

Does this work on SHA-3 or BLAKE2?

No, neither one is vulnerable. SHA-3 uses a sponge construction and BLAKE2 adds a finalization flag, so in both the digest is not the complete internal state. The resume trick has nothing to resume from, so H(secret || message) is safe with them, though HMAC is still the usual recommendation.

Is the forged message valid even with the binary glue in the middle?

It depends on the receiver. The glue padding is non-printable, but many parsers skip unknown bytes or honor the last value of a repeated field, so the extension still takes effect. Where the format rejects the glue, the attack does not apply.

References

1. The HMAC guide on this site, the correct construction that defeats this attack: /blog/hmac_guide/

2. The SHA-2 guide on this site, whose SHA-256 this breaker reuses and resumes: /blog/sha2-hash/

3. Duong, Thai, and Juliano Rizzo. “Flickr’s API Signature Forgery Vulnerability,” 2009 (a real length-extension break of a deployed signature scheme).