From Zero To X

zTrix's Blog

PHDays CTF IV Quals 2014 - Turututu Writeup

by Wenlei Zhu (zTrix@blue-lotus)

turututu is an ELF 64-bit executable, after some investigation, it’s easy to find out that the task.exe is a native binary generated using ocamlopt.

I know little about ocaml, so at first I searched a lot trying to get some bytecode or decompiler stuff, or some dedicated debugger for ocaml, but none of these tools could be found.

So it’s time to dive into assembly.

From the string constant Sorry, waybe next time...(typo here, LOL!) printed by task.exe, we xref to 0x402bf0, and at 0x402dda, it seems that some check function is called and then print Gratz! or Sorry, waybe next time...(LOL again!) according to its return value.

Deeper diving reaveals that the check function will invoke a list of functions to check the input value, and whenever something went wrong, the return value would be fail.

  • The first one is at 0x4024a0, which is a simple function who parse the arg to a ocaml list of chars.
  • The second one is at 0x402520, which is the check length function. From here we know the list size should be 16.
  • The third one is at 0x402790, ah, a magic string The sky above the port was the color of... can be seen here, it seems that some permutation operations are done here, and will always give positive return value, so just leave it here for later analysis.
  • The fourth one is at 0x402870, this is the real check, and will return false if the check fails.
  • And there are function 5, 6, 7, will check after function 4. Leave them for later analysis.

Ok now we know that we should run the program with a string as argument of 16 bytes, and if the string match something, the task.exe will print happy result. And it’s very likely that the input argument should be the flag.

There are a lot of ocaml library functions out there without any signature, making it very hard to read assembly. So I compiled a helloworld program using ocamlopt -g hw.ml, and by comparing the hex code, I can identify a lot of important ocaml functions like camlList__map, camlList_c_call, camlList__combine, caml_equal.

But it’s still very hard to figure out the actual behavior under the assembly code. Now it’s time for the peda weapon.

I wrote a small piece of code in peda to print ocaml list values

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def ocamlist(self, *arg):
    """
    dump ocaml list
    Usage:
        ocamlist register
        ocamlist address
    """
    (address,) = normalize_argv(arg, 1)
    if address is None:
        self._missing_argument()
    if str(address).startswith("r"):
        address = peda.getreg(arg[0])
    else:
        address = to_int(arg[0])
    result = []
    for i in range(100):
        result.append(peda.read_int(address, 8))
        address = peda.read_int(address+8, 8)
        if address < 0x1000:
            break
    msg('ocamllist: (%d) %s' % (len(result), repr(result)))
    return

Now fire! gdbinit here

file task.exe
b *0x402baa
r 1234567890ABCDEF

continue at gdb to skip the first function. Then ocamlist $rax

Breakpoint 1, 0x0000000000402baa in ?? ()
gdb-peda$ ocamlist $rax
ocamllist: (16) [99, 101, 103, 105, 107, 109, 111, 113, 115, 97, 131, 133, 135, 137, 139, 141]

Oops, why should ocaml put 2x+1 value in the list. Never mind.

continue two times to skip the length check. Then ocamlist $rax

Breakpoint 1, 0x0000000000402baa in ?? ()
gdb-peda$ ocamlist $rax
ocamllist: (16) [101, 135, 115, 111, 97, 141, 139, 99, 137, 133, 113, 103, 109, 107, 105, 131]

Now we have the permutation table. :)

ni into 0x402870, and ni to 0x402888, ocamlist $rax

gdb-peda$ ocamlist $rax
ocamllist: (8) [137, 133, 113, 103, 109, 107, 105, 131]

so 0x4025e0 cut the list from index 8, return the second part. ni to 0x40289d

0x000000000040289d in ?? ()
gdb-peda$ ocamlist $rax
ocamllist: (8) [101, 135, 115, 111, 97, 141, 139, 99]

we got the first half. Then at 0x4028a1, we can identify the function called to be camlList__combine by comparing hex code, we can also know the function camlList__map called at 0x4028b0, caml_equal loaded at 0x4028bf, and the constant list at 0x4028b5 is

gdb-peda$ ocamlist 0x621c20
ocamllist: (8) [591, 599, 687, 663, 475, 687, 687, 609]

So, the logic here become evident. if written in python, it should be sth like this

1
2
3
combined = zip(lst[:8], lst[8:])
maped = map(f, combined)
assert maped == [591, 599, 687, 663, 475, 687, 687, 609]

Now we need to know the function f, si into camlList__map and we can find out f at 0x402360

=> 0x402360:    sar    rbx,1
   0x402363:    lea    rax,[rax+rbx*4]
   0x402367:    ret

so the python code can be completed

1
2
3
combined = zip(lst[:8], lst[8:])
maped = map(lambda x: (x[1]>>1)*4+x[0], combined)
assert maped == [591, 599, 687, 663, 475, 687, 687, 609]

the next 3 check functions are at 0x4029e0, 0x402a80, 0x402b20, all of them looks like the function we just analysed. It’s obvious 0x402b20 is the simplest. Using the same technique stated above. We can find out this check is actually doing this:

1
assert lst[7:] == [145, 195, 233, 229, 221, 137, 243, 229, 233]

WTF? I just cannot believe this. Fine, we do not need to analyze other functions. Now we can get our most wanted flag

1
2
3
4
5
6
7
8
9
10
rev = [7, 0, 11, 14, 13, 12, 3, 10, 2, 4, 15, 9, 1, 8, 6, 5]

fun7 = [145, 195, 233, 229, 221, 137, 243, 229, 233]
fun4 = [591, 599, 687, 663, 475, 687, 687, 609]
p = []
for i in range(8):
    p.append(fun4[i] - (fun7[i+1]>>1)*4)
lst = p + fun7[1:]
lst = [(lst[rev[i]]-1)/2 for i in range(len(lst))]
print ''.join(map(chr, lst))

The flag is HenryDorsettCase

Comments