# hxp 36C3 CTF: md15
Full release of our research paper on executing a "preimage attack" on the MD5function.
The "paper" can be downloaded [here](https://hxp.io/assets/data/posts/70-md15/md15_full.pdf).
##### tl;dr
Apparently our joke on a feasible preimage attack on MD5 seemed to legit,because we saw _a lot_ of people actually reading crypto papers about MD5 at36C3.
The short answer is that we---like everybody else on this planet---also have nofeasible attack on MD5. Instead, we shamelessly backdoored the binary.The backdoor consists of two main components:
1. The `__libc_csu_init` function usually contains a nop that we replaced by an   instruction that would shift the pointers (of non-RELRO ELF binaries)   contained in the `init_array` by 8 bytes. This way, we could hide a jump   instruction in the code directly after the default constructor   (`frame_dummy`).2. The jump instruction targets code beyond the end of the segment limit. This   code is not displayed by any disassembler (try `objdump -D`) we are currently   aware of. Nevertheless, the GNU loader works at a page granularity when   loading segments and therefore code beyond the end of the segment limit ends   up in memory, perfectly executable. (Note that not all loaders offer this   (un-)feature; the ELF loader implemented in Microsoft's WSL honors segment   boundaries causing `md15` to crash immediately on program startup. We took   this risk, and according to [the internet](https://github.com/oranav/ctf-writeups/tree/master/36c3/md15)   it went unnoticed for a pretty long time.
The hidden code implemented a simple check on the input such that it would notreveal the backdoor functionality when sampling the MD5 implementation in thebinary using GDB. Only if the check passed (and if the environment looked sane),the backdoor code would patch the MD5 implementation in such a way that md5implementation was reduced to a 12 rounds. MD5 with 12 (instead of 64) roundscan be trivially inverted using a SMT solver. Our test solve script used z3 tocalculate the flag:
```pythonimport struct, z3
h = bytes.fromhex('3ed50eac373185348499454857b06fd3') # md5(flag ^ 'h')x = bytes.fromhex('448582faa78b404a898d0532542d327b') # md5(flag ^ 'x')p = bytes.fromhex('9973f05fde3fe6320be04a918c5b50ab') # md5(flag ^ 'p')
a0, b0, c0, d0 = 0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476ah, bh, ch, dh = struct.unpack('IIII', h)ax, bx, cx, dx = struct.unpack('IIII', x)ap, bp, cp, dp = struct.unpack('IIII', p)
unknown_words = z3.BitVecs('f0 f1 f2 f3', 32)remaining_words = struct.unpack('I' * 12, b'\x80' + b'\x00' * 39 + struct.pack('Q', 128))
h_flag = [w ^ 0x68686868 for w in unknown_words] + list(remaining_words)x_flag = [w ^ 0x78787878 for w in unknown_words] + list(remaining_words)p_flag = [w ^ 0x70707070 for w in unknown_words] + list(remaining_words)
K = [0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee,     0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501,     0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be]S = [7, 12, 17, 22] * 3def FF(b, c, d):    return (b & c) | ((~b) & d)def u32(value):    return (value + (1 << 32)) % (1 << 32) if isinstance(value, int) else valuedef ror(value, shift):    if isinstance(value, int):        shift %= 32        shifted = u32(value) >> shift        excess = value & ((1 << shift) - 1)        return shifted | (excess << (32 - shift))    return z3.RotateRight(value, shift)def invert_md5(a, b, c, d, values):    a -= a0    b -= b0    c -= c0    d -= d0    for r in range(11, -1, -1):        B, C, D = c, d, a        a_t1 = u32(ror(b - c, S[r]) - K[r])        a_t2 = u32(a_t1 - values[r])        A = u32(a_t2 - FF(B, C, D))        a, b, c, d = A, B, C, D    print(a, b, c, d)    return z3.And(a == a0, b == b0, c == c0, d == d0)
ss = z3.Solver()print('Adding H flag')ss.add(invert_md5(ah, bh, ch, dh, h_flag))print('Adding X flag')ss.add(invert_md5(ax, bx, cx, dx, x_flag))print('Adding P flag')ss.add(invert_md5(ap, bp, cp, dp, p_flag))print('Solving')print(ss.check())
m = ss.model()result = struct.pack('IIII', *[int(str(m.evaluate(w))) for w in unknown_words])print('hxp{' + result.decode() + '}')```