11a. Naughty/Nice List with Blockchain Investigation Part 1

Introduction

Tangle Coalbox in the Speaker UNPreparedness room after completing Snowball Fight

Crikey - that's it! You've done the Impossible! You've impressed this old elf today.

Great work identifying and abusing the pseudo-random sequence.

Now, the REAL question is, how else can this be abused? Do you think someone could try and cheat the Naughty/Nice Blockchain with this?

Objective

Hints

• MD5 Hash Collisions

Solution

The following files should be retrieved to complete this objective:

• The Naught/Nice Blockchain from Santa's desk - https://download.holidayhackchallenge.com/2020/blockchain.dat
• The suggested tools to help - https://download.holidayhackchallenge.com/2020/OfficialNaughtyNiceBlockchainEducationPack.zip

Rabbit hole

I initially started down a path of trying to create a 64-bit version of the Mersenne Twister Predictor

Well this was a waste of time.

I looked at the following to see if I could create mt19937_64:

• Find the appropriate parameter values at http://www.cplusplus.com/reference/random/mt19937_64/

• Comparing https://docs.rs/mersenne_twister/1.1.1/src/mersenne_twister/mt19937_64.rs.html with https://docs.rs/mersenne_twister/1.1.1/src/mersenne_twister/mt19937.rs.html

• and http://www.math.sci.hiroshima-u.ac.jp/m-mat/MT/VERSIONS/C-LANG/mt19937-64.c with http://www.math.sci.hiroshima-u.ac.jp/m-mat/MT/VERSIONS/C-LANG/980409/mt19937-1.c

I read the code at https://gist.github.com/Rhomboid/b1a882c70b7a1901efa9 and found out that the Python operator '//' is Floor division.

I also read the documentation from https://github.com/kmyk/mersenne-twister-predictor again and at https://mersenne-twister-predictor.readthedocs.io/en/latest/mt19937predictor.html. I even tested the example at the latter URL using 64 instead of 32 to see if it would work and it did. But I did not realise what I was doing.

I read the wikipedia page at https://en.wikipedia.org/wiki/Mersenne_Twister and about this implementation.

And this is Tom Liston's initial version: https://github.com/tliston/mt19937

It was only when I saw a message on the discord channel that said something like try reading the "as a library" section at https://github.com/kmyk/mersenne-twister-predictor that I finally realised what had to be done.

The starting point for this solution is the "as a library" example at https://github.com/kmyk/mersenne-twister-predictor.

In addition, the file naught_nice.py from OfficialNaughtyNiceBlockchainEducationPack.zip is needed for the classes Chain and Block.

The code that I developed is shown below:

#!/usr/bin/python3

from naughty_nice import Chain
from mt19937predictor import MT19937Predictor

# create the predictor
predictor = MT19937Predictor()

# read in the blockchain
c2 = Chain(load=True, filename='blockchain.dat')

# use 624 samples but make them go up to 5 prior to the end of the blockchain
# these will be used to prepare the predictor
for i in range((len(c2.blocks) - 624 - 5), (len(c2.blocks) - 5)):
    predictor.setrandbits(c2.blocks[i].nonce, 64)

# verify the predictions match for the last 5 blocks in the blockchain
for i in range((len(c2.blocks) - 5), (len(c2.blocks))):
    nonce = hex(c2.blocks[i].nonce)
    prediction = hex(predictor.getrandbits(64))
    print((128449 + i), ":", nonce, "-", prediction, "(", ("match" if nonce == prediction else "doesn't match"), ")")

# predict the values forward to block 130000
for i in range((len(c2.blocks)), (len(c2.blocks) + 4)):
    print((128449 + i), ":" ,"prediction", "-", hex(predictor.getrandbits(64)))

Answer

57066318f32f729d