writeups/litplus/otw19/Adv-25.md

   1 day-25 Lost in Maze
   2 -------------------
   3 OverTheWire Advent 2019, day 25
   4
   5 Discussion in [Mattermost](https://mattermost.w0y.at/otw-advent-2019/channels/day-25-lost-in-maze)
   6
   7 Full exploit on [GitLab](https://gitlab.w0y.at/ctfs/overthewire-advent-bonanza-2019/tree/master/day-25)
   8
   9 Time spent for this challenge: 16 hours + 1 hour write-up
  10
  11  * December 25: 7 hours (15:30-19:30, 21:00-00:00)
  12  * December 26: 9 hours (00:00-09:00)
  13
  14 ### Overview
  15
  16 ```
  17 Lost in Maze - misc
  18 Points: 1337
  19
  20 We have a code red ( and green, gold and white), we have lost Santa.
  21 While he was delivering gifts he seems to have gotten a bit tipsy and
  22 got lost somewhere over Europe. Luckily we saw this coming, we have a
  23 GPS and bodycam on him, but we need your help. Get him out of there and
  24 back on track to save Christmas.
  25
  26 Service: nc 3.93.128.89 1225
  27 Author: b0bb
  28 ```
  29
  30 Upon connection, the game presents a fancy splash screen and asks for a screen size:
  31
  32 ![Start screen](25-home.png)
  33
  34 After entering some screen size, the game renders a maze in ASCII art. In the bottom right corner, a mini-map is displayed.
  35
  36 ![Game screen](25-initscreen.png)
  37
  38 Navigation is possible via WASD.
  39
  40 ### Exploitation
  41 #### Mapping the search space
  42 I quickly realised that the whole game state can be represented using the little GPS map. Initially, I thought that by turning in specific increments, moving would be possible in straight lines. However, this turned out to be incorrect. The rotations do not allow to move in 90° angles, and the client needs to adjust to the 3D rotation. The exact rotation is not visible in the map, but can be inferred from the big screen. So the first approach I tried was to manually walk through the labyrinth and record the map to have some orientation.
  43
  44 After some Python™, I arrived at this state:
  45
  46 ![Small map reconstructed to big map](25-mapping.png)
  47
  48 The setup for this consists of [`client.py`](https://gitlab.w0y.at/ctfs/overthewire-advent-bonanza-2019/blob/35e34e8facfce4863ecabc0cb84374da3742e6c6/day-25/client.py) and a [`model.py`](https://gitlab.w0y.at/ctfs/overthewire-advent-bonanza-2019/blob/35e34e8facfce4863ecabc0cb84374da3742e6c6/day-25/model.py). The former handles the connection itself and the interaction logic, while the latter is responsible for modelling the game state as objects and operations on them.
  49
  50 What the client does at this point is connect to the server, input the screen size, and receive the screen. This is then output to the console. A command prompt allows to move via WASD and export the map to a file. After the sctreen is read, it is also passed to the model.
  51
  52 This first parses the `ScreenState` to find the GPS and provides the GPS parser with the contents of the GPS itself. It also strips the colour codes used to make the game visually attractive. These are not helpful for parsing content. `GpsState` then takes the GPS lines and parses the current position and target position. Then, it looks for the cursor as center point of reference. next, it parses all walls from the GPS and stores their positions relative to the center. Finally, it adds the current positon to the relative positions to obatain absolute positions of the walls observed. It stores a boolean array of walls for absolute coordinates. Finally, the `Map` object puts this all together and keeps track of current position and map, merging in new information from the GPS for every new screen. It also takes care of printing the map to a string.
  53
  54 Further, I deduced that distance is encoded as follows:
  55
  56 ```
  57 ` very far
  58 -
  59 ~
  60 :
  61 ^
  62 r
  63 =
  64 x
  65 z
  66 e
  67 m
  68 &
  69 &
  70 M
  71 N
  72 Q
  73 @ no distance
  74 ```
  75
  76 If more than half of the screen is made up of `@` characters, movement is denied. This is a useful heuristic to use later for automatic movement.
  77
  78 #### Directions for the driver
  79 Using fully manual control, I was only able to get to around `(30, 25)` in the 10 minutes of timeout. This is not very good since the target is `(81, 81)`. So, I decided that an algorithm was needed to suggest where I should go.
  80
  81 Like a true hacker, I got inspired by someone else's A-Star implementation for this: [Thanks Laurent Luce](https://www.laurentluce.com/posts/solving-mazes-using-python-simple-recursivity-and-a-search/). The implementation wasn't quite perfect and didn't fit all of our needs, so I had to adapt it. The main issue with this implementation of A-Star is that it is designed for a *known* search space, which we do not have. We only know about a small part of the maze via the mini-map. Importantly, heuristics are not stable and previously-promising tiles may lead to a dead end in the next update.
  82
  83 What the A-Star does is to discover new tiles adjacent to the current position and assign each one a heuristic value. The next tile to visit is the tile with the lowest heuristic value (that is supposed to represent the effort needed to get there). I used square distance to the goal as heuristic.
  84
  85 The way this is implemented in the [final `model.py`](https://gitlab.w0y.at/ctfs/overthewire-advent-bonanza-2019/blob/master/day-25/model.py#L179) is that after receiving an update, we creates a new `TilePathFinder` to suggest the next target. This stores the current candidate list in a heap (`open`). In `process`, it loops as long as there are candidate tiles. If the next tile is the goal, we return it (the `PqTile` model keeps track of the path we used to get there). Otherwise, we look at its neighbours, compute their heuristic, and add them to the candidate heap.
  86
  87 Later, I changed this portion of the algorithm to penalise already-visited tiles, because the bot kept getting stuck in locally-optimal solutions that did not take into account that not all of the maze was discovered. I also added a special tile state, `MYSTERY`, to represent that a tile's value is unknown. Later, I modified the algorithm to look primarily at such mystery tiles, because discovering more of the map is far more helpful than staying in the map. (The initial solution went to the tile that was closest to the goal of all known tiles, but this did not always reveal a closer tile.)
  88
  89 To assist the driver, I visualised visited tiles (blue), the current position (green) and the current A-Star target in the full map:
  90
  91 ![Map with colours](25-driver.png)
  92
  93 #### Automating it
  94 However, manual control was still too slow to reach the goal in a reasonable time-frame. I started adding [a small heuristic algorithm](https://gitlab.w0y.at/ctfs/overthewire-advent-bonanza-2019/blob/master/day-25/client.py#L185) to move straight ahead until an obstacle was encountered. This worked, but still needed manual control, had no parallelisation, and couldn't turn or go to a target.
  95
  96 Next, I added [a more complicated algorithm](https://gitlab.w0y.at/ctfs/overthewire-advent-bonanza-2019/blob/master/day-25/client.py#L103) that keeps track of the A-Star target and past moves. It uses the path information from `PqTile` to move to the A-Star target. If it detects that it gets stuck (this works by analysing the wall distances and if the last few moves changed the screen view), it does some random movement to get unstuck. It also autonomously turns to face the correct direction. Since this works fully automatically, I was able to run this in parallel with three instances running locally and six on a server I own, using Docker.
  97
  98 Applying this and incrementally improving the algorithm with different heuristics yielded quite successfuly executions like this:
  99
 100 ![close to the goal](25-close.png)
 101
 102 ![](25-something.png)
 103
 104 After reaching the goal for the first time, I learned that `except Exception` does not catch errors in Python, and lost the flag. Sad
 105
 106 One and a half hours later, the algorithm succeeded again, this time with proper error handling :)
 107
 108 ```
 109 You saved Christmas, here is your reward:
 110 AOTW{426573742077697368657320666F7220323032302121}
 111 ```
 112
 113 ---
 114
 115 Thanks for reading all of this, lol
 116