sokoban writeup

gistfile1.txt

From tsuro for Stratum Auhuur.
This challenge was a pwnable for 1000 points and it was a clone of the classic
game sokoban, reimplemented with the help of ncurses.  For everyone who doesn't
know what sokoban is, it's an old 2d puzzle game. (this is the time where you
should google for an image). You see your character from the top and have to
push boxes around to some marked destinations.  Anyway, the pwnable was exactly
that game. If you solve level 6, you get the option to enter an infinite mode in
which you get levels assigned randomly.

==Reversing==
The binary is little code so reversing it is not that bad (which is good, I'm
horrible at reversing).  The main function will call some ncurses setup routines
and enter the game loop. If the game returns 1, it will open the flag file and
print if for you, how convenient! How difficult can it be to do that.  So let's
take a look at the end of the game loop to find the spot where it returns 1...
but well, it doesn't. If you solve all levels, it will return 2, on any failure
it will return 0. So we'll have to pwn it after all.  The game has 3 game modes
it distinguishes internally, pre level 6, post level 6 and random. The levels
are stored in a char *array in ascii art and are loaded into the .data section
as follows: 0: empty space 1: goal (push the boxes here) 2: wall 4: box 5: box +
goal Also, there are variables for the player's x and y coordinate. The game
area is 32 byte wide and if you make a move, it will be checked if there's a
wall in your way but there are no other out of bounds checks besides that. If
you move to a space that is not empty, the code will check if the space behind
that is empty and move the byte to the next address.  Maybe you can see where
this is going.

==The bug==
As mentioned before, if you play the game up to level 6, it will ask you if you
want to switch to random mode. In that mode, the code will choose a random level
greater than 6 and load it to memory. However, there's an off by one error here
and you can load the string that marks the end of the array into the level
buffer. That string has conveniently no walls at all, which allows you to play
sokoban in memory instead. Sounds easy to pwn, so let's implement a "solver" for
the game next.

==Playing the game==
Interacting with ncurses over a socket from python is painful and looks
something like this: [0;10m. For the parsing, I just
scanned for the text strings I knew would come and played the first 6 levels
blind (since they're always the same). I wrote my "bot" with tmux :). Open two
panes next to each other, one is running vim and the other sokoban and then
:setw synchronize-panes. Play the first 6 levels manually and voila, you have
the solution in text form. Enter random mode and reset the level until this
string '..\x1b[0;10m\x1b[39;49m\x1b[37m\x1b[40m\x1b[K\r\n' appears.  This is
followed by '[$number;$numberH\x1b[1K \x1b[31m\x1b[40m@<' from which you can
parse the player start position.

==Pwning==
Alright, we can't play sokoban blind so let's draw a map. I dumped the programs
memory with gdb to a file and wrote a short script to convert it to ascii art.
Remember, we can move everything that is not a 2, but only if there's space (a
null byte) behind it. You can see my map here:
https://gist.github.com/stephenR/77b9f3d21d935993ab45
At the top is the got.plt, below that is the array with pointers to the ascii
strings of the levels, the @ is the player position (if you move it to 0:0) and
behind that are the variables for the x and y coordinates. X in the got.plt
marks the <rand> pointer and the question mark is a convenient magic byte that
can be changed to any even byte we want.  So, ideally we would change a function
pointer, but we can't move anything in there. For that we would have to move a
byte out first but we can't get between the pointers. My next idea was to
overwrite the x/y position so that we end up on top of one of the function
pointers, but that doesn't work since the coordinates will be reloaded after the
write. So what to do?  The problem is that there is no null byte in the function
pointers. But thanks to aslr, <rand> will have a null byte as the second byte
one in sixteen times. So my first approach was to push the least significant
byte out and put two new bytes in.  Luckily we got the libc, so we can look for
gadgets conveniently. And remember, we only have to make the game return a 1 and
it will print the flag for us. We already control eax on the call to rand, so
all there's left is to find a pop n/add rsp; ret gadget and there are plenty of
those.  So let's do that, find a gadget, push the byte out, put two new bytes in
and we're done. But that crashes :\. Between two moves, the adjacent function
pointer is used and the program segfaults. This point took me another while to
get to the next step though now it feels obvious: You don't have to push the
byte out, just find a gadget with the same first byte by just changing the
second byte. (Or you could move the first to the second byte and look for a
gadget with the first byte).  And that's basically it, find the gadget, push the
byte in and 1 in 16 times, it will print you the flag. And if you're lazy with
parsing, just write a loop that will dump all the responses to a file and use
strings after 30 minutes :).