SANS Holiday Hack Challenge 2020: Objective 11a — Naughty/Nice List with Blockchain Investigation Part 1
Each year, the SANS and Counter Hack Challenges teams put together my favorite capture the flag (CTF) competition, the SANS Holiday Hack Challenge. The 2020 SANS Holiday Hack Challenge, featuring KringleCon 3: French Hens! was held at Santa’s newly renovated castle at the North Pole from December 10, 2020 to January 11, 2021. This is a walk-through for an objective from the event.
Objective 11a) Even though the chunk of the blockchain that you have ends with block 129996, can you predict the nonce for block 130000? Talk to Tangle Coalbox in the Speaker UNpreparedness Room for tips on prediction and Tinsel Upatree for more tips and tools. (Enter just the 16-character hex value of the nonce).
I started by watching the video by Prof. Qwerty Petabyte to have a better understanding of how the Naughty/Nice Blockchain worked. Some key things I pulled out of this talk was that the blockchain was implemented in Python, meaning that the nonce was likely generated using Python’s Mersenne twister-based PRNG.
I downloaded the tools provided and spun up the blockchain. To start, I commented out the code in the main function and un-commented the block of code that would allow me to read blockchain blocks from a file named
blockchain.dat. Then I used a Python debugger to interact with the blockchain. I determined that I had about 1,500 blocks in the file I was given, plenty for taking advantage of issues with the Mersenne twister.
I iterated through the blocks and printed the nonce value to the screen for several of them. This revealed my first hurdle: the nonce values were 64-bit values and my script from the Snowball terminal game only worked on 32-bit values. I began updating the script to support 64-bit values. I did this in a copy of the
mt19937.py file called
my_64_mt19937.py. My goal here was to create a version of that file that would work on 64-bit values.
To figure out where to go with this, I looked at the Python source code to see how it implemented the same code for values larger than 32-bits. I am thankful for the Kringlecon Discord community for pointing me in the right direction with this. It turns out that Python deals with generating 64-bit values by calculating two 32-bit values and combining them.
To mimic this 64-bit behavior, I created a new method in the
mt19937 class in that file called
extract_64_number() which would be called in place of
extract_number() when I need to get the next predicted 64-bit number. Based on what I learned about Python’s implementation, all I needed to do was call extract_number twice and save the results of the first call into the low bits of the returned value and the results of the second call into the high bits of the returned result. I implemented that as follows. The decision on which results to place into the low and high bits was based on the endianness of the system the script was running on.
Next, I updataed the untemper process to reflect 64-bit numbers as well. Since the creation of a 64-bit number occurred by combining two generated numbers, the untemper process should work by splitting the provided value into two 32-bit numbers and calling untemper on each. To support this, I wrote the following helper function to split a 64-bit value into two 32-bit values which could each be untempered.
Finally, I updated the code in main to reflect the new process. Any references to
0xffffffff were replaced with
0xffffffffffffffff to indicate a 64-bit value should be generated. Where the code previously called
untemper(random.randrange(0xFFFFFFFF)), I updated it to generate a random 64-bit value, split it into low bits and high bits, and then untemper each. Then I replaced any references to
extract_64_number(). The final code for the main function is shown below.
When I ran this, it confirmed that I successfully predicted the next 20 values of the PRNG.
With a 64-bit PRNG predictor available, I moved on to predicting the value of the 130000th block. First, I added an import to bring in my 64-bit PRNG predictor:
from my_64_mt19937 import mt19937, untemper, split_64.
I updated the main code in my class as follows. First, I read the blocks in from the
blockchain.dat file and stored the nonce value of each block in a list object called
nonce_list. I populated the
myprng object (an instance of the
mt19937 class) with 624 seed values pulled from the first 312 nonce values from
nonce_list using the logic I had figured out previously for untempering 64-bit values. Then I threw out all the values between where I left off in the
nonce_list and the end of the
nonce_list with the exception of the last nonce. I printed that to the screen along with my prediction to ensure that I could successfully predict the nonce values. Since my nonce list ended at index 129996, I then printed out the predicted nonces for the values between 129997 and 129999. Finally, I generated one last 64-bit nonce value for index 130000. I printed this along with its hex output to the screen. The code for this follows:
I ran this script and got the following output. I was able to confirm that I successfully predicted the nonce value for the last block (index 129996 ) and that the nonce value for the desired block (index 130000) would be 6270808489970332317 or 57066318f32f729d when represented in hex. I entered this into my badge and successfully completed the challenge.
Interested in learning more about the 2020 SANS Holiday Hack Challenge? Check out my other walk-throughs available here.