1 00:00:01,350 --> 00:00:03,390 Hello, my name is Mike Stay. 2 00:00:03,390 --> 00:00:11,430 I'm the CTO of Pyrefx Corporation, and today I'm going to tell you about how we recovered several hundred thousand dollars worth of Bitcoin from an encrypted zip file. 3 00:00:12,950 --> 00:00:20,170 Around 20 years ago, I was working as a reverse engineer and cryptanalyst for AccessData while getting my physics degree at BYU. 4 00:00:20,590 --> 00:00:23,250 It was the late 90s, early 2000s. 5 00:00:23,250 --> 00:00:32,970 The US government had been gradually easing off export restrictions on software containing cryptography, but most software still contained pretty worthless password protection. 6 00:00:33,130 --> 00:00:40,410 We'd buy desktop office software, I'd reverse engineer it to figure out what algorithm it was using for access control, and then break the crypto. 7 00:00:40,450 --> 00:00:44,970 It was a never-ending stream of interesting but not impossible math puzzles. 8 00:00:44,970 --> 00:00:48,710 I wrote about 40 password crackers during my time there. 9 00:00:48,870 --> 00:00:54,230 We would sell them to home users, system administrators, local and federal law enforcement agencies. 10 00:00:54,490 --> 00:01:04,370 I got to go down to the Federal Law Enforcement Training Center in Glynco a few times to teach secret service agents, FBI agents, ATF, about cryptography and the use of our products. 11 00:01:05,250 --> 00:01:07,710 Two of the projects really stand out in my memory. 12 00:01:07,710 --> 00:01:10,370 The first was Microsoft Word 97. 13 00:01:10,950 --> 00:01:18,210 Before Word 97, the files were encrypted by XORing the bytes with a repeating 16-byte string derived from the password. 14 00:01:18,490 --> 00:01:24,470 The most common bytes in a Word file were either 0, 255, or 32, which is space. 15 00:01:24,470 --> 00:01:34,570 So we'd just look at the most common character in each of the 16 columns, try the 3 to the 16th variations on those, and recovering the key was usually instantaneous. 16 00:01:34,570 --> 00:01:47,090 But to help people feel like they'd gotten their money's worth, we'd put on a little show like the scene in War Games, where it would be animated, showing random characters that would gradually reveal the right password. 17 00:01:47,990 --> 00:01:50,610 Microsoft 97 changed that. 18 00:01:50,910 --> 00:01:58,710 It might have been possible to find out the encryption format through Microsoft Developer Network, but we were a small company and couldn't afford the subscription. 19 00:01:58,850 --> 00:02:03,650 It also wasn't clear we'd be allowed to write the cracker if we did get the info from them. 20 00:02:03,650 --> 00:02:07,370 So to figure out how it worked, I used softdice. 21 00:02:07,810 --> 00:02:12,150 There was a button on a cable that would go to a card in the computer. 22 00:02:12,170 --> 00:02:23,430 I'd type the password, and then hit enter and the button on the cable as fast as I could, and hope that it would break somewhere in the crypto stuff. 23 00:02:23,650 --> 00:02:28,830 I'd walk up the stack, trying to figure out where the algorithm was. 24 00:02:28,830 --> 00:02:45,250 This was in the days before IDA Pro, so I printed out a few dozen pages of assembly code and taped it to the wall, and then drew all over it with a red crayon, updating the function names and so on as I figured stuff out. 25 00:02:45,250 --> 00:02:47,790 I was very pleased when I finally worked it all out. 26 00:02:47,990 --> 00:02:54,550 At the time, Microsoft was only allowed to export 40-bit cryptography, so they did as much as they were legally permitted to do. 27 00:02:54,550 --> 00:03:08,710 They'd repeatedly MD5 the password with some salt, which is randomly chosen bytes that is stored in the file, and then they'd get a 40-bit key, then they'd add salt to that and repeatedly hash it again. 28 00:03:08,710 --> 00:03:13,090 So it took about half a second to test a password on the computers at the time. 29 00:03:13,090 --> 00:03:18,290 So despite being a 40-bit key space, it was a fairly hard problem to attack. 30 00:03:18,770 --> 00:03:23,550 We had to resort to a dictionary attack, because breaking it outright was pretty much impossible. 31 00:03:24,550 --> 00:03:42,770 We did eventually write a cracker for larger companies that had their own computer labs and resources, other large agencies, to brute force the 40-bit key space using the fancy MMX instructions on the Pentium. 32 00:03:42,810 --> 00:03:47,590 This was long before graphics processors were available. 33 00:03:47,590 --> 00:03:52,670 I knew of one place that ran the software for nine months before finally getting in. 34 00:03:52,670 --> 00:03:57,090 The other really fun one I did was Zip Archives. 35 00:03:57,090 --> 00:04:06,150 The developer of PKZip, Phil Katz, made the decision, which was unusual at the time, to document his file format and include it with his software. 36 00:04:06,670 --> 00:04:09,090 That made it a favorite of developers. 37 00:04:09,090 --> 00:04:12,730 Roger Schlafly designed the stream cipher used for encrypting the archives. 38 00:04:12,730 --> 00:04:17,790 The Zip standard quickly became by far the most popular compression format on Windows. 39 00:04:17,790 --> 00:04:27,010 And many other formats, like Java's JAR format, OpenOffice's document formats, are really just Zip files with a particular directory structure inside. 40 00:04:29,370 --> 00:04:33,490 InfoZip is an open source implementation of the software. 41 00:04:33,490 --> 00:04:38,250 It was used as the basis for nearly all other branded Zip software, like WinZip. 42 00:04:38,250 --> 00:04:45,030 And at the time I was trying to crack it, WinZip had 95% of the market, according to CNET downloads. 43 00:04:47,210 --> 00:04:53,150 Eli Biem and Paul Kosher had published a known plaintext attack on the cipher. 44 00:04:53,150 --> 00:04:56,490 But the known plaintext was compressed plaintext. 45 00:04:56,490 --> 00:05:03,390 To get the Huffman codes at the start of a deflated file, you basically need 32 kilobytes of the file. 46 00:05:03,870 --> 00:05:08,210 The attack was practically useless to law enforcement agencies. 47 00:05:08,250 --> 00:05:14,690 This diagram is an illustration of the internal workings of the Zip cipher. 48 00:05:14,690 --> 00:05:18,570 Each of these boxes represents a byte, 8 bits. 49 00:05:18,670 --> 00:05:24,210 The cipher has 96 bits of internal state, split into three 32-bit chunks. 50 00:05:24,210 --> 00:05:28,610 One is called Key0, Key1, and Key2. 51 00:05:28,610 --> 00:05:39,150 This subscript indicates the state of that chunk after having processed that many bytes of text. 52 00:05:39,250 --> 00:05:41,470 So here, this is the initial state. 53 00:05:41,470 --> 00:05:47,710 We feed in the first byte of text, and we get the subsequent state of Key0. 54 00:05:47,710 --> 00:05:52,990 Then we take part of that and feed it in here, and we get the subsequent state of Key1. 55 00:05:52,990 --> 00:05:57,750 Then we take one of these bytes and feed it in here, and get the subsequent state of Key2. 56 00:05:57,750 --> 00:06:03,870 Then we do one more operation on these two low bytes to get the stream byte. 57 00:06:04,870 --> 00:06:10,570 Going into a little more detail, this first section is CRC32. 58 00:06:10,570 --> 00:06:13,790 CRC stands for Cyclical Redundancy Check. 59 00:06:13,790 --> 00:06:21,090 It was designed for detecting errors on the circular tracks that you would find on floppy disks. 60 00:06:21,370 --> 00:06:25,230 So here we can see the shift, it's being shifted right 8 bits. 61 00:06:25,230 --> 00:06:33,210 We take these 8 bits that got shifted off the bottom, and use them to look up a 32-bit word in this table. 62 00:06:33,370 --> 00:06:39,430 Then we take the byte that's coming in, and we also look up a 32-bit word for that one in the table. 63 00:06:39,430 --> 00:06:49,350 Then we XOR the high 24 bits here, that were left after shifting it down, with these two words, and we get the new state of Key0. 64 00:06:50,150 --> 00:07:03,130 We take the low byte of the new value of Key0, add it to the current state of Key1, multiply by this constant, add 1, and get the new state of Key1. 65 00:07:03,770 --> 00:07:07,590 So this is called a truncated linear congruential generator. 66 00:07:07,590 --> 00:07:13,070 Truncated because we're only taking the high byte as output. 67 00:07:13,070 --> 00:07:15,850 Linear because it's addition. 68 00:07:16,290 --> 00:07:19,710 Congruential because it's modulo 2 to the 32. 69 00:07:19,710 --> 00:07:26,290 And generator because it's spitting out pseudo-random bytes. 70 00:07:26,290 --> 00:07:31,450 So it takes this byte that it's spitting out and feeds it into CRC32 again. 71 00:07:31,450 --> 00:07:42,610 Now, this is a linear feedback shift register, but this one is linear with respect to XOR, while this one is linear with respect to addition, with carries. 72 00:07:42,610 --> 00:07:48,430 So they don't work well together, and that's what really gives it whatever strength it does have. 73 00:07:49,730 --> 00:07:58,510 So, CRC32, truncated linear congruential generator, another CRC32, and then this pseudo-squaring operation. 74 00:07:58,510 --> 00:08:03,250 If you look in the source code, the pseudo-squaring operation is like this. 75 00:08:03,250 --> 00:08:12,390 You take Key2 and the low 16 bits of that, and you OR it with 2, so you set bit 1. 76 00:08:12,790 --> 00:08:16,910 And then you multiply that by itself XOR1. 77 00:08:16,910 --> 00:08:20,050 So one of the values is going to be even and the other one's odd. 78 00:08:20,050 --> 00:08:23,670 You shift it down by 8 and take 8 bits. 79 00:08:23,670 --> 00:08:29,670 So it's the middle of this pseudo-squaring operation. 80 00:08:29,710 --> 00:08:34,390 And the result is a stream byte. 81 00:08:34,390 --> 00:08:45,650 Now, the way this stream cipher works is that you initialize it first with a password, and then you encrypt the plaintext that you want to encrypt. 82 00:08:45,690 --> 00:08:50,610 To make it harder, they encrypt some salt first. 83 00:08:53,530 --> 00:09:02,170 PKZip used bytes that were in memory, so it would allocate 10 bytes and use whatever bytes were there. 84 00:09:02,170 --> 00:09:04,010 That's how it got its entropy. 85 00:09:05,850 --> 00:09:16,130 InfoZip, because it was built for use on Linux as well as Windows, couldn't do that because when the memory was allocated, it was also initialized. 86 00:09:16,130 --> 00:09:20,110 So they got their entropy from the process ID and the timestamp. 87 00:09:20,110 --> 00:09:26,470 You'd XOR those two together and call srand on it to seed the random number generator. 88 00:09:26,470 --> 00:09:32,570 Then it would use rand to generate 10 bytes as salt. 89 00:09:32,730 --> 00:09:38,090 In the file, then you'd follow it by CRC32 and the plaintext. 90 00:09:38,290 --> 00:09:44,450 Now, BM and Kosher had their attack, and it was published when InfoZip was implemented. 91 00:09:44,450 --> 00:09:55,750 So they knew that if they just used rand, then if somebody had the timestamp and the process ID, they could compute these bytes. 92 00:09:55,850 --> 00:10:00,230 The CRC was stored in the file to check that the password was entered correctly. 93 00:10:00,230 --> 00:10:07,650 So they would know these bytes, and that would give them 12 bytes, which was sufficient to mount a known plaintext attack. 94 00:10:07,650 --> 00:10:10,550 So InfoZip tried to avoid that. 95 00:10:11,450 --> 00:10:14,430 And they made it harder, but not quite hard enough. 96 00:10:17,520 --> 00:10:25,200 So renaming these bytes individually, R0 through R9 are the bytes generated by rand. 97 00:10:25,200 --> 00:10:28,260 C0, C1 are the CRC32 bytes. 98 00:10:28,420 --> 00:10:33,860 And P0 through P3 and so on are the plaintext bytes. 99 00:10:33,860 --> 00:10:35,920 And I'll call this array X. 100 00:10:36,940 --> 00:10:44,220 Now, when you feed the password into the cipher, it treats it as though it's plaintext. 101 00:10:44,220 --> 00:10:50,660 You feed in the first password byte, it updates key 0, key 1, key 2, spits out a stream byte. 102 00:10:51,160 --> 00:10:58,680 And then it throws the stream byte away until it gets to the last character of the password. 103 00:10:58,760 --> 00:11:04,700 And that final stream byte is used to encrypt the first salt byte, R0. 104 00:11:05,540 --> 00:11:20,140 So I get this set of 10 bytes that I call Y, which is just these first 10 bytes generated by rand, exclusive word with the 10 bytes generated by the stream cipher. 105 00:11:20,440 --> 00:11:25,600 Now you'll notice here I call this S0, but this one is S1X. 106 00:11:25,600 --> 00:11:37,600 These ones that end in X depend on the values in X, but S0 only depends on the password itself. 107 00:11:38,180 --> 00:11:57,200 That turned out to be their tragic flaw, that when they encrypted this a second time, so they were using Y as the salt bytes in the file, they would generate S0 again because it was the same password. 108 00:11:58,300 --> 00:12:09,120 So they would XOR with S0 once to get the salt byte, XOR with S0 again to get the byte that was stored in the encryption header. 109 00:12:09,120 --> 00:12:25,280 Now all of these are hard to figure out because they depend both on the randomly generated bytes from rand, as well as the stream cipher bytes, twice over. 110 00:12:25,280 --> 00:12:27,480 So this is doubly encrypted stuff. 111 00:12:27,480 --> 00:12:50,920 But this first byte leaked, and given five files in the archive, all encrypted with the same password, this gave me eight bits of entropy per file to find the 32-bit internal state of the rand pseudorandom number generator. 112 00:12:51,920 --> 00:13:12,880 So given five files, I could simply take the first byte of each archive, run through all 32 bits of possible internal state, and verify that every tenth byte gave me the byte I was expecting. 113 00:13:12,880 --> 00:13:21,440 So I could uniquely identify the internal state, could uniquely find these ten bytes. 114 00:13:21,440 --> 00:13:24,980 And so then I had some place to stand to mount the attack. 115 00:13:24,980 --> 00:13:33,960 So the next thing I did was notice that I didn't need all 96 bits to produce the next stream byte. 116 00:13:34,460 --> 00:13:37,140 I only needed 40 bits. 117 00:13:37,140 --> 00:13:48,560 So here I didn't need to know both key 0 and... or rather the second and the first byte of key 0. 118 00:13:48,560 --> 00:13:51,900 I only needed to know the XOR of this byte with that one. 119 00:13:51,900 --> 00:13:53,680 So that's an 8-bit guess. 120 00:13:53,680 --> 00:13:59,680 I know the value from rand that's going in, so I can predict this thing. 121 00:14:02,080 --> 00:14:05,080 Here I'm multiplying by this constant. 122 00:14:06,840 --> 00:14:17,960 If I take the... I don't need to know the entire value of key 1, I just need to know the high byte of key 1 times the constant. 123 00:14:17,960 --> 00:14:21,820 So I've distributed this multiplication across the addition we had earlier. 124 00:14:21,820 --> 00:14:24,040 So here is the high byte of that. 125 00:14:26,860 --> 00:14:31,500 And when I add 1, it might cause a carry bit, so I have to guess a carry bit. 126 00:14:31,640 --> 00:14:33,540 Then it comes in here. 127 00:14:34,880 --> 00:14:37,580 I know what the high byte of this is. 128 00:14:38,280 --> 00:14:39,520 I feed it in. 129 00:14:39,520 --> 00:14:42,140 I just need to know these values. 130 00:14:42,140 --> 00:14:51,300 And given the stream byte, I can then figure out what the low 6 bits are here that are needed. 131 00:14:51,820 --> 00:14:59,540 This is how to figure out, given a stream byte, well, a plain text and a cipher text pair. 132 00:14:59,540 --> 00:15:07,040 These are the bits that you have to guess in order to get this stream byte. 133 00:15:07,040 --> 00:15:22,460 So what I would do is I would guess 40 bits, which would allow me to process this byte here. 134 00:15:22,760 --> 00:15:29,920 And so then I could check for each of the five files, does this value match what I expect it to? 135 00:15:29,920 --> 00:15:41,980 And since I had 40 bits that I was guessing and 40 bits of entropy to compare it to from the file, I could filter out all but one guess. 136 00:15:42,160 --> 00:15:51,760 And then for the next byte, I would guess 26 more bits and then just a few more bits to get the rest of the state after that point. 137 00:15:51,760 --> 00:15:58,740 Usually, once I found this 40-bit one, the next one I could get within a few minutes. 138 00:15:58,740 --> 00:16:09,780 The whole attack ran in about two hours on a Pentium at the time, cipher text only attack. 139 00:16:09,780 --> 00:16:13,260 I was able to break into these zip files. 140 00:16:13,400 --> 00:16:17,820 We caught several child pornographers that way. 141 00:16:18,900 --> 00:16:20,960 And I got a paper out of it. 142 00:16:20,960 --> 00:16:36,380 So in 2001, fast software encryption, I got this paper and that led 20 years later to a surprising message. 143 00:16:36,380 --> 00:16:49,200 So in October of last year, a guy contacts me out of the blue and says, I read your paper on known plaintext attacks and I've got this password that I've forgotten. 144 00:16:49,200 --> 00:16:51,160 Is there anything you can do to help? 145 00:16:51,160 --> 00:16:54,300 Can you tell me how things are looking these days? 146 00:16:54,300 --> 00:17:02,880 And so I looked it over, turns out he only had two files in the archive. 147 00:17:02,880 --> 00:17:17,100 With only two files, I didn't have enough information to derive the internal state of RAND and I didn't have enough information to filter the guesses I was making. 148 00:17:17,100 --> 00:17:23,080 So far more guesses would pass each filtering stage. 149 00:17:23,080 --> 00:17:31,740 And it worked out to be something like, on my back of the envelope calculations, something like 2 to the 70. 150 00:17:31,740 --> 00:17:38,020 So I told him, you know, compare the work done this year to find hash collisions in SHA-1. 151 00:17:38,160 --> 00:17:45,080 SHA-1 has 128-bit output, so to find a collision, you've got to look at 2 to the 64th hashes. 152 00:17:45,080 --> 00:17:47,360 That cost around $100,000. 153 00:17:47,360 --> 00:17:52,200 This is not something that you can use off-the-shelf software for. 154 00:17:52,620 --> 00:17:57,440 And then he blew my mind and said, I could spend so much on this archive. 155 00:17:58,200 --> 00:18:05,700 At that point I knew that he probably had several hundred thousand dollars of Bitcoin in this thing. 156 00:18:07,260 --> 00:18:11,080 At this point I started doing a more careful analysis. 157 00:18:11,080 --> 00:18:16,280 There are 96 bits of key material that need to be guessed in various stages. 158 00:18:16,440 --> 00:18:19,540 But I can't guess the bits of key material directly. 159 00:18:19,540 --> 00:18:29,300 Instead I have to guess bits of a function of the key material and use those constraints to limit what the key material could be. 160 00:18:30,260 --> 00:18:37,120 This first part is CRC32 of the initial key 0 value with the 0 byte. 161 00:18:37,120 --> 00:18:49,580 Since CRC32 itself is invertible, once I guess these 4 bytes, there's a very simple linear operation I do to recover the initial key 0 value itself. 162 00:18:49,920 --> 00:18:52,920 With key 1 it's a little more complicated. 163 00:18:52,920 --> 00:19:02,340 We take the initial key 1 value and multiply it by this constant from the truncated linear congruential generator to the nth power. 164 00:19:02,780 --> 00:19:06,440 And I'm guessing the high byte of that value. 165 00:19:06,440 --> 00:19:16,720 Given 4 of these, that'll put enough constraints on key 1 that I can brute force it and figure out what key 1 is given those 4 bytes. 166 00:19:16,760 --> 00:19:20,560 The initial value of key 2 I can guess directly. 167 00:19:21,440 --> 00:19:28,840 So in the first stage I guess these 5 bytes, that's 40 bits, and I guess 4 carry bits. 168 00:19:28,840 --> 00:19:52,460 These carry bits come from the possibility that when I add 1 in the truncated linear congruential generator, it carries over all the way to the 24th bit, which would change the value of this most significant byte. 169 00:19:52,460 --> 00:19:54,580 So I have to guess these carry bits. 170 00:19:54,580 --> 00:20:03,700 I need to guess 2 for each file, there are 2 files, because I have 2 passes of encryption that I do to each byte. 171 00:20:03,740 --> 00:20:09,160 So 2 passes of encryption, 2 files, makes 4 carry bits that need to be guessed. 172 00:20:09,160 --> 00:20:20,800 So the total work for this stage is 2 to the 44th, and after filtering the 16 bits from the file, I get 2 to the 28th key guesses passing. 173 00:20:20,800 --> 00:20:28,720 In stage 2 I guess these 3 bytes, that's 24 bits, 4 more carry bits makes 28. 174 00:20:28,900 --> 00:20:35,380 Added to the previous 2 to the 28th key guesses, I have 2 to the 56th keys to filter. 175 00:20:35,420 --> 00:20:38,960 And after filtering, 2 to the 40th remain. 176 00:20:39,900 --> 00:20:45,640 In stage 3 I guess 16 bits plus 4 carry bits makes 20. 177 00:20:46,100 --> 00:20:50,580 Previous 40 carried forward gives us 2 to the 60th keys to test. 178 00:20:50,580 --> 00:20:54,200 And after filtering, 2 to the 44th pass the third stage. 179 00:20:55,740 --> 00:21:02,440 In the fourth stage, I guess 16, as before, 4 carry bits gives us 20. 180 00:21:02,520 --> 00:21:06,020 44 from the previous stage, 20 now makes 64. 181 00:21:06,180 --> 00:21:09,700 This was the most complicated stage, 2 to the 64th. 182 00:21:09,760 --> 00:21:12,440 After filtering, 2 to the 48th remain. 183 00:21:12,440 --> 00:21:15,820 Now in my original attack, this is where I would stop. 184 00:21:15,820 --> 00:21:18,120 I have all the key material. 185 00:21:18,120 --> 00:21:28,380 With these 4 bytes, I can brute force key 1, run through the 2 to the 32 possibilities, and get the value itself. 186 00:21:28,380 --> 00:21:31,420 I can invert this and that would work. 187 00:21:31,420 --> 00:21:45,600 But at this point it struck me, if I have to do 2 to the 32 work for each of these 2 to the 48 keys, that will give a total cost of 2 to the 80th. 188 00:21:45,600 --> 00:21:49,560 There is no way we could do a 2 to the 80th attack. 189 00:21:49,560 --> 00:22:01,950 So I had to come up with a special approach, a new idea to make this step much less expensive. 190 00:22:03,000 --> 00:22:10,740 I remembered having read somewhere about an attack on truncated linear congruential generators that uses lattice reduction. 191 00:22:10,740 --> 00:22:25,660 Lattice reduction is the idea that if you have a lattice, which is like a vector space but only integer coordinates, and a basis for that lattice, then you can find a nicer basis. 192 00:22:25,820 --> 00:22:30,540 Where nicer means that the vectors are shorter and closer to orthogonal. 193 00:22:30,540 --> 00:22:33,100 So here I have a two-dimensional lattice. 194 00:22:33,100 --> 00:22:38,640 Here's a basis for that lattice, where one of these goes here and another goes there. 195 00:22:38,640 --> 00:22:47,580 Every point on this grid has a coordinate in terms of how many steps of this kind and how many steps of that kind it takes to get there. 196 00:22:48,000 --> 00:22:50,640 But lattice reduction gives you a much nicer basis. 197 00:22:50,640 --> 00:22:53,680 These are both shorter and closer to orthogonal. 198 00:22:56,340 --> 00:23:00,560 Lattice reduction is in general a hard problem. 199 00:23:00,560 --> 00:23:09,880 About half of the candidates for the post-quantum cryptography ciphers that NIST is considering right now use lattice reduction, for example, NTRU. 200 00:23:09,880 --> 00:23:12,280 But in small cases, it's tractable. 201 00:23:12,280 --> 00:23:17,780 And I had a very small case, only four or five dimensional. 202 00:23:17,780 --> 00:23:25,160 So I went and poked around on the cryptography stack exchange and found exactly what I needed. 203 00:23:25,640 --> 00:23:35,200 The vectors, in this case, the basis vectors were powers of the constant from the truncated linear congruential generator. 204 00:23:35,200 --> 00:23:40,880 In our case, it was 08088405 in hex. 205 00:23:42,580 --> 00:23:52,720 So you take the, if we call that C, then C and C squared and C cubed and C to the fourth and so on become basis vectors for this lattice. 206 00:23:52,720 --> 00:23:59,420 And then you add in one more basis vector for the modulus, which in our case was two to the 32, here called M. 207 00:23:59,420 --> 00:24:27,880 So the idea was that given the four most significant bytes of the key one value times this consecutive powers of C, I would do a linear transformation, get a value that was close to a basis vector in this small vector basis, then round off to get it exactly to a basis vector and then transform back. 208 00:24:27,880 --> 00:24:33,160 That would give me the exact value of key one zero. 209 00:24:33,340 --> 00:24:38,520 So I wrote up a Sage program to figure out how exactly that would work. 210 00:24:39,320 --> 00:24:45,000 Sage is a library for Python that lets you do linear algebra, among many other things. 211 00:24:46,160 --> 00:24:49,860 So here we have the modulus, two to the 32. 212 00:24:50,120 --> 00:24:54,060 We have the constant from the truncated linear congruential generator. 213 00:24:54,720 --> 00:25:00,040 We have the matrix that defines the basis for our four dimensional vector space. 214 00:25:00,400 --> 00:25:10,300 Now the vectors themselves are the modulus and the powers of the constant with minus ones on the diagonal. 215 00:25:10,580 --> 00:25:13,260 This does the lattice reduction step. 216 00:25:13,260 --> 00:25:32,120 Now to test how B worked, I would generate a random initial k1 value, then compute the actual powers of C times k1, modulo m, that I was going to try to recover. 217 00:25:32,120 --> 00:25:33,600 So I'd print these out. 218 00:25:34,100 --> 00:25:37,120 The most significant bytes were the things that I had guessed. 219 00:25:37,120 --> 00:25:41,040 I wanted to recover k's from the MSBs. 220 00:25:41,040 --> 00:25:50,700 So the secret stuff that I needed to know were the low 24 bits, the part that I had masked off up here. 221 00:25:50,700 --> 00:25:55,700 So this is the secret 24 bit values that I need to guess. 222 00:25:55,920 --> 00:26:06,360 Given the vector that is the most significant bytes, I multiplied it by B, which switched from one lattice to the other, did a basis change. 223 00:26:06,360 --> 00:26:14,380 Then I rounded to the nearest vector in this nicer basis. 224 00:26:14,520 --> 00:26:23,800 And that meant that I would get an actual value of k10 that would produce those same most significant bytes. 225 00:26:24,380 --> 00:26:30,200 Then I reversed that, transformed back, and got the guess. 226 00:26:30,200 --> 00:26:31,960 And I'd print it out. 227 00:26:31,960 --> 00:26:35,520 And when I started doing this, the guess was never right. 228 00:26:36,360 --> 00:26:38,720 Or rarely right. 229 00:26:39,220 --> 00:26:45,180 And that was because of the limited number of guesses I had here. 230 00:26:47,900 --> 00:26:57,500 If I could do one more stage, then I would be able to get the right answer every time. 231 00:26:57,500 --> 00:27:04,600 But here I had too few powers of C to find out what it was exactly. 232 00:27:04,600 --> 00:27:09,890 But then I started checking the difference between the guess and the actual value. 233 00:27:10,540 --> 00:27:17,660 So I take the keys, subtract off the MSBs, and the difference between the guess and the actual one 234 00:27:22,250 --> 00:27:28,290 turned out to fall into one of 36 possibilities every time. 235 00:27:28,290 --> 00:27:38,030 So as I thought about it, I realized that in this four dimensional space, by truncating it and just using the most significant bytes, I was adding a bunch of noise. 236 00:27:38,350 --> 00:27:46,350 And so the point in the four dimensional space I wanted was at the center of a cell. 237 00:27:46,350 --> 00:27:55,710 And what I was actually getting was a point near the hull of this cell that tiled this four dimensional space. 238 00:27:55,710 --> 00:28:07,550 And so because it was always within this cell, there were only a finite number of other possible lattice points that it could be. 239 00:28:08,350 --> 00:28:23,750 And so I computed for all of the two to the 32 possible K10 values, what the set of guesses were, and found that they fit into this one of 36 classes. 240 00:28:23,750 --> 00:28:31,330 And so instead of having to try out all two to the 32 possible key ones each time, I would only have to do 36. 241 00:28:31,330 --> 00:28:34,870 So instead of four billion, 36 values. 242 00:28:34,870 --> 00:28:37,090 And that made the attack feasible again. 243 00:28:38,270 --> 00:28:47,190 Once we'd guessed all the key material, we could filter the two to the 48 keys at stage four by using the remaining bytes in the encryption header. 244 00:28:47,770 --> 00:28:54,770 My business partner, Nash Foster, then started working on adapting my CPU based attack to run on GPUs. 245 00:28:54,770 --> 00:29:02,310 He wrote the code harness for getting code and data onto the GPUs, did all the CUDA stuff, advised me on how to structure the attack. 246 00:29:02,730 --> 00:29:16,210 We discovered very quickly, though, that getting the petabytes of possible keys onto the GPU would take too long, that the GPUs would just be sitting idle for most of the time we were paying for them, waiting for the data to arrive to process. 247 00:29:16,210 --> 00:29:18,330 So I went back to the drawing board. 248 00:29:18,470 --> 00:29:26,110 In each stage, I was guessing a whole bunch of bits and then filtering those results using the two bytes from the two archives in the file. 249 00:29:26,350 --> 00:29:30,170 I'd only keep about one out of 65,000. 250 00:29:30,250 --> 00:29:39,930 If I had some way of using that information to derive bits, rather than just guessing and checking, it'd save a lot of work, and more importantly, a lot of network traffic. 251 00:29:40,090 --> 00:29:44,410 The problem with that idea was that the math is too complicated. 252 00:29:44,410 --> 00:29:50,990 It involves mixing finite fields with integer rings, and those simply don't play well together. 253 00:29:51,130 --> 00:29:57,690 So I thought about some other cryptanalytic attacks I knew, and one that seemed promising was a meet-in-the-middle attack. 254 00:29:58,330 --> 00:30:11,810 A meet-in-the-middle attack usually applies to block ciphers, when it uses one part of the key material to do the first half of the encryption, and the second part of the key material to do the second half of the encryption. 255 00:30:12,830 --> 00:30:22,170 The reason we have triple DES instead of double DES is precisely because of this. 256 00:30:22,170 --> 00:30:28,650 Triple DES is a 112-bit cipher, even though there are three keys involved. 257 00:30:29,690 --> 00:30:32,950 You can do encrypt, and then decrypt, and then encrypt. 258 00:30:32,950 --> 00:30:35,190 So 112 bits of strength. 259 00:30:35,190 --> 00:30:42,290 If it's 112 bits, why not just do DES with one key, and then DES with another key, encrypting it twice? 260 00:30:42,290 --> 00:30:44,210 Well, the answer is right here. 261 00:30:44,210 --> 00:30:54,910 What you do is you take your plaintext-ciphertext pair, and then encrypt the plaintext under all 256 possible first DES keys. 262 00:30:55,430 --> 00:31:01,390 And then you take the ciphertext and decrypt it under all possible 256 DES keys. 263 00:31:01,390 --> 00:31:06,510 And right here in the middle, chances are that one of them will match. 264 00:31:06,510 --> 00:31:27,130 And so you sort all of these intermediate plaintexts, and whenever you find two intermediate texts that are the same, one of them came from the plaintext and one came from the ciphertext, and that uniquely identifies the key that should go between these two. 265 00:31:27,130 --> 00:31:39,210 So a meet-in-the-middle attack works when you've got key material that is not all used at every stage of the cipher. 266 00:31:39,210 --> 00:31:42,190 And in this stream cipher, that seemed to be the case, right? 267 00:31:42,190 --> 00:31:54,310 I had only key 0 at the beginning and only key 2 at the end, and it seemed like we could do something in the middle, but it wasn't quite right. 268 00:31:54,310 --> 00:32:00,310 But then I realized I could use the XOR of certain bytes in the middle of the cipher to mount the attack. 269 00:32:01,470 --> 00:32:04,550 Here's a diagram of the cipher again. 270 00:32:04,550 --> 00:32:15,630 And the cipher gets called four times in each stage for each byte, two for each file, the double encryption of the byte from rand. 271 00:32:16,110 --> 00:32:28,030 So in the center of the cipher, there are four different most significant bytes for key 1 after each of these encryptions. 272 00:32:28,090 --> 00:32:39,350 So what I did was take the first of those four and exclusivore it with each of the other three to get a 24-bit key into a table. 273 00:32:39,350 --> 00:32:43,690 And under that key, I would store my guess for these bits. 274 00:32:44,910 --> 00:32:53,990 Then from the other side, given a stream byte, there are 64 possible 14-bit values here. 275 00:32:53,990 --> 00:33:06,850 So I would guess some intermediate stream bytes, six bits of this, I guess it's boxed here, these six bits to figure out what the other eight are. 276 00:33:06,850 --> 00:33:15,750 And that would allow me to derive linearly from this stuff what this most significant byte of key 1 was again. 277 00:33:15,750 --> 00:33:25,190 And so given these bits that I was guessing, I would derive a key and store these bits under that key. 278 00:33:25,230 --> 00:33:45,130 And then anytime I had a collision, I would know that the set of bits here that I guessed were consistent with the set of bits here that I guessed to give this plaintext going to that stream byte. 279 00:33:46,330 --> 00:33:56,340 Now that is far smaller than running through all of the possibilities and then filtering. 280 00:33:57,010 --> 00:34:03,590 The amount of memory it required was on the order of a few megabytes. 281 00:34:03,590 --> 00:34:06,430 So here is the code itself. 282 00:34:06,730 --> 00:34:10,990 This is stage 1a moving forward through the cipher. 283 00:34:10,990 --> 00:34:20,470 We guess the initial stream byte, because it was XORed with itself twice, we have no information about it, so we would guess that one. 284 00:34:20,470 --> 00:34:25,250 Then we'd guess chunk 2, which came from CRC 32 of key 0. 285 00:34:25,250 --> 00:34:29,150 Chunk 3 is the most significant byte of key 1. 286 00:34:30,210 --> 00:34:33,390 Here are the carry bits. 287 00:34:33,570 --> 00:34:40,850 There are two bits for each of the two files, so 2 to the 4th is 16 possible carry bits. 288 00:34:43,790 --> 00:34:50,050 This is debugging code for checking against files that we created ourselves. 289 00:34:51,410 --> 00:35:06,850 This is the first half of the cipher, and it updates an upper and a lower bound on the possible low 24 bits of key 1, so that if it ever goes out of bounds, we can throw it away. 290 00:35:08,610 --> 00:35:13,850 We compute various bytes, get through here. 291 00:35:13,850 --> 00:35:29,270 If it has passed all of these upper and lower bound checks, then this converts those four most significant bytes to a map key and stores the candidate under that map key. 292 00:35:29,830 --> 00:35:39,970 In the second half, we're guessing the stream1x byte for file 0. 293 00:35:40,290 --> 00:35:51,710 We're guessing the 64-bit prefix, because each stream byte has 64 possible pre-images under the pseudo-squaring operation. 294 00:35:52,270 --> 00:35:59,530 So these are all of the indexed pre-images, and this gets the specific pre-image that we're caring about. 295 00:36:00,090 --> 00:36:02,030 There's more debugging information. 296 00:36:02,030 --> 00:36:04,070 Again, we do the second half step. 297 00:36:04,070 --> 00:36:11,990 And if there are no consistent results, then we just go to the next guess. 298 00:36:12,010 --> 00:36:17,190 Here we're guessing the stream1x pass for file 1. 299 00:36:17,630 --> 00:36:19,870 We do that second half step. 300 00:36:19,870 --> 00:36:23,990 And again, if there are no consistent ones, we go back to the next guess. 301 00:36:24,830 --> 00:36:31,310 Finally, we compute the stream1y bytes. 302 00:36:33,010 --> 00:36:37,950 And if there are no consistent ones with that prefix, we continue. 303 00:36:37,950 --> 00:36:52,370 So now given each of the possibilities for the first and second and third bytes, we put them together into a map key, and then meet in the middle. 304 00:36:54,020 --> 00:36:57,320 Here is the CRC20. 305 00:36:58,480 --> 00:37:05,860 If you'd like to look at the code, you can see how these exclusive work together, and we can derive some certain things. 306 00:37:05,860 --> 00:37:19,180 So starting at the bottom, we derive bits 15 to 2 of K and L from 15 to 2 of S and T, and these bytes OP that we've computed. 307 00:37:19,180 --> 00:37:28,130 So in the center, we find those groups that... 308 00:37:29,130 --> 00:37:38,410 those guesses that work, and we push back that guess whenever the two match up with each other. 309 00:37:38,410 --> 00:37:40,290 And here's some more debugging information. 310 00:37:40,650 --> 00:38:03,790 So that's the idea of the differential meet in the middle attack, is computing forwards and backwards, exclusive oring one of the bytes with the other three, and then whenever the two guesses match, we have a set of candidates that's a product of the set from the first half of the attack with the set from the second half of the attack. 311 00:38:03,790 --> 00:38:15,030 Using the differential meet in the middle attack on stage 1 and stage 2 allowed us to reduce the complexity of the attack in stage 1 from 2 to the 40th down to 2 to the 22nd. 312 00:38:15,030 --> 00:38:18,730 That's from trillions down to mere millions. 313 00:38:18,730 --> 00:38:24,290 And then in stage 2 from 2 to the 56th down to 2 to the 40th. 314 00:38:24,290 --> 00:38:31,210 And that let us run stages 1 and 2 on each of the machines that had GPUs attached to it. 315 00:38:31,210 --> 00:38:36,650 We completely eliminated the need to ship batches of keys over the network. 316 00:38:36,650 --> 00:38:45,110 And so we could generate the keys in place and then run what we called the GPU stage 3 kernel that did all the rest of the attack. 317 00:38:45,550 --> 00:38:47,750 Now we ran it for 10 days. 318 00:38:48,310 --> 00:38:53,630 We had tried it on all of our test archives that we'd created. 319 00:38:53,630 --> 00:38:54,910 It worked fine. 320 00:38:56,190 --> 00:39:00,870 10 days passed and it didn't find a key. 321 00:39:00,870 --> 00:39:03,010 We were distraught, pulling our hair out. 322 00:39:03,010 --> 00:39:04,230 What have we done wrong? 323 00:39:04,230 --> 00:39:10,690 We went back and discovered that there were a few other process IDs that could have worked. 324 00:39:10,990 --> 00:39:14,930 And we were wondering, oh no, are we going to have to do this four more times? 325 00:39:16,290 --> 00:39:29,830 But then our client, who was a programmer himself, discovered that there was a bug between the GPU stage and the CPU stage. 326 00:39:29,830 --> 00:39:37,250 So when I had run the tests, I had done it locally on my computer using the CPU version. 327 00:39:37,270 --> 00:39:45,010 And the test, we knew exactly where the key had to be, so it was a very small piece of key space that we had to check. 328 00:39:45,310 --> 00:40:00,810 But when my client went back and tried it again using the GPU stage 3, he discovered that when the key candidate was the first one in a list, it succeeded, but when it was the second one, it failed. 329 00:40:01,250 --> 00:40:04,210 And that led me to this line right here. 330 00:40:04,230 --> 00:40:08,810 We had swapped the thread index with the block index. 331 00:40:08,810 --> 00:40:22,420 So instead of incrementing by one into the current block, it would increment the block number and go off into space that was uninitialized, and so it would never work. 332 00:40:23,010 --> 00:40:28,910 So by switching the block index with the thread index, we started the search over again. 333 00:40:28,910 --> 00:40:40,230 Within a day and a half, we had found the three keys that decrypted the archive, and our client was able to get his Bitcoin keys out. 334 00:40:41,350 --> 00:41:00,990 In the end, the improvements that I made to my old attack took it from something that we estimated at approximately $100,000 and a year of processing, down to something that took about $10,000 of GPU time and a little under two weeks. 335 00:41:01,710 --> 00:41:08,110 Our client was very pleased and gave us a big bonus, and that's how we recovered his Bitcoin core. 336 00:41:08,230 --> 00:41:09,250 Thank you very much.