Tags: rev 

Rating: 5.0

# hxp 36C3 CTF: md15

Full release of our research paper on executing a "preimage attack" on the MD5
function.

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 at
36C3.

The short answer is that we---like everybody else on this planet---also have no
feasible 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 not
reveal the backdoor functionality when sampling the MD5 implementation in the
binary 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 md5
implementation was reduced to a 12 rounds. MD5 with 12 (instead of 64) rounds
can be trivially inverted using a SMT solver. Our test solve script used z3 to
calculate the flag:

```python
import 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, 0x10325476
ah, 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] * 3
def FF(b, c, d):
return (b & c) | ((~b) & d)
def u32(value):
return (value + (1 << 32)) % (1 << 32) if isinstance(value, int) else value
def 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() + '}')
```