gman Write-up
Another year and another Bsides CTF! As with tradition, the plan was to rabbit hole on one reversing puzzle all weekend. This year I picked up gman, a video game inspired challenge.
gman is a terminal-based game of Pac-man, with a shared high score list and all. In the top left screenshot, the yellow character is the player, the blue characters are walls, and the other colored letters are ghosts. The most interesting aspect of this Pac-man game is its save states. After each death, the game issues a password to allow the player to return to that exact point in their game. The password encodes the level number, score, and number of lives left. This puzzle was worth 500 points, which is the max point value for a single puzzle. My team was only one of two to solve this challenge!
With my luck, the start of this CTF was environment setup hell: fighting Virtualbox to let me SSH into my instance, fixing the VM’s graphical lag, debugging why the clipboard wasn’t being shared between my host and guest OS, linking shared libraries under the correct symlinks, etc. The last item there was the biggest head ache; gman expects libncurses to be installed, which is easy enough, but it expects the library to be symlinked under /usr/lib/libncursesw.so.6 and /usr/lib/libncursesw.so.6.
The exact error was:
./gman: error while loading shared libraries: libncurses.so.6: cannot open shared object file: No such file or directoryThe solution is to locate your libcurses library, install it if necessary, and symlink it like so.
$ locate libncurses
/lib/i386-linux-gnu/libncurses.so.5
/lib/i386-linux-gnu/libncurses.so.5.9
/lib/i386-linux-gnu/libncursesw.so.5
/lib/i386-linux-gnu/libncursesw.so.5.9
$ sudo apt install libncurses5-dev libncursesw5-dev
$ sudo ln -s /lib/i386-linux-gnu/libncursesw.so.5.9 /usr/lib/libncurses.so.6
$ sudo ln -s /lib/i386-linux-gnu/libncursesw.so.5.9 /usr/lib/libtinfo.so.6You’re welcome!
Reversing the Puzzle
I was finally at a place where I could start debugging and reversing the actual puzzle at hand. A lot of time was spent aimlessly annotating the binary and figuring out the data structures used by the game. My teammate Ross made a great observation that the game’s state was stored as a struct on the stack. He also reversed the majority of the password format; this gave me enough information to start testing out custom passwords. In this process, I found a few crashes by messing with the password entry function. Unfortunately, the code it led me to didn’t turn out to be exploitable.
At this point in the CTF, from purely analyzing the binary, it still wasn’t clear what the intended goal of the puzzle was. On the morning of the second day, the CTF organizers dropped a huge hint that the goal was actually a file on the server called flag.txt. Great. That means I needed to find a way to read out this file.
From here, it was relatively easy to piece together the final steps; I already had a very clear picture of the binary since I spent the first day reversing it. There are convenient fopen and fread calls in the game itself to print the high scores. The pointer to the string of the file name that gets opened is stored on the stack in the instructions() function (suspicious!). The goal was to find an exploit to overrun this pointer on the stack so that it points to the player's name instead, which can be set to /home/ctf/flag.txt.
The two observations that were the key to finding the exploit were:
- The game state is stored on the stack.
- The password validation function doesn’t check that the level was under 100 (the max number of valid maps the game generates).
If one were to generate a password to trigger level 101, the map would load from arbitrary data on the stack that lives below the game struct. And what lives there? The pointer to the file name string — the target we want to modify. When Pac-man eats a pellet, it clears a bit on the stack, so if you carefully navigate Pac-man to eat the correct bits in level 101, you’d be able to perfectly craft the stack to contain the pointer to your name string, which was stored in a constant place in BSS. (ASLR doesn’t randomize the BSS section’s address.)
To generate the password to level 101, I loaded the game in GDB, edited the game state to load level 101, and then died. Voila, here’s the password:
With some careful bit calculations, I could figure out the pellets Pac-man needed to eat in level 101.
At this point in the CTF, I was down to minutes! In my rush, I managed some terribly embarrassing math and calculated the wrong pellets to eat, and missed the official CTF deadline (big oops). But after a pizza dinner, I came back with a clearer head and found the correct pellets (I’ll spare you the dry details). In the screenshot below, the pink dots indicate rows and bits I shouldn’t touch since it contained data like the stack canary that was awfully adamant about not being changed. The green dots were the ones I needed to eat. The blue dots were bits on the stack within the pointer I needed to keep high (don’t walk over those).
The final trick was to lead the ghosts into a corner so they couldn’t chase you while you ate the pellets. The ghosts can’t move backwards, so if you lead them into a corner where they are surrounded on three sides, they wouldn’t be able to escape. The ghosts’ AI would move towards the player even if the player is beyond a wall. Knowing this, I would position Pac-man with a trap corner between Pac-man and the ghosts and the ghosts would walk right into the corner.
And here’s the flag!
As always, kudos to the Bsides organizers for creating such fun and intricate puzzles. Credit to Ross Glashan and Jordan Mecom for also working on this puzzle! Thanks team! :-)
Learnings and Cool Observations
Ghidra’s decompiled output looked obfuscated in certain functions. For example, compare Ghidra’s decompiled version of get_bit() against the original source code.
Ghidra (with my annotations)
uint get_bit(byte *board,int pos_x,int pos_y)
{
byte zero;
int board_tile_id;
__x86.get_pc_thunk.ax();
board_tile_id = pos_x + pos_y * 0x1b;
if (board_tile_id < 0) {
board_tile_id = board_tile_id + 7;
}
pos_x = pos_y * 0x1b + pos_x;
zero = (byte)(pos_x >> 0x37);
/* crashes
(board[tile_id / 8] >> (7 - (pos_x % 8))) & 1 */
return (int)(uint)board[board_tile_id >> 3] >>
(7 - (((char)pos_x + (zero >> 5) & 7) - (zero >> 5)) & 0x1f) & 1;
}Note the variable that always evaluates to 0 that I named zero. Multiple subexpressions also evaluate to zero. Bonkers stuff. I put off analyzing this function since my eyes glazed over every time I read that stupidly long expression at the end. Even then, it took me a while to untangle what was going on since I wasn't expecting obfuscated code.
Original Source Code
uint8_t get_bit(uint8_t *array, int x, int y) {
int byte = ((y * COLS) + x) / 8;
int bit = ((y * COLS) + x) % 8; // Invert the bit so it reads left to right
bit = 7 - bit; return (array[byte] & (1 << bit)) ? 1 : 0;
}
The original code reads like sane C. The takeaway here is that decompilers still have a ways to go and to expect obfuscated code from decompilers.
Next, if you’re seeing odd pointer manipulation in your decompiled Ghidra output, it’s likely because Ghidra doesn’t know about the appropriate data types.
In the example above, I saw some awfully convoluted pointer manipulation; this was caused by Ghidra missing struct information. Once you tell it about the custom struct data type (you’ll need to fill in information about the field sizes yourself), the code looks much more sane.
Tools
Here are a few nifty tools I learned about. Thanks Jordan for showing me!
checksec
Cute bash script that checks what sorts of security features are enabled on a binary. Doesn’t require any dependencies; just run the shell script.
$ ./checksec.sh --file=./gman RELRO STACK CANARY NX PIE RPATH RUNPATH Symbols FORTIFY Fortified Fortifiable FILE Partial RELRO Canary found NX enabled No PIE No RPATH No RUNPATH 132 Symbols Yes 0 5./gmanreadelf
I learned that the rodata section of x86 binaries are not writable. I was misled by GDB since it can modify rodata, but during normal execution, the CPU doesn’t have such permissions. You can verify this using the tool readelf.
$ readelf -l ./gmanElf file type is EXEC (Executable file)
Entry point 0x8049250
There are 12 program headers, starting at offset 52Program Headers:
Type Offset VirtAddr PhysAddr FileSiz MemSiz Flg Align
PHDR 0x000034 0x08040034 0x08040034 0x00180 0x00180 R 0x4
INTERP 0x0011b4 0x080481b4 0x080481b4 0x00013 0x00013 R 0x1
[Requesting program interpreter: /lib/ld-linux.so.2]
LOAD 0x000000 0x08040000 0x08040000 0x0111c 0x01240 RW 0x1000
LOAD 0x0011b4 0x080481b4 0x080481b4 0x00638 0x00638 R 0x1000
LOAD 0x002000 0x08049000 0x08049000 0x035e4 0x035e4 R E 0x1000
LOAD 0x006000 0x0804d000 0x0804d000 0x00ad0 0x00ad0 R 0x1000
LOAD 0x006eec 0x0804eeec 0x0804eeec 0x001a8 0x001a8 RW 0x1000
DYNAMIC 0x006ef4 0x0804eef4 0x0804eef4 0x000f8 0x000f8 RW 0x4
NOTE 0x0011c8 0x080481c8 0x080481c8 0x00020 0x00020 R 0x4
GNU_EH_FRAME 0x0063dc 0x0804d3dc 0x0804d3dc 0x0014c 0x0014c R 0x4
GNU_STACK 0x000000 0x00000000 0x00000000 0x00000 0x00000 RW 0x10
GNU_RELRO 0x006eec 0x0804eeec 0x0804eeec 0x00114 0x00114 R 0x1
Checking for ASLR
Also, on Linux, you can check if ASLR is turned on with the following command.
$ cat /proc/sys/kernel/randomize_va_space0 – No randomization. Everything is static.
1 – Conservative randomization. Shared libraries, stack, mmap(), VDSO and heap are randomized.
2 – Full randomization. In addition to elements listed in the previous point, memory managed through brk() is also randomized.
CTF Tips and Takeaways
These are some tips and takeaways from doing multiple years of BSides reversing challenges.
- Start by analyzing the outwards behavior of the binary. This will give you the intuition of what to expect in the disassembly and decompiled code.
- Fully explore inputs to the binary. How does the user interact with the binary? What are your means to input a payload?
- Understand the goal. Not sure? Annotate the binary further. Pwnable challenges involve reading from a flag file on the server. Ask CTF organizers if you’re stuck; they are happy to provide assistance on Slack. Inspect the binary to find hints about a flag. Some puzzles include a help string, others include suspicious unused code in the binary. To find the unused subroutines, you’ll need to view the binary in the disassembled view. In IDA, code highlighted in red is unused.
- 100% Ghidra! I wrote up the setup steps and my first impressions here. In short, its GUI and decompiler are much easier to use than IDA’s.
- Set up your environment before hand. The BSides CTF folks tend to make Linux based puzzles, so have a Virtualbox VM running 64-bit Ubuntu at the ready. This will save you hours during the actual CTF. Plus, the Wi-Fi connection on site will be slow, so you’ll be cursing yourself if you have to download a giant Linux ISO at the conference.
