Holiday Hack 2020: Naughty/Nice List with Blockchain Investigation
Objective
Terminal - Snowball Fight
Challenge
There’s another archade game in the Speaker Unpreparedness room, Snowball Fight, and Tangle Coalbox is standing next to it:
Howdy gumshoe. I’m Tangle Coalbox, resident sleuth in the North Pole.
If you’re up for a challenge, I’d ask you to look at this here Snowball Game.
We tested an earlier version this summer, but that one had web socket vulnerabilities.
This version seems simple enough on the Easy level, but the Impossible level is, well…
I’d call it impossible, but I just saw someone beat it! I’m sure something’s off here.
Could it be that the name a player provides has some connection to how the forts are laid out?
Knowing that, I can see how an elf might feed their Hard name into an Easy game to cheat a bit.
But on Impossible, the best you get are rejected player names in the page comments. Can you use those somehow?
Check out Tom Liston’s talk for more info, if you need it.
Solution
Game
The challenge opens up with a menu to select a difficulty and a player name:
Clicking play loads a game like Battleship:
Some experimentation proves what Tagle and the splash screen suggested - giving the same name produces the same game board on the enemy’s side, which implies that the placement of the ships is somehow calculated based on the name input.
The difficulty of the game doesn’t impact the ship placement. It only impacts how good a shot the computer is (on insane it doesn’t miss), and how the name is set. For Easy and Medium, the player sets the name. For Hard, it’s set by the computer and displayed to the user like above. For Impossible!, it’s set by the computer and redacted:
Also for Impossible!, there is a comment in the HTML which gives 624 unused seeds (names) that are not used before redacting the userd one, presumably the one that follows:
It’s important to use the dev tools to view the page I’m actually view, and not “view-source”, which requests a new copy of the same page, and will get different numbers.
Calculate Name
Mersenne Twister is a widely used pseudo random number generator (PRNG). There are attacks against it where if you know the previous 624 values to come out of the PRNG, you can calculate the next value. Tom Listen gave a talk on this at this years KringleCon.
Since there are 624 unused values in the comments for the Impossible! level, I’ll assume those are the previous values to come out of the site. I’ll try to use those to calculate the value for the current came. First, copy those seeds into a file:
$ wc -l rejects
624 rejects
$ head rejects
2943688594 - Not random enough
529760399 - Not random enough
3341229050 - Not random enough
3370692404 - Not random enough
3346136354 - Not random enough
1025288101 - Not random enough
4092998779 - Not random enough
2472302771 - Not random enough
1630727217 - Not random enough
2274450635 - Not random enough
I want just the seeds in a file, so I’ll use awk to isolate the numbers and sponge to write back to the same file:
$ cat rejects | awk '{print $1}' | sponge rejects
$ head rejects
2943688594
529760399
3341229050
3370692404
3346136354
1025288101
4092998779
2472302771
1630727217
2274450635
mersenne-twister-predictor will take 624 32-bit integers and return the next numbers that will be generated. The example on the page will run until killed and make a lot of numbers. I’ll just use head -1 to get the next one, as that’s all that’s needed:
root@kali# mt19937predict rejects | head -1
3963570317
Now I can open another window and play easy with this name.
Once I know where all the ships are (I’ve yet to send (8,5), as that will clear the screen), I can go back to the Impossible window and hit every shot:
It is important to do the impossible in the in-game window to get credit for solving.
Naughty/Nice Part 1
Hints
Tangle suggests applying this same technique to the Naughty/Nice list:
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?
If you have control over to bytes in a file, it’s easy to create MD5 hash collisions.
One hint added in the badge:
- 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.
Talking to Tinsel Upatree in Santa’s Office as Santa will also provide context for this challenge:
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.
The tools link provides OfficialNaughtyNiceBlockchainEducationPack.zip, and I can download blockchain.dat from the scroll on the table.
Understand Tools
The tools come with a Docker image, a public/private key pair, and a Python file:
$ unzip -l OfficialNaughtyNiceBlockchainEducationPack
Archive: OfficialNaughtyNiceBlockchainEducationPack.zip
Length Date Time Name
--------- ---------- ----- ----
311 2020-12-08 17:37 OfficialNaughtyNiceBlockchainEducationPack/Dockerfile
638 2020-12-08 17:37 OfficialNaughtyNiceBlockchainEducationPack/docker.sh
22301 2020-12-08 20:21 OfficialNaughtyNiceBlockchainEducationPack/naughty_nice.py
450 2020-11-24 18:14 OfficialNaughtyNiceBlockchainEducationPack/official_public.pem
1679 2020-11-24 18:14 OfficialNaughtyNiceBlockchainEducationPack/private.pem
--------- -------
25379 5 files
The Python file is really well documented, and contains two classes that can be used to interact with the blockchain.
I can import this file, and then load the .dat file into it:
>>> import naughty_nice
>>> c = naughty_nice.Chain(load=True, filename='blockchain.dat')
Now I can interact with the blocks:
>>> len(c.blocks)
1548
>>> c.blocks[0]
Chain Index: 128449
Nonce: e3e12de5edfb51e2
PID: 0803508ada0a5ebf
RID: aecbf777616d9fa4
Document Count: 1
Score: 000000dc (220)
Sign: 1 (Nice)
Data item: 1
Data Type: 05 (PDF)
Data Length: 000003a7
Data: b'255044462d312e330a332030206f626a0a3c3c2f54797065202f506167650a2f506172656e742031203020520a2f5265736f75726365732032203020520a2f436f6e74656e74732034203020523e3e0a656e646f626a0a342030206f626a0a3c3c2f46696c746572202f466c6174654465636f6465202f4c656e677468203138323e3e0a73747265616d0a789c658eb10e82301884779ee212174da4b4a550ba9ae8e0dc1728e1078a501240797d51e3609c2eb9bbdc7712d788b34c638d4e16c9454048c6396c8db37d59a960c240a94d72d80a7bdb4e4458fc4008e37ac4c985ce0d3e60753366a280927c68e0f0a0c68523cafb82400f9a30b8db27297d838a5c8f71cbc61a7e6107d8ee17b91d29c41b79eeeb780cf1d2523cb7d4d7d80999994ca5b2d0ca68a3722db4fc5b484dc172f55e4813a912c925ff969e1a4c421d0a656e6473747265616d0a656e646f626a0a312030206f626a0a3c3c2f54797065202f50616765730a2f4b696473205b3320302052205d0a2f436f756e7420310a2f4d65646961426f78205b302030203631322e3030203739322e30305d0a3e3e0a656e646f626a0a352030206f626a0a3c3c2f54797065202f466f6e740a2f42617365466f6e74202f54696d65732d526f6d616e0a2f53756274797065202f54797065310a2f456e636f64696e67202f57696e416e7369456e636f64696e670a3e3e0a656e646f626a0a322030206f626a0a3c3c0a2f50726f63536574205b2f504446202f54657874202f496d61676542202f496d61676543202f496d616765495d0a2f466f6e74203c3c0a2f46312035203020520a3e3e0a2f584f626a656374203c3c0a3e3e0a3e3e0a656e646f626a0a372030206f626a0a3c3c0a2f54797065202f436174616c6f670a2f50616765732031203020520a2f4f70656e416374696f6e205b3320302052202f46697448206e756c6c5d0a2f506167654c61796f7574202f4f6e65436f6c756d6e0a3e3e0a656e646f626a0a787265660a3020380a303030303030303030302036353533352066200a30303030303030333339203030303030206e200a30303030303030353234203030303030206e200a30303030303030303039203030303030206e200a30303030303030303837203030303030206e200a30303030303030363238203030303030206e200a30303030303030373337203030303030206e200a747261696c65720a3c3c0a2f53697a6520380a2f526f6f742037203020520a3e3e0a7374617274787265660a3834300a2525454f460a0a'
Date: 03/24
Time: 13:21:00
PreviousHash: c6e2e6ecb785e7132c8003ab5aaba88d
Data Hash to Sign: 03cfb11504b8eee93b26aeb0d8ac39ff
Signature: b'PT4OZUq+vwfNDhqipxwt28NC4Hd7dw6N1i4XHMGkIMR53qy8dF47YwpqzEjW0EAbUYPZ+b/E4X3YjXUTI0VnoJ2VsJQWtIPwcGIk5ayMfe5dgrjuLle5NUyEpd1EpIPdiSLMnyvbJEzG3HfA2dpkNsXWtO/D5wFYWGEErAt/PyH9CK/QuV5w3ArCwEmM61KWV7XTmC38EQoIm9iz5QQIIBU2onlZUcBlZ81N+H8pL/utpArkLppSwdRdx5f2kHUTLM7I2egDAdHhQ5zPAbZLoJ03HYjEBGKXiSQjAGhqY47U2DmliyOEehchTmmq+JiBF3ozXiV5hm89y/mN2uUzmQ=='
Predicting Nonces
The nonces are 64-bit ints. For example:
>>> hex(c.blocks[0].nonce)
'0xe3e12de5edfb51e2'
To calculate them, I’ll use the same library I used in the Snowball Fight game, mersenne-twister-predictor, this time, inside Python. When it was using 32-bit ints, I needed to give it 624 values to then get the next one. Since the nonces are 64-bit (twice as long), I need only half as many to predict the next. I’ll use blocks 0 to 311 to fill in the predictor:
>>> from mt19937predictor import MT19937Predictor
>>> predictor = MT19937Predictor()
>>> for b in c.blocks[:312]:
... predictor.setrandbits(b.nonce, 64)
...
The nonce for block 312 matches the predictor’s calculation:
>>> hex(predictor.getrandbits(64))
'0xd177a402ebe05817'
>>> hex(c.blocks[312].nonce)
'0xd177a402ebe05817'
With that understanding, this script will give the answer to the challenge:
#!/usr/bin/env python3
import naughty_nice
from mt19937predictor import MT19937Predictor
c = naughty_nice.Chain(load=True, filename='blockchain.dat')
predictor = MT19937Predictor()
for b in c.blocks:
predictor.setrandbits(b.nonce, 64)
for i in range(c.blocks[-1].index+1, 130001):
print(f'Block {i} nonce: {predictor.getrandbits(64):016x}')
Running it prints the following nonces up to index 130000, which is the one needed to solve the objective:
$ python3 11a.py
Block 129997 nonce: b744baba65ed6fce
Block 129998 nonce: 01866abd00f13aed
Block 129999 nonce: 844f6b07bd9403e4
Block 130000 nonce: 57066318f32f729d
Flag: 57066318f32f729d
Naught/Nice Part 2
Hints
No terminal or elves for this one, but there are hints in the badge from the previous terminal:
- Qwerty Petabyte is giving a talk about blockchain tomfoolery!
- The idea that Jack could somehow change the data in a block without invalidating the whole chain just collides with the concept of hashes and blockchains. While there’s no way it could happen, maybe if you look at the block that seems like it got changed, it might help.
- Apparently Jack was able to change just 4 bytes in the block to completely change everything about it. It’s like some sort of evil game to him.
- A blockchain works by “chaining” blocks together - each new block includes a hash of the previous block. That previous hash value is included in the data that is hashed - and that hash value will be in the next block. So there’s no way that Jack could change an existing block without it messing up the chain…
- If Jack was somehow able to change the contents of the block AND the document without changing the hash… that would require a very UNIque hash COLLision.
- Shinny Upatree swears that he doesn’t remember writing the contents of the document found in that block. Maybe looking closely at the documents, you might find something interesting.
Find Tampered Block
The challenge states that the modified block has a specific SHA256 hash. This script should identify it:
#!/usr/bin/env python3
import naughty_nice
from Crypto.Hash import SHA256
c = naughty_nice.Chain(load=True, filename='blockchain.dat')
target_hash = '58a3b9335a6ceb0234c12d35a0564c4ef0e90152d0eb2ce2082383b38028a90f'
for i,b in enumerate(c.blocks):
h = SHA256.new()
h.update(b.block_data_signed())
if h.hexdigest() == target_hash:
print(f'[+] Found block with target hash.\n Index {b.index}\n i in file: {i}')
c.save_a_block(i, filename='jf.block')
break
The index is 1010 in the given file, or 129459 overall:
$ python3 OfficialNaughtyNiceBlockchainEducationPack//11b.py
[+] Found block with target hash.
Index 129459
i in file: 1010
Looking at the block itself, it’s the max score, with a sign of nice. There are two attachments, a binary blob and a PDF:
>>> c.blocks[1010]
Chain Index: 129459
Nonce: a9447e5771c704f4
PID: 0000000000012fd1
RID: 000000000000020f
Document Count: 2
Score: ffffffff (4294967295)
Sign: 1 (Nice)
Data item: 1
Data Type: ff (Binary blob)
Data Length: 0000006c
Data: b'ea465340303a6079d3df2762be68467c27f046d3a7ff4e92dfe1def7407f2a7b73e1b759b8b919451e37518d22d987296fcb0f188dd60388bf20350f2a91c29d0348614dc0bceef2bcadd4cc3f251ba8f9fbaf171a06df1e1fd8649396ab86f9d5118cc8d8204b4
ffe8d8f09'
Data item: 2
Data Type: 05 (PDF)
Data Length: 00009f57
Data: b'255044462d312e330a...[snip]...
Date: 03/24
Time: 13:21:41
PreviousHash: 4a91947439046c2dbaa96db38e924665
Data Hash to Sign: 347979fece8d403e06f89f8633b5231a
Signature: b'MJIxJy2iFXJRCN1EwDsqO9NzE2Dq1qlvZuFFlljmQ03+erFpqqgSI1xhfAwlfmI2MqZWXA9RDTVw3+aWPq2S0CKuKvXkDOrX92cPUz5wEMYNfuxrpOFhrK2sks0yeQWPsHFEV4cl6jtkZ//OwdIznTuVgfuA8UDcnqCpzSV9Uu8ugZpAlUY43Y40ecJPFoI/xi+VU4xM0+9vjY0EmQijOj5k89/AbMAD2R3UbFNmmR61w7cVLrDhx3XwTdY2RCc3ovnUYmhgPNnduKIUA/zKbuu95FFi5M2r6c5Mt6F+c9EdLza24xX2J4l3YbmagR/AEBaF9EBMDZ1o5cMTMCtHfw=='
Evaluate Documents
Get PDF
I’ll dump the documents associated with this block:
>>> jf = c.blocks[1010]
>>> jf.dump_doc(1)
Document dumped as: 129459.bin
>>> jf.dump_doc(2)
Document dumped as: 129459.pdf
The .bin file is completely random. I can’t make anything out of it.
The .pdf is interesting. It’s full of nothing but praise for Jack Frost:
Clearly this is a fake.
Map IDs
A PDF file is a bunch of text sections describing objects, fonts, pages, images, and text, and the various sections point to each other.
pdfid and pdf-parser are two tools from Didier Stevens that are useful for parsing PDFs.
pdfid shows the various elements in a given PDF:
$ pdfid 129459.pdf
PDFiD 0.2.7 129459.pdf
PDF Header: %PDF-1.3
obj 23
endobj 23
stream 8
endstream 8
xref 1
trailer 1
startxref 1
/Page 2
/Encrypt 0
/ObjStm 0
/JS 0
/JavaScript 0
/AA 0
/OpenAction 0
/AcroForm 0
/JBIG2Decode 0
/RichMedia 0
/Launch 0
/EmbeddedFile 0
/XFA 0
/Colors > 2^24 0
When looking for malicious documents, it’s useful to look for elements like JS, javascript, and OpenAction. What stands out to me about this PDF is the two /Page objects, even though I only saw one page.
The /Catalog is the root of the file. An example /Catalog would look like:
obj 1 0
<<
/Type /Catalog
/Pages 2 0 R
/PageMode /UseOutlines
/Outlines 3 0 R
>>
Jack Frost’s PDF has the following /Catalog:
$ pdf-parser -o 1 129459.pdf
obj 1 0
Type: /Catalog
Referencing: 2 0 R
<<
/Type /Catalog
/_Go_Away /Santa
/Pages '2 0 R 0ùÙ¿W\x8e<ªå\rx\x8fç`ó\x1dd¯ª\x1e¡ò¡=cu>\x1a¥¿\x80bOÃF¿ÖgÊ÷I\x95\x91Ä\x02\x01í«\x03¹ï\x95\x99\x1c[I\x9f\x86Ü\x859\x85\x90\x99\xadT°\x1es?姤\x89¹2\x95ÿTh\x03MIy8èù¸Ë:ÃÏPð\x1b2[\x9b\x17tu\x95B+sxð%\x02á©°¬\x85(\x01z\x9e'
>>
There’s a few odd things. /_Go_Away /Santa is an interesting string, and suggests I’m on the right path. Also, there’s not typically this string of random junk in the /Pages string.
This element references element 2, a /Page object:
$ pdf-parser -o 2 129459.pdf
obj 2 0
Type: /Pages
Referencing: 23 0 R
<<
/Type /Pages
/Count 1
/Kids [23 0 R]
>>
That one references object 23, which references objects 16 and 17:
$ pdf-parser -o 23 129459.pdf
obj 23 0
Type: /Page
Referencing: 16 0 R, 17 0 R, 2 0 R
<<
/Type /Page
/Contents 16 0 R
/Resources 17 0 R
/MediaBox [0 0 612 792]
/Parent 2 0 R
>>
I can make a tree of the references:
1 Catalog
2 Page
23 Kids
16 Contents
17 Resources
18 Font
19 F1
20 FontDescriptor
21 FontFile
22 ToUnicode
But there’s another page object at object 3:
$ pdf-parser -o 3 129459.pdf
obj 3 0
Type: /Pages
Referencing: 15 0 R
<<
/Type /Pages
/Count 1
/Kids [15 0 R]
>>
Mapping it out:
3 Page
15 Kids
4 Contents
5 Resources
6 Font
7 F1
8 FontDescriptor
9 FontFile2
10 ToUnicode
11 F2
12 FontDescriptor
13 FontFile2
14 ToUnicode
This is basically an entire different document, just never referenced by the PDF. If I open the PDF in a text editor and change the Catalog to point to object 3 instead of object 2, it is a completely different PDF:
The document describes how Jack Front did something terrible, and Shinny was submitting him for max naughty points. I suspect that Jack arrange for this to happen, as well as the frozen pipes back at Shinny’s house, so he could submit the report.
MD5 Attack
Overview
Jack needed to submit this report as Shinny with the valid bad report, have it signed, and then go back and modify the block chain later so that the new report would show up but the report would still be valid. The reason he could do this is that the integrity of this blockchain is based on MD5 hashes.
In the hints there’s a fantastic presentation by Ange Albertini on hash attacks. It goes into a lot of attacks, but the one here is the UNICOLL attack. To pull off this attack, someone must start with a given document. There is a calculation that can be made such that what looks like random garbage will finish out that 64-byte block, as well as one block beyond it. Once that is there, you can add one to the 10th byte in the last legit block, and subtrack one from the 10th byte in the last random block, and the MD5 hash will stay the same. Also, you can append data to the end of the random block and it will still work.
Jack Frost did this attack twice on the block he submitted to the naught/nice blockchain - once on the naughty / nice flag, and once in the PDF.
Block
I’ll write the block in question to a file:
>>> with open('jf.block', 'wb') as f: f.write(jf.block_data_signed())
...
41411
The file outputs the hash given in the prompt:
$ sha256sum jf.block
58a3b9335a6ceb0234c12d35a0564c4ef0e90152d0eb2ce2082383b38028a90f jf.block
Click for full size imageIf Jack were to start with just the data leading up to the attached files, including the header data for the first file, shown in yellow highlight:
On running the UNICOLL attack, it will fill out the rest of this block and a full next block with random stuff. Then Jack can add one to the 10th byte in the second to last block, and subtract one from the 10th byte in the last block, and the MD5 won’t change. In this case, that byte he adds one to is the naughty/nice flag, so he can submit it as 0 (naughty), but later flip it to 1 (nice) just by changing the meaningless byte in the random attachment as well.
He can do then append his double path PDF to the block, including the header with file type (0x05) and size (0x9f57) up to the point where the page is defined (yellow highlight):
The random data generated in the attack gets appended as part of the /Pages string, and most PDF readers are forgiving enough to process through that. Jack can then append the rest of the PDF.
There are now two places that Jack can change without changing the MD5 of the document. So he submits the report (as Shinny) with max value and naughty, and the PDF pointing to the report Shinny wrote. Once it’s verified and in the system, he edits the block chain, incrementing the naughty/nice flag from 0 to 1 (and decrementing 0x40 bytes later in the random binary attachment), and then decrementing the /Catalog in the PDF to point to the other document (and incrementing the byte 0x40 later in the randomness in the string). This modified document still has the same MD5 hash, so the next block’s hash still shows it valid.
Undo It
To undo it, I’ll change four bytes in jf-mod.block using a hex editor:
$ diff <( xxd jf.block ) <( xxd jf-mod-block )
5c5
< 00000040: 3266 6666 6666 6666 6631 6666 3030 3030 2ffffffff1ff0000
---
> 00000040: 3266 6666 6666 6666 6630 6666 3030 3030 2ffffffff0ff0000
9c9
< 00000080: 22d9 8729 6fcb 0f18 8dd6 0388 bf20 350f "..)o........ 5.
---
> 00000080: 22d9 8729 6fcb 0f18 8dd7 0388 bf20 350f "..)o........ 5.
17c17
< 00000100: 7461 2f50 6167 6573 2032 2030 2052 2020 ta/Pages 2 0 R
---
> 00000100: 7461 2f50 6167 6573 2033 2030 2052 2020 ta/Pages 3 0 R
21c21
< 00000140: 0201 edab 03b9 ef95 991c 5b49 9f86 dc85 ..........[I....
---
> 00000140: 0201 edab 03b9 ef95 991b 5b49 9f86 dc85 ..........[I....
$ md5sum jf.block jf-mod-block
b10b4a6bd373b61f32f4fd3a0cdfbf84 jf.block
b10b4a6bd373b61f32f4fd3a0cdfbf84 jf-mod-block
There’s one byte different on four rows, but the MD5sums are still the same.
The SHA256 of this block solves the objective:
$ sha256sum jf-mod-block
fff054f33c2134e0230efb29dad515064ac97aa8c68d33c58c01213a0d408afb jf-mod-block
Flag: fff054f33c2134e0230efb29dad515064ac97aa8c68d33c58c01213a0d408afb
Story
In Santa’s Office, Tinsel tells me to head out onto the balcony:
You - you did it! You solved the mystery!
Quickly, go out to the balcony to be recognized!
Out there, Santa Congratulates me:
Thank you for foiling Jack’s foul plot!
He sent that magical portrait so he could become me and destroy the holidays!
Due to your incredible work, you have set everything right and saved the holiday season!
Congratulations on a job well done!
Ho Ho Ho!
Jack Frost, in his prison jumpsuit, is not happy:
My plan was NEARLY perfect… but I never expected someone with your skills to come around and ruin my plan for ruining the holidays!
And now, they’re gonna put me in jail for my deeds.