Applied cryptography. How we restored bitcoins for 300 thousand dollars

I will share with you one story. About twenty years ago, I received a degree in physics, but was engaged in reverse engineering and cryptanalysis. Our company AccessData worked in the late 90s and early 2000s. Then the US government gradually lifted restrictions on the export of cryptography, however, password protection in most programs was still rather useless. We took office programs, I performed reverse engineering and figured out the encryption algorithm, and then broke cryptographic protection.

It was an endless stream of interesting, but not particularly difficult mathematical puzzles. For all the time I wrote about forty password crackers. We sold them to home users, system administrators, and local and federal law enforcement agencies. I had to go to the federal law enforcement training center in Glinko several times to explain to the guys from the Secret Service, the FBI and ATF the basics of cryptography and how to use our products.

I especially remember two projects. The first was Microsoft Word 97. Before it appeared, the files were encrypted using XOR bytes of clear text and a 16-byte string that was output from the password. The most common bytes in a Word file were usually 0x00, 0xFF, or 0x20 (space), so we just chose the most common character in each column and checked 3 to ¹⁶ options. The key recovery usually happened instantly, but so that people didn’t think that they had wasted money, we inserted a small animation similar to the Hollywood hacker scene with a lot of random characters, from which the correct password gradually emerges.

Microsoft Word 97 has changed everything. Perhaps MSDN also revealed the encryption format, but our small company could not afford a subscription. And not the fact that we would be allowed to write a program for hacking after receiving information. To understand, in SoftICE I set a breakpoint immediately after entering the password, and then slowly moved up the stack until I found an algorithm. This was before the release of IDA Pro, so I had dozens of pages of printouts with an assembler code streaked with a red marker on my wall. I was very pleased when I finally figured it out. At that time, Microsoft was allowed to export only 40-bit cryptography, so the company dutifully implemented strictly allowed cryptography: they repeatedly hashed the password in MD5 using "salt" (randomly selected bytes from the file),to get a 40-bit key, then salt was added to it and hashed again. Password checking on computers of that time took about half a second. We had to use a dictionary attack because it was almost impossible to crack a password with brute force. As a result, we wrote a password cracker for large companies and agencies. The program executed the bruteforce of a 40-bit key space using these fancy MMX Pentium instructions. I heard that once she worked for nine months before I picked up the password.The program executed the bruteforce of a 40-bit key space using these fancy MMX Pentium instructions. I heard that once she worked for nine months before I picked up the password.The program executed the bruteforce of a 40-bit key space using these fancy MMX Pentium instructions. I heard that once she worked for nine months before I picked up the password.

Another really fun project is zip archives. Phil Katz, creator of PKZIP, made an unusual decision for that time to document his file format and include this documentation in the software package, which made ZIP a favorite format for developers. Roger Schlafly developed a stream cipher for encrypting archives. The zip standard quickly became the most popular under Windows, and many other formats, such as .jar java files and OpenOffice documents, were actually zip files with a specific directory structure inside. The open source version of the program was called InfoZIP, it was the basis of almost all proprietary zip archivers, such as WinZip. When I started hacking WinZip, it occupied 95% of the market.

Eli Biham and Paul Kocher published a description of the attack with known plaintext (text before encryption), but in our case, the known plaintext was archived . To get the Huffman codes at the beginning of a compressed file, you essentially need the whole file. The attack was practically useless for law enforcement.

The zip cipher contains 96 bits of internal state, divided into three 32-bit blocks called key0, key1andkey2. The first and third are the internal state of two copies of CRC32, a linear shift register with feedback (a simple mathematical model that allows you to create pseudorandom sequences). In short, to update the state with a new byte of data, you shift everything down by one byte (discarding the lower byte), and then do XOR with a constant from the conversion table indexed by the data byte after XOR with the lower byte. key1Is the internal state of a truncated linear congruent generator (TLCG). To update its internal state, we add a byte of data, multiply by a constant, which we will callc, and add one. The cipher works as follows: enter the data byte in the first CRC32, then take the lower byte and enter it in TLCG, then take the upper byte from there and enter it in the second CRC32, then take the state and square (approximately), and then issue the second byte result in a stream of bytes. To initialize 96 bits of the internal state, you start with a known state and encrypt the password, and then encrypt ten bytes of salt.

PKZIP gets its salt bytes, allocating memory without initializing it, so it contains bits of materials from other running programs or images, or documents, whatever. This worked fine on Windows, but on many Unix systems, memory initializes automatically when allocated. InfoZIP select salt bytes using functionrandC language. He initialized the state of the random number generator by making an XOR timestamp on the process ID, and then generated ten bytes per file. In this case, knowing the time stamp and the process identifier, it was possible, theoretically, to recover the bytes of the header, which, in turn, made it possible to carry out an attack by Biham and Kocher. It seems that InfoZIP authors knew about this attack because they went a step further - and encrypted the header using a password. Thus, the attacker had only twice the encrypted plaintext, and the attack would not have worked.

I noticed this, because the password is the same in both passes, the first byte of the stream is the same in each of them. In the same way as when the light switch is switched twice, it remains where it was at the beginning, when the byte is repeated XOR with the same stream byte, it remains untouched. This allowed me to develop a very powerful attack only on ciphertext : having received five encrypted files in the archive, I could output the internal state of the functionrandwithout having to look at the time stamp or know the process ID. Then I could generate the original unencrypted headers. Since just a few bits in each part of the cipher affect the next part, I could also guess a few bits of status and check if decoding the next bytes twice gives the answer that I expected. As I moved forward, I had to guess less and less pieces of the key. Each additional file also allowed to exclude more potential key materials; at that time, it took several hours on one desktop. I published an article about this and got the opportunity to present it in Japan at the Fast Software Encryption 2001 conference.

Soon I left AccessData, worked for a startup on neural networks for a year, spent three years studying for a master's degree in computer science at the University of Auckland with Chris Kaloud, started my doctoral studies with mathematical physicist John Baez at the University of California Riverside, worked for six years As part of the Google’s Applied Security team, he completed his doctorate and a few years later became the CTO of the new startup.

About half a year ago, I quite unexpectedly received a message on LinkedIn from a Russian guy. He read the article I wrote 19 years ago and wanted to know if the attack would work on an archive that contains only two files. A quick analysis showed that it requires a huge amount of computing power and money. Since there are only two files, at each stage of the selection there are much more false positives. The result is ^2,773 possible keys for testing, almost 10 sextillion. I calculated that a large cluster on the GPU will work for a year, and its cost will be about 100 thousand dollars. He hit me, saying that he agreed to spend so much money to restore the key.

The fact is that in January 2016, he bought bitcoins for about $ 10-15 thousand and placed the keys in an encrypted zip file. Now they cost more than $ 300 thousand, and he could not remember the password. Fortunately, he still had the original laptop, and he knew exactly the encryption time. Since InfoZip derives entropy based on a timestamp, this promised to significantly reduce the number of possible key options “only” to 10 quintillion - and made the attack quite feasible in a couple of months on an average GPU farm. We signed a contract and I got to work.

I spent some time recovering the attack described in the article. To my chagrin, there were some tricky details that I missed in the article, but I worked them out again. And then I discovered that I had made a terrible mistake in evaluating the amount of computation!

In my original attack, I guessed the high bytes of the keys key1 · c, key1 · c ² , key1 · c ³ and key1 · c ⁴ . By the time I guessed this fourth byte, I knew the complete state of the rest of the cipher; I just needed to convert these four bytes to the original key1, and that’s it. I would go over the 32-bit state space for key1 and check each one to see if it gives the correct high bytes. However, here would have to check quintillion keys; if you need to do 2 ³² tests on each, it would take several hundred thousand years.

I vaguely remembered that some work had been done on the TLCG cryptanalysis through reduction of the lattice basis, so I dug up the original article. So it was! It was just necessary to determine the lattice with the basis vectors given by 2 ³² and the degree of constant from TLCG, and then make the reduction of the basis of the lattice. On a reduced basis, I could restore the original state from high bytes by simply multiplying the matrices.

At least that is the idea. It took five bytes to get to the only correct result, and at that time I had only four attacks. The process described in the article rarely gave the correct answer. However, I knew that the answer should be close to the correct one, so I could go over all the possible values ​​of key1 and check the difference between the real answer and the true one. The difference has always been one of 36 vectors! With this optimization, I can reduce the search to just 36 options instead of four billion. We are still in business.

Further, we were faced with the problem of transferring data between machines with a GPU. My business partner, Nash Foster, was involved in GPU implementation. He advised me how quickly various operations are performed, and wrote most of the supporting structures for the application with my code for crypto cracking. How to get these petabytes of candidate keys for GPU testing? They will be idle almost all the time, tossing their cores in anticipation of work. It occurred to me that at every stage of my attack a lot of bits are checked, and then only one of about 65 thousand candidates is saved. If I could find some way to outputthese bits are based on the available information, and not just brute-force them, I would save a lot of work and, more importantly, a lot of network traffic. The problem here was too complicated algorithms, representing a mixture of finite fields with rings of integers, but they do not fit very well with each other.

I thought of other cryptanalytic attacks that I know of. One of them was the “meet-in-the-middle” attack. She seemed a promising candidate. The attack is applied to a block cipher when it uses one part of the key material to perform the first half of encryption, and the other part for the second. This applied to the zip cipher, but the key material far outweighed the number of bits in the middle. Then it occurred to me, what if we use the linearity of CRC32: if we perform the XOR operation on the two outputs of the last CRC32, then the result will be independent of key2! Instead of calculating the intermediate state of the cipher and storing it in a table, I would calculate the XOR of the two intermediate states and store it instead.

I wrote a differential meeting “meeting in the middle” and launched it on my laptop. The stage, which used to take several hours, now completed in just a few seconds. The next stage, which could take a week on the GPU farm, ended in a few hours on one powerful CPU. I couldn’t optimize the third stage of the attack enough to affect the overall speed, but there was no need to move the data completely: we just calculated the candidates for each GPU on the computer with these cards. Nash wrote GPU code that worked at incredible speed.

The attack lasted ten days and ended in failure.

My heart was broken. Are we missing one of the possible keys? We went back and looked at the maximum process identifier on his laptop and found that it was several bits more than we expected, and therefore there were a little more possible source seeds for rand. I also double-checked all our code. Maybe we missed something? Maybe the version on the CPU worked somehow differently than on the GPU? Finally, I found that the version on the GPU could not find the correct key when it was second in the candidate list, but only the first. Rummaging through the code, we found that we confused the block index with the stream index when calculating the offset in the data structure.

We fixed the error, re-run the code and found the correct key within a day. Our client was very satisfied and gave us a big bonus for finding the key so quickly and saving him so much money beyond our initial estimate.

Now I am looking for work. If you have interesting problems with technical analysis or optimization, let me know.

---