Post-Quantum Standards for the Future of the Internet

Hello. And I think we're live. Welcome, everyone. This is a plasma ball. It's not an internet thing completely, but for sure we're just welcoming here in our special segment Post Quantum, about the post-quantum internet. And with me, I have the real stars of our program today: Cloudflare researchers, Bas Westerbaan. I hope I said that well... Close enough. based in Amsterdam and Armando Faz Hernández, based in San Francisco, I'm João Tomé storyteller at your service, and I'm in Lisbon, Portugal and it's so hot here. So if there's some lagging in the image, it's my fault. So we have three time zones. And first, the news. Last week, it was a big week. The Internet continues to evolve. And this month, July 2022, some post-quantum cryptography algorithms were considered for standardization, were announced by the US National Institute of Standards and Technology. So let's start... Go ahead, Bas. Yes. It's been a very, very big week for cryptography and I think for the Internet as well, because we've been waiting for this day since 2016 and finally it's announced that cryptography is going to be standardized, the post- quantum cryptography that's going to be standardized and which will underpin the security and the privacy of our Internet in the coming years. - Decades... - For sure. I think it's interesting for people to understand first, What does it mean post-quantum internet in a sense? What are we discussing here? Yes. So there's this thing, a quantum computer. At the moment, they're still very small and very much research. They're like in the in the very early stages. You know those pictures where they have these old computers with these huge tubes which are weaker than your pocket calculator. That's the state of quantum computers now. They can't do a lot, but we know, just like back then, we knew where computers would go now. We do know where quantum computers will go now. And there's a big up side and a big down side. The big up side is that with quantum computers, you can simulate nature much better. So we will get better materials. Instead of having to try new metal amalgams, we can simulate them. And that will be great. There will be a lot of progress there. That's something to look forward to. But there's a minor inconvenience with quantum computers. You can break practically all cryptography that's deployed today. So that means all private messages, credit card numbers, everything that's sent today on the Internet, it can be recorded and later with someone who has a quantum computer can break it. And that's something we would like not to happen. So we want to change out the cryptography with something that's protected against a quantum computer, against attacks of quantum computers, and that's what what this big moment is, where finally NIST announced which of this post-quantum cryptography, secure against quantum computers, they will standardize. Yeah. For sure. So in this case it was the US. But it's the beginning of this chapter in terms of standards, right. Yeah. The US, NIST, they took the lead, but it was really a community effort. So there have been around 70 submissions from all around the world, researchers all around the world who submitted proposals for post-quantum cryptography in 2016 and then in all these years, also researchers from all around the world have been publicly debating each of these algorithms. It was quite intense at times, and it has been slowly whittled down to just a few finalists. And finally it was chosen. So so even though the NIST is... we're very happy for NIST, for leading this competition. But it's really been a public effort worldwide. And what amazes me as someone that doesn't understand a lot about this is that most people don't understand that their Internet, the Internet they know right now, could change completely in terms of safety with quantum computers getting around. And that's the reality, that is what we're discussing here. But I think most people aren't aware of how unsafe it could be if quantum computers evolve and we don't have this post-quantum cryptography standards in place. So I think that's important, something important to highlight there. But in terms of history and Armando, I know you have a lot of background there, Cloudflare has been working for a number of years in this post-quantum cryptography. So it's a topic close to heart, right? Yeah. So there are two things that we need to consider. First of all, if this is something that should happen now versus later, so so many people think that maybe we are we're going too fast on doing the migration to post quantum, but something that we are trying to achieve here at Cloudflare is take advantage of the of the points that we have spread about the Internet so we can made experimentation in order to help to the to the post-quantum algorithm choice to make a better decision. So this is why we started some experiments since like a few years ago with parameters with one trying to replace like one post-quantum algorithm in one of the most popular network security algorithms, which is TLS. So basically what we do there is, okay, let's replace the part that does the key change of the TLS protocol. And rather than using like a classical elliptic curve algorithm, let's try to make a pair with some other algorithms. And in that case, with one algorithm based on... And then we tried to measure what was the impact of that. And since then, so we noticed that one of the biggest impacts is on latency. So basically for the key change, you know, even having... we can have certain leeway on the size of the messages, but definitely latency is something that will affect the TLS connections. After that, yeah, we'll continue with other different experiments like try to replace BIN a little bit more, do something different with now authentication, not the second part of the TLS that is guaranteed in the protocol. And then we work with KEM TLS and in this case it's just how to remove or how to use like TLS protocol without signatures and using only KEMs, which is one of the parts that we are, that are being standardized. I'm curious in terms of also in terms of what this announcement means. There was other possibilities. Bas already explained that. There were a lot of people contributing to this. I think you, Bas, also contributed in some way to create this standard. How was that process of choosing? Do you think it was a good process in terms of the solution that was found for a standard, for a possible standard? Yeah. So there are two things that were chosen. I think Armando already alluded to it. So we have the the encryption, the key agreement part and we have the signatures, the authentication part. So NIST chose, for the encryption part, NIST chose Kyber and there were actually quite a lot of good options, Kyber, Saber, NTRU, NTRU Prime. - Perhaps I'm missing even a few. - A few, yeah. Yeah, these are all, they were all great options. So we had to look at the performance with the experiments three or four years ago with a very similar one. And the performance was quite good. So, if any of these were chosen, we would be happy. We made a guess. Because we couldn't experiment with all, we had to guess, It might be Kyber... And we got lucky there. So, Because we were preparing for that, right? Yeah. Yeah. So we're already trying to get experience implementing and working with certain algorithms and Kyber was one of them, so we got lucky there. But I mean, any of the other ones, they would have also been good choices. So that's on the encryption part and that's really great. And then on the other side, you have the signatures, authentication. That part is for the little padlock when you're going to... when you see it, whether it's really the website you're going to. There the situation was much more difficult because none of the post- quantum signature schemes that were proposed, none of them are ideal. They they are all bad in one way or another, none of them was really perfect. And the, so to sa,y the best of the worst were Dilithium and Falcon. So Falcon was smaller, is smaller, but still a bit big, but it's very difficult to implement securely and Dilithium is much easier to implement, but it's bigger. It's like two and a half kilobytes where elliptic curves are only 64 bytes... - When you say bigger, bigger there, it means what for... - Signatures. Signatures... So in terms of the size of the - signatures. - Yeah, so you need to transfer more data. And public keys too. Yeah. So you want efficiency there. So the bigger, the worse because you want efficiency. You don't want to spend a lot of data with that, right? Yeah. So, so, so we, we had some guesses there, but we also did experiments. We really did an experiment where we checked out... If it becomes this much bigger, these signatures, how does it affect actually performance? So we put dummy data into TLS connections and we checked how much does it influence the timing. And if it would go to Dilithium, if it would just have Dilithium, then it would add 17 kilobytes and that would probably add, would make the TLS connection probably twice as slow, the handshake. So, so that was quite bleak. So we started thinking about all kinds of different ways in preparation, how we could avoid this. We wrote a blog about it and said this is going to be a problem because NIST has said time and time again that they will only choose either Falcon or Dilithium. The reason is, is that they are very similar in security. They they are both so called structured lattices. And NIST would like to standardize different options that are based on different security assumptions, so that if structured lattices are broken, then at least there is an alternative. But to... so we got clever, we got that right but we thought they would just standardize Dilithium and SPHINCS, which is really nice... one also because of cost effective, but it's not practical for TLS because it's very much too big. But to our great surprise, NIST chose to standardize both Dilithium and Falcon against what they said earlier, and that was a very pleasant surprise. - Why? - Because it means that post-quantum TLS authentication will be much more practical because the sizes are much smaller. Oh, the sizes. The efficiency there. The efficiency there. Yeah. Yeah. Just to add some context here. So, but this experiment. We are not only worried about, like the size of WAN key in the TLS protocol, I mean, of course the certificate carrier is like, you know, like the public key and the signature of that, but like in a normal WAN regular connection, it's not only one certificate, it's a chain of certificates that links from WAN website up to the certificate that was provided by the CA and the certificates that are back to the CA. So it's it's more than than that. And then we have like things like OCSP's table. Could you please comment that a little bit more, Bas? You're more familiar with that. Yeah. So, OCSP's tables are not widely deployed. They're used to prove that the certificate is not revoked yet. It's not very common. But two things that are very common, which are included as well are signed certificate time stamps – SCTs, and these are used by certificate transparency. This is a part of TLS that a lot of, that is not very well known, but it's two extra signatures to prove that the certificate has been locked at independent lock servers. So in total, there are six, seven signatures and two public keys when you make a connection to a website. Yeah. So here, so if you go down a bit. So we talked about encryption that the performance there is great. So if you go down a bit further to the first graph. This one? No, that's a table. Further down. Yes, this one. It's a graph further down. Oh, sorry. Yes, here. So this is the experiment we did in, I think 2019 from if I recall correctly. Here we did a combination of a classical and a post-quantum key agreement. And there's actually three lines here. There's a there's a blue, an orange and a green line. The green line is a SIKE, which is one post-quantum algorithm. And the blue and orange line, the blue is the control, which is just classical, and the orange line is NTRU-HRSS, which is very similar to to Kyber. It's a bit bigger and slower, but as you can see, it's very hard to distinguish between the blue and orange line, which is fantastic because it means that performance will be very similar to what we're used to. I think if you can zoom in a little bit, on one of the graphs at least, so we can... Let me see if I can do that. I'm not being able to let me... do it this way. There you go. There you are. Yeah, so basically we're seeing like a statistical difference between different distributions and that means like different algorithm choices. And in different operating systems, like Android, Linux... And it's all about latency, right? So the, the way that the Internet goes into... it's given to a person. So it's faster or less faster. The latency is all about that, right? And our objective here is to be as close as the Internet is right now, right? Or even faster. Yes, exactly. Well, at the moment we are adding the post-quantum cryptography on top, so we're doing something extra. So at the moment, we won't be faster because we're doing more. But in the future, not within not within a few years, but in the future, we will have gained more trust in it. And then we will be able to go use only the post-quantum cryptography. And actually post-quantum cryptography is, it's a little bit bigger typically in keys and signatures and ciphertext, but it's actually much faster, much lighter on the CPU. So it, so when the day comes that we use just post-quantum cryptography, it will actually be a speed boost. Interesting. That's interesting. I'm curious also about, mostly here, the the timeline for this. Of course, this is one of the first steps. Many steps were already given. Of course, this is one in terms of standardization, for sure. But what is the timeline to be expected even in terms of quantum computers and post quantum Internet? What is the timeline in place? It's difficult to say, right? Yeah, there's a lot of parties involved and each go at their own pace. So NIST has picked now which ones they are going to standardize. And it will take another one, two years. I think 2024 is their goal to have actually the standard written, but we're very eager to to to already deploy post-quantum cryptography. So our aim is to have a great deal of our internal traffic secure, post-quantum secure, at the end of this year. And so that that that's one goal. Then, for the Internet at large, we can't do it alone. We also have to work with the with the browser vendors and the other clients to, to agree on, on, on the cryptography and then to enable it. But we... On the standards too, right? Yes. On the standards that everyone uses. Yes. But we're working hard at this. We're working at IETF to propose to propose the code points to actually go and deploy this. And in the coming weeks we might have a few exciting announcements on that, too. - But, can't say it. - Interesting. Sorry. Armando, go ahead. Another important aspect of this is that, as I mentioned before, like, when is the right time to do it? And one thing that we need to be aware is that maybe we don't have right now like a quantum computer, which is like powerful enough to break the current systems. But something that we need to take care is that about the encryption of connections. So whatever is encrypted right now with classic algorithms and then you save it and then just store it. And then you let pass some period of time, let's say, until the big enough quantum computer is ready. So you may be able to decrypt that. Is that a threat? Maybe, well, we need to consider it. So this risk assessment, saying that we need to take care, and then one of the proposals is it is better to be proactive and then try to prevent this type of things happen. Not right now, but in the future. Of course, there is some unknown there that I think is very interesting for someone that is trying to understand this. Quantum computers are already here. They're not that efficient right now. They are getting better. If they get really better in terms of put the encryption that is in place right now out of order, like say like that, things will be messy a lot. We don't know in terms of who will achieve that first, what company, what country. So the main thing here is it's much better to be prepared already for those possible computers that will break security as we know it now. Right? As soon as possible, in a sense. Yes. Exactly. So right now there is some like quantum computing, or at least to run also simulations that solve some kind of problems that are not the same type of problems that that need to be solved to solve cryptographic algorithms. So some some applications on chemistry or some modulation of of molecules. These types of problems are very different and some early quantum computers, they already solve that. But this is totally a different type of problems when it's more generic machine power that in order to break, let's say for example, RSA or integer factorization. And we also have already an optimized crypto library for Go, right? That that was something that was in place since 2019, right? Yeah. So something like... So going back to, to, to this timeline, so a few years ago, we noticed that we needed to experiment with quantum crypto and, but at that time there was like very few implementations of, or very few code available about, about quantum algorithms. And then we initiated this effort and this library that we've written in Go, which is called CIRCL. And we started trying to be as a resource for programmers and for ourselves in Cloudflare too, to be a resource to put some cryptographic algorithms like both pre and post quantum. Right now there are several post-quantum algorithms that people can start playing with. We have SIKE, we have two of the winners, well not the winner, but the finalists of the NIST announcement of last week, which is Kyber for KEMs and Frodo for KEMs too. And for digital signature, we have Dilithium. And this is great. So this, if anyone else is also trying to experiment with the tradeoffs that these new systems have, they have a library, which is already there, it's open sourced and you can play with it. Yeah. In a sense, the blog post we did that I was sharing before actually, has some links for people, for those who want to to use what we have already, right? Yeah. So what we're seeing on the screen is a blog post, Bas wrote it, like and this small section explained how to, for example, create a very simple Go program for signing a message with a hybrid scheme that uses both Dilithium and Ed25519 signatures. As you can see, the code is is super small. It's like ten or 15 lines of code and then it runs well, it is optimized and then we are happy if people use it in its projects or if they have suggestions to improve this code. One of the things that amazed me on this area and I think you think the same thing, is this reminds me and possibly others of the beginning of the Internet, the collaboration that it took to create the standards between people from different countries, different universities, different companies. Do you agree with that, with that collaboration important to create the standards? Yes, it's been a fantastic worldwide collaboration, even though sometimes there were emotions. I think, I think in the end, we have, I mean, compared to the first time that people started using other systems such as RSA, I mean, it was just used. There hasn't been a process of years before it, before people evaluated this. And that's that's been really great. It's, it's, it's, it's a great moment. Yeah. And I think this is also a good time for everyone to, to, to start thinking now, What is our roadmap? How are we going to be post-quantum, to be quantum secure or well deploy post- quantum cryptography? Because now it's exciting this this enthusiasm, but probably within I don't know how many years it will also be probably mandatory for certification. So better be ahead of the curve I suppose. And more importantly, you want to protect your customers' data. Exactly. Data, it's all about security and also privacy. The privacy element is also important there, of course. I'm curious also before we wrap up, there's some algorithms that have an influence here. One of them is the Shor's algorithm. Can you explain a little bit how that works? In 3 minutes? In 2 minutes. In 2 minutes? So Shor's algorithm is the algorithm that's used to break classical, to break classical cryptography on a quantum computer. The trick is, is that it uses a variation of the Fourier transform to measure repetitions in either the multiplication by a fixed number, which can be used to dissolve this gridlock, which in turn is used to find the order of an element, which is used to factor numbers. And I'm afraid if this doesn't make sense, it probably will take an hour for me to properly explain it. Armando, can you sum up? Yeah, there is a thing of, like, related dependencies and the core part is solved by the sshort algorithm that basically, as was mentioned, just detects some function that is periodic and then try to get this period. Yeah. So something that I want to wrap up for, for the, for the segment is that yeah, we were very surprised by the recent NIST announcement. - Definitely surprised! - Yeah, so... There is still room open for investigation on signatures. That means that this is not the end of the story. So we really still need to figure out what are the best algorithms for different protocols because one size doesn't fit all and then try to see how this can be deployed on TLS or on SSH or on VPNs, so there are different protocols for CAs, for example. So yeah, the different trade-offs that they have and the different use cases that that are in the network protocols is what's going to allow us to make a better informed choice. And also NIST opened and second call in order to receive more proposals for signature schemes. So we need to watch out about what what is, how it is going to happen and what is going to be the next steps for that. For sure. So it's a path that is still being made in a sense. But these are exciting times there. It's interesting stuff. Any any other things before we wrap up? Let me just mention, if you want to see more about this, check our blog for sure, and also research.cloudflare.com. And we're open to research visits. So let's wrap... anything that people should be aware of this before we wrap up? Yeah, follow our website. Follow the blog posts and then keep it posted. We will share the information as much as we can, we have. Thanks so much for the invitation, by the way. And thank you so much for your insights. I know a little bit more now that you explained to me. Thank you so much. Have a good day. Bye bye.