Tags: assembly binja reversing 

Rating: 5.0

# Eat Sleep Trace Repeat

```bash
$ ./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:
```asm
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:
```py
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:
```c
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:
```c
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:
```c
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
```py
# 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_?}`

Original writeup (https://cor.team/posts/Zh3r0%20CTF%20V2%20-%20EAT%20SLEEP%20TRACE%20REPEAT).