Sunday, April 20, 2014

Plaid CTF 2014 - Tiffany writeup

Looking at the binary for the first time we can say that this challenge is a 64bit ELF binary that does something related with ptrace. Because Hex-Rays fails with decompiling 64bit code we need to play a bit with a disassembler and find out how does the program work. To solve this crackme I’ve used Bokken (this is quite nice frontend for pyew & radare). After some time spend in front of disassembler and debugger I was able to say that the program has used a bit unconventional way of sending the messages that looked as follow:
  1. Attach to a process
  2. Set the dword at 0x618180 to 0x1 // notify about the message
  3. Set the dword at 0x618184 to destination id // each pid had its unique id
  4. Set the dword at 0x618188 to message type // offset in the procedures table
  5. Fill the space from 0x61818c up to 0x69818c by message arguments
  6. Detach from the process
  7. Send the signal to the process
Each (except parent) process had its own dispatcher of incoming messages that was checking address 0x618180 and when it was set to some not-null value, the corresponding handler of the message was called (based on the message type).

The dispatcher:

So when the message arrived, first it was checked if it was addressed to self node (which id was hold in r13) and if not, it was forwarded to previous from 7 nodes using the same method as described earlier (attach, modify memory, detach, signal). Using this scheme the parent process could send the message to any node having the handler only to its first child which would forward the message to the other node and so forth...

In fact the child process forwards the message to its predecessor and the initial predecessor of the #0 child was the parent node but the parent process changes it by sending the message to #0 asking to set the default forward node to #6 (function with offset 0 in procedures table, let’s use one-based indexing and name it the message of the first type).

Using this message forwarding, the parent process sends many messages of the second type to #0 where each message is addressed for different child:

for (child = 0; child < 8; ++child):
  r14 = [0x618160 + 4*child]
  ptrace_attach([0x618160 + 4*r14])
  ptrace_modify([0x618160 + 4*r14], 0x618180, 1)
  ptrace_modify([0x618160 + 4*r14], 0x618184, r14)
  ptrace_modify([0x618160 + 4*r14], 0x618188, 1)
  r12 = [0x6180c0 + 8*r14]
  r13 = [0x618100 + 4*r14]
  for (i = 0; i < r13; ++i)
    ptrace_modify([0x618160 + 4*r14], 0x61818c + 4*i, [r12 + 4*i])
  ptrace_detach([0x618160 + 4*r14])

From high level perspective the handler of the second messages does quite a simple thing, just stores the memory - argument of procedure - to it’s internal buffer (*0x618140 + 4):

Procedure #2 at 0x401196:
  length = *0x61818c * 0x404
  *0x618140 = malloc(4 + length)
  *0x618140 = (DWORD)*0x61818c
  memcpy(buffer, length, 0x618190)

It takes a moment and after that we are asked to enter the string of our choice:

This may take a while...
Please enter a string: _

When we enter some password, the parent process starts to send the fourth type of messages to its first child:

for each letter in password:
  ptrace_attach(*0x618160) // first child
  ptrace_modify(*0x618160, 0x618180, 1)
  ptrace_modify(*0x618160, 0x618184, 0)
  ptrace_modify(*0x618160, 0x618188, 3)
  ptrace_modify(*0x618160, 0x61818c, [rsp+0x98]) // letter

but as we can see, the child forwards it to its predecessor:

Procedure #4 at 0x4011f5:
  *0x618148 = (DWORD)[buffer + 4*(*0x618148 * 0x101 + *0x61818c + 1)]
  if (r14d < 7) // not the last child
    ptrace_attach(*0x61814c) // predecessor
    ptrace_modify(*0x61814c, 0x618180, 1)
    ptrace_modify(*0x61814c, 0x618184, r15) // self id + 1
    ptrace_modify(*0x61814c, 0x618188, *0x618188)
    for (i = 0; i < 0x20000; ++i)
      ptrace_modify(*0x61814c, 0x61818c + 4*i, *(0x61818c + 4*i)
  else notify parent about finish

In practise it looks like each child except the last one sends the message to its predecessor addressed to its successor, so the message is forwarded by all of the nodes to finally reach its destination. If you look closer to this procedure it not only forwards the data but also changes the state using the received letter. Finally when all of the letters are sent, the parent submits the last message (third type) that is some kind of a check of a password and looks like this:

Procedure #3 at 0x400db8:
  [rsp+0x98] = getpid()
  [rsp+0x9c] = 1
  for (int i = 0; i < 8; ++i)
    if (i == myId)
      [rsp+0x9c] &= [buffer + 4*(*0x618148 * 0x101)]
      ptrace_modify(*0x61814c, 0x618180, 1)
      ptrace_modify(*0x61814c, 0x618184, i)
      ptrace_modify(*0x61814c, 0x618188, 4)
      ptrace_modify(*0x61814c, 0x61818c, [rsp+0x98])

      while (*0x618180 == 0) sleep()
      *0x618180 = 0

      [rsp+0x9c] &= *0x61818c

  ptrace_modify(*0x618150, 0x618180, 1)
  ptrace_modify(*0x618150, 0x618180, 0)
  ptrace_modify(*0x618150, 0x618188, 0)
  ptrace_modify(*0x618150, 0x61818c, [rsp+0x9c])

So in short: send the message of the fifth type to each node except myself and wait for the answer. In the end send the message to parent informing if each of the nodes verified the password as true.

Procedure #5 at 0x40142c:
  [rsp+98] = [buffer + 4*(*0x618148 * 0x101)]
  ptrace_modify(*0x61818c, 0x618180, 1)
  ptrace_modify(*0x61818c, 0x618184, 0)
  ptrace_modify(*0x61818c, 0x618188, 0)
  ptrace_modify(*0x61818c, 0x61818c, [rsp+98])

Now having the knowledge how all of this stuff works, we could try to find the string that will be verified by all of child nodes. The value returned by each child is:

[buffer + 4*(*0x618148 * 0x101)]

where *0x618148 is previously generated from password letters:

*0x618148 = (DWORD)[buffer + 4*(*0x618148 * 0x101 + *0x61818c + 1)]

which looks like some kind of map… and in fact it is sort of map or finite state machine whose states are described by this fragments of memory previously transferred to each of the nodes. Now doing the boring part of analysis this memory chunks and transforming it into finite state machines we are able to discover that each of children checks some part of the password.

Using regular expressions:

#0: ^\{[^}]*\}$
#1: ^.{32}$
#2: _[^_]*_[^_]*_
#3: ^.my
#4: _synchronization
#5: _[^_]*_skills
#6: _[^_]*_[^_]*_suck

All of these parts can be easily merged to the final solution: {my_synchronization_skills_suck} 
That's all, nice one.

1 comment: