PlaidCTF 2011 – 25 – PC Rouge – 600 pts

This is my writeup for the twenty-fifth challenge in the PlaidCTF 2011 competition. The information for the challenge was:

“Amalgamated has banned the use of Solitaire due to loss of productivity.
The only employee who would write a new game for everyone only likes ‘retro’ games, and has placed a text-adventure version of pacman on a company server.
We don’t believe he could have coded this securely, and the server contains a vital key.
Connect to the game here and find the key.
nc a9.amalgamated.biz 60123”

There was no binary available for download, so this level was actually completely blind. Connecting to the game we get:

Typing “help” gave a list of valid commands:

Walking around in the maze eating pills we notice a few things. First I noticed that after eating 16 pills, each increasing my number of points with 8, my number of points suddenly becomes -128. This indicates that a signed 8-bit integer is used to store the number of points.

We also notice that the number of power points seem to determine which item that is listed in our status. Each time we eat a powerpill the number of points increase with 40, and each time we make a move the number of power points (if any) decreases with one. The somehow odd “t” command which is described as “wait” decreases the number of power points with one as well, and surely this must be for a reason.

Moving on through the game eating pills and powerpills as we encounter them, we will sooner or later run into this situation:

We cannot eat another powerpill since this would put us over the maximum of 128. However, if a signed 8-bit integer is used for the number of powerpoints as well the real maximum should be 127. Let’s use the “t” command a few times until our number of powerpoints is 88, and let’s see what happens when we eat the powerpill:

Notice anything strange? Well, besides now having a negative number of powerpoints (which we sort of expected) we can also see that our item-string is now “n” instead of “The some-name Trophy!”. Since the number of powerpoints seemed to determine the item that is listed, it seems likely that the number of powerpoints is used as an index into an array of items/trophies and that when a negative index is being used (-128) it will point into some other string that in this case happened to be “n”.

So where does this “n” come from? Well, since “n” is one of the commands for this game it could certainly be a command string that I’ve entered earlier. It’s not the last command I’ve entered though, so if “n” is indeed a command it is probably stored in a command history buffer. Looking back through the scrollback we also notice:

See the “Command limit reached.” message? We got that on our 127:th command, which probably means that a history of 127 commands are being stored in an array. If this array is stored right before the item string array, the “n” listed as our item after getting a negative number of powerpoints may be taken from this command history array. So, let’s see what happens if we use “t” or some other command until the command limit is reached again:

As you can see I’ve jumped ahead a bit to show you how this bug is turned into an exploitable vulnerability. The very first command entered after the command limit has been reached is used as the item-string, and is actually being passed directly as the format string argument to presumably printf(). This allows to read memory, like we do above, or even write to arbitrary addresses using the %n format string specifier.

After the number of power points have been wrapped into -128, it stays there, so now we can just wrap around the command history buffer each time we want to use a different format string. I developed the following script for being able to play around, enter different format strings and examine their output:

Note that {32-bit-integer-in-hex} will be converted to a raw binary 32-bit integer by the script. This can be used to embed addresses to dump or overwrite. Here’s a sample session:

Here I first determine the offset to the command buffer, by dumping the stack four bytes at a time with %x. The first three bytes are overwritten by a command that has been sent later (‘t’ = 0x74), so if we want to embed an address to read from or write into we should prepend some padding. My second attempt uses %12$s to dereference the pointer that I embed at offset 12 (0x08048000). Obviously NUL-bytes are not a problem, as long as they are located after the format string. The format string buffer is actually located in dynamically allocated memory on the heap, while the command buffer is located in a local variable on the stack. The only problematic byte is 0x0a (e.g. ‘\n’ = line-feed), which ends the command string and is converted to a NUL-byte in the buffer.

Using this technique we are able to dump the entire binary for the level, except for a few bytes at addresses containg 0x0a that we assume are NUL-bytes. This produces a valid enough binary for further analysis in IDA Pro, where we can clearly see the vulnerable call to printf:

We also see that fgets() is used to read our commands, and that the line-feed character is converted to a NUL-byte, just as we have observed:

If we use the format string vulnerability to overwrite a GOT-entry, fgets() seems to be the perfect choice since its first argument happens to be a pointer to our buffer. If we embed a command line to be executed there and point fgets() into system() instead, our command line will be executed.

Now we just need to find system(), either by bruteforcing it or by reading a GOT-entry and calculating the address to system() based on its offset from the function whose GOT-entry we’ve read. We used the latter method to find system() based on its offset from fgets(). Since we had not yet noticed that a5 and a9 used the same libc, we first dumped libc using this vulnerability as well. :) Finally, we ended up with the following exploit:

And finally, here is a sample run: