Root Causes 05: Cryptographic Quantum Apocalypse

Hosted by

Fellow

Original broadcast date

February 7, 2019

As quantum computing continues to progress, the world's widespread cryptographic schemes are in danger. To prepare for the cryptographic "Quantum Apocalypse" we will need to replace our RSA- and ECC-based schemes with a new set of ciphers.

Podcast transcript

Lightly edited for flow and brevity.

TCTim CallanWe’ve got an interesting one today that’s quite cutting edge: quantum computing and cryptography and, for want of a better word, what people describe as the Quantum Apocalypse.

Jason SorokoLet’s back up just a second to talk about what encryption is and how it works at its fundamentals. I'm going to assume that a lot of members of the audience probably know a lot of this. So I'm not going to go too much into depth, but to put it extremely simply, encryption works because the physical manifestation of encryption and encrypting is easy and the code breaking is very, very hard. For a little bit of input of making a mathematical calculation, you can make it tremendously difficult for a traditional computer to actually break that - to decipher what was a very small investment in terms of computing, relatively

TCTim CallanTherefore, if you have anything that’s remotely approaching parity in the computing power on both ends of the equation then it’s badly tilted in favor of the encryptor, and therefore the whole system works.

Jason SorokoThankfully, because of the way traditional computers work, doing things like factoring prime numbers is tremendously difficult because the computer has no choice but to go through every combination. That’s the basis of RSA encryption as an example. Elliptic Curve Cryptography works because of the properties of an elliptic curve, and solving for two points in that curve is actually very difficult for a traditional computer.

I think, Tim, where we’re going with this is that a lot of people have been talking about about quantum computing and the super position of quantum computing. Unlike traditional computers with traditional bits of zero or one, a qubit (or a quantum bit) can be zero or one but can also represent some super position of that and, interestingly enough, can even become entangled and can even interfere with one another. So qubits have very interesting properties. For our purposes today in this conversation it’s about what happens when not only encryption is easy but the code breaking of traditional encryption algorithms is also easy.

TCTim CallanWhen we say this phrase Quantum Apocalypse it’s kind of a big phrase, but the idea is that as quantum computing reaches a certain level of practicality that all of the sudden the decryption capabilities are vastly improved and therefore that parity we were talking about before is no longer sufficient. That the disparity in the amount of processing power required to run the two halves of this lifecycle is no longer so extreme, and that may make it possible for bad guys to start to decrypt our encrypted data in a shorter timeframe than it’s possible to upgrade our complex ecosystem to deal with this fact.

Jason SorokoExactly right. The reason we’re having this conversation now is, I think it’s Michele Mosca who talked about this very simple equation of, if x plus y is greater than z then you need to worry. So what is x? Well x is how long do you need your crypto keys to be secure.

In other words, what’s the security shelf life? Is x. y is how long will it take to retool, or what’s your migration time? And z is what this podcast is about today. z is how long will it take for large scale quantum computing to be built. In other words, that is the collapse time. That is the apocalypse and I think one of the challenging things for people is to really define what z really is.

TCTim CallanWould it be fair to say that while there’s a lot of very smart people giving a lot of thought to this, ultimately the answer to that question must today be somewhat speculative?

Jason SorokoIt is speculative, Tim. Absolutely there’s a lot of speculation but speculation by incredibly precise people, and you know a mathematician’s version of speculation may not be the same as your friend when you’re throwing some dice around.

TCTim CallanFair enough. So, do we have visibility on what z is?

Jason SorokoI think we do. We’ll get there, and we’re going to double click on a lot of these topics in future podcasts. Let’s talk about Shor’s algorithm for a moment.

TCTim CallanTell us about Shor’s algorithm.

Jason SorokoHow do you factor primes? Very, very efficiently with a quantum computer. If you happen to have a quantum computer, what would be the most efficient algorithm with which to factor primes? Peter Shor, back in 1994/95 came up with Shor’s algorithm. I think to this point it’s still the state of the art. Given an integer, find its primes. And it uses more or less a geometric method of finding those primes. Finding periodicities within a function and therefore, because of the fact that primes tend to follow a pattern or a sequence, what is the most effective way of finding that pattern or sequence with a quantum computer? We can go into that in a future podcast but suffice to say Shor’s algorithm is what you would use to break the RSA encryption technique, as an example, if you had a quantum computer.

So how do you make yourself more resistant to that algorithm? Well you could just take RSA and instead of having RSA 2048-bit encryption you could knock up that bit. Knock that number of bits up incredibly high. The problem is you now have a very difficult to deal with bit of cryptographic material.

TCTim CallanIt's very heavy.

Jason SorokoThese are some numbers that are mostly agreed upon. It currently takes about 5,000 to 10,000 qubits to solve RSA 2048 in, let’s call it, a reasonable amount of time. We’re currently looking at quantum computers that are running about 512 qubits. Really smart people, guys like Michele Mosca, where I'm getting a lot of my information from, the researcher at the University of Waterloo, is basically saying the rate at which quantum computing will continue to accelerate from the standpoint of when we’ll get from 512 qubits to 1,000 qubits to 5,000 qubits to 10,000 qubits.

Because that’s the point at which we’re going to have this Quantum Apocalypse. That’s following a fairly stable rate. It’s not quite like Moore’s Law in which it’s very exponential. It is following more or less, let’s call it a...

TCTim CallanA linear progression, shall we say?

Jason SorokoIt’s more like a linear progression. Let’s take a look at some numbers that I have seen. Back in April 2015, Michele Mosca said that there was a one in seven chance of breaking RSA 2048 by 2026 and a one-half chance by 2031.

We also have another quote. Simon Benjamin said at a conference in London back in September 2017, if someone is willing to go “Manhattan Project,” you could probably get to that date by about six to twelve years from now.

TCTim CallanSuggesting that it would need literally like the resources of a nation state in order to get it done.

Jason SorokoA nation state would be the type to bring it faster than what Michele Mosca was talking about in his one in seven chance by 2026.

TCTim CallanOk.

Jason SorokoBut now let’s talk about what that means. What does breaking RSA 2048 mean? It’s really important to understand because I think what people think it means is that you’re doing real time decryption of say an SSL encrypted stream of information. If you think about it, what does it affect the most? It does effect RSA and Elliptic Curve Cryptography. So that means basically TLS key arrangements with Diffie-Hellman. And it’s basically based on a retroactive concept. Meaning you had to have - - if you’re doing a man in the middle attack and you are reading an encrypted stream and you are recording it, what we mean by breaking, with the definition of breaking according to a lot of these researchers, is being able to retroactively decrypt it within a reasonable amount of time.

And reasonable can sometimes mean a month or two. Instead of it being 100 years, it is within our lifetime and definitely within a year or two. Here’s an interesting thing that a lot of people also don’t realize: It doesn’t affect all cryptography the same way. Hash methods such as AES or Triple DES or SHA, the current most modern version of SHA. These are quantum resistant just by their definition in that they’re not susceptible to Shor’s algorithm, but quantum computing might render the need for hashing algorithms to need larger bits. So that’s another interesting piece that I think a lot of people might be missing in this story.

TCTim CallanSo hash algorithms like SHA are less worrisome you would say than, let’s say, RSA encryption?

Jason SorokoI think we should be looking at everything. If you take a look at what we’ve had to solve in the past and what we’ve successfully solved in our recent past in this industry, Tim, we’ve already seen the deprecation of SHA-1 as a hash algorithm. And you know, obviously there’s a lot of key material sitting out there. You know, hashed with that algorithm still in use today and might not be able to be changed because of where it’s sitting. It just can’t be gotten to. Maybe it’s unconnected.

But I think the industry as a whole has already gone through a world where we’ve had to think about this. We’ve had to have a concept of cryptographic agility. So I think for hashing functions specifically we’ve already gone through the exercise of going, “Hey, we need to either change the algorithm or up our bits.”

But I think for RSA and for Elliptic Curve, these are ubiquitous and therefore it is obviously something that we really need to think hard about. And I think in future podcasts, Tim, what we will be talking about are if it’s not going to be RSA, traditional RSA and it’s not going to be Elliptic Curve, if we can’t do encryption by prime numbers anymore starting around 2026 as an example, then what are the new quantum resistant algorithms that are out there? What are their maturity levels? Therefore, once you answer that question, you can start to get a clearer picture of, what will the Quantum Apocalypse look like? Will it be like a Y2K situation where it just kind of blows over, or are we really in trouble? Those we’ll explore down the road.

TCTim Callan2026 is extremely close, right? If we still believe the assessment and we do think there’s a one in seven chance of everything being compromised or potentially compromised by 2026, seven years to swap out our entire complex infrastructure is a Herculean task. That is an all-hands-on-deck kind of situation.

Jason SorokoThat’s why we’re talking about it, right?

TCTim CallanYeah.

Jason SorokoWe can’t be ignoring this. Everybody who’s in the industry needs to be thinking about it. As a trusted third-party CA, you know we are being looked at as being the leaders for how are we going to deal with it. And therefore that’s why we’re going to have these podcasts. We’re going to be talking through this problem. And we invite listeners to add their comments, and we’ll see where this conversation journey takes us.

TCTim CallanThis is a complex topic. We can’t hope to cover it today. What we wanted to do today was frame the discussion, and we’re going to return to this on multiple occasions to try to get through what there is to discuss.

One little teaser: You talked about these quantum resistant algorithms. Is there a clear path forward? Or are there a set of clear paths forward that are good options algorithmically, or is this still an open question?

Jason SorokoWow, that’s a bit of a loaded question. However, I think maybe I'm safe to say, without being personally the mathematician whose working on it, there definitely are some very prime candidates. That term prime is kind of funny.

TCTim CallanGet it? Get it?

Jason SorokoThere definitely are some candidate algorithms that are out there that are based on really good math and by people who have an understanding. In other words, if people think the sky is falling, I think the problem we face is this, Tim. To answer your question a slightly different way, yes, the math is there. The algorithms are there. But let me ask you the question. How long did it take for Elliptic Curve to become and stable and trusted?

TCTim CallanOh yeah. Absolutely. And the only reason that we could even get our basic fundamentals of encryption in place when the World Wide Web blew up as fast as it did is because it was built on work that had been going on for the previous decade, so we were ready to take an existing trust system that already had been worked through and plug it into this new paradigm.

Jason SorokoA factoid, and somebody can correct me if I'm wrong on this, but this is my understanding: One of the reasons why elliptic curve is trusted, and never mind all the shenanigans that went on with the NIST curve parameters, that’s a whole other issue. For those of you who were in the industry, if you think about the solving of Fermat’s Last Theorem, which again is way beyond the scope of this podcast, one of the things that needed to be solved to solve Fermat’s Last Theorem was the proof that there is no basic unraveling of Elliptic Curve.

In other words, it’s sound as an encryption method. That’s one of the things that, to paraphrase it, needed to be solved in Fermat’s Last Theorem. Just as a factoid. In other words, the bedrock of truth and the bedrock of knowledge that the mathematical thinking and tradition that went on behind our current encryption methods is very, very solid.

TCTim CallanSo there certainly are good avenues that are paths forward, but at a bare minimum there would need to be a whole lot of engineering to take place, right?

Jason SorokoOh that’s a whole other issue. We can theorize that this math is really good in the CA industry. But we’re in the commercial end of this. What is going to be the engineering it takes to be able to issue a lattice-based certificate? And those are things we’re going to explore in future podcasts.

Stay informed with expert insights

Subscribe to Root Causes for engaging discussions on PKI, digital security, and best practices for protecting your organization's critical assets. Don’t miss an episode!