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 33-byte length is known)
known_message = b"user=alice&admin=false"
original_mac = sha256_scratch(secret + known_message)

extension = b"&admin=true"
secret_len = 33  # length known/guessed by the attacker
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.

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.

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

Naive length-extension forgery attempt on HMAC output: de4b20b143fcf46ce0f35b765ffa79ef5ff2cfa348f47d77eacd00eebf521996
Real HMAC of extended message                        : d788efc1c0c55ab56f8a4c874af42817bde54a8583471b88becc844b4f5d1e5d
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.

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).