reversefreemedium

Königsberg Delivery Problem

gpn24

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.

$ ls tags/ techniques/
reversecfg_mazejump_tableeulerian_pathgraph_coverscanf_formatelf_piekitctfgpnctf
control_flow_graph_reversingjump_table_extractioncovering_walkbfs_nearest_unvisitedscanf_format_string_analysisstatic_disassembly_parsingdocker_dynamic_verification

$ cat /etc/rate-limit

Rate limit reached (20 reads/hour per IP). Showing preview only — full content returns at the next hour roll-over.

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;"

...

$ grep --similar

Similar writeups