Getty Images
In October, Michael Stay got a weird message on LinkedIn. A total stranger had lost access to his bitcoin private keys—and wanted Stay’s help getting his $300,000 back.
It wasn’t a total surprise that The Guy, as Stay calls him, had found the former Google security engineer. Nineteen years ago, Stay published a paper detailing 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 had forgotten the password. He was hoping Stay could help him break in.
In a talk at the Defcon security conference this week, Stay details the epic attempt that ensued.
Zip is a popular file format used for “lossless” compression of large files, like the little drawstring sack that can somehow contain your sleeping bag. Many implementations of zip are known to be insecure, to the point that US senator Ron Wyden of Oregon called on the National Institute of Standards and Technology last summer to investigate the issue. “If we find the password successfully, I will thank you,” The Guy wrote with a smiley face. After an initial analysis, Stay estimated that he would need to charge $100,000 to break into the file. The Guy took the deal. After all, he’d still be turning quite the profit.
“It’s the most fun I’ve had in ages. Every morning I was excited to get to work and wrestle with the problem,” says Stay, who today is the chief technology officer of the blockchain software development firm Pyrofex. “The zip cipher was designed decades ago by an amateur cryptographer—the fact that it has held up so well is remarkable.” But while some zip files can be cracked easily with off-the-shelf tools, The Guy wasn’t so lucky.
That’s partly why the work was priced so high. Newer generations of zip programs use the established and robust cryptographic standard AES, but outdated versions—like the one used in The Guy’s case—use Zip 2.0 Legacy encryption that can often be cracked. The degree of difficulty depends on how it’s implemented, though. “It’s one thing to say something is broken, but actually breaking it is a whole different ball of wax,” says Johns Hopkins University cryptographer Matthew Green.
Stay had only a few clues to go on to inform his approach. Since The Guy still had the laptop he had used to make and encrypt the zip file—also a decent indicator that the bitcoin was actually his to begin with—Stay at least knew which zip program had encrypted the file and what version it ran. He also had the time stamp of when the file was created, which the Info-ZIP software uses to inform its cryptography scheme. From a massive pool of passwords and encryption keys, Stay was able to narrow it down to something on the order of quintillions.
To run an attack of that scale would require renting cloud graphics-processing units. Stay tapped Pyrofex CEO Nash Foster to implement the cryptanalysis code and run it 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 need to run to produce results.
“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. “Mike ended up being able to do a more effective job with the cryptanalysis, so we spent more time developing the attack but then only needed to run it for about a week. That saved the guy 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 probably would have exceeded the value of his bitcoin.”
The question still remained, though, whether all that GPU-crunching would actually work. After months of hammering on the problem, Stay was finally ready to try. The Guy hadn’t given the entire zip file to Stay and Foster; he likely didn’t trust that they wouldn’t steal his cryptocurrency if they did manage to crack the keys. Instead, because of how encryption is implemented in zip files, he was able to just give Stay and Foster the encrypted “headers,” or informational notes about the file, without sharing its actual content. By February, four months after that first LinkedIn message, they queued it all up and started the attack.
It ran for 10 days—and failed. Stay later wrote that he was “heartbroken.”
“We’d had lots of bugs before, but the tests I ran on my laptop all worked perfectly,” he says now. “If it was a bug, it had to be a subtle one, and I worried that it would take us a long time to find.” It didn’t help that throughout February, bitcoin’s price was dropping, and the value of the zip file’s contents with it. The Guy was antsy.
Stay combed through his attack, worried about some obscure, incorrect assumption or a hidden bug. He soon struck on a new idea about which number, or “seed,” to try as the starting point for the random number generator used in the cryptographic scheme. The Guy combed the test data as well and noticed an error that occurred if the GPU didn’t process the correct password on the first attempt. Stay and Foster fixed the bug. With both of these revisions to the attack in place, they were ready to try again.
“Poof! Out came a bunch of Bitcoin,” Foster says. “It was such a relief,” Stay adds.
In the end, the infrastructure costs to run 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 smoking deal,” Foster says. “Projects like this are just completely unusual. If the details of his situation had been 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 of the project in April, a number of people have reached out, asking him to help them recover the passwords to their Bitcoin wallets. Unfortunately, it’s a common plight. Even WIRED itself feels that pain. But the zip attack has nothing to do with cryptocurrency wallets, which can occasionally have hackable flaws but are made with strong, modern encryption.
Still, the fact that zip is so ubiquitous means that Stay and Foster’s research does have larger implications.
“It’s really cool from a crypto fiddling perspective,” Johns Hopkins’ Green says. “It’s one of these ancient attacks on a crummy scheme, and nobody would have thought about it being relevant. But believe it or not, this bad stuff is still out there everywhere, so it’s actually really relevant. And the fact that there’s a pile of money at the end of it is really great.”
We should all be so lucky.
This story originally appeared on wired.com.