SHA-256 and HMAC in Python: The Merkle-Damgård Construction, Length-Extension Attacks, and RFC 4231 Verification

Introduction

https://yuhi-sa.github.io/en/posts/20260614_cryptography_roadmap/1/ listed “SHA-2 / SHA-3 / BLAKE2 and HMAC” as a placeholder for a future article. And https://yuhi-sa.github.io/en/posts/20260715_tls13_handshake/1/ repeatedly used HMAC-SHA256 inside HKDF without ever explaining HMAC’s own construction principle. This article derives SHA-256 from the Merkle-Damgård construction and implements it from scratch, demonstrates with a real attack (the length-extension attack) why the naive design of simply concatenating a secret key and a message before hashing is dangerous, and then verifies how HMAC’s nested construction fixes this vulnerability.

SHA-256’s Construction: Merkle-Damgård

SHA-256 splits a message into 512-bit blocks and processes each one sequentially through a compression function, following the Merkle-Damgård construction:

where \(f\) is the compression function, \(M_i\) is the \(i\) -th message block, and \(H_i\) is the 256-bit (eight 32-bit words) intermediate state. The final \(H_n\) is the hash value. The crucial property of this construction is that the final output \(H_n\) depends only on the last intermediate state — not on “the entire original message” as a distinct object. This property is exactly what causes the length-extension attack below.

Padding

To make the message length a multiple of 512, a single 0x80 byte is appended, followed by zero bytes, followed by the original message length in bits, encoded as 64 bits.

The Compression Function

Each block goes through 64 rounds. In each round, eight hash variables \((a,b,c,d,e,f,g,h)\) are updated using bitwise boolean operations (\(\text{Ch}\) , \(\text{Maj}\) ) combined with bit rotations (\(\Sigma_0\) , \(\Sigma_1\) ):

\(K_i\) is one of 64 fixed constants (derived from the fractional parts of the cube roots of the first 64 primes), and \(W_i\) is the message schedule (the 16-word input block expanded to 64 words).

Python Implementation

The round constants \(K_i\) can be generated mechanically from “the fractional part of the cube root of the \(i\) -th prime” — no need to hardcode them.

import struct
import sympy

def first_n_primes(n):
    primes, candidate = [], 2
    while len(primes) < n:
        if sympy.isprime(candidate):
            primes.append(candidate)
        candidate += 1
    return primes

def frac_cube_root_bits(p):
    cube_root = p ** (1 / 3)
    frac = cube_root - int(cube_root)
    return int(frac * (2**32)) & 0xFFFFFFFF

MASK32 = 0xFFFFFFFF
K = [frac_cube_root_bits(p) for p in first_n_primes(64)]
H0 = [0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a,
      0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19]

def rotr(x, n):
    return ((x >> n) | (x << (32 - n))) & MASK32

def sha256_pad(msg, total_len_override=None):
    ml = (total_len_override if total_len_override is not None else len(msg)) * 8
    msg = msg + b"\x80"
    while (len(msg) * 8) % 512 != 448:
        msg += b"\x00"
    return msg + struct.pack(">Q", ml)

def sha256_compress(state, block):
    w = list(struct.unpack(">16I", block)) + [0] * 48
    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[i] = (w[i-16] + s0 + w[i-7] + s1) & MASK32

    a, b, c, d, e, f, g, h = state
    for i in range(64):
        S1 = rotr(e, 6) ^ rotr(e, 11) ^ rotr(e, 25)
        ch = (e & f) ^ (~e & g)
        temp1 = (h + S1 + ch + K[i] + w[i]) & MASK32
        S0 = rotr(a, 2) ^ rotr(a, 13) ^ rotr(a, 22)
        maj = (a & b) ^ (a & c) ^ (b & c)
        temp2 = (S0 + maj) & MASK32
        h, g, f, e, d, c, b, a = g, f, e, (d + temp1) & MASK32, c, b, a, (temp1 + temp2) & MASK32

    return [(x + y) & MASK32 for x, y in zip(state, [a, b, c, d, e, f, g, h])]

def sha256_scratch(msg, init_state=None, total_len_override=None):
    state = list(init_state) if init_state else list(H0)
    padded = sha256_pad(msg, total_len_override)
    for i in range(0, len(padded), 64):
        state = sha256_compress(state, padded[i:i+64])
    return b"".join(struct.pack(">I", x) for x in state)

The two extra arguments init_state and total_len_override are needed to “resume computation from an intermediate state” for the length-extension attack below (they’re unused in normal SHA-256 usage). Comparing the generated K against all 64 official FIPS 180-4 constants one by one, all 64 matched exactly — confirming that deriving them from the definition reproduces the hardcoded values in the spec.

Experiment 1: Exact Match Against hashlib

We compared the from-scratch implementation against hashlib.sha256 on four inputs: an empty string, a short string, a pangram, and a 1000-byte string.

All four match exactly, confirming the Merkle-Damgård construction, compression function, and padding are implemented correctly.

The Length-Extension Attack: Why H(secret ‖ message) Is Dangerous

A naive intuition says: “if we concatenate a secret key with a message before hashing, an attacker who doesn’t know the key shouldn’t be able to forge a message without detection.” Under the Merkle-Damgård construction, this intuition is wrong.

The attacker knows original_mac = SHA256(secret ‖ message) and the length of secret (often guessable or brute-forceable), but not the value of secret itself. However, since SHA-256’s final output is the last intermediate state, the attacker can reuse original_mac as the initial state for a new computation and compute SHA256(secret ‖ message ‖ glue_padding ‖ extension) without ever knowing secret (glue_padding is mechanically determined by SHA-256’s padding rule).

secret = b"s3cr3t-key-unknown-to-attacker!!"  # unknown to the attacker (assume only its 32-byte length is known)
known_message = b"user=alice&admin=false"
original_mac = sha256_scratch(secret + known_message)

extension = b"&admin=true"
secret_len = 32  # length known/guessed by the attacker (len(secret) == 32; off by even one byte and the forgery fails)
glue_padding = sha256_pad(b"\x00" * secret_len + known_message)[secret_len + len(known_message):]

forged_state = list(struct.unpack(">8I", original_mac))
forged_mac = sha256_scratch(
    extension,
    init_state=forged_state,
    total_len_override=secret_len + len(known_message) + len(glue_padding) + len(extension),
)

Output:

Original MAC = SHA256(secret || message): 06a4e85d01c06ec4a1c424c2e3db1d07349777dc0b18864d9f477b87912e9387
Forged MAC (attacker, no secret) : 7c0e1115cef381a74c5bf8a9f8dc7ef78d34e00ed94eb8afce3ba72773578076
Real MAC   (secret + full msg)   : 7c0e1115cef381a74c5bf8a9f8dc7ef78d34e00ed94eb8afce3ba72773578076
Attack succeeds: True

The attacker forged a valid MAC without ever knowing secret. The forged message — the original user=alice&admin=false with a privilege-escalating &admin=true appended — carries the exact same MAC value the server (which does know secret) would compute. This is the same class of known vulnerability that was actually exploited against Flickr’s API in 2009.

Caveat: secret_len being off by even one byte breaks the attack. Re-running the code above with secret_len set to 33 (one more than the actual 32) shifts the length of glue_padding, and forged_mac no longer matches real_mac (Attack succeeds: False). So the attack never requires knowing the value of secret — but it does require knowing (or correctly guessing, e.g. via brute force) its exact length. Because many real systems use a fixed key length (16 or 32 bytes, say) or one of a small number of candidates, this precondition is frequently satisfiable in practice — which is precisely why the design remains dangerous.

HMAC: A Nested Construction as a Defense (RFC 2104)

HMAC solves this problem by applying the hash function twice, nested, with the key mixed into both layers:

\(K'\) is the key padded to the block size (64 bytes for SHA-256), and \(\text{ipad}\) /\(\text{opad}\) are fixed patterns of 0x36/0x5c repeated 64 times.

def hmac_sha256_scratch(key, msg):
    block_size = 64
    if len(key) > block_size:
        key = sha256_scratch(key)
    key = key + b"\x00" * (block_size - len(key))
    o_key_pad = bytes(b ^ 0x5c for b in key)
    i_key_pad = bytes(b ^ 0x36 for b in key)
    inner = sha256_scratch(i_key_pad + msg)
    return sha256_scratch(o_key_pad + inner)

Experiment 2: Matching RFC 4231 Test Vectors

Using RFC 4231 Test Case 1 (a 20-byte key of repeated 0x0b, message "Hi There"), we compared the from-scratch implementation against Python’s standard hmac module.

scratch : b0344c61d8db38535ca8afceaf0bf12b881dc200c9833da726e9376c2e32cff7
hmac lib: b0344c61d8db38535ca8afceaf0bf12b881dc200c9833da726e9376c2e32cff7
match: True

They match exactly, confirming the RFC 2104 nested construction is implemented correctly.

Experiment 3: HMAC Resists the Length-Extension Attack

We attempted the same “reuse the MAC output as an initial state” attack against HMAC’s output. The attacker’s only public information is that HMAC’s block size is 64 bytes (RFC 2104), so they try reusing original_hmac as though it were the intermediate state of SHA256(64-byte-padded key ‖ known_message).

known_message = b"user=alice&admin=false"
extension = b"&admin=true"
hmac_key = b"hmac-secret-key-of-any-length"
original_hmac = hmac_sha256_scratch(hmac_key, known_message)

# The attacker only knows the 64-byte block size, so they assume the state came
# from a 64-byte-padded key followed by known_message, and try to continue from there
assumed_prefix_len = 64 + len(known_message)
glue_padding = sha256_pad(b"\x00" * assumed_prefix_len)[assumed_prefix_len:]

fake_forged_state = list(struct.unpack(">8I", original_hmac))
naive_forged = sha256_scratch(
    extension,
    init_state=fake_forged_state,
    total_len_override=assumed_prefix_len + len(glue_padding) + len(extension),
)
real_hmac_of_extended = hmac_sha256_scratch(hmac_key, known_message + glue_padding + extension)

Output:

original_hmac        : 41761b3768c7c93c847725233afcadfc57cd8d66fab9ca3d3daddc5422f743b6
naive_forged          : d271cb903261507c9b97d1bdc306dd94cac0e6ee36134fc5f0ded05dd83a9425
real_hmac_of_extended: c3d71f89be480af38ea463b8494bc345b8fb6ce4f5539ef7019fd873bc1b9037
Naive attack succeeds (should be False): False

The forgery failed. HMAC’s output is the result of hashing \(K'\oplus\text{opad}\) prepended to the inner hash \(H(K'\oplus\text{ipad} \Vert m)\) — resuming that outer hash computation requires \(K'\oplus\text{opad}\) , i.e., the key itself. Since the attacker only ever sees the final output, they can’t reconstruct the outer hash’s “input,” so an attack that reuses the inner intermediate state simply doesn’t apply. This is precisely why a raw hash function should never be used directly as a MAC — a vetted construction like HMAC is required.

Edge Cases and Design Caveats

SHA-3 (Keccak) isn’t Merkle-Damgård, so this specific attack doesn’t apply

The length-extension attack stems from a property specific to the Merkle-Damgård construction: the hash function’s final output can be reused directly as the initial state for further computation. SHA-3 (Keccak), by contrast, uses a sponge construction — only part of its 1600-bit internal state (the “rate” portion) is ever exposed as output; the rest (the “capacity” portion) cannot be recovered from the output. So SHA3-256(secret ‖ message) cannot be forged by the technique in this article.

That doesn’t mean using raw SHA3-256 directly as a MAC is fine, though. SHA-3 itself doesn’t expose an official keyed API, and the secret ‖ message concatenation pattern can still have other attack surfaces beyond length extension (implementation-dependent timing differences, for instance). NIST SP 800-185 defines KMAC (a Keccak-based MAC) as the keyed construction for the SHA-3 family — rather than mixing the key directly into the hash input, it uses Keccak’s generalized cSHAKE for proper domain separation. Instead of checking case-by-case whether your hash function’s internal construction happens to resist length extension, it’s safer to default to a vetted keyed construction like HMAC or KMAC every time.

Truncating HMAC’s output doesn’t change its length-extension resistance

RFC 4231 permits truncating HMAC-SHA-256’s output to 96 or 128 bits. Truncation affects collision-resistance arguments (it reduces the exhaustive-search cost an attacker faces), but it’s irrelevant to length-extension resistance. The attack’s precondition is “the final state can be reused as the initial state for further computation” — and HMAC already blocks that at the point where the outer hash’s input can’t be reconstructed, regardless of how many bits of the final output are kept.

A length-extension attack found in the wild in 2025

Length-extension attacks aren’t just “a 2009 Flickr story.” In October 2025, security researcher Frank Denis published a proof-of-concept length-extension attack against CDN provider BunnyCDN’s token authentication scheme, which was built on the pattern SHA256(secret ‖ query_string). He demonstrated that an attacker who never learns the secret key can still forge a validly-signed URL by appending a parameter such as role=admin to an existing signed URL. This case shows that the naive “concatenate a secret key with a message before hashing” MAC design is still finding its way into production systems nearly 17 years later.

Related Articles

• Cryptography Roadmap: Classical Ciphers, Symmetric Keys, RSA, Diffie-Hellman, Elliptic Curves, Hashing, Signatures, and TLS in Python - This article implements one of this hub’s “planned for the future” placeholders.
• Dissecting the TLS 1.3 Handshake in Python - Implements how this article’s HMAC-SHA256 is used repeatedly inside HKDF.
• Digital Signatures (ECDSA / EdDSA / RSA-PSS): Theory and Python Implementation - Signature schemes also sign a hash rather than the message itself, making hash-function security foundational there too.
• AES / ChaCha20 Symmetric Cryptography: Theory and Python Implementation - AEAD’s built-in authentication (tamper detection) serves the same “message authentication” purpose as this article’s HMAC, integrated directly into encryption.

References

• National Institute of Standards and Technology (2015). Secure Hash Standard (SHS). FIPS PUB 180-4.
• Krawczyk, H., Bellare, M., & Canetti, R. (1997). HMAC: Keyed-Hashing for Message Authentication. RFC 2104.
• Nystrom, M. (2005). Identifiers and Test Vectors for HMAC-SHA-224, HMAC-SHA-256, HMAC-SHA-384, and HMAC-SHA-512. RFC 4231.
• Duong, T., & Rizzo, J. (2009). Flickr’s API Signature Forgery Vulnerability (a real-world length-extension attack).
• Kelsey, J., Chang, S., & Perlner, R. (2016). SHA-3 Derived Functions: cSHAKE, KMAC, TupleHash, and ParallelHash. NIST SP 800-185.
• Denis, F. (2025). Length-Extension Attacks Are Still a Thing. 00f.net (a 2025 real-world case against BunnyCDN’s token authentication).