Step 234. Hash Attacks: Length Extension and Collision Concepts — What Happens When You Use a Hash as a "Signature"

Level 3 — Real-World CTF & Advanced Offensive Skills | Difficulty ★★★☆☆ | Estimated time: 4 hours

Prerequisites: the mod instincts from Step 227 (Crypto Math Foundations) and the symmetric-crypto flow through Step 233 (AES). Today we use only Python’s standard library hashlib.

⚠️ All exercises in this chapter are for your own lab and legal platforms only. Applying them to unauthorized systems is a crime.

What you need: Python 3 (measured: 3.12.14). No external tools — standard library only.
Caution: the "toy hash" we build today is a teaching toy for understanding structure. It imitates a real hash; it is not one.

A hash is a fingerprint — change the input by a single bit and the output flips entirely, and you can’t reverse it. But assemble this safe tool the wrong way and it becomes an attack. The classic case is the length extension attack: on a server that uses H(secret + message) like a "signature," an attacker forges a valid new signature with extra data appended — without knowing the secret key. Today you’ll pull off this attack yourself on a scaled-down model, and organize why MD5 and SHA-1 were retired (collisions) and why HMAC is safe.

1. Learning Objectives

By the end of this chapter, you will be able to:

Explain that Merkle-Damgård hashes "carry forward internal state"
Reproduce the length extension attack’s conditions and procedure on a scaled-down model
Measure the avalanche effect (a 1-bit difference → total output change) with hashlib
Organize the fates of collision-broken MD5 and SHA-1 and where SHA-256 stands
Explain the structural reason HMAC is safe against length extension

2. Background Knowledge — Today’s Tools and Concepts

Today’s Tools at a Glance

Category	Details
Language/environment	Python 3 (measured: 3.12.14) — standard library `hashlib` only, nothing to install
Today’s commands	`hashlib.sha256()`, `.md5()`, `.sha1()`, `.hexdigest()` + a hand-built toy hash
Concepts needed	Merkle-Damgård construction, padding, length extension attack, collision resistance, HMAC
Today’s deliverable	Avalanche-effect output + a successful length-extension forgery (toy hash) + defense notes

2-1. What a Hash Promises — Three Properties

A cryptographic hash function promises three things. ① Preimage resistance: you cannot reconstruct the input from the hash. ② Second-preimage resistance: given one input, it’s hard to find a different input with the same hash. ③ Collision resistance: finding any two inputs with the same hash is hard at all.

The avalanche effect is a symptom of these promises — change the input by a single bit and about half the output bits flip randomly. We confirm it by measurement today.

2-2. The Merkle-Damgård Construction — A Hash That Carries State Forward

MD5, SHA-1, and the SHA-2 family (including SHA-256) all use the Merkle-Damgård construction. The input is split into fixed-size blocks, and each block is compressed into an "internal state" in turn. The internal state after the final block is the hash output.

Here’s the crux — the hash output is the internal state, published as-is. Anyone who knows H(X) effectively holds "the internal state right after processing X," and can continue the computation from that state. That is the entire length extension attack.

2-3. The Length Extension Attack — Not a Signature, but Playing One

Suppose a server authenticates requests with signature = H(secret + message). The attacker doesn’t know the secret. But knowing the original message and signature, and guessing the secret’s length (usually by brute force), they forge like this:

original : H(secret || msg) = sig
attack   : adopt sig as the "internal state," compress || suffix after the padding
result   : H(secret || msg || padding || suffix) computed successfully, no secret needed

The server receives msg + padding + suffix, computes H(secret + that) its own way — and it matches the attacker’s forgery exactly. Appending &role=admin to a message requires no secret key. Today we actually run this.

2-4. Collisions and HMAC — Why MD5 Was Retired

A collision is the event of two different inputs having the same hash. Ideally, finding one in a 256-bit hash should take 2¹²⁸ tries, but structural weaknesses were found in MD5 and collision pairs became creatable in practical time (since 2004); SHA-1 got its death sentence in 2017 when Google published a real colliding file pair (SHAttered).

The answer to length extension is HMAC — H(k⊕opad || H(k⊕ipad || m)). Because the inner hash’s result is wrapped in another hash, the output is not "an internal state you can continue from." SHA-3 (Keccak) also has a different structure (sponge construction), so length extension doesn’t work there either.

3. Follow Along

All output in this chapter was measured 2026-09-09 on Python 3.12.14.

3-1. The Avalanche Effect — The Result of a 1-Bit Difference

import hashlib

a, b = "hello", "hellp"   # last byte 'o' -> 'p' (a 1-bit difference)
ha = hashlib.sha256(a.encode()).hexdigest()
hb = hashlib.sha256(b.encode()).hexdigest()
print("SHA256(hello) =", ha)
print("SHA256(hellp) =", hb)
diff = sum(1 for x, y in zip(ha, hb) if x != y)
print("differing hex digits:", diff, "/ 64")

SHA256(hello) = 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824
SHA256(hellp) = fdd7585e08c4e2afd71dcabdb4636c89d557a3f42db9e2040c8bbd1708aa4ce7
differing hex digits: 63 / 64

How to read the output: a 1-bit difference changed 63 of 64 digits. There’s no correlation between the two hashes — that "similar inputs give similar outputs" does not hold is the life of a hash.

Regardless of input length, the output length is always the same:

print("SHA256(empty) =", hashlib.sha256(b"").hexdigest())
print("SHA256(1MB)   =", hashlib.sha256(b"A" * 1000000).hexdigest())

SHA256(empty) = e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855
SHA256(1MB)   = e23c0cda5bcdecddec446b54439995c7260c8cdcf2953eec9f5cdb6948e5898d

3-2. Building a Toy Merkle-Damgård Hash

SHA-256’s internals are complex, so let’s build an 8-bit toy with the structure scaled down. It carries state h forward, compressing each byte with h = (h*31 + b) % 256, and appends padding (0x80, 0x00s, and a 1-byte length) at the end.

class ToyMD:
    def __init__(self, h=0):
        self.h = h
    def compress(self, block_byte):
        self.h = (self.h * 31 + block_byte) % 256
    @staticmethod
    def padding_for(length):
        pad = bytearray([0x80])
        while (length + len(pad) + 1) % 4 != 0:
            pad.append(0x00)
        pad.append(length % 256)
        return bytes(pad)
    @classmethod
    def pad(cls, msg):
        return msg + cls.padding_for(len(msg))
    def digest(self, msg):
        for b in self.pad(msg):
            self.compress(b)
        return self.h

secret = b"s3cr3t!"
msg = b"id=guest"
server_sig = ToyMD().digest(secret + msg)
print("server's H(secret + msg) =", server_sig)

server's H(secret + msg) = 168

How to read it: one compress call corresponds to one call of a real hash’s "compression function." Only the complexity differs — the structure of "carry the state forward, process block by block, output the final state" is identical to SHA-256.

3-3. Running the Length Extension Attack

Now become the attacker. You don’t know the secret, but you know server_sig = 168 and the secret’s length (7 bytes).

key_len = 7                      # secret length (guessed by brute force in the field)
pad1 = ToyMD.padding_for(key_len + len(msg))
print("padding bytes:", pad1.hex())

suffix = b"&role=admin"
h2 = ToyMD(h=server_sig)         # adopting the state — the attack's core line
total_len = (key_len + len(msg) + len(pad1)) + len(suffix)
for b in suffix + ToyMD.padding_for(total_len):
    h2.compress(b)
forged_sig = h2.h
print("forged hash =", forged_sig)

# compare against what the server actually computes
real_sig2 = ToyMD().digest(secret + msg + pad1 + suffix)
print("server's own computation =", real_sig2)
print("match:", forged_sig == real_sig2)
print("forged message =", (msg + pad1 + suffix))

padding bytes: 800000000f
forged hash = 57
server's own computation = 57
match: True
forged message = b'id=guest\x80\x00\x00\x00\x0f&role=admin'

How to read the output: without knowing the secret, we produced a valid signature for a message with &role=admin appended. The \x80\x00\x00\x00\x0f in the middle of the forged message is the original padding’s residue — if the server parses the message as a string and ignores the padding or doesn’t treat it as a parameter delimiter (as real vulnerable systems did), this request goes through.

3-4. Why HMAC Is Safe

inner = ToyMD().digest(b"\x36" * key_len + msg)      # miniature of H(k⊕ipad || m)
outer = ToyMD().digest(b"\x5c" * key_len + bytes([inner]))  # H(k⊕opad || inner)
print("toy HMAC value:", outer)

toy HMAC value: 47

How to read it: HMAC’s output outer is not "the internal state after processing m" but an outer state that re-hashes the intermediate result inner. Even if an attacker adopts outer and appends a suffix, the result is H(k⊕opad || inner || ...), not H(k⊕opad || H(k⊕ipad || m || suffix)) — the structure seals off extension. In practice, use the hmac module. Never assemble it yourself.

3-5. MD5 and SHA-1 Today

print("MD5(hello)  =", hashlib.md5(b"hello").hexdigest())
print("SHA1(hello) =", hashlib.sha1(b"hello").hexdigest())

MD5(hello)  = 5d41402abc4b2a76b9719d911017c592
SHA1(hello) = aaf4c61ddcc5e8a2dabede0f3b482cd9aea9434d

How to read it: both still compute fine — the problem is that they’re "broken," not that they’re "gone." You’ll still meet them in non-adversarial uses like file-integrity checks, but in adversarial settings — signatures, authentication, passwords — they’re forbidden. When MD5/SHA-1 shows up in a CTF, put "a collision or rainbow table is likely the answer" on your candidate list.

4. Missions & Exercises

Mission — Reproducing and Defending the Length Extension Attack

Using 3-2’s ToyMD, build a server scenario with the secret changed to b"topsecret" (9 bytes) and succeed at forging a signature with &debug=1 appended via length extension — assume you don’t know the secret length and include a loop that brute-forces guesses 1~16
Change the same scenario to the H(msg + secret) order and explain in one line why length extension fails
Prove with output that the forged value matches the server’s computation

Exercises

Exercise 1. Explain why H(secret + msg)-style authentication is vulnerable to length extension, from the perspective of "the internal state being public."

Exercise 2. In the avalanche experiment, 63 of 64 digits changed. If some hash changed only 8 digits, which property’s destruction would you suspect?

Exercise 3. Answer in one sentence each: why MD5 was "retired for signature use," and why it’s still used for file-download integrity checks.

Exercise 4. Explain why HMAC is safe against length extension, comparing its structure with H(k + m). And how does SHA-3’s reason for safety differ from HMAC’s?

5. Model Answers & Completion Criteria

Mission Model Answer

The core is the "length-guessing loop" (pattern confirmed by measurement 2026-09-09):

secret = b"topsecret"          # known only to the server (must not appear in attacker code)
msg = b"id=guest"
server_sig = ToyMD().digest(secret + msg)

suffix = b"&debug=1"
for guess in range(1, 17):     # brute-force the secret length
    pad1 = ToyMD.padding_for(guess + len(msg))
    h2 = ToyMD(h=server_sig)
    total = guess + len(msg) + len(pad1) + len(suffix)
    for b in suffix + ToyMD.padding_for(total):
        h2.compress(b)
    pad1_real = ToyMD.padding_for(len(secret) + len(msg))
    if h2.h == ToyMD().digest(secret + msg + pad1_real + suffix):
        print(f"forgery succeeded at length {guess}: {h2.h}")
        break

How to verify: ① does the guessing loop succeed at length 9? ② for the H(msg + secret) order — since the hash processes msg first, the output state is a "later state" that includes the secret, but even if the attacker adopts it, the result is shaped like H(msg || secret || pad || suffix), which mismatches the server’s expected H(msg+secret) verification structure (with the secret at the end, appended data lands outside the secret, not after it) — did you explain this? ③ is there output showing the forged value matching the server’s value?

Exercise Answers

Answer 1. A Merkle-Damgård hash’s output is the internal state itself, right after finishing the input. Knowing H(secret + msg) lets you continue compressing from that state, so you can compute H(secret || msg || pad || extra data) without knowing the secret. The attack exists precisely because the output is the state.

Answer 2. A weak avalanche effect — and beyond that, you’d suspect destroyed collision resistance. If similar inputs have similar hashes, a guided attack becomes possible: nudge the input bit by bit and "approach" a desired hash.

Answer 3. Retired because: since 2004, collision pairs became generatable in practical time, letting an attacker swap in a different signed document. Still used for integrity because: in non-adversarial settings like download verification you only need to catch accidental corruption, and collision attacks are meaningless there (still, SHA-256 or better is recommended for new systems).

Answer 4. In H(k + m), the output is the internal state, so extension works. HMAC is H(k⊕opad || H(k⊕ipad || m)) — the outer hash’s input is the inner hash’s result, so adopting the output gives no way to extend the inner side. SHA-3 is a sponge construction, not Merkle-Damgård, so the output isn’t the full internal state (only part of the state is exposed) — it’s safe by structure alone: even SHA3(k + m) resists length extension without HMAC.

Completion Criteria Checklist

[ ] I can describe the Merkle-Damgård construction as "repeated compression carrying state forward"
[ ] I confirmed the avalanche effect with hashlib measurements
[ ] I succeeded at a length-extension forgery on the toy hash (match: True output)
[ ] I know the procedure for brute-forcing the secret length when it’s unknown
[ ] I can distinguish "MD5/SHA-1 are broken (collisions)" from "they still compute"
[ ] I can explain the structural reasons HMAC and SHA-3 are each safe
[ ] Mission: forgery script with the length-guessing loop complete

6. Common Pitfalls & Fixes

Wall 1. The forged value doesn’t match the server’s computation

Symptom: the match check in 3-3 prints False.
Cause: most commonly, you computed the padding based on "the original message length" instead of "the suffix length." The final padding must always be based on the total length the server will see (secret + msg + pad1 + suffix).
Fix: print the length you feed to padding_for() — the original padding should come out at 15 and the final at 31 (per the 3-3 measurement).

Wall 2. pow works, but adopting hash state doesn’t

Symptom: you can’t find a way to inject an arbitrary state into a hashlib.sha256 object.
Cause: the standard hashlib doesn’t allow internal-state injection — that’s why real length extension against SHA-256 needs dedicated tools like hashpump/hashpumpy (which manipulate state directly).
Fix: in this chapter, understand the structure with the toy hash; on real problems (CTFs), use hashpumpy in that platform’s environment. The principle is exactly what we measured today.

Wall 3. The server rejects the request because of the padding bytes

Symptom: the \x80\x00... in the middle of the forged message breaks the server’s parser.
Cause: real systems that normalize messages or reject special bytes.
Fix: such a system is (accidentally) less vulnerable to length extension — the attack’s condition is "the server hashes the message including the padding residue as-is." CTF problems are mostly designed to hash it as-is.

Wall 4. "If SHA-256 is breakable, why use it?"

Symptom: the fact that length extension works makes you distrust hashes altogether.
Cause: a confusion of use cases. Length extension attacks the misassembly H(secret + msg) — it is not a weakness of the hash itself. SHA-256 inside file fingerprints, integrity checks, and HMAC remains healthy.
Fix: write a table in your notes separating "algorithm weaknesses" from "assembly weaknesses."

Wall 5. I hashed "hello" with MD5 and got a different value than the book

Symptom: you got something other than 5d41402a....
Cause: an input-encoding difference — "hello" vs b"hello", or an included newline changes the hash.
Fix: make the input explicitly bytes (b"hello"), and read files in rb mode when hashing them.

7. Summary

Today’s Concepts

Concept	One-line explanation
Merkle-Damgård construction	A hash structure that compresses block by block, carrying state forward — MD5, SHA-1, SHA-2
Avalanche effect	A 1-bit input difference → half the output bits flip
Length extension attack	Adopt `H(secret+msg)`‘s output (= internal state) and forge appended data
Collision resistance	The property that two same-hash inputs are hard to find — destroyed in MD5 and SHA-1
Padding	Length info appended to the message’s end — an essential ingredient of length-extension math
HMAC	Standard message authentication that wraps the hash twice, sealing off length extension
SHA-3	Sponge construction — the output isn’t the full internal state, so length-extension resistant

Today’s Commands & Code

Command	What it does
`hashlib.sha256(b"...").hexdigest()`	SHA-256 hash (hex string)
`hashlib.md5() / .sha1()`	Retired hashes — for identification and analysis only
`ToyMD(h=value)` (hand-built)	A state-adopting toy hash — for demonstrating length extension
`padding_for(length)` (hand-built)	Compute the padding appended to a message of a given length

An Instinct More Important Than Commands

Today’s lesson is one — a safe component becomes a vulnerability when assembled wrong. SHA-256 is sturdy, but H(secret + msg) breaks. Conversely, HMAC merely wraps the same hash twice, and the structure seals off the attack. From now on, whenever you meet a design that "uses a hash like a signature" in any system, recall that one line we measured today — adopting the state.

Once every box is checked, Step 234 is complete. Click the checkbox in the sidebar to save your progress.

Step 234. Hash Attacks: Length Extension and Collision Concepts — What Happens When You Use a Hash as a “Signature”