Maze of Power

Last weekend I played the Cyber Apocalypse CTF with VUBar. More than 12,000 players signed up for this CTF and it featured 67 challenges across 8 categories. The difficulty level ranged from very easy to insane. During this CTF, I was the first person that solved the insane reversing challenge MazeOfPower. This writeup explains how I solved it.

If you would like to try this challenge yourself before reading the writeup, you can download the challenge here. Note that it is easy to find the fake flag in the binary, but that is not the goal. The challenge was hosted on a server during the CTF, so the goal is to write a script that sends an input to the program that makes it print the flag.

Let's dive into the challenge.

Initial Analysis
The Naive Approach
Analyzing the Binary
Implementing the Solution
Mitigation
Summary

Initial Analysis

When we execute the program locally, we are first confrontend with a proof of work:

$ ./main
proof of work: curl -sSfL https://pwn.red/pow | sh -s s.AAATiA==.eiuw0WPt53wB7zHQJLbluQ==
solution:

A proof of work is often used in CTF challenges to prevent brute force attacks, because the proof of work takes some time to solve. The solution can easily be calculated by running the given command:

$ curl -sSfL https://pwn.red/pow | sh -s s.AAATiA==.eiuw0WPt53wB7zHQJLbluQ==
s.cU1jTeFBgLO1CFUMoJxZmRhxght5TqY48BG0o9HNDiucVnAmPsgT0h8cpJ1A1djpfxKNc75JyPbWGjihP7QyMusclM0IrOuXW/8oCIXRaUeQM7WAE/NY1WMHp+H5ns/PQsYLbZnXnV52pXQCAKlA2gpOobYOKW6NXZHWXs9gVjpHH0Fryb78/vG4IFZp+krsPWh+ZpVvXk/uI7pkm/afAA==

After entering the solution we get the following prompt:

Can you solve my maze within 20 seconds?
Controls: q/k/j/h/l

This prompt is followed by a lot of whitespace, with SS at the start and EE at the end. If we increase the size of our terminal window, we can see that the SS appears at the top left and the EE appears at the bottom right.

By pressing the keys that are mentioned in the prompt, we figure out that q terminates the program, and the k, j, h and l keys can be used to move a player up, down, left and right respectively. The player starts at SS and is marked by ::. However, there seem to be many invisible walls. Looks like we have to solve an invisible maze.

The Naive Approach

It is not that difficult to solve an invisible maze. We simply try to move the player in all possible directions. If the player does not move after pressing a key, we know that there is a wall. Otherwise, we know that there is a path. If we hit a dead end, we go back and try a different path. By keeping track of the steps that we have taken we can make sure that we do not visit the same path twice. Eventually, the player reaches the end of the maze (EE). This algorithm is similar to performing a depth-first search.

Unfortunately, this approach turned out to be too slow. We never reached the end of the maze in 20 seconds. We had to come up with a better solution.

Analyzing the Binary

The main problem is that the maze is invisible. If we can predict the layout of the maze, we can easily calculate a path from start to end. In order to figure out how the maze is generated, I opened the program with IDA.

The program seems to be written in Go, which can be a pain to reverse engineer. Luckily, all function names are available, so we can easily jump to the main.main function. IDA's decompiler often struggles with languages that are different from C or C++, but in this case it is still quite helpful.

For example, there is a main.printFinished function that takes a duration argument and reads the flag if it is less than 20 billion (measured in nanoseconds). This function is called when the end of the maze is reached.

if ( duration / 1000000000 <= 20 )
{
  v5 = "./flag.txt";
  v6 = 10LL;
  os_ReadFile(*(string *)(&v6 - 1));
  if ( a4 )
    v6 = 14LL;
  v10 = v6;
  if ( a4 )
    v7 = (uint8 *)"HTB{f4k3_fl4g}";
  v11 = v7;
  for ( i = 0LL; i < 5; i = v9 + 1 )
  {
    v9 = i;
    *(_OWORD *)&a.array = v4;
    v14 = runtime_slicebytetostring(0LL, v7, v6);
    v14.str = (uint8 *)runtime_convTstring(v14);
    a.array = (interface_ *)&RTYPE_string_0;
    a.len = (int)v14.str;
    v14.len = (int)os_Stdout;
    v14.str = (uint8 *)&go_itab__ptr_os_File_comma_io_Writer;
    v15.str = (uint8 *)"Here is your flag: %s\n";
    v15.len = 22LL;
    v13.len = 1LL;
    v13.cap = 1LL;
    v13.array = (interface_ *)&a;
    fmt_Fprintf((io_Writer)v14, v15, v13);
    v7 = v11;
    v6 = v10;
  }
}

We can also see how the maze is configured in main.main:

maze.Height = 25LL;
maze.Width = 50LL;
maze.Start = (github_com_itchyny_maze_Point *)runtime_newobject((internal_abi_Type *)&RTYPE_maze_Point);
p_maze_Point = (maze_Point *)runtime_newobject((internal_abi_Type *)&RTYPE_maze_Point);
p_maze_Point->X = 24LL;
p_maze_Point->Y = 49LL;
maze.Goal = (github_com_itchyny_maze_Point *)p_maze_Point;
maze.Solved = 0;
maze.Started = 0;
maze.Finished = 0;
maze.Cursor = maze.Start;
github_com_itchyny_maze__ptr_Maze_Generate(&maze);
...
format.Wall.len = 2LL;
format.Wall.str = (uint8 *)"  ";
format.Path.len = 2LL;
format.Path.str = (uint8 *)"  ";
format.StartLeft.len = 2LL;
format.StartLeft.str = (uint8 *)"SS";
format.StartRight.len = 2LL;
format.StartRight.str = (uint8 *)"SS";
format.GoalLeft.len = 2LL;
format.GoalLeft.str = (uint8 *)"EE";
format.GoalRight.len = 2LL;
format.GoalRight.str = (uint8 *)"EE";
...
format.Cursor.len = 2LL;
format.Cursor.str = (uint8 *)"::";

Indeed, it looks like the start is marked by SS, the goal is marked by EE, and both walls and paths are marked with whitespace. This part of the code also reveals that the maze is generated with a public repository: https://github.com/itchyny/maze. By viewing maze.go, we find that the maze is generated based on the output of rand.Int:

// Next advances the maze path randomly and returns the new point
func (maze *Maze) Next(point *Point) *Point {
    neighbors := maze.Neighbors(point)
    if len(neighbors) == 0 {
        return nil
    }
    direction := neighbors[rand.Int()%len(neighbors)]
    maze.Directions[point.X][point.Y] |= direction
    next := point.Advance(direction)
    maze.Directions[next.X][next.Y] |= Opposite[direction]
    return next
}

// Generate the maze
func (maze *Maze) Generate() {
    point := maze.Start
    stack := []*Point{point}
    for len(stack) > 0 {
        for {
            point = maze.Next(point)
            if point == nil {
                break
            }
            stack = append(stack, point)
        }
        i := rand.Int() % ((len(stack) + 1) / 2)
        point = stack[i]
        stack = append(stack[:i], stack[i+1:]...)
    }
}

It is important to know that rand.Int is not cryptographically secure. The documentation on the math/rand package explains this:


Package rand implements pseudo-random number generators suitable for tasks such as simulation, but it should not be used for security-sensitive work. 

...

This package's outputs might be easily predictable regardless of how it's seeded. For random numbers suitable for security-sensitive work, see the crypto/rand package.

If we can predict the output of rand.Int we can reconstruct the maze that is generated by the program. In general, there are two ways to predict the output of an insecure RNG:

Observe a (potentially large) number of output values and use them reconstruct the internal state of the RNG. Once the state has been recovered it can be used to calculate future outputs.
Guess or predict the seed that was used to initialize the RNG and use that to initialize a new RNG that generates the same output.

The first approach is not possible in this challenge because we cannot observe any output values of the RNG. But the second approach turns out to be fruitful. Remember that we had to calculate a proof of work? Well, the seed that is used to initialize the RNG turns out to be the CRC-32 hash of the proof of work solution:

v26.loc = (time_Location *)bufio__ptr_Reader_ReadString(&b, 0xAu);
*(_QWORD *)&v23[9] = 10LL;
v53.len = 10LL;
v53.str = (uint8 *)v26.loc;
v57 = github_com_redpwn_pow__ptr_Challenge_Check(c, v53);
if ( !v57._r1.tab && v57._r0 )
{
  v54.str = (uint8 *)v26.loc;
  v54.len = *(_QWORD *)&v23[9];
  v58 = runtime_stringtoslicebyte(0LL, v54);
  LODWORD(v58.array) = hash_crc32_ChecksumIEEE(v58);
  math_rand_Seed(LODWORD(v58.array));

With this knowledge, it is easy to calculate the seed.

Implementing the Solution

We know that we can calculate the seed based on the proof of work and use that to predict the layout of the maze. We can use that to calculate a solution for the maze and guide the player through the shortest path.

Luckily for us, the maze repository comes with a tool that generates the maze for a given seed and can even calculate a solution for us. We compile the repository locally and invoke the tool as follows:

$ ./maze --seed <seed> --solution --width 50 --height 25

The output may looks as follows:

Now all that remains is writing a script that automatically connects to the server, solves the proof of work, predicts the path through the maze and guides the player to the end. The following script is the one that I used to solve the challenge:

from pwn import *
import binascii
import os
import subprocess

UP = "k"
DOWN = "j"
LEFT = "h"
RIGHT = "l"

X_MAP = {
    LEFT: -1,
    RIGHT: 1,
    DOWN: 0,
    UP: 0
}

Y_MAP = {
    LEFT: 0,
    RIGHT: 0,
    DOWN: 1,
    UP: -1
}

REVERSE = {
    LEFT: RIGHT,
    RIGHT: LEFT,
    UP: DOWN,
    DOWN: UP
}

# Establish a connection with the server
p = remote("94.237.59.132", 43416)

# Receive the proof of work command
line = p.recvline()
cmd = line[15:]

# Solve the proof of work and send it back to the server
response = subprocess.check_output(cmd, shell=True)
p.sendline(response)

# Calculate the seed and generate a solution for the maze
seed = binascii.crc32(response)
solution = subprocess.check_output([
    "./maze", "--seed", str(seed), "--solution",
    "--width", "50", "--height", "25"
])

# Print the solution to the console
print("---")
lines = [line.decode()[2:] for line in solution.splitlines()[1:-1]]
for line in lines:
    print(line)
print("---")

# Determine the key presses that are needed to guide the player through the maze
directions = []
x, y = 2, 1
while True:
    # To determine the next step, we look for a ':' in one the neighbor cells
    for direction in [LEFT, RIGHT, UP, DOWN]:
        # An additional check is needed to prevent the player from going backwards
        if directions and direction == REVERSE[directions[-1]]:
            continue
        check_x = x + X_MAP[direction] * 2
        check_y = y + Y_MAP[direction] * 1
        next_x = x + X_MAP[direction] * 4
        next_y = y + Y_MAP[direction] * 2
        try:
            if lines[check_y][check_x] == ":":
                directions.append(direction)
                x, y = next_x, next_y
                break
        except IndexError:
            pass # We don't want to fall off the map
    else:
        # When there are no more possible steps, we have reached the end of the maze
        break

# Send the key presses to the server
for direction in directions:
    p.recvuntil(b"Controls: q/k/j/h/l\n")
    p.sendline(direction.encode())

# Receive the flag!
p.interactive()

Mitigation

We could reconstruct the maze because it used an insecure random number generator. When security-sensitive information is at stake, it is important to use a cryptographically secure RNG.

Summary

The goal is to quickly solve an invisible maze.
We can predict the seed because it is the CRC-32 hash of our proof of work solution.
We use a public repository to reconstruct the maze with the predicted seed and calculate the the shortest path offline.
We automate this process with a script and run it against the server to obtain the flag.