The HackMIT 2016 Puzzle — Part Deux

A puzzle for hackers, snackers, and slackers.

Published in

HackMIT Stories

9 min readAug 22, 2016

(part 2 of [1, 2])

After geohashing and NoSQL injection in the first two puzzles, puzzlers confronted had to escape velociraptors using a mystery programming language and predict results of sports games by exploiting an insecure random number generator.

Velociraptor Escape

When puzzlers reached the third challenge, they saw a game-like interface and straightforward help menu. This puzzle, Velociraptor Escape, required them to control an agent in a 2D grid using commands in a mystery programming language (named Raptor, made specifically for this puzzle).

The grid contained velociraptors that moved around and ate the agent, which would cause them to lose the game. To pass a level, players needed to write programs that safely moved the agent to a certain spot in the grid. Players knew how to move the agent up, down, left, and right from the help menu, but there was one further restriction imposed by the game: their programs had to conform to a complexity standard to prevent them from just typing out a list of directions[1].

In order to figure out how to write more abstract programs to pass the challenges, puzzlers had to look through the source code to figure out how the game and the language worked. By reading through this EBNF, players could learn the syntax of the language, and by reading through the interpreter code, they could figure out what the syntax actually did.

This puzzle consisted of five levels, each of which was meant to introduce players to a new feature of the language.

[1] We realized that there was an easy way to bypass the complexity standard check with our original version of the puzzle, so we wrote some code to fix it. Unfortunately, we forgot to actually use it in production, and we couldn’t update it after-the-fact out of fairness to all the puzzlers. This puzzle should have been a lot harder!

Level 0

The first level was straightforward. There were a few valid movement sequences that safely brought the agent to the goal, one of which was “R, D, R, D”. But simply entering those movement commands wouldn’t work; it wouldn’t pass the complexity requirements. To satisfy this level, puzzlers needed to learn how to define functions in Raptor language and abstract out the repeated “R, D” sequence. Here’s some valid Raptor code that solves this puzzle:

diagonalDown {
  moveRight
  moveDown
}
diagonalDown
diagonalDown

Level 1

The next level required players to use recursion in their solutions. It’s pretty easy to see that the valid path is “R, R, R, R, R”, but entering that verbatim movement sequence resulted in a complexity of 111, much higher than the required 55. Raptor doesn’t support for/while loops, but you can still achieve the same effect with recursion.

moveRightN => n {
  n > 0 {
    moveRight
    moveRightN -> n - 1
  }
}
moveRightN -> 5

Level 2

The movement sequence for this level is a lot longer than that of the last two. The velociraptors are sparse so it’s a little less clear what the expected path is, but one that works and seems to contain sufficiently abstract-able patterns is, “6 L, 3 U, 6 R, 3 U, 6 L”.

The cleanest way to implement this in Raptor is to take advantage of first-class functions and partial function application. By defining a loopN function that calls a function f n-many times, we can express this sequence as follows:

loop => n => f {
  n > 0 {
    f
    loop -> (n-1) -> f
  }
}
loop6 = loop -> 6
loop3 = loop -> 3
loop6Left {
  loop6 -> moveLeft
}
loop6Left
loop3 -> moveUp
loop6 -> moveRight
loop3 -> moveUp
loop6Left

This achieves a complexity of 129, below the maximum of 160 (you can actually get lower than this ;)).

Level 3

The pattern for this level was a spiral. The important thing players had to realize was that they could programmatically decide which direction to move in with the move function. With this tool in hand, it’s a lot easier to write code that spirals the agent to the goal. Here’s some code that solves the puzzle with a complexity metric of 105.

multimove => n => d {
  n > 0 {
    move -> d
    multimove -> (n-1) -> d
  }
}
spiral => n => d => t {
  t > 0 {
    multimove -> (n) -> d
    d > 0 {
      spiral -> (n-1) -> (d-1) -> (t-1)
    } : {
      spiral -> (n-1) -> (3) -> (t-1)
    }
  }
}
spiral -> 6 -> 3 -> 6

Level 4

The challenge posed by this level was staying within the compute constraints. The pattern was a Fibonacci spiral, so players needed to compute the Fibonacci numbers somehow. And unluckily for them, the well-known recursive definition is too slow. Also, Raptor doesn’t support features like lists, so there’s not really an easy way to memoize intermediate computations. Here’s the efficient recursive way to compute the Fibonacci numbers:

fibh => a => b => n {
  n == 0 { return a }
  n == 1 { return b }
  return fibh -> (b) -> (a+b) -> (n-1)
}
fib => n {
  return fibh -> 0 -> 1 -> n
}
multimove => n => d {
  n > 0 {
    move -> d
    multimove -> (n-1) -> d
  }
}
spiral => n => d => t {
  t > 0 {
    multimove -> (fib -> n) -> d
    d > 2 {
      spiral -> (n+1) -> 0 -> (t-1)
    } : {
      spiral -> (n+1) -> (d+ 1) -> (t-1)
    }
  }
}
spiral -> 1 -> 1 -> 6

This program gets a complexity of 151, but you can do even better if you notice the similar recursive structure of the spiral and fibh functions and inline the Fibonacci computation:

multimove => n => d {
  n > 0 {
    move -> d
    multimove -> (n-1) -> d
  }
}
spiral => n => f => d => t {
  t > 0 {
    multimove -> (n) -> d
    d < 3 {
      spiral -> (f) -> (n+f) -> (d+1) -> (t-1)
    } : {
      spiral -> (f) -> (n+f) -> (0) -> (t-1)
    }
  }
}
spiral -> 1 -> 1 -> 1 -> 6

This gives a complexity of 109, successfully solving the level and completing the puzzle.

Sports Commentary

This year’s final puzzle was inspired by “Sports Commentary” (https://xkcd.com/904/).

This puzzle puts hackers in the spot of a sports commentator, and it’s their job to build a successful narrative about the 18 Backyard Baseball teams that are competing in the Grand Sportsball Competition. They have boundless information at their disposal, produced by a weighted random number generator — how do they use it?

When visiting the puzzle page for the first time, you are inundated with information

Unfortunately, after a few page refreshes on the site, there doesn’t seem to be a discernible pattern to the rankings of the teams in the competition. Looking at the page source seems to confirm this — there are a couple of functions that call getRandonNumber (actually a typo for getRandomNumber — oops!). More specifically, the create_winrate_table function seems to rely on it heavily, which means the huge stats table is just a bunch of random numbers.

Looks like the weighted random number generator is simply that — no tricks, but that also means we can’t discern any information from the table or the charts.

Solving this puzzle requires a deeper look at the page source. Upon page load, the website makes a quick request to the /yourgithubusername/xorshift128plus endpoint, and a quick Google search of “xorshift128plus” turns up this Wikipedia page of a pseudorandom number generator, XorShift128+. Visiting Sportsball’s XorShift128+ endpoint seems to return a huge list of random numbers every time you refresh.

Digging deeper, the page uses the first number from this huge list to generate the list of teams at the top, through use of the add_winners function. If only we could predict the result…

Luckily, XorShift128+ is pseudorandom: if we know the seed, we can predict the next output. Although the seed can’t be explicitly found anywhere, it’s not intractable to find the seed since XorShift128+ is not cryptographically secure.

One possible way to find the seed of XorShift128+ is through the use of a SMT solver (also known as a satisfiability solver). SMT solvers allow users to give a computer a set of constraints, and the computer can intelligently search through the space of inputs to the constraints to find some inputs that satisfy them. We can represent the XorShift128+ algorithm and RNG outputs as constraints that must be solved, and we can ask the computer to solve for the internal state of the RNG. Using the internal state, we can predict the next output!

Big thanks to Douglas Goddard and his blog post on this matter: his post was part of the inspiration of this puzzle, and many puzzle solvers ended up using his post for inspiration.

After this step, most implementations will fail. Running your satisfiability script on the outputs from the XorShift128+ endpoint will frequently result in incorrect guesses or “UNSAT” (unsatisfiable; no internal state exists that would output the given numbers). We must be missing a critical piece.

There are 18 teams, so how many possible orderings are there? 18! ~ 6.4* 10¹⁵. XorShift128+ outputs 64 bit numbers, so how many possible RNG outputs are there? A naive answer would be 2⁶⁴ ~ 1.8*10¹⁹. However, diving deep into JavaScript internals reveals that all numbers are stored as 64 bit floating point numbers, which use 52 bits to store the mantissa, or the precision bits. With these restrictions, it means that JavaScript can only safely store numbers up to 2⁵²[2].

Indeed, looking closer at the outputs of the XorShift128+ endpoint reveals that the numbers never exceed 2⁵² -1. This is further confirmed by the fact that getRandonNumber divides by Math.pow(2, 52). The algorithm on the backend must be masking the outputs of the XorShift128+ RNG, only giving the least significant 52 bits!

A modification of the satisfiability script from before should start to produce correct guesses at this stage. With this, all that’s left is to plug the output of the script into the add_winners function in the console, and you’ll be greeted with a perfect prediction of the Grand Sportsball Competition team rankings at the top of the page!

[2] Actually, it’s 2⁵³, since there’s an extra precision bit not explicitly stored, but that’s for another day.

After finishing this final puzzle part, hackers submitted their email in the command center, and they and their team were guaranteed admission to HackMIT.

Our team had a ton of fun putting together these puzzles, and we hope hackers enjoyed solving it too! We especially loved seeing hackers’ struggles on Slack: