1 00:00:00,000 --> 00:00:09,600 *preroll music* 2 00:00:09,600 --> 00:00:11,350 Herald: I did some research, 3 00:00:11,350 --> 00:00:12,880 and it was not, not easy 4 00:00:12,880 --> 00:00:15,510 that Diffie-Hellman key exchange 5 00:00:15,510 --> 00:00:17,539 is so much above my pay grade 6 00:00:17,539 --> 00:00:19,879 therefore, I'm going to keep it simple. 7 00:00:19,879 --> 00:00:21,079 Please welcome 8 00:00:21,079 --> 00:00:24,480 we have Alex Halderman from the University of Michigan, 9 00:00:24,480 --> 00:00:28,799 and Nadia Heninger from the University of Pennsylvania. 10 00:00:28,799 --> 00:00:32,759 *applause* 11 00:00:32,759 --> 00:00:37,270 AH: Thank you. 12 00:00:37,270 --> 00:00:38,710 Thank you all so much. 13 00:00:38,710 --> 00:00:43,519 It's wonderful to be back again in 32C3. 14 00:00:43,519 --> 00:00:46,429 I'm Alex Halderman from the University of Michigan, 15 00:00:46,429 --> 00:00:49,379 here again this year with, 16 00:00:49,379 --> 00:00:51,309 with many of my students from my group 17 00:00:51,309 --> 00:00:54,070 here in the audience also speaking. 18 00:00:54,070 --> 00:00:57,110 We study security in the real world. 19 00:00:57,110 --> 00:01:00,960 So tonight, we have a very special story to tell you 20 00:01:00,960 --> 00:01:03,670 that I'm very proud to be telling 21 00:01:03,670 --> 00:01:06,260 along with my colleague Nadia Heninger. 22 00:01:06,260 --> 00:01:07,660 We're going to be talking 23 00:01:07,660 --> 00:01:10,890 about discrete log, Diffie-Hellman 24 00:01:10,890 --> 00:01:13,770 and some of the, um, 25 00:01:13,770 --> 00:01:15,790 the research that we've done 26 00:01:15,790 --> 00:01:16,890 over the past year, 27 00:01:16,890 --> 00:01:19,500 try to understand how the NSA 28 00:01:19,500 --> 00:01:21,640 may be breaking so much of the crypto 29 00:01:21,640 --> 00:01:23,740 that we know they're breaking. 30 00:01:23,740 --> 00:01:25,680 Why do we...? So this work is 31 00:01:25,680 --> 00:01:28,840 joint work with a number of co-authors, 32 00:01:28,840 --> 00:01:30,750 with 12 other co-authors, 33 00:01:30,750 --> 00:01:33,570 3 of them are in this room right now, 34 00:01:33,570 --> 00:01:34,750 and I'd ask to stand up 35 00:01:34,750 --> 00:01:35,920 but they said they didn't want to 36 00:01:35,920 --> 00:01:38,210 so please, a quick round of applause 37 00:01:38,210 --> 00:01:39,790 for my co-authors as well. 38 00:01:39,790 --> 00:01:47,980 *applause* 39 00:01:47,980 --> 00:01:49,790 So, thank you. 40 00:01:49,790 --> 00:01:51,100 So in this very room, 41 00:01:51,100 --> 00:01:53,620 a year ago at 31C3, 42 00:01:53,620 --> 00:01:56,250 Jacob Appelbaum and Laura Poitras 43 00:01:56,250 --> 00:01:59,250 gave a talk, "Reconstructing Narratives", 44 00:01:59,250 --> 00:02:02,860 in which they announced some new results 45 00:02:02,860 --> 00:02:05,450 from the Snowden archives. 46 00:02:05,450 --> 00:02:08,780 They were able to tell us how the NSA, 47 00:02:08,780 --> 00:02:11,920 that the NSA was breaking cryptography 48 00:02:11,920 --> 00:02:15,320 used in widespread online communication. 49 00:02:15,320 --> 00:02:17,660 And, they later published 50 00:02:17,660 --> 00:02:20,890 an article in der Spiegel, 51 00:02:20,890 --> 00:02:23,610 in which the article included documents 52 00:02:23,610 --> 00:02:27,690 that showed indeed the scope of NSA 53 00:02:27,690 --> 00:02:30,410 breaking widely used encryption 54 00:02:30,410 --> 00:02:32,210 was significant. 55 00:02:32,210 --> 00:02:33,750 That NSA is breaking, 56 00:02:33,750 --> 00:02:35,560 maybe not all crypto, 57 00:02:35,560 --> 00:02:38,230 but they're able to break widely used crypto 58 00:02:38,230 --> 00:02:40,250 from many of the different kinds 59 00:02:40,250 --> 00:02:44,540 of services and protocols we care about. 60 00:02:44,540 --> 00:02:46,400 What the leaks didn't answer 61 00:02:46,400 --> 00:02:49,440 is how NSA is breaking this cryptography 62 00:02:49,440 --> 00:02:51,210 and to a technologist, 63 00:02:51,210 --> 00:02:54,020 well, if we don't know how they're breaking it, 64 00:02:54,020 --> 00:02:56,970 what can we do to stop it? 65 00:02:56,970 --> 00:02:59,760 So, Nadia and I and our co-authors set out 66 00:02:59,760 --> 00:03:00,780 earlier this year 67 00:03:00,780 --> 00:03:03,550 to try to, through our research, 68 00:03:03,550 --> 00:03:05,780 start answering those questions. 69 00:03:05,780 --> 00:03:08,110 How is NSA likely to be breaking 70 00:03:08,110 --> 00:03:10,100 likely used cryptography, 71 00:03:10,100 --> 00:03:13,330 and what can we and other researchers do 72 00:03:13,330 --> 00:03:15,170 to stop government from being able 73 00:03:15,170 --> 00:03:18,350 to attack the crypto that all of us depend on? 74 00:03:18,350 --> 00:03:21,130 So, so... *applause* 75 00:03:21,130 --> 00:03:24,240 Let's tell the story. 76 00:03:24,240 --> 00:03:28,030 Wait until you see how it ends! 77 00:03:28,030 --> 00:03:30,390 So if I were setting out as the attacker 78 00:03:30,390 --> 00:03:32,140 to break widely used crypto, 79 00:03:32,140 --> 00:03:35,990 well, there's a few different ways that I could do it. 80 00:03:35,990 --> 00:03:38,040 One branch of the decision tree here 81 00:03:38,040 --> 00:03:40,269 is to attacking the implementations 82 00:03:40,269 --> 00:03:42,470 right, either finding vulnerabilities 83 00:03:42,470 --> 00:03:43,980 or introducing backdoors, 84 00:03:43,980 --> 00:03:46,850 we've all been witnessing over the past 85 00:03:46,850 --> 00:03:50,610 week or so with Juniper and their systems 86 00:03:50,610 --> 00:03:54,040 being compromised. 87 00:03:54,040 --> 00:03:57,290 On the other hand, there's another prong you could take. 88 00:03:57,290 --> 00:03:59,980 You could try to attack the crypto algorithms themselves, 89 00:03:59,980 --> 00:04:01,930 the underlying crypto. 90 00:04:01,930 --> 00:04:02,950 And the difference is, 91 00:04:02,950 --> 00:04:04,440 if you're attacking implementations, 92 00:04:04,440 --> 00:04:05,830 you have to make a big investment 93 00:04:05,830 --> 00:04:09,020 in every hardware device and piece of software 94 00:04:09,020 --> 00:04:10,840 that you're trying to compromise. 95 00:04:10,840 --> 00:04:13,160 If you're attacking the underlying crypto, 96 00:04:13,160 --> 00:04:17,339 you have just one, a one-stop shop 97 00:04:17,339 --> 00:04:21,029 to gain access to, potentially a very wide swath 98 00:04:21,029 --> 00:04:23,039 of all the crypto in use. 99 00:04:23,039 --> 00:04:25,139 So a small number of algorithms 100 00:04:25,139 --> 00:04:28,229 predominate for both symmetric cryptography, 101 00:04:28,229 --> 00:04:30,590 things like AES and RC4, 102 00:04:30,590 --> 00:04:32,710 but those particular algorithms anyway, 103 00:04:32,710 --> 00:04:34,509 most cryptographers seem to think 104 00:04:34,509 --> 00:04:35,659 that breaking them, 105 00:04:35,659 --> 00:04:37,300 at least in the general case, 106 00:04:37,300 --> 00:04:39,470 is pretty hard right now. 107 00:04:39,470 --> 00:04:41,300 Instead though, we also have 108 00:04:41,300 --> 00:04:44,199 a very small number of public key crypto algorithms 109 00:04:44,199 --> 00:04:46,559 that are also in use very widely 110 00:04:46,559 --> 00:04:50,339 for most or all of the protocols and services we care about. 111 00:04:50,339 --> 00:04:53,059 Things like RSA and Diffie-Hellman. 112 00:04:53,059 --> 00:04:55,779 And here be dragons, as they say, 113 00:04:55,779 --> 00:04:59,520 this is the cryptography that we and many other cryptographers 114 00:04:59,520 --> 00:05:02,610 think is most likely to be targeted. 115 00:05:02,610 --> 00:05:04,960 So, I'll hand it off to Nadia 116 00:05:04,960 --> 00:05:08,059 to talk about breaking public key. 117 00:05:08,059 --> 00:05:15,170 *applause* 118 00:05:15,170 --> 00:05:16,819 NH: So, in order to understand 119 00:05:16,819 --> 00:05:19,240 a little bit about how cryptanalysis works, 120 00:05:19,240 --> 00:05:20,800 I'm going to go all the way back 121 00:05:20,800 --> 00:05:23,349 to the very beginning of public key cryptography 122 00:05:23,349 --> 00:05:25,460 from the 70s, 123 00:05:25,460 --> 00:05:28,729 and I'll start by explaining a little bit about RSA. 124 00:05:28,729 --> 00:05:31,670 This is Rivest, Shamir, and Adleman up on the screen here, 125 00:05:31,670 --> 00:05:33,519 from the 70s, you can tell. 126 00:05:33,519 --> 00:05:35,780 And this is sort of the simple example, 127 00:05:35,780 --> 00:05:37,360 and then we'll talk a little bit more 128 00:05:37,360 --> 00:05:40,900 about the actual Diffie-Hellman-based cryptanalysis 129 00:05:40,900 --> 00:05:43,270 that we're actually talking about. 130 00:05:43,270 --> 00:05:46,770 So, this the first public-key crypto algorithm 131 00:05:46,770 --> 00:05:47,800 that was ever published, 132 00:05:47,800 --> 00:05:49,939 and it is still the most widely used 133 00:05:49,939 --> 00:05:52,680 cryptography, public key cryptography algorithm out there. 134 00:05:52,680 --> 00:05:55,389 That shows you, I guess something about the naturalness of ideas, 135 00:05:55,389 --> 00:05:56,749 or maybe the lack of progress 136 00:05:56,749 --> 00:05:59,049 that we've had in the past 40 years. 137 00:05:59,049 --> 00:06:03,529 So, here's sort of the textbook version of RSA encryption, 138 00:06:03,529 --> 00:06:05,020 what we really care about is that... 139 00:06:05,020 --> 00:06:06,639 So, Alice and Bob, they want 140 00:06:06,639 --> 00:06:08,569 to bootstrap communication over 141 00:06:08,569 --> 00:06:09,759 an untrusted channel, 142 00:06:09,759 --> 00:06:12,009 so there's some eavesdropper in between them 143 00:06:12,009 --> 00:06:13,430 who's intercepting their messages. 144 00:06:13,430 --> 00:06:15,860 And, in order to get around this, 145 00:06:15,860 --> 00:06:17,599 they need to somehow figure out 146 00:06:17,599 --> 00:06:20,979 how to share a key in order to 147 00:06:20,979 --> 00:06:23,129 actually encrypt their communications. 148 00:06:23,129 --> 00:06:25,080 And the way that RSA accomplishes this, 149 00:06:25,080 --> 00:06:30,240 is, Bob here on the right has a public key 150 00:06:30,240 --> 00:06:32,729 which in RSA is e modulus N 151 00:06:32,729 --> 00:06:35,479 which is the product of two large prime factors, 152 00:06:35,479 --> 00:06:37,589 and he sends this over to Alice, 153 00:06:37,589 --> 00:06:39,339 and Alice uses Bob's public key 154 00:06:39,339 --> 00:06:41,650 to encrypt a message, like a session key, 155 00:06:41,650 --> 00:06:43,430 and send it back to Bob, 156 00:06:43,430 --> 00:06:45,189 and then Bob can decrypt the message, 157 00:06:45,189 --> 00:06:46,340 get the session key, 158 00:06:46,340 --> 00:06:47,860 and they can communicate using 159 00:06:47,860 --> 00:06:49,510 some other symmetric cipher. 160 00:06:49,510 --> 00:06:53,919 So, this is the big picture of RSA encryption. 161 00:06:53,919 --> 00:06:55,229 The reason that we think 162 00:06:55,229 --> 00:06:58,099 that RSA is secure is because 163 00:06:58,099 --> 00:07:02,869 the best way that we know how to break an RSA public key 164 00:07:02,869 --> 00:07:04,879 is to factor the modulus, 165 00:07:04,879 --> 00:07:08,159 and as far as we know, factoring is not very easy. 166 00:07:08,159 --> 00:07:10,860 So, in particular, factoring is 167 00:07:10,860 --> 00:07:11,849 what we hope is something like 168 00:07:11,849 --> 00:07:13,179 a one-way function, 169 00:07:13,179 --> 00:07:14,610 multiplication is easy, 170 00:07:14,610 --> 00:07:17,050 factoring the number into two pieces again is hard, 171 00:07:17,050 --> 00:07:18,199 in some sense. 172 00:07:18,199 --> 00:07:19,969 And the best algorithm that we have 173 00:07:19,969 --> 00:07:21,189 in the general case, of, say 174 00:07:21,189 --> 00:07:23,719 an RSA modulus that's well-generated, 175 00:07:23,719 --> 00:07:27,110 is called the number field sieve. 176 00:07:27,110 --> 00:07:28,699 So here is the... 177 00:07:28,699 --> 00:07:30,909 this is as bad as technical as I'm going to get, 178 00:07:30,909 --> 00:07:32,789 and I'm waving my hands vigorously here, 179 00:07:32,789 --> 00:07:34,869 but here's something along the lines of 180 00:07:34,869 --> 00:07:36,419 what the number field sieve algorithm 181 00:07:36,419 --> 00:07:37,919 actually looks like, 182 00:07:37,919 --> 00:07:39,550 so it's a multi-stage algorithm, 183 00:07:39,550 --> 00:07:41,240 it's rather complex, 184 00:07:41,240 --> 00:07:43,479 some stages parallelise very well, 185 00:07:43,479 --> 00:07:44,679 embarrassingly well, 186 00:07:44,679 --> 00:07:47,990 other stages parallelise somewhat less well, 187 00:07:47,990 --> 00:07:51,189 and so we've got these multiple stages that we go through, 188 00:07:51,189 --> 00:07:53,479 and at the end of the algorithm, 189 00:07:53,479 --> 00:07:55,189 we discover, we hope, a prime factor 190 00:07:55,189 --> 00:07:59,929 of the number that we're trying to factor. 191 00:07:59,929 --> 00:08:01,579 So, how long does it take to factor? 192 00:08:01,579 --> 00:08:02,710 Here's one answer: 193 00:08:02,710 --> 00:08:04,159 if you ask a number theorist, this is 194 00:08:04,159 --> 00:08:05,589 the answer that they all give you, 195 00:08:05,589 --> 00:08:07,479 they all go through the optimisation, 196 00:08:07,479 --> 00:08:09,679 and they will tell you the answer is 197 00:08:09,679 --> 00:08:11,639 a sub-exponential function in the size 198 00:08:11,639 --> 00:08:13,380 of the number that we're trying to factor. 199 00:08:13,380 --> 00:08:14,559 That I think is not the answer 200 00:08:14,559 --> 00:08:16,740 that you guys are looking for. 201 00:08:16,740 --> 00:08:19,979 So, here's a slightly more concrete answer. 202 00:08:19,979 --> 00:08:21,679 So, how long does it take to factor 203 00:08:21,679 --> 00:08:23,080 different sizes of keys? 204 00:08:23,080 --> 00:08:25,469 So, for 512-bit RSA, 205 00:08:25,469 --> 00:08:29,979 the first 512-bit RSA modulus was factored in 1999 206 00:08:29,979 --> 00:08:30,779 by a group of academics, 207 00:08:30,779 --> 00:08:34,179 that took them 6 months and a few supercomputers, 208 00:08:34,179 --> 00:08:36,789 now you can rent supercomputers by the hour. 209 00:08:36,789 --> 00:08:38,099 So what does that do? 210 00:08:38,099 --> 00:08:39,679 Well, some students of mine 211 00:08:39,679 --> 00:08:44,099 actually were able to factor a 512-bit RSA key 212 00:08:44,099 --> 00:08:48,980 for 4 hours and 75 dollars on Amazon EC2. 213 00:08:48,980 --> 00:08:50,830 If you would like to do this too... 214 00:08:50,830 --> 00:08:54,469 *applause* 215 00:08:54,469 --> 00:08:56,880 So, you can also do this too, 216 00:08:56,880 --> 00:08:59,730 code is online, right here, download it, 217 00:08:59,730 --> 00:09:02,560 send us bug reports, etc. 218 00:09:02,560 --> 00:09:05,370 So, as we go up in key sizes, 219 00:09:05,370 --> 00:09:07,540 768-bit RSA modulus, 220 00:09:07,540 --> 00:09:10,069 estimate, current estimate is 221 00:09:10,069 --> 00:09:12,470 less than 1000 core-years, 222 00:09:12,470 --> 00:09:15,050 and for sort of reasonable-size academic clusters, 223 00:09:15,050 --> 00:09:19,270 that should take less than a calendar year to finish, now. 224 00:09:19,270 --> 00:09:22,589 That was, the first 768-bit RSA factorisation 225 00:09:22,589 --> 00:09:25,440 was done in public in 2009. 226 00:09:25,440 --> 00:09:28,459 So, that gives you some idea of sort of the progress. 227 00:09:28,459 --> 00:09:31,019 For 1024-bit RSA, nobody has factored 228 00:09:31,019 --> 00:09:32,860 a key of that size in public, 229 00:09:32,860 --> 00:09:34,139 the estimate is probably, 230 00:09:34,139 --> 00:09:36,350 it's about a million core-years, 231 00:09:36,350 --> 00:09:37,610 which is certainly within range 232 00:09:37,610 --> 00:09:41,060 for a large government, 233 00:09:41,060 --> 00:09:43,480 so it is against better recommendations 234 00:09:43,480 --> 00:09:47,539 to use a 1024-bit RSA key size, at this point. 235 00:09:47,539 --> 00:09:48,660 Current recommendation is to use 236 00:09:48,660 --> 00:09:50,810 a 2048-bit RSA modulus, 237 00:09:50,810 --> 00:09:52,600 with current algorithms, 238 00:09:52,600 --> 00:09:54,110 nobody should ever be able to factor 239 00:09:54,110 --> 00:09:55,360 something at this size, 240 00:09:55,360 --> 00:09:57,769 without some kind of major improvement. 241 00:09:57,769 --> 00:10:02,400 So, there's the big picture for you. 242 00:10:02,400 --> 00:10:05,040 Now move on to Diffie-Hellman. 243 00:10:05,040 --> 00:10:08,870 So, the paper that introduced Diffie-Hellman 244 00:10:08,870 --> 00:10:11,440 was called "New Directions in Cryptography", 245 00:10:11,440 --> 00:10:13,959 it's one of the seminal papers of the 20th century, 246 00:10:13,959 --> 00:10:15,869 how many of you have read this paper? 247 00:10:15,869 --> 00:10:17,629 You should all go read it right now, 248 00:10:17,629 --> 00:10:20,750 I mean not right now, maybe after I talk. 249 00:10:20,750 --> 00:10:22,700 The first sentence of this paper, 250 00:10:22,700 --> 00:10:24,690 written in 1976, 251 00:10:24,690 --> 00:10:28,399 is "We stand today on the brink of a revolution in cryptography". 252 00:10:28,399 --> 00:10:30,279 This is one of the best opening sentences 253 00:10:30,279 --> 00:10:32,360 of an academic paper I've ever read, 254 00:10:32,360 --> 00:10:36,170 and they were 100% right about everything they put in the paper. 255 00:10:36,170 --> 00:10:37,860 They laid out the entire foundations 256 00:10:37,860 --> 00:10:41,089 of cryptographic research for a couple decades, 257 00:10:41,089 --> 00:10:43,269 and to boot they came up with 258 00:10:43,269 --> 00:10:45,660 the first public key exchange, 259 00:10:45,660 --> 00:10:48,230 that is still one of the commonly used 260 00:10:48,230 --> 00:10:50,510 public key methods we 261 00:10:50,510 --> 00:10:51,850 have on the Internet. 262 00:10:51,850 --> 00:10:55,750 So, all that in one paper. 263 00:10:55,750 --> 00:10:58,759 So, the way that textbook Diffie-Hellman works, 264 00:10:58,759 --> 00:11:00,910 is, you've got a couple of parameters, 265 00:11:00,910 --> 00:11:03,509 you've got a prime p, 266 00:11:03,509 --> 00:11:09,060 and some element g less than p, 267 00:11:09,060 --> 00:11:11,250 you can think, for concreteness, g is 2. 268 00:11:11,250 --> 00:11:12,760 It's a good number. 269 00:11:12,760 --> 00:11:15,759 And p is some very large prime, 270 00:11:15,759 --> 00:11:18,620 say 1024, 2048-bit prime. 271 00:11:18,620 --> 00:11:20,579 And so Alice and Bob, 272 00:11:20,579 --> 00:11:21,800 same as our previous scenario, 273 00:11:21,800 --> 00:11:23,190 they want to bootstrap communication 274 00:11:23,190 --> 00:11:25,790 in the presence of an untrusted eavesdropper. 275 00:11:25,790 --> 00:11:26,980 So what they're going to do, 276 00:11:26,980 --> 00:11:29,479 Alice will generate some secret value a, 277 00:11:29,479 --> 00:11:32,259 and she will compute g^a mod p, 278 00:11:32,259 --> 00:11:34,049 and send it over to Bob, 279 00:11:34,049 --> 00:11:36,920 and Bob will compute some secret value b, 280 00:11:36,920 --> 00:11:38,410 and compute g^b mod p, 281 00:11:38,410 --> 00:11:40,089 and send it over to Alice, 282 00:11:40,089 --> 00:11:43,870 the eavesdropper sees the values g^a and g^b, 283 00:11:43,870 --> 00:11:45,720 can't derive anything useful from those, 284 00:11:45,720 --> 00:11:47,779 but Alice and Bob can individually 285 00:11:47,779 --> 00:11:48,790 take their secrets 286 00:11:48,790 --> 00:11:52,410 and derive the values g^ab mod p, 287 00:11:52,410 --> 00:11:53,819 both the same values. 288 00:11:53,819 --> 00:11:55,680 And that becomes a shared secret, 289 00:11:55,680 --> 00:11:58,250 which they can then use as a session key, 290 00:11:58,250 --> 00:11:59,860 and, you know, switch to AES 291 00:11:59,860 --> 00:12:02,550 and start symmetrically encrypting their data. 292 00:12:02,550 --> 00:12:05,070 So, that's Diffie-Hellman key exchange. 293 00:12:05,070 --> 00:12:06,470 Used all over the Internet, 294 00:12:06,470 --> 00:12:09,389 one of the commonly used things possible. 295 00:12:09,389 --> 00:12:12,939 So, one of the reasons that people 296 00:12:12,939 --> 00:12:15,499 have been advocating Diffie-Hellman key exchange recently 297 00:12:15,499 --> 00:12:17,189 over, say, RSA, 298 00:12:17,189 --> 00:12:20,319 is because it can be, it can provide 299 00:12:20,319 --> 00:12:22,470 the property of perfect forward secrecy. 300 00:12:22,470 --> 00:12:23,649 So assuming that Alice and Bob 301 00:12:23,649 --> 00:12:26,720 generate fresh random secret values a and b 302 00:12:26,720 --> 00:12:28,639 for every single connection, 303 00:12:28,639 --> 00:12:32,600 then if, say, some large government agency 304 00:12:32,600 --> 00:12:34,740 is collecting all of their communications 305 00:12:34,740 --> 00:12:37,290 and later tries to hack into Alice or Bob, 306 00:12:37,290 --> 00:12:38,730 or break one of their keys, 307 00:12:38,730 --> 00:12:40,899 in order to decrypt their communication, 308 00:12:40,899 --> 00:12:44,029 they can't hack into Alice or Bob's computer later, 309 00:12:44,029 --> 00:12:46,389 and then discover the key 310 00:12:46,389 --> 00:12:47,860 that Alice and Bob used 311 00:12:47,860 --> 00:12:51,080 to generate all the conversations that they had, 312 00:12:51,080 --> 00:12:53,650 because Alice and Bob have already forgotten 313 00:12:53,650 --> 00:12:55,160 the keys that they used. 314 00:12:55,160 --> 00:12:56,560 So, as long as Alice and Bob 315 00:12:56,560 --> 00:12:59,969 are generating fresh random values every time, 316 00:12:59,969 --> 00:13:01,279 those values should reveal nothing 317 00:13:01,279 --> 00:13:04,719 about past or future communications. 318 00:13:04,719 --> 00:13:07,320 So, that's perfect forward secrecy. 319 00:13:07,320 --> 00:13:09,470 And, a lot of people have, 320 00:13:09,470 --> 00:13:11,090 who really know what they're talking about, 321 00:13:11,090 --> 00:13:13,039 including, unfortunately, me, 322 00:13:13,039 --> 00:13:15,080 on this stage a couple years ago, 323 00:13:15,080 --> 00:13:19,920 have said, "you guys should always use Diffie-Hellman over RSA key exchange 324 00:13:19,920 --> 00:13:22,590 because of this property of perfect forward secrecy". 325 00:13:22,590 --> 00:13:24,670 So here's a selection of quotes 326 00:13:24,670 --> 00:13:25,939 that I found on the Internet, 327 00:13:25,939 --> 00:13:27,629 just from googling "perfect forward secrecy" 328 00:13:27,629 --> 00:13:29,029 and "Diffie-Hellman key exchange", 329 00:13:29,029 --> 00:13:30,839 and you find people saying that 330 00:13:30,839 --> 00:13:33,100 this provides better security, 331 00:13:33,100 --> 00:13:35,699 the NSA can decrypt nothing, 332 00:13:35,699 --> 00:13:40,589 1024-bit Diffie-Hellman is arguably better than 1024-bit RSA, 333 00:13:40,589 --> 00:13:45,829 and then 1024-bit Diffie-Hellman is better than any key size for RSA. 334 00:13:45,829 --> 00:13:47,870 This is a selection of friends 335 00:13:47,870 --> 00:13:49,300 and people I respect, 336 00:13:49,300 --> 00:13:52,500 and some also, also some random people on Stack Overflow, 337 00:13:52,500 --> 00:13:53,999 which is where... 338 00:13:53,999 --> 00:13:55,180 *laughter* 339 00:13:55,180 --> 00:13:56,149 where we know everybody's actually 340 00:13:56,149 --> 00:13:58,270 getting their recommendations from. 341 00:13:58,270 --> 00:14:00,980 So, there's been wide-scale advocacy 342 00:14:00,980 --> 00:14:03,419 of perfect forward secrecy as 343 00:14:03,419 --> 00:14:05,639 like, the reason that you should use Diffie-Hellman. 344 00:14:05,639 --> 00:14:09,149 It will protect you against the NSA. 345 00:14:09,149 --> 00:14:13,049 I'm sorry. We were wrong. 346 00:14:13,049 --> 00:14:14,230 And, why were we wrong? 347 00:14:14,230 --> 00:14:15,339 I'm going to tell little bit more 348 00:14:15,339 --> 00:14:17,199 about what the cryptanalysis looks like 349 00:14:17,199 --> 00:14:18,379 for Diffie-Hellman. 350 00:14:18,379 --> 00:14:21,670 So, the underlying problem that we hope is hard 351 00:14:21,670 --> 00:14:22,779 for the security of Diffie-Hellman 352 00:14:22,779 --> 00:14:24,110 is called discrete log, 353 00:14:24,110 --> 00:14:26,629 it is exactly sort of the problem of 354 00:14:26,629 --> 00:14:30,160 given one of the key exchange values g^a mod p 355 00:14:30,160 --> 00:14:33,059 compute, say, Alice's secret a. 356 00:14:33,059 --> 00:14:34,470 This would allow the attacker 357 00:14:34,470 --> 00:14:35,579 to compute the shared secret 358 00:14:35,579 --> 00:14:39,050 in the same way that Alice did. 359 00:14:39,050 --> 00:14:42,950 And, sort of similar to factoring and multiplication, 360 00:14:42,950 --> 00:14:44,540 discrete log, we think it's much harder 361 00:14:44,540 --> 00:14:46,550 than modular exponentiation, 362 00:14:46,550 --> 00:14:48,420 the computation that actually 363 00:14:48,420 --> 00:14:50,519 gives you the value g^a mod p. 364 00:14:50,519 --> 00:14:52,810 And the best algorithm that we have 365 00:14:52,810 --> 00:14:54,720 is called the number field sieve. 366 00:14:54,720 --> 00:14:58,049 So, there's a lot of parallels going on here. 367 00:14:58,049 --> 00:14:59,259 So what does the number field sieve 368 00:14:59,259 --> 00:15:00,939 for discrete log look like? 369 00:15:00,939 --> 00:15:05,030 Hopefully this diagram is somewhat familiar to you by now, 370 00:15:05,030 --> 00:15:06,600 it's a multi-stage algorithm, 371 00:15:06,600 --> 00:15:10,490 it has many of the same stages as factoring, 372 00:15:10,490 --> 00:15:12,699 you can sort of line them up in parallel, 373 00:15:12,699 --> 00:15:14,949 the last bit looks a little bit different, 374 00:15:14,949 --> 00:15:17,090 but we can sort of ignore that for the moment. 375 00:15:17,090 --> 00:15:20,160 Okay. So, we have some pictures 376 00:15:20,160 --> 00:15:22,829 of what the number field sieve looks like. 377 00:15:22,829 --> 00:15:24,699 How long does it take? 378 00:15:24,699 --> 00:15:28,720 Answer number 1: The same answer as factoring. 379 00:15:28,720 --> 00:15:31,379 In case you didn't remember, here it is again. 380 00:15:31,379 --> 00:15:33,420 This is kind of why everybody has been saying 381 00:15:33,420 --> 00:15:35,260 "Okay, the security of, you know, 382 00:15:35,260 --> 00:15:36,829 1024-bit Diffie-Hellman key exchange 383 00:15:36,829 --> 00:15:38,959 is about the same as the security of 384 00:15:38,959 --> 00:15:41,059 a 1024-bit RSA key." 385 00:15:41,059 --> 00:15:44,809 It's because we have the same complicated formula that tells us 386 00:15:44,809 --> 00:15:47,730 how hard it is to break. 387 00:15:47,730 --> 00:15:49,779 The sort of more subtle answer for... 388 00:15:49,779 --> 00:15:51,699 or, not more subtle, but the more practical answer 389 00:15:51,699 --> 00:15:53,070 for, how secure is it, 390 00:15:53,070 --> 00:15:55,769 is, we can say, well, how long do we think 391 00:15:55,769 --> 00:15:56,959 it will take to actually compute 392 00:15:56,959 --> 00:15:59,910 a discrete log for commonly used key sizes, 393 00:15:59,910 --> 00:16:01,089 and the answer is, 394 00:16:01,089 --> 00:16:04,600 slightly longer than factoring an RSA key of equivalent size, 395 00:16:04,600 --> 00:16:09,479 but, not so much longer than an RSA key. 396 00:16:09,479 --> 00:16:12,160 And, the minimum recommended key size 397 00:16:12,160 --> 00:16:14,759 today is 2048 bits. 398 00:16:14,759 --> 00:16:18,019 Okay, so, 2048-bit Diffie-Hellman, 399 00:16:18,019 --> 00:16:22,219 we're good. Great! We can all go home. 400 00:16:22,219 --> 00:16:24,499 Okay. However, okay, 401 00:16:24,499 --> 00:16:26,350 what if you want to break many connections 402 00:16:26,350 --> 00:16:28,829 that use the same public parameter p? 403 00:16:28,829 --> 00:16:30,749 Do you have to go through 404 00:16:30,749 --> 00:16:33,569 this whole computation, 405 00:16:33,569 --> 00:16:35,269 every single, for every single connection 406 00:16:35,269 --> 00:16:36,569 that you want to break? 407 00:16:36,569 --> 00:16:41,100 That was kind of the justification 408 00:16:41,100 --> 00:16:42,550 for perfect forward secrecy, 409 00:16:42,550 --> 00:16:43,949 that every single connection 410 00:16:43,949 --> 00:16:45,920 should be as hard as factoring an RSA key 411 00:16:45,920 --> 00:16:48,259 of the equivalent size. 412 00:16:48,259 --> 00:16:50,489 Except that's not quite the case. 413 00:16:50,489 --> 00:16:51,850 Because if you look at where 414 00:16:51,850 --> 00:16:54,360 the actual target that we're trying to compute 415 00:16:54,360 --> 00:16:56,730 appears in this plot, 416 00:16:56,730 --> 00:16:58,620 it's only at the very last stage. 417 00:16:58,620 --> 00:17:00,410 So all of this only depends 418 00:17:00,410 --> 00:17:01,979 on the prime p. 419 00:17:01,979 --> 00:17:05,720 So we can actually divide up the algorithm in two pieces: 420 00:17:05,720 --> 00:17:09,579 A few stages that depend only on the prime p that we're using, 421 00:17:09,579 --> 00:17:11,640 and then the final computation 422 00:17:11,640 --> 00:17:14,480 that takes the output of this first precomputation stage, 423 00:17:14,480 --> 00:17:15,520 and that's the only stage 424 00:17:15,520 --> 00:17:17,280 that actually matters, 425 00:17:17,280 --> 00:17:19,450 that actually depends on the target 426 00:17:19,450 --> 00:17:22,610 of our discrete log computation. 427 00:17:22,610 --> 00:17:27,459 So, we're in trouble. 428 00:17:27,459 --> 00:17:29,550 In particular, that means that 429 00:17:29,550 --> 00:17:33,390 if many connections are using this same prime p, 430 00:17:33,390 --> 00:17:35,650 you can do the precomputation once, 431 00:17:35,650 --> 00:17:37,470 spend a huge amount of effort, 432 00:17:37,470 --> 00:17:39,490 and then the actual effort required 433 00:17:39,490 --> 00:17:43,260 to break individual connections using those primes 434 00:17:43,260 --> 00:17:46,060 is much, much smaller. 435 00:17:46,060 --> 00:17:48,300 So here's our current estimates, 436 00:17:48,300 --> 00:17:50,430 these are actually somewhat new from our paper, 437 00:17:50,430 --> 00:17:54,120 of how long the individual log stage takes in practice, 438 00:17:54,120 --> 00:17:55,810 if you push the primer as far as you can 439 00:17:55,810 --> 00:17:57,680 to make this as fast as possible. 440 00:17:57,680 --> 00:17:59,330 And the answer is basically, 441 00:17:59,330 --> 00:18:01,810 if you're worried about a government, 442 00:18:01,810 --> 00:18:03,540 you better start worrying 443 00:18:03,540 --> 00:18:08,650 for reasonable key sizes that people are using. 444 00:18:08,650 --> 00:18:11,380 See, so I'll let Alex continue 445 00:18:11,380 --> 00:18:14,520 with the next part of our talk. 446 00:18:14,520 --> 00:18:21,800 *applause* 447 00:18:21,800 --> 00:18:24,830 So this fact that Nadia just told us 448 00:18:24,830 --> 00:18:27,290 about Diffie-Hellman 449 00:18:27,290 --> 00:18:29,150 and the number field sieve, 450 00:18:29,150 --> 00:18:33,600 this was something that the mathematical crypto people knew about, 451 00:18:33,600 --> 00:18:35,970 but most of us who did system security, 452 00:18:35,970 --> 00:18:37,610 people like me, 453 00:18:37,610 --> 00:18:40,030 didn't ever get the memo. 454 00:18:40,030 --> 00:18:43,880 So, it's, I'm here in part to apologise 455 00:18:43,880 --> 00:18:45,290 to everyone I've taught 456 00:18:45,290 --> 00:18:48,290 about Diffie-Hellman and cryptanalysis 457 00:18:48,290 --> 00:18:50,010 who didn't get to hear about this, 458 00:18:50,010 --> 00:18:51,000 as we were talking about 459 00:18:51,000 --> 00:18:52,490 perfect forward secrecy. 460 00:18:52,490 --> 00:18:54,840 Right, this fact about the cryptanalysis 461 00:18:54,840 --> 00:18:56,910 and how well it can apply in exactly 462 00:18:56,910 --> 00:18:58,670 the scenario that we're worried about, 463 00:18:58,670 --> 00:19:02,090 this kind of situation involving mass surveillance, 464 00:19:02,090 --> 00:19:04,670 was news to many of those. 465 00:19:04,670 --> 00:19:06,320 But now that we have that fact, 466 00:19:06,320 --> 00:19:08,040 how can we exploit it, 467 00:19:08,040 --> 00:19:09,870 to try to break Diffie-Hellman, 468 00:19:09,870 --> 00:19:12,080 in scenarios that we all care about? 469 00:19:12,080 --> 00:19:13,020 And we're going to talk about 470 00:19:13,020 --> 00:19:15,960 two scenarios in the talk today. 471 00:19:15,960 --> 00:19:19,130 The first one applies to HTTPS, 472 00:19:19,130 --> 00:19:21,720 to encrypted web connections, 473 00:19:21,720 --> 00:19:24,960 and it applies not only to government agencies, 474 00:19:24,960 --> 00:19:27,750 but also just to normal everyday attackers, 475 00:19:27,750 --> 00:19:29,020 with maybe the same resources 476 00:19:29,020 --> 00:19:31,030 that you or I have. 477 00:19:31,030 --> 00:19:35,280 Right, this is a down-to-earth kind of attack on HTTPS, 478 00:19:35,280 --> 00:19:37,630 and we call it Logjam. 479 00:19:37,630 --> 00:19:39,870 Logjam allows us to break 480 00:19:39,870 --> 00:19:41,740 the HTTPS connections 481 00:19:41,740 --> 00:19:44,070 to many, many popular websites 482 00:19:44,070 --> 00:19:45,800 in modern browsers, 483 00:19:45,800 --> 00:19:48,610 by fooling those browsers into using 484 00:19:48,610 --> 00:19:53,310 1990s-era backdoored crypto. 485 00:19:53,310 --> 00:19:55,680 So where does this backdoored crypto come from? 486 00:19:55,680 --> 00:19:57,650 This is from the first crypto wars, 487 00:19:57,650 --> 00:19:59,040 back in the 90s, 488 00:19:59,040 --> 00:20:01,330 when my country, the US, 489 00:20:01,330 --> 00:20:04,110 had restrictions on what kind and strength 490 00:20:04,110 --> 00:20:06,680 of cryptography could be exported, 491 00:20:06,680 --> 00:20:08,690 and used by people abroad. 492 00:20:08,690 --> 00:20:10,580 So US companies were prohibited 493 00:20:10,580 --> 00:20:12,570 from exporting products that contained 494 00:20:12,570 --> 00:20:15,960 cryptography that had greater than a certain strength. 495 00:20:15,960 --> 00:20:18,020 For RSA, that was that the key size 496 00:20:18,020 --> 00:20:21,250 had to be less than or equal to 512 bits, 497 00:20:21,250 --> 00:20:22,840 and for Diffie-Hellman it was that 498 00:20:22,840 --> 00:20:27,400 basically the prime had to be 512 bits or less. 499 00:20:27,400 --> 00:20:28,540 So back in the 90s, 500 00:20:28,540 --> 00:20:29,970 these were constants, 501 00:20:29,970 --> 00:20:31,380 these were strengths of crypto 502 00:20:31,380 --> 00:20:33,730 that were chosen presumably because 503 00:20:33,730 --> 00:20:37,740 they were easy for NSA to break. 504 00:20:37,740 --> 00:20:39,690 So, if you were an American company 505 00:20:39,690 --> 00:20:42,170 making products, like let's say 506 00:20:42,170 --> 00:20:44,830 Netscape Navigator, the web browser 507 00:20:44,830 --> 00:20:50,980 that initiated the first SSL protocol, 508 00:20:50,980 --> 00:20:53,000 you needed some way to be able 509 00:20:53,000 --> 00:20:54,980 to communicate with, 510 00:20:54,980 --> 00:20:56,920 from servers in the US, 511 00:20:56,920 --> 00:20:59,360 to clients, including your own browser, 512 00:20:59,360 --> 00:21:01,070 that you would ship to people abroad, 513 00:21:01,070 --> 00:21:03,120 say, here in Germany. 514 00:21:03,120 --> 00:21:04,870 And so they came up with a way 515 00:21:04,870 --> 00:21:10,660 to use, to have HTTPS automatically select 516 00:21:10,660 --> 00:21:12,880 the appropriate key strength 517 00:21:12,880 --> 00:21:14,430 depending on whether the browser 518 00:21:14,430 --> 00:21:17,470 was able to support the full-strength cryptography, 519 00:21:17,470 --> 00:21:18,740 or the weakened version 520 00:21:18,740 --> 00:21:20,530 for deployment abroad. 521 00:21:20,530 --> 00:21:22,290 And the way that they did that 522 00:21:22,290 --> 00:21:23,350 was something called 523 00:21:23,350 --> 00:21:26,210 export-grade cipher suites. 524 00:21:26,210 --> 00:21:27,090 So when your browser, 525 00:21:27,090 --> 00:21:29,080 whenever it starts a TLS connection 526 00:21:29,080 --> 00:21:31,380 for an HTTPS URL, 527 00:21:31,380 --> 00:21:32,800 one of the first thing that it does 528 00:21:32,800 --> 00:21:35,540 is, the browser will send to the server 529 00:21:35,540 --> 00:21:37,480 a list of the kinds of cryptography 530 00:21:37,480 --> 00:21:38,930 that it can speak, 531 00:21:38,930 --> 00:21:40,950 these are called cipher suites, 532 00:21:40,950 --> 00:21:44,150 and then the server selects one of those, 533 00:21:44,150 --> 00:21:46,240 that is compatible with whatever cryptography 534 00:21:46,240 --> 00:21:48,190 the server has available, 535 00:21:48,190 --> 00:21:50,450 and then that negotiated cipher suite 536 00:21:50,450 --> 00:21:53,540 is what's used for the connection. 537 00:21:53,540 --> 00:21:55,210 Now the way that they supported 538 00:21:55,210 --> 00:21:57,890 the 90s-era backdoor crypto 539 00:21:57,890 --> 00:22:01,380 was by having browsers shipped abroad 540 00:22:01,380 --> 00:22:03,370 from the United States that could only 541 00:22:03,370 --> 00:22:06,140 speak a certain subset of crypto algorithms, 542 00:22:06,140 --> 00:22:07,520 that were limited in strength 543 00:22:07,520 --> 00:22:09,880 to 512 bits or less, 544 00:22:09,880 --> 00:22:11,730 those were the export-grade cipher suites 545 00:22:11,730 --> 00:22:13,870 with the names you see here. 546 00:22:13,870 --> 00:22:18,930 Now, even though no browser has been shipped 547 00:22:18,930 --> 00:22:21,740 that is limited to only these suites, 548 00:22:21,740 --> 00:22:24,340 since probably 2000-sometime, 549 00:22:24,340 --> 00:22:27,520 when the US relaxed its export regulations, 550 00:22:27,520 --> 00:22:29,440 there wasn't just any one day 551 00:22:29,440 --> 00:22:33,060 when all of those old browsers 552 00:22:33,060 --> 00:22:35,490 from before that era went away. 553 00:22:35,490 --> 00:22:38,830 So, servers, even now, many servers 554 00:22:38,830 --> 00:22:42,630 will still accept and speak these weakened cipher suites, 555 00:22:42,630 --> 00:22:45,450 if that's all the browser has available. 556 00:22:45,450 --> 00:22:47,550 Like if you're running an e-commerce site, 557 00:22:47,550 --> 00:22:49,760 right, I'm sure you still want to be able 558 00:22:49,760 --> 00:22:51,430 to speak to any customers 559 00:22:51,430 --> 00:22:54,670 who have 1998-era Netspace Navigator involved, 560 00:22:54,670 --> 00:22:57,030 otherwise you'd lose some sales, right? 561 00:22:57,030 --> 00:22:59,010 So there was no reason to turn them off, 562 00:22:59,010 --> 00:23:02,050 because no modern browser any more, 563 00:23:02,050 --> 00:23:03,900 now that those restrictions are lifted, 564 00:23:03,900 --> 00:23:06,690 would choose these weakened suites. 565 00:23:06,690 --> 00:23:09,450 Well, that's what we thought, anyway. 566 00:23:09,450 --> 00:23:13,360 So, in, over this past year, 567 00:23:13,360 --> 00:23:15,740 there were two attacks that exploited 568 00:23:15,740 --> 00:23:17,290 these weakened cipher suites, 569 00:23:17,290 --> 00:23:20,710 that found ways to convince modern browsers 570 00:23:20,710 --> 00:23:23,990 to speak them instead of full-strength cryptography. 571 00:23:23,990 --> 00:23:26,500 The first was the FREAK attack, 572 00:23:26,500 --> 00:23:28,800 which was revealed in early 2015 573 00:23:28,800 --> 00:23:32,040 by a separate group of authors, 574 00:23:32,040 --> 00:23:34,980 and the FREAK attack was an implementation flaw 575 00:23:34,980 --> 00:23:38,850 in many modern browsers. 576 00:23:38,850 --> 00:23:40,370 In order to exploit it, 577 00:23:40,370 --> 00:23:42,150 all you need to do is to be able 578 00:23:42,150 --> 00:23:44,220 to relatively inexpensively 579 00:23:44,220 --> 00:23:48,340 factor a 512-bit RSA key. 580 00:23:48,340 --> 00:23:50,070 And, as Nadia has told you, 581 00:23:50,070 --> 00:23:52,760 this is now a matter of maybe 4 hours, 582 00:23:52,760 --> 00:23:55,250 maybe 75 dollars, something like that, 583 00:23:55,250 --> 00:23:57,230 and if you did that, you'd able to break 584 00:23:57,230 --> 00:23:59,640 all the connections coming into 585 00:23:59,640 --> 00:24:01,920 a weak server for a long period of time, 586 00:24:01,920 --> 00:24:06,150 to a server that still spoke these cipher suites. 587 00:24:06,150 --> 00:24:08,030 So this affected most modern browsers, 588 00:24:08,030 --> 00:24:14,440 and just shy of 10% of Alexa top million sites that speak HTTPS. 589 00:24:14,440 --> 00:24:16,880 Now that left the Diffie-Hellman 590 00:24:16,880 --> 00:24:18,650 export-grade cipher suites, 591 00:24:18,650 --> 00:24:21,000 which were not affected by FREAK. 592 00:24:21,000 --> 00:24:25,780 But we came up with a paper in May of this year, 593 00:24:25,780 --> 00:24:27,570 that showed a separate attack, 594 00:24:27,570 --> 00:24:29,180 the Logjam attack, 595 00:24:29,180 --> 00:24:32,000 which is a protocol flaw in TLS, 596 00:24:32,000 --> 00:24:34,450 and affects all modern browsers, 597 00:24:34,450 --> 00:24:38,370 and, similarly, allows you to downgrade connections 598 00:24:38,370 --> 00:24:40,580 to export-grade Diffie-Hellman, 599 00:24:40,580 --> 00:24:43,010 and then intercept or modify the contents, 600 00:24:43,010 --> 00:24:46,840 if the server speaks and still supports 601 00:24:46,840 --> 00:24:50,840 these export-grade Diffie-Hellman cipher suites. 602 00:24:50,840 --> 00:24:52,290 So now let me give you 603 00:24:52,290 --> 00:24:55,030 the hopefully brief technical overview 604 00:24:55,030 --> 00:24:57,090 of how the Logjam attack works. 605 00:24:57,090 --> 00:24:59,080 If you've been curious about this, 606 00:24:59,080 --> 00:25:02,840 this is the chance to see it. 607 00:25:02,840 --> 00:25:04,920 So, Logjam is a problem that happens 608 00:25:04,920 --> 00:25:08,460 during the TLS connection handshake. 609 00:25:08,460 --> 00:25:10,200 And the first thing that happens in the handshake, 610 00:25:10,200 --> 00:25:11,610 at the top of this diagram, 611 00:25:11,610 --> 00:25:13,430 so this is just your browser connecting 612 00:25:13,430 --> 00:25:16,600 to some website, some server there on the right, 613 00:25:16,600 --> 00:25:19,580 maybe Alice connecting to her favourite website here. 614 00:25:19,580 --> 00:25:21,560 So the first stage is this client hello, 615 00:25:21,560 --> 00:25:24,520 where, you know, a normal client is going to say, 616 00:25:24,520 --> 00:25:26,790 I speak various kinds of cryptography, 617 00:25:26,790 --> 00:25:29,650 including full-strength Diffie-Hellman. 618 00:25:29,650 --> 00:25:31,350 The server at that point is going to 619 00:25:31,350 --> 00:25:35,720 respond by picking some cipher suite, 620 00:25:35,720 --> 00:25:37,560 let's say Diffie-Hellman, 621 00:25:37,560 --> 00:25:40,610 and then sending over its certificate chain, 622 00:25:40,610 --> 00:25:45,280 as well as its Diffie-Hellman public parameters, 623 00:25:45,280 --> 00:25:47,990 p and g, the server gets to choose them, 624 00:25:47,990 --> 00:25:49,260 as well as g^a. 625 00:25:49,260 --> 00:25:50,820 And then it's going to use 626 00:25:50,820 --> 00:25:54,760 its long-term RSA key that is the thing 627 00:25:54,760 --> 00:25:56,810 that is signed in its certificate, 628 00:25:56,810 --> 00:26:00,210 in order to make a signature on those Diffie-Hellman parameters. 629 00:26:00,210 --> 00:26:02,130 Okay, then it's going to do... 630 00:26:02,130 --> 00:26:05,390 complete the negotiation, and so on. 631 00:26:05,390 --> 00:26:06,820 In the Logjam attack, 632 00:26:06,820 --> 00:26:08,610 we have a man-in-the-middle attacker, 633 00:26:08,610 --> 00:26:10,970 who's able to modify some of these messages 634 00:26:10,970 --> 00:26:13,030 as they're going by. 635 00:26:13,030 --> 00:26:14,960 So the first thing the attacker does, 636 00:26:14,960 --> 00:26:17,460 he modifies the client hello message, 637 00:26:17,460 --> 00:26:19,710 to replace all of the different kinds of cryptography 638 00:26:19,710 --> 00:26:21,640 the client says it supports, 639 00:26:21,640 --> 00:26:24,560 and just put in export-grade Diffie-Hellman. 640 00:26:24,560 --> 00:26:27,240 Ah, the 90s are here again. 641 00:26:27,240 --> 00:26:29,920 Alright, so then, you know, the server 642 00:26:29,920 --> 00:26:32,790 will get that, and if the server supports 643 00:26:32,790 --> 00:26:34,850 export-grade Diffie-Hellman, 644 00:26:34,850 --> 00:26:39,180 as about 10% or so of servers 645 00:26:39,180 --> 00:26:41,070 still support export grade Diffie-Hellman, 646 00:26:41,070 --> 00:26:43,670 it's going to respond and say, 647 00:26:43,670 --> 00:26:46,110 okay, that's what you asked for, I'll take it, 648 00:26:46,110 --> 00:26:49,100 and it's going to send over its side 649 00:26:49,100 --> 00:26:51,270 of the Diffie-Hellman key exchange, 650 00:26:51,270 --> 00:26:54,170 but using a 512-bit prime, 651 00:26:54,170 --> 00:26:56,550 because that's what is required under 652 00:26:56,550 --> 00:26:59,500 these export-grade suites. 653 00:26:59,500 --> 00:27:02,400 Now, at that point, the browser would 654 00:27:02,400 --> 00:27:04,600 normally reject this message, 655 00:27:04,600 --> 00:27:06,540 because it didn't ask for export-grade, 656 00:27:06,540 --> 00:27:09,770 it really asked for full-strength, 657 00:27:09,770 --> 00:27:11,540 so instead, the man in the middle has to 658 00:27:11,540 --> 00:27:15,500 modify the server's hello message, 659 00:27:15,500 --> 00:27:18,270 and say that this is full-strength Diffie-Hellman, 660 00:27:18,270 --> 00:27:19,630 well, if it's full-strength, 661 00:27:19,630 --> 00:27:22,970 why is it only a 512-bit prime that's being used? 662 00:27:22,970 --> 00:27:25,780 Well, there's actually no limitation, 663 00:27:25,780 --> 00:27:27,820 and no distinction between the messages 664 00:27:27,820 --> 00:27:33,550 that the server would send in that space with p and g, 665 00:27:33,550 --> 00:27:35,980 that says normal-grade Diffie-Hellman 666 00:27:35,980 --> 00:27:38,410 has to be more than 512 bits. 667 00:27:38,410 --> 00:27:41,110 In fact we found a handful of real sites 668 00:27:41,110 --> 00:27:43,480 that even for normal-strength Diffie-Hellman 669 00:27:43,480 --> 00:27:48,540 just happened to use 512-bit or even weaker cryptography. 670 00:27:48,540 --> 00:27:50,960 So, as long as we modify this earlier message, 671 00:27:50,960 --> 00:27:52,680 the server's hello message, 672 00:27:52,680 --> 00:27:55,240 and make it say, "normal-strength Diffie-Hellman", 673 00:27:55,240 --> 00:27:57,460 there's no way for the client to tell 674 00:27:57,460 --> 00:27:59,420 from just the structure of the protocol, 675 00:27:59,420 --> 00:28:01,460 that anything is amiss. 676 00:28:01,460 --> 00:28:04,570 So, at this point, there is one last place 677 00:28:04,570 --> 00:28:06,130 that we could catch the problem, 678 00:28:06,130 --> 00:28:07,850 that the client or the server could see 679 00:28:07,850 --> 00:28:09,670 that something's wrong, 680 00:28:09,670 --> 00:28:12,800 which is that each side sends the other a finished message, 681 00:28:12,800 --> 00:28:15,010 here at the end, 682 00:28:15,010 --> 00:28:22,100 that says, basically, has, uses the session secrets 683 00:28:22,100 --> 00:28:25,020 to add an authentication code 684 00:28:25,020 --> 00:28:27,750 to a dialogue of all of the protocol messages 685 00:28:27,750 --> 00:28:30,370 that match the handshake dialogue, 686 00:28:30,370 --> 00:28:34,090 all the messages going back in each direction so far 687 00:28:34,090 --> 00:28:37,280 have to be the same from each side of you. 688 00:28:37,280 --> 00:28:40,300 However, in our case, in Logjam, 689 00:28:40,300 --> 00:28:43,170 the attacker is able to spoof these messages, 690 00:28:43,170 --> 00:28:45,730 to make them look correct to each side. 691 00:28:45,730 --> 00:28:48,370 He's able to modify that dialogue why? 692 00:28:48,370 --> 00:28:52,900 Well, because we're using this 512-bit Diffie-Hellman 693 00:28:52,900 --> 00:28:58,150 that we know from using the number field sieve, 694 00:28:58,150 --> 00:29:00,270 we are able to efficiently break. 695 00:29:00,270 --> 00:29:02,730 So, if the attacker is able to quickly 696 00:29:02,730 --> 00:29:03,990 perform the discrete log 697 00:29:03,990 --> 00:29:08,560 on the Diffie-Hellman key exchange 698 00:29:08,560 --> 00:29:11,430 that's going by at 512-bit strength, 699 00:29:11,430 --> 00:29:14,610 then he can fix up the client and server hello messages, 700 00:29:14,610 --> 00:29:17,380 and neither side will notice that anything went wrong. 701 00:29:17,380 --> 00:29:19,290 So that's Logjam in a nutshell. 702 00:29:19,290 --> 00:29:21,790 I'm sorry, it's a little bit complicated. 703 00:29:21,790 --> 00:29:24,680 So, how widely shared are 704 00:29:24,680 --> 00:29:27,500 these Diffie-Hellman public parameters? 705 00:29:27,500 --> 00:29:30,850 Well, we used Internet-wide scanning to find out. 706 00:29:30,850 --> 00:29:33,640 So, my group, we also made something called zmap, 707 00:29:33,640 --> 00:29:35,810 that I talked about here a couple of years ago, 708 00:29:35,810 --> 00:29:39,010 which lets us quickly probe everything on the Internet, 709 00:29:39,010 --> 00:29:42,210 and so we did this and tried to make 710 00:29:42,210 --> 00:29:44,480 connections to each HTTPS server 711 00:29:44,480 --> 00:29:46,850 in the public IPv4 address space, 712 00:29:46,850 --> 00:29:49,590 and found out what key exchange methods 713 00:29:49,590 --> 00:29:52,280 were supported and with what primes. 714 00:29:52,280 --> 00:29:56,120 And what we find is that 97% of hosts 715 00:29:56,120 --> 00:29:58,470 that support export-grade Diffie-Hellman 716 00:29:58,470 --> 00:30:01,130 use one of only 3 512-bit primes. 717 00:30:01,130 --> 00:30:02,930 They're that widely-shared. 718 00:30:02,930 --> 00:30:04,840 Why is this? Because those parameters 719 00:30:04,840 --> 00:30:06,720 are very often either hard-coded 720 00:30:06,720 --> 00:30:08,160 or encoded in standards 721 00:30:08,160 --> 00:30:10,040 that different people implement. 722 00:30:10,040 --> 00:30:11,680 The most common of these, 723 00:30:11,680 --> 00:30:15,100 used by 80% of hosts that support export-grade Diffie-Hellman, 724 00:30:15,100 --> 00:30:20,760 is a public parameter that's hardcoded into Apache 2.2. 725 00:30:20,760 --> 00:30:23,160 So, it's actually there, embedded in the source, 726 00:30:23,160 --> 00:30:26,100 you have to recompile Apache to change it. 727 00:30:26,100 --> 00:30:28,500 13% of hosts supported something, 728 00:30:28,500 --> 00:30:31,850 a second prime that has also 512 bits, 729 00:30:31,850 --> 00:30:34,770 that's hardcoded in mod_ssl, 730 00:30:34,770 --> 00:30:37,260 and the next most popular, 4%, 731 00:30:37,260 --> 00:30:40,050 was in the Sun JDK. 732 00:30:40,050 --> 00:30:43,270 Only 10 primes accounted for 99% 733 00:30:43,270 --> 00:30:45,270 of all the hosts we found in the public address space 734 00:30:45,270 --> 00:30:49,090 that supported export-grade Diffie-Hellman. 735 00:30:49,090 --> 00:30:54,370 So, if we would like to compromise these, 736 00:30:54,370 --> 00:30:56,900 well, Nadia just told you about 737 00:30:56,900 --> 00:31:01,870 how long it takes to use the number field sieve 738 00:31:01,870 --> 00:31:05,050 to break 512-bit discrete log, 739 00:31:05,050 --> 00:31:08,480 well, we actually went and did the precomputation 740 00:31:08,480 --> 00:31:13,140 for all 3 of these most widely used Diffie-Hellman primes, 741 00:31:13,140 --> 00:31:18,760 and our colleagues who make a tool called CADO-NFS 742 00:31:18,760 --> 00:31:22,180 where able to implement the code 743 00:31:22,180 --> 00:31:28,450 for that piece of the discrete log version of the number field sieve 744 00:31:28,450 --> 00:31:30,960 and they ran the algorithm on these primes 745 00:31:30,960 --> 00:31:34,080 on a cluster they just happened to have lying around, 746 00:31:34,080 --> 00:31:37,800 it took about a week of time on the cluster 747 00:31:37,800 --> 00:31:39,570 for each of these primes. 748 00:31:39,570 --> 00:31:41,980 After which, using an optimised version 749 00:31:41,980 --> 00:31:45,040 of the last portion of the number field sieve, 750 00:31:45,040 --> 00:31:47,530 it takes about 70 seconds for us to break 751 00:31:47,530 --> 00:31:49,470 any individual connection 752 00:31:49,470 --> 00:31:54,330 that uses any one of these 3 most popular primes. 753 00:31:54,330 --> 00:31:57,090 So, Logjam and our precomputations 754 00:31:57,090 --> 00:31:59,100 now allow us to break any connection 755 00:31:59,100 --> 00:32:04,670 to about 8% of the top million HTTPS sites from Alexa 756 00:32:04,670 --> 00:32:07,920 and when we came up with this attack, 757 00:32:07,920 --> 00:32:10,950 it worked in all modern browsers. 758 00:32:10,950 --> 00:32:12,530 So, mitigation! 759 00:32:12,530 --> 00:32:19,280 *applause* 760 00:32:19,280 --> 00:32:21,770 This is bad, everyone, this is the crypto 761 00:32:21,770 --> 00:32:24,740 all of us are using. 762 00:32:24,740 --> 00:32:26,560 So we do have some mitigations. 763 00:32:26,560 --> 00:32:28,340 This is the actual positive part, 764 00:32:28,340 --> 00:32:29,840 is that the browser makers have now 765 00:32:29,840 --> 00:32:32,900 started to increase the minimum strength 766 00:32:32,900 --> 00:32:34,860 of Diffie-Hellman they will accept. 767 00:32:34,860 --> 00:32:37,010 So IE, Chrome, and Firefox will reject 768 00:32:37,010 --> 00:32:38,750 primes less than 1024 bits 769 00:32:38,750 --> 00:32:41,200 and Safari less than 768. 770 00:32:41,200 --> 00:32:43,980 And the new draft of TLS 1.3 is including 771 00:32:43,980 --> 00:32:45,200 an anti-downgrade flag 772 00:32:45,200 --> 00:32:46,690 that will make it even harder 773 00:32:46,690 --> 00:32:49,750 for such attacks to take place in the future. 774 00:32:49,750 --> 00:32:52,140 Now back to Nadia. 775 00:32:52,140 --> 00:32:54,240 NH: So we promised in our abstract... 776 00:32:54,240 --> 00:32:59,600 *applause* 777 00:32:59,600 --> 00:33:02,190 ...that there would be a hands-on portion of this talk. 778 00:33:02,190 --> 00:33:03,570 So, you have a couple options, 779 00:33:03,570 --> 00:33:05,580 number 1 is, if you're really into this, 780 00:33:05,580 --> 00:33:08,230 you can do and download CADO-NFS yourselves, 781 00:33:08,230 --> 00:33:11,770 cado-nfs.gforge.inria.fr 782 00:33:11,770 --> 00:33:16,440 and, you know, run discrete log algorithms yourselves 783 00:33:16,440 --> 00:33:17,790 for any prime you wish 784 00:33:17,790 --> 00:33:20,030 and then you can compute arbitrary discrete logs. 785 00:33:20,030 --> 00:33:21,700 However, since we have already done 786 00:33:21,700 --> 00:33:22,820 some of the computations, 787 00:33:22,820 --> 00:33:25,200 we figured that we would make them available for you guys 788 00:33:25,200 --> 00:33:26,930 if you wanted to play with them. 789 00:33:26,930 --> 00:33:32,590 So... *applause* 790 00:33:32,590 --> 00:33:36,170 We have done so through the Twitter API, 791 00:33:36,170 --> 00:33:39,150 so we have a bot running on Twitter 792 00:33:39,150 --> 00:33:40,580 and if you would like to compute 793 00:33:40,580 --> 00:33:45,110 discrete logs for any of these widely-used parameters, 794 00:33:45,110 --> 00:33:48,240 this bot will do so for you. 795 00:33:48,240 --> 00:33:52,910 So here is the group generator and the primes in hexadecimal, 796 00:33:52,910 --> 00:33:56,910 for the 3 groups that we did the precomputation for. 797 00:33:56,910 --> 00:33:59,290 And if you wanted to test out, 798 00:33:59,290 --> 00:34:00,590 you would do something like this, 799 00:34:00,590 --> 00:34:01,810 so this using Sage, 800 00:34:01,810 --> 00:34:04,910 which is a Python-based open source mathematics package, 801 00:34:04,910 --> 00:34:06,760 that does a lot of algebra and number theory, 802 00:34:06,760 --> 00:34:08,290 if you like playing with the stuff, 803 00:34:08,290 --> 00:34:09,429 sage is super cool, 804 00:34:09,429 --> 00:34:15,500 so, I said, say, my prime m is this last value in hex there, 805 00:34:15,500 --> 00:34:16,860 the mod_ssl prime, 806 00:34:16,860 --> 00:34:23,780 then I take 2 and raise it to the 0x1337 power mod m, 807 00:34:23,780 --> 00:34:26,189 and then I print it out in hexadecimal, 808 00:34:26,189 --> 00:34:35,230 and I get this value, then I can copy-paste it into a tweet @DLogBot 809 00:34:35,230 --> 00:34:39,050 then some comp stuff happens on our back end, 810 00:34:39,050 --> 00:34:40,889 this is running on one of the machines in my lab, 811 00:34:40,889 --> 00:34:43,530 so please don't break it, 812 00:34:43,530 --> 00:34:46,550 and after a minute or two, 813 00:34:46,550 --> 00:34:49,019 you should get back an answer. 814 00:34:49,019 --> 00:34:58,310 *applause* 815 00:34:58,310 --> 00:35:01,520 So, there's a queue, only one thing can run at a time, 816 00:35:01,520 --> 00:35:02,990 median time is 70 seconds, 817 00:35:02,990 --> 00:35:06,260 it can vary between 30 seconds and 3 minutes, 818 00:35:06,260 --> 00:35:08,830 so, you know, if it doesn't respond to you 819 00:35:08,830 --> 00:35:12,470 within like, you know, an hour or something, 820 00:35:12,470 --> 00:35:15,760 then send us a ping and we'll see if it's still running. 821 00:35:15,760 --> 00:35:18,300 Okay. So, have fun. 822 00:35:18,300 --> 00:35:21,480 Please don't actually use this for malice. 823 00:35:21,480 --> 00:35:27,540 *applause* 824 00:35:27,540 --> 00:35:30,230 We already have some satisfied customers. 825 00:35:30,230 --> 00:35:33,970 *laughter* 826 00:35:33,970 --> 00:35:35,790 AH: Alright, so we promised there were 827 00:35:35,790 --> 00:35:39,400 two exploits that have to do with weakened Diffie-Hellman, 828 00:35:39,400 --> 00:35:41,750 and the first, Logjam, right, anyone can 829 00:35:41,750 --> 00:35:43,410 use backdoors from the 90s 830 00:35:43,410 --> 00:35:45,480 to pwn modern browsers, 831 00:35:45,480 --> 00:35:49,200 well, the second one is a little bit more widespread. 832 00:35:49,200 --> 00:35:50,810 So, we're going to talk about 833 00:35:50,810 --> 00:35:53,330 how Diffie-Hellman weaknesses 834 00:35:53,330 --> 00:35:56,150 can be used for mass surveillance. 835 00:35:56,150 --> 00:35:58,280 We believe that governments can probably 836 00:35:58,280 --> 00:36:03,280 already right now, exploit 1024-bit discrete log 837 00:36:03,280 --> 00:36:08,050 to break Diffie-Hellman for wide-scale passive decryption 838 00:36:08,050 --> 00:36:10,850 of Internet communications. 839 00:36:10,850 --> 00:36:13,970 So, is breaking 1024-bit Diffie-Hellman 840 00:36:13,970 --> 00:36:15,390 within the reach of governments, 841 00:36:15,390 --> 00:36:17,970 let's look back at these numbers quickly. 842 00:36:17,970 --> 00:36:22,300 So we can see that for 512-bit RSA and Diffie-Hellman, 843 00:36:22,300 --> 00:36:26,090 they're both really in reach of basically any effort right now, 844 00:36:26,090 --> 00:36:27,670 any one of you can probably, 845 00:36:27,670 --> 00:36:30,210 most of the resources to do this. 846 00:36:30,210 --> 00:36:34,970 For 768-bit RSA or Diffie-Hellman, 847 00:36:34,970 --> 00:36:37,460 well, we think this is now in the reach 848 00:36:37,460 --> 00:36:41,330 of a concerted academic effort. 849 00:36:41,330 --> 00:36:44,820 For 1024, it's a little bit more complicated, 850 00:36:44,820 --> 00:36:46,710 because the number field sieve algorithm 851 00:36:46,710 --> 00:36:48,090 is complicated enough that even 852 00:36:48,090 --> 00:36:52,500 making estimates of the runtime at this size and larger 853 00:36:52,500 --> 00:36:54,690 is very, very complicated 854 00:36:54,690 --> 00:36:58,200 and having a high-confidence estimate is difficult. 855 00:36:58,200 --> 00:37:01,260 But we've tried to do the math conservatively, 856 00:37:01,260 --> 00:37:03,490 and we believe that a conservative estimate, 857 00:37:03,490 --> 00:37:05,920 at least for 1024-bit Diffie-Hellman 858 00:37:05,920 --> 00:37:08,200 is to break, to do those precomputations 859 00:37:08,200 --> 00:37:10,630 for a single prime p, 860 00:37:10,630 --> 00:37:13,480 would take about 45 million core-years. 861 00:37:13,480 --> 00:37:18,190 Now 45 million core-years sounds like a hell of a lot. 862 00:37:18,190 --> 00:37:20,520 But, when you start to think about it, 863 00:37:20,520 --> 00:37:22,640 if you're going to do an effort that large, 864 00:37:22,640 --> 00:37:26,050 there are some optimisations you could start doing, 865 00:37:26,050 --> 00:37:28,920 and, for instance, maybe instead of 866 00:37:28,920 --> 00:37:31,690 running this on general-purpose PCs, 867 00:37:31,690 --> 00:37:33,040 like these estimates show, 868 00:37:33,040 --> 00:37:35,140 if you're going to do an effort on this scale, 869 00:37:35,140 --> 00:37:37,560 maybe you're going to tape out some chips, 870 00:37:37,560 --> 00:37:39,800 maybe you're going to use custom hardware. 871 00:37:39,800 --> 00:37:42,520 And if we do the math and look at what kind of gains 872 00:37:42,520 --> 00:37:44,380 we can get from custom hardware 873 00:37:44,380 --> 00:37:47,840 in other applications that are similar to this, 874 00:37:47,840 --> 00:37:49,320 we estimate that we can get 875 00:37:49,320 --> 00:37:51,890 maybe a speedup of 80 times 876 00:37:51,890 --> 00:37:54,160 just by doing it in custom hardware. 877 00:37:54,160 --> 00:37:57,450 Okay, and then we ask what's that's going to cost, 878 00:37:57,450 --> 00:38:00,670 well, we estimate that for... 879 00:38:00,670 --> 00:38:02,080 to build a machine that could break 880 00:38:02,080 --> 00:38:07,610 one 1024-bit p, precompute for one 1024-bit p every year, 881 00:38:07,610 --> 00:38:09,070 would cost somewhere in the neighbourhood 882 00:38:09,070 --> 00:38:11,390 of low hundreds of millions of dollars, 883 00:38:11,390 --> 00:38:12,810 in a one-time investment. 884 00:38:12,810 --> 00:38:14,820 As a result of this, you can churn out 885 00:38:14,820 --> 00:38:16,630 precomputations once a year 886 00:38:16,630 --> 00:38:19,410 that will let you break efficiently 887 00:38:19,410 --> 00:38:22,600 every connection that uses that p. 888 00:38:22,600 --> 00:38:24,630 Now, individual logs then are going to be 889 00:38:24,630 --> 00:38:26,230 close to real-time, and in fact you can 890 00:38:26,230 --> 00:38:28,270 re-use much of the same hardware 891 00:38:28,270 --> 00:38:32,370 to do the computations for individual logs very quickly. 892 00:38:32,370 --> 00:38:34,590 So, um, oh shit. 893 00:38:34,590 --> 00:38:37,550 This is what the estimates look like. 894 00:38:37,550 --> 00:38:44,050 Now is NSA actually doing this? 895 00:38:44,050 --> 00:38:45,030 NH: This is where we get into 896 00:38:45,030 --> 00:38:47,730 the conspiracy theories. 897 00:38:47,730 --> 00:38:52,720 *applause* 898 00:38:52,720 --> 00:38:55,010 So, there have been rumours flying around 899 00:38:55,010 --> 00:38:56,930 for many years, I mean for decades, really, 900 00:38:56,930 --> 00:38:59,720 but sort of credible rumours for many years, 901 00:38:59,720 --> 00:39:02,810 of some large cryptanalytic breakthrough 902 00:39:02,810 --> 00:39:04,130 that the NSA made. 903 00:39:04,130 --> 00:39:05,890 So here's an article from James Bamford, 904 00:39:05,890 --> 00:39:09,310 one of the, you know, world experts in open ??? 905 00:39:09,310 --> 00:39:11,350 of what the NSA's activities are 906 00:39:11,350 --> 00:39:13,820 and he wrote an article in 2012 907 00:39:13,820 --> 00:39:15,530 saying very clearly that he had talked 908 00:39:15,530 --> 00:39:17,290 to multiple government officials 909 00:39:17,290 --> 00:39:19,980 who said that the NSA made some enormous breakthrough 910 00:39:19,980 --> 00:39:21,260 several years ago. 911 00:39:21,260 --> 00:39:22,770 Everybody's a target, 912 00:39:22,770 --> 00:39:24,730 everybody with communication is a target, 913 00:39:24,730 --> 00:39:25,960 and this computing breakthrough 914 00:39:25,960 --> 00:39:27,320 is going to give them the ability 915 00:39:27,320 --> 00:39:29,480 to crack current public encryption. 916 00:39:29,480 --> 00:39:31,960 And it was so secret that no oversight, 917 00:39:31,960 --> 00:39:35,150 anybody had sort of access to the details of it. 918 00:39:35,150 --> 00:39:38,770 But whatever it was, it was major and massive. 919 00:39:38,770 --> 00:39:40,250 Of course, you know, after we saw this, 920 00:39:40,250 --> 00:39:41,530 we said, oh my god, you know, 921 00:39:41,530 --> 00:39:42,470 what could it possibly be, 922 00:39:42,470 --> 00:39:44,370 are they breaking RSA? 923 00:39:44,370 --> 00:39:46,090 Bamford actually goes on in this article 924 00:39:46,090 --> 00:39:48,960 to speculate that it's something about AES, 925 00:39:48,960 --> 00:39:51,170 which at least to my mind seems less likely 926 00:39:51,170 --> 00:39:54,510 than some kind of major public key breakthrough. 927 00:39:54,510 --> 00:39:56,480 So clearly we have sort of these rumours 928 00:39:56,480 --> 00:40:02,200 of large breakthroughs by the NSA's tens of thousands of mathematicians. 929 00:40:02,200 --> 00:40:04,980 Simultaneously, we can say, you know, 930 00:40:04,980 --> 00:40:07,910 we know the NSA is clearly interested in cryptanalysis, 931 00:40:07,910 --> 00:40:11,390 is cryptanalysis on the scale of hundreds of millions of dollars 932 00:40:11,390 --> 00:40:13,630 within their reach? 933 00:40:13,630 --> 00:40:17,260 The answer, thanks to Snowden, is yes. 934 00:40:17,260 --> 00:40:18,920 We have some of their budgets 935 00:40:18,920 --> 00:40:21,700 and they spend billions of dollars a year 936 00:40:21,700 --> 00:40:23,650 on computer network operations, 937 00:40:23,650 --> 00:40:25,560 they spend hundred of millions of dollars 938 00:40:25,560 --> 00:40:28,110 on cryptanalytic IT systems, 939 00:40:28,110 --> 00:40:31,490 cybercryptanalysis, exploitation solutions, 940 00:40:31,490 --> 00:40:33,980 in fact, a couple years ago there was even 941 00:40:33,980 --> 00:40:41,830 an increase of hundreds of millions of dollars in their budget for cryptanalysis. 942 00:40:41,830 --> 00:40:42,950 Interesting. 943 00:40:42,950 --> 00:40:45,360 So, a hundred million dollars of special-purpose hardware 944 00:40:45,360 --> 00:40:51,880 is certainly within range of a government the size of ours. 945 00:40:51,880 --> 00:40:53,630 Additionally, we can ask, 946 00:40:53,630 --> 00:40:55,860 what would the impact of doing one of 947 00:40:55,860 --> 00:40:57,600 these single precomputations 948 00:40:57,600 --> 00:41:01,670 for a discrete log for a single prime would be, 949 00:41:01,670 --> 00:41:04,590 and the answer is actually surprisingly large. 950 00:41:04,590 --> 00:41:06,150 So if you did this precomputation 951 00:41:06,150 --> 00:41:08,750 for a single 1024-bit prime, 952 00:41:08,750 --> 00:41:10,619 that would allow passive decryption 953 00:41:10,619 --> 00:41:13,290 of connections to 66% of VPN servers 954 00:41:13,290 --> 00:41:16,020 and 26% of SSH servers. 955 00:41:16,020 --> 00:41:18,180 This is from Internet-wide scanning, 956 00:41:18,180 --> 00:41:19,520 we connected to all of these 957 00:41:19,520 --> 00:41:21,380 and we said "we would like to speak 958 00:41:21,380 --> 00:41:24,120 Diffie-Hellman with you, what parameters do you prefer?" 959 00:41:24,120 --> 00:41:26,780 and these are the servers that preferred 960 00:41:26,780 --> 00:41:32,060 a single 1024-bit prime over every other parameter in key size. 961 00:41:32,060 --> 00:41:33,770 A second 1024-bit prime would allow 962 00:41:33,770 --> 00:41:38,630 passive decryption for 18% of the top million HTTPS domains. 963 00:41:38,630 --> 00:41:40,080 These are domains that prefer 964 00:41:40,080 --> 00:41:45,670 to speak Diffie-Hellman with this fixed prime. 965 00:41:45,670 --> 00:41:47,720 And, the final piece of evidence 966 00:41:47,720 --> 00:41:49,840 for something like this being within range 967 00:41:49,840 --> 00:41:52,280 and at least being worth worrying about 968 00:41:52,280 --> 00:41:57,630 is actually some of the slides that were release last year, 969 00:41:57,630 --> 00:41:59,050 by der Spiegel, 970 00:41:59,050 --> 00:42:01,780 and in particular they have a large amount of detail 971 00:42:01,780 --> 00:42:06,530 about passive decryptions of VPN traffic. 972 00:42:06,530 --> 00:42:08,230 So here's an example, 973 00:42:08,230 --> 00:42:09,510 it is clear from the slides that 974 00:42:09,510 --> 00:42:10,580 whatever the NSA is doing, 975 00:42:10,580 --> 00:42:12,420 they have the ability to passively decrypt 976 00:42:12,420 --> 00:42:15,280 VPN connections on a large scale. 977 00:42:15,280 --> 00:42:18,900 And they're very happy about it. 978 00:42:18,900 --> 00:42:21,480 I think this is my favourite Snowden slide ever. 979 00:42:21,480 --> 00:42:22,620 *laughter* 980 00:42:22,620 --> 00:42:25,010 I feel this way when I decrypt things too. 981 00:42:25,010 --> 00:42:27,089 *laughter* 982 00:42:27,089 --> 00:42:29,580 So, if we take a look at what, 983 00:42:29,580 --> 00:42:33,540 and these slides are specifically talking about IPsec VPNs, 984 00:42:33,540 --> 00:42:39,100 if we take a look at what the key exchange looks like for IPsec VPNs, 985 00:42:39,100 --> 00:42:41,260 what happens is, we have two hosts 986 00:42:41,260 --> 00:42:45,400 who want to make a VPN connection with each other, 987 00:42:45,400 --> 00:42:50,950 the key exchange actually uses a fixed set of parameters 988 00:42:50,950 --> 00:42:54,080 from a small list of possibilities, 989 00:42:54,080 --> 00:42:55,619 and so Alice and Bob will negotiate 990 00:42:55,619 --> 00:42:58,040 which parameters they're going to use from this list, 991 00:42:58,040 --> 00:43:00,050 and then they will do a Diffie-Hellman key exchange, 992 00:43:00,050 --> 00:43:03,240 from that they will have a shared secret, g^ab, 993 00:43:03,240 --> 00:43:05,550 and then they, in the most commonly used mode, 994 00:43:05,550 --> 00:43:07,140 they also have some pre-shared key, 995 00:43:07,140 --> 00:43:09,400 like a password that has been shared 996 00:43:09,400 --> 00:43:11,250 over some other channel. 997 00:43:11,250 --> 00:43:14,010 And that Diffie-Hellman secret 998 00:43:14,010 --> 00:43:16,020 that was negotiated together with the pre-shared key 999 00:43:16,020 --> 00:43:19,370 or mixed together to generate the session key. 1000 00:43:19,370 --> 00:43:22,300 So, if somebody wanted to 1001 00:43:22,300 --> 00:43:24,330 break a connection of this type, 1002 00:43:24,330 --> 00:43:26,080 one option would be to, say, 1003 00:43:26,080 --> 00:43:28,010 steal the pre-shared key through some other mechanism 1004 00:43:28,010 --> 00:43:29,380 and then break Diffie-Hellman. 1005 00:43:29,380 --> 00:43:32,559 That would be a possibility. 1006 00:43:32,559 --> 00:43:35,500 So, if we look what the NSA's requirements are 1007 00:43:35,500 --> 00:43:38,920 for their mass-scale decryption efforts, 1008 00:43:38,920 --> 00:43:42,369 they require finding out what the pre-shared key is, 1009 00:43:42,369 --> 00:43:44,990 getting both sides of the connection, 1010 00:43:44,990 --> 00:43:47,690 getting both the asymmetric key exchange 1011 00:43:47,690 --> 00:43:50,350 and the symmetrically encrypted data, 1012 00:43:50,350 --> 00:43:52,589 and then having some metadata. 1013 00:43:52,589 --> 00:43:56,240 These are the requirements for them to get decryption. 1014 00:43:56,240 --> 00:43:58,210 And we can also take a closer look 1015 00:43:58,210 --> 00:44:04,260 at what their decryption flow actually looks like, 1016 00:44:04,260 --> 00:44:06,290 this is somewhat complicated, 1017 00:44:06,290 --> 00:44:07,850 but in this diagram, 1018 00:44:07,850 --> 00:44:10,840 so they're getting the IK exchange, 1019 00:44:10,840 --> 00:44:12,990 and the symmetric data, 1020 00:44:12,990 --> 00:44:17,130 they're sending it into one system that they have, 1021 00:44:17,130 --> 00:44:19,230 they're sending the IKE messages through 1022 00:44:19,230 --> 00:44:21,880 out to some high-performance computing resources, 1023 00:44:21,880 --> 00:44:23,619 and then they get sent back with 1024 00:44:23,619 --> 00:44:28,690 some data from stored databases of information 1025 00:44:28,690 --> 00:44:32,910 that returns the actual decrypted data. 1026 00:44:32,910 --> 00:44:34,840 So that's what the decryption flow looks like. 1027 00:44:34,840 --> 00:44:37,130 We don't have any details of the cryptanalysis, 1028 00:44:37,130 --> 00:44:39,480 but we have details from the sysadmin's perspective 1029 00:44:39,480 --> 00:44:43,190 of how the systems that do the cryptanalysis 1030 00:44:43,190 --> 00:44:44,670 are hooked together. 1031 00:44:44,670 --> 00:44:46,000 And they're doing something 1032 00:44:46,000 --> 00:44:48,280 that requires high-performance computing, 1033 00:44:48,280 --> 00:44:49,700 that takes in key exchanges 1034 00:44:49,700 --> 00:44:54,040 and hands out decrypted data. 1035 00:44:54,040 --> 00:44:59,740 So, we can line up sort of the NSA's on-demand IKE decryption 1036 00:44:59,740 --> 00:45:03,710 with what a discrete log decryption would actually look like, 1037 00:45:03,710 --> 00:45:05,619 and they're very close, 1038 00:45:05,619 --> 00:45:07,640 so they would both require the pre-shared key, 1039 00:45:07,640 --> 00:45:09,490 both sides of the handshake, 1040 00:45:09,490 --> 00:45:12,440 both the handshake and the symmetric data, 1041 00:45:12,440 --> 00:45:13,450 and they would send off the data 1042 00:45:13,450 --> 00:45:16,090 to high-performance computing. 1043 00:45:16,090 --> 00:45:17,990 So in the same set of slides, 1044 00:45:17,990 --> 00:45:20,770 they also discuss targeted implants 1045 00:45:20,770 --> 00:45:23,040 against particular implementations, 1046 00:45:23,040 --> 00:45:26,890 if you were going to design a backdoor to make your life easy, 1047 00:45:26,890 --> 00:45:30,360 you would have fewer requirements than this. 1048 00:45:30,360 --> 00:45:31,320 Potentially. 1049 00:45:31,320 --> 00:45:33,090 There are many kinds of backdoors that you could design, 1050 00:45:33,090 --> 00:45:35,190 but if you were being clever about it, 1051 00:45:35,190 --> 00:45:38,090 you might try to make it a little bit easier on yourself 1052 00:45:38,090 --> 00:45:41,100 to decrypt the mess. 1053 00:45:41,100 --> 00:45:43,750 So I will let Alex finish with this. 1054 00:45:43,750 --> 00:45:51,090 *applause* 1055 00:45:51,090 --> 00:45:53,890 So to wrap up, 1056 00:45:53,890 --> 00:45:55,520 what we've seen today 1057 00:45:55,520 --> 00:46:00,150 through the cryptanalysis of Diffie-Hellman 1058 00:46:00,150 --> 00:46:05,330 is probably a mass surveillance dream. 1059 00:46:05,330 --> 00:46:08,180 The algorithms that we've talked about 1060 00:46:08,180 --> 00:46:11,400 would let a government with sufficient resources 1061 00:46:11,400 --> 00:46:15,010 to invest in these precomputation attacks 1062 00:46:15,010 --> 00:46:18,840 break connections on an almost unheard-of scale, 1063 00:46:18,840 --> 00:46:23,950 across almost every widely-used crypto protocol on the Internet. 1064 00:46:23,950 --> 00:46:25,530 Here are some numbers again, 1065 00:46:25,530 --> 00:46:28,490 for HTTPS, the top million sites, 1066 00:46:28,490 --> 00:46:29,960 we're looking at a device like 1067 00:46:29,960 --> 00:46:32,480 the ones we hypothesised 1068 00:46:32,480 --> 00:46:38,150 breaking connections to maybe 56% of them passively. 1069 00:46:38,150 --> 00:46:42,900 For IKE, for Internet key exchange v1 and v2, 1070 00:46:42,900 --> 00:46:46,090 we're looking at in the 60%s of servers 1071 00:46:46,090 --> 00:46:48,240 are potentially compromisable 1072 00:46:48,240 --> 00:46:50,750 using this same hardware. 1073 00:46:50,750 --> 00:47:00,290 For SSH, for IMAP with secure encrypted connections, for SMTP with STARTTLS, 1074 00:47:00,290 --> 00:47:02,259 the encrypted mail transports, 1075 00:47:02,259 --> 00:47:05,570 all of these protocols are potentially jeopardised 1076 00:47:05,570 --> 00:47:07,390 by the same kind of attack, 1077 00:47:07,390 --> 00:47:09,490 because everyone fundamentally, 1078 00:47:09,490 --> 00:47:11,110 so many people fundamentally 1079 00:47:11,110 --> 00:47:14,400 rely on the same underlying cryptography, 1080 00:47:14,400 --> 00:47:17,050 often with the very same public parameters 1081 00:47:17,050 --> 00:47:19,560 that are so widely shared. 1082 00:47:19,560 --> 00:47:21,850 So what can we do about this? 1083 00:47:21,850 --> 00:47:24,820 So first, let's go back to the Logjam attack again, 1084 00:47:24,820 --> 00:47:27,490 using 90s-era backdoored crypto 1085 00:47:27,490 --> 00:47:30,930 that lets any of us break connections to modern browsers. 1086 00:47:30,930 --> 00:47:32,760 Luckily, browsers have already started 1087 00:47:32,760 --> 00:47:34,490 to mitigate this, as I said, 1088 00:47:34,490 --> 00:47:35,990 by increasing the minimum strength 1089 00:47:35,990 --> 00:47:37,470 of Diffie-Hellman they support, 1090 00:47:37,470 --> 00:47:39,650 although there's still a way to go there, 1091 00:47:39,650 --> 00:47:43,350 since they're all still accepting 1024-bit key exchange. 1092 00:47:43,350 --> 00:47:45,760 Our biggest recommendation under here though, 1093 00:47:45,760 --> 00:47:49,160 I think the lesson is: don't backdoor crypto! 1094 00:47:49,160 --> 00:47:50,810 Right, because the backdoored crypto 1095 00:47:50,810 --> 00:47:52,840 of 20 years ago is now coming back 1096 00:47:52,840 --> 00:47:54,510 to bite everyone. 1097 00:47:54,510 --> 00:47:59,440 *applause* 1098 00:47:59,440 --> 00:48:01,630 And then, we have the second attack, 1099 00:48:01,630 --> 00:48:03,510 the 1024-bit case that enables 1100 00:48:03,510 --> 00:48:05,220 so much mass surveillance. 1101 00:48:05,220 --> 00:48:06,970 Well, to get around this, 1102 00:48:06,970 --> 00:48:09,570 we're going to have to do some upgrades. 1103 00:48:09,570 --> 00:48:11,440 Probably the easiest thing to do, 1104 00:48:11,440 --> 00:48:12,859 and the thing that almost 1105 00:48:12,859 --> 00:48:15,420 every cryptographer that we talked to 1106 00:48:15,420 --> 00:48:16,590 recommends now, 1107 00:48:16,590 --> 00:48:18,690 is to move to elliptic-curve crypto. 1108 00:48:18,690 --> 00:48:19,950 Yes, there's been talk 1109 00:48:19,950 --> 00:48:22,530 about whether the specific NIST curves 1110 00:48:22,530 --> 00:48:25,790 may have been backdoored by NSA, 1111 00:48:25,790 --> 00:48:27,470 but by and large, we think that 1112 00:48:27,470 --> 00:48:29,590 elliptic curve is the most sound choice 1113 00:48:29,590 --> 00:48:31,550 we have for now. 1114 00:48:31,550 --> 00:48:33,119 Now if elliptic curve isn't an option, 1115 00:48:33,119 --> 00:48:35,490 and there's technical reasons why it might not be, 1116 00:48:35,490 --> 00:48:38,570 at the very least use a Diffie-Hellman prime 1117 00:48:38,570 --> 00:48:41,410 that's 2048 bits or longer. 1118 00:48:41,410 --> 00:48:43,480 If even that isn't an option, 1119 00:48:43,480 --> 00:48:45,970 you're using legacy systems for some reason, 1120 00:48:45,970 --> 00:48:49,610 well, or Java yes, thanks, 1121 00:48:49,610 --> 00:48:52,709 if there's anyone there who works for Sun, 1122 00:48:52,709 --> 00:48:58,340 please, please tell them to fix the crypto in Java! 1123 00:48:58,340 --> 00:49:04,920 *applause* 1124 00:49:04,920 --> 00:49:06,740 But if that's not an option, 1125 00:49:06,740 --> 00:49:07,660 if that's not an option, 1126 00:49:07,660 --> 00:49:09,359 the fallback is you can generate, 1127 00:49:09,359 --> 00:49:13,890 at least generate your own 1024-bit prime. 1128 00:49:13,890 --> 00:49:17,000 Mind you, there various tricks that you have to make sure you do 1129 00:49:17,000 --> 00:49:20,310 when generating a prime, it must be a safe prime, 1130 00:49:20,310 --> 00:49:22,450 but there are implementations of doing this, 1131 00:49:22,450 --> 00:49:27,100 so it's not exactly free to generate your own 1024-bit prime, 1132 00:49:27,100 --> 00:49:28,300 but it's inexpensive, 1133 00:49:28,300 --> 00:49:29,810 and if you have no other option, 1134 00:49:29,810 --> 00:49:32,950 at least so that this large government adversary 1135 00:49:32,950 --> 00:49:35,000 has to spend a lot of precomputation, 1136 00:49:35,000 --> 00:49:37,990 a year perhaps, targeting you individually, 1137 00:49:37,990 --> 00:49:40,330 and they can't just get this for free. 1138 00:49:40,330 --> 00:49:43,360 Alright, so, that is our talk for tonight, 1139 00:49:43,360 --> 00:49:45,950 we're saving a lot of time for questions, 1140 00:49:45,950 --> 00:49:49,040 thank you all very very much. 1141 00:49:49,040 --> 00:50:00,410 *applause* 1142 00:50:00,410 --> 00:50:05,300 Herald: Nadia. Nadia and Alex, thank you very much. 1143 00:50:05,300 --> 00:50:07,350 We installed some microphones here in the room, 1144 00:50:07,350 --> 00:50:09,290 so please queue up, but first, 1145 00:50:09,290 --> 00:50:11,890 signal angel, do we have some questions from the net? 1146 00:50:11,890 --> 00:50:14,810 Signal Angel: Yes, we have a lot of questions. 1147 00:50:14,810 --> 00:50:16,160 First question is, 1148 00:50:16,160 --> 00:50:17,780 do you think it's possible that the NSA 1149 00:50:17,780 --> 00:50:19,890 uses quantum Shor factorisation 1150 00:50:19,890 --> 00:50:24,790 for 1024 or bigger keys already? 1151 00:50:24,790 --> 00:50:27,520 NH: I would believe it is much more likely 1152 00:50:27,520 --> 00:50:29,720 that they're using classical cryptanalysis 1153 00:50:29,720 --> 00:50:31,480 for 1024-bit keys than than they have 1154 00:50:31,480 --> 00:50:34,770 a quantum computer that nobody has heard about. 1155 00:50:34,770 --> 00:50:37,230 Herald: And another one? 1156 00:50:37,230 --> 00:50:38,760 Signal Angel: Another one... Is it thinkable 1157 00:50:38,760 --> 00:50:41,490 that the NSA solved the P=NP problem 1158 00:50:41,490 --> 00:50:43,210 but keeps quiet? 1159 00:50:43,210 --> 00:50:45,780 *laughter* 1160 00:50:45,780 --> 00:50:47,670 AH: Probably not, but if they have, 1161 00:50:47,670 --> 00:50:50,539 yes, I think they'd want to keep quiet about it. 1162 00:50:50,539 --> 00:50:52,000 NH: I hope they would tell us! 1163 00:50:52,000 --> 00:50:53,570 AH: I hope they would tell us too, 1164 00:50:53,570 --> 00:50:56,010 but I doubt it. 1165 00:50:56,010 --> 00:50:59,930 Herald: Okay, and over to number 1, please. 1166 00:50:59,930 --> 00:51:01,540 Q: Two questions. 1167 00:51:01,540 --> 00:51:05,600 First, is it reasonable to think that, 1168 00:51:05,600 --> 00:51:09,200 is it possible they are attacking individual RSA keys, 1169 00:51:09,200 --> 00:51:11,320 that they can fetch individual RSA keys 1170 00:51:11,320 --> 00:51:13,530 in about a week with custom hardware, 1171 00:51:13,530 --> 00:51:17,580 and two, NSA Suite B came out 2005 1172 00:51:17,580 --> 00:51:19,160 and they don't use Diffie-Hellman, 1173 00:51:19,160 --> 00:51:22,670 so NSA themselves, they told us in 2005, 1174 00:51:22,670 --> 00:51:24,730 "we won't use Diffie-Hellman", 1175 00:51:24,730 --> 00:51:26,570 so is it reasonable that, 1176 00:51:26,570 --> 00:51:28,400 when they changed the requirement 1177 00:51:28,400 --> 00:51:30,730 for top secret, we should follow? 1178 00:51:30,730 --> 00:51:33,470 AH: Well, to the first part of your question, 1179 00:51:33,470 --> 00:51:35,859 about whether they're factoring RSA, 1180 00:51:35,859 --> 00:51:38,580 I think the answer for 1024, 1181 00:51:38,580 --> 00:51:40,600 is very likely, yes they are, 1182 00:51:40,600 --> 00:51:42,320 for high-value targets. 1183 00:51:42,320 --> 00:51:45,020 So if you're a major website at least 1184 00:51:45,020 --> 00:51:48,090 and you're using a 1024-bit RSA key, 1185 00:51:48,090 --> 00:51:53,000 well, it's long past time to change to a higher strength. 1186 00:51:53,000 --> 00:51:56,480 NH: If the NSA has not factored a 1024-bit key, 1187 00:51:56,480 --> 00:51:58,050 I'm going to be very disappointed, 1188 00:51:58,050 --> 00:52:00,930 I'm going to ask where my tax dollars are going. 1189 00:52:00,930 --> 00:52:07,370 *laughter, applause* 1190 00:52:07,370 --> 00:52:09,440 And also I think actually, 1191 00:52:09,440 --> 00:52:11,000 the point of sort of watching 1192 00:52:11,000 --> 00:52:12,830 what the defensive side of the NSA 1193 00:52:12,830 --> 00:52:15,200 is advocating in terms of recommendations 1194 00:52:15,200 --> 00:52:17,180 is actually a wise thing to do, 1195 00:52:17,180 --> 00:52:20,160 because as far as we know, 1196 00:52:20,160 --> 00:52:22,140 at least the public recommendations 1197 00:52:22,140 --> 00:52:26,450 defensively should... I mean, 1198 00:52:26,450 --> 00:52:27,580 making recommendations for people 1199 00:52:27,580 --> 00:52:31,000 who are building systems that are going to be handling classified data, 1200 00:52:31,000 --> 00:52:32,780 so they should be solid recommendations 1201 00:52:32,780 --> 00:52:33,960 as far as we know. 1202 00:52:33,960 --> 00:52:35,280 AH: What the NSA has told me 1203 00:52:35,280 --> 00:52:37,580 about those recommendations, by the way, 1204 00:52:37,580 --> 00:52:40,280 is that as long as you follow them exactly, 1205 00:52:40,280 --> 00:52:41,609 you're going to be okay, 1206 00:52:41,609 --> 00:52:44,160 but if you deviate in any small way whatsoever, 1207 00:52:44,160 --> 00:52:46,960 then they make no guarantees whatsoever. 1208 00:52:46,960 --> 00:52:50,040 So, think about what that might mean 1209 00:52:50,040 --> 00:52:52,220 in terms of your implementation 1210 00:52:52,220 --> 00:52:55,630 the next time you read through those particular recommendations 1211 00:52:55,630 --> 00:52:58,470 that they make. 1212 00:52:58,470 --> 00:53:01,280 Herald: Okay. Then we hop over to microphone 3, please. 1213 00:53:01,280 --> 00:53:03,549 Q: So, for the moment, is 1214 00:53:03,549 --> 00:53:07,380 elliptic-curve-based Diffie-Hellman secure? 1215 00:53:07,380 --> 00:53:09,860 NH: I hope so. 1216 00:53:09,860 --> 00:53:13,650 AH: It doesn't suffer from the same shape of attack 1217 00:53:13,650 --> 00:53:14,900 that we've described here. 1218 00:53:14,900 --> 00:53:16,770 As far as we know, there's not a way 1219 00:53:16,770 --> 00:53:19,020 to do this same kind of precomputation 1220 00:53:19,020 --> 00:53:20,710 for elliptic-curve Diffie-Hellman. 1221 00:53:20,710 --> 00:53:22,530 NH: So what we didn't mention in the talk 1222 00:53:22,530 --> 00:53:24,630 is, so, one of the reasons that 1223 00:53:24,630 --> 00:53:27,300 elliptic curve keys are so much shorter 1224 00:53:27,300 --> 00:53:30,730 than, say, finite-field Diffie-Hellman or RSA 1225 00:53:30,730 --> 00:53:35,350 is because we have this superpowerful index calculus 1226 00:53:35,350 --> 00:53:37,410 number field sieve-type algorithms 1227 00:53:37,410 --> 00:53:41,270 for factoring and for discrete log over finite fields, 1228 00:53:41,270 --> 00:53:43,040 and those don't seem, 1229 00:53:43,040 --> 00:53:44,310 we don't actually have equivalents 1230 00:53:44,310 --> 00:53:47,890 of those algorithms for properly generated elliptic curves. 1231 00:53:47,890 --> 00:53:50,580 So, that's why those key sizes are shorter 1232 00:53:50,580 --> 00:53:54,020 and that's why we think they seem to be more secure. 1233 00:53:54,020 --> 00:53:57,109 Herald: Then we take another one from microphone 3, please. 1234 00:53:57,109 --> 00:54:01,310 Q: Yes, you said that when doing the precomputations 1235 00:54:01,310 --> 00:54:04,820 for commonly-used primes, 1236 00:54:04,820 --> 00:54:08,330 you can reduce the effort you have to put 1237 00:54:08,330 --> 00:54:11,280 in a single connection to about 70 seconds. 1238 00:54:11,280 --> 00:54:12,830 How is that usable? 1239 00:54:12,830 --> 00:54:15,850 If my TLS handshake is delayed 70 seconds, 1240 00:54:15,850 --> 00:54:18,420 I already ran away. 1241 00:54:18,420 --> 00:54:20,480 AH: Ah! So we refer you to the paper 1242 00:54:20,480 --> 00:54:22,090 for the full answer to that, 1243 00:54:22,090 --> 00:54:23,680 but it turns out there's a bunch of tricks 1244 00:54:23,680 --> 00:54:28,520 that you can do to keep a session handshake open 1245 00:54:28,520 --> 00:54:30,210 for at least 70 seconds. 1246 00:54:30,210 --> 00:54:32,240 So, this may not be what you want to do 1247 00:54:32,240 --> 00:54:35,330 to the connection, say, in a web browser 1248 00:54:35,330 --> 00:54:37,770 that's loading index.html, 1249 00:54:37,770 --> 00:54:39,530 but whichever one is loading, say, 1250 00:54:39,530 --> 00:54:44,619 the, I don't know, the 1-pixel tracking image in the background, 1251 00:54:44,619 --> 00:54:46,349 that nobody sees, 1252 00:54:46,349 --> 00:54:48,710 which is also getting the same session cookie, 1253 00:54:48,710 --> 00:54:51,060 that one you can hold open for 70 seconds 1254 00:54:51,060 --> 00:54:52,840 without the user noticing. 1255 00:54:52,840 --> 00:54:54,070 So what we've been able to do 1256 00:54:54,070 --> 00:54:56,369 is show a variety of ways that we can trick 1257 00:54:56,369 --> 00:54:58,020 browsers and other implementations 1258 00:54:58,020 --> 00:55:00,840 into holding the connection open long enough. 1259 00:55:00,840 --> 00:55:03,490 Also, 70 seconds is just what we were able to do 1260 00:55:03,490 --> 00:55:07,040 with a few weeks of hacking around and optimisation, 1261 00:55:07,040 --> 00:55:10,660 we think that with not that much more effort 1262 00:55:10,660 --> 00:55:13,239 we could get that number down quite a bit more. 1263 00:55:13,239 --> 00:55:16,280 But 70 seconds we think already is not so bad, 1264 00:55:16,280 --> 00:55:18,240 and there's plenty of ways that we can exploit it. 1265 00:55:18,240 --> 00:55:21,489 NH: Proof of concept. 1266 00:55:21,489 --> 00:55:24,230 Herald: Okay. Do we have something from the net? 1267 00:55:24,230 --> 00:55:26,780 Signal Angel: How long do you estimate the security 1268 00:55:26,780 --> 00:55:29,490 of RSA-DHE to sustain, 1269 00:55:29,490 --> 00:55:31,030 and do you have any idea if and when 1270 00:55:31,030 --> 00:55:33,680 there's any quantum encryption algorithms 1271 00:55:33,680 --> 00:55:35,320 that will soon be available to be used 1272 00:55:35,320 --> 00:55:36,850 by a broad public? 1273 00:55:36,850 --> 00:55:38,950 AH: Oh, quantum encryption algorithms. 1274 00:55:38,950 --> 00:55:41,150 NH: You should watch Dan and Tanja's talk from yesterday. 1275 00:55:41,150 --> 00:55:44,070 AH: Yeah, last night was the time to hear about that. 1276 00:55:44,070 --> 00:55:46,170 NH: The dangers of quantum cryptography. 1277 00:55:46,170 --> 00:55:48,220 I mean, the short answer is 1278 00:55:48,220 --> 00:55:49,750 that people who know what they're talking about 1279 00:55:49,750 --> 00:55:51,830 have said we should start worrying now 1280 00:55:51,830 --> 00:55:53,930 because we may see quantum computers 1281 00:55:53,930 --> 00:55:56,740 within the next 15 years, maybe. 1282 00:55:56,740 --> 00:55:59,220 But it's really hard to speculate about 1283 00:55:59,220 --> 00:56:05,030 advances in physics that may be pretty far off. 1284 00:56:05,030 --> 00:56:06,770 Herald: Do we have another one? 1285 00:56:06,770 --> 00:56:09,550 Signal angel: Sure. What's your opinion on the NIST curves, 1286 00:56:09,550 --> 00:56:10,890 especially with the current rumours 1287 00:56:10,890 --> 00:56:15,530 about the curve parameters having a backdoor? 1288 00:56:15,530 --> 00:56:18,310 NH: There are no known ways 1289 00:56:18,310 --> 00:56:20,710 that the curves could have been backdoored 1290 00:56:20,710 --> 00:56:23,460 with the given parameters. 1291 00:56:23,460 --> 00:56:25,630 AH: But if you don't trust them, 1292 00:56:25,630 --> 00:56:28,160 you know Dan Bernstein has a curve you can use too. 1293 00:56:28,160 --> 00:56:30,120 NH: So... 1294 00:56:30,120 --> 00:56:32,230 *applause* 1295 00:56:32,230 --> 00:56:35,250 NH: Do you trust Dan, or do you trust the NSA? 1296 00:56:35,250 --> 00:56:37,250 *laughter* 1297 00:56:37,250 --> 00:56:38,859 Herald: Over to 2, please. 1298 00:56:38,859 --> 00:56:41,800 Q: Some of the little bit that you recommend, 1299 00:56:41,800 --> 00:56:46,249 you say Diffie-Hellman is worse than RSA now, 1300 00:56:46,249 --> 00:56:49,930 so, does it mean I should switch back 1301 00:56:49,930 --> 00:56:54,370 to RSA, preferring it instead of Diffie-Hellman? 1302 00:56:54,370 --> 00:56:57,070 AH: With equivalent key sizes, 1303 00:56:57,070 --> 00:56:59,980 equivalent sizes of your primes, 1304 00:56:59,980 --> 00:57:02,670 or your RSA modulus, 1305 00:57:02,670 --> 00:57:05,020 yes, we are saying that. 1306 00:57:05,020 --> 00:57:06,940 That in the 1024-bit case, 1307 00:57:06,940 --> 00:57:10,109 there's strong reasons that you should 1308 00:57:10,109 --> 00:57:14,160 distrust the very common repeated primes 1309 00:57:14,160 --> 00:57:15,690 for Diffie-Hellman. 1310 00:57:15,690 --> 00:57:17,750 But that's not the whole story. 1311 00:57:17,750 --> 00:57:26,510 Right, so for longer sizes of modulus, 1312 00:57:26,510 --> 00:57:27,790 larger strengths of crypto, 1313 00:57:27,790 --> 00:57:31,680 RSA is probably still okay. 1314 00:57:31,680 --> 00:57:34,369 But I think either way, 1315 00:57:34,369 --> 00:57:37,750 switching to elliptic curve for key exchange 1316 00:57:37,750 --> 00:57:39,980 is probably the thing to do right now. 1317 00:57:39,980 --> 00:57:42,320 NH: I think the precise statement that we can make 1318 00:57:42,320 --> 00:57:44,619 is, if you're comparing 1024-bit Diffie-Hellman 1319 00:57:44,619 --> 00:57:47,430 to a 1024-bit RSA key, 1320 00:57:47,430 --> 00:57:48,730 that if you're using Diffie-Hellman 1321 00:57:48,730 --> 00:57:50,980 with the most commonly used parameters, 1322 00:57:50,980 --> 00:57:52,690 say, the Oakley group 2 1323 00:57:52,690 --> 00:57:55,070 that everybody on the Internet is using, 1324 00:57:55,070 --> 00:57:57,460 and you think it is likely that a large government agency 1325 00:57:57,460 --> 00:58:00,700 has already done the precomputation for that prime, 1326 00:58:00,700 --> 00:58:05,359 then breaking an individual connection using that prime 1327 00:58:05,359 --> 00:58:06,750 with Diffie-Hellman key exchange 1328 00:58:06,750 --> 00:58:08,849 would be much, much, much less effort 1329 00:58:08,849 --> 00:58:14,720 than factoring a freshly generated 1024-bit RSA key that is unique to you. 1330 00:58:14,720 --> 00:58:17,720 Even if that 1024-bit RSA factorisation 1331 00:58:17,720 --> 00:58:20,460 is within range of the NSA, 1332 00:58:20,460 --> 00:58:21,490 it may not be worth their while 1333 00:58:21,490 --> 00:58:23,420 to actually factor your key. 1334 00:58:23,420 --> 00:58:25,810 Whereas breaking a Diffie-Hellman key exchange, 1335 00:58:25,810 --> 00:58:27,180 they've already done the hard work 1336 00:58:27,180 --> 00:58:28,500 to break everybody on the Internet, 1337 00:58:28,500 --> 00:58:31,250 so, you're just one more fish. 1338 00:58:31,250 --> 00:58:32,000 That's the precise statement 1339 00:58:32,000 --> 00:58:33,590 that we can make about the security. 1340 00:58:33,590 --> 00:58:35,430 The real answer: use elliptic curves, 1341 00:58:35,430 --> 00:58:41,990 or, to use 2048-bit Diffie-Hellman: probably fine. 1342 00:58:41,990 --> 00:58:43,849 Herald: And, over to number 1, please. 1343 00:58:43,849 --> 00:58:47,230 Q: How realistic is it to use, or to create 1344 00:58:47,230 --> 00:58:50,210 a new prime for every exchange 1345 00:58:50,210 --> 00:58:52,990 or at least every few exchanges? 1346 00:58:52,990 --> 00:58:55,840 NH: So, unfortunately, the properties 1347 00:58:55,840 --> 00:59:01,039 that you need for discrete log to be hard, 1348 00:59:01,039 --> 00:59:02,470 you need to have a safe prime 1349 00:59:02,470 --> 00:59:05,720 and you would hopefully like it not to be backdoored, 1350 00:59:05,720 --> 00:59:09,430 generating safe primes is still kind of effortful 1351 00:59:09,430 --> 00:59:10,609 on modern hardware, 1352 00:59:10,609 --> 00:59:12,010 I mean if you try to do it on your laptop 1353 00:59:12,010 --> 00:59:15,170 it will probably take like, I don't know, a minute or something. 1354 00:59:15,170 --> 00:59:16,940 So, it's actually a lot of effort 1355 00:59:16,940 --> 00:59:20,230 to generate a new safe prime all the time. 1356 00:59:20,230 --> 00:59:24,490 Just use a larger safe prime and you'll be better. 1357 00:59:24,490 --> 00:59:26,090 Herald: So we're running out of time, 1358 00:59:26,090 --> 00:59:28,730 but let's... with number 2. 1359 00:59:28,730 --> 00:59:32,060 Q: You said that elliptic curve cryptography 1360 00:59:32,060 --> 00:59:36,930 is not susceptible to this precomputation attack, 1361 00:59:36,930 --> 00:59:43,750 is that luck, or is it engineered to be that way? 1362 00:59:43,750 --> 00:59:44,300 *AH laughs* 1363 00:59:44,300 --> 00:59:45,520 NH: ...luck? 1364 00:59:45,520 --> 00:59:46,940 AH: In part! 1365 00:59:46,940 --> 00:59:48,010 NH: I mean, a combination of both, but 1366 00:59:48,010 --> 00:59:49,160 so as far as we know, I mean, you can't do 1367 00:59:49,160 --> 00:59:50,980 precomputation with elliptic curves, 1368 00:59:50,980 --> 00:59:53,570 so, you know, sort of generically, 1369 00:59:53,570 --> 00:59:54,560 the best thing that you can say 1370 00:59:54,560 --> 00:59:58,500 is you can do a lot of precomputation 1371 00:59:58,500 --> 01:00:00,720 but you still have to do a lot of effort 1372 01:00:00,720 --> 01:00:03,290 for each individual value, 1373 01:00:03,290 --> 01:00:05,849 so you could do, you know, generically 1374 01:00:05,849 --> 01:00:06,920 if you want to break an elliptic curve 1375 01:00:06,920 --> 01:00:08,880 you could do like, a square-root-of-n attack 1376 01:00:08,880 --> 01:00:10,830 against the key size, 1377 01:00:10,830 --> 01:00:13,599 you could do, say, n^2/3 precomputation 1378 01:00:13,599 --> 01:00:17,540 and then you would have n^1/3 online work 1379 01:00:17,540 --> 01:00:19,369 if that makes sense to you. 1380 01:00:19,369 --> 01:00:22,820 But you get less effort as far as we know. 1381 01:00:22,820 --> 01:00:24,610 Less benefit. 1382 01:00:24,610 --> 01:00:28,490 Herald: Sorry. We're going to finalise then, with number 4. 1383 01:00:28,490 --> 01:00:31,060 Q: What do you think about blacklisting these common primes, 1384 01:00:31,060 --> 01:00:32,460 just in the modern browsers? 1385 01:00:32,460 --> 01:00:34,920 Will this get rid of this issue? 1386 01:00:34,920 --> 01:00:36,920 AH: Just blacklisting the common primes, 1387 01:00:36,920 --> 01:00:39,109 well, if you blacklist the common primes, 1388 01:00:39,109 --> 01:00:41,030 if you blacklisted the common primes 1389 01:00:41,030 --> 01:00:43,230 when we first came up with this, 1390 01:00:43,230 --> 01:00:47,480 you'd immediately break about 10% of websites 1391 01:00:47,480 --> 01:00:49,670 because there's not a good fallback mechanism 1392 01:00:49,670 --> 01:00:52,420 if you don't like the prime you got 1393 01:00:52,420 --> 01:00:54,730 during key negotiation. 1394 01:00:54,730 --> 01:00:56,730 What the browsers are more likely to do 1395 01:00:56,730 --> 01:01:01,920 is to phase out this kind of finite-field Diffie-Hellman entirely, 1396 01:01:01,920 --> 01:01:04,550 over the next larger number of years. 1397 01:01:04,550 --> 01:01:06,580 So first they're going to start rejecting things 1398 01:01:06,580 --> 01:01:09,390 that use unusually weak primes, 1399 01:01:09,390 --> 01:01:11,580 that's what they're doing already today, 1400 01:01:11,580 --> 01:01:13,060 but I think in the long term 1401 01:01:13,060 --> 01:01:16,810 they're going to encourage the use of elliptic curves as an alternative, 1402 01:01:16,810 --> 01:01:18,410 if you want forward secrecy, 1403 01:01:18,410 --> 01:01:22,020 elliptic curves will be the way to get it. 1404 01:01:22,020 --> 01:01:24,560 Herald: Nadia, Alex, once again, 1405 01:01:24,560 --> 01:01:25,700 thank you so much. 1406 01:01:25,700 --> 01:01:26,790 AH: Thank you. 1407 01:01:26,790 --> 01:01:32,570 *applause* 1408 01:01:32,570 --> 01:01:43,661 *postroll music*