read blog here:https://thesavageteddy.github.io/posts/what-a-maze-meant-defcon-2023-quals/
or below:
+++weight = 7tags = ["ctf", "writeup", "speedpwn"]categories = ["CTF Writeups"]publishDate = 1685376000 # 30/05/2023description = "A writeup for a speedpwn challenge in LiveCTF of DEFCON CTF Quals 2023" title_img = """{{< image src="https://ctftime.org/media/cache/94/e9/94e9dbfeeac979015ff6fc74b5151fd8.png" alt="" style="border-radius: 5px; height: auto; width: 3em; display: inline; vertical-align: middle; " >}}"""title = """what-a-maze-meant - DEFCON Quals 2023 Writeup"""cover = """defcon-quals-scoreboard-2023.png"""cover_alt = ""+++
# Table of Contents
[`Overview`](#overview) - a brief summary of the event
[`Writeup`](#challenge-overview) - writeup of the challenge
[`Conclusion`](#conclusion) - final closing thoughts
# Overview
I played DEFCON Quals 2023 with [`if this doesn't work we'll get more for next year`](https://ctftime.org/team/220769), a merger team with around 10 teams combined. Despite our best efforts, we placed `15th`, just short of the top 12 that qualified, but given that it was our first year, I think we did pretty well, and I guess we'll need to get more for next year!
In this post is a quick writeup of `what-a-maze-meant`, the first speedpwn challenge released in the LiveCTF section, where the quickest solves will earn the most points, so speed is key! It was a relatively easy challenge that together with some teamates, I solved pretty quickly. Enjoy!
## Challenge overview
We are given a binary, where the goal seems to be to complete the maze, by giving directions such as North, South, East and West. [Decompiling online](https://dogbolt.org/?id=fda734c4-0d96-48dc-9247-1cafa71dc8bd) we can dive into the code.
{{< code language="c" title="main()" id="1" expand="Show" collapse="Hide" isCollapsed="false" >}}int __cdecl main(int argc, const char **argv, const char **envp){  unsigned int v3; // eax  char v5; // [rsp+Bh] [rbp-3A5h] BYREF  int i; // [rsp+Ch] [rbp-3A4h]  int j; // [rsp+10h] [rbp-3A0h]  unsigned int v8; // [rsp+14h] [rbp-39Ch]  unsigned int v9; // [rsp+18h] [rbp-398h]  int v10; // [rsp+1Ch] [rbp-394h]  char v11[904]; // [rsp+20h] [rbp-390h] BYREF  unsigned __int64 v12; // [rsp+3A8h] [rbp-8h]  __int64 savedregs; // [rsp+3B0h] [rbp+0h] BYREF
  v12 = __readfsqword(0x28u);  setvbuf(stdin, 0LL, 2, 0LL);  setvbuf(stdout, 0LL, 2, 0LL);  v3 = time(0LL);  srand(v3);  for ( i = 0; i <= 29; ++i )  {    for ( j = 0; j <= 29; ++j )      *((_BYTE *)&savedregs + 30 * i + j - 912) = 35;  }  puts("Reticulating splines... ");  generate_maze((__int64)v11, 1, 1, 1);  puts("\n\nWelcome to the maze!");  v8 = 1;  v9 = 1;  v10 = 1;  while ( 1 )  {    if ( show_maze )      display_maze((__int64)v11, v8, v9);    printf("You are in room (%d, %d)\n", v8, v9);    if ( v10 )      randomDescription();    else      v10 = 1;    puts("Which would you like to do?");    if ( validwalk(*((_BYTE *)&savedregs + 30 * (int)(v8 - 1) + (int)v9 - 912)) )      printf("go (n)orth, ");    if ( validwalk(*((_BYTE *)&savedregs + 30 * (int)(v8 + 1) + (int)v9 - 912)) )      printf("go (s)outh, ");    if ( validwalk(*((_BYTE *)&savedregs + 30 * (int)v8 + (int)(v9 - 1) - 912)) )      printf("go (w)est, ");    if ( validwalk(*((_BYTE *)&savedregs + 30 * (int)v8 + (int)(v9 + 1) - 912)) )      printf("go (e)ast, ");    printf("or (q) end the torment");    printf(": ");    __isoc99_scanf(" %c", &v5;;    putchar(10);    switch ( v5 )    {      case 'a':        puts("You cast arcane eye and send your summoned magical eye above the maze.");        show_maze = 1;        v10 = 0;        break;      case 'e':        if ( validwalk(*((_BYTE *)&savedregs + 30 * (int)v8 + (int)(v9 + 1) - 912)) )          ++v9;        break;      case 'n':        if ( validwalk(*((_BYTE *)&savedregs + 30 * (int)(v8 - 1) + (int)v9 - 912)) )          --v8;        break;      case 'q':        exit(0);      case 's':        if ( validwalk(*((_BYTE *)&savedregs + 30 * (int)(v8 + 1) + (int)v9 - 912)) )          ++v8;        break;      case 'w':        if ( validwalk(*((_BYTE *)&savedregs + 30 * (int)v8 + (int)(v9 - 1) - 912)) )          --v9;        break;      default:        break;    }    if ( *((_BYTE *)&savedregs + 30 * (int)v8 + (int)v9 - 912) == 42 )    {      if ( rand() % 1213 == 1212 )      {        puts("You successfully exit the maze!");        winner();      }      puts("Just as you are about to exit, a displacer beast captures you. You die.");      exit(0);    }  }}{{< /code >}}
Running the provided binary and inputting `a`, we can see the maze layout:
{{< image src="./img/mazelayout.png" alt="" position="center" style="border-radius: 5px;" >}}
There are already a lot of scripts online to solve mazes, and since we want to solve this as fast as possible for the most points, we use ChatGPT to generate a script for us:
{{< code language="python" title="maze_solver.py" id="2" expand="Show" collapse="Hide" isCollapsed="false" >}}class MazeSolver:    def __init__(self, maze):        self.maze = maze        self.rows = len(maze)        self.cols = len(maze[0])        self.visited = [[False for _ in range(self.cols)] for _ in range(self.rows)]        self.directions = {'N': (-1, 0), 'S': (1, 0), 'W': (0, -1), 'E': (0, 1)}        self.path = []
    def solve(self, start_row, start_col):        if self._dfs(start_row, start_col):            return self._get_solution()        else:            return []
    def _dfs(self, row, col):        if not self._is_valid(row, col):            return False
        self.visited[row][col] = True        self.path.append((row, col))
        if self.maze[row][col] == '*':            return True
        for direction in self.directions.values():            next_row = row + direction[0]            next_col = col + direction[1]            if self._dfs(next_row, next_col):                return True
        self.path.pop()        return False
    def _is_valid(self, row, col):        if row < 0 or row >= self.rows or col < 0 or col >= self.cols:            return False        if self.maze[row][col] == '#' or self.visited[row][col]:            return False        return True
    def _get_solution(self):        solution = []        for i in range(1, len(self.path)):            prev_row, prev_col = self.path[i-1]            curr_row, curr_col = self.path[i]            if curr_row < prev_row:                solution.append('n')            elif curr_row > prev_row:                solution.append('s')            elif curr_col < prev_col:                solution.append('w')            elif curr_col > prev_col:                solution.append('e')        return solution
maze = [    "#@#.................#.....#.#",    "#.#.#######.#######.#.###.#.#",    "#.#.#.#.....#.....#...#...#.#",    "#.#.#.#.#######.#.#####.###.#",    "#.#...#.#.......#.#...#.....#",    "#.#####.#.#####.###.#.#####.#",    "#.#...#.#.#.....#...#.......#",    "#.#.#.#.#.#######.###########",    "#...#...#.#.......#.......#.#",    "#########.#.#######.#####.#.#",    "#.#.......#...#...#...#...#.#",    "#.#.#.#######.#.#.###.#.###.#",    "#.#.#.....#...#.#.....#.....#",    "#.#.#####.#.###.###########.#",    "#.#.....#.#.#...#.#.......#.#",    "#.#####.#.#.#.###.#.###.###.#",    "#.......#...#...#...#.#...#.#",    "#.###########.#.#.###.###.#.#",    "#.#.......#...#.#.#.....#...#",    "#.#######.#.###.#.#.###.#####",    "#.......#.....#.#...#...#...#",    "#######.#######.#####.#####.#",    "#.....#.....#...#...#.#.....#",    "#.###.#####.#.###.###.#.###.#",    "#.#.#.....#.#.#.......#.#...#",    "#.#.###.###.#.#.#######.#.###",    "#.....#.......#.........#...#",    "####################*########"]
solver = MazeSolver(maze)solution = solver.solve(0, 1)print("Instructions to solve the maze:")print(solution)
{{< /code >}}
The script outputs the instructions required to solve the maze, starting from `@` to the goal `*`. Writing up a quick script in python we can verify this works:
{{< code language="python" title="solve.py" id="3" expand="Show" collapse="Hide" isCollapsed="false" >}}# MazeSolver() here...from pwn import *import time
elf = context.binary = ELF("./challenge")p = process()
p.recvuntil(b"Which would you like to do?")p.sendline(b"a")p.recvuntil(b"You cast arcane eye and send your summoned magical eye above the maze.")
maze = p.recvuntil(b"You", drop=True).decode().split("\n")maze = [i for i in maze if "." in i or "#" in i] # scuffed method to get mazemaze = maze[1:]
solver = MazeSolver(maze)solution = solver.solve(0, 1)
for moves in solution:    p.sendline(moves)
p.interactive(){{< /code >}}
{{< image src="./img/maze_die.png" alt="" position="center" style="border-radius: 5px;" >}}
However, after reaching the goal we seem to just die. Reading the decompiled code further, we see why.
The goal is to call the `winner()` function, which gives us a shell:
```cvoid __noreturn winner(){  puts("Congratulations! You have solved the maze!");  system("/bin/sh");  exit(0);}```
However, the catch is that apart from solving the maze, we must also pass a random check, and if we don't, we die. So previously, we were dying because `rand() % 1213` was not equal to `1212`.
```c      if ( rand() % 1213 == 1212 )      {        puts("You successfully exit the maze!");        winner();      }      puts("Just as you are about to exit, a displacer beast captures you. You die.");      exit(0);```
Fortunately, the `rand()` seed is set to the current time with `srand()` at the start of the program.
```c  v3 = time(0LL);  srand(v3);```
Therefore our method to solve the challenge would be:- Figure out how to solve the maze (Done)- Mimic the `rand()` function in our script by seeding with the same time- Keep track of the number of `rand()` calls- Find a way to call `rand()`, and call it additional times until the next call results in `rand() % 1213 == 1212`
Doing a search in the decompiled code, we see functions `rand_range()` and `randomDescription()` each call `rand()` once when ran. 
```c__int64 __fastcall rand_range(int a1, int a2){  ...  return (unsigned int)(rand() % (a2 - a1 + 1) + a1);}
unsigned __int64 randomDescription(){  ...  v2[0] = (__int64)"cozy";  v2[1] = (__int64)"medium-sized";  v2[2] = (__int64)"spacious";  ...  v0 = rand();  printf(    "As you step into the room, you find yourself standing in a %s space. The walls are adorned with %s and a two large %"    "s dominate the center of the room. You see %d flowers in a vase, and through a window you stop to count %d stars. Th"    "e room appears well designed in the %s style.\n",  ...  return v5 - __readfsqword(0x28u);}```
`randomDescription()` is called every time we move, **even if our move/input is invalid**. This means we can call `rand()` once ourselves by inputting something that's not a command.
Lets debug with [`pwndbg`](https://github.com/pwndbg/pwndbg) to figure out how many times `rand()` is called when generating the maze.
We start the binary and immediately break with `starti`, and place a breakpoint after `generate_maze()`:
{{< image src="./img/starti.png" alt="" position="center" style="border-radius: 5px;" >}}
[]()
{{< image src="./img/break.png" alt="" position="center" style="border-radius: 5px;" >}}
Then, we set a breakpoint at `rand()`, and write a simpe python counter to keep track of how many times `rand()` was called (which was how many times the breakpoint was triggered)
```pypythoncounter = 0
def breakpoint_handler(event):    global counter    counter += 1    print(f"srand called. total times called: {counter}")
gdb.events.stop.connect(breakpoint_handler)end```
{{< image src="./img/gdbpythoncool.png" alt="" position="center" style="border-radius: 5px;" >}}
And we find `generate_maze()` hits the breakpoint `590` times (the `591` in the bottom of image is when it hits the breakpoint after `generate_maze()` in `main()`, so doesn't count).
Now that we have the amount of times `rand()` is called, we can simulate this in python to predict what number the next `rand()` call will yield.
```pyfrom ctypes import CDLL
libc = CDLL("./libc.so.6")libc.srand(int(time.time()))
def callrand():    return libc.rand() % 1213
# simulate rand() calls in generate_maze()for _ in range(590):    callrand()
callrand() # the initial random message it sends
...
for moves in solution:    callrand() # simulate rand() call in the random message we get after every input    p.sendline(moves)```
Now, after integrating the random calls into our solve script, we can stop before exiting the maze, keep calling `rand()` by submitting an invalid input, until the next `callrand()` we simulate yields `1212`. When it does, we can finally exit the maze, and `winner()` should be called, giving us a shell!
```pylastmove = solution[-1]
for moves in solution[:-1]: # do all moves except last    callrand() # simulate rand() call in the random message we get after every input    p.sendline(moves)
nextrand = callrand()while not nextrand == 1212:    p.sendline(b"x") # send invalid input to call rand()    nextrand = callrand()
p.sendline(lastmove)
p.interactive()```
Final solve script:
{{< code language="py" title="solve.py" id="4" expand="Show" collapse="Hide" isCollapsed="true" >}}class MazeSolver:    def __init__(self, maze):        self.maze = maze        self.rows = len(maze)        self.cols = len(maze[0])        self.visited = [[False for _ in range(self.cols)] for _ in range(self.rows)]        self.directions = {'N': (-1, 0), 'S': (1, 0), 'W': (0, -1), 'E': (0, 1)}        self.path = []
    def solve(self, start_row, start_col):        if self._dfs(start_row, start_col):            return self._get_solution()        else:            return []
    def _dfs(self, row, col):        if not self._is_valid(row, col):            return False
        self.visited[row][col] = True        self.path.append((row, col))
        if self.maze[row][col] == '*':            return True
        for direction in self.directions.values():            next_row = row + direction[0]            next_col = col + direction[1]            if self._dfs(next_row, next_col):                return True
        self.path.pop()        return False
    def _is_valid(self, row, col):        if row < 0 or row >= self.rows or col < 0 or col >= self.cols:            return False        if self.maze[row][col] == '#' or self.visited[row][col]:            return False        return True
    def _get_solution(self):        solution = []        for i in range(1, len(self.path)):            prev_row, prev_col = self.path[i-1]            curr_row, curr_col = self.path[i]            if curr_row < prev_row:                solution.append('n')            elif curr_row > prev_row:                solution.append('s')            elif curr_col < prev_col:                solution.append('w')            elif curr_col > prev_col:                solution.append('e')        return solution
from pwn import *from ctypes import CDLLimport time
libc = CDLL("./libc.so.6")
def callrand():    return libc.rand() % 1213
elf = context.binary = ELF("./challenge")
# seed with the current time right before starting the programlibc.srand(int(time.time())) p = process()
# simulate rand() calls in generate_maze()for _ in range(590):    callrand()
callrand() # the initial random message it sends
p.recvuntil(b"Which would you like to do?")p.sendline(b"a")p.recvuntil(b"You cast arcane eye and send your summoned magical eye above the maze.")
maze = p.recvuntil(b"You", drop=True).decode().split("\n")maze = [i for i in maze if "." in i or "#" in i] # scuffed method to get mazemaze = maze[1:]
solver = MazeSolver(maze)solution = solver.solve(0, 1)
lastmove = solution[-1]
for moves in solution[:-1]: # do all moves except last    callrand() # simulate rand() call in the random message we get after every input    p.sendline(moves)
nextrand = callrand()while not nextrand == 1212:    p.sendline(b"x") # send invalid input to call rand()    nextrand = callrand()
p.sendline(lastmove)
p.interactive(){{< /code >}}
Running the final script we indeed get a shell, and solve the challenge!
{{< image src="./img/shell.png" alt="" position="center" style="border-radius: 5px;" >}}
To recieve our points, we had to submit a `.tar` file with a Dockerfile and the solve script, which should run `./submitter` after getting a shell, and print the flag. However, since I didn't use any `p.recv()` after sending the moves, the buffer would crash the docker and the submission would fail. Fortunately, one of my teammates [Zafirr](https://github.com/zafirr31) submitted with `p.sendlineafter()` to overcome the issue and we got the points :)
# Conclusion
I would like to thank all my teammates for putting in all their effort playing the CTF, and especially [`Zafirr`](https://github.com/zafirr31), [`KebabTM`](https://twitter.com/KebabTM), [`Eth007`](https://eth007.me/blog/), [`Ainsetin`](https://twitter.com/ainsetin) and `Goldenboy` (sorry if i missed anyone) for helping me figure things out (especially the `rand()` calls) while I wrote the solve script to solve this challenge!
It was fun playing with a lot of people, and for the second day I met up with some of my teammates to solve more challenges - you can see [`toasterpwn`](https://twitter.com/toasterpwn)'s writeup on them [here](https://toasterpwn.github.io/posts/defcon-ctf-2023-qualifiers/)!
Unfortunately this CTF was right in the middle of my exams so I couldn't dedicate full time to it, but I hope to play with everyone again and hopefully qualify next year! Thanks for reading!
- teddy / TheSavageTeddy