CSCG 2023 - Traps

Last modification on


A flag checker. Cheap entertainment.

Challenge Files


We are provided with a single binary, a flag-checker called traps. The objective is to understand how flags are checked for validity, and generate a single input (the real flag) that satisfies all conditions.


We begin reverse-engineering and immediately notice that the program uses ptrace to prevent other processes from debugging it. Additionally, the first function called in main (fcn.004025b0) seems like it doesn't do anything but compute a value without using the result, and outputting "NO :(" before exiting. Not very reversing friendly.

On closer inspection, however, we can decipher what is happening and that the actual input validation is implemented elsewhere.

The function fcn.004025b0 is called in main with the process pid as its argument:

0x00401581      e80a1f0300     call fcn.__getpid
0x00401586      4863d8         movsxd rbx, eax
0x00401589      89df           mov edi, ebx
0x0040158b      e820100000     call fcn.004025b0
0x00401590      e8ab120300     call fcn.fork

Inside fcn.004025b0 we find that a child process is forked, which begins ptracing the parent and modifies its registers.

0x004025c2      char input[0x40]
0x004025c2      if (__fork() != 0)
0x00402681          wait(nullptr)
0x004026ac          puts("Welcome to your average flag cheā€¦")
0x004026c0          _IO_fgets(&input, 0x40, stdout)
0x004026c8          no_and_exit(&input)
0x004026c8          noreturn
0x004025db      if (ptrace(PTRACE_ATTACH, arg1, nullptr, nullptr) s>= 0)
0x004025ed          int32_t var_fc
0x004025ed          int32_t rax_2 = waitpid(arg1, &var_fc, 0x40000000)
0x004025f2          int16_t rdx_1 = var_fc.w
0x00402611          if (rax_2 s< 0 || (rax_2 s>= 0 && (rdx_1.b & 0x7f) + 1 s> 1) || (rax_2 s>= 0 && (rdx_1.b & 0x7f) + 1 s<= 1 && (rdx_1.b & 0x7f) == 0))
0x004026d0              exit(status: zx.d(rdx_1:1.b))
0x004026d0              noreturn
0x00402611          if (rax_2 s>= 0 && (rdx_1.b & 0x7f) + 1 s<= 1 && (rdx_1.b & 0x7f) != 0 && ptrace(PTRACE_GETREGS, arg1, nullptr, &input) s>= 0)
0x0040263d              input[0].q = 0
0x00402653              if (ptrace(PTRACE_SETREGS, arg1, nullptr, &input) s>= 0 && ptrace(PTRACE_DETACH, arg1, nullptr, nullptr) s>= 0)
0x0040266e                  exit_2(0)
0x0040266e                  noreturn
0x0040269b      exit(status: 0xffffffff)
0x0040269b      noreturn

It reads the register contents into the same memory region occupied by the user input in the child process (causing the input[0] lifting artifact), and sets the first quad-word member inside the register struct to 0. This corresponds to the register r15 of the parent process. After this, the child detaches and exits.

Subsequently, the parent who was waiting at 0x00402681 is awoken by the child exit. Here, the lifter hides the control flow allowing this function to return normally, since the branch comparing r15 after wait seems like it should only ever resolve one way.

0x00402681      e8da000300     call fcn.wait
0x00402686      4c89f8         mov rax, r15
0x00402689      4885c0         test rax, rax
0x0040268c      7512           jne 0x4026a0
0x0040268e      4881c4f80000.  add rsp, 0xf8
0x00402695      5b             pop rbx
0x00402696      5d             pop rbp
0x00402697      c3             ret

This means that during normal execution, the calculations and greeter prints in fcn.004025b0 aren't even called!

Considering the rest of the main function, we find more ptrace shenanigans.

0x0040158b      bait(sx.d(__getpid()))
0x00401590      pid_t child = __fork()
0x00401597      int64_t ret
0x00401597      if (child == 0)
0x004015a3          ret = ptrace(PTRACE_TRACEME, 0, nullptr, nullptr)
0x004015ab          if (ret s>= 0)
0x004015b6              raise(0x13)
0x004015c0              child = child_run()
0x004015ab      if ((child == 0 && ret s>= 0) || child != 0)
0x004015d6          int32_t child_status
0x004015d6          int32_t* child_status_1 = &child_status
0x004015db          int32_t ret_1 = waitpid(child, &child_status, 0x40000000)
0x004015e0          int16_t child_rc = child_status.w
0x004015e6          if (ret_1 s< 0)
0x004017de              exit_label8:
0x004017de              exit(status: zx.d(child_rc:1.b))
0x004017de              noreturn
0x004015f6          if ((child_rc.b & 0x7f) + 1 s> 1)
0x004015f6              goto exit_label8
0x004015ff          if ((child_rc.b & 0x7f) == 0)
0x004015ff              goto exit_label8
0x0040161d          if (ptrace(PTRACE_SETOPTIONS, child, nullptr, 0x100000) s>= 0 && ptrace(PTRACE_CONT, child, nullptr, 0x12) s>= 0)
0x00401648              uint8_t func_len = 0x7f
0x0040164f              uint8_t* len = &chunk_lens
0x00401656              uint64_t* key = &chunk_keys
0x0040165d              int64_t pos = 0
0x0040167c              int32_t ret_2
0x0040167c              while (true)
0x0040167c                  ret_2 = waitpid(child, child_status_1, 0x40000000)
0x00401681                  child_rc = child_status.w
0x00401687                  if (ret_2 s< 0)
0x00401687                      break
0x00401697                  if ((child_rc.b & 0x7f) + 1 s> 1)
0x00401697                      break
0x004016a0                  if ((child_rc.b & 0x7f) == 0)
0x004016a0                      break
0x004016c1                  uint64_t regs[0x1d]
0x004016c1                  if (ptrace(PTRACE_GETREGS, child, nullptr, &regs) s< 0)
0x004016c1                      break
0x004016c7                  uint64_t func_len_1 = zx.q(func_len)
0x004016ea                  void* r12_2 = regs[0x10]
0x004016f2                  regs[0xd].o = func_len_1.q | *key << 0x40
0x00401702                  if (ptrace(PTRACE_SETREGS, child, nullptr, &regs) s< 0)
0x00401702                      break
0x00401715                  void* rbx_1 = r12_2 + 0x86
0x0040171d                  uint8_t rax_17 = func_len u>> 3
0x00401720                  int64_t i = 0
0x0040172e                  if (rax_17 != 0)
0x0040175a                      int64_t rax_19
0x0040175a                      do
0x00401741                          rax_19 = ptrace(PTRACE_POKETEXT, child, rbx_1, *(&chunk_codes + pos + (i << 3)))
0x00401749                          if (rax_19 s< 0)
0x00401749                              break
0x0040174f                          i = i + 1
0x00401753                          rbx_1 = rbx_1 + 8
0x00401753                      while (i != zx.q(rax_17))
0x00401749                      if (rax_19 s< 0)
0x00401763                          break
0x00401763                  pos = pos + func_len_1
0x0040177d                  if (ptrace(PTRACE_CONT, child, nullptr, 0x12) s< 0)
0x0040177d                      break
0x0040177f                  func_len = *len
0x00401783                  key = &key[1]
0x00401789                  len = &len[1]
0x0040178f                  if (func_len == 0)
0x004017a1                      int32_t ret_3 = waitpid(child, child_status_1, 0x40000000)
0x004017a6                      child_rc = child_status.w
0x004017bd                      if (ret_3 s>= 0 && (child_rc.b & 0x7f) + 1 s<= 1 && (child_rc.b & 0x7f) != 0)
0x004017d2                          return 0
0x004017aa                      break
0x00401687              if (ret_2 s< 0)
0x004017d6                  goto exit_label8
0x004017d6      exit(status: 0xffffffff)
0x004017d6      noreturn

First, another child is spawned that enables ptracing of its process through PTRACE_TRACEME and waits for a tracer to attach through raise(SIGSTOP).

The parent waits for the child to stop, then makes a PTRACE_SETOPTIONS request with PTRACE_O_EXITKILL to ensure that the child is killed if the parent exits, and resumes child execution through PTRACE_CONT. The parent then enters a loop in which values are read from an array in memory, and used to modify the rdi register, as well as the program memory at rip+0x86 in the child process. The child is awoken in each iteration through PTRACE_CONT, presumably to execute the new instructions copied into its memory.

Let's see what child_run does:

0x0040251b      void* rax = mmap(nullptr, 0x1000, 7, 0x22, 0, 0)
0x00402524      if (rax == -1)
0x0040252b          exit(status: 0xffffffff)
0x0040252b          noreturn
0x00402537      int64_t rdx = 0
0x0040254b      do
0x0040253d          *(rax + rdx) = *(rdx + 0x40246f)
0x00402540          rdx = rdx + 1
0x00402540      while (rdx != 0x87)
0x0040254d      jump(rax)

And at 0x0040246f..

0x0040246f      breakpoint
0x00402476      int64_t i = 0x100
0x00402484      uint8_t buf[0x101]
0x00402484      do
0x00402480          buf[i] = i.b
0x00402484          i = i - 1
0x00402484      while (i != 0)
0x00402489      int64_t i_2 = (i + 1) << 8
0x0040248d      uint8_t val = 0
0x004024bb      int64_t _i_2
0x004024bb      do
0x00402497          val = val + buf[i_2]
0x00402499          _i_2 = i_2
0x0040249c          i_2.b = i_2.b & 7
0x0040249f          i_2.b = i_2.b << 3
0x004024a8          val = val + (key u>> i_2.b).b
0x004024aa          int64_t __i_2 = _i_2
0x004024ad          _i_2.b = buf[__i_2]
0x004024b2          uint8_t tmp = buf[1 + val]
0x004024b2          buf[1 + val] = _i_2.b
0x004024b2          _i_2.b = tmp
0x004024b6          buf[__i_2] = _i_2.b
0x004024bb          i_2 = __i_2 - 1
0x004024bb      while (i_2 != 0)
0x004024bd      val = 0
0x004024ed      do
0x004024c9          i_2 = i_2 + 1
0x004024cc          int64_t xorb
0x004024cc          xorb.b = i_2.b
0x004024ce          val = val + buf[1 + xorb]
0x004024d1          _i_2.b = buf[1 + xorb]
0x004024d5          uint64_t tmp_2 = buf[1 + val]
0x004024d5          buf[1 + val] = _i_2.b
0x004024d5          _i_2.b = tmp_2
0x004024d9          buf[1 + xorb] = _i_2.b
0x004024dd          xorb.b = buf[1 + val]
0x004024e0          xorb.b = xorb.b + _i_2.b
0x004024e3          xorb.b = buf[1 + xorb]
0x004024e6          *(i_2 + 0x4024f5) = *(i_2 + 0x4024f5) ^ xorb.b
0x004024e6      while (len != i_2)
0x004024f6      return val

First, 0x87 bytes of instructions from 0x0040246f are copied into a heap chunk and executed. An initial breakpoint causes the child to halt execution until receiving PTRACE_SIGCONT from the parent. When the child is halted at 0x0040246f the parent writes to rip+0x86 (0x00402470+0x86 = 0x4024f6), inserting instructions and overwriting the final return. The RC4-like encryption algorithm after the breakpoint decrypts the copied memory in-place and subsequently executes it.

To find out what is being executed, we can replicate the decryption on the chunk array and analyze each chunk's functionality. I opted to reimplement the decryption in Python, however, instrumenting this code blob using the Unicorn Engine is also viable.
import struct
import os
import os.path

lines = open("./blobs.hex").read().split("\n")
chunk_keys = bytes.fromhex(lines[0])
chunk_lens = bytes.fromhex(lines[1])
chunk_codes = bytes.fromhex(lines[2])

def rc4_decrypt(key, chunk, version=1):
    buf = [(i & 0xff) for i in range(0x101)]

    # key scheduling
    val = 0
    for i in range(0x100, 0, -1):
        val = (val + buf[i]) & 0xff
        key_shift = (i % 8) * 8
        key_byte = (key >> key_shift) & 0xff
        val = (val + key_byte) & 0xff
        tmp = buf[1 + val]
        buf[1 + val] = buf[i]
        buf[i] = tmp

    if version == 1:
        val = 0
        val = 0x90

    chunk = list(chunk)
    for i in range(1, len(chunk) + 1, 1):
        xorb = i & 0xff
        val = (val + buf[1 + xorb]) & 0xff
        tmp = buf[1 + val]
        buf[1 + val] = buf[1 + xorb]
        buf[1 + xorb] = tmp
        xorb = (buf[1 + val] + buf[1 + xorb]) & 0xff
        xorb = buf[1 + xorb]
        chunk[i-1] ^= xorb
    chunk = bytes(chunk)

    return chunk

pos = 0
chunk_lens = [0x7f] + list(chunk_lens)
for i,chunk_len in enumerate(chunk_lens):
    if chunk_len == 0:
    chunk_key = struct.unpack("<Q", chunk_keys[i*8:i*8+8])[0]
    chunk_code = chunk_codes[pos:pos+chunk_len]
    if i < 3:
        dec_chunk = rc4_decrypt(chunk_key, chunk_code, version=1)
        dec_chunk = rc4_decrypt(chunk_key, chunk_code, version=2)
    if not os.path.exists(f"dec/chunk.{pos:04x}"):
        with open(f"dec/chunk.{pos:04x}", "wb+") as f:
    pos += chunk_len

Reversing what each chunk does is not exactly as straight-forward as reading its standalone disassembly since chunks often reference parts of the program outside themselves and relative to where they are mapped. One trick to dealing with this is to map the chunks into the original binary again (one at a time) at the position they would be in memory relative to the loader code, and use a disassembler to make sense of what is being referenced.

As it turns out, the first few chunks are responsible for outputting the greeter text, getting user input, xoring it with 0x0d and modifying the encryption algorithm (hence the version parameter).

The rest of the chunks validate the input through multiple checksums and finally output whether the flag was correct.

Each chunk follows a similar format:

/* load start of user input */
   0:   48 8d 5c 24 08          lea    rbx, [rsp+0x8]

/* compute some val in rdi, by multiplying dwords from
   compute blob (see below) with dwords from user input */
   5:   48 8d 15 2f 00 00 00    lea    rdx, [rip+0x2f]  # 0x3b
   c:   48 31 ff                xor    rdi, rdi
   f:   48 31 c0                xor    rax, rax
  12:   48 31 c9                xor    rcx, rcx
  15:   8b 04 8a                mov    eax, DWORD PTR [rdx+rcx*4]
  18:   0f af 04 8b             imul   eax, DWORD PTR [rbx+rcx*4]
  1c:   01 c7                   add    edi, eax
  1e:   fe c1                   inc    cl
  20:   48 83 f9 10             cmp    rcx, 0x10
  24:   72 ef                   jb     0x15

/* val = (val == 0x9b1bf3e5) */
  26:   2b 3d 4f 00 00 00       sub    edi, DWORD PTR [rip+0x4f]  # 0x7b
  2c:   f7 df                   neg    edi
  2e:   19 ff                   sbb    edi, edi
  30:   ff c7                   inc    edi

/* increment value on stack if correct */
  32:   58                      pop    rax
  33:   01 f8                   add    eax, edi
  35:   50                      push   rax

/* next chunk */
  36:   e9 c4 00 00 00          jmp    0xff

/* compute blob */
  3b:   07                      (bad)
  3c:   80 32 0a                xor    BYTE PTR [rdx], 0xa
  3f:   c0 47 41 c9             rol    BYTE PTR [rdi+0x41], 0xc9
  43:   ca 55 64                retf   0x6455
  46:   b7 61                   mov    bh, 0x61
  48:   8f                      (bad)
  49:   d6                      (bad)
  4a:   e0 89                   loopne 0xffffffffffffffd5
  4c:   b8 95 44 27 49          mov    eax, 0x49274495
  51:   37                      (bad)
  52:   26 90                   es nop
  54:   6c                      ins    BYTE PTR es:[rdi], dx
  55:   28 0c c6                sub    BYTE PTR [rsi+rax*8], cl
  58:   e3 0c                   jrcxz  0x66
  5a:   22 e2                   and    ah, dl
  5c:   72 bd                   jb     0x1b
  5e:   24 13                   and    al, 0x13
  60:   b1 f2                   mov    cl, 0xf2
  62:   1d be 0e 0e 04          sbb    eax, 0x40e0ebe
  67:   34 67                   xor    al, 0x67
  69:   89 f3                   mov    ebx, esi
  6b:   1c 22                   sbb    al, 0x22
  6d:   98                      cwde
  6e:   21 a5 41 3e 36 bd       and    DWORD PTR [rbp-0x42c9c1bf], esp
  74:   18 37                   sbb    BYTE PTR [rdi], dh
  76:   af                      scas   eax, DWORD PTR es:[rdi]
  77:   d0 5b 66                rcr    BYTE PTR [rbx+0x66], 1
  7a:   9a                      (bad)
  7b:   e5 f3                   in     eax, 0xf3
  7d:   1b                      .byte 0x1b
  7e:   9b                      fwait
  7f:   90                      nop
  80:   d5                      (bad)
  81:   d1                      .byte 0xd1


We can extract the constraint information (compute blob and checksum) from each chunk exported and solve for an input string that satisfies these constraints using z3.
from z3 import *
import struct

s = Solver()

chunk_excl = ["chunk.0000", "chunk.007f", "chunk.00db",
            "chunk.01b9", "chunk.0a49"]
flag = [BitVec(f"f{i}", 32) for i in range(0x40 // 4)]
chunks = os.listdir("dec")
count = 0
for chunk in chunks:
    if chunk in chunk_excl:
    count += 1
    data = open("dec/"+chunk, "rb").read()
    checkvals = [struct.unpack("<I", data[i:i+4])[0] for i in range(0x3b, 0x7b, 4)]
    checksum = struct.unpack("<I", data[0x7b:0x7b+4])[0]
    _checksum = 0
    for i,val in enumerate(checkvals):
        _checksum += val * flag[i]
    s.add(_checksum == checksum)
assert(count == 0x10)

while s.check() == sat:
    m = s.model()
    flagvals = [m[v].as_long() for v in flag]
    flagbytes = b"".join([struct.pack("<I", v) for v in flagvals])
    flagbytes = bytes([c ^ 0x0d for c in flagbytes])
    for i,v in enumerate(flag):
        s.add(v != flagvals[i])