Zh3r0 CTF V2 - EAT SLEEP TRACE REPEAT
- Author: clubby789
- Date:
1$ ./chall
2enter password: zh3r0{xxxxxx...}
3search complete
4$ # :)
Disassembly
We receive a trace of the execution of an executable. From the description, we can assume this is the chall binary that was executed, and the flag entered. It begins like this:
0x401000 : call 0x401068
0x401068 : mov eax, 0x1
0x40106d : mov rdi, rax
0x401070 : lea rsi, ptr [0x4028d0]
0x401078 : mov edx, 0x10
0x40107d : syscall
0x40107f : call 0x401005
0x401005 : push rbp
0x401006 : mov rbp, rsp
0x401009 : xor rax, rax
0x40100c : xor rdi, rdi
0x40100f : lea rsi, ptr [0x402808]
...
The file is 181888 lines long, so we’re not going to be able to manually read through. To aid our understanding of the binary, we first began by painstakingly modifying the assembly in order to re-assemble the program into shellcode. This would allow us to view cross references and understand the flow.
Reassembly
After a lot of trial-and-error, we settled on this script:
1from keystone import *
2import ctypes
3
4f = open('./trace.txt')
5data = f.read().splitlines()
6instr = {int(x.split(' : ')[0], 16):x.split(' : ')[1] for x in data}
7instr_tup = [(x, instr[x]) for x in instr.keys()]
8instr_tup.sort(key = lambda x : x[0])
9base = instr_tup[0][0]
10print('base address: 0x%x' % base)
11
12for i in range(len(instr_tup)):
13 if '0x40' in instr_tup[i][1]:
14 target = instr_tup[i][1].index('0x40')
15 temp = instr_tup[i][1][target:target+8]
16 val = int(temp, 16)
17 instr_tup[i] = (instr_tup[i][0], instr_tup[i][1].replace(temp, hex(val-base)))
18 instr_tup[i] = (instr_tup[i][0] - base, instr_tup[i][1])
19for i in instr_tup:
20 print(hex(i[0]) + ' ' + i[1])
21
22result = []
23counter = 0
24curr = 0
25
26ks = Ks(KS_ARCH_X86, KS_MODE_64)
27while counter < 0x200:
28 if curr < len(instr_tup) and instr_tup[curr][0] == counter:
29 instr = instr_tup[curr][1].replace('qword', '')
30 if any(x in instr for x in ['jmp', 'jnz', 'jz']): # relative short jump
31 dist = int(instr[(instr.index('0x')):], 16) - instr_tup[curr][0]
32 if dist > 0x80:
33 instr = instr[:instr.index('0x')] + hex(ctypes.c_byte(dist).value)
34 else:
35 instr = instr[:instr.index('0x')] + '+' + hex(dist)
36 if 'call' in instr and 'syscall' not in instr: # relative call
37 dist = int(instr[(instr.index('0x')):], 16) - instr_tup[curr][0]
38 instr = instr[:instr.index('0x')] + hex(ctypes.c_int(dist).value)
39 if ('mov' in instr or 'lea' in instr) and ('[' in instr and ']' in instr) and not ('+' in instr or '-' in instr): # relative data loads, gdb displays as absolute
40 offset = int(instr[instr.index('[')+1: instr.index(']')].split('0x')[1], 16)
41 offset -= instr_tup[curr][0]
42 instr = instr.replace(hex(offset + instr_tup[curr][0]), hex(offset))
43 if not any(x in instr for x in ['qword', 'dword', 'word', 'byte']):
44 instr = instr.replace('ptr', '')
45 print(instr)
46 code, count = ks.asm(instr)
47 result.append((counter, bytes(bytearray(code)), instr_tup[curr][1]))
48 counter += len(code)
49 curr += 1
50 else:
51 result.append((counter, b'\x90', 'nop'))
52 counter += 1
53
54for i in result:
55 print(hex(i[0]), i[1], i[2])
56
57f = open('binary', 'wb')
58for i in result:
59 f.write(i[1])
60f.write(b'\xf4')
61f.write(b'\x00' * 0x2000)
62f.close()
Re-disassembly
We then loaded the generated shellcode into Binary Ninja, and receive this decompilation:
100000000 int64_t _start()
2
300000000 sub_68()
400000000 return sub_5() __tailcall
5
6
700000005 int64_t sub_5()
8
900000022 return syscall(0, &data_1808, 0x64)
10
11
1200000023 int64_t sub_23()
13
1400000053 int64_t rax
1500000053 int64_t rdx
1600000053 rdx:rax = 0
1700000056 data_1000 = 0
180000005e return rax
19
20
210000005f int64_t sub_5f(int64_t arg1)
22
230000005f data_1000 = arg1
24
25
2600000068 int64_t sub_68()
27
280000007d syscall(1, &data_18d0, 0x10)
290000007f sub_5()
3000000089 sub_5f(0x41424344)
310000008e int64_t rcx = 0x800
3200000093 void* r15 = nullptr
3300000099 for (; rcx != 0; rcx = rcx - 1)
34000000a2 *(r15 + 0x1008) = sub_23()
35000000a9 r15 = r15 + 1
36000000b1 void* rsi = nullptr
37000000b6 char rdi
38000000b6 while (true)
39000000b6 rdi = *(rsi + 0x1808)
40000000bd void* rax_2 = sub_106(rdi)
41000000c6 if (rax_2 == -1)
42000000c6 break
43000000c8 *(rsi + 0x186c) = rax_2.b
44000000ce rsi = rsi + 1
45000000ec if (rsi.b == 0x64)
46000000ec syscall(1, &data_18e1, 0x10, rcx)
47000000f8 rdi = syscall(0)
48000000f8 break
4900000105 return sub_106(rdi) __tailcall
50
51
5200000106 void* sub_106(char arg1)
53
540000010d void* rdx = nullptr
5500000110 char rax
5600000110 do
5700000110 rax = *(rdx + 0x1008)
5800000116 rdx = rdx + 1
5900000200 if (rdx == 0x7ff)
6000000200 trap(0xd)
6100000200 while (rax != arg1)
6200000130 return rdx - 1
_start() - calls the entrypoint
sub_5() - Reads 0x64 bytes into 0x1808 - this is the flag
sub_23- Due to typing errors, the decompiler has eliminated most of the code here. The disassembly:
100000023 488b0ddd0f0000 mov rcx, qword [rel data_1000]
20000002a 90 nop
30000002b 4889ca mov rdx, rcx
40000002e 48c1ea0c shr rdx, 0xc
500000032 4831d1 xor rcx, rdx
600000035 4889ca mov rdx, rcx
700000038 48c1e219 shl rdx, 0x19
80000003c 4831d1 xor rcx, rdx
90000003f 4889ca mov rdx, rcx
1000000042 48c1ea1b shr rdx, 0x1b
1100000046 4831d1 xor rcx, rdx
1200000049 48b81ddd6c4f91f4…mov rax, 0x2545f4914f6cdd1d
1300000053 48f7e1 mul rcx {0x0}
1400000056 48890da30f0000 mov qword [rel data_1000], rcx {0x0}
150000005d 90 nop
160000005e c3 retn {__return_addr}
The nature of this function suggested a PRNG function to me. The value at 0x1000 is loaded, then passed through a series of shifts and XORs, before it is saved back to 0x1000, then multiplied by a large constant and returned.
sub5f(arg) - Sets the value at 0x1000 to arg
sub_68() - The main body, begins by writing out 0x10 bytes (likely the enter password: message seen in the description).
The PRNG is then seeded with 0x41424344, and a loop is iterated over 0x800 times:
1int i = 0;
2int j = 0x800;
3for (; j > 0; j--) {
4 arr[i] = sub_23();
5 i++;
6}
The array at 0x1008 is filled with a series of predictable random numbers. Finally, we iterate over each character of the flag, and call sub_106() on it. After 0x64 characters, the final message is printed. So, what is sub_106()? It essentially finds a byte in an array - in this case, it finds each char of the flag within the array of random bytes. As this iterates over each position of the array, we are able to trace the number of array iterations, which will allow us to find the position of each flag character in the random byte array. We’re ready to implement a solver.
Solving
1# Lots of '& 0xffffffffffffffff' to simulate a 64 bit integer in Python
2class State:
3 def __init__(self, seed):
4 self.state = seed & 0xffffffffffffffff
5 def next(self):
6 rcx = self.state
7 rdx = rcx
8 rdx = rdx >> 0xc
9 rcx = rcx ^ rdx
10 rdx = rcx
11 rdx = rdx << 0x19
12 rdx = rdx & 0xffffffffffffffff
13 rcx = rcx ^ rdx
14 rcx &= 0xffffffffffffffff
15 rdx = rcx
16 rdx = rdx >> 0x1b
17 rcx = rcx ^ rdx
18 rcx &= 0xffffffffffffffff
19 rax = 0x2545f4914f6cdd1d
20 result = rax* rcx
21 rdx = result >> 64
22 rax = result & 0xffffffffffffffff
23 self.state = rcx
24 return rax & 0xff
25
26inp = [0 for _ in range(0x64)]
27s = State(0x41424344)
28# Seed our random number array
29values = [s.next() for _ in range(0x800)]
30
31with open('trace.txt', 'r') as f:
32 lines = f.read().split('\n')
33
34count = 0
35for line in lines:
36 addr, ins = line.split(' : ')
37 addr = int(addr, 16)
38 if addr == 0x401116:
39 # Where the binary increments the loop counter
40 count += 1
41 if addr == 0x401126:
42 # Where the function returns, i.e. the char has been found
43 print(f"{chr(values[count-1])}", end='')
44 count = 0
We simply count the number of iterations from entering the function to leaving it, and print that char within the random byte array - this gives us the flag:
zh3r0{d1d_y0u_enjoyed_r3v3rs1ng_w1th0ut_b1n4ry_?}