Rating: 4.0

In this challenge, you're given a binary called `maze`, and a remote host/port. Disassembling it, we see a ton of dead/unreferenced code, and only 2 referenced functions. The main function does something like

sys_write(1, "Welcome to the maze!", 0x27);
sys_read(2, &move, 0x5DC);
if (walk(move) == 1)
// open flag.txt and otutput it

Our goal is then to make the walk function return a 1. Looking closer at the `walk` function, it checks if the input is a newline, and if not it subtracts `'0'` from it, and increments RDI to point to the next charater from the input. Then it jumps into a switch/case with the numbers 1, 2, 3 and 4. So our input should be one of those numbers. Inside the cases, it calculates an offset that is one of these mappings `{1: -5493, 2: -193, 3: 19, 4: 5319}`. Next it loads the current address into RAX, adds the offset to it, and then jumps there!

Looking at the code segments we can jump to, 3 of them are all `XOR EAX, EAX; RETN` and the last is an exact copy of our first `move`-function, just located at a different location. Turns out that there are over a thousand of these functions spread across the binary, where the `XOR EAX, EAX` functions represent dead ends in our jumping maze. Looking around for outliers, we find another function that does `mov eax, 1; RETN`, which is our goal. The plan then, is to jump from move-function to move-function around the binary, until we land at the goal "gadget".

We first tried to use instruction counts to do this, assuming that there would be a singular path surrounded with dead-ends, but after a few moves, a cycle must've appeared, because the program kept find the same moves over and over. Next, we considered a backtracking-approach, but that would require us to know if we had visited a certain location earlier or not. At that point, we may as well just solve this as a directed graph, and calculate the shortest path from the start to the goal.

The lazy solution to this, is to just copy the disassembly from IDA to a file, then parse through line by line, identifying move-functions and dead-ends. Then create nodes with `networkx` and find the shortest path. Here's the meat of the code, after parsing all the snippets as nodes. All the nodes have a name and start/end address, representing the points where someone can land, and what address it jumps from:

import networkx as nx

move_lookup = {-5493:"1", -193:"2", 19:"3", 5319:"4"}
transitions = {}

G = nx.DiGraph()
for node in nodes:

for node in nodes:
for move in move_lookup.keys():
if node.end + move in dead_ends:
if node.start == node.end == GOAL:
target = [e.name for e in nodes if e.start == (node.end+move)]
assert len(target) == 1
G.add_edge(node.name, target[0])
if node.name not in transitions:
transitions[node.name] = {}
transitions[node.name][target[0]] = move_lookup[move]

path = nx.shortest_path(G, source="START", target="GOAL")
movelist = ""
for i in range(len(path)-1):
movelist += transitions[path[i]][path[i+1]]

After a few seconds, the correct path pops out:

Inputing this on the server, gives us the flag.