Challenge: Königsberg Delivery Problem (binary: cartographer) · CTF: GPN CTF 2026 · Category: Reversing · Difficulty: Medium

Summary

cartographer is a 250-state automaton (compiled from LLVM IR with control-flow flattening) that reads 250 signed bytes as a “program”. The success check requires every state to be visited, so the input is a Hamiltonian path through the transition graph plus one halt symbol.

Solution

Step 1: Understand the binary

main reads exactly 250 values with scanf("%hhd;") into a buffer, then calls cfg(buf). cfg is a flattened state machine. Each state block is:

1
2
3
4
5
6
7
8

inc byte [rsp+N]            ; mark state N as visited
movzx edx, byte [rdi+rcx]   ; read next input symbol
cmp   rdx, MAX_N            ; per-state bound
ja    0x40d4               ; out-of-range  -> HALT (call check_instance)
inc   rcx
movsxd rdx, [table_N + rdx*4]
add   rdx, table_N
jmp   rdx                   ; goto next state's block

check_instance(buf, 250) (called at 0x40d4) opens /flag only if all 250 visited-counters are nonzero. So we start at state 0 (marked on entry), each valid symbol moves us to another state (marked on entry), and an out-of-range symbol ends the run. To touch all 250 states in 250 reads we need a Hamiltonian path (249 edges) followed by one halt symbol (e.g. 127, larger than every state’s bound). The challenge name and flag (“Euler”, “Königsberg”) are the graph-traversal hint.

Step 2: Extract the graph, find the path, fire at remote

The transition tables live in .rodata as (MAX+1) signed dword offsets per state. We parse them straight from the ELF, build the graph, find a Hamiltonian path from state 0 with a Warnsdorff-heuristic backtracking search, then send path-edges-symbols + 127 (250 bytes) to the service.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

#!/usr/bin/env python3
import struct, sys, random, subprocess, re

BIN  = "cartographer"
HOST = "butter-basted-tiramisu-wrapped-in-cured-soy-foam-ezzn.gpn24.ctf.kitctf.de"
PORT, N = 443, 250

data = open(BIN, "rb").read()
s32  = lambda va: struct.unpack("<i", data[va:va+4])[0]   # vaddr == file offset

# 1) Find every state block by signature: movzx edx,[rdi+rcx]; cmp rdx, imm8
SIG = bytes.fromhex("0fb6140f4883fa")
addr2state, blocks = {}, []
pos = data.find(SIG)
while pos != -1:
    maxsym = data[pos + len(SIG)]
    p = pos + len(SIG) + 1
    p += 6 if data[p:p+2] == b"\x0f\x87" else 2     # ja rel32 or ja rel8
    p += 3                                            # inc rcx
    if data[p:p+3] in (b"\x48\x8d\x35", b"\x48\x8d\x05"):  # lea rsi/rax, [rip+rel]
        table = p + 7 + struct.unpack("<i", data[p+3:p+7])[0]
    else:
        table = 0x6004                                # state 0 uses preloaded rax
    if   data[pos-3:pos]   == b"\xfe\x04\x24": state, start = 0, pos-3
    elif data[pos-4:pos-1] == b"\xfe\x44\x24": state, start = data[pos-1], pos-4
    else: state, start = struct.unpack("<i", data[pos-4:pos])[0], pos-7  # disp32
    addr2state[start] = state
    blocks.append((state, table, maxsym))
    pos = data.find(SIG, pos + 1)

# 2) Build transition graph and adjacency (one witnessing symbol per edge)
trans  = {st: [addr2state[t + s32(t + 4*s)] for s in range(m+1)]
          for st, t, m in blocks}
maxsym = {st: len(r)-1 for st, r in trans.items()}
adj    = [{} for _ in range(N)]
for u in range(N):
    for sym, v in enumerate(trans[u]):
        adj[u].setdefault(v, sym)
succ = [list(a) for a in adj]

# 3) Hamiltonian path from state 0 (Warnsdorff ordering + backtracking)
sys.setrecursionlimit(10000)
def ham(seed):
    random.seed(seed); vis = [False]*N; vis[0] = True; path = [0]; bud = [3_000_000]
    def dfs(u):
        if len(path) == N: return True
        bud[0] -= 1
        if bud[0] < 0: raise TimeoutError
        cand = sorted((v for v in succ[u] if not vis[v]),
                      key=lambda v: sum(not vis[w] for w in succ[v]))
        random.shuffle(cand)
        cand.sort(key=lambda v: sum(not vis[w] for w in succ[v]))
        for v in cand:
            vis[v] = True; path.append(v)
            if dfs(v): return True
            vis[v] = False; path.pop()
        return False
    try:    return path if dfs(0) else None
    except TimeoutError: return None
path = next(filter(None, (ham(s) for s in range(100))), None)
assert path and len(set(path)) == N

# 4) symbols: one per edge, then a halt symbol (out of range for last state)
syms = [adj[path[i]][path[i+1]] for i in range(N-1)] + [127]
assert 127 > maxsym[path[-1]]
payload = (";".join(map(str, syms)) + ";").encode()

# 5) send to remote (instance handshake is flaky -> retry)
cmd = ["openssl", "s_client", "-quiet", "-servername", HOST, "-connect", f"{HOST}:{PORT}"]
for _ in range(8):
    try:    out = subprocess.run(cmd, input=payload, capture_output=True, timeout=15).stdout
    except subprocess.TimeoutExpired: out = b""
    m = re.search(rb"GPNCTF\{[^}]*\}", out)
    if m:
        print(m.group().decode()); break

1
2

$ python3 solve_cartographer.py
GPNCTF{5Ay_eulER_THE_Ow1_0wL5_IN_Köni65B3rg_10_tImE5_fAst!}

Flag

1

GPNCTF{5Ay_eulER_THE_Ow1_0wL5_IN_Köni65B3rg_10_tImE5_fAst!}