Getty Images
In October, Michael Stay received a strange message on LinkedIn. A total stranger had lost access to his private Bitcoin keys – and wanted Stay to get his $ 300,000 back.
It was no complete surprise that The Guy, as Stay calls him, had found the former Google Security Engineer. Nineteen years ago, Stay published a paper describing a technique for breaking into encrypted zip files. The guy had bought around $ 10,000 worth of Bitcoin in January 2016, well before the boom. He had encrypted the private keys in a zip file and forgot the password. He hoped Stay could help him break in.
In a talk at Defcon's security conference this week, Stay describes the epic attempt that followed.
Zip is a popular file format used for "lossless" compressing large files, such as. B. the little drawstring that can somehow contain your sleeping bag. Many zip implementations are known to be unsafe, to the point that US Senator Ron Wyden of Oregon asked the National Institute of Standards and Technology to investigate the issue last summer. "If we successfully find the password, I will thank you," the guy wrote with a smiley face. After initial analysis, Stay estimated he would have to charge $ 100,000 to get into the file. The guy accepted the deal. After all, he would still be making quite a profit.
"It's the most fun I've had in ages. Every morning I was excited to go to work and grapple with the problem," said Stay, who is now the chief technology officer at blockchain software development company Pyrofex. "The zip cipher was designed by an amateur cryptographer decades ago – the fact that it has held up so well is remarkable." But while some zip files can be easily cracked with off-the-shelf tools, The Guy wasn't that lucky.
That is partly why the work was so expensive. Newer generations of Zip programs use the established and robust AES cryptographic standard, but outdated versions – like the one used in the case of The Guy – use Zip 2.0 legacy encryption, which can often be cracked. However, the level of difficulty depends on how it is implemented. "It's one thing to say that something is broken, but actually it's a whole different ball of wax," said Matthew Green, cryptographer at Johns Hopkins University.
Stay only had a few pointers to inform about his course of action. Since The Guy still had the laptop he had used to create and encrypt the zip file – also a decent indicator that the Bitcoin had actually been his from the start – at least he knew which zip program had encrypted the file and which version it was running. It also had the timestamp of when the file was created, which the Info-ZIP software uses to inform the cryptographic scheme. From a huge pool of passwords and encryption keys, Stay was able to narrow it down to something on the order of trillions.
To carry out an attack of this magnitude, cloud graphics processors would have to be rented. Stay tuned to Nash Nash, CEO of Pyrofex, to implement the cryptanalysis code and run on general-purpose Nvidia Tesla GPUs. As they delved deeper into the project, Stay was able to refine the attack and reduce the time it took to get results.
"Our initial expectation was that we would do a few months of engineering and then the attack would have to take several months to be successful," Foster told WIRED. "Mike was ultimately able to make the cryptanalysis more effective. So we spent more time developing the attack, but then only had to run it for about a week. That saved the man a lot of money on infrastructure costs. Ten years Some time ago there would have been no way to do this without building special hardware, and the cost would likely have exceeded the value of your bitcoin. "
The question remained, however, whether all of the GPU crunching would actually work. After months of pounding on the problem, Stay was finally ready to give it a try. The guy hadn't given the entire zip file to Stay and Foster. He probably didn't trust that if they managed to crack the keys, they wouldn't steal his cryptocurrency. Because of the implementation of encryption in zip files, he could instead just give Stay and Foster the encrypted "headers" or informational notes about the file without sharing the actual content. In February, four months after that first LinkedIn message, they queued everything and launched the attack.
It ran for 10 days – and failed. Stay later wrote that he was "heartbroken".
"We've had a lot of bugs, but the tests I ran on my laptop all worked perfectly," he says now. "If it was a mistake, it had to be a subtle one, and I was concerned that it would take us a long time to find it." It didn't help that during February the price of Bitcoin fell, and with it the value of the contents of the zip file. The guy was nervous.
Stay combed through his attack and worry about an obscure, false assumption, or hidden flaw. Soon he had a new idea as to which number or which "starting value" should serve as the starting point for the random number generator used in the cryptographic scheme. The guy also combed the test data and noticed an error that would occur if the GPU didn't process the correct password on the first try. Stay and Foster fixed the bug. With these two revisions to the attack, they were ready to try again.
"Poof! A bunch of Bitcoin came out," says Foster. "It was a huge relief," adds Stay.
In the end, the infrastructure cost to carry out the attack was $ 6,000 to $ 7,000 instead of the original estimate of $ 100,000, Foster says. The guy paid about a quarter of the original price.
"He's got a smoking contract," says Foster. "Projects like this are just completely unusual. If the details of his situation had been different, if he had used a slightly newer version of zip, it would have been impossible. But in this particular case we could have done something."
Stay says that since the release of his technical report on the project in April, a number of people have contacted and asked him to help them recover the passwords for their Bitcoin wallets. Unfortunately, it's a common emergency. Even WIRED itself feels this pain. However, the zip attack has nothing to do with cryptocurrency wallets, which can occasionally have hackable bugs, but are created with strong, modern encryption.
However, the fact that zip is so ubiquitous means that Stay and Foster's research is making a bigger impact.
"It's really cool from a crypto violin standpoint," says Johns Hopkins & # 39; Green. "It's one of those age-old attacks on a shitty scheme and nobody thought it was relevant. But believe it or not, this bad stuff is still out there all over the place, so it's actually really relevant. And the fact that there is a bunch of money in the end is really great. "
We should all be so lucky.
This story originally appeared on wired.com.
