Blockchain Investigation Part 1

At first glance, this seems like a tough one, so I go to talk with Tangle Coalbox in the Speaker Unpreparedness Room to get some help.

First though, he needs my help with his SnowBall Game terminat. He says that people were solving it on IMPOSSIBLE level, which should really be impossible:

Howdy Boss. You look a tad flushed. Can I get you some water from the vending machine? I’m still looking into the Snowball Game like you asked. I read the write-up of the test completed earlier this summer with the web socket vulnerabilities. I was able to complete the Easy level, but the Impossible level is, umm… I’d call it impossible, but I just saw someone beat it! Is it possible that the name a player provides influences how the forts are laid out? Oh, oh, maybe if I feed a Hard name into an Easy game I can manipulate it! UGH! on Impossible, the best I get are rejected player names in the page comments… maybe that’s useful? I’ll have to re-watch Tom Liston’s talk again ( LINK). Thanks for all the tips and encouragement Santa!

It seems I am tasked with solving the game on IMPOSSIBLE difficulty to see how the others have done it. Following Tangle’s advice, I watch the KringleCon talk by Tom Liston on PRNGs that offers essential information. To get started, I click on the machine which pops up the below welcome screen. I make sure to read the instructions very carefully, at least twice:

Levels Easy & Medium are indeed quite simple to solve without any trickery. It gets interesting once I start playing with the input box for my Name: this value is used as a seed for a random generator that creates the board. The same value always results in the same board setup.

On IMPOSSIBLE difficulty this value is redacted but I think there is a way I may try to predict it using the script from Tom Liston’s talk. To get to the redacted value I need a certain amount of random numbers generated to clone the internal state of the Mersenne Twister that’s used as the generator. Quite unexpectedly, there is a dump of discarded random values in the game’s page source:

Next I formulate the below plan to solve it on IMPOSSIBLE difficulty:

1. Start a new game on IMPOSSIBLE difficulty
2. Grab discarded random values from the HTML source
3. Feed these values to a modified version of Tim’s scipt to predict next value
4. Start a new game on EASY mode with the predicted number from step #2
5. Verify that both open games have identical setup by comparing your side of the table
6. Solve game on Easy mode manually, then replay it on the other game hitting only known cells
7. Collect hints from Tangle

The code I wrote is based on Tim’s python code, with the main changed to:

1if __name__ == "__main__":
2    my_random = mt19937(0)
3    with open("random.txt") as fp: 
4	    i = 0
5	    for line in fp.readlines(): 
6	        my_random.MT[i] = untemper(int(line))
7	        i+=1
8    print(f"Next int: {my_random.extract_number()}")

First it creates a new instance of the Mersenne Twister, then loads the discarded random values from a file called random.txt and uses them to clone the internal state of the generator used to create the game board. Finally, it generates the next random number which is used to start a new game on EASY level so that I can figure out the cells I need to hit on IMPOSSIBLE:

Finally, Tangle is ready to share his hints:

Wow, it really was all about abusing the pseudo-random sequence! I’ve been thinking, do you think someone could try and cheat the Naughty/Nice Blockchain with this same technique? I remember you told us about how if you have control over to bytes in a file, it’s easy to create MD5 hash collisions. But the nonce would have to be known ahead of time. We know that the blockchain works by “chaining” blocks together. There’s no way you know who could change it without messing up the chain, right Santa? I’m going to look closer to spot if any of the blocks have been changed. If Jack was able to change the block AND the document without changing the hash… that would require a very UNIque hash COLLision. Apparently Jack was able to change just 4 bytes in the block to completely change everything about it. It’s like some sort of evil game to him. I think I need to review my Human Behavior Naughty/Niceness curriculum again.

I also get some useful links from him:

• GitHub repo about MD5 Hash Collisions
• GitHub repo about MD5 & SHA-1 cryptanalysis
• Presentation on Hash Collisions Exploitations
• KringleCon Talk from Prof. Qwerty Petabyte on Working with the Official Naughty/Nice Blockchain…

For some extra hints I stop by in Santa’s office to talk with Tinsel Upatree:

Howdy Santa! Just guarding the Naughty/Nice list on your desk. Santa, I don’t know if you’ve heard, but something is very, very wrong… We tabulated the latest score of the Naughty/Nice Blockchain. Jack Frost is the nicest being in the world! Jack Frost!?! As you know, we only really start checking the Naughty/Nice totals as we get closer to the holidays. Out of nowhere, Jack Frost has this crazy score… positive 4,294,935,958 nice points! No one has EVER gotten a score that high! No one knows how it happened. Most of us recall Jack having a NEGATIVE score only a few days ago… Worse still, his huge positive score seems to have happened way back in March. Our first thought was that he somehow changed the blockchain - but, as you know, that isn’t possible. We ran a validation of the blockchain and it all checks out. Even the smallest change to any block should make it invalid. Blockchains are huge, so we cut a one minute chunk from when Jack’s big score registered back in March. You can get a slice of the Naughty/Nice blockchain on your desk. You can get some tools to help you here. Tangle Coalbox, in the Speaker UNPreparedness room. has been talking with attendees about the issue.

Next I download the tools mentioned by Tinsel as well as the blockchain file which is necessary for solving the main objective.

The two pem files are not important so much for Objective11a. The bash script, and the Dockerfile are there just for the easy setup of an environment where the python script runs without dependency issues. With the provided python script I can interact with the blockchain.dat file and extract all the information needed for solving the objective.

The instructions tell me that the blockchain stops at index 129996, and my task is to predict the nonce for block 130000 and submit its HEX value in the badge. This naturally reminds me of the SnowBall Game, so I figure that the same script may be useful here too. I proceed to extract the nonce values from all the blocks and notice that there are roughly 1500 blocks altogether, plenty more than 624, so that’s good! Meanwhile, I also notice that these nonce values are much larger than the random values that I dealt with in the SnowBall Game. In fact, that game used 32 bit random integers, while this blockchain uses 64 bit integers as nonces.

Next I try to modify Tom Liston’s script to produce 64 bits random values instead of 32 bits. I eventually succeed in this following an example. However, the nonce it generates is not accepted. Next I get in touch with some fellow KringleCon attendees via Discord to discuss my approach to try see if I am in a rabbit hole or not.

Eventually I realize that the script does not need to be modified, as the sstem that created the blockchain also used a PRNG that produces 32 bit long random values. Rather, the nonce value in each block is constructed from two independent random values. Part of the challenge is to figure out how they are combined to turn them into a 64 bit random values.

Next I tweak the naughty_nice.py script to take the first 312 nonce values and feed them into the script from Tom Liston’s by splitting each nonce in half. By trial and error I figure out the correct method that’s implemented below:

 1c2 = Chain(load=True, filename='blockchain.dat')
 2
 3twister, i = mt19937(0), 0
 4for block in c2.blocks[:312]:
 5    twister.MT[i] = untemper(block.nonce & 0x00000000FFFFFFFF); i+=1
 6    twister.MT[i] = untemper(block.nonce >> 32); i+=1
 7
 8for block in c2.blocks[312:]:
 9    print(f"\nReal nonce: \t{block.nonce} at index {block.index}")
10    print(f"Predicted: \t{get_next(twister)}")
11
12for i in range(4):
13    print(f"Hex-#{i+129997}: \t{hex(get_next(twister))}")

The output shows that starting from block 313, all of the nonce values from the blocks are identical with the value produced by the cloned generator I created. Finally, I take the hex value for block 130000 and submit it in my badge, which is accepted:

 1...
 2Real nonce:   7556872674124112955 at index 129995
 3Predicted:    7556872674124112955
 4Real nonce:   16969683986178983974 at index 129996
 5Predicted:    16969683986178983974
 6
 7Hex-#129997:  0xb744baba65ed6fce
 8Hex-#129998:  0x1866abd00f13aed
 9Hex-#129999:  0x844f6b07bd9403e4
10Hex-#130000:  0x57066318f32f729d

On to the final objective! 😎