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

```C

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:

```python

import networkx as nx

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

transitions = {}

G = nx.DiGraph()

for node in nodes:

G.add_node(node.name)

for node in nodes:

for move in move_lookup.keys():

if node.end + move in dead_ends:

continue

if node.start == node.end == GOAL:

continue

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]]

print(movelist)

```

After a few seconds, the correct path pops out:

```

11224422442211112222443344224422222244334422444444331133443344222222443333442222444433113333443344334433111122112211221133113344443333111111334433333311111122112222224444222244221111333311113311113344443311333311334433333333443311333344444444224422112211112244442244334444221122224444334422444433334433333311221111333333442244334433113333111122111133333311111111222244334422442222442244222211331133113333111122111111333344224433331133111122222222221111333344333311331122112211112211111133443344444433111111112211112222442244

```

Inputing this on the server, gives us the flag.