Naughty/Nice List with Blockchain Investigation Part 1⚓︎
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)
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.
MD5 Hash Collisions
If you have control over to bytes in a file, it's easy to create MD5 hash collisions. Problem is: there's that nonce that he would have to know ahead of time.
Predicting the nonce for block 130000 requires recreating or cloning the state of the Mersenne Twister pseudo random number generator (PRNG) that was originally used to generate the nonce values in the blockchain.
To do this we require a few things. As Santa, grab the
blockchain.dat file from the desk in your office. We also need the
naughty_nice.py script from the official Naughty/Nice Blockchain education pack so we can load the
blockchain.dat file and extract the nonces. Finally, grab a copy of Tom Liston's
mt19937.py script that will allow us to clone a Mersenne Twister PRNG.
Two libraries, same outcome
mt19937.py script is an implementation of a 32-bit MT19937 PRNG. The nonces in the
blockchain.dat file however are 64-bit integers. A little bit of extra work is required to first convert the 64-bit nonces to 32-bit integers.
An alternative 32-bit Mersenne Twister Python implementation which already supports multiples of 32-bit integer sizes is Kimiyuki Onaka's mersenne-twister-predictor library. The final
generate_nonce.py script solves the challenge using both libraries to help explain how a 32-bit Mersenne Twister PRNG state can be recreated using 64-bit integers and how we can then use the 32-bit PRNG to predict the next 64-bit values.
To generate the nonce for block 130000, open
blockchain.dat (line 3) and read all the nonce values into a list (lines 12-13).
1 2 3 4 5 6 7 8 9 10 11 12 13
1 2 3 4 5 6 7
The internal state of a 32-bit Mersenne Twister is tracked using an array of 624 32-bit integer values. Because we can split our 64-bit nonce values into two 32-bit parts we need at least 312 64-bit nonces to recreate the internal state of the PRNG. For
kmyk this 64-bit to 32-bit conversion is handled behind the scenes and we just need to specify the bit size as a parameter (line 3).
tliston implementation we need to split the 64-bit nonce into two 32-bit integers ourselves before sending each part through the PRNG's
untemper() function. The first 32-bit integer is simply the lower 32 bits of the 64-bit nonce (line 9). The second 32-bit integer is created by right-shifting the upper half of the nonce by 32 bits (line 11).
1 2 3 4 5 6 7 8 9 10 11 12
We don't use the final 5 nonce values to clone the PRNG because we need something to compare our predicted values against. Generating the next 5 numbers using
kmyk (line 8) and
tliston (line 10) should match the last 5
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
Generating 64-bit random numbers
To use a 32-bit Mersenne Twister PRNG to generate a 64-bit integer, generate two 32-bit random numbers and combine them together into a 64-bit value by using the reverse process used for splitting a 64-bit number into two 32-bit values. This is exactly what the
extract_number_64() function does.
1 2 3 4 5 6 7 8 9
generate_nonce.py script to verify that everything is working as intended.
The 5 generated values from both cloned PRNGs match up with the 5 final nonce values from the
blockchain.dat file. The final part of the script uses the
kmyk (line 6) and
tliston (line 8) PRNGs to predict the next 4 nonces up to block 130000.
1 2 3 4 5 6 7 8 9 10 11 12 13 14