1 00:00:00,000 --> 00:00:18,580 *35C3 preroll music* 2 00:00:18,580 --> 00:00:25,620 Herald: The next talk is called "The year in post-quantum crypto" by Tanja Lange, 3 00:00:25,620 --> 00:00:32,439 she's researching in Eindhoven, and Daniel Bernstein, researching at the University 4 00:00:32,439 --> 00:00:39,249 of Chicago. They both had the first ever conference on post-quantum cryptography in 5 00:00:39,249 --> 00:00:46,739 2006 and they both contribute to libsalt crypto library. Their talk is going to be 6 00:00:46,739 --> 00:00:52,829 a summary of the NIST post-quantum crypto competition and they're gonna provide an 7 00:00:52,829 --> 00:00:58,850 overview of problems of post-quantum cryptography and hopefully show us how to 8 00:00:58,850 --> 00:01:03,290 integrate post-quantum crypto in existing software. Please welcome them with a huge 9 00:01:03,290 --> 00:01:04,714 round of applause. 10 00:01:04,714 --> 00:01:15,730 *applause* 11 00:01:15,730 --> 00:01:19,830 Tanja Lange: All right, well, thank you. First of all, this title word post-quantum 12 00:01:19,830 --> 00:01:24,890 cryptography, what it means, we're talking about cryptography where we're designing 13 00:01:24,890 --> 00:01:29,790 the systems under the assumption that our attacker - not the user, just the attacker 14 00:01:29,790 --> 00:01:34,520 - has a large quantum computer. Also to remind you from three years ago, when we 15 00:01:34,520 --> 00:01:42,320 showed you the attacker, we're talking about attackers. All right. So, we're 16 00:01:42,320 --> 00:01:48,050 seeing like over the last few years 2015, say middle August, there was a big 17 00:01:48,050 --> 00:01:51,320 announcement by the NSA saying "Oh yeah, acutally the world should care about post- 18 00:01:51,320 --> 00:01:55,500 quantum cryptography. We need more research." They finally wake up to it and 19 00:01:55,500 --> 00:01:59,230 actually they had a nice roll-out effect, that pretty much every agency - just 20 00:01:59,230 --> 00:02:03,920 highlighting three of them here, so U.K., the Netherlands and the NSA themselves - 21 00:02:03,920 --> 00:02:08,530 made some statements about the urgency of rolling out post-quantum, that normal 22 00:02:08,530 --> 00:02:11,840 cryptography that we're currently using, so elliptic curves and RSA and Diffie- 23 00:02:11,840 --> 00:02:16,160 Hellman and finite fields, will be broken as soon as a quantum computer, and the 24 00:02:16,160 --> 00:02:19,230 NIST, which is the National Institute for Standards and Technology, so it's an 25 00:02:19,230 --> 00:02:25,141 institute in the U.S., which is working on standards said, ok, we're gonna call for a 26 00:02:25,141 --> 00:02:30,790 standardization project for post-quatum cryptography. So yes, it's a U.S. 27 00:02:30,790 --> 00:02:36,030 institution, but it has in cryptography a mostly good history. They have been 28 00:02:36,030 --> 00:02:39,310 running competitions which gave us AES. They've been running competitions which 29 00:02:39,310 --> 00:02:44,140 gave us the SHA3. And they also, without a competition, gave us Dual_EC. 30 00:02:44,140 --> 00:02:48,331 *laughter* TL: So, competitions with NIST, good 31 00:02:48,331 --> 00:02:54,220 thing, everything else, well, judge for yourself. This sounds like a great story. 32 00:02:54,220 --> 00:02:58,100 It's also a little bit disappointing when you look at where it started. So back in 33 00:02:58,100 --> 00:03:01,860 2003, Dan here coined the term post- quantum cryptography and then they've been 34 00:03:01,860 --> 00:03:06,209 running around for 10 years going like "The end is nigh, please invest in post- 35 00:03:06,209 --> 00:03:11,300 quantum cryptography, do something", just that 10 years later the NSA said "Oh my 36 00:03:11,300 --> 00:03:15,290 God, we have to do something, quatum computers are comming". So it's a little 37 00:03:15,290 --> 00:03:18,290 bit. Yeah, I told you so. Not a great story, but. 38 00:03:18,290 --> 00:03:22,250 Daniel J. Bernstein: All right so what happened with this competition. Well after 39 00:03:22,250 --> 00:03:27,100 NIST said "Hey everybody, send us some proposals for post-quantum crypto to 40 00:03:27,100 --> 00:03:31,830 standardize", a lot of people did. So, they said actually more than 80 41 00:03:31,830 --> 00:03:35,560 submissions came in and some of them were incomplete, like one of the requirements 42 00:03:35,560 --> 00:03:39,239 was include software, and whatever reasons, they said some of the submissions 43 00:03:39,239 --> 00:03:42,880 are not complete, but they posted 69 complete submissions, the submission teams 44 00:03:42,880 --> 00:03:47,891 include 260 people from around the world, all sorts of academia, industry, maybe 45 00:03:47,891 --> 00:03:52,010 even some government people. There's lots and lots of names and we're not gonna go 46 00:03:52,010 --> 00:03:55,530 through, like, what all these things are, but we are going to say something... 47 00:03:55,530 --> 00:03:58,690 TL: Oh we have 60 minutes. DJB: Oh that's true. So BIG QUAKE: This is 48 00:03:58,690 --> 00:04:01,560 a code based system... *laughter* 49 00:04:01,560 --> 00:04:05,970 No, we're gonna give you some idea of, like, what the big picture is of how well 50 00:04:05,970 --> 00:04:11,629 these things have held up. So, these were all posted by NIST on the 21st of December 51 00:04:11,629 --> 00:04:17,910 last year, and some of you who saw our LatticeHacks talk last year remember that 52 00:04:17,910 --> 00:04:21,840 this list, already there was some damage to it by the time of our talk on the 28th 53 00:04:21,840 --> 00:04:26,690 of December 2017. By the end of the year, there were eight submissions that had 54 00:04:26,690 --> 00:04:30,880 attacks, at different levels of severity. I should explain the color coding here. 55 00:04:30,880 --> 00:04:36,620 The stuff that's in brown is less security than claimed, which could be for instance 56 00:04:36,620 --> 00:04:41,060 they claimed something was, it would take 2 to the 128 operations to break and 57 00:04:41,060 --> 00:04:46,520 somebody says "no, it's 2 to the 100 or 2 to the 80". Does that really matter? Or 58 00:04:46,520 --> 00:04:49,330 maybe a different direction is somebody says: "this is a system where you can 59 00:04:49,330 --> 00:04:54,199 reuse the key any number of times", which we expect for for normal crypto systems 60 00:04:54,199 --> 00:04:57,420 that you can publish your key and people can keep sending you messages or you can 61 00:04:57,420 --> 00:05:01,250 sign many times under some keys, but sometimes people claimed they had that 62 00:05:01,250 --> 00:05:06,410 feature and they turned out to be wrong; those were attackable, like HILA5 in this 63 00:05:06,410 --> 00:05:10,530 list, which is not necessarily kicking them out of the competition, because NIST 64 00:05:10,530 --> 00:05:15,470 said, you can have a system with one-time keys that can be useful for some 65 00:05:15,470 --> 00:05:18,790 applications. The things in red are, everything that they proposed, all the 66 00:05:18,790 --> 00:05:24,040 concrete parameters are broken. The underlines are those where there's attacks 67 00:05:24,040 --> 00:05:28,060 scripts, Python scripts, stage scripts, whatever it takes to demonstrate that, 68 00:05:28,060 --> 00:05:33,000 yeah, look, here's here's your secret key, or decrypting something. So that was the 69 00:05:33,000 --> 00:05:38,600 end of 2017. How about now. Well, OK, let's extrapolate, three days from now. 70 00:05:38,600 --> 00:05:44,510 Probably the situation is at least the following. At least by twenty eighth of 71 00:05:44,510 --> 00:05:52,470 December 2018, 22 submissions have attacks. So it's about a third of those 69 72 00:05:52,470 --> 00:05:58,370 submissions, and you can see more, well, most, well, 13 of those, out of the 22, 73 00:05:58,370 --> 00:06:03,100 are red, mostly with underlines. I think some of this is from us, a lot from other 74 00:06:03,100 --> 00:06:07,509 people. And I think we did well early on establishing that people should put out 75 00:06:07,509 --> 00:06:11,240 scripts to demonstrate that ,yeah, you really can break these things. So again 76 00:06:11,240 --> 00:06:15,600 the underlines are demonstrated attacks; some of the submitters have withdrawn the 77 00:06:15,600 --> 00:06:21,120 broken submissions; some of them have not. TL: All right, so when you look at this, 78 00:06:21,120 --> 00:06:27,020 we're not going to go through explaining those, but let me categorize these. So 79 00:06:27,020 --> 00:06:30,310 when we look at the ones which are not completely smashed and broken, we can put 80 00:06:30,310 --> 00:06:33,900 them into boxes, we can say "hey, what is the underlying mathematical problem", 81 00:06:33,900 --> 00:06:38,770 "what do we hope is something the attacker has to do in order to break the 82 00:06:38,770 --> 00:06:42,919 cryptosystem". And then there is one category of using error-correcting codes, 83 00:06:42,919 --> 00:06:48,050 which is then used for building an encryption system or a signature scheme, 84 00:06:48,050 --> 00:06:51,760 hash functions, you can only build signature schemes from, isogeny-based 85 00:06:51,760 --> 00:06:55,380 crypto, for the competition we're only seeing an encryption system, and honestly 86 00:06:55,380 --> 00:07:00,460 all the signatures we have seen so far are pretty inefficient. Lattices we see for 87 00:07:00,460 --> 00:07:04,790 both, that is something we talked about last year, so if you want to get a full- 88 00:07:04,790 --> 00:07:08,680 blown lattice explanation, go for last year's talk. And then finally, there's 89 00:07:08,680 --> 00:07:13,820 something using systems in many variables, many equations, and we get signatures and 90 00:07:13,820 --> 00:07:19,050 encryption from that. So that's one way of saying "Well, these are good things for 91 00:07:19,050 --> 00:07:23,340 post-quantum". It does not mean that everything which isn't in these boxes is 92 00:07:23,340 --> 00:07:28,290 secure. You can still design a system, which somehow relates to this math 93 00:07:28,290 --> 00:07:32,810 problem, but the attacker can do a way around. Some of those systems, RaCoSS I'll 94 00:07:32,810 --> 00:07:37,889 get back to later, is a code-based system - code-based is on the list, first one up 95 00:07:37,889 --> 00:07:42,150 there - so should be totally secure, and yet it's one of the red underlined 96 00:07:42,150 --> 00:07:47,600 systems. So just being in one of the categories does not mean it's secure, but 97 00:07:47,600 --> 00:07:52,970 it's at least some hopeful and helpful thing to box things. There are other ways 98 00:07:52,970 --> 00:07:56,780 of describing why this is the situation we have now. 99 00:07:56,780 --> 00:08:00,450 DJB: As an example of this kind of categorization, sometimes people might 100 00:08:00,450 --> 00:08:05,430 say: "Oh, lattice-based cryptography is is the safe thing to do. All of that red was 101 00:08:05,430 --> 00:08:09,420 people who were not using lattice-based- cryptography and everything lattice-based 102 00:08:09,420 --> 00:08:13,730 is good, everything else is scary". But if you look at the lattice-based systems, 103 00:08:13,730 --> 00:08:18,860 it's not all black. There's some red stuff here. Compact LWE. That one is broken, 104 00:08:18,860 --> 00:08:21,500 with a script, we're quite sure it's broken. There's some others with some 105 00:08:21,500 --> 00:08:25,220 damage, DRS, HILA5. So it's not that the lattice-based submissions have held up 106 00:08:25,220 --> 00:08:30,400 perfectly and also it's not just that these are isolated mistakes that people 107 00:08:30,400 --> 00:08:34,789 have made. There's ongoing research which is making better and better lattice 108 00:08:34,789 --> 00:08:39,339 attacks. For instance, some papers from last month and this month from the three 109 00:08:39,339 --> 00:08:44,779 authors listed there are talking about lattice-based systems being broken by 110 00:08:44,779 --> 00:08:49,800 decryption failures. Now this phenomenon, most of the lattice submissions have 111 00:08:49,800 --> 00:08:57,399 occasional decryption failures. Once every 2 to the 64 ciphertexts maybe, you won't 112 00:08:57,399 --> 00:09:01,630 be able to decrypt. Which might sound like "oh, it's no big deal, it's, maybe 113 00:09:01,630 --> 00:09:05,380 occasionally you might have some user has that happen and they'll just, the browser 114 00:09:05,380 --> 00:09:10,779 will reconnect, whatever it takes, it's not a significant failure rate". Except 115 00:09:10,779 --> 00:09:15,660 that those failures, if the attacker is trying to decrypt a particular cipher text 116 00:09:15,660 --> 00:09:20,120 or maybe attack or figure out somebody's secret key, they can usually get that 117 00:09:20,120 --> 00:09:24,800 information out of watching the pattern of decryption failures, if decryption 118 00:09:24,800 --> 00:09:29,170 failures happen often enough. And these papers are saying, for two different 119 00:09:29,170 --> 00:09:33,410 reasons, decryption failures are actually happening more often, maybe much more 120 00:09:33,410 --> 00:09:37,390 often than people claim. So that's kind of scary. 121 00:09:37,390 --> 00:09:42,620 TL: All right. One explanation, which I of course like very much. I've been running a 122 00:09:42,620 --> 00:09:49,170 European protocol, PQCRYPTO, and just use everything in our portfolio. It's good 123 00:09:49,170 --> 00:09:53,250 right? Actually, it's looking better than the arguments saying: "I'll use everything 124 00:09:53,250 --> 00:09:56,490 lattice-based. We have one which is slightly scratched, but everything else is 125 00:09:56,490 --> 00:10:00,580 good. Right. Yay." DJB: Except, well, there's another 126 00:10:00,580 --> 00:10:06,350 explanation than just, well, whoever these PQCRYPTO project people are, obviously the 127 00:10:06,350 --> 00:10:10,990 right people, putting together a great portfolio. There's another possibility. 128 00:10:10,990 --> 00:10:15,160 Not saying this is right, but you could imagine the cryptanalysts who are deciding 129 00:10:15,160 --> 00:10:20,880 what to do out of that huge pile of 69 submissions. Maybe they thought the people 130 00:10:20,880 --> 00:10:25,430 who were in this project doing this stuff for some number of years are maybe not the 131 00:10:25,430 --> 00:10:30,360 top targets. Maybe you should look at the other 49 submissions. Maybe you should 132 00:10:30,360 --> 00:10:34,080 look at the submissions with the specification written in Microsoft Word. 133 00:10:34,080 --> 00:10:38,540 Probably more likely to be broken. Maybe there's other ways that you can decide how 134 00:10:38,540 --> 00:10:41,779 to - no offence to Microsoft people - TL: It worked. 135 00:10:41,779 --> 00:10:48,720 DJB: yeah, that did work coincidentally. Yeah. So, the thing to keep in mind is 136 00:10:48,720 --> 00:10:53,210 that there's a huge pile of submissions, more than a million words in these 69 137 00:10:53,210 --> 00:10:57,930 submission documents, and this is like, a word in English is usually a kind of 138 00:10:57,930 --> 00:11:01,660 imprecise thing, reviewing that, this is I would say more effort than reviewing a 139 00:11:01,660 --> 00:11:06,529 million lines of code. This is a lot of stuff, lot of junk to go through. There's 140 00:11:06,529 --> 00:11:10,980 a real flood, there's too much for us to all the people who care about attacking 141 00:11:10,980 --> 00:11:14,710 systems to, to actually go through everything. So people are making a 142 00:11:14,710 --> 00:11:17,519 selecttion, and maybe they just haven't bothered looking at these PQCRYPTO 143 00:11:17,519 --> 00:11:22,070 submissions. So, if you want to actually have security review, it's really 144 00:11:22,070 --> 00:11:26,020 important to keep this denial of service effect in mind, that the flood of 145 00:11:26,020 --> 00:11:30,570 submissions has to be small enough that it can be handled by the number of people who 146 00:11:30,570 --> 00:11:33,470 are looking at these submissions and evaluating the security. 147 00:11:33,470 --> 00:11:37,200 TL: So, call for help, please join, please break. Don't break ours. 148 00:11:37,200 --> 00:11:42,250 *laughter* TL: Now, one thing which in this audience 149 00:11:42,250 --> 00:11:46,120 is a little funny, but in an normal academic conference where you talk to like 150 00:11:46,120 --> 00:11:50,730 40 or 100 people, we like, we actually have a lot of people now being interested 151 00:11:50,730 --> 00:11:54,420 in post-quantum cryptography. This was this year's conference on this, when Dan 152 00:11:54,420 --> 00:11:58,940 and I started this in 2006, we were looking at an audience of 40. This is 350 153 00:11:58,940 --> 00:12:04,459 people. Well, they would probably fit in here, but, well - for academics, this is 154 00:12:04,459 --> 00:12:08,010 big. There's a huge interest right now. This was the combined conference together 155 00:12:08,010 --> 00:12:14,540 with a NIST workshop. And so people are looking. So that's the good news. There's 156 00:12:14,540 --> 00:12:17,620 more denial of service going on, I mentioned RaCoSS already as one which is 157 00:12:17,620 --> 00:12:22,399 broken, but not withdrawn. Broken actually three different ways, where our last 158 00:12:22,399 --> 00:12:26,260 message to them was basically "abandon all hope, this is not gonna work", but they 159 00:12:26,260 --> 00:12:31,060 keep on hoping. If I zoom in there, they have, they are on the way to publishing 160 00:12:31,060 --> 00:12:34,899 new parameters. *laughter* 161 00:12:34,899 --> 00:12:40,149 TL: When he was reading it out, actually at the conference, he was saying "the keys 162 00:12:40,149 --> 00:12:46,209 and signature size may be several dozens of terabytes". Well, there is some effect 163 00:12:46,209 --> 00:12:49,060 that we're most likely not going to break it so easily, because when you're trying 164 00:12:49,060 --> 00:12:53,410 to download several terabytes of data, it might not reconnect. 165 00:12:53,410 --> 00:12:59,079 DJB: So, NIST is certainly aware of the fact that there's just this denial of 166 00:12:59,079 --> 00:13:03,800 service on security analysis. And one of the ways that they tried to simplify the 167 00:13:03,800 --> 00:13:09,120 picture is, said, after their conference they put out this call saying, "all right, 168 00:13:09,120 --> 00:13:13,620 if you have similar submissions, see if you can merge them". And then hopefully 169 00:13:13,620 --> 00:13:16,760 you get something which is, you know, going to be a combined submission that's 170 00:13:16,760 --> 00:13:20,930 easier for us to analyze than these two separate submissions in the first place. 171 00:13:20,930 --> 00:13:25,170 And they said this is an interesting little guarantee. They said "NIST will 172 00:13:25,170 --> 00:13:29,769 accept a merged submission to the second round if either of the submissions being 173 00:13:29,769 --> 00:13:34,209 merged would have been accepted". So you can imagine kind of attacking this if 174 00:13:34,209 --> 00:13:38,820 there's a strong submission and you have a weak submission, like the strong one, they 175 00:13:38,820 --> 00:13:42,640 surely have to accept that, and then you merge your weak submission into the strong 176 00:13:42,640 --> 00:13:46,550 one if you can somehow convince the other team to do that, then your weak submission 177 00:13:46,550 --> 00:13:50,450 is also going to get into the the second round, but NIST said "well, you should 178 00:13:50,450 --> 00:13:54,860 only merge submissions that are similar and the merged submissions should be like 179 00:13:54,860 --> 00:13:59,800 a combination of the two original submissions". So that sounds kind of 180 00:13:59,800 --> 00:14:04,090 reasonable, an example, while the first announcement of a merger - I don't think 181 00:14:04,090 --> 00:14:09,750 NIST said that you have to publicly announce - but HILA5 merged with Round2, 182 00:14:09,750 --> 00:14:15,019 and of course this was after the HILA5 attack and part of the merger was fixing 183 00:14:15,019 --> 00:14:20,500 the issue in that attack, and they formed Round5 and they said "Round5, this result 184 00:14:20,500 --> 00:14:25,220 of the merge, is a leading lattice-based candidate in terms of security, bandwidth 185 00:14:25,220 --> 00:14:30,510 and CPU performance". So, three weeks later, the security turned out to be kind 186 00:14:30,510 --> 00:14:35,730 of a problem. Mike Hamburg said that here is a very strong reason to believe that 187 00:14:35,730 --> 00:14:43,320 decryption failures are much much more likely than what they claimed, and as a 188 00:14:43,320 --> 00:14:49,230 result of that, and they they accepted the argument and said yeah, oops. As a result 189 00:14:49,230 --> 00:14:51,390 of that, like I mentioned before, decryption failures are something that 190 00:14:51,390 --> 00:14:57,079 attackers can use to break security. And it's not that that a full attack was 191 00:14:57,079 --> 00:15:01,959 implemented, but it's pretty clear that the attack would work, and this is also an 192 00:15:01,959 --> 00:15:06,020 interesting attack because the mergers were supposed to be just taking, like take 193 00:15:06,020 --> 00:15:09,970 the best features of your two submissions, that you're merging. But this was a 194 00:15:09,970 --> 00:15:14,110 mistake. The vulnerability that Hamburg exploited was a mistake that was not in 195 00:15:14,110 --> 00:15:19,100 either of the submissions that were being put together. So there's some process of 196 00:15:19,100 --> 00:15:23,889 break and fix and merge, making more mistakes, which get broken and then fixed 197 00:15:23,889 --> 00:15:28,490 and, well, what was the fix. They said, "oh, here's a proposed fix". They're 198 00:15:28,490 --> 00:15:32,019 "looking at the security proof adjustments", there will be a Round5 real 199 00:15:32,019 --> 00:15:35,949 proposal, their actual merge will be in the future. I think now they have Round5a, 200 00:15:35,949 --> 00:15:42,800 Round5b and Round5c, where A is broken, B is questionable, C is still not defined. 201 00:15:42,800 --> 00:15:48,990 What does a security proof, what does a security proof mean, if you have a 202 00:15:48,990 --> 00:15:52,779 security proof previously that they were adjusting, and the security proof is for 203 00:15:52,779 --> 00:15:58,250 something that is not actually secure. Very strange. More merger announcements, 204 00:15:58,250 --> 00:16:01,690 post-quantum RSA encryption and post- quantum RSA signatures merged to form 205 00:16:01,690 --> 00:16:05,830 post-quantum RSA, saying that that "is a leading candidate in terms of depth of 206 00:16:05,830 --> 00:16:10,660 security analysis, amount of network traffic, and flexibility". For people not 207 00:16:10,660 --> 00:16:17,100 familiar with post-quantum RSA, this means using RSA with gigabyte or terabyte keys, 208 00:16:17,100 --> 00:16:20,110 which is leading in the amount of network traffic. 209 00:16:20,110 --> 00:16:21,630 *laughter* *applause* 210 00:16:21,630 --> 00:16:27,600 DJB: We want the internet to have as much cryptography as possible. 211 00:16:27,600 --> 00:16:32,391 TL: Use more bandwidth. DJB: Yeah. Remember, you have, if you're 212 00:16:32,391 --> 00:16:38,620 measuring the amount of encrypted data on your network, this increases that. More 213 00:16:38,620 --> 00:16:42,040 mergers, more mergers, more mergers. Some of these are kind of gluing submissions 214 00:16:42,040 --> 00:16:47,210 together in a way that does not simplify the, the security analysis. But this last 215 00:16:47,210 --> 00:16:50,839 one is a good example, I would say, of a merge entry. NTRU-HRSS and NTRUEncrypt, 216 00:16:50,839 --> 00:16:55,019 two of the NTRU-based submissions, they actually put some thought into what they 217 00:16:55,019 --> 00:16:59,470 wanted to keep and what they wanted to throw away. And so analyzing the merge is 218 00:16:59,470 --> 00:17:06,520 easier than analyzing the, both of the initial submissions. After the November 219 00:17:06,520 --> 00:17:11,629 deadline for mergers, NIST said they will announce the second round candidates. 220 00:17:11,629 --> 00:17:16,539 Maybe it'll be, probably less than 30, some hints it'll be 25 or even 20, 221 00:17:16,539 --> 00:17:20,230 candidates, and maybe that's starting to get down to a small enough flood that we 222 00:17:20,230 --> 00:17:25,399 can start seriously analyzing what's left. They're going to announce that, I think on 223 00:17:25,399 --> 00:17:29,460 exactly January 10th they're scheduled to do that, and then a week after this 224 00:17:29,460 --> 00:17:33,539 announcement they said, "Well, the government might be shutting down, and in 225 00:17:33,539 --> 00:17:37,770 that case we're not allowed to do any work, so we're going to be completely 226 00:17:37,770 --> 00:17:42,609 silent in case of a shutdown". It's important in the U.S. government, during 227 00:17:42,609 --> 00:17:48,389 shutdown there's a definition of essential personnel, like NSA, and non-essential 228 00:17:48,389 --> 00:17:51,260 personnel, like people protecting us against NSA. 229 00:17:51,260 --> 00:17:54,100 *laughter* DJB: - and only the essential personnel 230 00:17:54,100 --> 00:17:58,789 are allowed to do work. You know what else is not allowed to do work? The backend 231 00:17:58,789 --> 00:18:06,960 database for NIST's web pages, which might sound a little bit weird, although maybe 232 00:18:06,960 --> 00:18:11,850 they're paying Oracle for the backend database, and they have to turn off the 233 00:18:11,850 --> 00:18:16,289 payments to Oracle. I don't know what's going on here, but if you look for the 234 00:18:16,289 --> 00:18:21,750 competition information, you can't find it on their web pages anymore. We're not 235 00:18:21,750 --> 00:18:25,109 quite sure how long this shutdown is going to last. Of course, there are some people 236 00:18:25,109 --> 00:18:31,990 who say that this is not a problem, because we can figure out without this 237 00:18:31,990 --> 00:18:35,759 competition how to protect ourselves against quantum computers. 238 00:18:35,759 --> 00:18:38,999 *laughter* TL: All right, now that we have aliens 239 00:18:38,999 --> 00:18:44,309 already, are quantum computers actually coming? Big question, we don't know. What 240 00:18:44,309 --> 00:18:48,899 we can monitor is progress in quantum computing and just middle December, there 241 00:18:48,899 --> 00:18:54,109 was a news item from IonQ, which is a small startup company, announcing their 242 00:18:54,109 --> 00:19:00,960 largest ever quantum computer based on ion traps. All the other quantum computers 243 00:19:00,960 --> 00:19:04,929 we've seen so far, which are of this size, like 40 to 70, they were using 244 00:19:04,929 --> 00:19:09,769 superconducting qubits. So, it is again a race between different technologies, but 245 00:19:09,769 --> 00:19:14,340 both of them are advancing, and there are some more which are growing. So, it looks 246 00:19:14,340 --> 00:19:18,119 like it's coming. Whenever I see that picture like this, I'm reminded of a nice 247 00:19:18,119 --> 00:19:23,750 joke from a colleague of mine, Steven Galbraith. 248 00:19:23,750 --> 00:19:31,369 *laughter* TL: Can you distinguish? Yep. So, with all 249 00:19:31,369 --> 00:19:34,590 these news coming up, the National Academy of Sciences in the US has been 250 00:19:34,590 --> 00:19:38,059 interviewing people for the last about year and a half. So they got people in 251 00:19:38,059 --> 00:19:41,789 physics and engineering, building quantum computers, people doing quantum 252 00:19:41,789 --> 00:19:45,879 algorithms, people doing quantum error- correcting codes, and putting all of this 253 00:19:45,879 --> 00:19:51,179 together into a report, which just came out, where they look into, well, what is 254 00:19:51,179 --> 00:19:56,110 the progress and what are the prospects. So the first part of key findings, the 255 00:19:56,110 --> 00:20:01,759 first one is the good news, saying don't panic. We do not expect that anything is 256 00:20:01,759 --> 00:20:07,940 going to happen in the next 10 years which will threaten RSA 2048 or similar, where I 257 00:20:07,940 --> 00:20:12,909 assume what they mean, well, elliptic curves, discrete logs on finite fields. So 258 00:20:12,909 --> 00:20:16,909 that's the good news. But they wouldn't have just one key finding, it actually 259 00:20:16,909 --> 00:20:24,019 goes on, two three, ten, by the time they reach 10, I think this is panic. So that 260 00:20:24,019 --> 00:20:27,710 they say is, well, it takes forever to roll out these things. The hazard of such 261 00:20:27,710 --> 00:20:34,599 a machine is high enough. And then, "the deployment of post-quantum cryptography is 262 00:20:34,599 --> 00:20:39,019 critical for minimizing the chances of a potential security and privacy disaster". 263 00:20:39,019 --> 00:20:43,299 These are strong words from the National Academy of Sciences. 264 00:20:43,299 --> 00:20:49,049 DJB: So, OK, can we deploy post-quantum cryptography? Is it deployable? Well, some 265 00:20:49,049 --> 00:20:55,070 people would say we've already deployed it, but maybe that doesn't include the 266 00:20:55,070 --> 00:20:59,460 NIST submissions, so let's look at the deployability of the NIST submissions. The 267 00:20:59,460 --> 00:21:04,220 main thing that matters for deployment in most applications, the main problem for 268 00:21:04,220 --> 00:21:09,989 post quantum cryptography, is the sizes. So, here's a picture of the night sky over 269 00:21:09,989 --> 00:21:16,099 Leipzig. No, this is a picture of, on the horizontal axis is the size of your public 270 00:21:16,099 --> 00:21:20,139 key for a bunch of signature systems, not all of the signature systems, for instance 271 00:21:20,139 --> 00:21:24,899 WalnutDSA, which is broken with a script in the first five versions - 272 00:21:24,899 --> 00:21:28,099 TL: Post-quantum RSA is missing. DJB: Yeah, post-quantum RSA is also 273 00:21:28,099 --> 00:21:30,099 omitted from this, sorry. TL: It's kind of, of 274 00:21:30,099 --> 00:21:36,230 *laughter* DJB: Yeah, that would be like, I'm one of 275 00:21:36,230 --> 00:21:38,349 the designers of post-quantum RSA by the way. 276 00:21:38,349 --> 00:21:40,769 TL: I'm not. DJB: It's the future of cryptography. 277 00:21:40,769 --> 00:21:47,190 *laughter* DJB: That was good. Yeah. So what you can 278 00:21:47,190 --> 00:21:51,450 see here is, for example this "gui" submission, this has, you can get your 279 00:21:51,450 --> 00:21:56,730 your verticals, the signature size down to just 32 bytes or 35 bytes, something like 280 00:21:56,730 --> 00:22:02,789 that, but you need something like 400,000 bytes in your public key. And then there's 281 00:22:02,789 --> 00:22:06,830 three different dots for gui. Those are three different security levels, and maybe 282 00:22:06,830 --> 00:22:10,259 all the different submissions here are maybe not exactly comparable on the 283 00:22:10,259 --> 00:22:13,629 security levels. It should be a three dimensional graph, if we measure 284 00:22:13,629 --> 00:22:17,350 everything properly by exactly how secure it is, which of course we're not quite 285 00:22:17,350 --> 00:22:21,749 sure about until there's been enough security analysis. You can see, various 286 00:22:21,749 --> 00:22:26,009 different trade-offs are possible, none of which are down where we want to be with 287 00:22:26,009 --> 00:22:29,860 things like under 100 bytes for your public key and under 100 bytes for your 288 00:22:29,860 --> 00:22:33,890 signature, which is what we're used to right now. That's what ecliptic curve 289 00:22:33,890 --> 00:22:39,059 crypto gives us, is signature sizes and public sizes, which are both below 100 290 00:22:39,059 --> 00:22:42,559 bytes. And that's something you can fit into your applications much more easily 291 00:22:42,559 --> 00:22:49,559 than, say, 100,000 byte public keys or 10,000 byte signatures. There's various 292 00:22:49,559 --> 00:22:52,429 different trade-offs, and maybe your application can handle some of that, but 293 00:22:52,429 --> 00:22:57,309 there's nothing that's just really small, which is what we're used to right now. 294 00:22:57,309 --> 00:23:02,489 Another more complicated graph. This is for encryption and showing more 295 00:23:02,489 --> 00:23:06,870 candidates. Well, there are more encryption submissions. This is still not 296 00:23:06,870 --> 00:23:10,890 all of the encryption submissions, but a representative sample. And you can see 297 00:23:10,890 --> 00:23:18,220 that, well, there's still no really great sizes here. The best in terms of sizes is 298 00:23:18,220 --> 00:23:24,210 "sike", supersingular isogeny keyexchange, which is something like 400, little less 299 00:23:24,210 --> 00:23:28,019 than 400 bytes for the public key and for the cipher text, and then it starts 300 00:23:28,019 --> 00:23:32,309 getting bigger from there. And you get, on this graph you get things up to megabyte 301 00:23:32,309 --> 00:23:37,590 or bigger. You can get a little below 300-400 bytes, you can get down to 100 or 302 00:23:37,590 --> 00:23:42,560 so bytes for the cipher text, as long as you are willing to accept a public key 303 00:23:42,560 --> 00:23:47,460 that's much, much bigger, with some of these code-based systems. And then just to 304 00:23:47,460 --> 00:23:50,889 zoom in on some of the smaller ones, you can start seeing where some different 305 00:23:50,889 --> 00:23:57,080 candidates are. This is everything which is public key and cipher text below 1280 306 00:23:57,080 --> 00:24:02,809 bytes. And again, you see "sike" down there, a little below 400 bytes, and then 307 00:24:02,809 --> 00:24:07,289 some other possibilities. But well, what are the security levels of these things? 308 00:24:07,289 --> 00:24:10,420 Could all of these be broken? There's not actually that many of them, how many of 309 00:24:10,420 --> 00:24:14,340 these have actually been studied? It's kind of scary. And again, much bigger 310 00:24:14,340 --> 00:24:19,899 sizes than we're used to in cryptography. TL: So, yes, size does matter. 311 00:24:19,899 --> 00:24:24,219 *laughter* TL: So, Google and Cloudflare this year in 312 00:24:24,219 --> 00:24:27,729 April were saying, well, we don't really know what the outcome of this competition 313 00:24:27,729 --> 00:24:33,049 is going to be, but we have some categories of different crypto systems, 314 00:24:33,049 --> 00:24:38,080 and let's just send dummy packets of data of respective sizes, and see what happens 315 00:24:38,080 --> 00:24:40,999 when we do this on the Internet. Now this is Google and Cloudflare, so they they 316 00:24:40,999 --> 00:24:44,729 were doing this on the Chrome browser for connections that go through Cloudflare, so 317 00:24:44,729 --> 00:24:49,879 they could actually see from where it came, where it ended, whether it came 318 00:24:49,879 --> 00:24:54,460 back, whether it dropped. Dan mentioned "sike", so this is the one category of 319 00:24:54,460 --> 00:24:59,229 supersingular isogenies, those are just 400 bytes. And that was pretty much fine, 320 00:24:59,229 --> 00:25:03,129 so when you look at the first column, you have a small latency increase. You also 321 00:25:03,129 --> 00:25:12,529 see the inaccuracy, that's a -0.2. So, the numbers are mostly correct. Then there is, 322 00:25:12,529 --> 00:25:15,389 in the lattices, this was the zoom-in what Dan was showing, those are mostly 323 00:25:15,389 --> 00:25:19,320 something that could take a, we have structured lattices, those are around the 324 00:25:19,320 --> 00:25:27,159 MTU, so 1,100 something bytes. And that was, mostly worked, some small increases, 325 00:25:27,159 --> 00:25:30,840 but under 20 percent, so this is also something we feel like, yes, you could 326 00:25:30,840 --> 00:25:35,999 actually deploy this on the Internet. Then a different category still within lattices 327 00:25:35,999 --> 00:25:40,649 are unstructured lattices. Those would come with 10 kilobytes of data for the 328 00:25:40,649 --> 00:25:46,450 public key. And there they just noticed that too many pages, including, like, top 329 00:25:46,450 --> 00:25:52,979 pages on Alexa 500, such as LinkedIn, were just dropping. They tried, funny enough, 330 00:25:52,979 --> 00:25:59,090 9999, where fewer pages was dropping, so 10K was worse than 9999, but even then 331 00:25:59,090 --> 00:26:03,360 LinkedIn was still dropping. And so they decreased it to a third, as basically a 332 00:26:03,360 --> 00:26:09,960 placeholder, measured with these 3300 bytes, and then scaled up by a factor of 333 00:26:09,960 --> 00:26:18,149 three. Now, those increases in the latency is what they said, well, this is not 334 00:26:18,149 --> 00:26:20,830 acceptable. So then for the next experiments, they were only looking at 335 00:26:20,830 --> 00:26:27,409 isogenies and structured lattices. Isogenies are also special, not just being 336 00:26:27,409 --> 00:26:31,869 the smallest, but also being the slowest. Well okay, not absolutely the slowest, but 337 00:26:31,869 --> 00:26:38,659 it's the only system where the speed is much more an issue than the size. And so 338 00:26:38,659 --> 00:26:41,219 despite Google having quite a few computers, they were saying we can't 339 00:26:41,219 --> 00:26:45,889 actually use isogenies for the speed reasons. Size would be awesome, but speed, 340 00:26:45,889 --> 00:26:52,239 not so sure. It's also a relatively recent system, it's just in 2012. So maybe also 341 00:26:52,239 --> 00:26:56,289 it's a security question. So just now in December, they announced that they're 342 00:26:56,289 --> 00:26:59,789 actually building a new experiment, they announced which candidate they have 343 00:26:59,789 --> 00:27:02,899 chosen, NTRU-HRSS, which Dan just mentioned was also one of the recent 344 00:27:02,899 --> 00:27:07,389 mergers. And so this is one of the structured lattices systems, designers are 345 00:27:07,389 --> 00:27:13,609 Andreas Hulsing, Joost Rijneveld, Peter Schwab and John Schanck. Great score for 346 00:27:13,609 --> 00:27:20,889 Eindhoven team, current professor, former student, and then some collaborators. And 347 00:27:20,889 --> 00:27:25,379 so they're now building a system which is a combined elliptic curve, so that's the 348 00:27:25,379 --> 00:27:29,389 combined EC, that's combined elliptic curves and post-quantum. This is the 349 00:27:29,389 --> 00:27:33,669 second round running, and so this would come to some Internet browser near you 350 00:27:33,669 --> 00:27:39,339 soon. Another nice result, I mean this is not the only thing up there. The IETF this 351 00:27:39,339 --> 00:27:43,929 year finished standardizing XMSS, which is a hash based signature system. It's been 352 00:27:43,929 --> 00:27:46,429 in the making, down there you see the timeline, it's been in the making for 353 00:27:46,429 --> 00:27:51,100 three years. It's not really fast, but it's also the first of its kind. This was 354 00:27:51,100 --> 00:27:55,919 the first time that IETF has published a post-quantum RFC, request for comments, 355 00:27:55,919 --> 00:27:59,409 but that's basically their standards. And so there's a lot of boilerplate text, 356 00:27:59,409 --> 00:28:03,280 which was developed in this thing, in the process of making the standard, which is 357 00:28:03,280 --> 00:28:08,080 dealing with, yeah, post-quantum, quantum attacks and so on, how you should handle 358 00:28:08,080 --> 00:28:13,210 it. XMSS is interesting. It's not one of the NIST submissions, because it doesn't 359 00:28:13,210 --> 00:28:16,700 satisfy the normal thing that you learn in primary school, what a signature should be 360 00:28:16,700 --> 00:28:22,830 doing. Signature you expect to have a public key. You use it to sign something, 361 00:28:22,830 --> 00:28:29,379 and then you have a signature. XMSS, you have a public key, you have a state. You 362 00:28:29,379 --> 00:28:33,690 get a message, you sign it, and you update your state. And if you ever forget to 363 00:28:33,690 --> 00:28:39,600 update your state, you will lose security. So it's something which is not as cool as 364 00:28:39,600 --> 00:28:43,029 a normal signature scheme, but there are also many applications where you actually 365 00:28:43,029 --> 00:28:46,690 know how many signatures you've made. I mean, if you're doing operating system 366 00:28:46,690 --> 00:28:52,289 updates, you better know how often you got your key out of the drawer and used it. So 367 00:28:52,289 --> 00:28:56,229 it is not impossible to use, but it might not be exactly what you want for your web 368 00:28:56,229 --> 00:28:59,700 applications. DJB: Good thing about XMSS is still, if 369 00:28:59,700 --> 00:29:04,200 you can count, then the size is much smaller than the signature systems that we 370 00:29:04,200 --> 00:29:09,549 were looking at before. Another size advantage, size advance is something 371 00:29:09,549 --> 00:29:13,239 called Glowstick. I should explain the name. This is starting from a lattice 372 00:29:13,239 --> 00:29:18,780 submission called Saber, which is one of the unbroken ones, and Saber has a big 373 00:29:18,780 --> 00:29:23,399 version called FireSaber, high security level, scaled up. It also has a small 374 00:29:23,399 --> 00:29:28,509 version called LightSaber. *laughter and groans* 375 00:29:28,509 --> 00:29:35,029 DJB: And this Glowstick is the even smaller version. It's like, let's scale it 376 00:29:35,029 --> 00:29:39,950 down as far as we can get that it's not quite broken, and there's various 377 00:29:39,950 --> 00:29:45,299 technical details and it hasn't been broken in the months since it's been 378 00:29:45,299 --> 00:29:49,669 proposed, the six months or so, and it is interesting. I mean, it is something which 379 00:29:49,669 --> 00:29:54,039 is a good challenge. It's nice to have these scaled down problems, so we can try 380 00:29:54,039 --> 00:29:57,580 different ways of attacking these things and people who like breaking stuff, it's 381 00:29:57,580 --> 00:30:01,339 good to have the simpler systems to practice doing attacks, and that gives you 382 00:30:01,339 --> 00:30:04,080 some insight into what could work against the larger systems. 383 00:30:04,080 --> 00:30:09,779 TL: All right. So, since we're coming to funny names... Oh, no, since we're coming 384 00:30:09,779 --> 00:30:16,009 to sizes, why do we still care about big sizes? I mean, people are scaling things 385 00:30:16,009 --> 00:30:19,759 down. Google says, oh, we don't like big sizes. So why do people say post-quantum 386 00:30:19,759 --> 00:30:24,529 systems are bigger and we still care about it? So one of the reasons is, well, 387 00:30:24,529 --> 00:30:28,779 highlighting McEliece here, which is our submission in this competition, these have 388 00:30:28,779 --> 00:30:34,509 had a lot of analysis. So classic McEliece is based on a system from 1978, basically 389 00:30:34,509 --> 00:30:39,519 unchanged except for some changes where we can really prove this is the same as that. 390 00:30:39,519 --> 00:30:43,659 It has one of the shorter ciphertext, just 200 bytes, so that's actually kind of 391 00:30:43,659 --> 00:30:50,899 tolerable on the Internet, but a megabyte of key. Key generation is also pretty 392 00:30:50,899 --> 00:30:55,609 slow, but then the, well, it's nowadays called encapsulation, decapsulation 393 00:30:55,609 --> 00:30:59,289 because all you want is your AES key, you don't want to actually encrypt the 394 00:30:59,289 --> 00:31:04,960 message, but basic thing of encryption and decryption of that. So, nice system, very 395 00:31:04,960 --> 00:31:11,609 good history in security, pretty fast, pretty small, except for the public keys. 396 00:31:11,609 --> 00:31:18,909 It's like, "Grandma, why do you have so big keys?". Why are these keys so big? So 397 00:31:18,909 --> 00:31:21,629 one thing is, it's like a two dimensional key. We have this big matrix there, what 398 00:31:21,629 --> 00:31:28,359 you see on the left is an identity matrix. This thing has about 7000 columns. It's 399 00:31:28,359 --> 00:31:33,479 like pretty long. It's only for, the height is n-k, which is just like thousand 400 00:31:33,479 --> 00:31:40,309 five hundred, so it's really long and stretched. And so all of this part on your 401 00:31:40,309 --> 00:31:46,700 right-hand side, that part is random and you have to send that. You can of course, 402 00:31:46,700 --> 00:31:49,919 everybody remembers what an identity matrix looks like. You can forget about 403 00:31:49,919 --> 00:31:55,369 this one, but this one you have to send, because the encryption works by the sender 404 00:31:55,369 --> 00:32:01,049 thinking, which of those around 7000 column he wants to pick, and then just 405 00:32:01,049 --> 00:32:06,019 XORing them up, and for doing that, well, you need to have this big matrix. 406 00:32:06,019 --> 00:32:13,760 And if you calculate, well, 1547 times 5413 , that's the part of the right matrix, 407 00:32:13,760 --> 00:32:19,100 you're getting to this one megabyte size. Now what are the issues with having big keys? 408 00:32:19,100 --> 00:32:24,909 It's bandwidth, but honestly, when you download, a picture it's also a megabyte. 409 00:32:24,909 --> 00:32:28,969 So, it might not be so bad. I mean, if you're on the German trains then you will 410 00:32:28,969 --> 00:32:31,190 hate it, but - *laughter* 411 00:32:31,190 --> 00:32:37,489 TL: - normally, elsewhere in the world or on your mobile, it's fine. Google was 412 00:32:37,489 --> 00:32:44,159 saying, we actually excluded some systems, so they didn't experiment with classic 413 00:32:44,159 --> 00:32:48,920 McEliece, largest they looked at was 10,000 kilobytes, and even then some dropped, 414 00:32:48,920 --> 00:32:53,509 and they said, well, some are too large to be viable within TLS. 415 00:32:53,509 --> 00:32:59,510 So they just said, well, we don't do this. But then again, you have a secure system. 416 00:32:59,510 --> 00:33:04,300 You can just also design a secure protocol to go with it. We don't need to stick with TLS. 417 00:33:04,300 --> 00:33:09,249 But there is a real problem with having a megabyte of key, because if your 418 00:33:09,249 --> 00:33:15,080 protocol assumes that the client generates this one megabyte and then just throws it 419 00:33:15,080 --> 00:33:19,739 at the server, and the server has to accept one megabyte from every single 420 00:33:19,739 --> 00:33:24,450 client that is throwing a megabyte at it, and then has to do something with it, 421 00:33:24,450 --> 00:33:28,419 well, this is really an invitation for a denial of service attack, because you're 422 00:33:28,419 --> 00:33:32,810 allocating memory on the server for doing these operations. The operations are pretty fast, 423 00:33:32,810 --> 00:33:39,677 it's just XORing 0s and 1s, but you have to allocate 1 megabyte for each client. 424 00:33:39,677 --> 00:33:43,159 And so this is a problem, no matter what the protocol we designed, 425 00:33:43,159 --> 00:33:47,939 we have to deal with the possibility of denial of service attacks, or avoid them. 426 00:33:47,939 --> 00:33:53,259 So, can servers avoid storing these big keys? You want to XOR 427 00:33:53,259 --> 00:33:58,259 these columns, so one of the first limitation on small devices was saying, 428 00:33:58,259 --> 00:34:05,190 well, "I'm a very small device, but I can pick those positions and then, outside 429 00:34:05,190 --> 00:34:11,490 world, please be nice to me and spoon feed me one column at a time". So the small 430 00:34:11,490 --> 00:34:18,331 device memorizes 1500 bits, not so big, and then gets the next column. 431 00:34:18,331 --> 00:34:22,859 If it was selected, it XORs it in, if it wasn't selected, well, it keeps the intermediate 432 00:34:22,859 --> 00:34:29,470 state. So this works. And at the end, you output the normal ciphertext. But what we 433 00:34:29,470 --> 00:34:33,899 have here is, we're operating in a friendly environment where we do not 434 00:34:33,899 --> 00:34:39,109 expect this outside world to do something nasty to us, and also we have some memory. 435 00:34:39,109 --> 00:34:45,829 Now if we put this on the real Internet and we don't want to have any state, so we 436 00:34:45,829 --> 00:34:49,260 cannot memorize these 1500, because, well, we don't know when the next column is 437 00:34:49,260 --> 00:34:56,038 going to come, so we output and send this back to this client. That's not gonna work. 438 00:34:56,038 --> 00:35:03,119 When you tell the client, "Oh, this is my current result", then the server 439 00:35:03,119 --> 00:35:07,869 gets the next column, maybe XORs it in, maybe not, sends it back to the client, 440 00:35:07,869 --> 00:35:11,980 anybody who is watching this traffic could see whether there was a change or there 441 00:35:11,980 --> 00:35:16,829 was no change. So this is not a way of dealing with it. So what Dan and I have 442 00:35:16,829 --> 00:35:20,900 been busy with, and, well, I put 2018 with a question mark, we still have like three 443 00:35:20,900 --> 00:35:26,640 days, right? So we're working on this system called McTiny, tiny because it's 444 00:35:26,640 --> 00:35:32,918 made for tiny web servers, where we assume that this web server is not allocating 445 00:35:32,918 --> 00:35:38,590 any per-client storage, any per-client state. And so, we again work with spoon feeding 446 00:35:38,590 --> 00:35:43,079 things, but we're making sure that everything that the server gets and sends 447 00:35:43,079 --> 00:35:48,740 out is encrypted, is authenticated, there is some stuff to avoid replay attacks, so 448 00:35:48,740 --> 00:35:53,789 that somebody can't just say, "oh, what if I change the column here or there". So all 449 00:35:53,789 --> 00:35:59,430 these things are encrypted, and what we do is we use properties of doing these sums 450 00:35:59,430 --> 00:36:05,770 and pieces by chunking up this big matrix into chewable pieces that are small enough 451 00:36:05,770 --> 00:36:11,299 to fit in one MTU and still have some space for some cookies. So this is similar 452 00:36:11,299 --> 00:36:16,650 to normal uses of cookies, this is a cookie, encrypted to the server, send to 453 00:36:16,650 --> 00:36:21,399 a client, you handle the storage, and then client sends the next piece, 454 00:36:21,399 --> 00:36:26,779 sends the old cookie. Now, the cookie is encrypted, but the way that the key is 455 00:36:26,779 --> 00:36:31,900 handled is the same for all clients. So there is no per-client storage of any 456 00:36:31,900 --> 00:36:36,019 keys. It's a symmetric key, it's pretty small. So that's the one thing that the 457 00:36:36,019 --> 00:36:40,390 server remembers, and then it gets a packet, it from this cookie part recovers 458 00:36:40,390 --> 00:36:44,549 all the, like, which columns to pick, what's the intermediate result, and then 459 00:36:44,549 --> 00:36:50,470 does some computation, sends it back. So, the result of this is that we need several 460 00:36:50,470 --> 00:36:55,090 round trips, but there's absolutely no per-client state on the server. 461 00:36:55,090 --> 00:37:00,849 DJB: Of course you could say, well, there were still all that bandwidth, and what if 462 00:37:00,849 --> 00:37:06,170 you do have bandwidth problems, but some people say that we're familiar with 463 00:37:06,170 --> 00:37:11,858 sending a lot of data around, so that's really not a big deal. Something else that 464 00:37:11,858 --> 00:37:15,670 could interfere with deployment is patents. Now Tanja mentioned before that 465 00:37:15,670 --> 00:37:20,250 classic McEliece does not have patents, but what if somebody says, "I just don't 466 00:37:20,250 --> 00:37:23,240 want to handle the megabyte", or for whatever reason people want something 467 00:37:23,240 --> 00:37:28,750 smaller or there are signature questions. Well, we have a lot of information about 468 00:37:28,750 --> 00:37:33,369 some systems which are patented. The 18 systems shown here, because NIST had as 469 00:37:33,369 --> 00:37:37,770 one of the rules for the competition that you had to deliver statements to them, 470 00:37:37,770 --> 00:37:42,599 signed by every member of the submission team, saying either "we do not have 471 00:37:42,599 --> 00:37:46,970 patents, patent applications on our submission", or, "here's the patents, 472 00:37:46,970 --> 00:37:50,490 patent applications, here's their numbers". And so, OK, as a result of that 473 00:37:50,490 --> 00:37:53,549 and NIST, after checking they had a complete pile of statements, put them 474 00:37:53,549 --> 00:37:57,510 online, so now we know that these are exactly the 18 submissions where the 475 00:37:57,510 --> 00:38:02,110 submission teams claim patents on their submissions, including for example Compact 476 00:38:02,110 --> 00:38:08,250 LWE and DME and WalnutDSA, which are rapidly broken by scripts that are online. 477 00:38:08,250 --> 00:38:11,990 And RLCE-KEM, that one has half of the parameters are broken, there's another 478 00:38:11,990 --> 00:38:16,099 half which are not broken. It's not that the patented submissions are somehow 479 00:38:16,099 --> 00:38:19,710 better than the rest of the submissions, but well, for some reason people think 480 00:38:19,710 --> 00:38:23,980 they can make money off of patents, and maybe they're not actually so wrong, 481 00:38:23,980 --> 00:38:28,430 because you can't just throw away these 18 submissions and say "that's the end of it". 482 00:38:28,430 --> 00:38:37,619 The problem is that there's some patents which cover more submissions. Now, 483 00:38:37,619 --> 00:38:45,490 NIST does not require these submitters to say that, "here's which patents are, which 484 00:38:45,490 --> 00:38:50,839 submissions are covered by my patent". The submitters are only required to say 485 00:38:50,839 --> 00:38:54,980 something about their own submissions, and also NIST has no way to say anything about 486 00:38:54,980 --> 00:38:58,779 whatever random patent trolls that are out there, that have not submitted anything. 487 00:38:58,779 --> 00:39:03,119 They can't impose any rules on that. I mean, of course you can try doing patent 488 00:39:03,119 --> 00:39:07,434 searches, but you won't necessarily find things, for instance this patent. Nobody 489 00:39:07,434 --> 00:39:14,690 noticed until it was revealed in, well, by a member of some submission team, this 490 00:39:14,690 --> 00:39:19,780 patent was issued in 2015, at the top there, which might make you think, "oh, if 491 00:39:19,780 --> 00:39:23,369 something was published before 2015, it would be okay", and some submissions were 492 00:39:23,369 --> 00:39:28,369 published earlier. But what's important is the date down at the bottom here, which is 493 00:39:28,369 --> 00:39:33,660 the priority date of February 18th 2010. If you look on Google Patents, one good 494 00:39:33,660 --> 00:39:38,000 thing is they put the priority date pretty far up, where you can easily see it. What 495 00:39:38,000 --> 00:39:43,140 this means is that, in order to be prior art for this patent, well, you have to 496 00:39:43,140 --> 00:39:46,540 check what exactly they filed in 2010. They might have made later changes, 497 00:39:46,540 --> 00:39:51,170 but the 2010 thing, assuming that has all the same stuff as the patent, which it's 498 00:39:51,170 --> 00:39:57,440 possible to find out, this, anything that was published after 2010 is not prior art 499 00:39:57,440 --> 00:40:02,109 for this. Now what's really scary about this patent, and I hope that really soon 500 00:40:02,109 --> 00:40:06,010 I'm gonna have analysis online of which submissions are covered by which patents 501 00:40:06,010 --> 00:40:10,310 of all the patents I've seen. This one is by far the scariest, because this one 502 00:40:10,310 --> 00:40:15,450 covers a whole bunch of submissions. This one covers basically every submission 503 00:40:15,450 --> 00:40:21,440 which is using what's called the LPR cryptosystem, a ring-LWE-lattice-based 504 00:40:21,440 --> 00:40:25,710 crypto system. This is a very popular type of lattice-based crypto system, which was 505 00:40:25,710 --> 00:40:35,880 published by L, P, and R, Lyubashevsky, Peikert, and Regev, in May 2010, which is 506 00:40:35,880 --> 00:40:43,930 after this patent application was filed. Now, there was a talk in April which had 507 00:40:43,930 --> 00:40:48,640 the same stuff from LPR, and it seems like there might even have been a talk in 508 00:40:48,640 --> 00:40:54,430 January from LPR, but they didn't put the slides online, and then, well, it starts 509 00:40:54,430 --> 00:40:57,996 getting into interesting questions of patent law. This looks like a very 510 00:40:57,996 --> 00:41:01,839 strong patent, covering a whole lot of submissions, and there's more cases, 511 00:41:01,839 --> 00:41:05,970 there's a whole company called ISARA that is specializing in planting landmines, 512 00:41:05,970 --> 00:41:10,240 patent landmines, around things that other people are doing, sometimes on things that 513 00:41:10,240 --> 00:41:14,273 other people have already published, and then you get a court fight about it. This 514 00:41:14,273 --> 00:41:17,920 is gonna be a problem; it's something we really have to watch out for, is what is 515 00:41:17,920 --> 00:41:24,253 patented, and again, I hope to be sometime soon done with some patent analysis. 516 00:41:24,253 --> 00:41:28,619 Of course, some people would say that we don't have to worry about patents as long 517 00:41:28,619 --> 00:41:32,340 as we find something that we can deploy, that somebody tries deploying it 518 00:41:32,340 --> 00:41:36,069 and they don't get sued. TL: Not sure that's going to be deployed 519 00:41:36,069 --> 00:41:44,937 anytime soon. I mean, 95 out of 3000, *Laughter* okay. All right. Funny names, I said. 520 00:41:44,937 --> 00:41:55,170 So what do you see here? Can anybody read phonetics? Yeah? "si-said". Okay, so, 521 00:41:55,170 --> 00:42:02,040 seaside. Now, CSIDH is what you really always wanted. CSIDH is an efficient post- 522 00:42:02,040 --> 00:42:06,350 quantum commutative group action. Did you know that you wanted a commutative group 523 00:42:06,350 --> 00:42:14,119 action? Actually, you did. So, what all people ask me is, like, "I'm using Diffie- 524 00:42:14,119 --> 00:42:18,609 Hellman these days. What can you give me in the post-quantum world?". And then it 525 00:42:18,609 --> 00:42:25,440 depends a lot on how you define Diffie- Hellman. Some features that we come to use 526 00:42:25,440 --> 00:42:30,539 from Diffie-Hellman are that, well, you publish a public key, I publish a public key, 527 00:42:30,539 --> 00:42:37,430 other people publish public keys, and we can reuse them. Kind of nice. Also, we 528 00:42:37,430 --> 00:42:40,849 don't have to talk to each other. We can just look up the other public key on the 529 00:42:40,849 --> 00:42:45,830 phone book, have a shared key, and start using that one. And if I send you 530 00:42:45,830 --> 00:42:51,339 something encrypted with our shared public keys, like, combined thing of this, then 531 00:42:51,339 --> 00:42:55,920 you will be able to decrypt this. There are some nice other features; you can 532 00:42:55,920 --> 00:43:00,980 blind things, you can like take your g to the a and then multiply, compute in the 533 00:43:00,980 --> 00:43:06,299 exponent times r, so put some blinding factors there, and there is no difference 534 00:43:06,299 --> 00:43:11,580 whether I'm the initiator or I am the responder in this. We don't have this 535 00:43:11,580 --> 00:43:15,039 anywhere else in post quantum cryptography. All the systems that you see 536 00:43:15,039 --> 00:43:19,572 for NIST submissions make a difference between are you the sender, are you the 537 00:43:19,572 --> 00:43:25,619 responder. So this is the first efficient post-quantum, well, Diffie-Hellman-like 538 00:43:25,619 --> 00:43:32,270 thing, which, well, by fancy math called commutative group action. So, if you are a 539 00:43:32,270 --> 00:43:35,339 user, you don't want to know all the details. I'm not going to give an entire 540 00:43:35,339 --> 00:43:40,609 talk about this, unless, maybe next year. What you see exposed to you is just one 541 00:43:40,609 --> 00:43:44,410 single finite field element. So there is some fixed prime, that all the people in 542 00:43:44,410 --> 00:43:48,300 the system know, and then everybody's public key is just one single field 543 00:43:48,300 --> 00:43:55,140 element. So Alice computes her field element, Bob computes his field element, 544 00:43:55,140 --> 00:43:59,340 they post these somewhere, and then sometime later, years later, maybe if 545 00:43:59,340 --> 00:44:03,940 quantum computers are built, they find each other, they compute their shared 546 00:44:03,940 --> 00:44:08,990 public key, they combine the shared, the public keys into their shared secret key, 547 00:44:08,990 --> 00:44:13,630 sorry, and then they have the shared secret. Now, a little bit of the math 548 00:44:13,630 --> 00:44:18,480 behind this, A actually appears in some form there, so this is one of the 549 00:44:18,480 --> 00:44:20,720 elliptic curves that we've been talking about in, gosh, 550 00:44:20,720 --> 00:44:25,280 when was this, 2013 or so. No, 14 at least. DJB: 14. 551 00:44:25,280 --> 00:44:34,130 TL: So there's EA: y^2 = x^3, and then A, this public key A, x^2 + x, and that what 552 00:44:34,130 --> 00:44:41,410 the computation is to go from one key to another key is using an isogeny, same 553 00:44:41,410 --> 00:44:45,170 isogeny kind of thing that you heard in sike before, it's a math object that just 554 00:44:45,170 --> 00:44:50,039 means you move from one elliptic curve to another elliptic curve. If somebody tells 555 00:44:50,039 --> 00:44:54,759 you to implement this, what you need to get doing is, well, take this prime p, 556 00:44:54,759 --> 00:45:01,059 compute modulo p for addition, multiplications and divisions, out of 557 00:45:01,059 --> 00:45:06,760 those you for instance build the curve operations, and then some more operations 558 00:45:06,760 --> 00:45:10,960 which computes an isogeny, but all of those are just combined from those things. 559 00:45:10,960 --> 00:45:15,869 So there's nothing particularly scary behind it, except for, well, we came up 560 00:45:15,869 --> 00:45:24,900 with this thing in January 2018 at this lovely beach. Was great there, but please 561 00:45:24,900 --> 00:45:29,319 don't use it yet. Experiment with it all you want, but this has not had enough 562 00:45:29,319 --> 00:45:34,889 analysis. But another reason why you might want this is security, key sizes and so on. 563 00:45:34,889 --> 00:45:41,750 So, what are we looking at? First of all, how many keys are there? So how big 564 00:45:41,750 --> 00:45:49,359 do we have to look at this p? When you have fixed your prime p, say n bits, then 565 00:45:49,359 --> 00:45:55,819 there are square root of p, so 2 to the n over 2, many such curves. So these are the 566 00:45:55,819 --> 00:46:00,789 numbers of public keys. And then, similar to how the elliptic curve discrete log, 567 00:46:00,789 --> 00:46:05,539 kind of meet-in-the-middle attacks, work, so basically smart bruce force search, you 568 00:46:05,539 --> 00:46:11,140 get a square root of the number of keys as your security. So if you have square root 569 00:46:11,140 --> 00:46:17,940 of p many keys, it takes your fourth root of p time to find out what Alice's key is. 570 00:46:17,940 --> 00:46:23,220 So if you want 128 bit security, you have to choose your prime p four times as many 571 00:46:23,220 --> 00:46:30,570 bits, so a 512 bit prime. But this is a talk on post-quantum cryptography. 572 00:46:30,570 --> 00:46:36,310 So where do we stand there? Elliptic curves would be totally broken. Nice enough for 573 00:46:36,310 --> 00:46:40,549 isogenies, we don't have any complete break. There are some sub-exponential 574 00:46:40,549 --> 00:46:46,490 attacks, so doesn't have full exponential security as we maybe would like to have, 575 00:46:46,490 --> 00:46:49,829 on the other hand, with RSA and finite field Diffie-Hellman, we have been dealing 576 00:46:49,829 --> 00:46:53,500 with the growth of keys, with sub- exponentil attacks, so this is something 577 00:46:53,500 --> 00:46:57,910 we're familiar with. It doesn't kill things, but you look at the literature, 578 00:46:57,910 --> 00:47:01,470 it's mostly asymptotics, so we and also some others have been looking into 579 00:47:01,470 --> 00:47:06,099 details. I think our analysis, which we have at quantum.isogeny.org, is the most 580 00:47:06,099 --> 00:47:11,050 detailed one, looking into, like, what actual security you get against somebody 581 00:47:11,050 --> 00:47:16,359 with a really really big quantum computer. Now with elliptic curves, you'll hopefully 582 00:47:16,359 --> 00:47:20,049 have also learned that you must always validate, you need to get a point, 583 00:47:20,049 --> 00:47:23,420 somebody says "oh, this is my public key", the first thing you do is check, is this 584 00:47:23,420 --> 00:47:29,039 thing on the curve, does it have the right order? Same thing for isogeny-based 585 00:47:29,039 --> 00:47:32,829 crypto, for CSIDH you have a very quick check, you check that this curve has the 586 00:47:32,829 --> 00:47:35,799 number of points, you know what it is, you don't even need to do full point counting, 587 00:47:35,799 --> 00:47:42,148 you just take a point, do some scalar multiplications, and you check it. This is 588 00:47:42,148 --> 00:47:46,670 another thing that we've gotten totally used to doing. This is another thing that 589 00:47:46,670 --> 00:47:51,089 is really really really hard for most post-quantum systems. Most post-quantum 590 00:47:51,089 --> 00:47:55,839 systems you add another proof to it, so typically when you encrypt to somebody's 591 00:47:55,839 --> 00:47:59,970 key and you're sending something which looks like a key, you reveal all the 592 00:47:59,970 --> 00:48:05,230 secrets in there, that's why you can't reuse it, or you have to do a big zero 593 00:48:05,230 --> 00:48:09,759 knowledge proof to prove that you actually generated this thing properly. With CSIDH, 594 00:48:09,759 --> 00:48:15,678 it's just there. All you need to do is check if it's a valid curve, and you're done. 595 00:48:15,678 --> 00:48:21,521 Size it's also pretty neat. So, 32 bytes for the secret key, 64 bytes. 596 00:48:21,521 --> 00:48:26,140 So just twice as large as normal elliptic curves, that is really like bottom-left 597 00:48:26,140 --> 00:48:32,200 corner of Dan's graph where there was nothing, so CSIDH does fill a big gap, a 598 00:48:32,200 --> 00:48:38,210 big gap, but a small key, there with something, which pre-quantum has at least 599 00:48:38,210 --> 00:48:43,420 128 bit security and post-quantum, so what NIST was asking for is comparisons with 600 00:48:43,420 --> 00:48:48,570 AES-128 and then you look at, like, how big are the sizes, how big are the quantum 601 00:48:48,570 --> 00:48:52,801 computers and so on. And we think that CSIDH-512, to the best of our knowledge, 602 00:48:52,801 --> 00:48:57,990 based on the latest analysis, will be as secure as that. There is some code written 603 00:48:57,990 --> 00:49:09,040 by Lorenz, somewhere? Ah, Lorenz. Yay. This is on Skylake. Your mileage may vary. 604 00:49:09,040 --> 00:49:14,550 This is a, it's not a super-quick hack, but it's not deployment code. So this is 605 00:49:14,550 --> 00:49:17,349 not yet constant time, there are some others who've been working on constant 606 00:49:17,349 --> 00:49:23,769 time, it makes it about three times slower. It is similar to sike in that it's 607 00:49:23,769 --> 00:49:28,990 really nice small keys, but somewhat slow. On the other hand, this is still very new, 608 00:49:28,990 --> 00:49:32,329 it's just from January. So we're still figuring out ways to make it faster, 609 00:49:32,329 --> 00:49:36,181 whereas, well, sike has been doing a lot of work getting to the speed that they 610 00:49:36,181 --> 00:49:39,940 have now. So there's hope that this will get faster, and there's some hope it will 611 00:49:39,940 --> 00:49:45,240 remain unbroken until next year, but, well, I'm not sure yet where I'd put my 612 00:49:45,240 --> 00:49:48,737 money, at the, at this moment I think actually CSIDH has a better chance than 613 00:49:48,737 --> 00:49:53,690 sike of surviving, but who knows. Don't use it for anything yet. 614 00:49:53,690 --> 00:49:56,839 DJB: Speaking of broke, there's a lot of people who are investing 615 00:49:56,839 --> 00:50:00,819 in crypto currencies, - *laughter* 616 00:50:00,819 --> 00:50:06,359 DJB: - and I think, I think it's Nick Mathewson's fault, this whole quantum- 617 00:50:06,359 --> 00:50:10,380 cyber blockchain idea, if you know something earlier than 2016, well anyway, 618 00:50:10,380 --> 00:50:14,200 there's variations of it since then, like quantum AI blockchain, apparently you can 619 00:50:14,200 --> 00:50:20,059 buy the t-shirt. We have about 10 minutes left, so I'd like to finish things off 620 00:50:20,059 --> 00:50:25,950 with some comments on software. Now this is looking back at 40 years of public key 621 00:50:25,950 --> 00:50:32,089 cryptography, well RSA was from '77 or so, the McEliece cryptosystem from '78, and 622 00:50:32,089 --> 00:50:37,559 then, well, here's some, some schematics of what the software quality has been in 623 00:50:37,559 --> 00:50:42,049 cryptography, on a scale of "good", "bad", "terrible", and "horrifying". 1978, I 624 00:50:42,049 --> 00:50:46,280 don't actually know, I haven't seen software from back then. By 1988, it was 625 00:50:46,280 --> 00:50:51,230 clear that the software quality was horrifying. By 1998, it had moved up to 626 00:50:51,230 --> 00:50:56,099 terrible. By 2008, it moved up to bad. And by 2018, it has jumped back down to 627 00:50:56,099 --> 00:51:05,501 horrifying. *laughter and applause* 628 00:51:05,501 --> 00:51:09,510 DJB: And of course a major contributor to this is all of these NIST submissions, 629 00:51:09,510 --> 00:51:14,589 which have code written by mathematicians, who barely can implement anything and 630 00:51:14,589 --> 00:51:18,329 certainly don't have good code quality. There's occasional submission teams that 631 00:51:18,329 --> 00:51:23,079 have people who can write code, but in general, if you, well, for a good time, 632 00:51:23,079 --> 00:51:24,650 pick up a random - TL: McEliece is fine! 633 00:51:24,650 --> 00:51:28,140 DJB: Yeah, the classic McEliece code is fine. There's other submissions where the 634 00:51:28,140 --> 00:51:34,009 code is is fine, but if you just take a random submission and look at the code, 635 00:51:34,009 --> 00:51:42,769 it's, well, interesting. If you would like to find out where the software is and 636 00:51:42,769 --> 00:51:45,180 download it. *laughter* 637 00:51:45,180 --> 00:51:50,340 DJB: Yeah, NIST doesn't work very well. I did look, archive.org has, like, you 638 00:51:50,340 --> 00:51:55,589 search for "NIST round one" on DuckDuckGo, and the top link is to the NIST page, and 639 00:51:55,589 --> 00:52:00,200 then you take the URL for that, put it into archive.org, and I tried a few of the 640 00:52:00,200 --> 00:52:04,030 submissions and the zip files that NIST prepared with the specifications and the 641 00:52:04,030 --> 00:52:07,920 code, those are available from archive.org. I guess they got most or all 642 00:52:07,920 --> 00:52:12,359 of them. You can also look for more than half the submissions, there are upstream 643 00:52:12,359 --> 00:52:17,569 websites with newer code. NIST has not updated the code, but lots of submissions, 644 00:52:17,569 --> 00:52:22,990 the submission teams have, lots of the fastest code, and even some faster while 645 00:52:22,990 --> 00:52:27,210 improved code, is available in our SUPERCOP benchmarking framework, so this 646 00:52:27,210 --> 00:52:30,509 is the system for unified performance evaluation related to cryptographic 647 00:52:30,509 --> 00:52:39,359 operations and primitives, bench.cr.yp.to, and this one has, well, 170 primitives 648 00:52:39,359 --> 00:52:45,750 from 40 of the 69 submissions. Might have accidentally left out all of the patented 649 00:52:45,750 --> 00:52:50,800 submissions, well, the SUPERCOP policy is anybody who sends us code to put in, we'll 650 00:52:50,800 --> 00:52:54,730 benchmark it, it doesn't have to be unpatented, it doesn't have to be secure, 651 00:52:54,730 --> 00:53:00,349 we benchmark MD5, we benchmark RSA-512. But anyways, there's 40 submissions where 652 00:53:00,349 --> 00:53:04,510 code is in there, from other people or from me painfully going through getting 653 00:53:04,510 --> 00:53:10,829 code to actually work. The primitives are, for instance, RSA-512, and RSA-1024, and 654 00:53:10,829 --> 00:53:14,799 RSA-2048. They're all RSA, but they're different primitives, or different 655 00:53:14,799 --> 00:53:19,460 mathematical functions with different security levels and, well, in these 656 00:53:19,460 --> 00:53:23,049 submissions, there's typically three different security levels, sometimes more 657 00:53:23,049 --> 00:53:26,820 choices, sometimes less and then a lot of the primitives have multiple 658 00:53:26,820 --> 00:53:31,170 implementations, like reference code and optimized code for different platforms 659 00:53:31,170 --> 00:53:35,150 maybe. So, okay, a lot of those are collected in this benchmarking framework, 660 00:53:35,150 --> 00:53:39,940 all with the same API. libpqcrypto, I think I might have a few minutes to say a 661 00:53:39,940 --> 00:53:44,780 little more about this, libpqcrypto is focusing on having an API which is 662 00:53:44,780 --> 00:53:49,740 suitable for cryptographic deployment in the future. If you imagine that the 663 00:53:49,740 --> 00:53:54,579 implementation quality of the underlying crypto is dramatically improved, at least 664 00:53:54,579 --> 00:53:59,356 that interface layer is supposed to be something that you'll be able to use. Some 665 00:53:59,356 --> 00:54:04,220 more examples of things out there, pqm4 is a library optimized for small ARM 666 00:54:04,220 --> 00:54:11,029 microcontrollers, the ARM Cortex-M4, or pqhw is for FPGAs, and this last one,Open 667 00:54:11,029 --> 00:54:16,680 Quantum Safe, that one, they don't have as many primitives maybe as libpqcrypto or 668 00:54:16,680 --> 00:54:19,980 SUPERCOP, but what's cool about that project is, they've got working 669 00:54:19,980 --> 00:54:26,250 integrations of all of these into OpenSSL and OpenSSH. So if you're in, say the TLS 670 00:54:26,250 --> 00:54:31,150 world, then that's clearly the way to use these post-quantum proposals, at least 671 00:54:31,150 --> 00:54:38,180 quite a few of them, inside TLS. Okay, let me look a little bit at libpqcrypto and 672 00:54:38,180 --> 00:54:43,480 then we'll finish this off. There's lots of cryptographic libraries which give you 673 00:54:43,480 --> 00:54:48,869 a nice, simple API for hash. They'll have some simple function like sha256, which 674 00:54:48,869 --> 00:54:53,499 takes a message, okay, in C you have to say there's a pointer to the beginning of 675 00:54:53,499 --> 00:54:58,440 the message plus the length of the message, and then gives you back some hash 676 00:54:58,440 --> 00:55:03,099 of some 256 bit, 32 byte hash. In a higher level language, of course, you say 677 00:55:03,099 --> 00:55:09,020 something like "h = sha256(m)", and m knows what its length is, but in C it 678 00:55:09,020 --> 00:55:14,460 looks like you have h and m and the length of m as arguments. Why not do this for all 679 00:55:14,460 --> 00:55:18,339 cryptographic functions? Somehow, it's really weird, lots of cryptographic 680 00:55:18,339 --> 00:55:22,030 libraries just have a nice, simple interface for hashing, and then if you 681 00:55:22,030 --> 00:55:25,710 want to do something like public key signatures, it's, well, okay, first we're 682 00:55:25,710 --> 00:55:30,599 going to find the factory, which is producing the keys, while the generator 683 00:55:30,599 --> 00:55:35,349 method for the key, blah blah blah, and well, you can just say, and what 684 00:55:35,349 --> 00:55:40,329 libpqcrypto does is, it simply says, you sign something, with whichever signature 685 00:55:40,329 --> 00:55:44,609 scheme, you have to tell it, well, I'm going to put the signed message somewhere, 686 00:55:44,609 --> 00:55:48,289 and then the length of the message is an output, the message you're signing and the 687 00:55:48,289 --> 00:55:51,960 length are inputs, and your secret key is an input. And then it just takes 688 00:55:51,960 --> 00:55:56,009 everything in wire format, produces everything in wire format. You don't have 689 00:55:56,009 --> 00:56:00,269 to have conversion functions, input/output serializations etc. This is actually an 690 00:56:00,269 --> 00:56:04,950 API that goes back to, we've been doing SUPERCOP for many years, and SUPERCOP, the 691 00:56:04,950 --> 00:56:10,944 salt (NaCl) library, libsodium etc. are all using the same API. And this is 692 00:56:10,944 --> 00:56:16,630 something which, actually people have measured the impact on usability of 693 00:56:16,630 --> 00:56:20,809 cryptographic libraries depending on the different API provided by these libraries, 694 00:56:20,809 --> 00:56:24,430 and so we're pretty confident about benefits of having a nice, simple way to 695 00:56:24,430 --> 00:56:30,520 use crypto. NIST looked at this and said, well, ok, yeah. People should submit 696 00:56:30,520 --> 00:56:37,160 something to the post-quantum competition using this API, but they didn't have test 697 00:56:37,160 --> 00:56:42,070 code that people could use to make sure that they were following the 698 00:56:42,070 --> 00:56:46,359 rules. They didn't require that everybody pass any particular set of tests and they 699 00:56:46,359 --> 00:56:52,730 accepted submissions which didn't work, for example, in SUPERCOP. So, well, ok, 700 00:56:52,730 --> 00:56:55,819 that's why I had to do a bunch of work to integrate a bunch of submissions into, 701 00:56:55,819 --> 00:57:00,970 into SUPERCOP. But it's been sufficiently close to everybody using this that there 702 00:57:00,970 --> 00:57:05,069 has been a lot of code shared between these different projects, Open Quantum 703 00:57:05,069 --> 00:57:09,710 Safe is also starting from the same API and then providing higher level 704 00:57:09,710 --> 00:57:14,779 integrations into OpenSSL and OpenSSH. OK. There's a bunch of different signature 705 00:57:14,779 --> 00:57:19,279 systems and a bunch of different encryption systems in libpqcrypto. Here's 706 00:57:19,279 --> 00:57:23,450 an example of what the higher level API looks like in Python. If you want to use 707 00:57:23,450 --> 00:57:28,029 libpqcrypto and sign a message, well first somebody has to generate a public 708 00:57:28,029 --> 00:57:32,599 key and a secret key using the pqcrypto library. Signature system, here's one of 709 00:57:32,599 --> 00:57:37,630 the signature systems; Sphincs is a stateless hash-based signature system, you 710 00:57:37,630 --> 00:57:42,829 don't have to record anything when you sign message, and then 128 is security 711 00:57:42,829 --> 00:57:47,180 level 2 to the 128, using the SHA-256 hash, and well, you just have to know this 712 00:57:47,180 --> 00:57:52,039 name and then you say, give me a key pair, sign a message using a secret key, open a 713 00:57:52,039 --> 00:57:57,130 message using a public key. Now this is not "you get a signature and then you do 714 00:57:57,130 --> 00:58:02,539 verify of a message and a signature". This is another little API detail, designed to 715 00:58:02,539 --> 00:58:06,435 protect people against screwing up. There's lots of applications which verify 716 00:58:06,435 --> 00:58:11,280 signatures, and then if the verification fails, nobody's ever tested it, and the 717 00:58:11,280 --> 00:58:16,989 verification failure is ignored. What actually works to protect application 718 00:58:16,989 --> 00:58:21,960 programmers is have an interface where you have a signed message as one bundle, it 719 00:58:21,960 --> 00:58:27,070 goes into the opening a signature, opening a signed message and producing a message, 720 00:58:27,070 --> 00:58:31,589 and the cryptographic library does not produce a message as output if the 721 00:58:31,589 --> 00:58:36,510 signature was invalid. So the signed message is produced, is handled by the 722 00:58:36,510 --> 00:58:41,780 cryptographic library producing a message if the signature is valid. Also there's an 723 00:58:41,780 --> 00:58:45,670 exception being raised, but even if you ignore the exception in Python or if 724 00:58:45,670 --> 00:58:49,509 you're using a lower level language without exceptions, then you just aren't 725 00:58:49,509 --> 00:58:55,099 given back a message. This is what lots of little thought that goes into the API. 726 00:58:55,099 --> 00:58:59,599 Maybe a bigger example in Python; this is a whole thing of using the library, 727 00:58:59,599 --> 00:59:05,170 generating a key, signing some random message and opening the message. OK. What's 728 00:59:05,170 --> 00:59:11,280 going to happen in libpqcrypto coming up is, first of all, one of the big problems 729 00:59:11,280 --> 00:59:16,500 with code quality is there's lots of exposure to timing attacks. I saw a great 730 00:59:16,500 --> 00:59:20,670 talk earlier today about Spectre, and there's lots and lots of these attacks, 731 00:59:20,670 --> 00:59:24,701 and part of fixing these attacks is fixing software, along with we're going to have 732 00:59:24,701 --> 00:59:29,529 to do lots of hardware fixes. There's been some work on some implementations to fix 733 00:59:29,529 --> 00:59:35,270 this, but much more is required. Need a lot more work on correctness. Lots and 734 00:59:35,270 --> 00:59:40,119 lots of the code doesn't even pass address sanitizer. And this was, I don't want to 735 00:59:40,119 --> 00:59:44,970 tell you how much pain to get code working and address sanitizer, where, I mean 736 00:59:44,970 --> 00:59:49,499 anybody writing code professionally is going to be using these automatic tests as 737 00:59:49,499 --> 00:59:52,819 they're writing the code, and this is something that just doesn't happen when 738 00:59:52,819 --> 00:59:58,280 you ask a bunch of mathematicians to write code. Formal verification. We'll do much 739 00:59:58,280 --> 01:00:02,789 more than testing and do much more than, say, address sanitizer does and much more 740 01:00:02,789 --> 01:00:07,430 than even an expert auditor will do. That formal verification is going to guarantee 741 01:00:07,430 --> 01:00:11,829 that your code is doing what it's supposed to for every possible input, which I used 742 01:00:11,829 --> 01:00:16,194 to be very skeptical about because it seemed so painful to do for any realistic 743 01:00:16,194 --> 01:00:20,150 code, but I've started getting much more enthusiastic about it, because the tools 744 01:00:20,150 --> 01:00:25,990 are getting much much better. And one example of something I did was a sorting 745 01:00:25,990 --> 01:00:30,420 verification, where some really fast sorting code is actually completely 746 01:00:30,420 --> 01:00:34,299 verified to work correctly, the machine code is verified, so you compile it, even 747 01:00:34,299 --> 01:00:38,470 if there's compiler bugs, then the machine code is what's verified, so the 748 01:00:38,470 --> 01:00:43,110 verification isn't going to rely on some compiler being correct. This is using the 749 01:00:43,110 --> 01:00:46,569 angr toolkit, also, I don't know if there's any Trail of Bits people here, 750 01:00:46,569 --> 01:00:52,209 Manticore I understand has similar features, I used angr, but, well. There's 751 01:00:52,209 --> 01:00:55,750 really cool tools out there for doing symbolic execution and as part of that 752 01:00:55,750 --> 01:01:00,960 formal verification. Speed is important and trying to get the code volume down, 753 01:01:00,960 --> 01:01:04,930 there's lots of duplication, we need more internal libraries to get post-quantum 754 01:01:04,930 --> 01:01:10,670 crypto on a smaller, easier to review code base. And finally, hopefully, at the end 755 01:01:10,670 --> 01:01:15,980 of all this we'll be able to throw away as many primitives as possible and focus on a 756 01:01:15,980 --> 01:01:20,180 small number of things, where we can say "We've really, seriously reviewed these. 757 01:01:20,180 --> 01:01:24,790 We've reviewed the designs, we've reviewed the implementations, and we're confident 758 01:01:24,790 --> 01:01:29,320 that these things are secure". That's it. Thank you for your attention. 759 01:01:29,320 --> 01:01:44,680 *applause* 760 01:01:44,680 --> 01:01:49,369 Herald: Thank you Tanja & Daniel. If you would like to leave at this point, please do 761 01:01:49,369 --> 01:01:54,779 that very quietly, we'll have a short run of Q&A. Signal angel, your first question. 762 01:01:54,779 --> 01:01:59,960 Microphone: [unintelligible] from older submission in code base, are there any 763 01:01:59,960 --> 01:02:06,310 other ones that use smaller keys? TL: Use smaller keys you said? 764 01:02:06,310 --> 01:02:08,420 Signal angel: Yeah. From all the submissions - 765 01:02:08,420 --> 01:02:10,769 TL: Yeah, so code-based cryptography, there's two submissions classic McEliece, 766 01:02:10,769 --> 01:02:14,229 which I highlighted because it's ours, and there's NTS-KEM [CHECK], which has these 767 01:02:14,229 --> 01:02:19,170 gigantic keys. Both of those are using goppa codes, which is what has received 768 01:02:19,170 --> 01:02:26,519 the most analysis so far, but at this gigantic list of - Yep. What Dan is 769 01:02:26,519 --> 01:02:32,450 showing here, several of those are actually code based. So, bigquake for 770 01:02:32,450 --> 01:02:36,700 instance, down there, is a code-based system, then - 771 01:02:36,700 --> 01:02:39,859 DJB: Lake, that's, that's - TL: Bike is one, lake is one, down there, 772 01:02:39,859 --> 01:02:45,720 so lake would be fitting this by saying it's very small keys and signatures and 773 01:02:45,720 --> 01:02:53,089 ciphertext. The downside is, it is using far less well-studied codes. So we need to 774 01:02:53,089 --> 01:02:57,650 see how that develops. Herald: Thank you. For people in the room, 775 01:02:57,650 --> 01:03:02,039 please try to limit your questions to a single sentence. Microphone number 3, your 776 01:03:02,039 --> 01:03:05,829 question. Microphone 3: OK. How exactly do you 777 01:03:05,829 --> 01:03:11,059 define post-quantum crypto? I mean, you have Shor's algorithm, you have the other 778 01:03:11,059 --> 01:03:17,339 algorithms, but do you say, OK, it's just secure against factoring, discrete 779 01:03:17,339 --> 01:03:22,309 logarithms, or do you also take into account optimization problems and stuff 780 01:03:22,309 --> 01:03:26,470 like that? DJB: Yeah. So, I mean the definition 781 01:03:26,470 --> 01:03:31,349 is, we're trying to protect against any attacker who has a big quantum computer 782 01:03:31,349 --> 01:03:36,090 and we have a rough understanding of what quantum computers can do, because they're 783 01:03:36,090 --> 01:03:41,920 limited by the laws of quantum physics. Which tells us that, OK, if you can build 784 01:03:41,920 --> 01:03:46,450 a computer that supports what are called Toffoli gates and Hadamard gates, then you 785 01:03:46,450 --> 01:03:50,979 can, well, it's not completely proven, but it's very plausible that you can simulate 786 01:03:50,979 --> 01:03:52,789 the matrix at that point, a quantum matrix. 787 01:03:52,789 --> 01:03:54,640 Microphone 3: Yes, but that's the universal model. 788 01:03:54,640 --> 01:03:58,450 DJB: Yes, you have a universal quantum computer at that point. The problem is, 789 01:03:58,450 --> 01:04:03,130 how do we know, even if we say, well OK, by believing that quantum physics is 790 01:04:03,459 --> 01:04:08,089 everything we can do in the universe, that tells us we have a computation build out 791 01:04:08,089 --> 01:04:12,210 of Hadamards and Toffolis. That doesn't tell you what kinds of algorithms you can 792 01:04:12,210 --> 01:04:16,249 put together. And there's this big problem that's always been a problem for 793 01:04:16,249 --> 01:04:20,619 cryptography, is trying to imagine what all possible algorithms are, and sometimes 794 01:04:20,619 --> 01:04:24,569 people miss something. And so if somebody ever tells you, "oh, the system is 795 01:04:24,569 --> 01:04:28,099 provably secure, there's, there can't possibly be an algorithm which is faster 796 01:04:28,099 --> 01:04:32,381 than this to break the system", no there's no guarantees, and lots of people have 797 01:04:32,381 --> 01:04:36,569 been overconfident and burned, because there is actually a faster algorithm. 798 01:04:36,569 --> 01:04:39,940 We've had a lot of work on people trying to figure out good algorithms using 799 01:04:39,940 --> 01:04:44,249 quantum computers, for instance for the sub-exponential attacks that Tanja was 800 01:04:44,249 --> 01:04:48,839 mentioning against CSIDH, and that's something where, there's a long history to 801 01:04:48,839 --> 01:04:52,569 those attacks, starting with Cooperberg's algorithm, and this is going beyond Shor's 802 01:04:52,569 --> 01:04:56,710 algorithm and Grover's algorithm. And it's really important to look more at what sort 803 01:04:56,710 --> 01:05:00,440 of quantum algorithms could attack cryptographic systems. There's been some 804 01:05:00,440 --> 01:05:02,279 initial work, but there definitely needs to be more. 805 01:05:02,279 --> 01:05:06,749 TL: I mean, our attacker is allowed to do whatever they want. That's why I'm showing 806 01:05:06,749 --> 01:05:10,220 this as attacker. The attacker is not playing by the rules. The only thing we 807 01:05:10,220 --> 01:05:12,119 know is our attacker has a quantum computer. 808 01:05:12,119 --> 01:05:15,869 Microphone 3: Okay. Herald: Right, signal angel, your next 809 01:05:15,869 --> 01:05:18,769 question. Signal angel: Question from the Internet. 810 01:05:18,769 --> 01:05:22,660 Size does matter, but what about the performance of post-quantum cryptography 811 01:05:22,660 --> 01:05:28,220 compared to classical algorithms for embedded or FPGA devices, for example of 812 01:05:28,220 --> 01:05:32,549 firmware signing or communication and encryption? 813 01:05:32,549 --> 01:05:41,220 TL: OK. So on the big list, and quickly firing up. pqm4, that's using a Cortex ARM 814 01:05:41,220 --> 01:05:45,720 M4, so that's a rather small device. They did not implement all algorithms and for 815 01:05:45,720 --> 01:05:50,880 some of them they said, it is very cumbersome to do with the big keys. So 816 01:05:50,880 --> 01:05:54,970 yes, it's more of an issue. I mean, we're spoiled with elliptic curves, just having 817 01:05:54,970 --> 01:06:00,390 256 bits there, and all the systems are larger than that. CSIDH is the closest you 818 01:06:00,390 --> 01:06:05,450 get, but then it has the big computation. But there is effort, and these smaller and 819 01:06:05,450 --> 01:06:10,450 more fitting systems have been implemented. Hopefully we'll get better. 820 01:06:10,450 --> 01:06:14,809 Herald: Thanks. Microphone number 4, your question. 821 01:06:14,809 --> 01:06:20,720 Microphone 4: You said, when Google did some tests, that said it's just too slow, 822 01:06:20,720 --> 01:06:26,789 they cannot really use it. Would the solution be acceleration units, like used 823 01:06:26,789 --> 01:06:32,099 for AES in CPUs? TL: So, Google was excluding the use of 824 01:06:32,099 --> 01:06:35,769 the supersingular isogenies based on speed. I assume that's what you mean, 825 01:06:35,769 --> 01:06:42,260 rather than the big ones with bandwidth. I don't know all the details of it. My 826 01:06:42,260 --> 01:06:46,349 assumption is, it was factoring in also the security, like how much time have 827 01:06:46,349 --> 01:06:50,079 people spent on analyzing it, which made them more comfortable with the structured 828 01:06:50,079 --> 01:06:55,609 lattices than the supersingular isogenies. You can speed things up if you have a big 829 01:06:55,609 --> 01:07:00,869 engine, which would be manufactured to do finite field arithmetic, but that is much, 830 01:07:00,869 --> 01:07:07,200 much bigger than, say, an AES engine. DJB: Maybe just an extra comment. I think 831 01:07:07,200 --> 01:07:11,529 that the choice they made of NTRU-HRSS is really an excellent choice of, it's 832 01:07:11,529 --> 01:07:16,650 something which is small enough to fit into most applications, I mean 1,000 bytes 833 01:07:16,650 --> 01:07:20,569 or so, it's much bigger than elliptic curve crypto, but compared to all the data 834 01:07:20,569 --> 01:07:24,859 we tend to send around, it usually fits, unless you got, like, some really small 835 01:07:24,859 --> 01:07:30,900 communication happening, then you usually can fit a kilobyte or so, which is the 836 01:07:30,900 --> 01:07:37,019 NTRU-HRSS sizes. And it's something which, it's got some history of study. I would be 837 01:07:37,019 --> 01:07:41,240 the last person to say that lattices are definitely secure, and we actually, our 838 01:07:41,240 --> 01:07:46,481 NTRU Prime submission is worried about ways that something like NTRU-HRSS could 839 01:07:46,481 --> 01:07:52,059 maybe be broken, but there's no evidence of any problems, and NTRU has held up for 840 01:07:52,059 --> 01:07:57,910 about 20 years of study without being broken. So, it's also reasonably fast, so 841 01:07:57,910 --> 01:08:01,950 it's a reasonable compromise between the different constraints of trying to have 842 01:08:01,950 --> 01:08:07,339 something secure and not ridiculously big, and, well, if it gets broken, then 843 01:08:07,339 --> 01:08:13,570 we're in trouble. But hopefully it's okay. Herald: Thanks. Signal angel. The final 844 01:08:13,570 --> 01:08:16,710 question please. Signal angel: The final question. Can 845 01:08:16,710 --> 01:08:21,460 CSIDH drawn on a hardware accelerator make for regular elliptic curves, or is it is 846 01:08:21,460 --> 01:08:24,219 the handling of isogenies more problematic? 847 01:08:24,219 --> 01:08:29,100 TL: All right, so depends what your hardware accelerator has. If it's like one 848 01:08:29,100 --> 01:08:33,200 of fairly generic elliptic curve arithmetics, you can probably use it. 849 01:08:33,200 --> 01:08:37,770 We're getting some speed from not using elliptic curves in Weierstrass form, but 850 01:08:37,770 --> 01:08:42,250 Montgomery forms, so you probably would want to modify the accelerator they're 851 01:08:42,250 --> 01:08:47,830 currently using to fit this better. Also, most systems are optimized for 256 bit 852 01:08:47,830 --> 01:08:53,150 elliptic curves or 384, with 512 bits we're a little bit outside, but most of 853 01:08:53,150 --> 01:08:58,130 the operations would be looking just the same. The most time we spend on doing a 854 01:08:58,130 --> 01:09:04,139 big scalar multiplication, and then we have some operations in these isogenies, 855 01:09:04,139 --> 01:09:09,029 but they are fairly similar. If you have, like, the field arithmetic built up, you 856 01:09:09,029 --> 01:09:15,510 can just put these together and have an isogeny computation as well. So yes, it 857 01:09:15,510 --> 01:09:18,750 can get faster. As I said, this is from January, we're still working on the 858 01:09:18,750 --> 01:09:23,850 security analysis, so don't build any hardware, at this moment, quite yet. 859 01:09:23,850 --> 01:09:26,940 *laughter* Herald: Thank you so much. Please give 860 01:09:26,940 --> 01:09:29,868 them a huge round of applause for the talk. 861 01:09:29,868 --> 01:09:38,069 *applause* 862 01:09:38,069 --> 01:09:39,719 *postroll music* 863 01:09:39,719 --> 01:10:01,000 subtitles created by c3subtitles.de in the year 2020. Join, and help us!