1 00:00:00,000 --> 00:00:10,064 *preroll music* 2 00:00:10,064 --> 00:00:12,189 Herald: Tanja Lange and djb, 3 00:00:12,189 --> 00:00:15,519 or, Daniel Bernstein, 4 00:00:15,519 --> 00:00:19,980 came from the elliptic curve 5 00:00:19,980 --> 00:00:21,710 are gonna talk today also about 6 00:00:21,710 --> 00:00:24,380 the McEliece crypto where they took us. 7 00:00:24,380 --> 00:00:25,759 They're both in the steering committee 8 00:00:25,759 --> 00:00:28,219 for the PQCrypt 9 00:00:28,219 --> 00:00:30,259 and I've talked to other people in the community 10 00:00:30,259 --> 00:00:31,239 and they said, 11 00:00:31,239 --> 00:00:32,390 especially about Tanja, 12 00:00:32,390 --> 00:00:37,739 she is the one that brings practice and reality into all this theoretical mess 13 00:00:37,739 --> 00:00:44,420 so let's please have a hand for Tanja Lange and Daniel Bernstein. 14 00:00:44,420 --> 00:00:55,260 *applause* 15 00:00:55,260 --> 00:00:58,769 djb: Okay. Am I on? I apparently am. 16 00:00:58,769 --> 00:01:01,980 Welcome to a late night show, with Dan and Tanja. 17 00:01:01,980 --> 00:01:05,570 *laughter* There's a lot of crypto talks out there 18 00:01:05,570 --> 00:01:09,560 where you'll get the idea that crypto has problems. 19 00:01:09,560 --> 00:01:12,340 Crypto has massive usability problems, 20 00:01:12,340 --> 00:01:13,890 has performance problems, 21 00:01:13,890 --> 00:01:15,460 has pitfalls for implementors, 22 00:01:15,460 --> 00:01:17,750 has crazy complexity in implementation, 23 00:01:17,750 --> 00:01:19,729 stupid standards, 24 00:01:19,729 --> 00:01:21,920 millions of lines of unauditable code, 25 00:01:21,920 --> 00:01:23,320 and then all of these problems 26 00:01:23,320 --> 00:01:27,189 are combined into a grand unified clusterfuck 27 00:01:27,189 --> 00:01:30,030 called transport layer security. 28 00:01:30,030 --> 00:01:38,030 *laughter, applause* 29 00:01:38,030 --> 00:01:41,449 But, actually, the situation is worse. 30 00:01:41,449 --> 00:01:43,510 *laughter* 31 00:01:43,510 --> 00:01:45,790 Because of what's coming, namely, 32 00:01:45,790 --> 00:01:49,260 quantum computers. 33 00:01:49,260 --> 00:01:51,610 These typical talks will give you the idea 34 00:01:51,610 --> 00:01:54,829 that the core of crypto, the basic cryptographic primitives 35 00:01:54,829 --> 00:01:57,280 like elliptic curve crypto, ECC, 36 00:01:57,280 --> 00:01:59,240 that those are just fine, and all the problems 37 00:01:59,240 --> 00:02:01,229 are integration into applications, 38 00:02:01,229 --> 00:02:03,100 that's where the security problems happen. 39 00:02:03,100 --> 00:02:06,609 But quantum computers will break ECC. 40 00:02:06,609 --> 00:02:09,258 This has been know since the 1990s. 41 00:02:09,258 --> 00:02:11,500 For people who don't recognise the picture here, 42 00:02:11,500 --> 00:02:17,040 this is a mathematician named Peter Shor, 20 years ago. 43 00:02:17,040 --> 00:02:25,769 *laughter, applause* 44 00:02:25,769 --> 00:02:27,640 20 years ago he wrote a paper saying 45 00:02:27,640 --> 00:02:29,340 that a big quantum computer would be 46 00:02:29,340 --> 00:02:33,300 able to factor big integers in polynomial time. 47 00:02:33,300 --> 00:02:34,770 Now, if you like doing attacks, 48 00:02:34,770 --> 00:02:36,259 and you hear about something like this, 49 00:02:36,259 --> 00:02:37,190 then your first thought is 50 00:02:37,190 --> 00:02:39,080 "Ooh, I wanna quantum computer!" 51 00:02:39,080 --> 00:02:41,430 "I want a big quantum computer so I can run this attack!" 52 00:02:41,430 --> 00:02:43,350 "And, where is it? Does anybody have one?" 53 00:02:43,350 --> 00:02:44,620 "Can anybody gimme one?" 54 00:02:44,620 --> 00:02:46,610 "Oh, it isn't there yet? Well, what's the progress?" 55 00:02:46,610 --> 00:02:48,670 "Are we there yet? Can I have one, please?" 56 00:02:48,670 --> 00:02:50,470 And, well, in the news, you now hear 57 00:02:50,470 --> 00:02:53,669 about this D-wave quantum computer, 58 00:02:53,669 --> 00:02:56,879 which, okay, there's some very good quantum engineering 59 00:02:56,879 --> 00:02:58,180 that goes into this machine. 60 00:02:58,180 --> 00:02:59,420 It's pretty clear that it's quantum, 61 00:02:59,420 --> 00:03:01,800 I mean, it's actually doing the quantum stuff they say it does. 62 00:03:01,800 --> 00:03:04,920 And there's some fantastic marketing in this machine. 63 00:03:04,920 --> 00:03:06,230 But, unfortunately, 64 00:03:06,230 --> 00:03:07,650 it's not actually useful. 65 00:03:07,650 --> 00:03:09,780 So the D-wave quantum computer 66 00:03:09,780 --> 00:03:11,690 doesn't do the basic things 67 00:03:11,690 --> 00:03:14,830 that we expect a universal quantum computer to do. 68 00:03:14,830 --> 00:03:18,159 It can only do very limited kinds of quantum computation. 69 00:03:18,159 --> 00:03:20,480 It cannot maintain qubits, 70 00:03:20,480 --> 00:03:22,520 do error correction on qubits for a while, 71 00:03:22,520 --> 00:03:23,750 hold on to them to be able to do 72 00:03:23,750 --> 00:03:25,659 basic qubit computations. 73 00:03:25,659 --> 00:03:27,739 It can't even do those computations, 74 00:03:27,739 --> 00:03:29,769 even if it could hold on to the qubits. 75 00:03:29,769 --> 00:03:31,299 It can't do Shor's algorithm. 76 00:03:31,299 --> 00:03:32,939 Can't factor big numbers. 77 00:03:32,939 --> 00:03:35,390 Can't do other quantum algorithms that we care about. 78 00:03:35,390 --> 00:03:38,080 Now, the D-wave company says that's not the point, 79 00:03:38,080 --> 00:03:39,519 there's some other computations 80 00:03:39,519 --> 00:03:41,799 that we designed this machine to do. 81 00:03:41,799 --> 00:03:43,549 But they cherry-picked the computations 82 00:03:43,549 --> 00:03:45,280 for this machine, saying basically 83 00:03:45,280 --> 00:03:48,769 Here is the problem of simulating this machine 84 00:03:48,769 --> 00:03:51,129 simulating the quantum thing that it's doing, 85 00:03:51,129 --> 00:03:53,400 and of course the machine is very good at simulating itself, 86 00:03:53,400 --> 00:03:54,610 by just running, 87 00:03:54,610 --> 00:03:57,909 whereas a normal laptop, they compared to 88 00:03:57,909 --> 00:04:00,189 sort of standard programs on a normal laptop, 89 00:04:00,189 --> 00:04:02,439 and latest results, 10^8 times faster 90 00:04:02,439 --> 00:04:06,129 except, well, there's a much more optimised program 91 00:04:06,129 --> 00:04:07,780 that somebody put out last year, 92 00:04:07,780 --> 00:04:10,159 which basically is the same speed as the D-wave machine 93 00:04:10,159 --> 00:04:12,049 and like ten thousand times cheaper. 94 00:04:12,049 --> 00:04:15,630 So, the D-wave machine is not, for the moment, something useful. 95 00:04:15,630 --> 00:04:18,360 Lange: Well, if this makes you kind of comfortable, 96 00:04:18,360 --> 00:04:22,440 so, no Shor monster coming, 97 00:04:22,440 --> 00:04:23,720 there is progress. 98 00:04:23,720 --> 00:04:25,760 There will be a universal quantum computer, 99 00:04:25,760 --> 00:04:28,000 so, something that can run Shor's algorithm, 100 00:04:28,000 --> 00:04:30,020 and there's a lot of research effort going into this, 101 00:04:30,020 --> 00:04:32,120 so if you track, like, spending on crypto 102 00:04:32,120 --> 00:04:33,320 and you can spend... 103 00:04:33,320 --> 00:04:36,450 and track spending on quantum computers, 104 00:04:36,450 --> 00:04:37,670 that is a lot of money. 105 00:04:37,670 --> 00:04:39,850 And there's a lot of institutions and companies 106 00:04:39,850 --> 00:04:41,700 and of course governments all over the world 107 00:04:41,700 --> 00:04:43,090 building stuff. 108 00:04:43,090 --> 00:04:44,250 And we do see progress, so 109 00:04:44,250 --> 00:04:45,730 we're keeping track on this, 110 00:04:45,730 --> 00:04:48,300 and, go to the Wikipedia page here 111 00:04:48,300 --> 00:04:50,270 so we see over the last few years 112 00:04:50,270 --> 00:04:53,980 a huge progress in stability of qubits, 113 00:04:53,980 --> 00:04:56,430 so these things usually forget what they had, 114 00:04:56,430 --> 00:04:57,930 they decay, 115 00:04:57,930 --> 00:04:59,890 but they get more stable, 116 00:04:59,890 --> 00:05:01,730 there's better error correction, 117 00:05:01,730 --> 00:05:03,040 and there's better communication. 118 00:05:03,040 --> 00:05:06,900 So the latest was that even silicon-based qubits can communicate. 119 00:05:06,900 --> 00:05:08,530 So something is happening. 120 00:05:08,530 --> 00:05:12,970 Um, IBM has on the record of Mark Ketchen 121 00:05:12,970 --> 00:05:15,390 who's their CEO saying 122 00:05:15,390 --> 00:05:19,640 "We actually do things that make us think like, hey, this isn't 50 years off" 123 00:05:19,640 --> 00:05:23,260 "This is maybe just 10 or 15 years off. It's within reach." 124 00:05:23,260 --> 00:05:24,590 So IBM is leaning out the window 125 00:05:24,590 --> 00:05:27,510 and saying, yup, we're gonna be there pretty damn soon. 126 00:05:27,510 --> 00:05:31,560 They said that in 2012, so let's fast-forward by 10 to 15 years 127 00:05:31,560 --> 00:05:34,930 so it's now 2022 or 2027 128 00:05:34,930 --> 00:05:37,990 and so there is a universal quantum computer. 129 00:05:37,990 --> 00:05:42,220 The effect this has on the Internet crypto 130 00:05:42,220 --> 00:05:45,320 is that RSA, which is still the majority 131 00:05:45,320 --> 00:05:46,650 of all the connections today, 132 00:05:46,650 --> 00:05:49,760 RSA is broken. RSA is dead. 133 00:05:49,760 --> 00:05:51,820 Discrete logs in finite fields. 134 00:05:51,820 --> 00:05:53,250 You might have thought a lot about it 135 00:05:53,250 --> 00:05:55,000 earlier this year about Logjam. 136 00:05:55,000 --> 00:05:57,740 But Logjam just breaks the very small one. 137 00:05:57,740 --> 00:06:00,210 This is breaking any big one. 138 00:06:00,210 --> 00:06:03,250 So, discrete logs in finite fields is totally dead as well. 139 00:06:03,250 --> 00:06:05,810 Elliptic curves, that I already mentioned, ECC is dead. 140 00:06:05,810 --> 00:06:11,030 So this breaks all public-key crypto on the Internet. 141 00:06:11,030 --> 00:06:13,460 There's another algorithm due to Grover, 142 00:06:13,460 --> 00:06:16,190 which is somewhat better under control, 143 00:06:16,190 --> 00:06:18,360 somewhat less scary for crypto, 144 00:06:18,360 --> 00:06:19,820 but it still has quite an effect, 145 00:06:19,820 --> 00:06:22,250 so if you believe in the security of AES 146 00:06:22,250 --> 00:06:26,010 and go like, well, AES-128 seems just fine, 147 00:06:26,010 --> 00:06:27,200 has been not getting any 148 00:06:27,200 --> 00:06:30,300 big progress in cryptanalysis, 149 00:06:30,300 --> 00:06:33,850 but it halves the security, so AES 128-bit keys 150 00:06:33,850 --> 00:06:36,800 are only 64-bit secure. 151 00:06:36,800 --> 00:06:40,460 However, you can go to 256 bits. 152 00:06:40,460 --> 00:06:43,470 djb: Okay, so, the AES situation: not so bad, 153 00:06:43,470 --> 00:06:45,530 but all this public key stuff is broken. 154 00:06:45,530 --> 00:06:46,470 So what do we do? 155 00:06:46,470 --> 00:06:48,370 Well, you could bury your head in the sand, 156 00:06:48,370 --> 00:06:50,870 you could hope that quantum computers don't come along, 157 00:06:50,870 --> 00:06:55,800 you could deploy a physically secure crypto. 158 00:06:55,800 --> 00:06:59,100 You could take a locked briefcase and chain it to your wrist, 159 00:06:59,100 --> 00:07:01,090 or you could do quantum key distribution. 160 00:07:01,090 --> 00:07:04,000 Now these things, obviously, are very very expensive. 161 00:07:04,000 --> 00:07:07,610 This is crypto, information protection for rich people. 162 00:07:07,610 --> 00:07:11,980 Or, quantum key distribution is crypto for even richer people. 163 00:07:11,980 --> 00:07:15,370 You, obviously, aren't going to be able to democratically give this 164 00:07:15,370 --> 00:07:16,840 to everybody who has a laptop. 165 00:07:16,840 --> 00:07:19,210 But, well, okay, imagine that you have enough money, 166 00:07:19,210 --> 00:07:20,490 that you don't mind this. 167 00:07:20,490 --> 00:07:23,830 There's a bigger problem with physical cryptography, 168 00:07:23,830 --> 00:07:25,290 which is the security. 169 00:07:25,290 --> 00:07:26,950 Now these things are always advertised 170 00:07:26,950 --> 00:07:30,100 as provably secure, guaranteed secure. 171 00:07:30,100 --> 00:07:31,760 Nobody can get into this briefcase! 172 00:07:31,760 --> 00:07:34,300 Nobody can get into this quantum key distribution system! 173 00:07:34,300 --> 00:07:36,340 Assuming, of course, blah blah blah. 174 00:07:36,340 --> 00:07:37,550 And then you look at the assumptions 175 00:07:37,550 --> 00:07:38,410 and you start saying 176 00:07:38,410 --> 00:07:40,570 "Wait a minute, is that actually true?" 177 00:07:40,570 --> 00:07:43,440 And then it turns out that when people try attacking these systems, 178 00:07:43,440 --> 00:07:44,770 the assumptions are not true. 179 00:07:44,770 --> 00:07:47,520 And the systems get broken again and again and again 180 00:07:47,520 --> 00:07:50,380 for a very reasonable attack cost. 181 00:07:50,380 --> 00:07:54,270 Okay. Even if you have a system where you think it's secure, 182 00:07:54,270 --> 00:07:55,770 which nobody's managed to build yet, 183 00:07:55,770 --> 00:07:59,080 even if you had that, the design of this physical security system 184 00:07:59,080 --> 00:08:01,590 is incredibly difficult to audit. 185 00:08:01,590 --> 00:08:03,700 It's something where, if somebody wants to slip in a backdoor, 186 00:08:03,700 --> 00:08:05,020 it's really easy. 187 00:08:05,020 --> 00:08:06,260 But there's an even worse problem 188 00:08:06,260 --> 00:08:07,860 with physical cryptography, 189 00:08:07,860 --> 00:08:10,480 which is that it doesn't do very much crypto. 190 00:08:10,480 --> 00:08:14,860 Typically these systems do about the same thing that AES does. 191 00:08:14,860 --> 00:08:17,000 You start with a shared secret, 192 00:08:17,000 --> 00:08:18,310 and then from that shared secret 193 00:08:18,310 --> 00:08:20,560 you can authenticate more secrets 194 00:08:20,560 --> 00:08:24,590 that you transmit through this physically secure communication mechanism. 195 00:08:24,590 --> 00:08:26,050 For instance, quantum key distribution 196 00:08:26,050 --> 00:08:28,520 starts with some way, some pre-existing way 197 00:08:28,520 --> 00:08:30,190 of authenticating. 198 00:08:30,190 --> 00:08:33,070 But that's just like AES starts with a, a secret key 199 00:08:33,070 --> 00:08:34,450 which is then used to generate 200 00:08:34,450 --> 00:08:36,529 more and more secret data. 201 00:08:36,529 --> 00:08:38,330 And quantum key distribution says 202 00:08:38,330 --> 00:08:40,610 well, it's provably secure under certain assumptions, 203 00:08:40,610 --> 00:08:42,770 instead of AES which, well, 204 00:08:42,770 --> 00:08:44,860 we just heard AES may be a little affected 205 00:08:44,860 --> 00:08:46,260 by quantum computers, but 206 00:08:46,260 --> 00:08:48,160 AES-256 is not broken. 207 00:08:48,160 --> 00:08:50,030 Nobody has any idea how to break it. 208 00:08:50,030 --> 00:08:52,200 So this physical cryptography 209 00:08:52,200 --> 00:08:54,570 isn't actually serving the needs that we want. 210 00:08:54,570 --> 00:08:58,470 Imagine trying to distribute operating system updates 211 00:08:58,470 --> 00:09:00,550 through locked briefcases. 212 00:09:00,550 --> 00:09:01,810 It's just not going to happen. 213 00:09:01,810 --> 00:09:04,330 Microsoft sending out billions of locked briefcases 214 00:09:04,330 --> 00:09:05,800 to all of its customers. 215 00:09:05,800 --> 00:09:07,020 If you think that's realistic, 216 00:09:07,020 --> 00:09:11,150 or if you think that, just, lasers are cool, 217 00:09:11,150 --> 00:09:13,450 then there's a talk about quantum crypto 218 00:09:13,450 --> 00:09:15,340 tomorrow, I believe. 219 00:09:15,340 --> 00:09:20,010 Back in the real world, we obviously need to do something better with crypto. 220 00:09:20,010 --> 00:09:22,770 Lange: Alright, so, let me take, momentarily, 221 00:09:22,770 --> 00:09:24,770 a slightly more optimistic perspective. 222 00:09:24,770 --> 00:09:26,370 Is there any hope? Yes. 223 00:09:26,370 --> 00:09:29,180 So, the title of this talk, PQCHacks, 224 00:09:29,180 --> 00:09:31,310 comes from post-quantum crypto, 225 00:09:31,310 --> 00:09:32,860 and that's the term Dan coined 226 00:09:32,860 --> 00:09:34,510 back in 2003 227 00:09:34,510 --> 00:09:36,290 for crypto that remains secure 228 00:09:36,290 --> 00:09:38,840 even if the adversary has a quantum computer. 229 00:09:38,840 --> 00:09:42,500 So you, the normal people, me, him, the normal people, 230 00:09:42,500 --> 00:09:44,290 the Internet, all the connections, 231 00:09:44,290 --> 00:09:46,740 we have normal computers. 232 00:09:46,740 --> 00:09:49,080 The adversary has a quantum computer. 233 00:09:49,080 --> 00:09:50,700 We, today, encrypt something. 234 00:09:50,700 --> 00:09:51,970 Adversary has all the time in the world 235 00:09:51,970 --> 00:09:53,450 to build the quantum computer, 236 00:09:53,450 --> 00:09:56,390 break us now or break us in the future. 237 00:09:56,390 --> 00:09:57,370 And so this took off, 238 00:09:57,370 --> 00:09:58,550 and there's been the first workshop 239 00:09:58,550 --> 00:10:02,370 on post-quantum crypto, called PQCrypto2006 240 00:10:02,370 --> 00:10:03,770 and then there's been a series of workshops 241 00:10:03,770 --> 00:10:04,850 you can see here. 242 00:10:04,850 --> 00:10:07,270 These are the attendees of the last edition 243 00:10:07,270 --> 00:10:09,580 which was in Waterloo. It's more than a hundred people, 244 00:10:09,580 --> 00:10:11,390 going like, yes, this is an important topic, 245 00:10:11,390 --> 00:10:13,490 let's do some research on it. 246 00:10:13,490 --> 00:10:15,740 So something is happening. 247 00:10:15,740 --> 00:10:17,500 If you're curious what's happening, 248 00:10:17,500 --> 00:10:20,620 next there's a workshop in Japan in February 249 00:10:20,620 --> 00:10:23,420 and then in the Netherlands in 2017, 250 00:10:23,420 --> 00:10:26,630 and we also got a project through from the EU 251 00:10:26,630 --> 00:10:28,810 to support research on post-quantum. 252 00:10:28,810 --> 00:10:30,320 So something is happening. 253 00:10:30,320 --> 00:10:34,260 Actually, um, did I forget somebody? Yes. 254 00:10:34,260 --> 00:10:38,280 Um, the NSA is also saying, let's do something. 255 00:10:38,280 --> 00:10:44,400 So, on August 11 the NSA posted on their Suite B... page 256 00:10:44,400 --> 00:10:47,540 saying, "The Information Assurance Director (so, IAD) 257 00:10:47,540 --> 00:10:51,640 recognizes that there will be a move, in the not distant future, to a 258 00:10:51,640 --> 00:10:53,480 quantum resistant algorithm suite." 259 00:10:53,480 --> 00:10:56,180 Oh my god! Somebody is doing something! 260 00:10:56,180 --> 00:10:58,210 The public has realised we have to do something! 261 00:10:58,210 --> 00:11:00,510 Quick, quick, let's put out a press release! 262 00:11:00,510 --> 00:11:02,590 Um. 263 00:11:02,590 --> 00:11:05,560 Looks like they kind of realised it was embarrassing. 264 00:11:05,560 --> 00:11:09,690 So, eight days later they pushed a new release, saying 265 00:11:09,690 --> 00:11:15,210 "IAD will initiate a transition to quantum resistant algorithms in the not distant future." 266 00:11:15,210 --> 00:11:19,910 So, NSA will lead us to a bright and glorious future. 267 00:11:19,910 --> 00:11:22,760 djb: America, fuck yeah. 268 00:11:22,760 --> 00:11:30,790 *laughter, applause* 269 00:11:30,790 --> 00:11:34,510 Lange: But if you thought that, so far, this was bad, 270 00:11:34,510 --> 00:11:38,340 it actually takes a lot of time to build crypto. 271 00:11:38,340 --> 00:11:41,810 With let's say, NSA all ask the researchers 272 00:11:41,810 --> 00:11:44,000 If you have some idea of what could be secure 273 00:11:44,000 --> 00:11:45,510 against a quantum computer, 274 00:11:45,510 --> 00:11:47,120 say AES-256, 275 00:11:47,120 --> 00:11:48,590 the reason that you have confidence in it 276 00:11:48,590 --> 00:11:51,250 is we had more than ten years of people 277 00:11:51,250 --> 00:11:53,000 trying to break it, 278 00:11:53,000 --> 00:11:54,570 trying all kinds of approaches 279 00:11:54,570 --> 00:11:55,870 and not getting anywhere. 280 00:11:55,870 --> 00:12:00,350 It takes a lot of time to explore the space of cryptosystems. 281 00:12:00,350 --> 00:12:01,540 Once you have figured out 282 00:12:01,540 --> 00:12:02,880 what could be actually doable, 283 00:12:02,880 --> 00:12:05,230 you want to figure what the best attacks are, 284 00:12:05,230 --> 00:12:06,940 you want to focus on the security system, 285 00:12:06,940 --> 00:12:09,430 you want to figure out how to implement them, 286 00:12:09,430 --> 00:12:10,380 how to implement them securely, 287 00:12:10,380 --> 00:12:13,570 that is a whole lot of work that needs to be done 288 00:12:13,570 --> 00:12:15,860 before you can say, well, this is actually practical. 289 00:12:15,860 --> 00:12:18,060 We can actually use this. 290 00:12:18,060 --> 00:12:22,680 Or sometimes, this is as practical as we can get it. 291 00:12:22,680 --> 00:12:27,210 And then, you have this tiny little crypto primitive, 292 00:12:27,210 --> 00:12:28,410 and then you have to build the hooks 293 00:12:28,410 --> 00:12:31,200 and connections to get it into TLS. 294 00:12:31,200 --> 00:12:32,670 Then we said at the beginning 295 00:12:32,670 --> 00:12:33,910 that maybe you believe 296 00:12:33,910 --> 00:12:36,670 that the cute little crypto cores are all secure 297 00:12:36,670 --> 00:12:37,600 and it's just the connections 298 00:12:37,600 --> 00:12:39,500 with the AES, sorry, with the TLS 299 00:12:39,500 --> 00:12:42,029 in other world that is the problem. 300 00:12:42,029 --> 00:12:44,620 That still needs to be done for post-quantum as well. 301 00:12:44,620 --> 00:12:46,500 And, the side-channel attacks, 302 00:12:46,500 --> 00:12:48,260 there's, uh, as an example, 303 00:12:48,260 --> 00:12:52,370 ECC was introduced back in 85, 304 00:12:52,370 --> 00:12:54,100 and now 30 years later, 305 00:12:54,100 --> 00:12:57,460 we're seeing that ECC is actually getting deployed on the Internet, 306 00:12:57,460 --> 00:13:02,340 that now the IETF, having called for having elliptic curve crypto, 307 00:13:02,340 --> 00:13:05,560 because people start saying, yes, we would like to use this. 308 00:13:05,560 --> 00:13:08,440 So we cannot wait until there's a quantum computer 309 00:13:08,440 --> 00:13:10,670 in order to start research on it. 310 00:13:10,670 --> 00:13:14,770 If you remember what 85 looked like 311 00:13:14,770 --> 00:13:18,770 That's a while ago. 312 00:13:18,770 --> 00:13:21,970 Now, if that sounded bad, 313 00:13:21,970 --> 00:13:23,170 it's actually worse. 314 00:13:23,170 --> 00:13:26,400 It's not just that, in 15 years from now, 315 00:13:26,400 --> 00:13:29,259 whatever you send then will be broken. 316 00:13:29,259 --> 00:13:33,420 There's some indication that some entities 317 00:13:33,420 --> 00:13:40,690 might be recording your traffic. 318 00:13:40,690 --> 00:13:42,700 We've given a talk like this in 2012 319 00:13:42,700 --> 00:13:44,220 which was "Crypto for the Paranoid", 320 00:13:44,220 --> 00:13:45,400 everybody thought it was, like, 321 00:13:45,400 --> 00:13:46,960 pfft, you're crazy, 322 00:13:46,960 --> 00:13:48,720 now it goes like "well, there might be an entity" 323 00:13:48,720 --> 00:13:52,960 and everybody goes like, yeah, hmm, yeah. 324 00:13:52,960 --> 00:13:54,560 So, let's assume that this entity 325 00:13:54,560 --> 00:13:57,020 has the records of all the connections, 326 00:13:57,020 --> 00:14:01,220 and, that in ten years, you're going to be an interesting person. 327 00:14:01,220 --> 00:14:04,540 Maybe you're a politician, maybe you've become rich, 328 00:14:04,540 --> 00:14:07,880 maybe you associate with the wrong people, or so they think, 329 00:14:07,880 --> 00:14:12,630 and so somehow they go back to the 27th of December 2015, 330 00:14:12,630 --> 00:14:16,000 and figure out what you were emailing during the talks, 331 00:14:16,000 --> 00:14:18,279 because they have all the connections here 332 00:14:18,279 --> 00:14:20,410 so they can go back in time 333 00:14:20,410 --> 00:14:26,050 just by the metadata, and of course the real data. 334 00:14:26,050 --> 00:14:28,630 From the metadata, they can decrypt it, 335 00:14:28,630 --> 00:14:31,670 because this metadata is using RSA or ECC 336 00:14:31,670 --> 00:14:33,090 which are broken. 337 00:14:33,090 --> 00:14:34,550 And then they get the same key 338 00:14:34,550 --> 00:14:38,180 than you're currently using with your other side to communicate. 339 00:14:38,180 --> 00:14:42,920 And so they can go and decrypt this. 340 00:14:42,920 --> 00:14:45,529 So it's not only that we can't wait for quantum computers to come, 341 00:14:45,529 --> 00:14:51,320 we might already be too late. 342 00:14:51,320 --> 00:14:53,359 Well, on the next slide, 343 00:14:53,359 --> 00:14:56,190 here's a bunch of people who are getting together in this EU project, 344 00:14:56,190 --> 00:14:59,720 and we have come up with what we're currently thinking 345 00:14:59,720 --> 00:15:02,290 are good recommendations. 346 00:15:02,290 --> 00:15:04,080 We think it's necessary for people 347 00:15:04,080 --> 00:15:07,190 who really care about the security of their connections, 348 00:15:07,190 --> 00:15:08,480 and when I say people I include myself, 349 00:15:08,480 --> 00:15:10,740 I care about the security of my connections, 350 00:15:10,740 --> 00:15:12,330 we would like to have something 351 00:15:12,330 --> 00:15:15,050 that we believe is secure for the next hundred years. 352 00:15:15,050 --> 00:15:17,310 And so we put out a list of recommendations. 353 00:15:17,310 --> 00:15:19,910 So, for symmetric, it's relatively easy. 354 00:15:19,910 --> 00:15:22,500 You want something which is at least a 256-bit key 355 00:15:22,500 --> 00:15:25,110 and is sufficiently well understood 356 00:15:25,110 --> 00:15:29,129 so there we have Salsa20, and we have AES-256. 357 00:15:29,129 --> 00:15:32,990 Then, for authentication in symmetric, 358 00:15:32,990 --> 00:15:35,430 there, we don't actually have any decrease 359 00:15:35,430 --> 00:15:36,750 from a quantum computer, because 360 00:15:36,750 --> 00:15:38,899 these are already information-theoretically secure. 361 00:15:38,899 --> 00:15:40,899 So these are the nice part. 362 00:15:40,899 --> 00:15:44,220 These two talk items is where we go like 363 00:15:44,220 --> 00:15:47,690 "Pff. We might be okay on those." 364 00:15:47,690 --> 00:15:49,880 We can do better, we can have nice research 365 00:15:49,880 --> 00:15:51,740 and get something which is even better protected, 366 00:15:51,740 --> 00:15:54,010 even faster under the new scenario, 367 00:15:54,010 --> 00:15:55,740 but it's not so dire. 368 00:15:55,740 --> 00:15:59,240 The bottom two, these are the public key systems. 369 00:15:59,240 --> 00:16:03,399 That's public key encryption and public key signatures. 370 00:16:03,399 --> 00:16:05,220 That's what we're going to focus on in this talk. 371 00:16:05,220 --> 00:16:07,750 So, for public key encryption, we're recommending 372 00:16:07,750 --> 00:16:10,620 the McEliece cryptosystem with Goppa codes 373 00:16:10,620 --> 00:16:13,250 for a certain parameter size, 374 00:16:13,250 --> 00:16:15,240 and then for signatures, 375 00:16:15,240 --> 00:16:17,959 the recommendation is to use hash-based. 376 00:16:17,959 --> 00:16:19,170 djb: Okay, so... 377 00:16:19,170 --> 00:16:23,240 Let me dive into the hash-based part of this. 378 00:16:23,240 --> 00:16:26,220 This is something which goes back even further than the 80s. 379 00:16:26,220 --> 00:16:28,720 It goes back to the 1970s. Lamport. 380 00:16:28,720 --> 00:16:32,810 So here's a way to use hashes to do one-time signatures. 381 00:16:32,810 --> 00:16:34,300 Which are, we'll see in a few minutes, 382 00:16:34,300 --> 00:16:35,700 signatures that you can use 383 00:16:35,700 --> 00:16:38,460 to sign one message under a given key. 384 00:16:38,460 --> 00:16:40,660 And then, well, that's a little bit inconvenient 385 00:16:40,660 --> 00:16:41,910 that you can't sign more messages 386 00:16:41,910 --> 00:16:43,470 so then Merkle came along 387 00:16:43,470 --> 00:16:45,100 and said, you can sign more messages 388 00:16:45,100 --> 00:16:46,339 by modifying the system, 389 00:16:46,339 --> 00:16:47,730 and we'll also take a look at that. 390 00:16:47,730 --> 00:16:50,890 The only thing you need for these public-key signature systems 391 00:16:50,890 --> 00:16:52,130 is a good hash function. 392 00:16:52,130 --> 00:16:54,690 And, okay, that's something where historically, 393 00:16:54,690 --> 00:16:57,740 some hash functions designed in like, 1991 394 00:16:57,740 --> 00:16:58,580 had trouble. 395 00:16:58,580 --> 00:17:00,920 But, now, we have some good hash functions 396 00:17:00,920 --> 00:17:03,660 so, for instance, SHA-3 has some great hash functions, 397 00:17:03,660 --> 00:17:05,790 even SHA-2, there's no sign of trouble, 398 00:17:05,790 --> 00:17:07,400 of those things being broken. 399 00:17:07,400 --> 00:17:10,119 And then after these original systems from Lamport and Merkle, 400 00:17:10,119 --> 00:17:11,859 there's lots and lots of improvements, 401 00:17:11,859 --> 00:17:14,020 but all of these hash-based systems, 402 00:17:14,020 --> 00:17:16,670 it's really easy to understand the security. 403 00:17:16,670 --> 00:17:18,329 It's something where the basic idea 404 00:17:18,329 --> 00:17:19,589 is really, really simple, 405 00:17:19,589 --> 00:17:21,280 and the security analysis also ends up 406 00:17:21,280 --> 00:17:22,869 being very straightforward. 407 00:17:22,869 --> 00:17:24,679 You have to be careful about some things, 408 00:17:24,679 --> 00:17:26,589 but, when you're careful about those, 409 00:17:26,589 --> 00:17:28,790 and there's nothing subtle about it, nothing tricky, 410 00:17:28,790 --> 00:17:32,110 then we understand exactly what security we get from these. 411 00:17:32,110 --> 00:17:35,130 So let's dive into a signature scheme 412 00:17:35,130 --> 00:17:37,820 that can only sign empty messages. 413 00:17:37,820 --> 00:17:40,690 Now, this sounds kind of, like, wait a minute, 414 00:17:40,690 --> 00:17:42,760 what do you mean, "can only sign empty messages?" 415 00:17:42,760 --> 00:17:44,600 There's only one empty string, 416 00:17:44,600 --> 00:17:46,290 and that's the only thing you can sign. 417 00:17:46,290 --> 00:17:49,550 But imagine that you want to have a panic button, 418 00:17:49,550 --> 00:17:51,000 like, your revocation key, 419 00:17:51,000 --> 00:17:52,000 you want to be able to say, 420 00:17:52,000 --> 00:17:56,290 "Here's a message that says, my house, my computer's been compromised, 421 00:17:56,290 --> 00:17:58,290 don't trust anything from this anymore". 422 00:17:58,290 --> 00:18:00,750 It's this one message that you want to sign, 423 00:18:00,750 --> 00:18:01,500 under a certain key, 424 00:18:01,500 --> 00:18:03,750 and if anybody has that public key, 425 00:18:03,750 --> 00:18:06,800 then they should be able to verify that you sent that message, 426 00:18:06,800 --> 00:18:08,350 and nobody should be able to forge that, 427 00:18:08,350 --> 00:18:10,000 because it's really bad if somebody can forge 428 00:18:10,000 --> 00:18:10,880 your panic message. 429 00:18:10,880 --> 00:18:12,960 So, being able to sign just one message 430 00:18:12,960 --> 00:18:15,550 is not actually such a useless thing, 431 00:18:15,550 --> 00:18:16,790 and we'll also see that it builds up 432 00:18:16,790 --> 00:18:19,550 to the rest of hash-based crypto. 433 00:18:19,550 --> 00:18:23,040 Okay. Let's look at some Python stuff here, 434 00:18:23,040 --> 00:18:25,650 simple SHA-3 you can get online 435 00:18:25,650 --> 00:18:29,580 under Ubuntu or Debian do install python-pip and python-dev 436 00:18:29,580 --> 00:18:31,360 because it's a C library actually, 437 00:18:31,360 --> 00:18:33,840 and then, pip install simplesha3, 438 00:18:33,840 --> 00:18:36,210 that will give you SHA3-256, 439 00:18:36,210 --> 00:18:38,000 and then to generate a keypair 440 00:18:38,000 --> 00:18:41,140 in this empty-message signature system, 441 00:18:41,140 --> 00:18:43,850 all you do is you make 32 bytes of random data 442 00:18:43,850 --> 00:18:45,070 and just hash it again, 443 00:18:45,070 --> 00:18:49,740 just in in case... urandom is not too well-reviewed... 444 00:18:49,740 --> 00:18:51,770 I mean, we should trust urandom, 445 00:18:51,770 --> 00:18:54,090 but it's really cheap to put an extra hash on it. 446 00:18:54,090 --> 00:18:57,140 So that's your secret key, it's a 32-byte hash. 447 00:18:57,140 --> 00:18:58,530 And then the public key is, 448 00:18:58,530 --> 00:18:59,890 hash that secret again. 449 00:18:59,890 --> 00:19:03,040 So the public key is simply a hash of the secret key. 450 00:19:03,040 --> 00:19:05,120 And then return the public key and the secret key, 451 00:19:05,120 --> 00:19:06,640 of course the public key will get published, 452 00:19:06,640 --> 00:19:08,860 and the secret key you keep for yourself. 453 00:19:08,860 --> 00:19:11,370 As an example of doing this, well, um, 454 00:19:11,370 --> 00:19:12,600 you just get random-looking data 455 00:19:12,600 --> 00:19:15,000 coming out from your public key at the bottom 456 00:19:15,000 --> 00:19:17,910 your secret key right at the bottom and public key above that. 457 00:19:17,910 --> 00:19:19,870 And you can check that one of them's a hash of the other 458 00:19:19,870 --> 00:19:21,290 if you know the secret key, 459 00:19:21,290 --> 00:19:22,730 you can hash it to get the public. 460 00:19:22,730 --> 00:19:25,000 Okay, now, how do you sign a message? 461 00:19:25,000 --> 00:19:27,380 Well, this maybe sort of spelled out 462 00:19:27,380 --> 00:19:29,230 in more steps than it has to be. 463 00:19:29,230 --> 00:19:32,260 The API here, this is, I would say, 464 00:19:32,260 --> 00:19:33,910 getting to be a pretty popular API 465 00:19:33,910 --> 00:19:36,790 for signatures and for verification, 466 00:19:36,790 --> 00:19:40,010 where you include the signature and the message together, 467 00:19:40,010 --> 00:19:41,230 as a signed message. 468 00:19:41,230 --> 00:19:44,940 And to emphasise that, here's a returned signed message from the sign function. 469 00:19:44,940 --> 00:19:48,730 Now, the signed message will be later on verified, 470 00:19:48,730 --> 00:19:50,450 and you get a message out of it, 471 00:19:50,450 --> 00:19:52,080 where the only possible message 472 00:19:52,080 --> 00:19:53,670 to be signed is the empty string, 473 00:19:53,670 --> 00:19:55,610 and you can see that the top there 474 00:19:55,610 --> 00:19:57,540 of the signature is checking 475 00:19:57,540 --> 00:19:59,530 if the message is anything other than the empty string 476 00:19:59,530 --> 00:20:01,750 then you're not allowed to sign it. 477 00:20:01,750 --> 00:20:04,740 Um, if you have the empty string coming in 478 00:20:04,740 --> 00:20:09,600 then the signature is simply your secret key. 479 00:20:09,600 --> 00:20:11,780 So you reveal your secret key 480 00:20:11,780 --> 00:20:13,610 and the whole idea of hash-based crypto 481 00:20:13,610 --> 00:20:16,160 is that somebody can publicly check 482 00:20:16,160 --> 00:20:18,650 the hashes of something that you reveal 483 00:20:18,650 --> 00:20:22,220 to sign, in this case, the empty message. 484 00:20:22,220 --> 00:20:23,860 And we'll see later how you can use the same idea 485 00:20:23,860 --> 00:20:25,390 to sign lots more. 486 00:20:25,390 --> 00:20:27,030 And then, okay, verification, 487 00:20:27,030 --> 00:20:29,270 you simply checked that signedmessage, 488 00:20:29,270 --> 00:20:31,340 which is supposed to be the secret key, 489 00:20:31,340 --> 00:20:32,480 check its hash 490 00:20:32,480 --> 00:20:34,480 and see if that matches the public key. 491 00:20:34,480 --> 00:20:36,120 What would somebody have to do to attack this? 492 00:20:36,120 --> 00:20:37,360 He would have to, 493 00:20:37,360 --> 00:20:39,549 if you haven't actually signed a message, 494 00:20:39,549 --> 00:20:40,540 the one message, 495 00:20:40,540 --> 00:20:41,710 then he would have to figure out 496 00:20:41,710 --> 00:20:45,010 some string that, when you hash it, 497 00:20:45,010 --> 00:20:46,510 gives this public key. 498 00:20:46,510 --> 00:20:48,460 And, well, that public key, 499 00:20:48,460 --> 00:20:50,260 this is a preimage problem, 500 00:20:50,260 --> 00:20:51,760 inverting the hash function. 501 00:20:51,760 --> 00:20:53,580 The hash is supposed to be one-way, 502 00:20:53,580 --> 00:20:55,460 if the input were low-entropy, 503 00:20:55,460 --> 00:20:56,860 then this would be doable, 504 00:20:56,860 --> 00:20:59,140 but the input was a 32-byte random string, 505 00:20:59,140 --> 00:21:00,760 so nobody will be able to guess that, 506 00:21:00,760 --> 00:21:03,730 or find any other string that passes this. 507 00:21:03,730 --> 00:21:05,410 And then you return the message 508 00:21:05,410 --> 00:21:06,660 and you can try this out 509 00:21:06,660 --> 00:21:08,240 and see that it works. 510 00:21:08,240 --> 00:21:09,610 Alright, let's move on. 511 00:21:09,610 --> 00:21:11,470 We've managed to sign empty messages. 512 00:21:11,470 --> 00:21:13,790 How about signing 0 or 1? 513 00:21:13,790 --> 00:21:15,929 So now we'll make a signature system 514 00:21:15,929 --> 00:21:18,270 where your key can sign 0 515 00:21:18,270 --> 00:21:19,730 and your key can sign 1. 516 00:21:19,730 --> 00:21:22,400 And, well, this is going to be kind of stupid, 517 00:21:22,400 --> 00:21:24,850 what you do is, you make two keys, 518 00:21:24,850 --> 00:21:26,480 one of them is signing 0, 519 00:21:26,480 --> 00:21:28,370 and the other one is signing 1. 520 00:21:28,370 --> 00:21:31,600 You can see how complicated this hash-based signature stuff is, 521 00:21:31,600 --> 00:21:34,460 it's, okay, you put two keys together, 522 00:21:34,460 --> 00:21:36,450 you make one key that will sign 0, 523 00:21:36,450 --> 00:21:37,470 one key that will sign 1, 524 00:21:37,470 --> 00:21:38,610 concatenate the public keys, 525 00:21:38,610 --> 00:21:40,130 concatenate the secret keys, 526 00:21:40,130 --> 00:21:42,520 the p0+p1, s0+s1, 527 00:21:42,520 --> 00:21:43,880 and then if you want to sign, then, 528 00:21:43,880 --> 00:21:45,860 well, if you're signing 0, 529 00:21:45,860 --> 00:21:48,020 now the messages being signed are integers now 530 00:21:48,020 --> 00:21:49,490 instead the empty string, 531 00:21:49,490 --> 00:21:50,670 if you want to sign 0, 532 00:21:50,670 --> 00:21:51,940 then the signed message will be 533 00:21:51,940 --> 00:21:55,830 the string "0", followed by the 32 bytes, 534 00:21:55,830 --> 00:21:59,059 well, this is again more complicated than it has to be, 535 00:21:59,059 --> 00:22:01,400 but think of this as signing the empty message 536 00:22:01,400 --> 00:22:03,460 with the empty signature system, 537 00:22:03,460 --> 00:22:06,540 which is just copying the 32 bytes of the secret key. 538 00:22:06,540 --> 00:22:08,410 And then if you want to sign message 1, 539 00:22:08,410 --> 00:22:12,240 then you do that with the other 32 bytes of the secret key. 540 00:22:12,240 --> 00:22:13,770 And then, to verify it, 541 00:22:13,770 --> 00:22:16,100 well, just whether the signed message is 0 or 1, 542 00:22:16,100 --> 00:22:18,150 just do the obvious thing. 543 00:22:18,150 --> 00:22:19,950 Maybe I should emphasise this code 544 00:22:19,950 --> 00:22:22,440 was written just for this talk, 545 00:22:22,440 --> 00:22:24,179 it has not been reviewed, 546 00:22:24,179 --> 00:22:25,860 and you should audit everything. 547 00:22:25,860 --> 00:22:26,809 You know, you might feel like 548 00:22:26,809 --> 00:22:28,990 six lines of code, you can't possibly screw it up, 549 00:22:28,990 --> 00:22:32,530 but, don't ever use code like that in crypto. 550 00:22:32,530 --> 00:22:34,760 So, this is just meant for you to understand 551 00:22:34,760 --> 00:22:35,700 what this is supposed to be doing, 552 00:22:35,700 --> 00:22:36,860 this has not passed review. 553 00:22:36,860 --> 00:22:39,640 But, I like to think it would pass review. 554 00:22:39,640 --> 00:22:41,650 Um, okay, if you try 555 00:22:41,650 --> 00:22:44,570 signing the 1 message, for example, 556 00:22:44,570 --> 00:22:47,549 and take the signed 1 message and open that signed message, 557 00:22:47,549 --> 00:22:49,360 you do get the integer 1 back. 558 00:22:49,360 --> 00:22:50,470 And if you try forging it, 559 00:22:50,470 --> 00:22:51,600 you're again faced with this problem 560 00:22:51,600 --> 00:22:53,980 of coming up with some 32-byte string 561 00:22:53,980 --> 00:22:56,580 that hashes to a particular result. 562 00:22:56,580 --> 00:22:59,790 Alright, let's move on to 4-bit messages! 563 00:22:59,790 --> 00:23:02,440 So, I promise I won't do every possible length. 564 00:23:02,440 --> 00:23:04,610 But, 4 bits, this will make an important point 565 00:23:04,610 --> 00:23:06,600 that you don't see from 1 bit. 566 00:23:06,600 --> 00:23:08,720 Let's try to sign a 4-bit message 567 00:23:08,720 --> 00:23:11,150 by signing each of the four bits. 568 00:23:11,150 --> 00:23:13,960 This all scales up to signing 1000 bits if you want. 569 00:23:13,960 --> 00:23:17,950 Um, so, okay, let's make 4 sign-bit keypairs 570 00:23:17,950 --> 00:23:21,179 where each of those was two 32-byte hashes, 571 00:23:21,179 --> 00:23:25,590 I mean, each secret key is two 32-byte random strings 572 00:23:25,590 --> 00:23:29,380 and each of the public keys is the hash of those 32-byte random strings. 573 00:23:29,380 --> 00:23:31,970 Make 4 of those pairs and concatenate them 574 00:23:31,970 --> 00:23:34,950 to make some new public keys and secret keys. 575 00:23:34,950 --> 00:23:38,489 Alright, and now to sign a message, well, you look at the message 576 00:23:38,489 --> 00:23:41,179 and check, is it an integer between 0 and 15, 577 00:23:41,179 --> 00:23:42,580 and reject otherwise, 578 00:23:42,580 --> 00:23:44,960 and then sign each bit of the message. 579 00:23:44,960 --> 00:23:47,850 You can see m shifted right by 0, 1, 2, 3, 580 00:23:47,850 --> 00:23:49,750 extract the bottom bit of each of those, 581 00:23:49,750 --> 00:23:51,690 and then sign each of those bits, 582 00:23:51,690 --> 00:23:53,730 and then concatenate the signatures 583 00:23:53,730 --> 00:23:56,970 to get, well, signatures of the four bits of the message. 584 00:23:56,970 --> 00:24:00,200 And then verification works the way you expect 585 00:24:00,200 --> 00:24:02,750 and I'll just skip that. 586 00:24:02,750 --> 00:24:04,290 Alright, this has a problem. 587 00:24:04,290 --> 00:24:06,919 That if you use this signature system 588 00:24:06,919 --> 00:24:09,960 to sign two different messages, 589 00:24:09,960 --> 00:24:13,360 then you might actually allow forgeries. 590 00:24:13,360 --> 00:24:14,620 So let's look, for example, 591 00:24:14,620 --> 00:24:18,100 suppose you sign 11 and you sign 7. 592 00:24:18,100 --> 00:24:20,200 Now what is that signature of 11, 593 00:24:20,200 --> 00:24:22,799 11, uh-oh, I have to do 11 in binary now, 594 00:24:22,799 --> 00:24:27,260 so 11 sounds like 8+2+1. 595 00:24:27,260 --> 00:24:30,990 And you sign 7, which is 4+2+1. 596 00:24:30,990 --> 00:24:32,679 So what if you revealed now? 597 00:24:32,679 --> 00:24:35,510 You reveal the signature on that 8, 598 00:24:35,510 --> 00:24:38,090 so the 3rd bit you revealed 599 00:24:38,090 --> 00:24:41,330 a signature saying, "the 3rd bit is 1" 600 00:24:41,330 --> 00:24:43,390 as part of the signature of 11. 601 00:24:43,390 --> 00:24:45,350 But as part of the signature of 7, 602 00:24:45,350 --> 00:24:47,330 you revealed, you signed a message 603 00:24:47,330 --> 00:24:50,419 saying "the 3rd bit is 0". 604 00:24:50,419 --> 00:24:52,600 And now you can just mix and match those messages, 605 00:24:52,600 --> 00:24:53,830 wherever the bits were different. 606 00:24:53,830 --> 00:24:56,120 So for instance if you take the top bit from the 11 607 00:24:56,120 --> 00:24:58,970 and the bottom 3 bits from the 7 608 00:24:58,970 --> 00:25:00,830 then you end up signing 15. 609 00:25:00,830 --> 00:25:02,990 So this signature system, 610 00:25:02,990 --> 00:25:05,870 it's totally safe if you're signing one message. 611 00:25:05,870 --> 00:25:07,200 But if you think about the data flow, 612 00:25:07,200 --> 00:25:09,510 what does it mean to sign the individual bits 613 00:25:09,510 --> 00:25:11,270 of two different messages, 614 00:25:11,270 --> 00:25:12,669 then you can get in big trouble. 615 00:25:12,669 --> 00:25:15,809 So this is a one-time signature system. 616 00:25:15,809 --> 00:25:19,140 Alright. Here's how Lamport's signature system 617 00:25:19,140 --> 00:25:21,110 works for one-time signatures 618 00:25:21,110 --> 00:25:22,919 of any length of message. 619 00:25:22,919 --> 00:25:26,559 First of all, you scale that 4 bits up to 256 bits. 620 00:25:26,559 --> 00:25:28,600 And then, if you want to sign whatever length of message, 621 00:25:28,600 --> 00:25:32,460 you just hash the message to 256 bits. 622 00:25:32,460 --> 00:25:34,690 And the code for it is very simple. 623 00:25:34,690 --> 00:25:36,299 This is not quite the state of the art 624 00:25:36,299 --> 00:25:37,540 for one-time signatures, 625 00:25:37,540 --> 00:25:38,630 there's fancier things you can do, 626 00:25:38,630 --> 00:25:41,160 you can sign with Winternitz signatures 627 00:25:41,160 --> 00:25:46,260 and get instead of something like 256 or 512 hash values 628 00:25:46,260 --> 00:25:47,740 you can compress that down to like 629 00:25:47,740 --> 00:25:49,760 50 or even fewer hash values. 630 00:25:49,760 --> 00:25:52,410 There's all sorts of tricks to trade space for time 631 00:25:52,410 --> 00:25:53,049 in these systems 632 00:25:53,049 --> 00:25:56,010 but it's totally feasible to deploy Lamport signatures 633 00:25:56,010 --> 00:26:00,270 and, well, Winternitz makes it even more practical. 634 00:26:00,270 --> 00:26:02,690 Alright. What about this one-time restriction? 635 00:26:02,690 --> 00:26:04,110 So these last, the 4-bit, 636 00:26:04,110 --> 00:26:05,980 and the Lamport bigger message system, 637 00:26:05,980 --> 00:26:07,309 these are only usable for, 638 00:26:07,309 --> 00:26:08,790 you can only use your key 639 00:26:08,790 --> 00:26:10,620 to sign one message. 640 00:26:10,620 --> 00:26:13,030 And this was fixed by Merkle. 641 00:26:13,030 --> 00:26:14,690 What Merkle said was, 642 00:26:14,690 --> 00:26:18,980 you take 8 Lamport, for example 8, it can be any number, 643 00:26:18,980 --> 00:26:20,299 here's how we'll make a public key 644 00:26:20,299 --> 00:26:22,510 that can sign 8 different messages. 645 00:26:22,510 --> 00:26:24,990 You make, well, 8 different Lamport keys 646 00:26:24,990 --> 00:26:26,620 and you concatenate them together 647 00:26:26,620 --> 00:26:28,299 and you use each one just once. 648 00:26:28,299 --> 00:26:31,410 But it's actually more space-efficient than that sounds. 649 00:26:31,410 --> 00:26:33,130 So here's what you send along. 650 00:26:33,130 --> 00:26:38,780 You make 8 Ss there, those are the secret Lamport keys, 651 00:26:38,780 --> 00:26:41,130 that are able to each sign one message, 652 00:26:41,130 --> 00:26:43,400 and then you have 8 corresponding public keys, 653 00:26:43,400 --> 00:26:45,490 P1 through P8, 654 00:26:45,490 --> 00:26:48,040 and then you hash together in a tree, 655 00:26:48,040 --> 00:26:52,049 you hash together P1 and P2, and P3 and P4 656 00:26:52,049 --> 00:26:53,380 to form P9 and P10, 657 00:26:53,380 --> 00:26:55,059 and hash those together to get P13, 658 00:26:55,059 --> 00:26:58,510 and same over here to get a final public key P15. 659 00:26:58,510 --> 00:27:01,330 So just one hash value, that's your whole public key. 660 00:27:01,330 --> 00:27:03,679 And then you have to remember lots of secrets, 661 00:27:03,679 --> 00:27:06,040 but, okay, nobody has to see those secrets, 662 00:27:06,040 --> 00:27:08,150 you just keep them on your computer. 663 00:27:08,150 --> 00:27:09,270 And now what does it look like to, 664 00:27:09,270 --> 00:27:13,410 to hash, sorry, to sign one message? 665 00:27:13,410 --> 00:27:17,140 Well, here's what it looks like signing the first message. 666 00:27:17,140 --> 00:27:18,760 That's when you use S1. 667 00:27:18,760 --> 00:27:21,059 Once you use S1, you cross it out, 668 00:27:21,059 --> 00:27:21,940 you never use it again, 669 00:27:21,940 --> 00:27:23,419 you kill the secret. 670 00:27:23,419 --> 00:27:25,910 You sign your message with S1, 671 00:27:25,910 --> 00:27:27,200 and somebody can verify, 672 00:27:27,200 --> 00:27:30,760 if they see the public key P1 for Lamport signatures. 673 00:27:30,760 --> 00:27:32,309 Or whatever one-time signature system 674 00:27:32,309 --> 00:27:33,709 you put at the top. 675 00:27:33,709 --> 00:27:36,870 But, well, your public key in Merkle systems is P15. 676 00:27:36,870 --> 00:27:40,050 And how does somebody verify that P1 and P15 are related? 677 00:27:40,050 --> 00:27:44,770 Well, you show them the P2 and the P10 and the P14 678 00:27:44,770 --> 00:27:47,049 that they need to hash together with P1 679 00:27:47,049 --> 00:27:49,990 to get your public key, P15. 680 00:27:49,990 --> 00:27:52,210 Alright, and that's as complicated 681 00:27:52,210 --> 00:27:53,809 as the Merkle signature system gets, 682 00:27:53,809 --> 00:27:55,880 if you want to be able to sign a million messages, 683 00:27:55,880 --> 00:27:57,340 you have to have a million secrets, 684 00:27:57,340 --> 00:27:59,350 but, again, just put it on your local hard drive, 685 00:27:59,350 --> 00:28:00,900 you're not worried about the space. 686 00:28:00,900 --> 00:28:03,580 It takes a few moments to generate the key, 687 00:28:03,580 --> 00:28:06,059 but that's also not a problem. 688 00:28:06,059 --> 00:28:07,620 Okay. 689 00:28:07,620 --> 00:28:09,160 Good things about hash-based signatures, 690 00:28:09,160 --> 00:28:10,490 and a few bad things. 691 00:28:10,490 --> 00:28:12,309 Good things: It's post-quantum secure, 692 00:28:12,309 --> 00:28:15,610 we totally understand what hash function security looks like, 693 00:28:15,610 --> 00:28:19,080 after quantum computers and before quantum computers, 694 00:28:19,080 --> 00:28:20,730 all you need is a good hash function, 695 00:28:20,730 --> 00:28:21,830 and there's lots of hash functions 696 00:28:21,830 --> 00:28:23,330 which have been thoroughly studied, 697 00:28:23,330 --> 00:28:25,110 so, we're confident they're secure, 698 00:28:25,110 --> 00:28:27,460 SHA-3 was the result of a long competition 699 00:28:27,460 --> 00:28:28,990 with lots of people bashing on it, 700 00:28:28,990 --> 00:28:30,850 and really has no problems. 701 00:28:30,850 --> 00:28:32,220 The public key is very small, 702 00:28:32,220 --> 00:28:34,419 just one hash value. 703 00:28:34,419 --> 00:28:37,360 The security, as I said, is well-understood. 704 00:28:37,360 --> 00:28:39,840 All the computations are very fast, 705 00:28:39,840 --> 00:28:41,860 and you can already find standard proposals 706 00:28:41,860 --> 00:28:42,900 for this system. 707 00:28:42,900 --> 00:28:45,679 This is going to be the first standardised 708 00:28:45,679 --> 00:28:50,470 and the first deployed post-quantum public key system. 709 00:28:50,470 --> 00:28:54,000 On the other hand, if you look at the signature size, 710 00:28:54,000 --> 00:28:55,380 it's kind of big, 711 00:28:55,380 --> 00:28:56,740 and then the more scary thing 712 00:28:56,740 --> 00:28:59,210 is the statefulness. 713 00:28:59,210 --> 00:29:01,030 That you can only use S1 once, 714 00:29:01,030 --> 00:29:02,850 and then you have to cross it out. 715 00:29:02,850 --> 00:29:05,039 You can only use S2 once, and you have to cross it out. 716 00:29:05,039 --> 00:29:06,330 What if you clone your VM? 717 00:29:06,330 --> 00:29:08,220 What if you have a backup and restore? 718 00:29:08,220 --> 00:29:11,250 Then, you've forgotten that you've used S2. 719 00:29:11,250 --> 00:29:12,179 And then you use it again, 720 00:29:12,179 --> 00:29:14,470 and then somebody can forge messages, 721 00:29:14,470 --> 00:29:17,010 just like I was saying before. 722 00:29:17,010 --> 00:29:18,760 Alright, so state is a problem, 723 00:29:18,760 --> 00:29:20,130 actually some of you I'm sure were 724 00:29:20,130 --> 00:29:22,289 in Rutkowska's talk earlier today 725 00:29:22,289 --> 00:29:24,520 you also heard that state is harmful there. 726 00:29:24,520 --> 00:29:26,910 And the solution: 727 00:29:26,910 --> 00:29:29,969 Eliminate the state! 728 00:29:29,969 --> 00:29:36,360 *applause* 729 00:29:36,360 --> 00:29:38,360 I think I only have about three minutes left 730 00:29:38,360 --> 00:29:41,210 for this, this section, well, this slide, 731 00:29:41,210 --> 00:29:45,450 but, let me try to briefly say, the idea for getting rid of the state 732 00:29:45,450 --> 00:29:47,929 is, you have, instead of signatures, 733 00:29:47,929 --> 00:29:49,860 you have certificate chains. 734 00:29:49,860 --> 00:29:53,110 So you have whole chain of CAs, 735 00:29:53,110 --> 00:29:55,730 like, as a signer, you build a whole bunch of CAs, 736 00:29:55,730 --> 00:29:59,300 you build, say, 2^256 certificate authorities. 737 00:29:59,300 --> 00:30:00,990 Now, that's too much computation to do, 738 00:30:00,990 --> 00:30:03,010 but you do it on the fly, as you need them. 739 00:30:03,010 --> 00:30:04,900 So you say, I'm going to sign 740 00:30:04,900 --> 00:30:08,450 using one of these bottom-level certificate authorities, 741 00:30:08,450 --> 00:30:10,580 that will sign my actual message. 742 00:30:10,580 --> 00:30:13,200 And now, you don't have to know anything about any of the others, 743 00:30:13,200 --> 00:30:16,809 you just pick one and use that to sign your message. 744 00:30:16,809 --> 00:30:19,570 And then it has to be signed by the parent CA, 745 00:30:19,570 --> 00:30:20,850 and that's signed by the next parent, 746 00:30:20,850 --> 00:30:22,870 and so on, up the tree, to the top level, 747 00:30:22,870 --> 00:30:24,460 only 256 levels. 748 00:30:24,460 --> 00:30:28,200 And then, okay, you have your certificate chain, 749 00:30:28,200 --> 00:30:30,950 how do you manufacture these certificate authorities? 750 00:30:30,950 --> 00:30:35,950 Well, a certificate authority is just some bytes of code on disk, 751 00:30:35,950 --> 00:30:37,450 that's what real CAs are like, 752 00:30:37,450 --> 00:30:39,120 and you do the same thing signing, 753 00:30:39,120 --> 00:30:41,330 and, those bytes of code, you can, 754 00:30:41,330 --> 00:30:46,030 instead of storing the CA as a program in a configuration file on disk, 755 00:30:46,030 --> 00:30:48,590 you just generate it on the fly when you need it, 756 00:30:48,590 --> 00:30:52,370 by taking the position of the CA within this huge tree 757 00:30:52,370 --> 00:30:56,210 and then hashing that together with some long-term secret. 758 00:30:56,210 --> 00:30:59,419 That one long-term secret is the only thing you remember. 759 00:30:59,419 --> 00:31:01,809 So you can manufacture CAs on demand 760 00:31:01,809 --> 00:31:03,100 in some huge tree 761 00:31:03,100 --> 00:31:05,570 and have them sign certificates for each other 762 00:31:05,570 --> 00:31:08,020 only looking at a few CAs that you need 763 00:31:08,020 --> 00:31:11,000 for the particular signature that you want. 764 00:31:11,000 --> 00:31:12,409 The reason for having this big tree 765 00:31:12,409 --> 00:31:14,030 is that then you're never going 766 00:31:14,030 --> 00:31:17,880 to randomly use the same CA at the bottom twice. 767 00:31:17,880 --> 00:31:20,470 So the problem of having one-time signatures 768 00:31:20,470 --> 00:31:21,690 is no longer a problem. 769 00:31:21,690 --> 00:31:24,690 Each CA will only sign one message. 770 00:31:24,690 --> 00:31:26,500 Okay, and this is something where 771 00:31:26,500 --> 00:31:30,309 the original proposal from Goldreich in 87, 772 00:31:30,309 --> 00:31:32,440 if you use good one-time signatures, 773 00:31:32,440 --> 00:31:33,809 Winternitz and all that stuff, 774 00:31:33,809 --> 00:31:38,250 you get something like 0.6 megs for a signature. 775 00:31:38,250 --> 00:31:40,760 Now that's a little bit inconvenient, 776 00:31:40,760 --> 00:31:43,130 for comparison, if you do an OS update, 777 00:31:43,130 --> 00:31:45,580 you look at the average Debian packet size, 778 00:31:45,580 --> 00:31:47,700 then it's 1.2 megs. 779 00:31:47,700 --> 00:31:49,900 And then, there is some number of signatures 780 00:31:49,900 --> 00:31:53,419 with each update, and some of them are in packages, 781 00:31:53,419 --> 00:31:55,490 and well, it's not inconceivable 782 00:31:55,490 --> 00:31:57,460 to send 0.6 megs for each signature, 783 00:31:57,460 --> 00:31:58,799 but it's kind of big. 784 00:31:58,799 --> 00:32:00,940 And then if you look at, well, 785 00:32:00,940 --> 00:32:03,470 web pages, say the Alexa top million web pages, 786 00:32:03,470 --> 00:32:06,860 that average is 1.8 megs. 787 00:32:06,860 --> 00:32:09,150 And again there's several signatures on the web page, 788 00:32:09,150 --> 00:32:13,159 depending how many sites are providing graphics for it and so on. 789 00:32:13,159 --> 00:32:14,860 So, 0.6 megs is maybe a problem. 790 00:32:14,860 --> 00:32:17,720 But, okay, we took a look at this and 791 00:32:17,720 --> 00:32:21,520 a bunch of people made the signature a lot smaller, 792 00:32:21,520 --> 00:32:24,020 0.041 megabytes. 793 00:32:24,020 --> 00:32:27,059 You know how to make a 41-kilobyte signature sound small: 794 00:32:27,059 --> 00:32:34,250 only 0.041 megabytes for a sphincs 2^128 post-quantum secure signature system. 795 00:32:34,250 --> 00:32:36,080 If you're interested in more about what sphincs does, 796 00:32:36,080 --> 00:32:39,830 go to sphincs.cr.yp.to 797 00:32:39,830 --> 00:32:41,500 Lange: Alright, so. 798 00:32:41,500 --> 00:32:44,970 Now we have some idea of how we can do signatures. 799 00:32:44,970 --> 00:32:46,819 And signature's just the thing 800 00:32:46,819 --> 00:32:48,760 that quantum crypto really really can't do, 801 00:32:48,760 --> 00:32:51,549 I mean, also, locked briefcases, 802 00:32:51,549 --> 00:32:56,039 how do you trust that this is actually your locked briefcase? 803 00:32:56,039 --> 00:32:58,940 But also, public key crypto is a problem. 804 00:32:58,940 --> 00:33:01,820 So, the one that we recommend 805 00:33:01,820 --> 00:33:03,340 is code-based cryptography, 806 00:33:03,340 --> 00:33:05,250 and code, in this context, is not like 807 00:33:05,250 --> 00:33:07,309 code as in writing a program 808 00:33:07,309 --> 00:33:10,220 but it comes from error-correcting codes. 809 00:33:10,220 --> 00:33:12,140 So when you think about, say, your computer, 810 00:33:12,140 --> 00:33:13,960 you have RAM in there 811 00:33:13,960 --> 00:33:17,750 and this RAM might get cosmic radiation 812 00:33:17,750 --> 00:33:19,610 or just a bump somewhere, 813 00:33:19,610 --> 00:33:20,730 might forget something. 814 00:33:20,730 --> 00:33:22,280 Or, a more trivial example, 815 00:33:22,280 --> 00:33:25,090 if you order a book, or, nowadays, 816 00:33:25,090 --> 00:33:26,739 order any media, 817 00:33:26,739 --> 00:33:29,280 it has an ISBN number. 818 00:33:29,280 --> 00:33:32,950 This last digit is dependent on the previous digits. 819 00:33:32,950 --> 00:33:35,080 So they can figure out whether any of the digits before 820 00:33:35,080 --> 00:33:37,549 was mistransmitted 821 00:33:37,549 --> 00:33:39,360 then then go like, hmm, 822 00:33:39,360 --> 00:33:41,390 that number doesn't exist, try again. 823 00:33:41,390 --> 00:33:44,990 With your ECC RAM it's actually a little more sophisticated. 824 00:33:44,990 --> 00:33:46,919 So you have your RAM sitting there, 825 00:33:46,919 --> 00:33:50,190 and it stores 64 bits. 826 00:33:50,190 --> 00:33:53,950 But it stores these 64 bits with some redundancy. 827 00:33:53,950 --> 00:33:57,360 Internally, it has some extra check bits. 828 00:33:57,360 --> 00:34:00,600 It stores 8 extra bits 829 00:34:00,600 --> 00:34:02,080 and those 8 extra bits allow you 830 00:34:02,080 --> 00:34:05,850 to recover the 64 that you're interested in 831 00:34:05,850 --> 00:34:08,190 in case there was some error. 832 00:34:08,190 --> 00:34:09,339 Not in case of a massive error, 833 00:34:09,339 --> 00:34:12,619 not in case somebody took a screwdriver and hit it, 834 00:34:12,619 --> 00:34:14,639 but if there was just one random bit flip, 835 00:34:14,639 --> 00:34:16,268 you can recover it. 836 00:34:16,268 --> 00:34:18,210 Also, if two bits flip, 837 00:34:18,210 --> 00:34:20,289 you can at least figure out that there was something 838 00:34:20,289 --> 00:34:22,190 and raise a flag. 839 00:34:22,190 --> 00:34:24,079 So the common scenario in error correction 840 00:34:24,079 --> 00:34:30,319 is that we have a certain number, say, k bits that we care about 841 00:34:30,319 --> 00:34:34,199 and then in order to be able to recover those, 842 00:34:34,199 --> 00:34:35,199 to correct those, 843 00:34:35,199 --> 00:34:37,248 we add some redundancy. 844 00:34:37,248 --> 00:34:39,869 So we encapsulate, we encode those k bits 845 00:34:39,869 --> 00:34:41,569 into n bits. 846 00:34:41,569 --> 00:34:44,859 Now, we would like to have those n bits 847 00:34:44,859 --> 00:34:48,109 be not too much larger than k. 848 00:34:48,109 --> 00:34:50,029 We call those the parity check, 849 00:34:50,029 --> 00:34:52,239 so this is like from the old days where you check 850 00:34:52,239 --> 00:34:55,599 "those two add up to zero, zero zero zero... 851 00:34:55,599 --> 00:34:58,819 oops! there's one, aha, there must have been one bit flip." 852 00:34:58,819 --> 00:35:03,630 So parity as in, it has to be an even number at the end. 853 00:35:03,630 --> 00:35:04,960 If you're talking about more positions 854 00:35:04,960 --> 00:35:07,160 then it's obviously more than just the parity 855 00:35:07,160 --> 00:35:10,479 but it's parity of some more complicated equations. 856 00:35:10,479 --> 00:35:17,009 So, if no error occurred, if those 64 bits in your ECC RAM are just fine, 857 00:35:17,009 --> 00:35:21,969 then all those extra n-k checks will be okay. 858 00:35:21,969 --> 00:35:25,589 If there was an error, then something will fail, 859 00:35:25,589 --> 00:35:26,309 raise a flag, 860 00:35:26,309 --> 00:35:29,180 1, 2, 3 of those will not be satisfied, 861 00:35:29,180 --> 00:35:32,170 and depending on this error pattern, 862 00:35:32,170 --> 00:35:36,619 you will be able to recover what was going wrong in those bits. 863 00:35:36,619 --> 00:35:39,289 It might actually be that it was your parity check bits. 864 00:35:39,289 --> 00:35:42,289 It might be that one of those 8 extra bits flipped. 865 00:35:42,289 --> 00:35:45,729 In which case, your 64 bits were just fine 866 00:35:45,729 --> 00:35:49,649 but you don't know this when you get the error message. 867 00:35:49,649 --> 00:35:51,759 And, if you have a good code, 868 00:35:51,759 --> 00:35:54,359 so the kind of code that coding theorists study, 869 00:35:54,359 --> 00:35:55,339 then you would like to have 870 00:35:55,339 --> 00:35:59,890 your k pretty large, and the n not too much larger. 871 00:35:59,890 --> 00:36:02,549 Because that's the amount of storage 872 00:36:02,549 --> 00:36:03,519 you actually have to afford 873 00:36:03,519 --> 00:36:07,339 for just getting this much data out of it. 874 00:36:07,339 --> 00:36:11,400 Now, we get some guarantees when we design these, 875 00:36:11,400 --> 00:36:14,269 there's a guarantee of getting t errors, 876 00:36:14,269 --> 00:36:15,729 but for most of the codes that we know, 877 00:36:15,729 --> 00:36:17,489 the guarantees are actually worse 878 00:36:17,489 --> 00:36:19,029 than we get in practice, 879 00:36:19,029 --> 00:36:21,729 so if something guarantees you 100 errors, 880 00:36:21,729 --> 00:36:25,750 most of the time, you can actually correct 203. 881 00:36:25,750 --> 00:36:27,249 Um, to get a little bit further 882 00:36:27,249 --> 00:36:32,930 we actually did to, um, represent those equations with matrix, 883 00:36:32,930 --> 00:36:37,349 um, not quite this one, sorry. 884 00:36:37,349 --> 00:36:40,569 So, here's our equations. 885 00:36:40,569 --> 00:36:45,440 So, small example, we would like to encode 4 bits, 886 00:36:45,440 --> 00:36:46,900 k is 4, 887 00:36:46,900 --> 00:36:49,479 and we're adding 3 extra bits. 888 00:36:49,479 --> 00:36:50,809 That's not very efficient, 889 00:36:50,809 --> 00:36:54,789 but it's a very nice example that one can see. 890 00:36:54,789 --> 00:37:01,339 So, those rows there are our parity equations. 891 00:37:01,339 --> 00:37:03,160 So let's assume we have those 7 bits, 892 00:37:03,160 --> 00:37:05,549 which add redundancy to it, 893 00:37:05,549 --> 00:37:07,499 then let's translate this first row, 894 00:37:07,499 --> 00:37:10,410 which is 1 0 0 1 1 0 1, 895 00:37:10,410 --> 00:37:13,130 that means we take the first bit, 896 00:37:13,130 --> 00:37:14,690 skip the second and third, 897 00:37:14,690 --> 00:37:16,769 so, have be 0, 898 00:37:16,769 --> 00:37:19,469 and then, bit 3, then the next bit is set 899 00:37:19,469 --> 00:37:23,119 so bit 4, and then bit 6. 900 00:37:23,119 --> 00:37:24,969 Second row, similarly, we skip the first one, 901 00:37:24,969 --> 00:37:26,859 so there's no bit 0, there's a bit 1, 902 00:37:26,859 --> 00:37:28,479 no bit 2, there's a bit 3, 903 00:37:28,479 --> 00:37:30,759 it was a 1 1 0 column, 904 00:37:30,759 --> 00:37:32,979 and then bit 5 and bit 6, 905 00:37:32,979 --> 00:37:33,930 and similarly. 906 00:37:33,930 --> 00:37:38,279 So we have a nice diagonal on the left-hand side, 907 00:37:38,279 --> 00:37:41,589 and then the rest is determined by these equations. 908 00:37:41,589 --> 00:37:44,140 Now let's assume that something went wrong. 909 00:37:44,140 --> 00:37:46,049 So we have our 7 bits here, 910 00:37:46,049 --> 00:37:48,509 and a few hours later we come back 911 00:37:48,509 --> 00:37:50,630 and want to look at those 7 bits, 912 00:37:50,630 --> 00:37:52,160 we check whether anything went wrong, 913 00:37:52,160 --> 00:37:55,619 we run through this parity check program, 914 00:37:55,619 --> 00:37:58,869 and we actually get a failure pattern. 915 00:37:58,869 --> 00:38:01,790 If everything was fine, we would have gotten 0 0 0, 916 00:38:01,790 --> 00:38:05,900 but we're getting 1 0 1. 917 00:38:05,900 --> 00:38:08,229 So the first equation doesn't hold, 918 00:38:08,229 --> 00:38:10,219 the second one does hold, 919 00:38:10,219 --> 00:38:13,349 and the third one does not hold. 920 00:38:13,349 --> 00:38:17,239 Okay. Where could this come from? 921 00:38:17,239 --> 00:38:19,239 We're pretty sure that b1 is okay 922 00:38:19,239 --> 00:38:21,569 because otherwise the second equation would be wrong 923 00:38:21,569 --> 00:38:24,509 because b1 only appears there, 924 00:38:24,509 --> 00:38:25,880 and we're also making the promise 925 00:38:25,880 --> 00:38:27,729 that it would be only one error. 926 00:38:27,729 --> 00:38:29,339 If you have two errors, three errors, 927 00:38:29,339 --> 00:38:31,420 then lots of other combinations could occur. 928 00:38:31,420 --> 00:38:33,289 But it's much more likely that one bit flipped 929 00:38:33,289 --> 00:38:36,319 than that a whole bunch of bits flipped at once. 930 00:38:36,319 --> 00:38:39,779 Okay, so, tracing this a little bit further, 931 00:38:39,779 --> 00:38:42,739 yes, so the b3 would get the two first equations, 932 00:38:42,739 --> 00:38:45,059 b4, yes! b4 actually would get 933 00:38:45,059 --> 00:38:48,219 that the first and the third equations are false. 934 00:38:48,219 --> 00:38:50,809 So by seeing the error pattern 1 0 1, 935 00:38:50,809 --> 00:38:53,229 we know it was b4. 936 00:38:53,229 --> 00:38:55,539 Now this is a very nice and small example, 937 00:38:55,539 --> 00:38:57,710 which doesn't even cover like the ECC RAM, 938 00:38:57,710 --> 00:39:00,680 but it gives you an idea of how to try it. 939 00:39:00,680 --> 00:39:02,089 On the other hand, it also gives you 940 00:39:02,089 --> 00:39:04,549 the idea that you need to do kind of 941 00:39:04,549 --> 00:39:07,369 brute force search it. 942 00:39:07,369 --> 00:39:10,549 So for just n=7, you have to try up to 7 times. 943 00:39:10,549 --> 00:39:12,410 If you now have two errors, 944 00:39:12,410 --> 00:39:16,309 I would need to try every combination of 2 945 00:39:16,309 --> 00:39:18,090 out of those n. 946 00:39:18,090 --> 00:39:23,880 If I have a n which is like 2000 bits, really long, 947 00:39:23,880 --> 00:39:27,229 and I tell you there's 100 errors, 948 00:39:27,229 --> 00:39:28,930 so you would need to try every combination 949 00:39:28,930 --> 00:39:31,089 of 100 positions in there. 950 00:39:31,089 --> 00:39:33,569 So that would be a huge number. 951 00:39:33,569 --> 00:39:36,599 That's obviously not a good way of error correction, 952 00:39:36,599 --> 00:39:37,849 and that's certainly not how 953 00:39:37,849 --> 00:39:39,690 DVDs and whatever else works. 954 00:39:39,690 --> 00:39:41,859 Oh yeah, one bit of maths notation, 955 00:39:41,859 --> 00:39:46,449 so, we call these things, the parentheses up there, matrix, 956 00:39:46,449 --> 00:39:47,869 and in order to have a shorthand, 957 00:39:47,869 --> 00:39:54,589 because I can't quite put my 2000 bits times 1000 bits matrix on the page, 958 00:39:54,589 --> 00:39:57,480 I call this thing H, 959 00:39:57,480 --> 00:40:01,239 and boldface b is such a bit vector. 960 00:40:01,239 --> 00:40:04,839 So boldface b is that bits that I'm storing, 961 00:40:04,839 --> 00:40:08,519 and the combination of applying this matrix, 962 00:40:08,519 --> 00:40:11,130 wherever is 1, I take the variable, 963 00:40:11,130 --> 00:40:13,059 where there's a 0, I don't write it, 964 00:40:13,059 --> 00:40:15,380 that I write as H times b. 965 00:40:15,380 --> 00:40:16,499 So in maths, if you have seen this, 966 00:40:16,499 --> 00:40:19,549 this is just a matrix times vector multiplication, 967 00:40:19,549 --> 00:40:24,069 otherwise, just take this as the instruction of evaluating 968 00:40:24,069 --> 00:40:28,710 this, each row, as a set of equations. 969 00:40:28,710 --> 00:40:31,089 Alright, so, to give this some names, 970 00:40:31,089 --> 00:40:33,920 in coding theory we call c the code word, 971 00:40:33,920 --> 00:40:37,209 so that's an element which is not compromised, 972 00:40:37,209 --> 00:40:38,299 which will give you 0, 973 00:40:38,299 --> 00:40:40,229 then there might be an error vector, 974 00:40:40,229 --> 00:40:42,180 that's the bits that flip, 975 00:40:42,180 --> 00:40:44,059 and so, when you retrieve the memory 976 00:40:44,059 --> 00:40:45,779 or when you have a transmission, 977 00:40:45,779 --> 00:40:47,089 we call this the received word, 978 00:40:47,089 --> 00:40:50,239 and that's my b from the previous slide. 979 00:40:50,239 --> 00:40:52,259 We do like to save on space, 980 00:40:52,259 --> 00:40:53,420 so when there's this diagonal 981 00:40:53,420 --> 00:40:55,779 which has all 0s down there 982 00:40:55,779 --> 00:40:58,019 we just skip it. 983 00:40:58,019 --> 00:41:05,959 So instead of writing a 7-by-3, we just write 4 columns and 3 rows. 984 00:41:05,959 --> 00:41:08,200 Now there's lots of stuff happening in coding theory, 985 00:41:08,200 --> 00:41:10,660 it's a, well, 65 years old topic, 986 00:41:10,660 --> 00:41:13,200 and we can go up to very large matrices, 987 00:41:13,200 --> 00:41:16,119 and for some special codes, 988 00:41:16,119 --> 00:41:17,799 these are the ones that coding theorists come up with, 989 00:41:17,799 --> 00:41:19,799 we actually have efficient methods. 990 00:41:19,799 --> 00:41:23,359 Much much nicer than taking every combination of 100 positions 991 00:41:23,359 --> 00:41:26,549 out of 2000 positions. 992 00:41:26,549 --> 00:41:29,200 Of course, if you get too many errors, 993 00:41:29,200 --> 00:41:29,859 you can't correct. 994 00:41:29,859 --> 00:41:32,680 You can only correct up to whatever the promise is, 995 00:41:32,680 --> 00:41:34,640 plus maybe a little bit later. 996 00:41:34,640 --> 00:41:36,549 But if you don't know any of the structure, 997 00:41:36,549 --> 00:41:39,380 if you don't know what the coding theorists put into it, 998 00:41:39,380 --> 00:41:42,729 or if this H matrix got somewhat perturbed 999 00:41:42,729 --> 00:41:47,439 by me giving a slightly different representation, 1000 00:41:47,439 --> 00:41:50,709 I don't call this b1 anymore, I call it now b17, 1001 00:41:50,709 --> 00:41:52,150 and let's flip those and so on, 1002 00:41:52,150 --> 00:41:55,250 suddenly it doesn't look like the code that you're used to. 1003 00:41:55,250 --> 00:41:58,289 If it's a random matrix, 1004 00:41:58,289 --> 00:42:00,200 the best attacks are not quite as bad 1005 00:42:00,200 --> 00:42:02,999 as picking 100 out of 2000, 1006 00:42:02,999 --> 00:42:04,670 but they are close to that, 1007 00:42:04,670 --> 00:42:05,980 they're pretty slow attacks, 1008 00:42:05,980 --> 00:42:08,959 it's an exponential-time algorithm, 1009 00:42:08,959 --> 00:42:11,279 if you have a random matrix. 1010 00:42:11,279 --> 00:42:12,999 And so what we're doing in code-based crypto 1011 00:42:12,999 --> 00:42:16,009 is to use this difference for encryption. 1012 00:42:16,009 --> 00:42:17,599 Now going back again to the 70s, 1013 00:42:17,599 --> 00:42:21,009 so, basically, yes, the stuff that we're really confident in 1014 00:42:21,009 --> 00:42:22,829 that it will last another 100 years, 1015 00:42:22,829 --> 00:42:25,299 is the stuff from the 70s that lots of people have looked at, 1016 00:42:25,299 --> 00:42:27,299 so, McEliece in 1978, 1017 00:42:27,299 --> 00:42:29,779 so just the year after RSA, 1018 00:42:29,779 --> 00:42:35,719 came up with a system which is using encoding as encryption. 1019 00:42:35,719 --> 00:42:38,369 So your method is, 1020 00:42:38,369 --> 00:42:40,930 you just encode a vector, your message, 1021 00:42:40,930 --> 00:42:42,900 and then you add some errors to it. 1022 00:42:42,900 --> 00:42:44,880 And, if the other side doesn't have 1023 00:42:44,880 --> 00:42:47,379 an efficient algorithm to decode, 1024 00:42:47,379 --> 00:42:49,459 they actually can't break it. 1025 00:42:49,459 --> 00:42:51,700 They're using a special code in there, 1026 00:42:51,700 --> 00:42:53,449 so there's a code from Goppa 1027 00:42:53,449 --> 00:42:56,059 from a few years earlier than that, 1028 00:42:56,059 --> 00:42:58,029 and that code, so far, nobody has found 1029 00:42:58,029 --> 00:43:00,819 any way to take the perturbed, 1030 00:43:00,819 --> 00:43:03,119 this complicated way of representing it, 1031 00:43:03,119 --> 00:43:06,549 and coming up with efficient decoding algorithm. 1032 00:43:06,549 --> 00:43:10,660 1986, Niederreither came up with a version of McEliece 1033 00:43:10,660 --> 00:43:13,359 which is smaller, the code size is smaller, 1034 00:43:13,359 --> 00:43:15,529 the public key size is smaller, 1035 00:43:15,529 --> 00:43:19,180 and we have similar things to 1036 00:43:19,180 --> 00:43:21,239 what you've seen before, so we have those H matrix, 1037 00:43:21,239 --> 00:43:22,619 we skip the diagonal, 1038 00:43:22,619 --> 00:43:28,499 we just represent this H as our public key as the remaining part of the matrix, 1039 00:43:28,499 --> 00:43:33,139 the secret key, that's the algorithm that only I know. 1040 00:43:33,139 --> 00:43:34,769 It's a Goppa code, 1041 00:43:34,769 --> 00:43:35,890 but it's a Goppa code 1042 00:43:35,890 --> 00:43:39,259 and there's many many Goppa codes for the same size. 1043 00:43:39,259 --> 00:43:40,549 So that's something that Goppa says, 1044 00:43:40,549 --> 00:43:41,829 well, if you want to have Goppa codes 1045 00:43:41,829 --> 00:43:46,969 with 2000 bits that can correct 200 errors, 1046 00:43:46,969 --> 00:43:47,829 here's how you set it up, 1047 00:43:47,829 --> 00:43:51,200 but there's lots and lots and lots of choices in there. 1048 00:43:51,200 --> 00:43:52,469 And your encryption is just, 1049 00:43:52,469 --> 00:43:54,910 take an error vector, 1050 00:43:54,910 --> 00:43:57,269 with a fixed number of bits, 1051 00:43:57,269 --> 00:43:59,479 and send me the error pattern of it. 1052 00:43:59,479 --> 00:44:04,049 So the outcome of multiplying H by this e. 1053 00:44:04,049 --> 00:44:05,509 And then we want to use this in crypto, 1054 00:44:05,509 --> 00:44:08,209 so we use the hash of this to encrypt it. 1055 00:44:08,209 --> 00:44:12,329 Um, then Peter Schwabe and Tung Chou, our PhD student, 1056 00:44:12,329 --> 00:44:14,349 wrote a very efficient implementation of this 1057 00:44:14,349 --> 00:44:15,729 called mcbits, 1058 00:44:15,729 --> 00:44:17,380 so if you want to have more detail 1059 00:44:17,380 --> 00:44:19,619 on how you could really use this in practice, 1060 00:44:19,619 --> 00:44:21,350 then go to that url. 1061 00:44:21,350 --> 00:44:23,339 Um, but let me talk a little bit 1062 00:44:23,339 --> 00:44:26,130 about why we are confident in this. 1063 00:44:26,130 --> 00:44:28,180 Code-based crypto is less obvious than hash-based, 1064 00:44:28,180 --> 00:44:30,420 I mean with hash-based it's like, 1065 00:44:30,420 --> 00:44:32,079 the, all we're doing is, hash. 1066 00:44:32,079 --> 00:44:35,569 A hash function by definition is something which is one-way. 1067 00:44:35,569 --> 00:44:39,559 For this code-based crypto, you need to think a little more, 1068 00:44:39,559 --> 00:44:41,170 to have people studying it 1069 00:44:41,170 --> 00:44:44,630 to figure out why this actually can be secure. 1070 00:44:44,630 --> 00:44:47,619 Now, the attacks, if I may say so, 1071 00:44:47,619 --> 00:44:49,390 started before the cryptosystem was proposed, 1072 00:44:49,390 --> 00:44:50,999 so it was another hard problem 1073 00:44:50,999 --> 00:44:53,410 that coding theorists were studying naturally, 1074 00:44:53,410 --> 00:44:56,219 and then McEliece said, hey, we have this hard problem here, 1075 00:44:56,219 --> 00:44:58,940 decoding a random code is not easy, 1076 00:44:58,940 --> 00:45:01,539 well, actually, afterwards, figuring out, 1077 00:45:01,539 --> 00:45:05,039 well, if you have a really random code, 1078 00:45:05,039 --> 00:45:07,569 even finding out whether there is a smaller code word is NP-hard. 1079 00:45:07,569 --> 00:45:12,240 And then, once it was a cryptosystem, 1080 00:45:12,240 --> 00:45:14,890 so, Omura, Lee-Brickell, all of those, 1081 00:45:14,890 --> 00:45:17,519 those come after it was proposed for crypto. 1082 00:45:17,519 --> 00:45:20,529 There's some which have an extra parenthetic comment, 1083 00:45:20,529 --> 00:45:23,930 those are papers which study the security of McEliece 1084 00:45:23,930 --> 00:45:25,420 if the attacker has a quantum computer, 1085 00:45:25,420 --> 00:45:27,329 so there's been lots and lots of work 1086 00:45:27,329 --> 00:45:30,420 for studying it against a classical computer, 1087 00:45:30,420 --> 00:45:31,849 and there's been some work 1088 00:45:31,849 --> 00:45:33,719 studying it against quantum computers. 1089 00:45:33,719 --> 00:45:36,170 It's pretty clear that we can't use Shor, 1090 00:45:36,170 --> 00:45:37,390 but we can use Grover, 1091 00:45:37,390 --> 00:45:42,180 and it's not so easily obvious how much Grover can give us. 1092 00:45:42,180 --> 00:45:44,359 However, the best that Grover can do 1093 00:45:44,359 --> 00:45:46,519 is basically halve the bit size. 1094 00:45:46,519 --> 00:45:49,140 So we had this AES-128, leading to 64-bit security, 1095 00:45:49,140 --> 00:45:50,769 so if you're conservative, 1096 00:45:50,769 --> 00:45:54,430 if you want to be like really really on the secure size, 1097 00:45:54,430 --> 00:45:58,559 then let's assume that we want to go for pre-quantum security at least 256 1098 00:45:58,559 --> 00:46:02,469 in order to get post-quantum security 128. 1099 00:46:02,469 --> 00:46:04,440 So here are some key sizes, 1100 00:46:04,440 --> 00:46:07,759 so if you're okay with 1000 kilobytes, 1101 00:46:07,759 --> 00:46:14,690 then you're getting something which is at least 131 post-quantum secure, 1102 00:46:14,690 --> 00:46:17,170 and that's actually very conservative, 1103 00:46:17,170 --> 00:46:20,289 most likely we can go much down on the key size. 1104 00:46:20,289 --> 00:46:22,049 But that's where more research is needed. 1105 00:46:22,049 --> 00:46:25,660 If you need something where you can get a guarantee of 100 years security, 1106 00:46:25,660 --> 00:46:27,349 take this one, 1107 00:46:27,349 --> 00:46:28,809 it's not small, 1108 00:46:28,809 --> 00:46:31,650 it's fast, but it's not small, 1109 00:46:31,650 --> 00:46:34,479 and hopefully in 5 years, less than 5 years, 1110 00:46:34,479 --> 00:46:37,249 they can give you something which is smaller 1111 00:46:37,249 --> 00:46:39,669 and still as secure. 1112 00:46:39,669 --> 00:46:40,380 djb: Okay. 1113 00:46:40,380 --> 00:46:45,079 There are lots of possibilities for what the smaller things might be, 1114 00:46:45,079 --> 00:46:47,919 for instance, there's something called QC-MDPC, 1115 00:46:47,919 --> 00:46:48,930 there's actually lots and lots 1116 00:46:48,930 --> 00:46:50,680 of variations of McEliece 1117 00:46:50,680 --> 00:46:51,599 that people have proposed, 1118 00:46:51,599 --> 00:46:53,849 and some of those variations have held up, 1119 00:46:53,849 --> 00:46:55,109 some of them haven't. 1120 00:46:55,109 --> 00:46:58,479 QC-MDPC is something that has held up so far, 1121 00:46:58,479 --> 00:47:00,339 but how many people've looked at it, 1122 00:47:00,339 --> 00:47:03,539 and what's going to happen when more attacks get optimised? 1123 00:47:03,539 --> 00:47:06,039 You can't be trusting something which 1124 00:47:06,039 --> 00:47:09,140 is new or hasn't been studied enough, 1125 00:47:09,140 --> 00:47:10,849 or hasn't been studied in the right directions, 1126 00:47:10,849 --> 00:47:13,089 you also have to be sceptical about crypto. 1127 00:47:13,089 --> 00:47:14,949 There's, well, lots of proposals, 1128 00:47:14,949 --> 00:47:17,759 QC-MDPC looks like one of the most interesting ones, 1129 00:47:17,759 --> 00:47:20,930 that nobody's been able to damage its security, 1130 00:47:20,930 --> 00:47:23,680 for 2^80 pre-quantum security, 1131 00:47:23,680 --> 00:47:24,819 which is not very good, 1132 00:47:24,819 --> 00:47:26,479 but, just as an example, 1133 00:47:26,479 --> 00:47:30,160 they have 0.6 kilobytes, or 600 bytes, 1134 00:47:30,160 --> 00:47:31,789 for the public key, 1135 00:47:31,789 --> 00:47:34,329 and that's a very reasonable size for a public key, 1136 00:47:34,329 --> 00:47:35,449 not as small as ECC 1137 00:47:35,449 --> 00:47:37,039 but it's quite tolerable. 1138 00:47:37,039 --> 00:47:38,910 Um, lattice-based crypto, 1139 00:47:38,910 --> 00:47:40,009 there's NTRU, for example, 1140 00:47:40,009 --> 00:47:42,099 that's been around since the 1990s, 1141 00:47:42,099 --> 00:47:44,729 and maybe that's enough time to start getting confident, 1142 00:47:44,729 --> 00:47:46,690 but, well, again, there's lattice-based systems 1143 00:47:46,690 --> 00:47:48,079 that get proposed and broken, 1144 00:47:48,079 --> 00:47:52,009 for instance, there's a system from Smart-Vercauteren in 2009, 1145 00:47:52,009 --> 00:47:54,699 that was, it's not broken pre-quantum, 1146 00:47:54,699 --> 00:47:58,749 but it was shown in 2014-2015, some follow-up papers, 1147 00:47:58,749 --> 00:48:02,029 to be broken in polynomial time by a quantum computer. 1148 00:48:02,029 --> 00:48:05,130 So, it's a lattice-based system which sounded good at the beginning, 1149 00:48:05,130 --> 00:48:08,469 but is definitely not going to be part of post-quantum cryptography. 1150 00:48:08,469 --> 00:48:09,529 There's multivariate-quadratic, 1151 00:48:09,529 --> 00:48:12,150 now those have the interesting feature that 1152 00:48:12,150 --> 00:48:15,109 the signatures they provide can be very very small, 1153 00:48:15,109 --> 00:48:17,289 like, you can have 100-bit signatures 1154 00:48:17,289 --> 00:48:19,239 and still get some reasonable security 1155 00:48:19,239 --> 00:48:20,989 that nobody knows how to break these, 1156 00:48:20,989 --> 00:48:22,759 well, there's lots and lots of these proposals 1157 00:48:22,759 --> 00:48:24,819 and some of them are broken, some of them... 1158 00:48:24,819 --> 00:48:27,680 HFEv-, that's a multivariate quadratic system 1159 00:48:27,680 --> 00:48:31,140 that's been unbroken for 20 years. 1160 00:48:31,140 --> 00:48:32,489 Maybe it will continue holding up, 1161 00:48:32,489 --> 00:48:34,190 but, well, how many people have looked? 1162 00:48:34,190 --> 00:48:36,839 You have to make sure enough people look at these things. 1163 00:48:36,839 --> 00:48:39,469 The reason we like these simple systems from the 70s is 1164 00:48:39,469 --> 00:48:40,229 enough people have looked 1165 00:48:40,229 --> 00:48:42,910 but maybe if you've got more serious performance constraints 1166 00:48:42,910 --> 00:48:44,319 you should look at these other things, 1167 00:48:44,319 --> 00:48:46,359 and of course we are looking at these other things, 1168 00:48:46,359 --> 00:48:47,660 trying to figure out what's secure, 1169 00:48:47,660 --> 00:48:51,799 and how well we can actually, er, 1170 00:48:51,799 --> 00:48:54,179 choose among all these different possibilities. 1171 00:48:54,179 --> 00:48:56,139 Something else, just last mention here, 1172 00:48:56,139 --> 00:48:57,299 is isogeny-based, 1173 00:48:57,299 --> 00:48:59,469 this is for people who like elliptic curves, 1174 00:48:59,469 --> 00:49:02,930 that there is maybe a way to use elliptic curves post-quantum, 1175 00:49:02,930 --> 00:49:04,289 and this has the interesting feature 1176 00:49:04,289 --> 00:49:07,690 that it does exactly the same data flows as Diffie-Hellman. 1177 00:49:07,690 --> 00:49:09,599 So everything you're used to doing with Diffie-Hellman, 1178 00:49:09,599 --> 00:49:11,709 and having, like, a secret key over here 1179 00:49:11,709 --> 00:49:13,109 and a public key over there, 1180 00:49:13,109 --> 00:49:15,940 agree on a shared secret, 1181 00:49:15,940 --> 00:49:18,279 that you can also do with isogeny-based systems, 1182 00:49:18,279 --> 00:49:20,519 but only a few people have studied the security 1183 00:49:20,519 --> 00:49:21,999 and maybe this'll also get broken. 1184 00:49:21,999 --> 00:49:25,000 So, a lots more work, lots more possibilities. 1185 00:49:25,000 --> 00:49:27,969 Last slide, if you're interested in more information 1186 00:49:27,969 --> 00:49:29,909 here are a few places to look, 1187 00:49:29,909 --> 00:49:32,209 first of all you can go to pqcrypto.org, 1188 00:49:32,209 --> 00:49:36,640 so this is our first survey site for post-quantum cryptography, 1189 00:49:36,640 --> 00:49:38,269 and the biggest chunk of information there 1190 00:49:38,269 --> 00:49:42,369 is bibliography, and if anybody has newer papers, 1191 00:49:42,369 --> 00:49:45,539 if you happen to write papers on post-quantum crypto, 1192 00:49:45,539 --> 00:49:46,989 and you'd like us to add those, 1193 00:49:46,989 --> 00:49:48,119 then just let us know, 1194 00:49:48,119 --> 00:49:51,170 um, and then, well, we also have on the front page 1195 00:49:51,170 --> 00:49:53,849 things like pointers to all the PQCrypto conferences, 1196 00:49:53,849 --> 00:49:54,769 that's the main place to look, 1197 00:49:54,769 --> 00:49:57,150 go to pqcrypto.org and follow links to, 1198 00:49:57,150 --> 00:49:59,819 for instance, the February Japan conference. 1199 00:49:59,819 --> 00:50:02,390 Then pqcrypto.eu.org, that's the main page 1200 00:50:02,390 --> 00:50:05,459 for the EU project that Tanja mentioned, 1201 00:50:05,459 --> 00:50:08,229 which is putting out as it progresses, 1202 00:50:08,229 --> 00:50:09,640 well, it just started this year, but 1203 00:50:09,640 --> 00:50:13,499 it's putting out, soon, free libraries! 1204 00:50:13,499 --> 00:50:16,439 Software libraries, for actually doing post-quantum cryptography. 1205 00:50:16,439 --> 00:50:18,309 And benchmarking results, 1206 00:50:18,309 --> 00:50:19,199 so you can actually say 1207 00:50:19,199 --> 00:50:21,420 "Yeah, I've got the following performance constraints here, 1208 00:50:21,420 --> 00:50:23,070 that's what I'm able to use." 1209 00:50:23,070 --> 00:50:25,039 And then in 2017, there's going to be 1210 00:50:25,039 --> 00:50:28,920 a workshop, and a summer school, maybe it'll be a spring school, we'll see, 1211 00:50:28,920 --> 00:50:34,239 if you're interested in the Twitter feed for that, then twitter.com/pqc_eu 1212 00:50:34,239 --> 00:50:37,190 and final resource on the slide is you. 1213 00:50:37,190 --> 00:50:40,130 You have the responsibility if you care about crypto, 1214 00:50:40,130 --> 00:50:42,440 then you have to get used to this stuff. 1215 00:50:42,440 --> 00:50:43,699 You have to learn about hash-based, 1216 00:50:43,699 --> 00:50:47,029 code-based, maybe lattice-based, multivariate quadratics, 1217 00:50:47,029 --> 00:50:49,529 these are the things which will be the future of crypto. 1218 00:50:49,529 --> 00:50:53,819 In the future, all of crypto will be post-quantum crypto, 1219 00:50:53,819 --> 00:50:56,569 because eventually the attackers will have quantum computers. 1220 00:50:56,569 --> 00:50:58,479 If you want to adapt to that future, 1221 00:50:58,479 --> 00:51:00,369 then, well, take a look at these sytems 1222 00:51:00,369 --> 00:51:02,229 and see, maybe find improvements, 1223 00:51:02,229 --> 00:51:03,519 then, cool, then let us know, 1224 00:51:03,519 --> 00:51:05,539 and, you know, publish papers, 1225 00:51:05,539 --> 00:51:08,299 integrate them into real applications, networking applications, 1226 00:51:08,299 --> 00:51:09,969 implement the things that aren't implemented, 1227 00:51:09,969 --> 00:51:10,779 speed them up, 1228 00:51:10,779 --> 00:51:12,840 there's lots of work that still has to be done. 1229 00:51:12,840 --> 00:51:15,050 That's it, thank you for your attention. 1230 00:51:15,050 --> 00:51:28,799 *applause* 1231 00:51:28,799 --> 00:51:33,589 Herald: Wow. Now we'll have some short questions please. 1232 00:51:33,589 --> 00:51:35,660 Because we're a bit late on time. 1233 00:51:35,660 --> 00:51:39,559 Questioners, go around ahead, there's a mike there, 1234 00:51:39,559 --> 00:51:41,749 talk into it please. 1235 00:51:41,749 --> 00:51:42,910 Can we have mike 1? 1236 00:51:42,910 --> 00:51:45,869 Q: Oh, okay. Uh, quick question. 1237 00:51:45,869 --> 00:51:50,239 So there was this result of Laszlo Babai that there's a, 1238 00:51:50,239 --> 00:51:56,059 that graph isomorphism has a quasipolynomial time algorithm, 1239 00:51:56,059 --> 00:52:00,219 um, not really knowing the subject at all, 1240 00:52:00,219 --> 00:52:04,260 there's some very, very superficial similarities, 1241 00:52:04,260 --> 00:52:08,709 like, that is a hidden subgroup problem, basically. 1242 00:52:08,709 --> 00:52:11,849 Um, is there going to be any, like, 1243 00:52:11,849 --> 00:52:14,289 is there any indication that the methods he used in that proof 1244 00:52:14,289 --> 00:52:16,989 are relevant to breaking, like, 1245 00:52:16,989 --> 00:52:20,279 to weakening NTRU or things like this? 1246 00:52:20,279 --> 00:52:25,729 djb: That's a good question. So, the, um, the graph isomorphism advance now, 1247 00:52:25,729 --> 00:52:27,069 is basically saying, 1248 00:52:27,069 --> 00:52:30,229 so, graph isomorphism is a problem which was famous as being 1249 00:52:30,229 --> 00:52:32,619 not know to be solvable in polynomial 1250 00:52:32,619 --> 00:52:35,160 or even, like you said, quasipolynomial time. 1251 00:52:35,160 --> 00:52:38,209 Um, except there were some really good software algorithms 1252 00:52:38,209 --> 00:52:41,069 which would solve most cases of it, really quickly. 1253 00:52:41,069 --> 00:52:42,680 There were just some really weird, 1254 00:52:42,680 --> 00:52:43,849 highly symmetric cases, 1255 00:52:43,849 --> 00:52:44,630 that were hard to solve 1256 00:52:44,630 --> 00:52:47,249 and that's what Babai managed to completely kill now, 1257 00:52:47,249 --> 00:52:49,349 so he's handled all the cases. 1258 00:52:49,349 --> 00:52:51,949 But we try to stay away from problems like that in crypto, 1259 00:52:51,949 --> 00:52:54,660 so, an example that's very closely analogous to that is 1260 00:52:54,660 --> 00:52:56,589 what's called support splitting, 1261 00:52:56,589 --> 00:52:58,640 which is a certain type of attack strategy 1262 00:52:58,640 --> 00:53:00,599 against code-based crypto 1263 00:53:00,599 --> 00:53:03,190 if somebody gives away lots of information 1264 00:53:03,190 --> 00:53:05,039 from the legitimate user. 1265 00:53:05,039 --> 00:53:07,199 And that's something where the support-splitting algorithm 1266 00:53:07,199 --> 00:53:09,420 works in most cases, 1267 00:53:09,420 --> 00:53:12,529 but it kind of fails in some corner cases, 1268 00:53:12,529 --> 00:53:16,079 and, well, we try to stay away from thinking about this anyway, 1269 00:53:16,079 --> 00:53:18,690 because you just don't want to give somebody that extra information, 1270 00:53:18,690 --> 00:53:23,249 but if you did, then maybe Babai's technique could be useful there. 1271 00:53:23,249 --> 00:53:25,739 Herald: Thank you. This talk is not over. 1272 00:53:25,739 --> 00:53:30,009 If you're leaving, which is okay, please be silent. 1273 00:53:30,009 --> 00:53:33,670 Next question, number 3, no, number 1. 1274 00:53:33,670 --> 00:53:35,779 Q: Uh, hello, thank you for the talk. 1275 00:53:35,779 --> 00:53:40,430 Um, how are the chances to have something like forward secrecy with that? 1276 00:53:40,430 --> 00:53:43,729 I recognise the last algorithm has a chance 1277 00:53:43,729 --> 00:53:45,339 to reuse Diffie-Hellman, 1278 00:53:45,339 --> 00:53:47,739 that's possibly the only one? 1279 00:53:47,739 --> 00:53:51,619 Lange: So, if you think that forward secrecy means Diffie-Hellman, 1280 00:53:51,619 --> 00:53:55,759 you can have forward secrecy from normal encryption algorithms, 1281 00:53:55,759 --> 00:53:58,249 at the expense of generating a new key each time. 1282 00:53:58,249 --> 00:54:00,670 You can have forward secrecy with RSA, 1283 00:54:00,670 --> 00:54:03,140 if Alice talking to Bob starts by saying 1284 00:54:03,140 --> 00:54:06,440 "Okay, this is my one-time RSA key, 1285 00:54:06,440 --> 00:54:08,459 and I send this to Bob, 1286 00:54:08,459 --> 00:54:12,609 with a request to encrypt to this key." 1287 00:54:12,609 --> 00:54:16,099 If Alice never reuses this key, 1288 00:54:16,099 --> 00:54:18,170 then this method is forward-secure. 1289 00:54:18,170 --> 00:54:21,039 And similar to how you can do this with RSA keys, 1290 00:54:21,039 --> 00:54:23,420 you can also do this with McEliece keys. 1291 00:54:23,420 --> 00:54:25,489 At the moment, there is a difficulty 1292 00:54:25,489 --> 00:54:29,449 that the keys are very large. 1293 00:54:29,449 --> 00:54:32,719 It is inconvenient when you want to start talking, 1294 00:54:32,719 --> 00:54:35,849 "Hey, I'm a client, hello server, please talk to me", 1295 00:54:35,849 --> 00:54:37,289 and the first thing you have to do 1296 00:54:37,289 --> 00:54:41,900 is transmit a megabyte of key. 1297 00:54:41,900 --> 00:54:44,229 On the other hand, you can do it. 1298 00:54:44,229 --> 00:54:47,719 It just requires you to engineer your protocol to expect, 1299 00:54:47,719 --> 00:54:50,999 yes, you have to send a few packages. 1300 00:54:50,999 --> 00:54:53,959 And then it has all the forward secrecy that you want. 1301 00:54:53,959 --> 00:54:58,180 Q: But, uh, a way without transferring the key, 1302 00:54:58,180 --> 00:54:59,449 like Diffie-Hellman? 1303 00:54:59,449 --> 00:55:02,509 Lange: But, Diffie-Hellman is transferring a key. 1304 00:55:02,509 --> 00:55:03,259 Q: Okay. 1305 00:55:03,259 --> 00:55:04,989 Lange: I mean, you're basically transferring 1306 00:55:04,989 --> 00:55:07,349 the first part of a discrete log pair. 1307 00:55:07,349 --> 00:55:10,299 If Alice sends a*p, and there is some one-time key, 1308 00:55:10,299 --> 00:55:12,219 she's sending a public key. 1309 00:55:12,219 --> 00:55:16,029 It's just that the method of how those two public keys interact 1310 00:55:16,029 --> 00:55:19,279 is slightly different from how RSA encryption works. 1311 00:55:19,279 --> 00:55:20,980 Q: Okay, thank you. 1312 00:55:20,980 --> 00:55:25,049 Herald: Thank you. Do we have an Internet message? Question? 1313 00:55:25,049 --> 00:55:30,170 Signal Angel: Actually, we do. There are two questions that are somehow related. 1314 00:55:30,170 --> 00:55:31,479 The first one is: 1315 00:55:31,479 --> 00:55:37,299 Given that there is no actual working quantum computer, 1316 00:55:37,299 --> 00:55:40,619 how do you start developing a crypto algorithm? 1317 00:55:40,619 --> 00:55:42,410 Where do you start, how do you design it, 1318 00:55:42,410 --> 00:55:46,140 how do you test it? Is there a way to prove that it's secure? 1319 00:55:46,140 --> 00:55:49,349 And the second question is related: 1320 00:55:49,349 --> 00:55:55,079 The whole thing is based on the property of the hash functions being one-way, 1321 00:55:55,079 --> 00:55:57,969 how does one know that there is no quantum algorithm 1322 00:55:57,969 --> 00:55:59,920 that breaks this property? 1323 00:55:59,920 --> 00:56:01,859 Can you prove this? 1324 00:56:01,859 --> 00:56:03,729 djb: Okay. For both of these questions, 1325 00:56:03,729 --> 00:56:06,079 the technique that the community goes through, 1326 00:56:06,079 --> 00:56:08,189 that we all go through, is cryptanalysis. 1327 00:56:08,189 --> 00:56:11,219 So we have as many smart people as we can find 1328 00:56:11,219 --> 00:56:12,989 focusing on these problems and saying 1329 00:56:12,989 --> 00:56:16,549 "Can you find an algorithm which is breaking these problems 1330 00:56:16,549 --> 00:56:19,069 better than any previous algorithms can?" 1331 00:56:19,069 --> 00:56:20,999 and we put as many incentives as we can 1332 00:56:20,999 --> 00:56:23,099 so that we try to get as many smart people 1333 00:56:23,099 --> 00:56:25,299 to stay ahead of the bad guys, 1334 00:56:25,299 --> 00:56:27,299 and hopefully find the best algorithms. 1335 00:56:27,299 --> 00:56:28,709 But there's no guarantees in this. 1336 00:56:28,709 --> 00:56:30,449 And you do always have to be sceptical 1337 00:56:30,449 --> 00:56:33,140 about whether people have actually looked at, for instance 1338 00:56:33,140 --> 00:56:35,359 quantum algorithms to attack systems. 1339 00:56:35,359 --> 00:56:36,829 And there is that extra difficulty 1340 00:56:36,829 --> 00:56:39,819 that the first part of the question, at the beginning, was saying, 1341 00:56:39,819 --> 00:56:41,809 that we don't have a quantum computer. 1342 00:56:41,809 --> 00:56:45,339 So if we're trying to verify quantum algorithms that we're developing, 1343 00:56:45,339 --> 00:56:47,589 we don't get to experiment with them. 1344 00:56:47,589 --> 00:56:50,549 That's the usual procedure for making sure your algorithms work. 1345 00:56:50,549 --> 00:56:52,559 In state-of-the-art cryptanalysis, 1346 00:56:52,559 --> 00:56:55,029 like the number field sieve for factoring, 1347 00:56:55,029 --> 00:56:57,880 that does not have a proof that it works in any particular, 1348 00:56:57,880 --> 00:56:59,789 well, at the speed that we think, 1349 00:56:59,789 --> 00:57:01,349 it works out from experiment. 1350 00:57:01,349 --> 00:57:03,329 So experiments are really important, 1351 00:57:03,329 --> 00:57:05,829 because we don't have proofs for state-of-the-art cryptanalysis, 1352 00:57:05,829 --> 00:57:09,759 and that's something where it's actually really tough for quantum computers. 1353 00:57:09,759 --> 00:57:11,859 Of course eventually we'll all have quantum computers, 1354 00:57:11,859 --> 00:57:14,869 and there's ideas for simulating quantum algorithms 1355 00:57:14,869 --> 00:57:18,359 which have had some success at verifying that algorithms work 1356 00:57:18,359 --> 00:57:20,579 even though we can't actually run them yet. 1357 00:57:20,579 --> 00:57:25,050 That we're actually able to verify a simulation of those algorithms. 1358 00:57:25,050 --> 00:57:27,530 Lange: Let me do a second part of this. 1359 00:57:27,530 --> 00:57:30,769 Um, when we use quantum cryptanalysis, 1360 00:57:30,769 --> 00:57:33,189 for estimates, we usually go for the worst-case estimate. 1361 00:57:33,189 --> 00:57:39,230 So we say, well, McEliece, at worst, gets broken to half the security level. 1362 00:57:39,230 --> 00:57:41,380 Most likely it won't be that fast, 1363 00:57:41,380 --> 00:57:45,609 but we're staying on the side where we're very confident. 1364 00:57:45,609 --> 00:57:48,349 Um, if I understood correctly there was also the part of the question, 1365 00:57:48,349 --> 00:57:50,099 how can we test the algorithms? 1366 00:57:50,099 --> 00:57:52,670 If this is for the constructive algorithms, 1367 00:57:52,670 --> 00:57:54,369 then all the algorithms we analyse, 1368 00:57:54,369 --> 00:57:56,900 all the algorithms we propose for post-quantum crypto, 1369 00:57:56,900 --> 00:57:59,939 are algorithms that you can run on your normal computer. 1370 00:57:59,939 --> 00:58:02,309 So, you can test those, you can run those, 1371 00:58:02,309 --> 00:58:04,189 we have benchmarking numbers from those, 1372 00:58:04,189 --> 00:58:07,219 on our current hardware. 1373 00:58:07,219 --> 00:58:12,019 Herald: We'll do two more questions, please. Number 1. 1374 00:58:12,019 --> 00:58:15,630 Q: Yeah, I got a question on the practicality of the attacks. 1375 00:58:15,630 --> 00:58:19,150 So, um, if we assume there is a quantum computer, 1376 00:58:19,150 --> 00:58:21,729 how much time will it take in practice, 1377 00:58:21,729 --> 00:58:22,900 order of magnitude, 1378 00:58:22,900 --> 00:58:25,729 to break, let's say, RSA 2048-bit key? 1379 00:58:25,729 --> 00:58:28,829 Is it on the order of hours, weeks, months, years? 1380 00:58:28,829 --> 00:58:31,169 Lange: *snaps fingers* Done. 1381 00:58:31,169 --> 00:58:32,349 Q: Okay, thanks. 1382 00:58:32,349 --> 00:58:32,939 *laughter* 1383 00:58:32,939 --> 00:58:36,289 djb: That was easy! Herald: Number 3. 1384 00:58:36,289 --> 00:58:36,869 Q: Okay. 1385 00:58:36,869 --> 00:58:38,599 Herald: Talk into the mike, please. 1386 00:58:38,599 --> 00:58:41,369 Q: Thank you. So, it's very, very nice to have 1387 00:58:41,369 --> 00:58:45,789 both quantum encryption and signing, 1388 00:58:45,789 --> 00:58:48,650 but do you know anything about some other cryptographic primitives, 1389 00:58:48,650 --> 00:58:52,499 such as zero-knowledge proofs? 1390 00:58:52,499 --> 00:58:53,499 Lange: Well, I mean, zero-knowledge proofs 1391 00:58:53,499 --> 00:58:56,920 are basically signatures which are not interactive. 1392 00:58:56,920 --> 00:58:59,580 So if you have something which is, um, 1393 00:58:59,580 --> 00:59:02,249 a primitive for a signature is usually very closely related 1394 00:59:02,249 --> 00:59:03,789 to zero-knowledge proofs. 1395 00:59:03,789 --> 00:59:05,739 So, there is work going on, 1396 00:59:05,739 --> 00:59:07,680 we are focusing on the most important things 1397 00:59:07,680 --> 00:59:10,049 that we see on the Internet, 1398 00:59:10,049 --> 00:59:12,579 but, that shouldn't mean that people shouldn't do research on it. 1399 00:59:12,579 --> 00:59:17,060 Please do research on zero-knowledge proofs! 1400 00:59:17,060 --> 00:59:21,539 Herald: Okay. Last question. Number 1. 1401 00:59:21,539 --> 00:59:24,859 Q: So, why do you put so much emphasis 1402 00:59:24,859 --> 00:59:28,549 on smaller key sizes and on performance in encryption, 1403 00:59:28,549 --> 00:59:34,529 um, especially in a delicate topic like post-quantum computing? 1404 00:59:34,529 --> 00:59:37,269 Why can't we just use 1-megabyte keys 1405 00:59:37,269 --> 00:59:41,859 and why can't we just use a few seconds instead of miliseconds 1406 00:59:41,859 --> 00:59:43,599 to compute those? Lange: So... 1407 00:59:43,599 --> 00:59:44,949 Q: What's the the problem here? 1408 00:59:44,949 --> 00:59:47,660 Lange: We are suggesting to use a key of 1 megabyte. 1409 00:59:47,660 --> 00:59:51,809 So, our recommendation that we have on the Internet on the pqcrypto.org page 1410 00:59:51,809 --> 00:59:56,180 are precisely using this system which has a 1-megabyte key. 1411 00:59:56,180 --> 00:59:58,329 The nice thing is, that actually 1412 00:59:58,329 --> 01:00:02,449 encryption and decryption are very efficient. 1413 01:00:02,449 --> 01:00:03,579 But that was not our main goal, 1414 01:00:03,579 --> 01:00:06,430 our main goal was to get something which is very secure, 1415 01:00:06,430 --> 01:00:11,329 and where we have a high confidence that we actually understand the attack. 1416 01:00:11,329 --> 01:00:14,009 And then, well, once we have this system, 1417 01:00:14,009 --> 01:00:17,520 then you try to optimise how to implement it, 1418 01:00:17,520 --> 01:00:19,279 and the implementation, when we looked at the numbers 1419 01:00:19,279 --> 01:00:22,039 is actually faster than elliptic curve implementations 1420 01:00:22,039 --> 01:00:23,910 except for the size. 1421 01:00:23,910 --> 01:00:26,329 So, you get a very nice speed, 1422 01:00:26,329 --> 01:00:31,790 even though it was not our target for optimisation. 1423 01:00:31,790 --> 01:00:33,379 Herald: Okay, this is it. 1424 01:00:33,379 --> 01:00:35,430 Thank you very much, let's have a final hand 1425 01:00:35,430 --> 01:00:38,479 for Tanja Lange and djb Bernstein! 1426 01:00:38,479 --> 01:00:46,360 *applause* 1427 01:00:46,360 --> 01:00:56,830 *postroll music*