[00:01.350 --> 00:11.430]  Hello, my name is Mike Stay. 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.
[00:12.950 --> 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.
[00:20.590 --> 00:23.250]  It was the late 90s, early 2000s.
[00:23.250 --> 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.
[00:33.130 --> 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.
[00:40.450 --> 00:44.970]  It was a never-ending stream of interesting but not impossible math puzzles.
[00:44.970 --> 00:48.710]  I wrote about 40 password crackers during my time there.
[00:48.870 --> 00:54.230]  We would sell them to home users, system administrators, local and federal law enforcement agencies.
[00:54.490 --> 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.
[01:05.250 --> 01:07.710]  Two of the projects really stand out in my memory.
[01:07.710 --> 01:10.370]  The first was Microsoft Word 97.
[01:10.950 --> 01:18.210]  Before Word 97, the files were encrypted by XORing the bytes with a repeating 16-byte string derived from the password.
[01:18.490 --> 01:24.470]  The most common bytes in a Word file were either 0, 255, or 32, which is space.
[01:24.470 --> 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.
[01:34.570 --> 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.
[01:47.990 --> 01:50.610]  Microsoft 97 changed that.
[01:50.910 --> 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.
[01:58.850 --> 02:03.650]  It also wasn't clear we'd be allowed to write the cracker if we did get the info from them.
[02:03.650 --> 02:07.370]  So to figure out how it worked, I used softdice.
[02:07.810 --> 02:12.150]  There was a button on a cable that would go to a card in the computer.
[02:12.170 --> 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.
[02:23.650 --> 02:28.830]  I'd walk up the stack, trying to figure out where the algorithm was.
[02:28.830 --> 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.
[02:45.250 --> 02:47.790]  I was very pleased when I finally worked it all out.
[02:47.990 --> 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.
[02:54.550 --> 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.
[03:08.710 --> 03:13.090]  So it took about half a second to test a password on the computers at the time.
[03:13.090 --> 03:18.290]  So despite being a 40-bit key space, it was a fairly hard problem to attack.
[03:18.770 --> 03:23.550]  We had to resort to a dictionary attack, because breaking it outright was pretty much impossible.
[03:24.550 --> 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.
[03:42.810 --> 03:47.590]  This was long before graphics processors were available.
[03:47.590 --> 03:52.670]  I knew of one place that ran the software for nine months before finally getting in.
[03:52.670 --> 03:57.090]  The other really fun one I did was Zip Archives.
[03:57.090 --> 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.
[04:06.670 --> 04:09.090]  That made it a favorite of developers.
[04:09.090 --> 04:12.730]  Roger Schlafly designed the stream cipher used for encrypting the archives.
[04:12.730 --> 04:17.790]  The Zip standard quickly became by far the most popular compression format on Windows.
[04:17.790 --> 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.
[04:29.370 --> 04:33.490]  InfoZip is an open source implementation of the software.
[04:33.490 --> 04:38.250]  It was used as the basis for nearly all other branded Zip software, like WinZip.
[04:38.250 --> 04:45.030]  And at the time I was trying to crack it, WinZip had 95% of the market, according to CNET downloads.
[04:47.210 --> 04:53.150]  Eli Biem and Paul Kosher had published a known plaintext attack on the cipher.
[04:53.150 --> 04:56.490]  But the known plaintext was compressed plaintext.
[04:56.490 --> 05:03.390]  To get the Huffman codes at the start of a deflated file, you basically need 32 kilobytes of the file.
[05:03.870 --> 05:08.210]  The attack was practically useless to law enforcement agencies.
[05:08.250 --> 05:14.690]  This diagram is an illustration of the internal workings of the Zip cipher.
[05:14.690 --> 05:18.570]  Each of these boxes represents a byte, 8 bits.
[05:18.670 --> 05:24.210]  The cipher has 96 bits of internal state, split into three 32-bit chunks.
[05:24.210 --> 05:28.610]  One is called Key0, Key1, and Key2.
[05:28.610 --> 05:39.150]  This subscript indicates the state of that chunk after having processed that many bytes of text.
[05:39.250 --> 05:47.710]  So here, this is the initial state. We feed in the first byte of text, and we get the subsequent state of Key0.
[05:47.710 --> 05:52.990]  Then we take part of that and feed it in here, and we get the subsequent state of Key1.
[05:52.990 --> 05:57.750]  Then we take one of these bytes and feed it in here, and get the subsequent state of Key2.
[05:57.750 --> 06:03.870]  Then we do one more operation on these two low bytes to get the stream byte.
[06:04.870 --> 06:10.570]  Going into a little more detail, this first section is CRC32.
[06:10.570 --> 06:13.790]  CRC stands for Cyclical Redundancy Check.
[06:13.790 --> 06:21.090]  It was designed for detecting errors on the circular tracks that you would find on floppy disks.
[06:21.370 --> 06:25.230]  So here we can see the shift, it's being shifted right 8 bits.
[06:25.230 --> 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.
[06:33.370 --> 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.
[06:39.430 --> 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.
[06:50.150 --> 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.
[07:03.770 --> 07:07.590]  So this is called a truncated linear congruential generator.
[07:07.590 --> 07:13.070]  Truncated because we're only taking the high byte as output.
[07:13.070 --> 07:15.850]  Linear because it's addition.
[07:16.290 --> 07:19.710]  Congruential because it's modulo 2 to the 32.
[07:19.710 --> 07:26.290]  And generator because it's spitting out pseudo-random bytes.
[07:26.290 --> 07:31.450]  So it takes this byte that it's spitting out and feeds it into CRC32 again.
[07:31.450 --> 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.
[07:42.610 --> 07:48.430]  So they don't work well together, and that's what really gives it whatever strength it does have.
[07:49.730 --> 07:58.510]  So, CRC32, truncated linear congruential generator, another CRC32, and then this pseudo-squaring operation.
[07:58.510 --> 08:03.250]  If you look in the source code, the pseudo-squaring operation is like this.
[08:03.250 --> 08:12.390]  You take Key2 and the low 16 bits of that, and you OR it with 2, so you set bit 1.
[08:12.790 --> 08:16.910]  And then you multiply that by itself XOR1.
[08:16.910 --> 08:20.050]  So one of the values is going to be even and the other one's odd.
[08:20.050 --> 08:23.670]  You shift it down by 8 and take 8 bits.
[08:23.670 --> 08:29.670]  So it's the middle of this pseudo-squaring operation.
[08:29.710 --> 08:34.390]  And the result is a stream byte.
[08:34.390 --> 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.
[08:45.690 --> 08:50.610]  To make it harder, they encrypt some salt first.
[08:53.530 --> 09:02.170]  PKZip used bytes that were in memory, so it would allocate 10 bytes and use whatever bytes were there.
[09:02.170 --> 09:04.010]  That's how it got its entropy.
[09:05.850 --> 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.
[09:16.130 --> 09:20.110]  So they got their entropy from the process ID and the timestamp.
[09:20.110 --> 09:26.470]  You'd XOR those two together and call srand on it to seed the random number generator.
[09:26.470 --> 09:32.570]  Then it would use rand to generate 10 bytes as salt.
[09:32.730 --> 09:38.090]  In the file, then you'd follow it by CRC32 and the plaintext.
[09:38.290 --> 09:44.450]  Now, BM and Kosher had their attack, and it was published when InfoZip was implemented.
[09:44.450 --> 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.
[09:55.850 --> 10:00.230]  The CRC was stored in the file to check that the password was entered correctly.
[10:00.230 --> 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.
[10:07.650 --> 10:10.550]  So InfoZip tried to avoid that.
[10:11.450 --> 10:14.430]  And they made it harder, but not quite hard enough.
[10:17.520 --> 10:25.200]  So renaming these bytes individually, R0 through R9 are the bytes generated by rand.
[10:25.200 --> 10:28.260]  C0, C1 are the CRC32 bytes.
[10:28.420 --> 10:33.860]  And P0 through P3 and so on are the plaintext bytes.
[10:33.860 --> 10:35.920]  And I'll call this array X.
[10:36.940 --> 10:44.220]  Now, when you feed the password into the cipher, it treats it as though it's plaintext.
[10:44.220 --> 10:50.660]  You feed in the first password byte, it updates key 0, key 1, key 2, spits out a stream byte.
[10:51.160 --> 10:58.680]  And then it throws the stream byte away until it gets to the last character of the password.
[10:58.760 --> 11:04.700]  And that final stream byte is used to encrypt the first salt byte, R0.
[11:05.540 --> 11:16.240]  So I get this set of 10 bytes that I call Y, which is just these first 10 bytes generated by rand,
[11:16.240 --> 11:20.140]  exclusive word with the 10 bytes generated by the stream cipher.
[11:20.440 --> 11:25.600]  Now you'll notice here I call this S0, but this one is S1X.
[11:25.600 --> 11:37.600]  These ones that end in X depend on the values in X, but S0 only depends on the password itself.
[11:38.180 --> 11:45.760]  That turned out to be their tragic flaw, that when they encrypted this a second time,
[11:45.760 --> 11:50.420]  so they were using Y as the salt bytes in the file,
[11:51.420 --> 11:57.200]  they would generate S0 again because it was the same password.
[11:58.300 --> 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.
[12:09.120 --> 12:21.180]  Now all of these are hard to figure out because they depend both on the randomly generated bytes from rand,
[12:21.180 --> 12:25.280]  as well as the stream cipher bytes, twice over.
[12:25.280 --> 12:27.480]  So this is doubly encrypted stuff.
[12:27.480 --> 12:36.940]  But this first byte leaked, and given five files in the archive, all encrypted with the same password,
[12:36.940 --> 12:50.920]  this gave me eight bits of entropy per file to find the 32-bit internal state of the rand pseudorandom number generator.
[12:51.920 --> 12:59.260]  So given five files, I could simply take the first byte of each archive,
[13:00.160 --> 13:12.880]  run through all 32 bits of possible internal state, and verify that every tenth byte gave me the byte I was expecting.
[13:12.880 --> 13:21.440]  So I could uniquely identify the internal state, could uniquely find these ten bytes.
[13:21.440 --> 13:24.980]  And so then I had some place to stand to mount the attack.
[13:24.980 --> 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.
[13:34.460 --> 13:37.140]  I only needed 40 bits.
[13:37.140 --> 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.
[13:48.560 --> 13:51.900]  I only needed to know the XOR of this byte with that one.
[13:51.900 --> 13:53.680]  So that's an 8-bit guess.
[13:53.680 --> 13:59.680]  I know the value from rand that's going in, so I can predict this thing.
[14:02.080 --> 14:05.080]  Here I'm multiplying by this constant.
[14:06.840 --> 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.
[14:17.960 --> 14:21.820]  So I've distributed this multiplication across the addition we had earlier.
[14:21.820 --> 14:24.040]  So here is the high byte of that.
[14:26.860 --> 14:31.500]  And when I add 1, it might cause a carry bit, so I have to guess a carry bit.
[14:31.640 --> 14:33.540]  Then it comes in here.
[14:34.880 --> 14:37.580]  I know what the high byte of this is.
[14:38.280 --> 14:42.140]  I feed it in. I just need to know these values.
[14:42.140 --> 14:51.300]  And given the stream byte, I can then figure out what the low 6 bits are here that are needed.
[14:51.820 --> 14:59.540]  This is how to figure out, given a stream byte, well, a plain text and a cipher text pair.
[14:59.540 --> 15:07.040]  These are the bits that you have to guess in order to get this stream byte.
[15:07.040 --> 15:22.460]  So what I would do is I would guess 40 bits, which would allow me to process this byte here.
[15:22.760 --> 15:29.920]  And so then I could check for each of the five files, does this value match what I expect it to?
[15:29.920 --> 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.
[15:42.160 --> 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.
[15:51.760 --> 15:58.740]  Usually, once I found this 40-bit one, the next one I could get within a few minutes.
[15:58.740 --> 16:09.780]  The whole attack ran in about two hours on a Pentium at the time, cipher text only attack.
[16:09.780 --> 16:17.820]  I was able to break into these zip files. We caught several child pornographers that way.
[16:18.900 --> 16:20.960]  And I got a paper out of it.
[16:20.960 --> 16:36.380]  So in 2001, fast software encryption, I got this paper and that led 20 years later to a surprising message.
[16:36.380 --> 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.
[16:49.200 --> 16:54.300]  Is there anything you can do to help? Can you tell me how things are looking these days?
[16:54.300 --> 17:02.880]  And so I looked it over, turns out he only had two files in the archive.
[17:02.880 --> 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.
[17:17.100 --> 17:23.080]  So far more guesses would pass each filtering stage.
[17:23.080 --> 17:31.740]  And it worked out to be something like, on my back of the envelope calculations, something like 2 to the 70.
[17:31.740 --> 17:38.020]  So I told him, you know, compare the work done this year to find hash collisions in SHA-1.
[17:38.160 --> 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.
[17:45.080 --> 17:52.200]  That cost around $100,000. This is not something that you can use off-the-shelf software for.
[17:52.620 --> 17:57.440]  And then he blew my mind and said, I could spend so much on this archive.
[17:58.200 --> 18:05.700]  At that point I knew that he probably had several hundred thousand dollars of Bitcoin in this thing.
[18:07.260 --> 18:11.080]  At this point I started doing a more careful analysis.
[18:11.080 --> 18:16.280]  There are 96 bits of key material that need to be guessed in various stages.
[18:16.440 --> 18:19.540]  But I can't guess the bits of key material directly.
[18:19.540 --> 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.
[18:30.260 --> 18:37.120]  This first part is CRC32 of the initial key 0 value with the 0 byte.
[18:37.120 --> 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.
[18:49.920 --> 18:52.920]  With key 1 it's a little more complicated.
[18:52.920 --> 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.
[19:02.780 --> 19:06.440]  And I'm guessing the high byte of that value.
[19:06.440 --> 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.
[19:16.760 --> 19:20.560]  The initial value of key 2 I can guess directly.
[19:21.440 --> 19:28.840]  So in the first stage I guess these 5 bytes, that's 40 bits, and I guess 4 carry bits.
[19:28.840 --> 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.
[19:52.460 --> 20:03.700]  So I have to guess these carry bits. 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.
[20:03.740 --> 20:09.160]  So 2 passes of encryption, 2 files, makes 4 carry bits that need to be guessed.
[20:09.160 --> 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.
[20:20.800 --> 20:28.720]  In stage 2 I guess these 3 bytes, that's 24 bits, 4 more carry bits makes 28.
[20:28.900 --> 20:38.960]  Added to the previous 2 to the 28th key guesses, I have 2 to the 56th keys to filter. And after filtering, 2 to the 40th remain.
[20:39.900 --> 20:54.200]  In stage 3 I guess 16 bits plus 4 carry bits makes 20. Previous 40 carried forward gives us 2 to the 60th keys to test. And after filtering, 2 to the 44th pass the third stage.
[20:55.740 --> 21:09.700]  In the fourth stage, I guess 16, as before, 4 carry bits gives us 20. 44 from the previous stage, 20 now makes 64. This was the most complicated stage, 2 to the 64th.
[21:09.760 --> 21:12.440]  After filtering, 2 to the 48th remain.
[21:12.440 --> 21:31.420]  Now in my original attack, this is where I would stop. I have all the key material. With these 4 bytes, I can brute force key 1, run through the 2 to the 32 possibilities, and get the value itself. I can invert this and that would work.
[21:31.420 --> 21:49.560]  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. There is no way we could do a 2 to the 80th attack.
[21:49.560 --> 22:01.950]  So I had to come up with a special approach, a new idea to make this step much less expensive.
[22:03.000 --> 22:10.740]  I remembered having read somewhere about an attack on truncated linear congruential generators that uses lattice reduction.
[22:10.740 --> 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.
[22:25.820 --> 22:30.540]  Where nicer means that the vectors are shorter and closer to orthogonal.
[22:30.540 --> 22:38.640]  So here I have a two-dimensional lattice. Here's a basis for that lattice, where one of these goes here and another goes there.
[22:38.640 --> 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.
[22:48.000 --> 22:53.680]  But lattice reduction gives you a much nicer basis. These are both shorter and closer to orthogonal.
[22:56.340 --> 23:09.880]  Lattice reduction is in general a hard problem. About half of the candidates for the post-quantum cryptography ciphers that NIST is considering right now use lattice reduction, for example, NTRU.
[23:09.880 --> 23:17.780]  But in small cases, it's tractable. And I had a very small case, only four or five dimensional.
[23:17.780 --> 23:25.160]  So I went and poked around on the cryptography stack exchange and found exactly what I needed.
[23:25.640 --> 23:35.200]  The vectors, in this case, the basis vectors were powers of the constant from the truncated linear congruential generator.
[23:35.200 --> 23:40.880]  In our case, it was 08088405 in hex.
[23:42.580 --> 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.
[23:52.720 --> 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.
[23:59.420 --> 24:11.200]  So the idea was that given the four most significant bytes of the key one value times this consecutive powers of C,
[24:11.200 --> 24:22.100]  I would do a linear transformation, get a value that was close to a basis vector in this small vector basis,
[24:22.100 --> 24:27.880]  then round off to get it exactly to a basis vector and then transform back.
[24:27.880 --> 24:33.160]  That would give me the exact value of key one zero.
[24:33.340 --> 24:38.520]  So I wrote up a Sage program to figure out how exactly that would work.
[24:39.320 --> 24:45.000]  Sage is a library for Python that lets you do linear algebra, among many other things.
[24:46.160 --> 24:49.860]  So here we have the modulus, two to the 32.
[24:50.120 --> 24:54.060]  We have the constant from the truncated linear congruential generator.
[24:54.720 --> 25:00.040]  We have the matrix that defines the basis for our four dimensional vector space.
[25:00.400 --> 25:10.300]  Now the vectors themselves are the modulus and the powers of the constant with minus ones on the diagonal.
[25:10.580 --> 25:13.260]  This does the lattice reduction step.
[25:13.260 --> 25:20.180]  Now to test how B worked, I would generate a random initial k1 value,
[25:20.180 --> 25:32.120]  then compute the actual powers of C times k1, modulo m, that I was going to try to recover.
[25:32.120 --> 25:33.600]  So I'd print these out.
[25:34.100 --> 25:37.120]  The most significant bytes were the things that I had guessed.
[25:37.120 --> 25:41.040]  I wanted to recover k's from the MSBs.
[25:41.040 --> 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.
[25:50.700 --> 25:55.700]  So this is the secret 24 bit values that I need to guess.
[25:55.920 --> 26:01.520]  Given the vector that is the most significant bytes, I multiplied it by B,
[26:01.520 --> 26:06.360]  which switched from one lattice to the other, did a basis change.
[26:06.360 --> 26:14.380]  Then I rounded to the nearest vector in this nicer basis.
[26:14.520 --> 26:23.800]  And that meant that I would get an actual value of k10 that would produce those same most significant bytes.
[26:24.380 --> 26:30.200]  Then I reversed that, transformed back, and got the guess.
[26:30.200 --> 26:31.960]  And I'd print it out.
[26:31.960 --> 26:35.520]  And when I started doing this, the guess was never right.
[26:36.360 --> 26:38.720]  Or rarely right.
[26:39.220 --> 26:45.180]  And that was because of the limited number of guesses I had here.
[26:47.900 --> 26:57.500]  If I could do one more stage, then I would be able to get the right answer every time.
[26:57.500 --> 27:04.600]  But here I had too few powers of C to find out what it was exactly.
[27:04.600 --> 27:09.890]  But then I started checking the difference between the guess and the actual value.
[27:10.540 --> 27:17.660]  So I take the keys, subtract off the MSBs, and the difference between the guess and the actual one
[27:22.250 --> 27:28.290]  turned out to fall into one of 36 possibilities every time.
[27:28.290 --> 27:32.630]  So as I thought about it, I realized that in this four dimensional space,
[27:32.630 --> 27:38.030]  by truncating it and just using the most significant bytes, I was adding a bunch of noise.
[27:38.350 --> 27:46.350]  And so the point in the four dimensional space I wanted was at the center of a cell.
[27:46.350 --> 27:55.710]  And what I was actually getting was a point near the hull of this cell that tiled this four dimensional space.
[27:55.710 --> 28:01.550]  And so because it was always within this cell,
[28:01.550 --> 28:07.550]  there were only a finite number of other possible lattice points that it could be.
[28:08.350 --> 28:15.090]  And so I computed for all of the two to the 32 possible K10 values,
[28:15.430 --> 28:23.750]  what the set of guesses were, and found that they fit into this one of 36 classes.
[28:23.750 --> 28:28.930]  And so instead of having to try out all two to the 32 possible key ones each time,
[28:28.930 --> 28:34.870]  I would only have to do 36. So instead of four billion, 36 values.
[28:34.870 --> 28:37.090]  And that made the attack feasible again.
[28:38.270 --> 28:43.770]  Once we'd guessed all the key material, we could filter the two to the 48 keys at stage four
[28:43.770 --> 28:47.190]  by using the remaining bytes in the encryption header.
[28:47.770 --> 28:54.770]  My business partner, Nash Foster, then started working on adapting my CPU based attack to run on GPUs.
[28:54.770 --> 28:58.350]  He wrote the code harness for getting code and data onto the GPUs,
[28:58.350 --> 29:02.310]  did all the CUDA stuff, advised me on how to structure the attack.
[29:02.730 --> 29:09.210]  We discovered very quickly, though, that getting the petabytes of possible keys onto the GPU would take too long,
[29:09.210 --> 29:13.210]  that the GPUs would just be sitting idle for most of the time we were paying for them,
[29:13.210 --> 29:16.210]  waiting for the data to arrive to process.
[29:16.210 --> 29:18.330]  So I went back to the drawing board.
[29:18.470 --> 29:22.290]  In each stage, I was guessing a whole bunch of bits and then filtering those results
[29:22.290 --> 29:26.110]  using the two bytes from the two archives in the file.
[29:26.350 --> 29:30.170]  I'd only keep about one out of 65,000.
[29:30.250 --> 29:34.030]  If I had some way of using that information to derive bits,
[29:34.030 --> 29:37.730]  rather than just guessing and checking, it'd save a lot of work,
[29:37.730 --> 29:39.930]  and more importantly, a lot of network traffic.
[29:40.090 --> 29:44.410]  The problem with that idea was that the math is too complicated.
[29:44.410 --> 29:48.250]  It involves mixing finite fields with integer rings,
[29:48.250 --> 29:50.990]  and those simply don't play well together.
[29:51.130 --> 29:54.290]  So I thought about some other cryptanalytic attacks I knew,
[29:54.290 --> 29:57.690]  and one that seemed promising was a meet-in-the-middle attack.
[29:58.330 --> 30:02.570]  A meet-in-the-middle attack usually applies to block ciphers,
[30:03.230 --> 30:07.850]  when it uses one part of the key material to do the first half of the encryption,
[30:07.850 --> 30:11.810]  and the second part of the key material to do the second half of the encryption.
[30:12.830 --> 30:22.170]  The reason we have triple DES instead of double DES is precisely because of this.
[30:22.170 --> 30:28.650]  Triple DES is a 112-bit cipher, even though there are three keys involved.
[30:29.690 --> 30:32.950]  You can do encrypt, and then decrypt, and then encrypt.
[30:32.950 --> 30:35.190]  So 112 bits of strength.
[30:35.190 --> 30:39.690]  If it's 112 bits, why not just do DES with one key,
[30:39.690 --> 30:42.290]  and then DES with another key, encrypting it twice?
[30:42.290 --> 30:44.210]  Well, the answer is right here.
[30:44.210 --> 30:49.070]  What you do is you take your plaintext-ciphertext pair,
[30:49.070 --> 30:54.910]  and then encrypt the plaintext under all 256 possible first DES keys.
[30:55.430 --> 31:01.390]  And then you take the ciphertext and decrypt it under all possible 256 DES keys.
[31:01.390 --> 31:06.510]  And right here in the middle, chances are that one of them will match.
[31:06.510 --> 31:11.210]  And so you sort all of these intermediate plaintexts,
[31:11.210 --> 31:18.190]  and whenever you find two intermediate texts that are the same,
[31:18.190 --> 31:22.090]  one of them came from the plaintext and one came from the ciphertext,
[31:22.090 --> 31:27.130]  and that uniquely identifies the key that should go between these two.
[31:27.130 --> 31:31.590]  So a meet-in-the-middle attack works when you've got key material
[31:31.590 --> 31:39.210]  that is not all used at every stage of the cipher.
[31:39.210 --> 31:42.190]  And in this stream cipher, that seemed to be the case, right?
[31:42.190 --> 31:47.150]  I had only key 0 at the beginning and only key 2 at the end,
[31:47.150 --> 31:50.630]  and it seemed like we could do something in the middle,
[31:52.230 --> 31:54.310]  but it wasn't quite right.
[31:54.310 --> 31:57.570]  But then I realized I could use the XOR of certain bytes
[31:57.570 --> 32:00.310]  in the middle of the cipher to mount the attack.
[32:01.470 --> 32:04.550]  Here's a diagram of the cipher again.
[32:04.550 --> 32:09.590]  And the cipher gets called four times in each stage for each byte,
[32:10.370 --> 32:15.630]  two for each file, the double encryption of the byte from rand.
[32:16.110 --> 32:19.590]  So in the center of the cipher,
[32:19.590 --> 32:23.870]  there are four different most significant bytes for key 1
[32:25.390 --> 32:28.030]  after each of these encryptions.
[32:28.090 --> 32:32.770]  So what I did was take the first of those four
[32:32.770 --> 32:35.670]  and exclusivore it with each of the other three
[32:35.670 --> 32:39.350]  to get a 24-bit key into a table.
[32:39.350 --> 32:43.690]  And under that key, I would store my guess for these bits.
[32:44.910 --> 32:49.370]  Then from the other side, given a stream byte,
[32:49.590 --> 32:53.990]  there are 64 possible 14-bit values here.
[32:53.990 --> 32:58.410]  So I would guess some intermediate stream bytes,
[32:58.410 --> 33:02.990]  six bits of this, I guess it's boxed here,
[33:02.990 --> 33:06.850]  these six bits to figure out what the other eight are.
[33:06.850 --> 33:10.130]  And that would allow me to derive linearly from this stuff
[33:10.130 --> 33:15.750]  what this most significant byte of key 1 was again.
[33:15.750 --> 33:19.930]  And so given these bits that I was guessing,
[33:19.930 --> 33:25.190]  I would derive a key and store these bits under that key.
[33:25.230 --> 33:28.090]  And then anytime I had a collision,
[33:28.090 --> 33:35.410]  I would know that the set of bits here that I guessed
[33:35.410 --> 33:39.730]  were consistent with the set of bits here that I guessed
[33:39.730 --> 33:45.130]  to give this plaintext going to that stream byte.
[33:46.330 --> 33:53.750]  Now that is far smaller than running through
[33:53.750 --> 33:56.340]  all of the possibilities and then filtering.
[33:57.010 --> 34:03.590]  The amount of memory it required was on the order of a few megabytes.
[34:03.590 --> 34:06.430]  So here is the code itself.
[34:06.730 --> 34:10.990]  This is stage 1a moving forward through the cipher.
[34:10.990 --> 34:14.750]  We guess the initial stream byte,
[34:14.750 --> 34:17.430]  because it was XORed with itself twice,
[34:17.430 --> 34:20.470]  we have no information about it, so we would guess that one.
[34:20.470 --> 34:25.250]  Then we'd guess chunk 2, which came from CRC 32 of key 0.
[34:25.250 --> 34:29.150]  Chunk 3 is the most significant byte of key 1.
[34:30.210 --> 34:33.390]  Here are the carry bits.
[34:33.570 --> 34:36.770]  There are two bits for each of the two files,
[34:36.770 --> 34:40.850]  so 2 to the 4th is 16 possible carry bits.
[34:43.790 --> 34:50.050]  This is debugging code for checking against files that we created ourselves.
[34:51.410 --> 34:54.270]  This is the first half of the cipher,
[34:54.270 --> 35:02.450]  and it updates an upper and a lower bound on the possible low 24 bits of key 1,
[35:02.450 --> 35:06.850]  so that if it ever goes out of bounds, we can throw it away.
[35:08.610 --> 35:13.850]  We compute various bytes, get through here.
[35:13.850 --> 35:17.450]  If it has passed all of these upper and lower bound checks,
[35:17.450 --> 35:22.370]  then this converts those four most significant bytes to a map key
[35:22.370 --> 35:29.270]  and stores the candidate under that map key.
[35:29.830 --> 35:31.470]  In the second half,
[35:32.290 --> 35:39.970]  we're guessing the stream1x byte for file 0.
[35:40.290 --> 35:43.230]  We're guessing the 64-bit prefix,
[35:43.230 --> 35:51.710]  because each stream byte has 64 possible pre-images under the pseudo-squaring operation.
[35:52.270 --> 35:55.390]  So these are all of the indexed pre-images,
[35:55.390 --> 35:59.530]  and this gets the specific pre-image that we're caring about.
[36:00.090 --> 36:04.070]  There's more debugging information. Again, we do the second half step.
[36:04.070 --> 36:11.990]  And if there are no consistent results, then we just go to the next guess.
[36:12.010 --> 36:17.190]  Here we're guessing the stream1x pass for file 1.
[36:17.630 --> 36:19.870]  We do that second half step.
[36:19.870 --> 36:23.990]  And again, if there are no consistent ones, we go back to the next guess.
[36:24.830 --> 36:31.310]  Finally, we compute the stream1y bytes.
[36:33.010 --> 36:37.950]  And if there are no consistent ones with that prefix, we continue.
[36:37.950 --> 36:44.310]  So now given each of the possibilities for the first and second and third bytes,
[36:44.310 --> 36:46.990]  we put them together into a map key,
[36:49.130 --> 36:52.370]  and then meet in the middle.
[36:54.020 --> 36:57.320]  Here is the CRC20.
[36:58.480 --> 37:03.900]  If you'd like to look at the code, you can see how these exclusive work together,
[37:03.900 --> 37:05.860]  and we can derive some certain things.
[37:05.860 --> 37:15.240]  So starting at the bottom, we derive bits 15 to 2 of K and L from 15 to 2 of S and T,
[37:15.240 --> 37:19.180]  and these bytes OP that we've computed.
[37:19.180 --> 37:28.130]  So in the center, we find those groups that...
[37:29.130 --> 37:31.430]  those guesses that work,
[37:32.130 --> 37:38.410]  and we push back that guess whenever the two match up with each other.
[37:38.410 --> 37:40.290]  And here's some more debugging information.
[37:40.650 --> 37:44.650]  So that's the idea of the differential meet in the middle attack,
[37:44.650 --> 37:47.450]  is computing forwards and backwards,
[37:47.450 --> 37:50.850]  exclusive oring one of the bytes with the other three,
[37:50.850 --> 37:54.490]  and then whenever the two guesses match,
[37:55.090 --> 38:00.650]  we have a set of candidates that's a product of the set from the first half of the attack
[38:01.250 --> 38:03.790]  with the set from the second half of the attack.
[38:03.790 --> 38:07.930]  Using the differential meet in the middle attack on stage 1 and stage 2
[38:08.310 --> 38:13.170]  allowed us to reduce the complexity of the attack in stage 1 from 2 to the 40th
[38:13.170 --> 38:15.030]  down to 2 to the 22nd.
[38:15.030 --> 38:18.730]  That's from trillions down to mere millions.
[38:18.730 --> 38:24.290]  And then in stage 2 from 2 to the 56th down to 2 to the 40th.
[38:24.290 --> 38:31.210]  And that let us run stages 1 and 2 on each of the machines that had GPUs attached to it.
[38:31.210 --> 38:36.650]  We completely eliminated the need to ship batches of keys over the network.
[38:36.650 --> 38:39.110]  And so we could generate the keys in place
[38:39.110 --> 38:45.110]  and then run what we called the GPU stage 3 kernel that did all the rest of the attack.
[38:45.550 --> 38:47.750]  Now we ran it for 10 days.
[38:48.310 --> 38:53.630]  We had tried it on all of our test archives that we'd created.
[38:53.630 --> 38:54.910]  It worked fine.
[38:56.190 --> 39:00.870]  10 days passed and it didn't find a key.
[39:00.870 --> 39:03.010]  We were distraught, pulling our hair out.
[39:03.010 --> 39:04.230]  What have we done wrong?
[39:04.230 --> 39:10.690]  We went back and discovered that there were a few other process IDs that could have worked.
[39:10.990 --> 39:14.930]  And we were wondering, oh no, are we going to have to do this four more times?
[39:16.290 --> 39:20.890]  But then our client, who was a programmer himself,
[39:20.890 --> 39:29.830]  discovered that there was a bug between the GPU stage and the CPU stage.
[39:29.830 --> 39:33.470]  So when I had run the tests, I had done it locally on my computer
[39:34.810 --> 39:37.250]  using the CPU version.
[39:37.270 --> 39:40.390]  And the test, we knew exactly where the key had to be,
[39:40.390 --> 39:45.010]  so it was a very small piece of key space that we had to check.
[39:45.310 --> 39:50.910]  But when my client went back and tried it again using the GPU stage 3,
[39:50.910 --> 39:57.010]  he discovered that when the key candidate was the first one in a list,
[39:57.010 --> 40:00.810]  it succeeded, but when it was the second one, it failed.
[40:01.250 --> 40:04.210]  And that led me to this line right here.
[40:04.230 --> 40:08.810]  We had swapped the thread index with the block index.
[40:08.810 --> 40:15.110]  So instead of incrementing by one into the current block,
[40:15.110 --> 40:20.550]  it would increment the block number and go off into space that was uninitialized,
[40:20.550 --> 40:22.420]  and so it would never work.
[40:23.010 --> 40:26.910]  So by switching the block index with the thread index,
[40:26.910 --> 40:28.910]  we started the search over again.
[40:28.910 --> 40:32.010]  Within a day and a half, we had found the three keys
[40:32.010 --> 40:35.250]  that decrypted the archive,
[40:35.250 --> 40:40.230]  and our client was able to get his Bitcoin keys out.
[40:41.350 --> 40:45.010]  In the end, the improvements that I made to my old attack
[40:45.910 --> 40:50.310]  took it from something that we estimated at approximately $100,000
[40:51.610 --> 40:54.090]  and a year of processing,
[40:54.090 --> 40:58.470]  down to something that took about $10,000 of GPU time
[40:58.910 --> 41:00.990]  and a little under two weeks.
[41:01.710 --> 41:05.370]  Our client was very pleased and gave us a big bonus,
[41:05.370 --> 41:08.110]  and that's how we recovered his Bitcoin core.
[41:08.230 --> 41:09.250]  Thank you very much.