MDFlag

Platform: cryptohack | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-06-22 | Status: Solved Techniques: byte_by_byte_recovery, cyclic_key_wraparound, known_plaintext_oracle, md5_length_extension

Summary

Task: an oracle returns md5(data XOR cycle(FLAG)) for any attacker data >= len(FLAG); recover the 46-byte FLAG. Solution: exploit the public MD5 Merkle-Damgard padding plus the cyclic-key wrap-around (the flag's last byte '}' is immediately followed by its first 7 bytes 'crypto{'), giving 8 known plaintext bytes adjacent to a single unknown brute byte. Align the unknown byte at the end of a hashed block, read the oracle's digest as the MD5 internal state, then locally finish hashing (data || md5-pad) for each of the 256 guesses and match the oracle output. This recovers the cyclic key one byte at a time right-to-left; FLAG length is 46.

MDFlag — cryptohack (Hashes)

Description

"I think mdFLAG is better than HMAC."

The server (socket.cryptohack.org:13407) accepts hex data and replies with a hash:

 python read-only • copy allowed Copy
FLAG = b'crypto{??????????????????????????????????????}'   # 46 bytes

def challenge(self, msg):
    data = bytes.fromhex(msg["data"])
    if len(data) < len(FLAG):
        return {"error": "Bad input"}
    salted = bxor(data, cycle(FLAG))
    return {"hash": md5(salted).hexdigest()}

So the oracle returns md5(data XOR cycle(FLAG)) for any data whose length is at least len(FLAG)=46. The goal is to recover FLAG. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Analysis

This is a homemade keyed hash (mdFLAG) where the "key" is the flag, XORed cyclically into the data before a raw MD5. Two properties of MD5 break it:

1. MD5 is Merkle-Damgard with public padding. MD5 processes data in 64-byte blocks. After consuming n blocks the 128-bit chaining value is exactly the hex digest you would get if you stopped there. If you know the chaining state after some prefix, you can continue hashing more blocks yourself — this is the classic length-extension property. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

2. The key is cycle(FLAG), a fixed periodic stream of period 46. If we send data that is all zero bytes, the XOR mask at each position j is simply FLAG[j % 46]. Crucially the cyclic key wraps: position 45 is '}' (FLAG[-1]) and position 46 is 'c' (FLAG[0]). So the byte sequence }crypto{ appears as 8 consecutive known key bytes straddling the wrap boundary.

The attack recovers the cyclic key one byte at a time, right-to-left, by arranging exactly one unknown key byte at the last position of a complete block, with the 8 already-known bytes (}crypto{ initially) sitting just after it, and using length-extension to verify each of the 256 guesses against the oracle's digest. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Concretely: pad data so the unknown byte ends a block. Ask the oracle to hash data (this gives the MD5 internal state after that block). Then locally, for the candidate byte c, recompute the MD5 of data extended by the MD5 padding (get_pad_suffix) XORed against the known key bytes, seeded from the leaked state, and compare to a separately requested oracle digest that fixes the known suffix. The matching c reveals key_byte = known_pad_byte ^ c.

Solution

Key building blocks (full working solver solve_mdflag3.py, port 13407): ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

 python read-only • copy allowed Copy
import math, struct
constants   = [int(abs(math.sin(i+1))*4294967296)&0xFFFFFFFF for i in range(64)]
rotate_by   = [7,12,17,22]*4 + [5,9,14,20]*4 + [4,11,16,23]*4 + [6,10,15,21]*4
init_buffer = [0x67452301,0xefcdab89,0x98badcfe,0x10325476]

def lrot(x,a): x&=0xFFFFFFFF; return (x<<a|x>>(32-a))&0xFFFFFFFF

def get_pad_suffix(msg):
    """The MD5 padding bytes that would be appended to `msg` (its last <=64 bytes)."""
    msg=bytearray(msg); d=len(msg)%64; bits=(8*len(msg))&0xffffffffffffffff
    msg+=b"\x80"
    while len(msg)%64!=56: msg+=b"\x00"
    msg+=bits.to_bytes(8,"little")
    return bytes(msg[-64+d:])
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def proc(state, msg):                       # one or more 64-byte blocks from a given state
    it=list(state)
    for off in range(0,len(msg),64):
        A,B,C,D=it; blk=msg[off:off+64]
        for i in range(64):
            if   i<16: F=(B&C)|(~B&D); g=i
            elif i<32: F=(D&B)|(~D&C); g=(5*i+1)%16
            elif i<48: F=B^C^D;        g=(3*i+5)%16
            else:      F=C^(B|~D);     g=(7*i)%16
            tr=A+F+constants[i]+int.from_bytes(blk[4*g:4*g+4],"little")
            nb=(B+lrot(tr,rotate_by[i]))&0xFFFFFFFF
            A,B,C,D=D,nb,B,C
        for k,v in enumerate([A,B,C,D]): it[k]=(it[k]+v)&0xFFFFFFFF
    return sum(b<<(32*i) for i,b in enumerate(it))
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def md5_with_state(state_hex, msg, calculated_len):
    """Continue MD5 from a known internal `state_hex`, appending `msg` then MD-padding
    using the TRUE total length `calculated_len`."""
    msg=bytearray(msg); ml=calculated_len+len(msg)
    bits=(8*ml)&0xffffffffffffffff
    msg.append(0x80)
    while len(msg)%64!=56: msg.append(0)
    msg+=bits.to_bytes(8,"little")
    digest=proc(num_to_vec(hex_to_MD(state_hex)), msg)
    return MD_to_hex(digest)

def xor(a,b): return bytes(x^y for x,y in zip(a,b))

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Recovery loop — seed with the 8-byte wrap window }crypto{, then peel off one byte per round:

 python read-only • copy allowed Copy
FL = 46
block_number = 2

# First unknown byte: place it as the last byte before the }crypto{ wrap window.
data = b"\x00"*64*block_number + b"\x00"*(64-9)
known_suffix = get_pad_suffix(data)
state = oracle_hash(data)                         # MD5 internal state after these blocks
valid = md5_with_state(state, b"", (block_number+1)*64)
c = find_match(valid, prefix=data + xor(known_suffix[:8], b"}crypto{"), suffix=b"")
s = b"}crypto{" + bytes([known_suffix[8] ^ c])    # known cyclic-key window grows
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

for i in range(1, 38):                            # peel remaining bytes right-to-left
    data = b"\x00"*64*block_number + b"\x00"*(64-9-i)
    known_suffix = get_pad_suffix(data)
    state = oracle_hash(data)
    valid = md5_with_state(state, b"", (block_number+1)*64)
    c = find_match(valid, prefix=data, suffix=xor(known_suffix[1:], s))
    s = bytes([known_suffix[0] ^ c]) + s

idx = s.find(b"crypto{")
print("FLAG:", s[idx:idx+FL].decode())

find_match brute-forces the single unknown byte c in range(256), asking the oracle for md5(prefix || c || suffix XOR key) and returning the c whose digest equals the length-extension-predicted valid. Because the only unknown is one byte and everything else is either known plaintext or recoverable via length-extension, each round costs at most 256 queries. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Takeaways

Use this technique when:

• A "MAC" is built as md5(data XOR something_secret) or md5(secret || data) — raw MD5 (or any Merkle-Damgard hash) is never a safe MAC; it leaks its internal state as the digest, enabling length-extension. Use HMAC instead (hence the ironic flag).
• A keystream is periodic (cycle(FLAG)): the period creates a known wrap-around window (}crypto{ from the flag braces) that bootstraps byte-by-byte recovery.
• You can align a single unknown byte at a block boundary and verify guesses by re-deriving the digest locally from a leaked chaining value. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍