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);
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:

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