00:00:00.292-->00:00:04.917 >>My name is Elie Bursztein and today uh we’re going to talk about SHA-1. Uh it has been a 00:00:04.917-->00:00:10.875 joint collaboration with many people. Uh, the 4 the 5 people who were uh helping were Marc 00:00:10.875-->00:00:15.958 Stevens from CWI, Pierre Karpman from INRIA, Ange Albertini, Yarik Markov and Alex 00:00:15.958-->00:00:20.917 Petit-Bianco who are also from my team. And today I’m going to tell you about how we created 00:00:20.917-->00:00:25.167 this uh SHA-1 collision. Uh before that I will tell you a little bit about the story about 00:00:25.167-->00:00:29.125 how you do cryptographic and break hash function. And then we’ll talk about what happens in 00:00:29.125-->00:00:33.875 the post-collision world. Um we had a little bit of problem with the calibration of the video 00:00:33.875-->00:00:38.000 projector so I tried to shrink down a little bit a slide. Everyone can see them correctly? 00:00:38.000-->00:00:45.000 Yes? [off-mic comment] Alright. Awesome. So let’s get started. Um, uh to make sure everyone is 00:00:45.000-->00:00:51.167 on the same page uh let me briefly recap what the hash function is. A hash functions or 00:00:51.167-->00:00:56.125 cryptographic hash function has 2 unique property. The first thing is when you have 2 files 00:00:56.125-->00:01:02.250 uh when, if they are different is to hash to a different digest or short hashes. So basically a 00:01:02.250-->00:01:07.250 short hash is, is a thick strings uh which compress your arbitrary lang long file into 00:01:09.292-->00:01:14.708 this uh unifi- unique identifier and people use that as a unique identifier for files. The other 00:01:14.708-->00:01:20.583 thing that is obvious, obvi- for many of you is uh that the hash function is one way. You can has 00:01:20.583-->00:01:25.417 a thing but you cannot go back. And you cannot learn anything from the file by just looking at 00:01:25.417-->00:01:30.792 the hash. Those are 2 main property of a hash function and a lot of people depend on it. 00:01:30.792-->00:01:36.917 For example, a hash function I use uh involving document and s- software signing, uh you can use 00:01:36.917-->00:01:42.000 them for example for Windows update, Firefox update, and Safari uh if are using I used to 00:01:42.000-->00:01:47.417 make sure we can verify the signature. They are also used in the same way for HTTPS 00:01:47.417-->00:01:53.000 certificate. Uh they are involving to helping ensuring that the SSL certificate are 00:01:53.000-->00:01:58.833 signed by a senior authority and are therefore valid. Uh I use inversion control and you will 00:01:58.833-->00:02:05.458 see that they usually never talk and finally uh they also use uh backup integrity to check which 00:02:05.458-->00:02:09.625 file has been backup and if file has been back up correctly. Uh they’re also using a slew of 00:02:09.625-->00:02:15.167 other software uh including databases some 5 system and some 4. And this is a huge and 00:02:15.167-->00:02:19.917 variety of software which make it very hard to understand uh all the consequences of what 00:02:19.917-->00:02:24.542 happen when you use a collision. I’ll give you an example later in the talk about unforeseen 00:02:24.542-->00:02:29.875 consequences when you try to play with collision. So what we’re going to talk about today. 00:02:29.875-->00:02:34.083 We’re going to talk about 3 things. First as I said we’re going to look at how we going to 00:02:34.083-->00:02:38.542 attack hash function, then we’re going to discuss how we found the hash func- or the collision, 00:02:38.542-->00:02:43.583 what happened and what not. And finally, we’ll discuss uh post-collision world. And more 00:02:43.583-->00:02:48.625 specifically uh how you deal with legacy software with using SHA-1 and how you do, what does 00:02:48.625-->00:02:54.208 the future hold for hash function, what we’re going to. So, before getting started uh 00:02:54.208-->00:02:59.792 the one thing, it’s very important to mention is, uh SHA-1 collision is just a final 00:02:59.792-->00:03:04.875 straw, very, very long line of research and we are standing on shoulder of giant. Uh among all 00:03:04.875-->00:03:09.583 the people who contributed and there is a lot of people who did over the last 15 years uh 2 00:03:09.583-->00:03:14.583 stand as giant and they are not me. Uh they are uh Wong who what the first one who in 2005 came 00:03:16.708-->00:03:22.083 up with a term called way to attack both MD5 and SHA-1. She’s the one who divided the metal 00:03:22.083-->00:03:27.167 that has been refined and finally lead to collision. The second one is my coder, um Marc 00:03:27.167-->00:03:31.917 Steven who for the ne- the last 10 years actually was the one who kept going at it and despite 00:03:31.917-->00:03:37.875 other people dropping out, uh decided to hold uh strong and basically carry out uh all the 00:03:37.875-->00:03:42.417 work ‘til the end. So, they are the 2 that deserve most of the credit for the work. Uh I was 00:03:42.417-->00:03:48.500 just lucky to be there and be h- uh be able to give them a helpful hand. Um, actually a 00:03:48.500-->00:03:54.708 funny anecdote, uh that was my second item, that SHA-1. Uh when it was time for it, back in 00:03:54.708-->00:03:59.958 2009, 2010 u hwe looked briefly at the idea of trying to have to break SHA-1 in which case we 00:03:59.958-->00:04:04.833 were like, no way, that’s way too complicated it’s too much resource sensitive, can’t do it 00:04:04.833-->00:04:09.250 and we give up. And I think a lot of people did give up as well. Because it’s imp- uh 00:04:09.250-->00:04:14.292 except to Marc an impossible task so I’m glad we were able as Google to help uh prove 00:04:14.292-->00:04:18.167 financial resources. Uh so if you take something from the talk is like, Marc Steven is the 00:04:18.167-->00:04:23.417 awesome guy and Wong was a genius behind uh the security attack who get all started. So 00:04:23.417-->00:04:28.667 uh attacking hash function, um there are quite a bit of confusion about what other 00:04:28.667-->00:04:32.167 defend type of attack are. So I’m going to sum them up. Uh but before that a quick show of 00:04:32.167-->00:04:37.792 hand, how many of you know what a collision attack is? Quite a few, okay, okay. Uh how many of 00:04:37.792-->00:04:43.250 you know how, what is a pre-measure attack. Way, less way more, less people right 00:04:43.250-->00:04:48.583 okay. How about a second preimage attack? Okay, so to make sure we all on the same 00:04:48.583-->00:04:52.375 page we’re going to briefly recap and see a bunch of diagrams where it’s going to be 00:04:52.375-->00:04:57.875 very quick. Uh so collision attack is the topic of today is basically a, see a hack have to 00:04:57.875-->00:05:03.417 files control and the goal is you create 2 files who hash to the same thing. So basically, 00:05:03.417-->00:05:07.708 you are violating a license your only principle is that 2 files should hash to another hash 00:05:07.708-->00:05:11.708 function. That is a collision attack. We have also another type of attack which is called 00:05:11.708-->00:05:17.750 preimage attack. In that case uh, the at- there is an unknown file and you know the hash and 00:05:17.750-->00:05:22.917 the goal of an attack is to be able to engineer a second file which would hash to the same 00:05:22.917-->00:05:28.250 thing. So second preimage attack which is the one what is confusing most people is where 00:05:28.250-->00:05:33.167 you know a file, let’s say SSL certificate and as an attacker you create a file which is 00:05:33.167-->00:05:39.292 doubling anger in the sense that it actually has the same hash. So far so good? Yes. Awesome. 00:05:39.292-->00:05:43.542 Okay, so how to create a collision attack. The, the one where basically we have a lot of 00:05:43.542-->00:05:48.792 practical results uh preimage, second preimage don’t have uh practical attack. Uh for the 00:05:48.792-->00:05:55.250 main hash function sh- SHA-1 and also MD5 and of course a newer one like SHA-256. So we’re going 00:05:55.250-->00:06:00.250 to focus on the collision attack uh which we can do in practice. So, collision attack are not 00:06:02.417-->00:06:05.833 bruteforce attack. The first thing, which is important to understand, you can not brute 00:06:05.833-->00:06:11.583 force your way out of creating a collision. Uh it’s impractical. Even if you were to use GPU and 00:06:11.583-->00:06:16.750 even if you were to use a tone of GPU you can’t to give you an idea we think it’s about 12 00:06:16.750-->00:06:22.500 million years of computation with a GPU to get to a collision, not going to happen. 00:06:22.500-->00:06:26.542 So, if you can’t do that what, what are you going to do. You are going to use something which 00:06:26.542-->00:06:32.333 is called cryptanalysis. And the idea of cryptanalysis is we are studying how the function uh 00:06:32.333-->00:06:37.958 diffuses a bit and how it scrambles them in a way to find biases we can exploit to reduce 00:06:37.958-->00:06:42.583 the size of the competition to point where we can finally do it. So, I’m going to give you a 00:06:42.583-->00:06:47.042 primer on cryptanalysis. I’m going to skip a ton of detail. Uh it’s just for you to get an 00:06:47.042-->00:06:52.042 idea, if you want more detail uh research paper. Not me. [laughter] Alright, so here is a 00:06:54.625-->00:06:59.625 view of, I’m missing a slide here. Uh okay, okay we missing a slide, that’s fine. Okay. So 00:07:02.667-->00:07:09.208 here is the other version of the SHA-1 uh compressed function. Uh so the SHA-1 compressed function 00:07:09.208-->00:07:12.500 is not the one you’re going to find on Wikipedia. If you go to the Wikipedia page you get the 00:07:12.500-->00:07:17.208 more simpler function. So reason why we use this for presentation is because when we do 00:07:17.208-->00:07:21.833 cryptanalysis we need to understand very precisely each of the step of the function. 00:07:21.833-->00:07:26.583 This is what happen when you have a block. So you chop up your uh filing to small block 00:07:26.583-->00:07:30.417 and you hash them and then you pass it to the next one, to the next. Make something called a 00:07:30.417-->00:07:34.542 dam- uh damgard merkle construction. So basically, this is a function who do the 00:07:34.542-->00:07:39.125 crumbling. Alright then we study these 80 steps long and you see them on the screen. Our case a 00:07:39.125-->00:07:43.625 presentation of them and we do study how the bead flows through the sink and the thing which 00:07:43.625-->00:07:50.208 provides the crumbling are the little uh p- purple box uh like F is a non-linear function, plus 00:07:50.208-->00:07:55.208 is a studied to be modular um, operation and so forth. So, how cryptanalysis works. Um the idea 00:07:58.083-->00:08:03.042 is we are studying message differential paths so the idea is we try to understand for a 00:08:03.042-->00:08:08.375 group of messages uh wh- how the beats are moving and how they are being uh swapped around a, 00:08:08.375-->00:08:12.875 or flipped and so forth. And that’s the red dots you see on the screen. So when we have this 00:08:12.875-->00:08:18.250 understanding they give right to what we call a uh equation system and for SHA-1 we know 00:08:18.250-->00:08:23.583 exactly what happened for the first 16 step. Remember there’s 80 of those so for the first 16 00:08:23.583-->00:08:28.000 it’s basically solved and we understand what happened. So we can understand how to reduce the 00:08:28.000-->00:08:33.500 computation. Now we have reduced the computation uh by 16 step. Then uh we used a bunch of 00:08:33.500-->00:08:38.333 tricks uh including boomerang, neutral beat and so forth which is basically try to get to 00:08:38.333-->00:08:43.083 counteract the, the chaos in the atrophy creeping up me up uh to the point to pushing the 00:08:43.083-->00:08:48.083 computation to a smaller part by another 8, uh 8 steps which is up to step 24. And then well we 00:08:51.208-->00:08:55.792 don’t know. And the other part for you is this huge competition that’s in Tucson at least where 00:08:55.792-->00:09:00.750 there’s a part from 24 to 80 where we’re kind of, we cannot really understand what happened 00:09:00.750-->00:09:04.292 and it’s too big to say the expression is too large, so we cannot, that’s where we use a 00:09:04.292-->00:09:08.958 GPU to actually compute all the possibility. Or a huge fraction for those because we cannot 00:09:08.958-->00:09:15.500 understand what happened there. So, wh- how you create a collision. Well we use the idea 00:09:15.500-->00:09:20.083 from Wong which is the idea of using 2 collision, 2 blocks. So, you have a ba- a bunch of the 00:09:20.083-->00:09:24.375 beginning of the file which we call the prefix and this is whatever you want and then we 00:09:24.375-->00:09:28.958 have a first block which we pull a near collision. So, what is a near collision? A near collision 00:09:28.958-->00:09:34.167 is 2 blocks which basically are very close to each other uh for the definition of uh closeness, 00:09:34.167-->00:09:37.917 basically imagine that those 2 are good candidates and they are different but the are 00:09:37.917-->00:09:43.875 sufficiently close that we have a good uh, guess or we have a good uh belief that they are 00:09:43.875-->00:09:47.458 going to be resolved with a second block. So basically we take the compute of those 2 00:09:47.458-->00:09:51.917 blocks and then we have the bl- the second block who basically cancel out the, those 2 00:09:51.917-->00:09:57.042 collision. The collision and then wind up with the same output. So at that point the 00:09:57.042-->00:10:00.875 left and the right will have exactly the same output and after that you can put whatever 00:10:00.875-->00:10:06.000 you want after that. Um because the collision has been resolved. That is the basic idea of a 00:10:06.000-->00:10:11.750 collision and the technology part is we use 2 block. All you have to really remember is we 00:10:11.750-->00:10:15.583 have a prefix which is basically something you have to choose in event and then you have the near 00:10:15.583-->00:10:20.167 collision, collision and then after that it’s all the same. From a perspective, it’s all the 00:10:20.167-->00:10:24.542 same because there is no dependency in how you conv- create the has function to the 00:10:24.542-->00:10:29.250 past. So at that point it’s identical and you can put whatever you want for the uh 00:10:29.250-->00:10:35.250 suffix. So, okay, so, I described this one, this further one before don’t, don’t know, 00:10:35.250-->00:10:40.625 I’m not sure what happened. So how do you exploit collision? So exploiting collision uh the one 00:10:40.625-->00:10:45.917 we do for SHA-1 is what we call the fixed prefix attack which means uh we had to create a 00:10:45.917-->00:10:51.667 prefix, so choose a green box uh before we doing the computation because we can’t change it 00:10:51.667-->00:10:56.458 afterward because it fit into the collision so we selected the prefix and you have to select it 00:10:56.458-->00:11:00.917 in the first mark way and then we have the collision blocks and after that what you can do what 00:11:00.917-->00:11:05.042 we call an arbitrary suffix which is, uh you can jam whatever you want before after 00:11:05.042-->00:11:09.167 that then you can create many many document which have a collision in it and we’ll show 00:11:09.167-->00:11:15.042 you how we can explore that in a minute. So, uh here’s how it works. So it doesn’t seem very 00:11:15.042-->00:11:19.958 powerful right? Because you have choose everything. Everything is pre-computed, uh that is true. 00:11:19.958-->00:11:25.667 But the prefix you choose would actually influence how much you can do. In our cases we used PDF 00:11:25.667-->00:11:32.292 and JPEG. You can think of all the stuff like EDS, um I like other type of file from which 00:11:32.292-->00:11:38.417 have flexibility, but PDF for us was the best one. And so the idea is we use a collision block 00:11:38.417-->00:11:44.333 to change the length of specific fields of SHA comment and that way what we d- what we display 00:11:44.333-->00:11:48.375 on the screen will be different from file 1 because it’s going to point to one part of the 00:11:48.375-->00:11:53.792 suffix and on the other file is going to point to another part of the suffix. And that way even 00:11:53.792-->00:11:59.292 though we have the same suffix we’re able to display different view of the word uh because the 00:11:59.292-->00:12:04.542 collision blocks themselves are used to control some of the display function. I show you a 00:12:04.542-->00:12:09.542 practical example uh later on in the talk. Alright, uh chosen-prefix attack. So that is 00:12:12.250-->00:12:18.250 the one we tried using MD5, this is for reference. MD5 is way more weaker, so in that specific 00:12:18.250-->00:12:22.042 case you don’t have to worry about choosing a specific prefix, you can use the one you 00:12:22.042-->00:12:26.250 want. And that gives you way more uh flexibility I’m going to use, show you a practical attack 00:12:26.250-->00:12:31.250 as far as using the MD5 attack just to illustrate the purpose. Alright, enough theory. Ah. No 00:12:33.833-->00:12:37.792 we’re going to go to the uh real world attack and I’m going to show you exactly how to use 00:12:37.792-->00:12:42.708 these things in practice and we’re going to start with MD5 because the one which happened 00:12:42.708-->00:12:49.375 about 8 years ago and so we have a lot of um hindsight to look at in the real attack to show you. 00:12:49.375-->00:12:53.250 SHA-1 is too new to have those kind of stuff. It gives you a sense of what you can do when 00:12:53.250-->00:12:58.250 you have those collision. So, in two thou-, the first attack which was created um, using the 00:13:02.708-->00:13:07.917 MD5 collision in practice was creating a rogue SSL certificate. You should able to 00:13:07.917-->00:13:12.000 manipulate the signature of a certificate, it turns out you can create a third si- uh 00:13:12.000-->00:13:15.667 signing certificate for everything you want which is valid then you can impersonate 00:13:15.667-->00:13:20.875 any worksite on the planet. This is what Marc did with Alex [indescribable] and a bunch of 00:13:20.875-->00:13:25.875 other people. Uh, back in 2009. And so the way it works is as follow. This is what necessary 00:13:28.125-->00:13:32.917 certificate look like, uh you have a bunch of field which hare serial number and validity 00:13:32.917-->00:13:38.833 period which are uh from the uh what should I give you, the register and then you have the 00:13:38.833-->00:13:43.167 real cert name. Which is basically which domain is your certificate signing for? And 00:13:43.167-->00:13:47.875 then below that you have something very important which is the X509 cert- extensions CA 00:13:47.875-->00:13:52.625 FALSE. What it means is your certificate cannot be used to singed other certificate because 00:13:52.625-->00:13:57.000 obviously you’re not a CA. So the whole goal when you create this, when you forget 00:13:57.000-->00:14:01.875 certificate is to swap those 2 fields. So how you do that with a collision, here’s how you do 00:14:01.875-->00:14:08.250 it. Uh first you obviously, you write uh the cert name to say where I want to be able to sign 00:14:08.250-->00:14:14.000 for everything. So I remove the real domain name and then put a start instead. Then I put my own 00:14:14.000-->00:14:19.833 public key obviously so I can actually do the creation. And then I say, well I’m a CA 00:14:19.833-->00:14:24.375 certificate right. And then after that you have to hide the read priv- the read public key 00:14:24.375-->00:14:26.375 and you do that by hiding it into what we call the uh netscape comment extension, so a 00:14:26.375-->00:14:28.375 lot of SSL certificate have a lot of field and one of them is the ability to jump comment in 00:14:28.375-->00:14:32.875 turn, you can use that as a new trick to hide the previous public key and you use this 00:14:32.875-->00:14:37.875 space to create a collision. Then you leave the signature. you copy pass it to your new, 00:14:45.875-->00:14:50.000 brand new uh fake certificate then you have a signing certificate. That’s basically 00:14:50.000-->00:14:55.000 how you create a, uh fake uh valid SSL certificate. Uh, if you think that there, that’s a 00:14:58.042-->00:15:03.042 uh academic attack, it’s not. It turns out that uh in 2012 um a malware was discovered which was 00:15:06.167-->00:15:12.250 mainly uh spying on an Iranian com- computer. Uh the malware was called Flame. I’m not sure 00:15:12.250-->00:15:17.000 you remember it. Uh this malware it was fairly unique in a sense that it was using a colliding 00:15:17.000-->00:15:23.875 certificate to push fake Windows update. What happened is someone learned from it uh decided to 00:15:23.875-->00:15:30.292 create a collision uh by uh stealing uh by lifting the signature of a Windows terminal 00:15:30.292-->00:15:34.583 server, which should not have and removing the restrictions. Those payload certificates were 00:15:34.583-->00:15:38.125 only used for compatibility and they had a bunch of restrictions so what they did is they choose 00:15:38.125-->00:15:43.750 a certificate, changes the name and then remove to say it’s only for Windows th- uh XP. They say, 00:15:43.750-->00:15:49.583 no, no it’s for everything. Repackaged it and used it to deliver uh malware as a form of 00:15:49.583-->00:15:55.083 Windows update which we’re saying is a certificate to attack Iranian computer. Um 00:15:55.083-->00:16:00.750 what’s very interesting about this attack is uh because he choose collision, uh we, Marc 00:16:00.750-->00:16:05.250 and uh his team was able to reverse engineer how this malware works and were able to 00:16:05.250-->00:16:11.000 figure out how the collision was created. And low and behold it didn’t choose any of the 00:16:11.000-->00:16:15.625 technique which were discussed in that Cadamier it was using a completely other technique which 00:16:15.625-->00:16:19.667 were using a 4 block collision. If you remember I told you a 2 block collision is the way we do 00:16:19.667-->00:16:24.542 it because it’s the most efficient so now the people who created the Flame uh fake 00:16:24.542-->00:16:29.333 certificate was not using 2 block, they were using 4 block which is less efficient. You can 00:16:29.333-->00:16:34.042 still do it and were using uh vector which were another one discussed in Cadamier. So 00:16:34.042-->00:16:39.750 someone in the world had enough cryptographic uh knowledge and enough uh resources to pull out 00:16:39.750-->00:16:45.583 this kind of attack uh which led a lot of people to uh, I put it as it was a state sponsor 00:16:45.583-->00:16:50.333 malware. Um and that’s the explanation behind this. If you want to know more about it there 00:16:50.333-->00:16:55.000 is a very, very neat paper by Marc which is called, uh Reverse-engineering cryp- of the 00:16:55.000-->00:16:58.958 Cryptanalytic Attack Used in the Flame Super Malware, which explains all of this in detail 00:16:58.958-->00:17:04.625 but that’s the bottom line. So, basically you can weaponize collision to create attack and 00:17:04.625-->00:17:09.625 it has been done in the past and that’s why taking collision seriously is so important. So, 00:17:11.792-->00:17:16.542 where do we live today? Well for the old function the old dead, uh MD4 is dead, for very, very 00:17:16.542-->00:17:22.292 long time. Uh MD5 is so dead that you can do it on your smartphone, no kidding you can 00:17:22.292-->00:17:26.333 literally create a collision in your smartphone. And then SHA- t- SHA-1 is a new attack we 00:17:26.333-->00:17:33.208 created and it took us 2 63 competition. Which is pushing the limit of what we can do. Uh 00:17:33.208-->00:17:38.875 it’s one of the largest competition, uh competition in the world as far as we know. So 00:17:38.875-->00:17:43.875 how do we, do we find this collision? Well, uh we started in 2015 and as I said the prefix 00:17:46.250-->00:17:52.000 has to be fixed for SHA-1 so we had to create a clever prefix. Ange Albertini uh was the one 00:17:52.000-->00:17:58.000 who uh look at this because it is uh very, very well known for how to do uh world expression to 00:17:58.000-->00:18:02.708 craft thing, interesting uh documents. And so he came up with the idea of using PDF and 00:18:02.708-->00:18:07.542 JPEG so we can actually have a prefix which give us malleability to show one measure 00:18:07.542-->00:18:12.750 or another and make it very, very easy. I’ll show you a demo in a minute. Uh and then, uh I 00:18:12.750-->00:18:18.542 ran the first competition um between 2015 and 2016, took me about 9 months and 300-->000 00:18:18.542-->00:18:23.542 computer. Then uh, excitement began. Uh wait for the result and then uh we have to develop a 00:18:27.833-->00:18:33.875 full attack and we have quite a few sweater, 0:18:31 as well. And finally uh we did the second 00:18:33.875-->00:18:38.875 clash computation in early 2017 and then we uh issued the release in the press um in 00:18:41.625-->00:18:46.625 February 2017. So, what Ange game up with to be able to use, to, the collision to full extent 00:18:49.375-->00:18:56.333 was to embed a JPEG into the PD- to a PDF header to created collision which will be like 00:18:56.333-->00:19:03.042 valid PDF document. And the trick is uh JPEG has something called a comment and the idea is 00:19:03.042-->00:19:09.750 you’ll use a collision as a boundary for the length of the comment, so both, both file 00:19:09.750-->00:19:14.208 while having the same hash will actually display different thing because 1 in 1 case uh the 00:19:14.208-->00:19:19.917 length will point to the first dimension the other case um by rebounding on comment of comment 00:19:19.917-->00:19:25.125 will rebound to another images. So while the comment of the 2 files is the same, if someone is 00:19:25.125-->00:19:29.958 to open it you will see 2 different images that the power of creating collision, of course 00:19:29.958-->00:19:35.542 we can use whichever images you like. So now you can create any pair of doppelganger uh files. 00:19:35.542-->00:19:40.792 So, try to imagine 2 insurance contracts, one say you only have to pay 1-->000 dollars and the 00:19:40.792-->00:19:44.583 other one say well no actually have to pay a hu- 1 million dollars and those would hash the 00:19:44.583-->00:19:49.583 same. It’s a kind of stuff you can do with that. So, then I took Marc’s code and tried to 00:19:53.125-->00:19:59.917 scale it up to uh I decide to use about 300-->000 core uh in multiple data center around the 00:19:59.917-->00:20:04.625 world. And most of the complexity was to find the right balance between the resilience 00:20:04.625-->00:20:09.625 and preferences so every time you have to dispatch a new job we have to copy stuff in memory, 00:20:09.625-->00:20:13.292 move thing between computer and so for us there is a lot of overhead so you want to run as 00:20:13.292-->00:20:18.500 long as possible at the same time, computer fail and we have to reboot a job or the job has 00:20:18.500-->00:20:23.208 been preempted and so forth. So we said they’re done after a few try and out, about 1 hour batch 00:20:23.208-->00:20:28.958 and we run well quite a few of those, like million of those. Uh and then, uh also we factor the 00:20:28.958-->00:20:33.000 code to be stateless. Uh one of the difficult thing when you do this dash competition is when 00:20:33.000-->00:20:37.625 you have a database where you have to put all the job. Instead of doing that uh we were making 00:20:37.625-->00:20:41.917 each job stateless so you can restart them and then uh we’re using basically a random 00:20:41.917-->00:20:45.750 generator to decide which SHA to use instead of having a synchronization because 00:20:45.750-->00:20:50.792 otherwise you have to deal with fade over and replication of the master and become uh even more, 00:20:50.792-->00:20:55.792 a bigger hell to, to manage. And last but not least, uh I make a huge mistake. Um, Map Produce 00:20:58.292-->00:21:02.875 is, a very famous computation firmware and the idea is you map your computation and you’re 00:21:02.875-->00:21:05.583 going to reduce to all the solution, I’m like that’s perfect that seems to be the 00:21:05.583-->00:21:11.458 great tool to do the job. So now it’s actually the wrong tool for the job because the map is very, 00:21:11.458-->00:21:15.833 very complex. You look for the entire space but reusing the part where you aggregate the 00:21:15.833-->00:21:20.625 solution is very small. Huh It’s only a few bytes. And so we were spending a lot of time waiting 00:21:20.625-->00:21:25.708 for the last part of the computation to finish, I was running batches of uh I think uh 00:21:25.708-->00:21:32.042 50-->000 job at a time. So 50-->000 hours by 50-->000 hours and so w- as you can see on the graph uh 00:21:32.042-->00:21:37.417 most half of the time of the job was used for basically waiting for the last bits to finish. So 00:21:37.417-->00:21:43.250 for the second computation part we actually moved away from this part in, to uh using a simple 00:21:43.250-->00:21:47.500 job system where we have it factor in a bunch of job and make them all independent which 00:21:47.500-->00:21:51.833 was way more efficient. So lesson learned, don’t choose Map Produce for the job. Um, we 00:21:51.833-->00:21:56.833 learned that the hard way. Then becomes the part where we, was the most scary. Uh we finish the 00:22:01.000-->00:22:06.750 first computation, uh some time in uh I believe January and then uh in the middle of the night 00:22:06.750-->00:22:11.417 um, my, my phone rang and then I know, we found the first collision. I send an email to 00:22:11.417-->00:22:16.417 Marc, I’m saying, hey we found it. Great. Okay and then he said to look at it. I’m like, can I 00:22:16.417-->00:22:21.167 get to it and we’ll get to it? And I’m like, wait, wait, wait looking at it and then uh turned 00:22:21.167-->00:22:27.417 out that at first glance what we found was not solvable. Which mean that we didn’t know how we, 00:22:27.417-->00:22:31.917 we built an equation system to find the second block but we couldn’t figure out what was the 00:22:31.917-->00:22:37.583 equation system had no solution. And then we were very, very scared for many for quite a bit 00:22:37.583-->00:22:42.750 of time that we couldn’t do it. But then Marc and Pierre uh figured out how to add extract 00:22:42.750-->00:22:47.250 condition and fix the solvability using that technique to actually make it work again. 00:22:47.250-->00:22:51.750 And then we were able to find more speed up to accelerate the computation and then were able 00:22:51.750-->00:22:56.750 to run the computation and then Yarik, uh from my time actually run the second set of 00:22:59.000-->00:23:04.000 computation uh through GPU. So GPU is very interesting, uh a lot of people say GPU is great 00:23:04.000-->00:23:10.042 for crypto. That’s true. Except the architecture is from a, very different from uh a CPU. So you 00:23:10.042-->00:23:15.875 have to rethink how you do things, in particular uh memory transfer is very expensive so we 00:23:15.875-->00:23:20.000 couldn’t do load, unload, load, unload and those kinds of stuff. You have to allocate memory, do 00:23:20.000-->00:23:25.208 your computation, allocate [inaudible]. So what we decide to do, and that’s Pierre’s idea 00:23:25.208-->00:23:32.000 is to use a feet forward, where we compute the base solution in CPU and then we move on to the 00:23:32.000-->00:23:37.333 first 2 steps between 14 and 26 and we compute the pot- ton of potential solution. Using GPU to 00:23:37.333-->00:23:41.958 compute all the next step and until we have regular statistics do one step and move one step, 00:23:41.958-->00:23:46.042 move one step, when we don’t have enough solution go back and back and forth. So reason why 00:23:46.042-->00:23:52.417 that work is because the first few steps you have very, very little solutions. This is a, uh 00:23:52.417-->00:23:58.417 graphing logarithm. Logarithmic scale right? So it mean that the first step you do maybe a 00:23:58.417-->00:24:04.000 100-->000 computation. The one in the middle you do, you have up to 100 trillion of solution. So, 00:24:04.000-->00:24:09.333 if, it quickly ramps up. So what we do is we were saturating the memory with as many potential 00:24:09.333-->00:24:13.750 next step. Do all them at once and if we don’t find a solution back track, generate more 00:24:13.750-->00:24:17.000 solution, move back and forth and so forth. So it’s a completely different way to 00:24:17.000-->00:24:22.875 approach cryptography. So while GPU is great for crypto it also require a lot new way of uh 00:24:22.875-->00:24:26.417 distributing uh, distributing your computation because you don’t have the same memory in 00:24:26.417-->00:24:31.417 general, memory manipulation as you have in CPU. Alright, and then uh we spend 110 years uh of 00:24:36.833-->00:24:42.833 GPU a far cry from the 12 million would have spent if using bruteforce, we succeeded. 00:24:42.833-->00:24:48.833 That being said, before we succeeded, uh we had a funny incident. I mean I didn’t find 00:24:48.833-->00:24:55.500 it funny at that time but now it’s okay. Uh, so Yarik finish a computation and uh from my team, 00:24:55.500-->00:24:59.167 and send an email to Marc, saying hey we found the collision and we are ready to c- 00:24:59.167-->00:25:02.625 celebrate, you know the champagne is there for swig, we’d like where we’re going to 00:25:02.625-->00:25:08.833 celebrate something awesome. And Marc say, doesn’t work. And we’re like, what? Doesn’t work. 00:25:08.833-->00:25:15.417 What you mean it doesn’t work? And like, doesn’t work. And it turns out uh because the way we 00:25:15.417-->00:25:22.125 did computation we had it done in big endian instead of little endian and it was looking at it 00:25:22.125-->00:25:27.125 the other way. [laughter] Yep. So, we fixed it. [laughter] It’s fine for like 1 exchange but and 00:25:37.000-->00:25:42.000 then for all fine. But I I’m telling you, we were wiped. Anyways, so. And then we were 00:25:47.625-->00:25:52.417 happy, we were able to create those uh, colliding PDF, uh you might have it, from them online. 00:25:52.417-->00:25:59.083 So basically, you have um the same shell, it’s the same SHA-1 and a different SHA-256 and as 00:25:59.083-->00:26:05.375 you see because we use a comment of comment trait uh 1 is blue the other 1 is red. Uh that the 00:26:05.375-->00:26:11.583 idea we had uh and then we were like okay we’re going to give the world 90 days before we 00:26:11.583-->00:26:16.167 release this, the, the code to create uh 2 PDF which are doppelganger. Well trust the 00:26:16.167-->00:26:20.792 internet to do it in 2 days. Uh so they have a better tools than ours so I hear they’re releasing 00:26:20.792-->00:26:27.042 it up on GitHub one so I’m using their tool, thank you for recreating it. I, and so 00:26:27.042-->00:26:31.667 basically that’s easy as it is. So we have 2 PDF which have different values, a cat and a 00:26:31.667-->00:26:36.875 tiger that, that’s what, what you do is you basically use a collider script and the collider 00:26:36.875-->00:26:41.792 script will automatically match both of them into one PDF and align the comments 1 point to 00:26:41.792-->00:26:48.208 another and that’s how fast it is. Literally really time and then you can see, boom you have 00:26:48.208-->00:26:53.208 2 PDF’s which have the same. [applause] Thank you. Okay, and then the uh you have the 00:26:56.583-->00:27:01.583 SHA-256. Alright, so here is the gig impression behind the scene. Uh you have the fixed port I 00:27:05.417-->00:27:10.417 promised you which says PDF, uh the PDF headers and then below it we have the JPEG start and 00:27:14.750-->00:27:19.750 you see and then following that we have the JPEG comment. And then at the border of the JPEG 00:27:22.375-->00:27:27.375 comment we have a collision block right? And you can see it here. Let me try to do this. Uh 00:27:27.375-->00:27:31.333 y- you see it hear right. You have the last bit of the, of the comment which is inside the 00:27:31.333-->00:27:38.250 collision block. So they will be different in both cases right? And so one of the comment is 1, 00:27:38.250-->00:27:43.250 73 the other one is 1, 7, F. So as a result uh you do create a disorganization and in one of 00:27:48.042-->00:27:54.208 the file the image start way lower and it’s, it’s a comment. In the other file well until we 00:27:54.208-->00:28:00.167 link it I say it’s a JPEG and then in other case it’s a real image. And that how it works 00:28:00.167-->00:28:03.667 right so a lot of people were confused when we should you that how we can do and create as many 00:28:03.667-->00:28:08.667 as we want. Try to explain that to the press. They’re like [laughter]. And then that’s what 00:28:10.875-->00:28:15.708 it is. Uh I want to also give a big prop to Hector Martin which is a guy who actually created 00:28:15.708-->00:28:20.292 the visualization. Again, had a create one and he do a way better one so I stole with his 00:28:20.292-->00:28:24.208 permission, uh his version because I think it’s a clearer version we have. So thank you 00:28:24.208-->00:28:30.000 for him to do that. Um, so post-collision world. So what happen when you create a 00:28:30.000-->00:28:36.042 collision? Uh first thing, uh and that the thing which actually was the goal, uh we 00:28:36.042-->00:28:42.750 release the collision uh a few days or I think even on the day of a meeting between brother 00:28:42.750-->00:28:48.750 which was a, which is a consortium to decide what is the future of web browser and there 00:28:48.750-->00:28:54.333 was, it was about to have discussion about um, prolongating the lifetime of 00:28:54.333-->00:28:58.708 SHA-1, except it was um su- was supposed to be some type but people were like, no, rom my 00:28:58.708-->00:29:02.375 understanding because some people have complained, but in the life of the attack, uh 00:29:02.375-->00:29:06.833 Firefox is finally give up and say fine, we are going to immediately ahead of schedule 00:29:06.833-->00:29:11.917 stop it which was exactly our intention. If we engage to do any such a long computation is 00:29:11.917-->00:29:16.000 not for the fun. Also it was very fun it was because we really wanted to push the world 00:29:16.000-->00:29:21.000 to stop using SHA-1 once and for all and as many, many of the cryptographic loom unless you 00:29:21.000-->00:29:26.875 really should monitor the people and the real attacks tend to uh, delay it for another year. Right 00:29:26.875-->00:29:31.042 ya know, out of sight out of mind so we decided to put it in front of you so you have to do 00:29:31.042-->00:29:36.250 it. And I think for us it was the most important thing, is we did break SHA-1 and as a result 00:29:36.250-->00:29:40.542 user will feel lot safer so that’s really the goal of the entire exercise and it was a 00:29:40.542-->00:29:46.583 well worth investment. Uh, Microsoft Office did the same in May. Uh so now all uh, I believe 00:29:46.583-->00:29:51.292 every browser have duplicated SHA-1 so now we have, we are in a better world, better place. 00:29:51.292-->00:29:56.292 Um, we got leaked. Someone put a bet that SHA-1 would be broken in 2017, literally an hour 00:30:00.917-->00:30:07.167 before we were about to release. I have no idea who it is but the guy made 80 coin and I want my 00:30:07.167-->00:30:12.167 share. [laughter] So, uh also I, I assume Marc, so the release was about 5, uh 5am PSC because 00:30:18.250-->00:30:24.750 he’s in Netherland and so I saw him a few hours before scrambling to try to get the uh 00:30:24.750-->00:30:30.083 bug bounty for the uh for bitcoin so there is this people who are giving out, a little bit 00:30:30.083-->00:30:35.667 of bitcoin money for the people who break SHA-1 to incentive to buy them, to do on, see him 00:30:35.667-->00:30:39.917 wrestling to get the data, and the money, but he did. So he died claim the bounty just in 00:30:39.917-->00:30:44.917 time so Marc got the bounty that’s fair. Uh hopefully nobody stole it from us. Uh, and then, 00:30:48.000-->00:30:54.667 I, I spoke about um, enforcing c-, uh enforcing uh situation right. And I think the, the most 00:30:54.667-->00:30:59.083 impressive one and uh uh completely take us aback was when you get- have problem and 00:30:59.083-->00:31:03.542 I’m going to talk about it in a minute, well we insert SVN because none of us use SVN for 00:31:03.542-->00:31:09.458 very long time so we learn some of it. But then a guy from WebKit was like, WebKit which is 00:31:09.458-->00:31:15.125 the uh web wanderer for Safari, uh one of them was like, oh we use SHA-1, uh let me make sure 00:31:15.125-->00:31:19.417 we don’t [indiscernible] for collision, which is a great idea. And so he pushes you to 00:31:19.417-->00:31:24.417 test to the SVN of WebKit and the WebKit SVN die. It’s not like you can revert, it just 00:31:27.292-->00:31:32.500 died. And for 8 hours you see all the WebKit engineer completely freaking out like, 00:31:32.500-->00:31:36.833 did you try this command? And we do this. And ultimately they were able to recover it but it 00:31:36.833-->00:31:42.500 literally destroys the entire SVN from working for 8 hours. And then a patch did it m-, did 00:31:42.500-->00:31:47.375 issue an SVN uh emergency patch and say, please do not test collision on this SVN we know 00:31:47.375-->00:31:52.458 it’s broken. Don’t do this. So that’s an unforeseen collis- uh c- that’s an unforeseen 00:31:52.458-->00:31:56.333 situation. If we had known we had given them advanced notice but we did not. We did not have 00:31:56.333-->00:32:00.708 the test vectors, we did not know it would break anything. But we broke uh GIT which means 00:32:00.708-->00:32:05.250 there are other software somewhere which are broken by uh by SHA-1 so you have to find a 00:32:05.250-->00:32:11.292 way to mitigate those and that going to be uh. So next part of the talk, which is what do you 00:32:11.292-->00:32:16.292 do when you think there is a SHA-1 software looming into your network? Right. What do you do? 00:32:19.167-->00:32:24.167 Well we have a great example. GIT. So, despite early warning and there was a long strand and 00:32:27.083-->00:32:32.167 I put the link there and they’re on the slide about people trying to warn the news to not use 00:32:32.167-->00:32:36.500 SHA-1. Like no, no that’s fine I’m going to use SHA-1. Don’t do it. No no I’m fine I’m going to 00:32:36.500-->00:32:41.167 do it. So at the end of the day GIT use SHA-1 and it’s making so many assumptions that it’s 00:32:41.167-->00:32:46.583 really hard for them to move away from Sha-1. There are they are moving away from it finally 00:32:46.583-->00:32:52.958 but it took a long, lot of discussion and it’s still not there. So now we have SHA, we 00:32:52.958-->00:32:59.958 have a very well used software. How many of you use GIT? Yeah. So, all of you use something 00:32:59.958-->00:33:04.833 which is enabled to put directly to SHA-1 collision where we can have 2 blocks which share the 00:33:04.833-->00:33:09.125 same collision and you end up with 2 uh 2 different view of the world for the same GIT 00:33:09.125-->00:33:15.250 repository. Not good right? So how do you mitigate that? Well, turned out we have a tool. And 00:33:15.250-->00:33:20.292 actually Marc invented this tool. Um, he, it’s for uh, he invented this tool and applied 00:33:20.292-->00:33:26.500 that I said to flame but it still work for SHA-1. The idea is to use counter cryptanalysis. 00:33:26.500-->00:33:31.375 It’s a very mouthful word but the idea is because the way you create collision uh create 00:33:31.375-->00:33:36.458 unique property into the file. Most likely there are tr- trivial differences to the way 00:33:36.458-->00:33:42.125 we use differential pass. You can with a single file, this uh detect if this file is part of a 00:33:42.125-->00:33:48.375 collision. It is very very high precision. It’s like um zer- uh the full points are zero point 00:33:48.375-->00:33:53.792 zero, zero, zero, zero, zero like 17, zero, 1. So you can run it in a projection system, it 00:33:53.792-->00:33:59.208 has a little bit of overhead but it’s okay. And it only it’s also OU which is very important to 00:33:59.208-->00:34:03.125 understand. If you see a collision how it has been constructed. So you know if it’s 00:34:03.125-->00:34:07.833 ours or if it’s a new one we’ve never seen, so that’s how they did configure the same one. So, 00:34:07.833-->00:34:13.042 counter cryptanalysis, Marc improved the version he had and pushed it on GitHub so if you 00:34:13.042-->00:34:18.375 have a SHA-1 software, using ShA-1 please use counter cryptanalysis. We do. And the we 00:34:18.375-->00:34:23.375 did that so someone from Google, shown 0:34:22 um, fixed uh JGit to basically do counter 00:34:26.167-->00:34:32.917 cryptanalysis check when you submit. So JGit will refuse any collision uh block. The other 00:34:32.917-->00:34:36.750 one who did the same thing is GitHub. GitHub in March announced their blog, well 00:34:36.750-->00:34:41.208 finally we’re going to use counter cryptanalysis. So if you use GitHub, how many of you do 00:34:41.208-->00:34:48.000 use GitHub? That’s it? I’m kidding. A lot of people use it right? Um uh you are protected 00:34:48.000-->00:34:52.083 as well because they did put in place, so check when you push your, your comment to actually 00:34:52.083-->00:34:56.042 do this. So the way you actually deal with legacy software is by doing the protection and 00:34:56.042-->00:35:01.042 practice uh mitigation. Um, and even Git bought onto the counter-cryptanalysis band 00:35:03.292-->00:35:08.292 wagon, actually it was deployed in 2012, 2. So now we have a the same. Uh, we have uh 00:35:10.500-->00:35:16.375 counter-cryptanalysis also for every Gmail document. Uh and if it drives document for good for 00:35:16.375-->00:35:21.417 system uh somehow our user detests on the day of the release to see if it’s working 00:35:21.417-->00:35:25.542 with internet. It does. Uh the reason why we do that is because we are concerned with people 00:35:25.542-->00:35:29.917 using all uh client software that we don’t know of and it might actually store them in 00:35:29.917-->00:35:33.750 backup software we don’t know of. A lot of copyright users as well so we don’t know where 00:35:33.750-->00:35:38.458 their backup system are so we basically prevent collision that way and you can do the same. Um 00:35:38.458-->00:35:44.333 as I said uh we are concerned that crash legacy software like SVN, um might have colliding 00:35:44.333-->00:35:50.417 document with different terms like contract, lease, um power of attorney and so forth. And of 00:35:50.417-->00:35:54.625 course, blackswan is unforeseen consequences that we don’t know of. And we really don’t want to 00:35:54.625-->00:36:01.625 know of. And uh so, how much does it cost us? About 4.5 percent, uh of extract 00:36:01.625-->00:36:06.333 computation, 5 e- email attachment that we scan that way. Uh that’s based on the 1 00:36:06.333-->00:36:11.292 billion datasets we tested uh after we release it. So we believe that’s way worth the 00:36:11.292-->00:36:15.833 investment. It not a huge number. It’s significant, it’s not like impossible to do. So 00:36:15.833-->00:36:21.250 where that leave us, right? Well picture is bright. Uh it’s awesome. We have a hot new hash 00:36:21.250-->00:36:27.917 function coming online. Uh we have SHA-256 and the SHA-2 family and we also have SHA-3 00:36:27.917-->00:36:32.167 and BLAKE. And what’s great about all of them is they are using different construction 00:36:32.167-->00:36:35.375 which mean that if one breaks it’s unlikely it’s going to break all of them at the same 00:36:35.375-->00:36:38.958 time so we have a lot of diversity to choose from. We all have different perspectives so 00:36:38.958-->00:36:45.292 we’re in a very good place. So hopefully you won’t have that kind of talk for the next 10 00:36:45.292-->00:36:50.292 years, hopefully. Uh, and yea, so takeaway SHA, SHA-1 is finally dead. Uh long lived to 00:36:52.292-->00:36:58.958 SHA-256. Counter-cryptanalysis is a really cool tool, and I, I hope I inspire you to check it 00:36:58.958-->00:37:04.208 out. And the future is good, so thank you very much. I’m going to take any questions you would 00:37:04.208-->00:37:09.208 have. Uh, thank you very much. [applause]