Zh3r0 CTF V2 - EAT SLEEP TRACE REPEAT

rev
$ ./chall  
enter password: zh3r0{xxxxxx...}  
search complete  
$ # :)

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:

from keystone import *
import ctypes

f = open('./trace.txt')
data = f.read().splitlines()
instr = {int(x.split(' : ')[0], 16):x.split(' : ')[1] for x in data}
instr_tup = [(x, instr[x]) for  x in instr.keys()]
instr_tup.sort(key = lambda x : x[0])
base = instr_tup[0][0]
print('base address: 0x%x' % base)

for i in range(len(instr_tup)):
    if '0x40' in instr_tup[i][1]:
        target = instr_tup[i][1].index('0x40')
        temp = instr_tup[i][1][target:target+8]
        val = int(temp, 16)
        instr_tup[i] = (instr_tup[i][0], instr_tup[i][1].replace(temp, hex(val-base)))
    instr_tup[i] = (instr_tup[i][0] - base, instr_tup[i][1])
for i in instr_tup:
    print(hex(i[0]) + ' ' +  i[1])

result = []
counter = 0
curr = 0

ks = Ks(KS_ARCH_X86, KS_MODE_64)
while counter < 0x200:
    if curr < len(instr_tup) and instr_tup[curr][0] == counter:
        instr = instr_tup[curr][1].replace('qword', '')
        if any(x in instr for x in ['jmp', 'jnz', 'jz']): # relative short jump
            dist = int(instr[(instr.index('0x')):], 16) - instr_tup[curr][0]
            if dist > 0x80:
                instr = instr[:instr.index('0x')] + hex(ctypes.c_byte(dist).value)
            else:
                instr = instr[:instr.index('0x')] + '+' + hex(dist)
        if 'call' in instr and 'syscall' not in instr: # relative call
            dist = int(instr[(instr.index('0x')):], 16) - instr_tup[curr][0]
            instr = instr[:instr.index('0x')] + hex(ctypes.c_int(dist).value)
        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
            offset = int(instr[instr.index('[')+1: instr.index(']')].split('0x')[1], 16)
            offset -= instr_tup[curr][0]
            instr = instr.replace(hex(offset + instr_tup[curr][0]), hex(offset))
        if not any(x in instr for x in ['qword', 'dword', 'word', 'byte']):
            instr = instr.replace('ptr', '')
        print(instr)
        code, count = ks.asm(instr)
        result.append((counter, bytes(bytearray(code)), instr_tup[curr][1]))
        counter += len(code)
        curr += 1
    else:
        result.append((counter, b'\x90', 'nop'))
        counter += 1

for i in result:
    print(hex(i[0]), i[1], i[2])

f = open('binary', 'wb')
for i in result:
    f.write(i[1])
f.write(b'\xf4')
f.write(b'\x00' * 0x2000)
f.close()

Re-disassembly

We then loaded the generated shellcode into Binary Ninja, and receive this decompilation:

00000000  int64_t _start()

00000000      sub_68()
00000000      return sub_5() __tailcall


00000005  int64_t sub_5()

00000022      return syscall(0, &data_1808, 0x64)


00000023  int64_t sub_23()

00000053      int64_t rax
00000053      int64_t rdx
00000053      rdx:rax = 0
00000056      data_1000 = 0
0000005e      return rax


0000005f  int64_t sub_5f(int64_t arg1)

0000005f      data_1000 = arg1


00000068  int64_t sub_68()

0000007d      syscall(1, &data_18d0, 0x10)
0000007f      sub_5()
00000089      sub_5f(0x41424344)
0000008e      int64_t rcx = 0x800
00000093      void* r15 = nullptr
00000099      for (; rcx != 0; rcx = rcx - 1)
000000a2          *(r15 + 0x1008) = sub_23()
000000a9          r15 = r15 + 1
000000b1      void* rsi = nullptr
000000b6      char rdi
000000b6      while (true)
000000b6          rdi = *(rsi + 0x1808)
000000bd          void* rax_2 = sub_106(rdi)
000000c6          if (rax_2 == -1)
000000c6              break
000000c8          *(rsi + 0x186c) = rax_2.b
000000ce          rsi = rsi + 1
000000ec          if (rsi.b == 0x64)
000000ec              syscall(1, &data_18e1, 0x10, rcx)
000000f8              rdi = syscall(0)
000000f8              break
00000105      return sub_106(rdi) __tailcall


00000106  void* sub_106(char arg1)

0000010d      void* rdx = nullptr
00000110      char rax
00000110      do
00000110          rax = *(rdx + 0x1008)
00000116          rdx = rdx + 1
00000200          if (rdx == 0x7ff)
00000200              trap(0xd)
00000200      while (rax != arg1)
00000130      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:

00000023  488b0ddd0f0000     mov     rcx, qword [rel data_1000]
0000002a  90                 nop     
0000002b  4889ca             mov     rdx, rcx
0000002e  48c1ea0c           shr     rdx, 0xc
00000032  4831d1             xor     rcx, rdx
00000035  4889ca             mov     rdx, rcx
00000038  48c1e219           shl     rdx, 0x19
0000003c  4831d1             xor     rcx, rdx
0000003f  4889ca             mov     rdx, rcx
00000042  48c1ea1b           shr     rdx, 0x1b
00000046  4831d1             xor     rcx, rdx
00000049  48b81ddd6c4f91f4…mov     rax, 0x2545f4914f6cdd1d
00000053  48f7e1             mul     rcx  {0x0}
00000056  48890da30f0000     mov     qword [rel data_1000], rcx  {0x0}
0000005d  90                 nop     
0000005e  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:

int i = 0;
int j = 0x800;
for (; j > 0; j--) {
    arr[i] = sub_23();
    i++;
}

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

# Lots of '& 0xffffffffffffffff' to simulate a 64 bit integer in Python
class State:
    def __init__(self, seed):
        self.state = seed & 0xffffffffffffffff
    def next(self):
        rcx = self.state
        rdx = rcx
        rdx = rdx >> 0xc
        rcx = rcx ^ rdx
        rdx = rcx
        rdx = rdx << 0x19
        rdx = rdx & 0xffffffffffffffff
        rcx = rcx ^ rdx
        rcx &= 0xffffffffffffffff
        rdx = rcx
        rdx = rdx >> 0x1b
        rcx = rcx ^ rdx
        rcx &= 0xffffffffffffffff
        rax = 0x2545f4914f6cdd1d
        result = rax* rcx
        rdx = result >> 64
        rax = result & 0xffffffffffffffff
        self.state = rcx
        return rax & 0xff

inp = [0 for _ in range(0x64)]
s = State(0x41424344)
# Seed our random number array
values = [s.next() for _ in range(0x800)]

with open('trace.txt', 'r') as f:
    lines = f.read().split('\n')

count = 0
for line in lines:
    addr, ins = line.split(' : ')
    addr = int(addr, 16)
    if addr == 0x401116:
        # Where the binary increments the loop counter
        count += 1
    if addr == 0x401126:
        # Where the function returns, i.e. the char has been found
        print(f"{chr(values[count-1])}", end='')
        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_?}