User story: Never generate keys while drunk
David and Hanna got married in late 2017, a friend of theirs thought it would be really cool to gift them something useful instead of the usual wedding gifts, Bitcoin! They were right.
Against their friend's better judgement he decided to generate the paper wallet at the actual wedding event after all guests leave and he brought a laptop for this exact purpose. After everyone left and they were all drunk, they decided that it was time to proceed and generate the paper wallet and later on to fund it with their wedding gift.
The process they had in mind was to generate a paper wallet, divide the private key into 3 parts - one for the friend who gifted them the coins, one for the David's father and one for David and his wife. They used an obscure paper wallet generator website and opted in to generate a private key in a Minikey format.
a Minikey is a format that is usually 30 characters long, starts with a capital 'S' and is rarely used in this day and age. To generate a valid minikey, you need to concatenate 29 base58 chars to the 'S' prefix and to make sure it passes validation by adding a '?' at the end as the 31st character, hash it with SHA256 and make sure the first two characters of the SHA256 output are '00'.
Each party had to write down a 3rd of the Minikey and as a precaution each of them were to write the next 2 characters of the next part. The image below demonstrates the exact scheme they chose to divide this key:
Once Bitcoin hit the last all time high, David decided to cash out only to find out that he accidentally wrote down 12 characters of the Bitcoin address that was shown on the same page at the time, instead of his actual share of the private key.
Luckily, David's father was holding the first two characters of David's share leaving 8 unknown chars for us to recover. Since minikeys are in base58, that meant we had to loop through 58^8, or 128,063,081,718,016 options.
We coded a Rust program that does the following:
- Generate an index based 8 character base58 candidate, so we can loop through and make sure we go over each and every possible combination.
- Concatenate the first two shares with the candidate we just generated and validate it by adding the '?' suffix and hashing it with SHA256 confirming that the output starts with '00'.
- Get the properly formatted private key with our valid candidate.
- Derive a Bitcoin address using the generated private key.
- Compare the derived Bitcoin address with our known Bitcoin address, if we get a match, print out and exit.
We were able to generate about 4 billion candidates per second which meant that it will only take about 8 hours to go through all possible combinations and sure enough after about 6 hours we managed to get to the correct and complete minikey that allowed us to recover David's coins.