Starless C — LA CTF 2025 Reverse Engineering Writeup

Category: Reverse Engineering Difficulty: Medium Points: 211 Solves: 72 Flag: lactf{starless_c_more_like_starless_0xcc} Solved by: Smothy @ 0xN1umb

"Three doors. A bee. A key. A flag. I chose all of them — 145 times."

Challenge Description

The son of the fortune-teller stands before three doors. A bee. A key. A flag.

nc chall.lac.tf 32223

We're given a single binary starless_c and a netcat endpoint. The name is a reference to "Starless" by King Crimson — prog rock and CTFs, the perfect combo.

TL;DR

A hand-crafted ELF binary implements a virtual maze using 23 memory-mapped pages as rooms. Navigate with wasd, where passing through "NOP gates" closes them behind you and opens the next one ahead. Press f to trigger a NOP-sled chain through 5 specific rooms to reach the flag reader. BFS over ~500k states finds the 145-move solution. ELF segments go brrr.

Initial Recon

First impressions of the binary:

• Statically linked, no section headers — fully custom ELF
• No protections at all — no PIE, no canary, no RELRO, executable stack, RWX segments
• Base address 0x13370000 — leet speak: 1337. Author is vibing.
• 58 program headers — way more than any normal binary

Running it prints a cryptic message about fortune-tellers and flags, then reads input. Wrong input = SIGSEGV → error message → exit. The SIGSEGV handler is at 0x13370103.

The strace output reveals the binary reads 1 byte at a time from stdin. Each byte is a navigation command.

Step 1: Understanding the ELF Layout

Parsing all 58 program headers reveals 25 segments with actual code:

The room pages are arranged in a grid where:

• Moving right (d) = +0x1000 in virtual address space
• Moving down (s) = +0x8000 in virtual address space
• Moving left (a) = -0x1000
• Moving up (w) = -0x8000

Unmapped addresses between rooms are intentional — if you try to move to a non-existent room, the CPU fetches code from unmapped memory → SIGSEGV → game over.

Step 2: Disassembling Room Code

Each 0x1000-byte room page has a consistent structure:

Offset 0x000 — The Gate (4 bytes):

• 90 90 90 90 = NOP NOP NOP NOP → OPEN (passable in f-chain)
• 31 c0 88 00 = xor eax, eax; mov [rax], al → CLOSED (NULL deref crash)

Offset 0x004 — Chain Jump (5 bytes):

• e9 XX XX XX XX — hardcoded jump to the next room in the f-chain

Offset 0x00C — Navigation Code:

read(0, rsp, 1)     ; read 1 byte
cmp al, 0x0a        ; newline → retry
cmp al, 'w'         ; up
cmp al, 's'         ; down
cmp al, 'a'         ; left
cmp al, 'd'         ; right
cmp al, 'f'         ; flag chain trigger
; anything else → xor eax,eax; mov [rax],al → CRASH

The gate logic for each direction:

1. Read 4 bytes at target room's offset 0
2. If gate == 0x90909090 (open):
   • Close the gate (write crash code to target room)
   • Open the gate TWO rooms further in the same direction
3. Jump to target room's navigation code (always, regardless of gate state)

For the homies who haven't touched self-modifying code: the rooms literally rewrite each other's code at runtime. Passing through an open gate closes it behind you and opens the next one ahead. Like dominos.

Step 3: Mapping the Maze

The 23 rooms form this grid (gap at position (2,3) — unmapped):

S = Start, O = Initially OPEN gate, ╳ = Unmapped (wall)

Five gates are initially open: (0,2), (1,2), (3,2), (4,2), (3,3).

Step 4: The F-Chain — Path to the Flag

The f key is special — it always jumps to 0x6767A000 (room (1,0) at offset 0), regardless of which room you're in. Each room's f instruction has a different relative offset that all resolve to the same absolute target.

If room (1,0)'s gate is open (NOPs), execution slides through to offset 4, which is a hardcoded jump to the next room. This chains through 5 rooms:

Each arrow represents: NOP NOP NOP NOP → jmp next_room_offset_0

The last room (1,3) has a special jump at offset 4: e9 f7 6f 9d da which resolves to 0x42069000 — the flag reader page that opens and prints flag.txt.

ALL FIVE gates must be 0x90909090 simultaneously when f is pressed.

Step 5: Gate Shuffling — The Real Puzzle

Here's the core puzzle. We need to transform the gate state:

Key constraints:

• Gate count is conserved — each pass closes one gate and opens another (5 → 5)
• Open target must be mapped — writing NOP to an unmapped address = SIGSEGV = death
• Movement is free — you can always move to mapped rooms regardless of gate state
• Direction matters — gates shift along rows (left/right) or columns (up/down)
• The gap at (2,3) blocks several lateral gate movements

This is a sliding puzzle implemented in x86 memory pages. Wild.

Step 6: BFS Solver

Manual solving is impractical — we need to explore the state space. Each state is (player_position, frozenset_of_open_gates).

from collections import deque

# State: (position, frozenset of 5 open gates)
# BFS guarantees shortest path

positions = { ... }  # 23 mapped rooms
initial_open = frozenset({(0,2), (1,2), (3,2), (4,2), (3,3)})
target_gates = frozenset({(1,0), (1,1), (1,2), (0,3), (1,3)})

queue = deque([(((0,0), initial_open), "")])
visited = set()

while queue:
    (pos, gates), path = queue.popleft()

    if target_gates.issubset(gates):
        print(f"SOLUTION: {path}f")  # append 'f' to trigger chain
        break

    for direction in 'wasd':
        nx, ny = pos[0]+dx, pos[1]+dy
        if (nx,ny) not in positions: continue  # unmapped = crash

        new_gates = gates
        if (nx,ny) in gates:  # passing through open gate
            next_pos = (nx+dx, ny+dy)
            if next_pos not in positions: continue  # open-target unmapped = crash
            new_gates = (gates - {(nx,ny)}) | {next_pos}

        new_state = ((nx,ny), new_gates)
        if new_state not in visited:
            visited.add(new_state)
            queue.append((new_state, path + direction))

~500,000 states explored → 145-character solution found:

The Flag

lactf{starless_c_more_like_starless_0xcc}

The flag is a pun: "Starless C" → "Starless 0xCC". Every room page was padded with 0xCC bytes (INT3 / breakpoint opcode). No stars — just breakpoints. Beautiful.

The Solve Script

"""
Starless C — LA CTF 2025 Reverse Engineering
Solver by Smothy @ 0xN1umb

Custom ELF maze with self-modifying gate pages.
BFS over (position, gate_state) to find path that opens
all 5 f-chain gates simultaneously.
"""

import struct
from collections import deque
from pwn import *

with open('starless_c', 'rb') as f:
    data = f.read()

# Parse ELF segments
segments = []
for i in range(58):
    off = 64 + i * 56
    p_offset = struct.unpack_from('<Q', data, off + 8)[0]
    p_vaddr = struct.unpack_from('<Q', data, off + 16)[0]
    p_filesz = struct.unpack_from('<Q', data, off + 32)[0]
    if p_filesz > 0:
        segments.append((p_vaddr, p_offset, p_filesz))

def vaddr_to_offset(va):
    for vaddr, offset, filesz in segments:
        if vaddr <= va < vaddr + filesz:
            return offset + (va - vaddr)
    return None

base = 0x67679000
room_addrs = set(v for v, _, fs in segments if 0x67670000 <= v <= 0x676A0000 and fs > 0)

# Map to grid coordinates
positions = set()
for addr in room_addrs:
    diff = addr - base
    x = (diff % 0x8000) // 0x1000
    y = diff // 0x8000
    positions.add((x, y))

# Read initial gate states
initial_open = frozenset()
for x, y in positions:
    addr = base + y * 0x8000 + x * 0x1000
    foff = vaddr_to_offset(addr)
    gate_val = struct.unpack_from('<I', data, foff)[0]
    if gate_val == 0x90909090:
        initial_open = initial_open | {(x, y)}

target_gates = frozenset({(1,0), (1,1), (1,2), (0,3), (1,3)})

# BFS
dirs = {'w': (0,-1), 's': (0,1), 'a': (-1,0), 'd': (1,0)}
start = ((0,0), initial_open)
queue = deque([(start, "")])
visited = {start}

while queue:
    (pos, gates), path = queue.popleft()

    if target_gates.issubset(gates):
        solution = path + "f"
        break

    for dname, (dx, dy) in dirs.items():
        nx, ny = pos[0]+dx, pos[1]+dy
        if (nx, ny) not in positions:
            continue

        new_gates = gates
        if (nx, ny) in gates:
            ox, oy = nx+dx, ny+dy
            if (ox, oy) not in positions:
                continue
            new_gates = (gates - {(nx,ny)}) | {(ox,oy)}

        state = ((nx,ny), new_gates)
        if state not in visited:
            visited.add(state)
            queue.append((state, path + dname))

print(f"Solution ({len(solution)} moves): {solution}")

# Send to remote
r = remote('chall.lac.tf', 32223)
r.send(solution.encode())
r.recvuntil(b'lactf{')
flag = b'lactf{' + r.recvuntil(b'}')
print(flag.decode())

The Graveyard of Failed Attempts

1. "f goes to the right neighbor" — Spent way too long thinking f jumped to page_base + 0x1000. It actually always resolves to 0x6767A000 regardless of which room you're in. Each room's f instruction has a uniquely computed relative offset that cancels out to the same absolute address. Sneaky.

2. Arithmetic error on the chain — Initially calculated room (0,3)'s chain jump as going to 0x676A1000 (unmapped). Thought the chain was broken. Re-did the hex addition carefully: 0x67691009 + 0x0FF7 = 0x67692000 (room (1,3)). That carry bit almost cost me the solve.

3. Wrong simulation — First simulation assumed f goes to pos + 0x1000, got a false "SUCCESS" result, then the binary still crashed. Had to re-derive the f-target from scratch.

4. Trying to solve by hand — Attempted manual gate shuffling. After 30 minutes of "close this, open that, wait now THAT one's closed", gave up and wrote the BFS. Should have started there.

Key Takeaways

1. Custom ELF binaries can use program headers creatively — 58 LOAD segments as maze rooms is genuinely clever
2. Self-modifying code through RWE segments enables runtime gate mechanics — each room rewrites other rooms' code
3. Gate puzzles conserve count — closing one always opens another. It's a sliding puzzle in virtual memory.
4. BFS is your friend for state-space exploration — ~500k states is trivial for a modern CPU
5. Always double-check hex arithmetic — one wrong carry bit can send you down a multi-hour rabbit hole
6. The flag starless_0xcc is a perfect pun: 0xCC (INT3) is the padding byte in every room page. No stars, just breakpoints.

Tools Used

• Python 3 + struct (ELF parsing)
• objdump (disassembly)
• strace (syscall tracing)
• BFS solver (custom)
• pwntools (remote connection)
• Way too much caffeine

Writeup by Smothy from 0xN1umb team. "58 program headers walk into a bar. The bartender says 'we don't serve your type'. They SIGSEGV." GG.