r2con-ctf writeup: Madagascar

// under write-up ctf radare2 angr
// Mon 10 September 2018

This is a write-up for the Madagascar challenge of r2con 2018 CTF.

Are you sure what you see?

binary: scrabble_ad92a0e308d220dc89c4bc133e0ce64c

The string "Wk2p2pm3wg7eo7d" is quickly found using strings and naively inserted as a valid flag, obviously without success ;-)

Open the binary with radare2 and explore the functions and the main:

$ radare2 scrabble_ad92a0e308d220dc89c4bc133e0ce64c
[0x004004c0]> aaa
[0x004004c0]> e asm.pseudo = 1
[0x004004c0]> e asm.bytes = 0
[0x004004c0]> afl
0x00400460    3 26           sym._init
0x00400490    1 6            sym.imp.puts
0x004004a0    1 6            sym.imp.__stack_chk_fail
0x004004b0    1 6            sym.imp.printf
0x004004c0    1 6            sym.imp.__libc_start_main
0x004004d0    1 6            sub.__gmon_start_4d0
0x004004e0    1 41           entry0
0x00400510    4 50   -> 41   sym.deregister_tm_clones
0x00400550    4 58   -> 55   sym.register_tm_clones
0x00400590    3 28           sym.__do_global_dtors_aux
0x004005b0    4 38   -> 35   entry1.init
0x004005d6   11 234          main
0x004006c0    4 101          sym.__libc_csu_init
0x00400730    1 2            sym.__libc_csu_fini
0x00400734    1 9            sym._fini
[0x004004c0]> s main
[0x004005d6]> pdf

Looking at the main function shows interesting information.

First local_10h is initialized with a pointer to the string "Wk2p2pm3wg7eo7d",

0x0040060e      qword [local_10h] = str.Wk2p2pm3wg7eo7d

and below block loops through all chars until \0 is hit.

0x00400666      rax = qword [local_10h]
0x0040066a      eax = byte [rax]
0x0040066d      var = al & al
0x0040066f      if (var) goto 0x400626

The block at address 0x00400626 called for each valid char in the string is decomposed below.

Note that:

local_10h is a pointer to the string ("Wk2p2pm3wg7eo7d")
local_30h is a pointer to argv
local_18h is an int initialized to 0

0x00400626      rax = qword [local_10h]
0x0040062a      eax = byte [rax]
Load char pointed by local_10h

0x0040062d      eax ^= 3
0x00400630      byte [local_19h] = al
0x00400633      rax = [local_19h]
0x00400637      eax = byte [rax]
0x0040063a      edx = al
do some operations and store in edx:
rdx = ((*local_10h) ^ 3) & 0xf

0x0040063d      rax = qword [local_30h]
0x00400641      rax += 8
rax points now to the input string

0x00400645      rcx = qword [rax]
0x00400648      eax = dword [local_18h]
0x0040064b      cdqe
0x0040064d      rax += rcx
0x00400650      eax = byte [rax]
0x00400653      eax = al
rax points now to one char in our input
rax = input[local_18h] & 0xf

0x00400656      edx -= eax
0x00400658      eax = edx
rax gets the value of rdx - rax

0x0040065a      dword [local_14h] += eax
add rax to local_14h

0x0040065d      qword [local_10h] += 1
0x00400662      dword [local_18h] += 1
increment the pointer/counter

In other words:

input = "AAAAA"
string = "Wk2p2pm3wg7eo7d"
index = 0

for s in string:
  s = (s ^ 0x3) & 0xf
  i = input[index] & 0xf
  res += (s-i)
  index += 1

Finally the test that defines if we found the correct flag is done in block at 0x00400671

0x00400671      var = dword [local_14h] - 0
0x00400675      if (!var) goto 0x400688

where local_14h should be 0 in order to win.

That means that each input char must be equal to each respective char of the internal string xored with 0x03.

Here's a small python one-liner to find the flag:

$ python
>>> ''.join([chr(ord(x)^0x3) for x in "Wk2p2pm3wg7eo7d"])
'Th1s1sn0td4fl4g'

Enter the flag and win!

I then tried to solve this with angr as an exercise. It didn't work not because angr wasn't able to find a solution but because it was finding too many solutions.

The reason is that local_14 needs to be 0 for the flag to be valid (as shown above) however it doesn't say that some characters comparisons cannot be different to zero as long as those are being compensented and that the final value of local_14 is 0. What means that there isn't a single solution to it but multiple. Still only one flag was valid for scoring that challenge. If that was purposely used to avoid the use of angr, it worked ;-)

Below my angr script as a reference

#!/usr/bin/env python2

import angr
import claripy

path = './scrabble_ad92a0e308d220dc89c4bc133e0ce64c'
p = angr.Project(path, load_options={'auto_load_libs':False})
state = p.factory.entry_state()

# construct the argument
argv = [p.filename]
size = 16 # password size
pwd = claripy.BVS('sym_arg', 8*size)
argv.append(pwd)

state = p.factory.entry_state(args=argv)
for i in xrange(size):
    current_byte = pwd.get_byte(i)
    state.add_constraints(
        claripy.Or(
            claripy.And(current_byte >= 'a', current_byte <= 'z'),
            claripy.And(current_byte >= 'A', current_byte <= 'Z'),
            claripy.And(current_byte >= '0', current_byte <= '9')
        )
      )

sm = p.factory.simulation_manager(state)
sm.explore(find = 0x400688, avoid = (0x00400677, 0x4005fa))
if len(sm.found) > 0:
    # we have a valid path to success
    found = sm.found[0]
    result = found.solver.eval_upto(argv[1], 10, cast_to=str)
    print '\n'.join(result)