Root Causes 267: Can Quantum Computers Break RSA Today?

Hosted by

Tim Callan

Chief Compliance Officer

Jason Soroko

Fellow

Original broadcast date

January 9, 2023

Much has been made of Schor's algorithm and the inevitable defeat of RSA using quantum computers. But a new research paper suggests a quantum computer may be applied to the problem in a fundamentally different way, hastening RSA's demise beyond even our current expected timelines. In this episode we discuss this new research, reactions to it, and its potential implications.

Podcast Transcript

Lightly edited for flow and brevity.

Tim CallanWe have another piece of news in the whole quantum computer/Quantum Apocalypse story. This isn’t actually a post quantum computing story; this is a pre-quantum computing story if you will. We are operating off a Schneier Security article. So, Bruce Schneier, as he frequently does, is right near the forefront of reporting securing developments, and in this case, the article is called “Breaking RSA with a Quantum Computer.” And the gist of this is that Schneier reports a Chinese paper—and we’ve looked at the paper as well—where a group of Chinese researchers have claimed that they can build on existing work that’s been done and demonstrate that a quantum computer within the parameters of what can be made today could be used to break RSA. That’s kind of the capsule summary.

Jason SorokoYeah. That’s correct. It’s interesting in the article the way that it’s written that you really do get the sense that the current paper that’s been published was the result of, you know, some sharp people catching other people’s work, identifying some of the mistakes made and then basically throwing in theoretically what could a quantum computer that exists even today, with enough stable qubits, could it pull it off? And, there’s questions then still to be asked with this. So it’s an interesting state of things. I’m not terribly shocked by it at this point in time.

Tim CallanLet’s maybe give a little more detail on this. You and I covered something quite a while ago, like a year ago, we did a podcast about a paper that had been leaked, looked like a draft that had been leaked, from European academic called Claus Peter Schnorr. And let’s clarify that Claus Peter Schnorr is a different person from Peter Shor. The names sound similar so people can get them confused, by let’s clarify the difference between those two names because that’s obviously very important.

Claus Peter Schnorr had put out this paper that stated that he walked through a process at the end of which the draft made the contention that it would break RSA. People looked at it and poked at it a little, and I think the community subsequently decided that this was not sufficient work to break RSA even though it was illuminating and valuable, and the final version of this paper actually backed off on that claim, so it looked like Claus Peter Schnorr probably came to the same conclusion on this own.

However, this group of researchers essentially contends that by following the same process but using a quantum computer that it is possible to build on what Schnorr said in order and that you could break RSA with a quantum computer that has 372 qubits. Now this is meaningful because there is at least one quantum computer today with more qubits than that and perhaps others, and if not, there certainly are others on the way. So, these researchers are making the argument that in theory RSA could be broken, a 2048-bit RSA could be broken using existing quantum technology that humans have today.

Jason SorokoThat is right. And so, we are kind of in a waiting game. Right? So the paper is proposing something that’s theoretical. And if somebody has done the math and this proposal saying with even the lowest level of stable qubits that do exist at the moment today, hey, let’s try it out. It’s almost like a call to arms. Let’s at least try it out. So we are in a bit of a waiting game and it’s IBM right now who has a stable quantum computer of that level of capability.

Tim CallanRight. The Osprey computer.

Jason SorokoThat’s right. All eyes on IBM now to see whether or not they pick up the gauntlet and go with it and let’s see what happens.

Tim CallanYeah and in the spirit of throwing down the gauntlet, one of the things these researchers did was they actually did repeatedly factor 48-bit numbers using a 10-qubit quantum computer that they had available just as a proof of concept to demonstrate that their fundamental methodology was correct but, obviously, they didn’t have the necessary computer available to run a proper 2048-bit RSA attack. And so, I think definitely this could be seen as a challenge to somebody else to try that and see what happens, but this is meaningful. Like, among other things, if this comes together – and this is a story I’m certain you and I are gonna watch. If this comes together, it pulls forward the Zed date—to go to a term that nobody is really using anymore—a long way from what people have been saying even very recently.

Jason SorokoYeah, Tim. We’ve said a few things in the past that they’re not unique ideas to us but it’s worth repeating, and some of those ideas are, hey, Schor’s algorithm, which is the most talked about algorithm for plugging into a quantum computer in order to reduce time for integer factorization, as an example.

That gets all the headlines and gets all the talk but keep in mind that there are other ideas out there. They just don’t get the airtime and I think this particular idea is getting some air time now, and it shows you something that you and I talked about before, Tim, but Eureka moments might not even just come out of what has been a very linear, stable linear pattern of development within stable quantum computing. Meaning quantum computers are growing at a linear rate and therefore we can kind of figure out that in ten years or a bit less we are probably gonna enter the state where at least Shor’s algorithm will probably be able to render ECC and RSA something we might have deprecate.

Tim CallanInteresting you brought up ECC because this is very focused on RSA. I don’t know if this is equally applicable to ECC but I believe the answer is no. Is that correct?

Jason SorokoThat is what they are saying. It would take somebody who is gonna read through the dense math of the paper to really answer that question, but this is the second thing that we’ve said. It’s not only the Eureka moments of stable quantum computing, it’s also the Eureka moments of better math. In other words, something other than Schor’s algorithm but, again, the thing about RSA is integer factorization – the speeding up a factor, factorizing integers is something that makes RSA just that much more vulnerable and this is something we have mentioned. I was always a little more worried about RSA because there was an extreme richness of studies going on attacking RSA which, you know, always has been sound for so long. Especially with the 2048-bit. Whenever we do have to deprecate it, we are gonna have to give it a tip of the hat.

Tim CallanOh, Lord.

Jason SorokoIt’s not that it was a weak algorithm. It’s incredible.

Tim CallanWhat other piece of technology are we using from the 1970s that is considered to be solid and robust? I guess the basic ones are your chip architecture and just so little else. It’s been such a champion and it allowed us to build a whole global digital economy with communications networks and financial transactions and retail and just so many things, all of which just simply wouldn’t have been possible without RSA. It’s gonna go down in the annals of technology history as one of the great developments for sure. However, nonetheless, it does kind of feel like we are running out of runway on that one doesn’t it?

Jason SorokoIt does. Maybe the extremely oversimplified version of that – and I like doing this but risking making errors in what I’m saying just to make it understandable for everybody.

You know, solving for really large prime numbers, right, integer factorization is a heck of a lot – it’s not easy – but it’s a heck of a lot easier than for solving for those bloody points on an elliptic curve. That’s just unbelievably hard. Again, it’s factorization. It’s something that quantum computers will unravel one day, presumably, but that’s why you have RSA 2048 vs. ECC 256 as an example. The bit lengths are just so much smaller because of the fact that it’s not necessary to have such a large bit length in ECC. It’s just a much harder thing to solve. And some of the algorithms that are coming out that are not necessarily Schor’s algorithm, I’m not surprised that they are specifically targeting RSA and, in fact, Tim, we might have a podcast down the road where we can highlight maybe the top five or six RSA attacks that are out there in the world because they are actually mathematically quite interesting.

Tim CallanThat’s good. I like that.

So, let me ask you this then. Like, hypothetically, let’s suppose that this whole thing has some legs and some smart people go and poke at it and they realize that, holy smokes, we can do this. Let’s suppose that IBM comes back and says, yep, did it. Here’s the demonstration. At that point, do we all switch out all of our crypto to ECC? Like, is that the next step

Jason SorokoIt might be. But I will tell you this. There’s a couple things that come to mind. One of the first questions that I would ask, that maybe you would ask, Tim, and some others would ask is what are we talking about here? Does it take a current quantum computer like from IBM - - will IBM come back to us and say, you know, we were able to unravel or decrypt a certain small block of ciphertext and it took us six months to a year to do it. Or it’s gonna take us - - we know we are cracking it but we know it’s gonna take us 11 years. Rather than a million years.

Tim CallanI think that’s a huge difference. Right? And that’s something to understand. If they say, look, we know we are cracking it but it’s gonna take 11 years, then maybe nobody gets too freaked out. But if they say we can do it and we can do it in six months then even if we go, well, there’s not a lot of secrets that are gonna be worth grabbing and decrypting and, you know, there are very few computers in the world that can do this – possibly as few as one today – but what’s that gonna look like in a year. Right? Or in two years or in four years. And then you go back to your whole harvest and decrypt scenario – and we did a whole podcast just on this, which if you want to understand that phenomenon, go listen to that podcast – but then I start to say, well geez, man, if my secret is still going to be a secret in a year or two years or four years, I have a problem and I have a problem today.

And so people are walking around throwing out these dates. Gotta be all switched over by 2032. You know? It seems to me like it’s more like gotta be switched over now. Right? And because harvest and decrypt is a realistic risk for lots of kinds of secrets.

Jason SorokoThat is true regardless of any of these Eureka moments that you and I will be reporting on until one day we have to deprecate these things. And so doing that exercise of the inventory of what secrets do I have that are being recorded right now that if they were, you know, if they were decrypted ten years from now, five years from now, you know, a year from now, and put them in that kind of level of prioritization, that is an excellent inventorying that you can start doing right now.

Hey, Tim, I have one other thought I’d like to share about this.

Tim CallanPlease.

Jason SorokoAnd again, it’s about a consistent message that I think we’ve been giving. We’ve been talking about hybrid certificates as a bridge between classic cryptographic algorithms and the future post quantum algorithms, quantum resistant algorithms. I want to let everybody know – we’ve said this before. It’s especially worth repeating on this particular story and that is the fact that the usage of hybrid certificates also allows for the agility, the ability to move between cryptographic algorithms between RSA and ECC.

So there might even be reasons to start using hybrid certificates now just to be able to move - - who knows, there may be a period of time, Tim, where we all have to knee jerk react away from RSA and move to ECC. Hybrid certificates will be a great way of bridging systems that are hard-coded to RSA and essentially use ECC. It’s such a good idea and that could be applicable sooner than later.

Tim CallanThat is, I think, a very insightful and important point. We talk about hybrid certs as if the two ends of the fork are always a pre-quantum and existing current KEM and a post quantum algorithm. But there’s not reason why that has to be. A hybrid cert is just a hybrid cert. You could have any two things on the branches. I don’t even know if it has to be two. But you could have any set of things on the branches and if we find ourselves in a situation where we are nervous about RSA as a foundation stone, there is a no reason why hybrid certificates couldn’t have utility in advance of that in order to allow us to swap over to ECC in a hurry in the event that that’s what we needed.

Jason SorokoExactly. You know, none of us has a crystal ball to know exactly which Eureka story is gonna make us all have to jump but something will eventually, and so getting your hands dirty on it now, that’s just such a good move.

Tim CallanNow even then though, like hybrid certs, I’m not sure what level of software support exists for hybrid certs in a private CA scenario, but I wouldn’t count on the fact that my stuff is gonna use a hybrid cert correctly.

Jason SorokoNo.

Tim CallanSo, I’m not sure you can take your hybrid certs and just roll them out and have them work today. Furthermore, you definitely can’t get hybrid public certs because they’re just not allowed and so even if a CISO is listening to this podcast right this minute and says good golly, we are in danger. I’m gonna go do this today. I don’t know if you can do this today. I think the industry has to do some work before you are even able to do this.

Jason SorokoRight. I would say that it starts even at the HSM level because all of these things require thinking about, you know, even just a different CA. What kind of devices are doing the consuming? What are they able to consume? There is a really large inventory of work that needs to happen first. Can it apply? How does it apply? And then starting to take a look at that extra set of fields within the x.509 standard and understanding how do you issue that, how do my HSMs and how are my vendors covering that? Like you say, Tim, in the public trust realm there’s a whole pile of industry work that has to happen. I am referring very specifically to some private trust stuff, and don’t forget your signing documents as well. Keep your signing systems in mind whenever you are doing your inventory because they are gonna apply just as much if not more so at this point.

Tim CallanAbsolutely. My last thought on this is that you and I have talked in the past about when people sort of try to calculate the zed date, they’re imagining the progression according to the current line that we see going on right now, right? They’re almost Moore’s lawing it and that’s fine to set sort of a minimum level of progress but, of course, there’s the opportunity for there to be much more advanced progress than that as people come up with new methods and new techniques and that’s really the story that we have here. Now again, this has to be validated, but it’s distinctly possible that that turns out to be that that’s exactly what happened here and what that does is that just pulls all those dates in and there’s no way to know if this proves out to be true. There’s no way to know that this is the last time that this is gonna happen.

Jason SorokoYep.

Tim CallanThere might be someone else somewhere else that’s readying their paper for publication that’s gonna pull it in even further, and so we really gotta be careful about thinking that these dates are far in the future. They just don’t seem that far in the future to me.

Jason SorokoNo. And, you know, Tim, I don’t think we’ve heard the last from the quantum annealing folks, which is an entirely different computing method.

Tim CallanAbsolutely.

Jason SorokoThere was a great, great talk at both Black Hat and DEFCON on that. It’s funny, I keep saying that Peter Schor’s great work on the Schor’s algorithm gets all the headlines. There are other things out there and it’s not just this plodding pace of the more and more, stable quantum bits from all the big quantum computer, you know, those folks – IBM, Google, etc. and, of course, all the competitors at the nation state level in China, but there’s also just really good math and the application of math on not just quantum computers or quantum annealing computers, but even on traditional computers. If you and I were to wake up tomorrow and read a paper that says, hey, we’ve solved RSA 2048. We can decrypt something in under a month and we can do it and it doesn’t require a quantum computer, I wouldn’t even shocked to the ends of the earth if I heard that in the next little while. I think it’s an actual possibility.

Tim CallanSo, what we have to do doesn’t really change. We’ve gotta be urgent. We’ve gotta get these new things in place and there’s a lot of work that needs to happen to do that and in that sense, it’s all the same, but it will be interesting to see what we learn in terms of this particular set of work and whether at the end of the day, it’ll be interesting to see if IBM decides to try this and we will definitely keep our eyes peeled to see what happens there.

Jason SorokoAbsolutely. And when they do, we’ll let you know.

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!