In brief:
- Former Google engineer Mike Stay was asked to hack a zip file containing the private keys to over $300,000 worth of Bitcoin.
- After trial and error, he cracked the cipher.
- He restored the private key to its owner, who used it to access $300,000.
After one Bitcoin owner lost access to $300,000 worth of Bitcoin, cryptography expert Mike Stay managed to restore it within a matter of months. In a blog post yesterday, Stay revealed how he pulled it off.
Over half a year ago, a "Russian guy" asked Stay, a former Google engineer and cryptanalyst, to recover the private keys to a stash of Bitcoin," he said. With a lengthy history of accessing the inaccessible, he rose to the challenge.
The “Russian guy” had messaged Stay on LinkedIn and asked him to pull off the seemingly impossible—to decrypt a zip file that contained the private keys to a hoard of Bitcoin.
The mysterious Russian had invested heavily in Bitcoin in 2016, said Stay. But he was locked out of his Bitcoin after forgetting his password. He was thus unable to sell his stranded Bitcoin, which are now worth over $300,000.
The problem was that the encrypted file had an almost infinite amount of possible combinations. "I estimated it would take a large GPU farm a year to break, with a cost on the order of $100K," wrote Stay in a blog post published April 3.
"He astounded me by saying he could spend that much to recover the key."
Stay started work at once, reconstructing a similar attack vector from an academic paper he had written previously. However, he soon stumbled across a complication.
In the attack described in his old paper, Stay only needed to check a few constraints on the keys to decipher a solution. Once he had found enough, he could run through four billion possibilities to find the keys themselves.
But those constraints came from the number of files in the archive. He needed five for his old attack, and here he had only two. That meant he'd have to try four billion possibilities for every single candidate, of which there were trillions. "If I had to do 2^32 tests on each one, it would take a few hundred thousand years," he writes.
Stay developed several complex algorithms and managed to cut the combinations to just 36 possibilities per candidate. He also came up with a "differential meet-in-the-middle attack" that let him avoid transferring petabytes of data between different computers.
The attack failed when he ran the first time. Stay racked his brain and re-checked his tests. It was then that he discovered a bug in the GPU code. He rustled up a quick fix. That solved the problem, and he managed to decipher the key within a day.
Given the number of keys and passwords fumbled in the crypto industry, Stay might have struck a gold mine with his solution.
Editor's note: This article has been updated with clarifications about the process that Stay provided to Decrypt.