There were several quintillion decryption key options between a person and his cryptocurrency.
In October, Michael Stay received a strange message from LinkedIn. A stranger lost access to the private keys of his cryptocurrency and asked Stay for help getting back access to his $ 300,000.
It was not so surprising that “Dude,” as Stay calls him, found a former security specialist at Google. Nineteen years ago, Stay published a paper detailing the technology for cracking encrypted ZIP files. The dude bought about $ 10,000 worth of bitcoins in January 2016, long before the cryptocurrency boom. He encrypted the private keys in a ZIP file and forgot the password. And now he hoped that Stay could help him crack it.
At the recent Defcon conference, Stay described his epic attempts to do just that.
ZIP is a popular file format used for lossless compression of large files - just like a small tape cover can hold your sleeping bag. Many implementations of the ZIP format are known to have security issues - before even one US Senator approached the National Institute of Standards and Technology last summer to investigate the issue. “If we successfully find this password, I will thank you,” Dude wrote with a smiley at the end. After conducting the initial analysis, Stay estimated that breaking the file would cost $ 100,000. The dude accepted the offer - after all, the profit should be big.
“I haven't had such fun for a long time. Every morning I happily walked to work and struggled with this problem, ”says Stay, currently the CTO of blockchain technology firm Pyrofex. "ZIP encryption was developed by a lay cryptographer decades ago - so it's pretty remarkable that it lasted so long." However, if some ZIP files can be cracked using ready-made utilities, then Dude was not lucky.
In particular, that's why they asked so much for the work. New generations of ZIP programs use the reputable and reliable AES crypto standard, and older versions, one of which Dude used, is Zip 2.0 Legacy, which can often be hacked. The degree of complexity, however, depends on its implementation. “It's one thing to say that the standard is broken, but actually breaking it is a completely different question,” says cryptographer Matthew Green of Johns Hopkins University.
Only a handful of clues could help Stay with his approach. The Dude still had a laptop that he used to create the encrypted ZIP - which validated his ownership of the bitcoins, and also gave Stay information about which ZIP program and which version was used for encryption. He also knew the file creation time that Info-ZIP software uses for its cryptographic scheme. Stay was able to reduce the huge number of possible passwords and encryption keys to several quintillion.
To carry out an attack of this magnitude, it was necessary to rent cloud processing power for graphics processing. Stay approached Nash Foster, the director of Pyrofex, to write the cryptanalysis code and run it on a general-purpose GPU from Nvidia Tesla. As he delved deeper into the project, Stay was able to refine the attack and reduce the program's runtime required to achieve a result.
“Initially, we assumed that we would develop the program for a couple of months, and then it would work for a few more months,” Foster told Wired magazine. “As a result, Mike was able to conduct cryptanalysis more efficiently, and we spent more time developing the attack, and the program took only a week to work. This saved Dude a lot of money in infrastructure rent. Ten years ago, it would have been impossible to do this without assembling special equipment, and the cost of the project would probably have exceeded the cost of its bitcoins. "
However, the question of whether this grinding of numbers on the GPU would work was still open. After months of tinkering with this task, Stan was finally ready to give it a try. The dude didn't give Stay and Foster the entire file - he probably didn't trust them, believing that they could steal his cryptocurrency by cracking the keys. Because of the way he implemented ZIP encryption, he could only provide Stay and Foster with encrypted headers — informational records about the contents of the file — without transmitting the main content. By February, 4 months after the first LinkedIn message, they had prepared a program and launched an attack.
She worked for 10 days and failed. Stay later wrote that he was "heartbroken."
“Before that, we encountered various bugs, but on all tests that I ran on my laptop, everything worked fine,” he says. "If it was a mistake, she must have been some very cunning, and I was worried that it would take us a long time to find her." The fact that in February the cost of bitcoins began to fall, and with it the cost of the file, did not help either. The dude was very worried.
Stay went through the entire program, worried about any wrong assumptions or hidden bugs. But then he got a new idea of what random seed to start with the random number generator used in their program. The dude also looked at the test data and noticed an error that would occur if the GPU was not processing the correct password on the first pass. Stay and Foster have fixed the bug. After making those two program fixes, they were ready to start over.
"Bang! And a bunch of bitcoins popped out of the file, ”says Foster. “We breathed a sigh of relief,” adds Stay.
As a result, the cost of renting the infrastructure was $ 6,000 - $ 7,000 instead of the initially estimated $ 100,000, says Foster. The dude paid four times less than he expected.
“The deal was great for him,” says Foster. - Such projects are rare. If he had a slightly different situation, if he was using a more recent version of ZIP, it would be impossible to do this. But in this particular case, we could have done something. "
Stay says that after the publication of the technical description of the project in April, several people approached him with requests to recover passwords for their bitcoin wallets. Unfortunately, this is a common problem. Even the editorial staff of Wired have encountered this. But the ZIP attack has nothing to do with cryptocurrency wallets - they can sometimes have hackable flaws, but they are built with strong modern encryption.
Yet the prevalence of ZIP suggests that Stay and Foster's research has far-reaching implications.
“In terms of messing around with cryptography, this is a very cool project,” says Green. - This is one of the ancient attacks on an outdated scheme, and no one would have thought that it is still relevant. But, surprisingly, all this junk is still ubiquitous, so this topic is very relevant. And the fact that a lot of money was waiting for them at the end is generally cool. "
We would all be so lucky.