Snowball Fight

Tangle Coalbox:

Howdy gumshoe. I'm Tangle Coalbox, resident sleuth in the North Pole.

If you're up for a challenge, I'd ask you to look at this here Snowball Game.

We tested an earlier version this summer, but that one had web socket vulnerabilities.

This version seems simple enough on the Easy level, but the Impossible level is, well...

I'd call it impossible, but I just saw someone beat it! I'm sure something's off here.

Could it be that the name a player provides has some connection to how the forts are laid out?

Knowing that, I can see how an elf might feed their Hard name into an Easy game to cheat a bit.

But on Impossible, the best you get are rejected player names in the page comments. Can you use those somehow?

Check out Tom Liston's talk for more info, if you need it.

Location

Inside the Speaker UNpreparedness room, accessible from the Talks Lobby (see map) after opening the door

Hints

Python uses the venerable Mersenne Twister algorithm to generate PRNG values after seed. Given enough data, an attacker might predict upcoming values.

Tom Liston is giving two talks at once - amazing! One is about the Mersenne Twister.

Need extra Snowball Game instances? Pop them up in a new tab from https://snowball2.kringlecastle.com.

While system time is probably most common, developers have the option to seed pseudo-random number generators with other values.

Solution

Shall we play a game?

Let's start by playing a game on Easy. We can use the randomly generated name, but copy it because we're gonna want it again in a moment. As you play the game on Easy, you will notice that it is nearly impossible to lose. After beating the game once, play it again but use the same name as the first game. You'll notice that the location of all of the fort walls is exactly the same. This is because the game is using the name as the seed to the pseudorandom number generator (PRNG).

OK, easy enough. Let's try it on Hard. Hard does not allow us to choose a name, but does show us the name that was used. What if we took that name, opened another instance of the game (in another browser or tab), used that as the name for an Easy game, then used our knowledge of the wall locations from the Easy game to beat the Hard game? Awesome, now we can beat the game on Hard.

Now let's play the game on Impossible. Impossible is aptly named, as the computer never misses, so beating the level by 'luck' is very unlikely because you can never miss. Instead, we need to know where the walls are just like the computer does. On Impossible, the game does not let you pick a name, and doesn't even show it to you so the trick to beat Hard won't work directly. However, Tangle tells us that the game rejects some number of player names before settling on a name that is "random enough." These rejected names are added as an HTML comment in the page. If we use the browser's Development Tools to access the underlying HTML, we see the list in the comments of the game iframe. If you copy this list out and count them, you'll find 624 32-bit integers.

If you haven't already, now would be a good time to watch Tom Liston's talk on the Mersenne Twister PRNG, as this is the PRNG used by the Python random module.

The short version of Tom's talk is that while the Mersenne Twister PRNG (specifically the variant called MT19937) passes most statistic tests for randomness, it is not a cryptographically secure pseudorandom number generator (CSPRNG). A CSPRNG has the additional requirement that given any or all of the CSPRNG's past output, the future values cannot be reliably predicted. This is not the case with MT19937 - given 624 previously generated 32-bit values, all future outputs can be predicted with no error.

Conveniently, we happen to have 624 32-bit values and want to know what the next value would be. Using mersenne-twister-predictor we can take the discarded names and know what the next value (the game name and thus the random seed) was. With this knowledge, we can beat Impossible with the same process as Hard.

snowball_fight.py performs these steps for you, and will give you the coordinates of all of the walls. Start the game on Impossible from the Holiday Hack window (the game has to be beaten through the iframe or your achievement will not be recorded), copy the HTML comment element containing the discarded names, and paste them into a text file (the file can include the beginning text of the comment - it will be ignored). The script will predict the game's seed, then use web sockets to play the game on Easy and find the location of the walls. Then use the location of the walls to win on Impossible!

$ head input.txt          
<!--
    Seeds attempted:

    2547467952 - Not random enough
    719357570 - Not random enough
    3476536038 - Not random enough
    3330753950 - Not random enough
    2464956473 - Not random enough
    69475636 - Not random enough
    151438166 - Not random enough

$ python3 snowball_fight.py input.txt
[+] Welcome to the Snowball Fight game solver
[+] Determining the value used as the game seed
[+] Game seed: 1747545210
[+] Playing on Easy to determine the location of the fort walls
(2, 3)
(2, 4)
(2, 5)
(2, 6)
(2, 7)
(3, 0)
(4, 0)
(4, 1)
(4, 5)
(4, 6)
(4, 7)
(5, 1)
(6, 1)
(7, 1)
(8, 7)
(8, 8)
(8, 9)
[+] Done, 17 walls found!