Cache Me Outside picoCTF 2021 Solution

Description

1. Step 1

   Understand the heap layout with GDB

   Observation

   I noticed the challenge description mentioned a tcache binary and a heap dump file, which suggested the vulnerability involves glibc's per-thread caching freelist; mapping the exact chunk layout in GDB was the first step to finding the offset between user_buf and the tcache fd pointer.

   Run the binary in GDB with pwndbg or peda. The program allocates a buffer and stores the flag on the heap. By examining the heap, you find the flag is located at offset -5144 bytes relative to a specific heap pointer that the program asks you to index into.

   bash

   gdb ./heapedit

   Copied!

   bash

   # In GDB:

   Copied!

   bash

   run

   Copied!

   bash

   heap chunks

   Copied!

   What didn't work first

   Tried: Use 'heap bins' instead of 'heap chunks' to inspect the tcache state right away.

   'heap bins' shows the freelist bins but not the raw chunk layout or addresses, so you cannot compute the byte offset from user_buf to the tcache fd pointer. You need 'heap chunks' (or 'vis') to see every chunk's address and size, then cross-reference with 'tcachebins' to find which fd pointer to target.

   Tried: Run the binary without GDB first to observe its input prompts, then guess the offset from the heap dump zip file alone.

   The zip contains a static snapshot of one particular heap run; the actual heap base address randomizes with ASLR on each execution. The relative offset (-5144) must be derived from the live heap layout under GDB where you can read both user_buf's address and the tcache fd slot's address at the same runtime.

   Learn more

   The tcache (thread-local caching) is a per-thread free list introduced in glibc 2.26 (2017). When you free a small chunk, it goes into the tcache bin for its size class. The next malloc() of the same size returns the tcache entry immediately - very fast, but with minimal security checks compared to main arena bins.

   Heap layout for this challenge. When the program starts it does roughly:

   flag_chunk    = malloc(N);   // flag is read into here, then freed
                 free(flag_chunk);  // flag chunk now sits in tcache fd
   user_buf      = malloc(N);   // returns flag_chunk (LIFO)
                                // but flag bytes are still resident
                                // until you overwrite the chunk header
   
   heap layout (low -> high):
     +------------------+  <- heap_base
     | tcache bookkeeping (per-size counts + fd ptrs)
     +------------------+
     | flag_chunk       |  contains flag string
     +------------------+
     | user_buf header  |
     | user_buf data    |  <- program writes your byte[index] here
     +------------------+

   Tcache poisoning works by overwriting the fd(forward pointer) field of a freed tcache chunk to point to an attacker-controlled address. The next two malloc() calls return the attacker's address as if it were a valid heap chunk.

2. Step 2

   Send the negative index to reach the flag

   Observation

   I noticed the program accepts a signed index with no bounds check, which suggested that a negative value could reach backward into the tcache bookkeeping region at the heap base; writing a null byte there would corrupt the fd pointer so the next malloc returns the chunk still holding the flag.

   When the program asks for an index, send -5144. This causes the program to write a null byte to the address (heap_base + (-5144)), which overwrites the tcache fd pointer. The next malloc() call returns the address where the flag is stored, and the program prints it.

   python

   python3 << 'EOF'
   from pwn import *
   
   p = remote("mercury.picoctf.net", <PORT>)
   p.recvuntil(b"input:")
   p.sendline(b"-5144")
   p.recvuntil(b"input:")
   p.sendline(b"")
   print(p.recvall().decode())
   EOF

   Copied!

   Expected output

   picoCTF{...}

   What didn't work first

   Tried: Send a positive index like 5144 instead of -5144, expecting the tcache fd pointer to be located after user_buf in memory.

   The tcache bookkeeping region lives at the very base of the heap, which is at a lower address than user_buf. A positive index walks forward into later allocations (other heap chunks or unmapped memory) and either reads garbage or triggers a segfault; only a negative index reaches back toward the heap base where the freelist fd slots reside.

   Tried: Send -5144 as the index but then send a non-null byte (e.g., 0x41) as the value to write, hoping to redirect malloc to an arbitrary address.

   Writing a non-zero byte to the low byte of the tcache fd pointer produces an invalid heap pointer that malloc cannot dereference cleanly, typically causing a crash or corrupting the bin. The exploit relies on writing 0x00 specifically because that truncates the low byte to zero in a way that makes the fd pointer resolve to the address of the flag chunk - any other byte value produces a different (wrong) target address.

   Learn more

   Why -5144? The program treats user input as a signed index into user_buf with no bounds check. user_buf[-5144] resolves to the byte at &user_buf - 5144. Because the heap grows up but tcache bookkeeping sits at the very base of the heap, that negative offset lands inside tcache's freelist table:

   heap_base + 0x???      tcache fd[bin_for_flag_size]   <- TARGET
                          ...
   heap_base + 0x???      flag_chunk header
                          flag_chunk data (the flag)
                          ...
   heap_base + 0x???      user_buf header
   &user_buf  ----------- user_buf[0]                    <- index = 0
                          user_buf[-1]                    <- 1 byte before
                          ...
                          user_buf[-5144]                 <- lands on tcache fd's
                                                            lowest byte

   What the null byte does. The freed flag chunk's fd pointer normally points at the next free chunk in the same bin (or NULL). Writing 0x00 to the lowest byte of that pointer truncates it -- but in this challenge the goal is more clever: by stomping the right byte of the freelist head pointer you rewrite it to point at a chunk whose contents are the flag. The next malloc() request that hits the same size bin returns that chunk, and the program prints its contents back to you.

   Determining 5144 in practice. Run under pwndbg/gdb, breakpoint right before the indexed write, then:

   pwndbg> heap                                 # see all chunks
   pwndbg> tcachebins                            # see fd pointers
   pwndbg> p/x &user_buf - tcache_fd_target_addr # -> e.g. 0x1418 == 5144
   pwndbg> p/d -5144                              # confirm the index

   Verifying -5144 against your running glibc. The number is glibc-version-specific: tcache bookkeeping layout shifts subtly across releases (and entirely once safe-linking lands in 2.32+). Don't copy the constant blindly, confirm it under pwndbg:

   pwndbg> b *write_into_buf       # break right before the indexed write
   pwndbg> r
   pwndbg> heap                    # see all chunks + addresses
   pwndbg> tcachebins               # see the fd pointers per size class
   pwndbg> vis                      # visualize the heap byte-by-byte
   pwndbg> p/x &user_buf - &tcache_fd_target_byte
                                   # -> 0x1418 == 5144 (decimal)
   pwndbg> p/d -5144                # confirm the index value to send

   Modern glibc (2.32+) added tcache safe-linking: the stored fd is XOR-masked with the upper bits of its own address (fd ^ (addr >> 12)). On those versions a single null byte cannot meaningfully corrupt fd because you would need to compute a value that, when XOR'd with the random mask, yields the desired pointer. Older glibc (as in this challenge) stores fd as plaintext, so direct overwrite works. For more on the tcache primitive shapes and how they compose, see the heap exploitation guide; to drive the interaction in script form, see the pwntools guide.

Flag

Tcache poisoning overwrites the singly-linked free list's next pointer - the subsequent allocation then returns an attacker-chosen address.