At some point in our life, we’ve all lost or misplaced something. I’ve misplaced my phone and keys more times than I can count. They always have a way of finding themselves between the couch cushions. But have you ever lost the private keys to access your $300,000 worth of bitcoins? Neither have I. However, this is exactly what happened to a very unlucky man.
Last month, Defcon’s 28th annual event took place. The event is the most influential security hacking conference held in Las Vegas. Michael Stay, a reverse engineer and current CTO for Pyrofex Corp, shared the story with attendees. He started his presentation by saying, “And today I’m gonna to tell you about how we recovered several hundred thousand dollars worth of Bitcoin from an encrypted zip file.”
About twenty years ago, Stay published a cryptanalysis paper detailing how to break into encrypted zip files. This paper led an anonymous Russian investor to find Stay and send him a surprising message on LinkedIn. “So in October of last year, a guy contacts me out of the blue and says, “I read your paper on known plaintext attacks, and I’ve got this password that I’ve forgotten. Is there anything you can do to help?”” Stay said.
In 2016, the investor purchased $10,000 worth of bitcoins and placed the private keys in an encrypted zip file. After the Bitcoin boom, the purchase proved to be a great investment. There was just one slight problem: He forgot the password and had no way of accessing the Bitcoins.
After stumbling on Stay’s old cryptanalysis paper, he hoped Stay would help him break into the zip file and recover the lost keys. When Stay looked into the case, he soon realized this would be a difficult task. The attack he had written years ago needed five files to break into the zip file. This man only had two files in the archive.
With only two files, this would take Stay a lot of time and money to find a solution to the problem. After doing some calculations, he told the guy it would cost him around $100,000 to attempt to recover the keys. He simply couldn’t use regular “off-the-shelf software” to get this done.
The man agreed without hesitation. Stay’s mind was blown away with his response. “I knew he probably had several hundred thousand dollars of Bitcoin in this thing,” he said. The pressure was on!
To break-in, Stay enlisted his business partner, Nash Foster. Foster helped adapt his CPU based attacks to run on GPUs, and they rented a GPU farm. “Our initial expectation was we would do engineering for a couple of months, and then the attack would have to run for several months to succeed,” Foster told WIRED.
Four months after the initial LinkedIn message, they began the attack. “We had tried it in all our test archives that we’d created. It worked fine,” Stay said. They were hopeful. “Ten days passed, and it didn’t find a key. And we were distraught, pulling our hair out. What have we done wrong?” Stay asked himself.
After combing through the data, the investor, who is a programmer himself, discovered a bug in the GPU. Once Stay and Foster fixed the bug, they were able to restart their attack. Within a day and a half, they found the three keys they needed to decrypt the archive.
In the end, the improvements made to Stay’s old attack made a significant difference. Instead of the $100,000 and year of processing time that Stay estimated it would take, they were able to do it for less than $10,000 in two weeks of processing time.
“Our client was very pleased and gave us a big bonus! And that’s how we recovered his Bitcoin folder,” Stay said.
According to a 2017 research by analysis company, Chainanalysis, nearly 400 million Bitcoins are already lost. Although Bitcoins have no physical form, they can still be lost. Forgotten private keys and passwords, and discarded and lost devices account for this high number.
The Russian investor wasn’t so unlucky after all!