Königsberg Delivery Problem

Platform: gpn24 | Category: Reversing | Type: Challenge | Difficulty: Medium | OS: Linux | Author: XESXOR | Date: 2024-06-01 | Status: Solved Techniques: bfs_nearest_unvisited, control_flow_graph_reversing, covering_walk, docker_dynamic_verification, jump_table_extraction, scanf_format_string_analysis, static_disassembly_parsing

Summary

Task: reverse a 250-node control-flow-graph maze ELF (cartographer) where 250 signed-decimal inputs (%hhd; format) act as edge selectors driving a single walk through a jump-table graph. Solution: extract the graph from .rodata jump tables, then build a covering walk (greedy BFS to nearest unvisited node) that enters all 250 nodes at least once so check_instance opens /flag.

Königsberg Delivery Problem — GPN CTF 2024

Description

Euler the owl owls in Königsberg when he gets totally hungry. Sadly for Euler the owl, the Königsberg internal food delivery apps have only one very lazy driver that does not want to make multiple trips. Can you (Euler the night owl) get his pizza? Or are you willing to deliver it yourself?

We are given koenigsberg-delivery-problem.tar.gz containing one ELF64 PIE executable named cartographer (not stripped). The remote service prints /flag only when our input satisfies an internal gate.

Semantic clues (high priority for this category):

• "Euler / Königsberg" → Eulerian path / Seven Bridges of Königsberg → graph traversal.
• "one very lazy driver that does not want to make multiple trips" → a SINGLE walk covering the whole graph.
• The binary's main worker function is literally named cfg (control flow graph).

Analysis

Recon

$ file cartographer
ELF 64-bit LSB pie executable, x86-64, dynamically linked, not stripped, GLIBC 2.34

Key symbols: main (0x40f0), cfg (0x1190, a huge function), check_instance (0x5520). Strings include /flag, Congratulations! Here is your flag: %s, Error opening flag file, Not quite, try again!. So the binary reads /flag server-side and prints it only on success — the flag is not derived from the input; the input only satisfies a gate.

The binary would not run natively on macOS; it was executed/verified inside Docker ubuntu:24.04 --platform linux/amd64.

Reversing main()

main issues 250 successive scanf calls, each reading one value into a stack buffer (rbx = rsp+6, bytes rsp+6 .. rsp+0xff), then calls cfg(buffer).

The decisive detail is the format string in .data:

"%hhd;"

Each token is a signed decimal number followed by a literal ;, NOT a raw byte and NOT %c. The input is therefore 250 decimal numbers separated by ;:

0;0;0;2;3;...;127;

An initial attempt feeding raw bytes failed with "Not quite, try again!". Switching to the %hhd; decimal format was the single fix that made it work.

Reversing cfg() — the 250-node CFG maze

cfg(rdi = input buffer):

• A local 0x108 buffer at rsp is zeroed via xmm stores. Its first 250 bytes (rsp+0 .. rsp+0xf9) are per-node visit COUNTERS, one byte each.
• rcx is the walk index into the input, starting at 0.
• There are 250 node blocks (from 0x1210, 0x1230, … up to ~0x40b0). Each node block does:

 asm read-only • copy allowed Copy
incb   <off>(%rsp)                 ; increment THIS node's counter on ENTRY
movzbl (%rdi,%rcx),%edx            ; read next input value
cmpq   $MAX,%rdx ; ja 0x40d4       ; per-node maximum; value > MAX => terminate
incq   %rcx
leaq   <table>(%rip),%rsi
movslq (%rsi,%rdx,4),%rdx          ; int32 offset from jump table indexed by value
addq   %rsi,%rdx
jmp    *%rdx                       ; jump to next node

• Each node's jump table maps value c (0..MAX) to a target node. Targets are monotonic increasing and distinct, i.e. the value is the RANK of the chosen outgoing neighbor (an edge selector), not an ASCII character.
• Terminal block 0x40d4: mov rsp,rdi ; mov $0xfa(=250),esi ; call check_instance.

The counter is incremented on entry, before the bounds check, so a node is counted as visited even on the transition that terminates the walk.

Reversing check_instance(rdi=counters, esi=250)

• Loops i = 0..249; cl starts as 1 and becomes 0 (sticky) if any counter byte == 0.
• If all 250 counters are nonzero (cl == 1): open("/flag"), read 0x64 bytes, printf("Congratulations! Here is your flag: %s").
• Otherwise: puts("Not quite, try again!") and exit.

So the single walk encoded by the input must enter every one of the 250 nodes at least once — the Königsberg/Euler theme: deliver to every node in ONE trip (one lazy driver). Note: counters are single bytes, so visiting a node 256 times wraps to 0 — prefer a low-revisit covering walk.

Solution

Graph extraction

The whole binary is an obfuscated directed graph; extract it from .rodata rather than reading by hand.

1. Disassemble with objdump, parse all 250 node blocks via regex to recover for each node: counter index (0..249), MAX, and jump-table base VMA.
2. For this PIE the .rodata file offset equals its VMA (0x6000), so jump tables are read directly from the file.
3. For each node and each value c in 0..MAX:
   • entry = int32 at (table_base + 4*c)
   • target_vaddr = table_base + entry
   • map target_vaddr to its node index.

Result: a clean 250-node directed graph; every edge resolves to a valid node (no dangling targets), no explicit TERM entries in the tables (termination only via value > MAX). Start node = node 0 (first block, MAX=95). The graph is strongly connected.

Finding a covering walk

Greedy strategy: from the current node, BFS to the nearest not-yet-visited node, append the edge-value sequence, repeat until all 250 nodes are visited. This yields a 249-transition walk entering all 250 nodes exactly once (max visit count = 1, no byte-counter wraparound). Append a terminating value (127, which exceeds every node's MAX; max MAX observed = 120) so the program reaches check_instance.

 python read-only • copy allowed Copy
#!/usr/bin/env python3
# Conceptual solver: extract the CFG-maze graph and build a covering walk.
import re, struct, subprocess
from collections import deque

ELF = "cartographer"
RODATA_VMA = 0x6000          # for this PIE, file offset == VMA for .rodata
data = open(ELF, "rb").read()

# 1) Disassemble and parse each node block.
dis = subprocess.check_output(["objdump", "-d", "-M", "intel", ELF]).decode()

# Each node: incb off(rsp) ; ... ; cmp rdx,MAX ; lea rsi,[rip+table] ; jmp *rdx
# Parse (block_vaddr -> counter_index, MAX, table_vaddr). (regex omitted for brevity)
# nodes = { node_vaddr: {"idx": counter_index, "max": MAX, "table": table_vaddr} }
nodes = parse_node_blocks(dis)            # returns dict as described above

# Map every node start VMA to a sequential node index 0..249
vaddr_to_node = {}
for n, va in enumerate(sorted(nodes)):
    vaddr_to_node[va] = n

# 2) Build adjacency: for value c in 0..MAX, resolve target node.
#    adj[node][c] = target_node   (value c is the edge selector / neighbor rank)
adj = {}
for va, info in nodes.items():
    src = vaddr_to_node[va]
    adj[src] = {}
    tbl = info["table"]
    for c in range(info["max"] + 1):
        off = tbl - RODATA_VMA + 4 * c
        entry = struct.unpack_from("<i", data, off)[0]
        target_vaddr = tbl + entry
        adj[src][c] = vaddr_to_node[target_vaddr]

START = 0

# 3) Covering walk: repeatedly BFS to the nearest unvisited node.
def bfs_path(src, visited):
    # returns (target_node, [edge_values...]) reaching nearest unvisited node
    q = deque([(src, [])])
    seen = {src}
    while q:
        node, path = q.popleft()
        for c, tgt in adj[node].items():
            if tgt in seen:
                continue
            seen.add(tgt)
            np = path + [c]
            if tgt not in visited:
                return tgt, np
            q.append((tgt, np))
    return None, None

visited = {START}
cur = START
walk = []                     # sequence of edge-selector values
while len(visited) < 250:
    tgt, path = bfs_path(cur, visited)
    walk += path
    for c in path:
        cur = adj[cur][c]
        visited.add(cur)

walk.append(127)              # value > every node MAX => terminate -> check_instance

# 4) Format as 250 "%hhd;" tokens.
assert len(walk) <= 250
walk += [127] * (250 - len(walk))   # pad with terminators (harmless after stop)
payload = "".join(f"{v};" for v in walk)
open("flag_input.txt", "w").write(payload)
print(payload)

Verification and exploitation

Verified locally in Docker (ubuntu:24.04, with a test /flag): the binary printed Congratulations! Here is your flag: <test flag>.

Against the remote service:

 bash read-only • copy allowed Copy
cat flag_input.txt | ncat --ssl boiled-mozzarella-sticks-crusted-with-charred-b-arnaise-9fgh.gpn24.ctf.kitctf.de 443

Output:

Congratulations! Here is your flag: GPNCTF{REDACTED}