Skip to content

Objective 11a: Naughty/Nice List with Blockchain Investigation Part 1

Difficulty:

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

Hints

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.

Solution

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 nonce value

175
176
177
178
179
180
181
182
183
184
185
186
...
if(load == False):
    if all(p is not None for p in [index, block_data['documents'], block_data['pid'], block_data['rid'], block_data['score'], block_data['sign'], previous_hash]):
        self.index = index
        if self.index == 0:
            self.nonce = 0 # genesis block
        else:
            self.nonce = random.randrange(0xFFFFFFFFFFFFFFFF)                
        self.data = block_data['documents']
        self.previous_hash = previous_hash
        self.doc_count = len(self.data)
...

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:

  1. We must use setrandbits rather than setrand_int32 since we are dealing with 64 bit values rather than 32 bit values
  2. We must use getrandbits rather than genrand_int32 for the same reason as above
  3. Since each previous nonce provides 64 bits of previous values, we only need 312 (624/2) of these values

Note

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)

Answer

57066318f32f729d