vector-cache — UIUCTF 2026

Description

A recovery console has one token cached somewhere inside it. The verifier looks ordinary until the illegal instructions start firing.

A stripped x86-64 Linux PIE binary prompts token> and accepts a flag of the form uiuctf{<48 lowercase hex chars>}, printing accepted or rejected. Goal: recover the 48-hex token body.

Semantic clues

• "illegal instructions start firing" → the verifier is driven by SIGILL/ud2; the real control flow lives inside a signal handler, not in ordinary linear code.
• "vector-cache" / "one token cached somewhere inside it" → an embedded cached token blob and per-segment "vector-cache" data blobs are consulted by the VM.

Analysis

Front-end (main @ 0x1040)

• Prints vector-cache recovery console, reads the line with fgets (0x10e3), strips newline via strcspn (0x10fc), strlen (0x110d).
• Requires literal prefix uiuctf{, a } at index 55, total length 0x38, then hex-decodes the 48 hex chars into 24 raw bytes (0x111d..0x123b).
• Arms a SIGILL handler (sigaction) — handler pointer loaded at 0x106e (handler @ 0x2080), armed at 0x1091.

Three chained segments

The 24 bytes are verified through THREE chained "segments", each an illegal-instruction VM. Input mapping: seg0 → bytes[0:8], seg1 → [8:16], seg2 → [16:24].

The verifier FUNC @ 0x2620 is called as FUNC(rdi=out_buf, rsi=seg_idx, rdx=input_ptr, rcx=chaining_seed). It:

• seeds a PRNG from a per-segment seed table @ 0x7d00 (3 qwords/segment) plus the chaining seed rcx,
• builds a 256-byte S-box by Fisher–Yates at state+0x18,
• stores the VM-state pointer to .bss global @ 0xa030,
• then executes ud2 @ 0x2980 in a loop.

Each ud2 faults into the SIGILL handler @ 0x2080, which runs ONE VM round and advances the faulting RIP by +2 via ucontext (mcontext gregs REG_RIP at ucontext+0xa8).

Per VM round

The handler decrypts the next 16-byte chunk of that segment's 0x600-byte vector-cache blob (big blobs 0x3340..0x7540; low XOR-key blobs 0x3040/0x3140/0x3240) with a xorshift/rotr keystream, computes a 16-bit cx, and does cmp cx,[rsp+0x1c] (0x236c). Then a 7-way opcode dispatch (jump table @ 0x3020; entries {0x25e2,0x25b6,0x2594,0x255d,0x2536,0x2508,0x23da}) updates state.

Three critical insights

Insight #1 — the per-round cmp cx,target is a self-referential DECOY. The compared target is derived from the same input, so cx == target for every input; it never gates anything. Verified: flipping any input byte leaves all cx and all target values unchanged, yet the output bytes change.

Insight #2 — the real gate is an all-zero output accumulator. Every round ORs its output byte into an accumulator at state+0x128 via or [r15+0x128],rax (0x2409). So accumulator = OR of all 96 per-round output bytes. main's finaliser (0x1575..0x16c1) ORs into rbx: each segment's result[8:16] (the accumulator), each segment's err flag, each (count XOR 0x60), and a final xmm3 fold of segment outputs against the cached token @ 0x7bc0. ACCEPT iff rbx==0 (test rbx,rbx @ 0x16c1) → accepted (@0x7ee0), else rejected (@0x7ee9). Therefore ACCEPT ⇔ every one of the 96 output bytes is 0 in each segment (the err/count/token terms then also collapse to 0).

Output-byte formula (0x23e1..0x2406):

out_r = ( sbox[(r12_r + rbx_r) & 0xff] ^ ebp_r ^ edi_r ) & 0xff

where edi_r is INPUT-INDEPENDENT keystream and input enters ONLY through the S-box index (r12_r + rbx_r). The S-box and PRNG state are input-independent (proven because cx/target never move with input). Hence:

out_r == 0  ⇔  (r12_r + rbx_r) & 0xff == inv_sbox[ ebp_r ^ edi_r ]  (a fixed per-round target index)

Insight #3 — each segment is a low-arity CSP. Each round's output byte depends on AT MOST 3 of that segment's 8 input bytes (measured seg0 histogram: 15 rounds depend on 1 byte, 22 on 2, 59 on 3; max 3). So each segment reduces to a constraint satisfaction problem — 8 unknown bytes, 96 constraints, every constraint of arity ≤3 — solvable by memoized backtracking with forward-checking (solution unique per segment).

Segment chaining

• seg0: rcx = 0.
• seed1 = hash1850(input[0:8], seg0_result.low8, 0x13579bdf2468ace0); a fork+pipe splits an ordinary-looking front-end from a child that computes seg1 = FUNC(1, input, seed1) and pipes 24 bytes back.
• seed2 = hash1850(..., rol(seg1_result.low8,17) ^ seg0_result.low8, 0x0f1e2d3c4b5a6978); seg2 = FUNC(2, input, seed2).
• Solve order: seg0 → seed1 → seg1 → seed2 → seg2.

The 24 solved raw bytes, hex-encoded to 48 lowercase hex chars, form the flag body.

Solution

Emulation approach (static, no ptrace)

Host was macOS/Apple Silicon: the x86-64 Linux ELF cannot be natively ptraced (qemu-user/Rosetta cannot ptrace), so gdb dynamic analysis failed. The VM was emulated with Unicorn (+ pyelftools/capstone) by manually servicing SIGILL:

• catch UC_ERR_INSN_INVALID on ud2 (bytes 0f 0b),
• snapshot all GP regs + RSP + EFLAGS + XMM,
• run the handler on a dedicated signal stack — the key bug fix: the handler's rsp+0x10 scratch was overlapping the VM state that lives on the parent stack; putting the handler on its own stack fixed silent corruption,
• restore state and skip RIP += 2.

Solver

solve.py runs each segment as an arity-≤3 CSP with memoized backtracking + forward-checking, computing per-round target indices from the emulated (input-independent) S-box and keystream, chaining seeds between segments via the emulated hash1850.

#!/usr/bin/env python3
# Skeleton of the per-segment CSP solve (see solve.py / emu.py in TASK_DIR).
# For each segment we already have, from the Unicorn SIGILL-VM emulation:
#   sbox (input-independent 256-byte permutation)
#   inv_sbox
#   for each of the 96 rounds r: (deps_r, coeffs, ebp_r, edi_r)
# Constraint per round:  (r12_r + rbx_r) & 0xff == inv_sbox[ebp_r ^ edi_r]
# where (r12_r, rbx_r) are linear in the <=3 input bytes deps_r.

def solve_segment(rounds, deps):
    # rounds: list of (dep_indices<=3, eval_fn(inp8)->out_byte)
    # backtracking over 8 bytes with forward checking on satisfied constraints
    from functools import lru_cache
    inp = [None]*8
    order = order_by_constraint_coverage(rounds, deps)  # assign most-constrained first
    def ok_partial():
        for dep_idx, ev in rounds:
            if all(inp[i] is not None for i in dep_idx):
                if ev(inp) != 0:
                    return False
        return True
    def bt(pos):
        if pos == 8:
            return all(ev(inp) == 0 for _, ev in rounds)
        i = order[pos]
        for b in range(256):
            inp[i] = b
            if ok_partial() and bt(pos+1):
                return True
        inp[i] = None
        return False
    assert bt(0)
    return bytes(inp)

# Chain: seg0(seed=0) -> seed1=hash1850(...) -> seg1 -> seed2=hash1850(...) -> seg2
# Concatenate seg0||seg1||seg2 (24 bytes) and hex-encode for the flag body.

Verification

Ground truth used the REAL binary under Docker (plain Rosetta execution works; only ptrace/gdb does not):

printf 'uiuctf{<48-hex-body>}\n' | \
  docker run --rm -i --platform linux/amd64 -v "$PWD":/w -w /w ubuntu:22.04 ./vector-cache
# -> token> accepted