MD0

Platform: CUSTOM | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: N/A | **Author: XESXOR Techniques: davies_meyer_state_continuation, glue_padding_computation, length_extension_forgery

Summary

Walkthrough of the CUSTOM Crypto MD0. Task: forge a valid MAC sig=hash(key||data) containing admin=True without knowing the 16-byte key, where hash is a Davies-Meyer Merkle-Damgard construction (out=0; per 16-byte block out = AES_ECB(bloc

Description

"You'll never forge my signatures!"

Server socket.cryptohack.org:13388 signs hash(key + data) (key is a secret 16 random bytes) and grants the flag if you submit a message containing admin=True together with a matching signature. The compression is Davies-Meyer with AES as the block cipher:

 python read-only • copy allowed Copy
def hash(data):
    data = pad(data, 16)                       # PKCS#7, always adds 1..16 bytes
    out = b"\x00"*16
    for i in range(0, len(data), 16):
        blk = data[i:i+16]
        out = bxor(AES.new(blk, AES.MODE_ECB).encrypt(out), out)   # DM: E_blk(out) ^ out
    return out
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# sign:     refuses if b"admin=True" in data, else returns hash(key + data)
# get_flag: returns FLAG if hash(key + data) == sent_sig AND b"admin=True" in data

Note blk (the 16-byte message chunk) is used as the AES key, and out is the plaintext — that is the Davies-Meyer single-block compression f(out, blk) = E_blk(out) XOR out.

Analysis

This is a textbook Merkle-Damgard length-extension forgery. The returned signature sig = hash(key + data) is exactly the chaining value out after consuming all padded blocks of key + data. Because Davies-Meyer keeps no separate finalization, sig IS the internal state — we can keep iterating the compression over additional blocks ourselves, without knowing the key, as long as we account for the padding that the server already inserted. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

The catch versus textbook length-extension: this hash uses PKCS#7 padding (pad(data,16)), which always appends 1..16 bytes (a full extra block when already aligned), and it pads again at the very end. So we must:

1. Pick a benign data (no admin=True), get sig = hash(key + data).
2. The server hashed pad(key + data) = key + data + glue, where glue is the PKCS#7 padding for the length len(key)+len(data). The state after that is sig.
3. Choose our extension ext containing b"admin=True".
4. The forged message we send is data' = data + glue + ext. When the server hashes key + data', it appends a final PKCS#7 pad for the new total length.
5. So the forged signature continues Davies-Meyer from sig over the blocks ext + final_pad. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

The only assumption is len(key) == 16 (stated in the source: os.urandom(16)), which makes glue computable.

Solution

Glue + final-pad computation and DM continuation (full solver solve_md0.py):

 python read-only • copy allowed Copy
from Crypto.Cipher import AES
def bxor(a,b): return bytes(x^y for x,y in zip(a,b))

def dm_from(state, blocks):                 # continue Davies-Meyer from a known state
    out = state
    for i in range(0, len(blocks), 16):
        blk = blocks[i:i+16]
        out = bxor(AES.new(blk, AES.MODE_ECB).encrypt(out), out)
    return out
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

KEYLEN = 16
data   = b"hello"                           # benign, no admin=True

# glue = PKCS#7 pad that the server already applied to (key + data)
m_len  = KEYLEN + len(data)                 # 21
padlen = (-m_len) % 16 or 16                # PKCS#7 adds a full block if aligned
glue   = bytes([padlen]*padlen)

ext    = b"admin=True------"                # 16 bytes, contains admin=True

# final PKCS#7 pad for the NEW total length key + data + glue + ext
new_len      = KEYLEN + len(data) + len(glue) + len(ext)
final_padlen = (-new_len) % 16 or 16
final_pad    = bytes([final_padlen]*final_padlen)
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

forged_data = data + glue + ext             # what we SEND (server prepends key)
def forge(sig):                             # continue from leaked state over ext + final_pad
    return dm_from(sig, ext + final_pad)

# --- interaction ---
sig  = bytes.fromhex(call({"option":"sign","message":data.hex()})["signature"])
fsig = forge(sig)
call({"option":"get_flag","message":forged_data.hex(),"signature":fsig.hex()})   # -> flag

The server computes hash(key + forged_data) = hash(key + data + glue + ext) whose padded block stream is exactly [key+data blocks][glue][ext][final_pad], and its chaining value equals our forge(sig) — so the forged signature verifies and admin=True is present. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Takeaways

Use this technique when:

• A MAC is hash(secret || message) with a Merkle-Damgard / Davies-Meyer hash whose final output equals its internal chaining state — always vulnerable to length-extension; use HMAC instead.
• You can recover/guess the secret length (here fixed at 16) to compute the glue padding the server inserted between key||data and your extension.
• The hash uses PKCS#7 (not the usual MD bit-padding): remember it appends 1..16 bytes and a full block when already aligned — compute both the glue pad and the final pad with (-len) % 16 or 16. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Key Takeaways / Lessons

• Mastering davies_meyer_state_continuation, glue_padding_computation, length_extension_forgery was key to this challenge.
• Always check for common misconfigurations and verify assumptions.

---

Crafted by XESXOR Research • 2026-06-22 • CUSTOM • MD0 • Difficulty: Medium