Cache Me Outside picoCTF 2021 Solution

Description

1. Step 1Understand the heap layout with GDB

   Observation

   The description mentions a tcache binary and a heap dump, so the bug involves glibc's per-thread caching freelist. Mapping the exact chunk layout in GDB is what gives 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 there is no way to compute the byte offset from user_buf to the tcache fd pointer. Use 'heap chunks' or 'vis' to see every chunk's address and size, then cross-reference 'tcachebins' to pick the 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 holds a static snapshot of one heap run, while the real heap base randomizes with ASLR on every execution. Derive the relative offset, -5144, from the live layout under GDB, where you can read user_buf's address and the tcache fd slot's address at the same moment.

   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 2Send the negative index to reach the flag

   Observation

   The program takes a signed index with no bounds check, so a negative value reaches backward into the tcache bookkeeping region at the heap base. Writing a null byte there corrupts the fd pointer, and 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 sits at the very base of the heap, below user_buf. A positive index walks forward into later allocations or unmapped memory and either reads garbage or segfaults. Only a negative index reaches back toward the heap base where the freelist fd slots live.

   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 into the low byte of the tcache fd pointer leaves an invalid heap pointer that malloc cannot dereference cleanly, which crashes or corrupts the bin. The exploit needs 0x00 specifically, because zeroing that byte makes the fd pointer resolve to the flag chunk's address. Any other value points somewhere else.

   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.