Can you escape the maze and find the SHA2017 CTF tent?
nc maze.stillhackinganyway.nl 8001
The attached binary - maze is a 64 bit elf executable. After running checksec on it we get:
NX is enabled and objdump shows that the ret instruction in main is protected by a stack cookie. On the target system ASLR is enabled.
The analysis of the disassembly of the executable shows that the executable is a maze simulator. The maze is made up of rooms placed on a 32x32 square. Each room is numbered from 0 to 1023. While being in a given room we can move to rooms adjacent to us. Not every move is allowed - in the .data section of the executable there is a table encoding the allowed moves in each room. Each room contains a pseudo random ammount of mate. I do not know what mate means in this context but i think it could be related to the beverage called mate. In this writeup I will use the word mate to refer to the number storred in a given room of the maze. The mate values are stored in a table located on the stack.
We are prompted for commands in an infinite loop. The allowed commands are:
n- Move north (if the path is clear we substract 32 from the current room number)s- Move south (if the path is clear we add 32 to the current room number)w- Move west (if the path is clear we substract 1 from the current room number)e- Move east (if the path is clear we add 1 to the current room number)take X- Take exactly Xmatefrom the current room if the room has enoughmatein itdrop X- Leave exactly Xmatein the current room if we have got enoughmatehelp- display the avaliable commandsq- Exit the program
After executing each command the executable prints the current room number, the ammount of mate in the room and our current ammount of mate available for dropping.
The executable starts in the room number 0 and to exit the main loop we need to go to the room with number 1023 and have exactly 31337 mate with us.
The flaw in the executable is that we do not check whether we are still in the maze or not. The analysis of the hardcoded table in the .data section shows that we can leave the maze and explore rooms with negative numbers and rooms with numbers greater than 1023. The table in which the amount of mate in the rooms is saved is located on the stack together with the amount of mate available to us, the current room number and other local variables.
The amount of mate in the rooms is written as a 16 bit signed integer. Thanks to the take and drop command we can manipulate the stack and as the program prints the amount of mate in the current room we can read the variables on the stack. We do not have control of table describing the maze so in result we can not explore every variable on the stack and we need to be careful to not enter a room from which we can not leave.
I first tried to overwrite the current room number so I could teleport to a room with a number greater than 1023 but because the current room number was stored at a negative offset with respect to the table containing the ammount of mate available this failed. Because of it I analyzed the hardcoded table in the .data segment and obtained a sequence of moves that allows us to get to room 1023.
To write anything on the stack we need sufficient mate so because the amount of mate available was written on the stack as a signed 32 bit integer I have overwritten the 16 most significant bytes of this variable to get practically infinite mate. This allowed me to write anything on the stack.
Because of the small size of the binary and the lack of a syscall gadget in the binary we need to obtain some information about the location of the stack and shared libraries.
If we could get the location of the libc library and the stack during runtime the exploit would be straightforward. I first tried to locate the stack - analysis in gdb showed that in the rooms from -25 to -29 there is an address pointing to memory mapped to the stack. By dereferencing this address we get:
When the binary is launched the linux kernel together with libc do some magic to set up the executable before calling main. For people intrested what happens before main is called I recommend reading this article. During the initialization phase many functions are called and the resulting stack frames are not cleared uppon leaving. In conclusion I think that the obtained address is probably a saved rbp value leftover from the initialization of the binary - so we can locate the stack based on it. Analysis showed that the variable containing the current room number is located at offset 2120 from the leaked pointer.
After locating the stack and obtaining practically infinite mate we solve the maze and try to locate libc. After dumping variables from the stack I found the return address to libc. This address allowed me to use libc_database to determine the version of the libc running on the remote system.
I obtained two candidates.
The binary contains a pop rdi; ret; gadget:
We have enough information to start a shell. After obtaining the stack and libc location and practically infinite mate we overwrite the main return address with our payload:
Address of pop rdi; ret; gadgetAddress of "/bin/sh" on the stackAddress of system() function in libc"/bin/sh"
As we do not disturb the stack cookie - all we need to do after writing this payload to the stack is to exit the main loop. A simple q command is not enough as this command calls the exit() function. We need to win the game. Thanks to not checking whether the mate amount in a room overflows we simply issue a drop command in such a way that we got exactly 31337 of mate remaining. After going back to the room 1023 the rop chain is executed and we obtain a shell.
I want to thank Krzysztof Zając for providing a review of the first version of this writeup.