writeups/fkehrer/ctfzone19.md

   1 # CTFZone 2019 Quals
   2
   3 ## Fridge
   4
   5 The service sends you some 0s and 1s, which are arranged as a board. You send your input, which consists of two numbers. The response is either the updated board or the phrase "this one is solved", followed by a new board. Presumably, there is an end to this game, but we didn't reach it.
   6
   7 ### Level 1 - 4x4
   8
   9 The first level seems to be the same every time. I did not record it, but going from memory, I think it looked like this:
  10 ```
  11 0 1 0 0
  12 0 1 0 0
  13 1 1 1 1
  14 0 1 0 0
  15 ```
  16 After sending `2,1` (or maybe it was the other way around), the board would be solved.
  17
  18 Now, I assumed this to be a chess- or reversi-like situation: We have a quadratic board, and can choose one position on it, prompting the flip of the chosen position and some others, based on some rules. In this level, this would be like putting a (chess) tower on the position 2,1 (with the first number being the downward and the second number the rightward direction), and flipping all positions it could reach with one move. This results in a board of just 0s, which is the "solved" state.
  19
  20 I noticed two important properties about moves made in this and the next level: First of, applying a move twice has the same effect as not applying them, meaning any made move can be reversed by applying it again. And secondly, which positions get flipped do not depend on the board in any way, meaning also that moves can be applied in any order.
  21
  22 ### Level 2 - 4x4
  23
  24 Based on what we learned in level 1, we would assume this to be the same situation, with the added difficulty of having to make more moves, right? Wrong. For some reason, the moves do not follow the cross-shape of level 1 anymore, or any shape we could recognize. So we had to come up with something smarter.
  25
  26 The solution for level 2 is always easy (only a few moves), but since we do not know which move does what, we can't just solve the board by reading in the start state.
  27
  28 So I created a script, which tries every possible move once, records which fields are flipped, and once all moves have been recorded, reads the current state of the board and finds a combination of moves which solves it.
  29 One glaring limitation of my implementation is that I just assume that while trying moves, the board will never be solved by accident. This actually happens occassionally, but it's not often enough to be a serious problem.
  30
  31 This approach is actually a bit overkill, since we apply every move, and normally have to undo almost all of them in order to solve it. There are two reasons I decided to not apply every move twice though: First of, it would take twice as long to do all moves (the network is the limiting factor here), and more importantly, the chance of accidentally solving the board is much smaller (which would be bad, because I threw the script together in the last hours of the CTF, so I didn't want to handle the possibility).
  32
  33 ### Level 3 - 10x10(?)
  34
  35 So far, things were looking good. The script I made solved both level 1 and 2 almost instantly, but level 3 is where things became problematic. Just trying the moves took noticable time, and solutions were either not found within the time I let it running, or at all. Time was running out, and waiting forever was just not an option anymore.
  36
  37 The major change I made to the script was to switch the solution search from depth first to breadth first, since both level 1 and 2 had very short solutions, I assumed this would hold true for level 3 as well. This change turned out to be a pain, but I did eventually make it. However, tracking multiple attempts, my script found no solutions for any combination with less than five moves. Obviously, every stage of the search took a lot longer than the one before it, and at some point, I think it was a depth of 5 (checking all combinations of 5 moves), it ran for many minutes without finding anything, so I eventually stopped it.
  38
  39 Level 3 and beyond stayed unsolved.
  40
  41 Both the [DFS](ctfzone19/solve.py) and [BFS](ctfzone19/solve_bfs.py) versions are included. Note that both boards and moves are encoded as lists of True and False, where for boards this encodes the 0s and 1s of the board, and for boards it encodes whether a field is flipped or not. This allows me to easily apply any number of moves to a board by XORing their fields.
  42
  43 ### Closing thoughts
  44
  45 I fear that the reason I found no solutions for level 3 (within the timeconstraints of "oh no, the CTF ends in less than an hour") was that one of the many found properties and made assumptions simply did not hold for level 3. Maybe the shape was not strictly quadratic anymore, maybe moves worked differently, maybe other symbols were introduced, the things I do not know about this service far outweigh the things I do know. There's also a very real chance of my script being buggy.
  46
  47 Even with all these setbacks, this challenge was actually really entertaining to work on. My colleague Raphael, who was actually trying to study Maths next to me, was a great help by listening and contributing ideas, and without him, I would have probably failed to solve the challenge even harder. :)