non_perfect_guesser

Platform: spbctf | Category: pwn | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-07-05 | Status: Solved Techniques: fastbin_smallbin_simulation, int_malloc_reimplementation, malloc_state_parsing, tcache_head_prediction

Summary

Task: glibc 2.31 malloc-predictor pwn that dumps main_arena and the tcache_perthread_struct each round and asks you to predict the exact pointer malloc(size) will return, 42 times, to get cat /flag. Solution: because glibc 2.31 has no safe-linking, every tcache/fastbin fd is a raw address, so the full allocator state is disclosed; reimplement the _int_malloc allocation priority (tcache head -> fastbin -> smallbin bk -> unsorted/top) from the dumped structs to answer every round deterministically with zero memory corruption.

non_perfect_guesser — spbctf

Description

A remote service (nc 109.233.56.90 11754). Predict the EXACT pointer that malloc(size) will return, 42 times in a row (N_CHALLENGES=42). Each round the program dumps the full main_arena (struct malloc_state, 0x898 bytes) and the tcache_perthread_struct (g_tcache, 0x280 bytes). Commands: solution\n{hex(ptr)} (guess) and readQ\n{hex(ptr)} (arbitrary read). After 42 correct guesses it runs system("cat /flag").

Target: glibc 2.31 (Ubuntu 20.04.3 LTS, GLIBC 2.31-0ubuntu9.2). Binary is PIE, Partial RELRO, NX, no canary. This is the slightly easier sibling of perfect_guesser; guessers.diff shows the only source difference is the odd-index size pool modulus (% 1000 here vs % 2048 in the harder variant), so the size pool g_sizes[14] is smaller and stays in tcache/fastbin/smallbin range. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Note on flag format: the task header advertised CODEBY{...}, but the live server emits the flag as spbctf{...}. The server output is authoritative.

Analysis

The server heap is pre-arranged by massage(): it mallocs N_CHUNKS=2048 random-sized chunks (each interleaved with a malloc(0) guard), frees them all (filling each tcache bin to 7 and overflowing the rest into fastbins / smallbins / unsorted), does a malloc(10000), re-allocates 1/3 of them, then frees everything again. The result is a busy but fully-known allocator state. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

 c read-only • copy allowed Copy
void massage() {
  getrandom(g_sizes, sizeof(g_sizes), 0);
  for (i = 0; i < N_g_sizes; i++) {
    if (i & 1) g_sizes[i] = g_sizes[i] % 1000;  // odd idx  (perfect_guesser: % 2048)
    else       g_sizes[i] = g_sizes[i] % 256;   // even idx
  }
  for (i = 0; i < N_CHUNKS; i++) { size = g_sizes[rand % 14]; g_chunks[i] = malloc(size); malloc(0); }
  for (i = 0; i < N_CHUNKS; i++) { free(g_chunks[i]); g_chunks[i] = NULL; }
  malloc(10000);
  for (i = 0; i < N_CHUNKS/3; i++) { size = g_sizes[rand % 14]; g_chunks[i] = malloc(size); malloc(0); }
  for (i = 0; i < N_CHUNKS; i++) { free(g_chunks[i]); g_chunks[i] = NULL; }
}

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Then the main loop, 42 times, dumps state and asks for the next malloc(size):

 c read-only • copy allowed Copy
for (i = 0; i < N_CHALLENGES; i++) {
  getrandom(&size, sizeof(size), 0);
  size = g_sizes[size % N_g_sizes];
  dump_heap_state();                    // DumpHex(main_arena) + DumpHex(g_tcache)
  printf("malloc(%p) = ? \n> ", size);
  ... // "solution\n{hex}" -> malloc(size); if (guess != it) exit(-1);
      // "readQ\n{hex}"    -> printf("Q @ %p = %p\n", where, *where);
}
system("cat /flag");

Core insight. glibc 2.31 has no safe-linking (that mitigation landed in glibc 2.32). Therefore every fd/bk pointer stored in the tcache and the fastbins is a raw heap address, not ptr ^ (chunk_addr >> 12). Because the program dumps the entire struct malloc_state and the entire tcache_perthread_struct before every question, the complete allocator state is disclosed. That makes each malloc outcome fully deterministic and simulatable — no memory corruption is needed at all. The task reduces to faithfully reimplementing the _int_malloc allocation priority from the dumped bytes. The readQ arbitrary read is available for walking on-heap chunk metadata (fd/bk/size) but, in practice, the arena + tcache dumps alone were enough for all 42 rounds. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

glibc 2.31 allocation priority (as reimplemented)

Request-to-chunk size: nb = (req + 8 + 15) & ~15, minimum 0x20. tcache index: tidx = (nb - 0x20) / 0x10.

1. tcache hit — if tcache->counts[tidx] > 0, return tcache->entries[tidx] (the raw head pointer). This covered ~41 of 42 rounds.
2. fastbin — for fastbin-range chunk sizes, fidx = (nb >> 4) - 2 (bins 0..9); if fastbinsY[fidx] != 0 return head + 0x10.
3. smallbin — sidx = nb >> 4; take the last chunk victim = bin->bk and return victim + 0x10. Exercised exactly once (challenge 31, chunk size 0xa0 after that tcache bin was exhausted).
4. unsorted-bin loop then top-chunk split — implemented defensively (using readQ to walk chunk headers), but never triggered. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Key struct malloc_state offsets (glibc 2.31, x86-64)

bin i: fd = bins[(i-1)*2], bk = bins[(i-1)*2 + 1]; bin 1 = unsorted, 2..63 smallbins, 64..126 largebins; bin_at(base,i) = base + 0x70 + ((i-1)*2)*8 - 0x10.

tcache_perthread_struct: uint16_t counts[64] (128 bytes) then void* entries[64] (512 bytes), total 640 (0x280). ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Solution

Parse the two hexdumps each round, run the malloc simulation, and answer with solution\n{hex(predicted_ptr)}. Essential logic (trimmed from solve.py):

 python read-only • copy allowed Copy
#!/usr/bin/env python3
import re
from pwn import *

HOST, PORT = "109.233.56.90", 11754
TCACHE_MAX_BINS, TCACHE_FILL = 64, 7
MINSIZE, ALIGN = 0x20, 16
MAX_FAST_SIZE, MIN_LARGE_SIZE = 0x80, 0x400

OFF_HAVE_FAST, OFF_FASTBINS = 0x08, 0x10   # fastbinsY[10]
OFF_TOP, OFF_LASTREM, OFF_BINS = 0x60, 0x68, 0x70   # bins[254]

def req2chunk(req):                        # request size -> chunk size nb
    x = (req + 8 + (ALIGN - 1)) & ~(ALIGN - 1)
    return x if x >= MINSIZE else MINSIZE
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def csize2tidx(cs):    return (cs - MINSIZE) // ALIGN
def fastbin_index(cs): return (cs >> 4) - 2           # bins 0..9
def smallbin_index(cs): return cs >> 4                # SMALLBIN_WIDTH = 16

def parse_hexdump(lines):                  # "AA BB CC ... | ascii" -> bytes
    out = bytearray()
    for ln in lines:
        for t in ln.split('|')[0].split():
            if len(t) == 2 and all(c in '0123456789abcdefABCDEF' for c in t):
                out.append(int(t, 16))
            else:
                break
    return bytes(out)
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def parse_tcache(t):
    counts  = [u16(t[i*2:i*2+2]) for i in range(TCACHE_MAX_BINS)]
    eoff    = TCACHE_MAX_BINS * 2
    entries = [u64(t[eoff+i*8:eoff+i*8+8]) for i in range(TCACHE_MAX_BINS)]
    return counts, entries

def parse_arena(a):
    return {
        'fastbins': [u64(a[OFF_FASTBINS+i*8:OFF_FASTBINS+i*8+8]) for i in range(10)],
        'top':      u64(a[OFF_TOP:OFF_TOP+8]),
        'bins':     [u64(a[OFF_BINS+i*8:OFF_BINS+i*8+8]) for i in range(254)],
    }

def bin_at(base, i):                       # address of bin head sentinel (as a chunk ptr)
    return base + OFF_BINS + ((i-1)*2)*8 - 0x10
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def predict(req, arena_base, arena_raw, tcache_raw):
    counts, entries = parse_tcache(tcache_raw)
    A  = parse_arena(arena_raw)
    cs = req2chunk(req)
    tidx = csize2tidx(cs)

    # 1) tcache head
    if 0 <= tidx < TCACHE_MAX_BINS and counts[tidx] > 0:
        return entries[tidx]

    # 2) fastbin (chunk sizes 0x20..0x90 -> idx 0..9)
    if cs <= MAX_FAST_SIZE + 0x10:
        fidx = fastbin_index(cs)
        if 0 <= fidx < 10 and A['fastbins'][fidx]:
            return A['fastbins'][fidx] + 0x10       # user ptr = head_chunk + 0x10
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

    # 3) smallbin -> take last chunk (bin->bk)
    if cs < MIN_LARGE_SIZE:
        sidx = smallbin_index(cs)
        fd = A['bins'][(sidx-1)*2]
        if fd and fd != bin_at(arena_base, sidx):
            bk = A['bins'][(sidx-1)*2 + 1]          # victim = last(bin) = bin->bk
            return bk + 0x10

    # 4) unsorted-bin loop / top split (walk heap via readQ) -- never needed here
    return A['top'] + 0x10

def read_block(io, marker):                # returns (base_addr, bytes)
    line = io.recvline().decode(errors='replace')
    while marker not in line:
        line = io.recvline().decode(errors='replace')
    m = re.search(r'at (0x[0-9a-fA-F]+) of (0x[0-9a-fA-F]+) bytes', line)
    base, size = int(m.group(1), 16), int(m.group(2), 16)
    nlines = (size + 15) // 16
    return base, parse_hexdump([io.recvline().decode(errors='replace') for _ in range(nlines)])
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def main():
    io = remote(HOST, PORT)
    io.recvuntil(b"challenges for you")
    for chal in range(42):
        io.recvuntil(b"challenge ")
        io.recvline()
        arena_base, arena  = read_block(io, "main_arena")
        _,          tcache = read_block(io, "g_tcache")
        line = io.recvuntil(b"= ? ").decode(errors='replace')
        req = int(re.search(r'malloc\((0x[0-9a-fA-F]+)\)', line).group(1), 16)
        io.recvuntil(b"> ")

        answer = predict(req, arena_base, arena, tcache)
        io.sendline(b"solution")
        io.sendline(hex(answer).encode())
        res = io.recvline().decode(errors='replace')
        if "nope" in res:
            log.failure("WRONG at challenge %d: %s", chal, res.strip())
            print(io.recvall(timeout=3).decode(errors='replace')); return
    print(io.recvall(timeout=5).decode(errors='replace'))   # <- cat /flag
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

if __name__ == "__main__":
    main()

How it went

• First run used only the tcache-head strategy. It passed challenges 0..14, then stopped at challenge 15 when a tcache bin (chunk size 0x100) was fully exhausted (all 7 consumed) — proving the fallback path was needed.
• After adding the fastbin + smallbin branches, the second full run passed all 42 rounds and printed the flag. The smallbin branch fired at challenge 31 (chunk size 0xa0). ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍