On the 30th of December, FormAPI released a Bitcoin challenge on their website : https://formapi.io/blog/posts/2018-bitcoin-programming-challenge/
I solved the final stage about 24 hours later and won the 0.125 BTC (I was too slow to grab any of the intermediate prizes). This write-up is a walkthrough of all 4 stages of the puzzle.
Stage 1 : CSS
Stage 1 is a serie of 7 mini CSS puzzles. I’m not a CSS specialist so i Googled how to do geometric shapes. Puzzle 6 was the hardest for me until I found that you had to create a .circle::after class to make the second cercle. Puzzle 7 required a bit of trial and error to find the right values for the triangle.
Once all solved, you are given the first private key for the intermediate prize ( 5Kbf6NSm6SABiMHwDcuZKY17fmCsnsKRYxR4hcnGqfzPsTeZnEj) and the link to the second stage : https://btc2018.formapi.io/eab75cf16b878ce659a3c3d7b8a71cad2ea48a508f9333ef37807a3c8ff3f531/
Stage 2 : Cubes
An algorithm challenge where you had to solve a 3-dimensional 10-pieces jigsaw puzzle. I programmed my solving algorithm in Python and here are the steps that I followed:
- Fill in all the pieces with -1 so that you have 8x8x8 arrays. It’s way easier to manipulate after.
- Create 3 90° rotation functions (one around each axis). Pretty easy to do, you just had to do the following coordinate changes for example. X axis rotation :(x,y,z) -> (x,z,7-y) , Y axis rotation :(x,y,z) -> (7-z,y,x) , Z axis rotation :(x,y,z) -> (7-y,x,z)
- Create a translation function that moves the piece inside the cube for a (dx,dy,dz) translation vector. Return false if a part of the piece is outside the cube.
- For each one of last 9 pieces, create a list of copies of that piece, which are all the possible positions of that piece. To do that, you have to try all the 24 possible rotations and all the allowed translations. The easiest way to do it is just try all 64 rotations combining 0 to 3 of each of the 90°axis rotation and remove the obtained duplicates. Then try all translations with (dx,dy,dz) from (-7,-7,-7) to (7,7,7). The numbers of possible positions found for the 9 last pieces were respectively 72, 96, 360, 384, 288, 24, 1920, 48, 24.
- Try all the combinations of these pieces with a recursion function. That’s about 72*96*.. = 1.4608139e+19 total combinations but some branches of the tree are cut very early because you verify each time if a piece doesn’t collide your current puzzle.
The result was very fast and I found only one solution which gave my the following binary : 10110000001001011100010001100100100010001001110001101001100010111000100100011110111100001110101000100111111101100010011010101100111000000110110011101100110011011100111001110100010010110001000010100111000011010110000000110110011100011110010001110010100100100110011000011001110000001101101100101001000000111100110011001101001010000110101100111010011110101101001001001111100000100001000010010001111000111000111011111110011010110000000010001101000101010010101001011010100010000011110100101100000001010101111001100111
After xoring the 2 parts, we have in hex : d63c04bfa19fa546a175ca90f5b9a4bc718f6233a574c6058d57e80b5de12cf5 which correspond to the second private key : 5KSduuNXJccFdSrTeTH52SiStWeEAJ99JU6uRP8JXnfoDsEB3GJ
Stage 3 : T-Rex
The next stage address is therefore : https://btc2018.formapi.io/d63c04bfa19fa546a175ca90f5b9a4bc718f6233a574c6058d57e80b5de12cf5/
Here, we can think we have connection issues but it is in fact the puzzle. A classic chrome error page has been reproduced, and if you have a bad connection, you already know this little dinosaur. You just have to play the game (press space bar or up arrow to jump) and reach the point where you are given the third private key 5K3GHbUArCZ6eEwymYe4XEa34EudFCo5p5znAWH7tQJBigzrCBB and the 2 parts of the last stage : https://btc2018.formapi.io/a129db6cc02c06b7ab645a941eb9fbaf5f3349786e7b6f929ff4f29b2ea7ea2e/tests.bin and https://btc2018.formapi.io/a129db6cc02c06b7ab645a941eb9fbaf5f3349786e7b6f929ff4f29b2ea7ea2e/stage4.exe
Stage 4 :
We have two files, one .bin and one .exe. Upon first inspection, I found that the .exe is not a correct Windows executable file and I found some interesting patterns in the .bin file with an hex editor. It seemed that there is a large number of pairs of values, one binary and one hex string, always separated with the two bytes 92 C4. Upon further analysis, I figured the exact structure of that file : first, three magic numbers at DC 01 50, not sure of their meaning, then 336 different pairs of values, which have all the same structure :
- One byte at 92
- One byte at C4 or C5
- If C4, the next byte is the length of the first value; if C5, the next two bytes are the length of the first value.
- The first value
- One byte which is either the length of the second value + 160 , or if this byte is at D9, it is the next byte which is the length of the second value.
- The second value (all characters in the printable ascii range, almost always a hex string)
I could this way parse the tests.bin file and, with this name, I quickly figured it was a serie of tests, one value being the input and one being the output of a program.
But which program? I first thought it was the stage4.exe file, written in an esoteric language that I didn’t know. Then I had an idea, and if the .exe file was an input and we have to figure the output with the help of the tests? It made a lot of sense since the tests seemed to be exhaustive and go from simple to more complex.
So I started to try to understand the logic of the tests and to write my own program that will pass all the tests. I won’t give all the details about what byte value correspond to what operation, but I will give a sum up of how the program works. You can try to make a program yourself and make it work, it might be interesting!
The first few tests are the more important. You understand that the program works with a 16 x 4-bytes memory but only the first 8 x 4 bytes are given as an output. Then you have examples of all the operations you can do on that memory : allocation, copy, +1, -1, addition, substraction, product, division, and, or, xor, not, right and left shift.
Near the end of tests, the hard part for me, some special byte values that were hard to exactly understand. My final program did not past all the tests but it was apparently enough. What I figured what these values (not exactly sure) :
- FF : skip the next 3bytes.
- FE : skip the next 2 bytes.
- FD : skip the next byte.
- Ignore the value FF9EFE33FFB0 ?
- 9EFF33FFB0 : Print the memory (first 8 indexes) and erase it.
- Some variations of the previous one where you had to print the memory either in hex or decode it as utf-8. I didn’t fully understood but it ended up not mattering : I just always printed the hex values and did a final conversion.
So after using stage4.exe as an input, I got :
I was mind blown that, in the end, the program we had to create could take the bitcoin whitepaper as an input and return a private key (but if you analyse closely the language, you understand how it works, and why for example the value 9EFF33FFB0 was used to print an output). My program ended up giving the right output at the first try :
This hex corresponds to the private key 5JCPgLcXBqfYJpbpyEVqo38k7r3MMUL7Mriv1UG2NHgj9NvxeZ1 which was the one for the 0.125 prize.
Acknowledgments
I’d like to thank FormAPI.io for this fun, interesting, challenging and rewarding serie of puzzles !
