BTC 2018 Solutions - Stage 4: Virtual Machine
This blog post contains the solution for Stage 4 of the 2018 Bitcoin Programming Challenge.
Once you finish the T-Rex runner game (stage 3), you are given some links to some files.
Here are the links:
No further instructions were provided.
The winner has posted an amazing write-up about how they solved the puzzle. I’m really impressed that they were able to solve it in 24 hours!
The first thing to figure out is that tests.bin is a set of inputs and outputs that describes the instruction set for a virtual machine (or bytecode interpreter.) You must write a program that produces the expected output for each input. Once you’ve written this program, you can “execute” stage4.exe by using the file as the input to your program.
Then you need to figure out the structure of tests.bin. This is an array-of-arrays-of-strings encoded with MessagePack. It’s also possible to figure out the file structure by looking at the bytes in a hex editor, which is how the winner solved it. The first value in each nested array is the input, which is a string of bytes. The second value in the array is the expected output, which is a string of either hex-encoded data or UTF-8 text.
Here’s what the first few tests look like when the inputs are converted to hex strings:
[
["000000000000", "00000000"],
["", "00000000"],
["000000000001", "00000001"],
["000001000000", "01000000"],
["000000001000", "00001000"],
["0000ffffffff", "ffffffff"],
["000100001000", "0000000000001000"],
["000200001000", "000000000000000000001000"],
["000000000000000200001000", "000000000000000000001000"],
["000000000001000200001000", "000000010000000000001000"],
["000000001000000100000001", "0000100000000001"],
...To solve the puzzle, you must reverse engineer the instruction set, figure out how the registers work, and write a program that passes all of the tests.
This virtual machine has 16 4-byte registers. The first 8 registers can be printed as output (either hex-encoded data, or UTF-8 strings). The last 8 registers are only used internally.
Here are all of the instructions:
| Byte (Hex) | Instruction | Argument Bytes | Arguments |
|---|---|---|---|
00 | Copy 4-byte value into register | 4 | Register, 4-byte value |
01 | Copy constant from register B to register A | 2 | Register A, Register B |
02 | Increment register by one | 1 | Register |
03 | Decrement register by one | 1 | Register |
06 | Add register B to register A | 2 | Register A, Register B |
07 | Subtract register B from register A | 2 | Register A, Register B |
08 | Multiply register A by register B | 2 | Register A, Register B |
09 | Divide register A by register B | 2 | Register A, Register B |
0a | AND register B with register A | 2 | Register A, Register B |
0b | OR register B with register A | 2 | Register A, Register B |
0c | XOR register B with register A | 2 | Register A, Register B |
0d | NOT register B with register A | 2 | Register A, Register B |
0e | Bitwise right shift | 1 | Register |
0f | Bitwise left shift | 1 | Register |
fe | Print the first 8 registers as UTF-8, then reset | 5 | Magic constant: 9eff33ffb0 |
ff | Print the first 8 registers as hex, then reset | 5 | Magic constant: 9eff33ffb0 |
The first 4 bits are ignored for each instruction or register byte (with exceptions for the fe and ff instructions). This means that 00, 50, and f0 are all the same instruction, and 00, 50, and f0 all refer to the first register.
For the fe and ff print/reset instructions, the next 5 bytes must exactly match 9eff33ffb0 (the “magic constant”), otherwise the instruction should be ignored. I also decided that if you divide any value by zero, the result should be ffffffff. It’s as close as you can get to infinity in 4 bytes. (Not very close.)
Once all the tests were passing, you could use stage4.exe as the input to your program, and you would see the following message:
You could then follow the instructions to download the Bitcoin whitepaper PDF, and use this PDF as the input to your program:
$ ./scripts/execute_file.rb bitcoin.pdf
32314146e05f296c4075af0b3c28f5007c40ba13222002331804000022200234This is the 256-bit private key for a Bitcoin address that contained 0.125 BTC. The winner was able to make a transaction to claim the Bitcoins.
The program will ignore any invalid instructions, so any file can be used to generate a 256-bit value. It’s nowhere close to a cryptographic hash function (e.g. SHA-256), and there are usually a lot of zero bits in the output. Even so, I think it produced a decent result for the Bitcoin whitepaper PDF.
The source code has been posted on GitHub. Here’s the reference solution in Ruby.
I really enjoyed working on the obfuscated string generator that I used to create stage4.exe. I measured the code coverage with SimpleCov to make sure I used all of the available instructions.
I shuffled the registers, XORed registers with random values, and XORed all of the registers together in a sequence. This part was a lot of fun. I divide a register by zero to get ffffffff, do a bitwise left shift to get fffffffe, then a NOT to get 00000001, and then OR this value with a register if the last bit was meant to be 1. If you got anything wrong, the incorrect behavior would sort of have an avalanche effect through all of the registers, so the output would still be scrambled.
Thanks for reading, and I hope you enjoyed the 2018 Bitcoin Programming Challenge! If you want to take part in the next one, you can sign up for the DocSpring Crypto Puzzle mailing list:
(No spam. I’ll only send an email about the next crypto puzzle.)
Solutions for the 2018 Bitcoin Programming Challenge:
- Stage 1: PixelPerfect
- Stage 2: Cubes
- Stage 3: T-Rex Runner
- Stage 4: Virtual Machine