HackMirror: The HackMIT 2018 Puzzle Guide Part 2

(Part 2 of 1, 2, 3)

Welcome to part 2 of the HackMirror writeup! Check out Part 1 if you haven’t already; otherwise, buckle in for lockpicking, b l o c k c h a i n, and self-driving cars 🚗.

Keys

(website, GitHub)

One of my favorite parts about computer science is to see my computer program do something cool that I could never do. This puzzle was designed to make the puzzlers hopefully go through the same experience.

Navigating to the given link, the puzzlers were presented with a bit of fluffy lore and links to download a program for their operating system.

After downloading the app, the puzzlers were presented with an executable file, running which resulted in a window that looked like a badly-written game. The reason the game looks like something out of MS Paint is because it is out of MS Paint.

The game is fairly simple: the player needs to click on a lock, and then the lock jumps away to a random new location, and this repeats. The number of times the player can click on the lock until the time runs out is their final score.

The task of this puzzle is to get a score of 100. The puzzlers soon realized that trying to get this score by hand is virtually impossible.

A few keen puzzlers observed that the given app was written in Unity, a game framework that uses .NET to run its scripts. .NET is a fairly easy language to reverse engineer using the plethora of .NET decompilers out there. I specifically wanted people to not go this route and obfuscated the cryptographic secrets and most of the code very heavily. The score and timer variables were not standard integers in memory, but an encoding to prevent CheatEngine hax0rs from winning easy. The code even used a few anti-debugging tricks.

The intended solution was to do simple computer vision and mouse input emulation to find the lock and click on it at superhuman speeds. This can be done fairly easily in 60 lines of Python.

People came up with very creative ways to solve this puzzle, slowing down the time for that process, freezing the random generator and writing fast auto-clickers that clicked in a grid like scheme. One hacker did the hard work of reversing the obfuscated code to obtain the cryptographic secret.

HackCoin

(website, GitHub)

At HackMIT, we didn’t want to be left out of the crypto bubble. So we decided to create HackCoin: the decentralized revolutionary blockchain for all your VR needs. Like all crypto startups, the VR is a lie.

The puzzlers were presented with a fancy splash page pitching our cryptocurrency. From there, they could read the whitepaper, which was again bad blockchain jokes,

or they could go to the store,

or they could download the client: which was written in Python and consisted of the wallet and miner.

Each puzzler was given a unique blockchain with only two users: the server and the puzzler. Both the server and puzzler mine blocks and earn a few HackCoin. The goal is to donate 13337 HackCoin to the server to unlock the answer.

The intended solution of the puzzle is for the puzzler to earn a few HackCoin, optimize the mining code and carry out a series of double-spending attacks (51% attack) once they control the majority of the network. This way they can reverse transactions, and keep spending that same HackCoin over and over again, getting to the desired number of coins, and hence getting the answer.

Since the given miner was written in Python, it was fairly easy to optimize it. Many people chose to write miners in C++ to speed up the hashrate. We set the block difficulty such that the default miner solved a block every 5 minutes on an average computer.

Surprisingly, writing a simple blockchain could be done in just a few hundred lines. The core code turned out to be fairly cleanly written, so might possibly serve as an educational tool. It was very hard to come up with an idea for a blockchain puzzle, on how to make it decentralized while having some central control.

Side 🎵: Since the final version only had the server and the puzzler mining, and since the server was the one giving out the answer, we never made the server mine any blocks, instead we made it cheat the mining process by forcing the user to accept a block with any nonce the server wished. This helped us save a few hundred dollars in AWS charges.

This puzzle was incredibly fun to write since we had to learn fundamental concepts ourselves. We hoped the puzzlers enjoyed solving this too!

HackGPS

(website, GitHub)

When puzzlers reached the fifth puzzle, HackGPS, they were presented with a grid of roads and a car. The puzzlers were given the task of navigating the car back to “Tim’s house” within a time limit. At first glance, the puzzle seemed like a straightforward shortest path problem, but after trying it out for a bit with the manual controls on the website, puzzlers quickly realized that the car didn’t always follow instructions.

After digging around the site a bit more, and particularly after looking at the network tab on the browser inspector, puzzlers would have noticed a full API for the puzzle, including calls to fetch the map and make moves. Interestingly, they would notice an HTTP call to a /probability endpoint; through some subtle hints in the description (“The network connection from your console to his car is glitchy”), puzzlers deduced that their moves were being randomly changed.

From here, there were a couple different approaches people took to solving the puzzle. Many used a brute force method that always took the shortest path to the destination. We purposely designed maps such that this solution had a very low probability of succeeding, but unfortunately we didn’t make it low enough 😅

The intended solution was to use dynamic programming.

• Let dp[n][t] be the probability that the destination node can be reached from node n in t steps or less, for an optimal solution.
• The base case is dp[N][0] = 1, where N is the destination and dp[n][0] = 0 for all the other nodes
• Next, we can derive a recurrence dp[n][t] = max(dp[v][t — 1]) * (1 — p) + average(dp[v][t — 1]) * p, where the max and average are taken over all neighbors v of n, and p is the probability that a move is randomly changed. The recurrence holds because it’s always optimal to try to move to the node that has the highest probability of success.
• This DP has a complexity of O(N*T) where N is the number of states and T is the maximum number of moves. Because N*T = 1.35 * 10⁷, this is very feasible and runs in under a minute on most computers.
• The final solution, then, is to move in the direction of maximum probability of finishing (argmax(dp[v][t-1]) in the recursion above) when you are at position n at time t. The motivation behind this solution is to transform the given graph, which is a general directed graph, to a DAG in order to take advantage of the substructure and use dynamic programming. We do this by replicating the given graph for each time step and only allowing forward steps in time.

See an implementation here.

Another solution we saw took an optimization route instead of an algorithms route. The basic idea behind this solution is to view the entire graph as a Markov chain and the maze as a random walk on this Markov chain. Then, the goal is to set the transition probabilities between the nodes of the chain so as to maximize the absorption probability of the goal state. In the most general case, this becomes an optimization problem with N (the number of nodes in the graph) variables that can each take 4 discrete values — but because N = 22,500, this was too large of a problem to directly optimize. Instead, puzzlers could use various heuristics in order to optimize the probability of solving the graph enough to finish in one or two tries. For example, one successful approach involved assigning weights to all the nodes, where a higher weight indicates that the node is undesirable. These weights could be initialized based on shortest path distances, and then iterated on using a Markov-like calculation of weighted average neighbor weights for each node. Iterating relatively few times resulted in weights that led to the house with a pretty high probability.

We generated maps by first creating a minimum spanning tree using Prim’s algorithm and then randomly adding extra edges to achieve an ideal solve probability. We aimed for ~80% solve rate for the optimal solution and ~2% solve rate for the shortest path solution. Once we realized many people were able to solve the puzzle in a reasonable amount of time by repeatedly trying the shortest path solution, we considered merging two maps together (“Tim wants to stop at his house before getting to school”) so that the solve rates would become 0.8² = 64% and 0.02² = 0.04% respectively, making the shortest path solution much less feasible, but we chose not to change the puzzle to be fair to those who had already solved it.

Outside of the technical details, we had a lot of fun coming up with a Black Mirror theme for the puzzle 😃. Many puzzlers were confused about the actual location of Tim’s house, which we tried to hint at by saying that it was “really far”, but that ended up turning into a mini-puzzle of its own. All in all, hope everyone enjoyed working on the puzzle!

Tim finally found his house!

Almost there! Only Part 3 left — click for our hardest puzzles and some final puzzle stats.