Objective 11a: 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 hash)
TL;DR - Answer
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.
When we talk to Tinsel Upatree we are given the Official Naughty Nice Blockchain Education Pack which contains a few files of interest:
- naughty_nice.py - the code to manipulate and verify the blockchain
- official_public.pem - the public component of the RSA key that signs all blocks
- private.pem - a private RSA key to use for testing
- docker.sh and Dockerfile - setup a docker image to run naughty_nice.py; not really necessary
In additional to the Education Pack, we will also need the slice of the blockchain that can be found on Santa's desk.
The attack for this objective is an extension of the same attack used to beat Snowball Fight, so it's advised to complete that challenge first.
After beating Snowball Fight we know that the
random module in Python uses the MT19937 implementation of the Mersenne Twister PRNG. MT19937 is a statistically sound PRNG, but it is not cryptographyically secure because the next output can be predicted precisely if enough of the previous outputs are known. More specifically, given 624 32bit integers output from the PRNG, all future values can be predicted without error.
This attack applies to the Naughty/Nice list because looking at
naughty_nice.py we see that the
randrange function of the
random module is used to set the
175 176 177 178 179 180 181 182 183 184 185 186
Based on the function call, and the specifications of a naughty/nice block, we know that the nonce will be 64 bits. This requires three changes from Snowball Fight:
- We must use
setrand_int32since we are dealing with 64 bit values rather than 32 bit values
- We must use
genrand_int32for the same reason as above
- Since each previous
nonceprovides 64 bits of previous values, we only need 312 (624/2) of these values
For this particular attack we assume the
random module has not been reseeded during the range of time we're interested in (by calling
random.seed or restarting the process). If it had been, the attack would only be successful if there were enough previous bits (312 * 64) since the last reseed.
Other than the bitness changes, the attack proceeds the same. We extract the
nonce from all previous blocks, and use them to predict the
nonce for the next few blocks. analyze_nn_list.py provides a function to print the next
c nonces given a naughty/nice blockchain.
$ python3 analyze_nn_list.py predict -c 10 blockchain.dat 129996: 16969683986178983974 (0xeb806dad1ad54826, last block of chain) 129997: 13205885317093879758 (0xb744baba65ed6fce) 129998: 109892600914328301 (0x1866abd00f13aed) 129999: 9533956617156166628 (0x844f6b07bd9403e4) 130000: 6270808489970332317 (0x57066318f32f729d) 130001: 3451226212373906987 (0x2fe537f46c10462b) 130002: 13075056776572822761 (0xb573eedd19afe4e9) 130003: 14778594218656921905 (0xcd181d243aaff931) 130004: 6725523028518543315 (0x5d55db8fa38e9fd3) 130005: 8533705287792980227 (0x766dcfbee8c5f103)