Getty Images
In October, Michael Stay received a strange message on LinkedIn. A total stranger had lost access to his private keys bitcoin – and wanted help from Stay to get his $ 300,000 back.
It was no total surprise that The Guy, as Stay calls him, found the former Google security engineer. Nineteen years ago, Stay published a paper detailing a technique for hacking encrypted zip files. The Guy had bought about $ 10,000 worth of bitcoin in January 2016, good for the boom. He had encrypted the private keys in a zip file and had forgotten his password. He hoped Stay could help him break in.
In an interview at the Defcon Security Conference this week, Stay describes the episode that followed.
Zip is a popular file format that is used for “lossless” compression of large files, such as the small snug nose that your sleeping bag can somehow contain. Many implementations of zip are known to be unsafe, to the point that U.S. Senator Ron Wyden of Oregon last summer called on the National Institute of Standards and Technology to investigate the problem. “If we find the password successfully, I will thank you,” De Guy wrote with a smiley face. After an initial analysis, Stay estimated that he would need $ 100,000 to break into the file. The Guy took the deal. After all, he would still be turning the tide.
“It’s the best I’ve had in ages. Every morning I was up to get to work and wrestle with the problem,” said Stay, who is now chief technology officer at blockchain software development firm Pyrofex. . “The zip encoder was designed decades ago by an amateur cryptographer – the fact that it is so well kept is remarkable.” But while some zip files can be easily cracked with tools without tools, The Guy was not so lucky.
That is in part why the work was praised so highly. Newer generation zip programs use the established and robust cryptographic standard AES, but outdated versions – such as the one used in The Guy’s case – use Zip 2.0 Legacy encryption that can often be cracked. However, the degree of difficulty depends on how it is implemented. “It’s one thing to say something is broken, but in fact breaking it is a whole other ball of wax,” says cryptographer Johns Hopkins University Matthew Green.
Stay had only a few clues to go through to inform his approach. Since The Guy still had the laptop, he had used it to create and encrypt the zip file – also a decent indicator that bitcoin was actually his to begin with – Stay at least know which zip program had encrypted the file and which version it round. He also had the timestamp of when the file was created, which uses the Info-ZIP software to inform his cryptographic schema. From a massive pool of passwords and encryption keys, Stay was able to limit it to something in the order of quintillions.
To carry out an attack of that scale, hired cloud-graphics processing units would be needed. Keep tapping Pyrofex CEO Nash Foster to implement and run the crypto analytics code on Nvidia Tesla general purpose GPUs. As they got deeper into the project, Stay was able to refine the attack and reduce how long it would take to produce results.
“Our first expectation was that we would do a few months of engineering, and then the attack would have to take several months to succeed,” Foster told WIRED. “Mike eventually got to do a more effective job with the cryptanalysis, so we spent more time developing the attack, but then only needed a week to execute it. That saved the man a lot of money on infrastructure costs. Ten years ago there would have been no way to do this without building special purpose hardware, and the cost would probably have been the value of his bitcoin more. “
The question remained, however, though, though that GPU crunching would actually work. After months of hammering on the issue, Stay was finally ready to try. The Guy had not given the entire zip file to Stay and Foster; he probably did not trust that they would not steal his cryptocurrency if they managed to crack the keys. Instead, because of how encryption is implemented in zip files, he could simply provide the encrypted “headers”, as well as informative notes about the file, Stay and Foster, without sharing the actual content. By February, four months after that first LinkedIn message, they were queuing up and launching the attack.
It took 10 days – and failed. Stay later wrote that he was “heartbroken.”
“We had a lot of bugs before, but the tests I ran on my laptop all worked perfectly,” he says now. “If it was a break, it had to be a subtle one, and I was worried it would take us a long time to find it.” It did not help that the whole of February the price of bitcoin fell, and the value of the contents of the zip file with it. The guy was antsy.
Stay combed by his attack, worrying about something obscure, wrong assumption like a hidden flaw. He soon came up with a new idea about which number, as ‘seed’, to try as a starting point for the random number generator used in the cryptographic scheme. The Guy also combed the test data and noticed an error that occurred when the GPU did not process the correct password on the first try. Stay and Foster have repaired the break. With both of these versions of the attack in place, they were ready to try again.
“Poof! Out came a lump of Bitcoin,” says Foster. “It was such a relief,” Stay adds.
Ultimately, the infrastructure costs to carry out the attack were $ 6,000 to $ 7,000 instead of the roughly $ 100,000 they had originally estimated, Foster says. The Guy paid about a quarter of the original price tag.
“He got a smoke deal,” Foster says. “Projects like this are just completely unusual. If the details of his situation were different, if he had used a slightly more recent version of zip, it would have been impossible. But in this particular case, there was something we could do. “
Stay says that since publishing his technical account about the project in April, a number of people have reached out, asking him to help them get the passwords back into their Bitcoin wallets. Unfortunately, it is a common fate. Even WIRED himself feels that pain. But the zip attack has nothing to do with cryptocurrency wallets, which can sometimes have hackable flaws but are made with strong, modern encryption.
However, the fact that zip exists so extensively that the Stay and Foster investigation has greater implications.
“It’s very cool from a crypto-fiddling perspective,” says Johns Hopkins’ Green. “It’s one of those old attacks on a curved schedule, and no one would have thought it’s relevant. But believe it or not, this bad stuff is still everywhere, so it’s actually really relevant. And the fact that d ‘it’s a pile of money at the end of it is really great. “
We should all be so happy.
This story originally appeared on wired.com.
