Time-Traveling in the Puzzlelorean: The HackMIT 2017 Puzzle Guide
On July 1st, 2017, HackMIT released our fourth (!!!!) annual puzzle. Past years brought us memes, more memes, and webcomics, but this year we’re going all the way hack to the future (along with the entire hackathon itself — check it out)!
But first, if you haven’t seen the puzzle yet, we recommend you dial in to July 1st and try it out at hackmit.org! Come back later after you’re thoroughly stumped 😵
As is tradition, the entry point to the puzzle was hidden on our humble splash page.
At first everything appeared normal, but by clicking and dragging on the dial hackers noticed something strange…
… they began to jump ahead into the future, towards the date of HackMIT itself 😮
Empty the dial completely, and they were quickly warped to delorean.codes, the home of our command center!
This year’s command center used the same backend from previous years. Puzzlers could log in with their GitHub and look at the URLs for all the puzzles in sequence.
We made it look like the inside of the DeLorean from Back to the Future, with two time displays. The present time showed a deterministic value as a function of the current puzzle, which could be selected from the knob.
All puzzle answers were formatted as dates and were deterministic as a function of the puzzler’s GitHub username. Puzzlers could enter their answers in the destination time panel using the keypad.
It was particularly fun making some of the assets of the command center. A handful of the labels, the metallic Puzzlelorean logo, and the flickering neon lights at the entry point were done in Blender, an open source 3D modeling software and LuxRender, a raytracing renderer. Some of the buttons used were pictures of control panel buttons Shreyas found in his box of old buttons from Adafruit.
The first puzzle was meant to introduce the puzzlers to the puzzle workflow and mechanics. They were presented with something mostly familiar: a version of our main website in a curious alien font.
Peeking into the source of the page unmasked the alien font and gave the puzzler a bit more familiar of an alphabet. However, things still didn’t seem particularly intelligible… 🤔
A closer look revealed that the text on the page was encoded with a Caesar cipher, shifting all the letters of the alphabet by a fixed amount. Many puzzlers successfully decoded the page and found some fun stuff going down during our futuristic HackMIT, but not necessarily anything that brought them closer to solving the puzzle.
However, after looking a little closer puzzlers found a link on the page pointed to:
This linked to a JAR file that when executed, gave the following output:
Digging further into the JAR using any Java decompilation tool (JD-GUI shown here) revealed the source code of the app.
The source makes it clear that turning the user’s system clock back to the
START_EPOCH timestamp would reveal the actual answer.
Some puzzlers simply modified the JAR and removed the if statement to bypass the check. This puzzle was a reverse engineering task to get our puzzlers started before they delved into the more involved puzzles.
This puzzle confused many in the beginning. When users first arrived they were presented with a login page. The user field was a dropdown that contained two choices and the password field was empty.
Many puzzlers attempted injection attacks on the password field (possibly inspired by last year’s Bobby Tables puzzle), manipulating the value of the username field, and even attempted to attack the session cookie. None of these attempts were effective. After some internal discussion, we added hints and modified the implementation.
The key insight to getting past the login page of this puzzle is that a timing attack is feasible on the password field. The string comparison function looks something like this:
for i in range(min(map(len, [a,b]))):
if a[i] != b[i]:
return len(a) == len(b)
This means that each correct character will add some delay to the request.
Consider a naive brute force strategy. We allow uppercase and lowercase letters as well as digits. This means we have 62 possible characters. We also specify password length to be between 6 and 12 characters. Now even if we only considered 6-character passwords, there would be 62⁶ possible passwords (~10¹⁰ combinations). Making this many requests would be infeasible. The number of requests grows
k is the number of characters and
n is the length of the password.
Now consider a strategy informed by the amount time a request takes. For each character slot in the password we have to try 62 possible characters. Assuming we’re 100% certain that this character is the true password character, we can continue on to the next character. This means that the number of requests we have to make grows in
O(kn). Since the time it takes to verify each character slot grows with the size of the password, the total time it takes grows in
O(kn²). In order to speed up this process it’s possible to make the per-character requests in parallel.
This puzzle requires significant per-character delay and low response time variance. We exaggerated per-character delay to half a second. This makes the time difference very clear regardless of request latency. We attempted to decrease response time variance by making sure we had the capacity to handle a large number of concurrent requests. (after all requests can last up to 6 seconds) To do this we took advantage of gevent’s event loop, so we didn’t waste time time.sleeping when we could’ve been been answering requests.
To make response times more obvious we also added a response header
X-Upstream-Response-Time. This header was designed to just look like something nginx had attached, but in reality the number that it output was calculated by the puzzle app.
Once puzzlers had logged in they were presented with this page:
At this point it seemed that the obvious course of action was manipulating the session cookie or transfer field; however neither of these worked. This phase required another time-themed attack: race conditions.
Bank transfer operations are classic academic examples of race conditions. These vulnerabilities are particularly hard to find because concurrency is hard to wrap one’s mind around in large applications. Once you logged in to both users’ accounts (sorry for people who found the password by hand 😬) you could initiate
n transfers concurrently from one account to the other. The transfer function looked something like this:
x = get(marty)
y = get(biff)
This made it possible to break the invariant marty + biff = constant and create money. We added a delay in between the set operations, so much so that this attack was possible to execute by creating two tabs in your browser and Ctrl-Tab-ing quickly between them.
Something interesting: it’s possible to race in the “wrong direction”. If you race by calling transfer on the same account, you create money. However, if you race by calling transfer on different accounts, the final operation sets both balances to 0, effectively removing all of your funds and making the puzzle impossible to solve.
To prevent this we do an additional check to make sure that the sum of your balances isn’t 0 (this check is also not atomic 😉).
A huge thanks to Shreyas and Patrick for writing up the solutions to these puzzles! Warp ahead into part 2 to see things get really interesting…