Root Causes 434: Did Researchers Break AES Using Quantum Annealing?

Hosted by

Tim Callan

Chief Compliance Officer

Jason Soroko

Fellow

Original broadcast date

October 22, 2024

News reports claim Chinese researchers broke AES with a quantum annealing computer. We clarify the details and talk about the implications of this reported discovery.

Podcast Transcript

Tim CallanHow you doing today, Jason?

Jason SorokoDoing great, Tim. Glad to be here.

Tim CallanSo, Jason, let me ask you a question. Did Chinese researchers use quantum annealing to break AES?

Jason SorokoThey certainly did. Apparently, there was a paper published that is in Chinese from a Chinese journal, and I think what most people are reporting on is a newspaper article in China that was talking about this. That's where most people are getting their translations from. And so what most people are understanding is that the technique that was used with a quantum annealing computer was applied against a SPN structure, which is part of what AES is. It basically uses as part of how it employs its encryption. But Tim, the trick here was what they were applying it against was something that had a 22 bit key.
So let me set the stage for what I think really, really happened, and I'll let you put the color on top of it, which is way back in Root Causes Episode 37, you and I talked about the usage of quantum annealing and the fact that there was no equivalent Shor's algorithm for that type of quantum computing. But we expected it at some point. Well, guess what? Now we've seen it. Now we've seen it. Here's what really is going on, Tim. We were expecting way back in Episode 37 of this podcast, that a second front would be opened up. So it wouldn't just be a fully gated quantum computer along with Shor's algorithm, there would also be quantum annealing with another type of algorithm, and now we're finally seeing that.

Tim CallanAnd quantum annealing has its own pros and cons. Like it's still a quantum computing method. It still takes advantage of quantum physics. From an engineering perspective, I'm given to understand it's easier, but it seems like the use cases for quantum annealing are extremely specific. Is that.

Jason SorokoWell, I tell you what. Here's the way, a really good way of thinking about it. Quantum annealing is all about having a quantum computer that allows the erosion of qubits. And so you start with a much larger number of qubits, and then that degrades over time.

Tim CallanBecause that's the problem. Qubit stability is the big bug bear here and if that becomes less of an issue for you, then presumably some of the engineering problems are mitigated.

Jason SorokoAnd so we had always wondered, like going all the way back to the beginning of this podcast, when will quantum annealing potentially be used against forms of factorization problems, and we are now seeing that. So I think for people who are really in the know, and not just general journalism, what I'd like to say here is what we are now seeing is a second front. It's not just fully gated computers with Shor's algorithm. It is now quantum annealing along with I don't think there's enough translations yet of what these Chinese scientists had actually done, but suffice to say, they are using an off-the-shelf computer from a Canadian company called D-wave right in order to do this. And so this isn't some sort of secret nation state technology. It's off the shelf.

Tim CallanThis is something anybody who can afford the price tag can go by and D- wave has been around for a long time.

Jason SorokoYes, sir. Absolutely. So that is that's interesting. I think that the story of a second front is opening up is interesting. And I also find it interesting that they're not going to get going up against RSA or ECC. According to the translations, they're going up specifically against the basis of AES encryption, which is different than what we've seen before, Tim.

Tim CallanAnd that's that part's really interesting. Because there's kind of been this built in assumption of, look, we don't really need to worry about AES. Like, Grover's algorithm can reduce the attack time, but not enough that anybody is really worried about it. And maybe we want bigger keys. Maybe we don't even care about bigger keys. I've heard the argument being made that don't even bother changing the keys, because it's all fine. If this could be something that was materially better than what we could see through Grover's algorithm, might there be a need to swap out AES as well?

Jason SorokoTim, I don't think so, because we had a great conversation with Bas Westerbaan about this very topic and we talked about quantum computers in general and the issue with quantum computers was that you really aren't gaining a lot from the ability to factorize more quickly. It's definitely a threat against RSA and ECC, but against AES, I'm going to stick with what Bas taught us, which is that quantum computers and Grover's algorithm the amount of real additional power you're getting from a quantum computer, or even a quantum annealing computer, is perhaps not enough. So I think it's interesting research. It was against such a small bit length that, that's why they were successful and able to publish this. But in order to be to really crank this up, they need to do something different.

Tim CallanI think that's the question. If someone proof of concepts it on 22 bits, and then you say, look, it's just a matter of hard work to get up to a bit length we care about. That's one thing. It's a different thing if they can do it with 22 bits but that doesn't mean that we can extend that to something that's meaningful.

Jason SorokoI would be far more interested, Tim, to see researchers apply quantum annealing to the same kind of factorization problems that Shor's algorithm is trying to solve with a quantum computer. In other words, quantum annealing versus RSA and ECC will be a more interesting paper to me.

Tim CallanDo you think, in light of this paper, which did get a decent amount of press pickup, which you understand why. It’s an exciting headline. Do you think that will spur research into quantum annealing, and where it fits into all of these potential cryptographic attacks?

Jason SorokoWell, in all honesty, I hope it does, because it's been an awfully long time since we talked about it. And, it's been very quiet on that front. Now, there may be something going on, obviously underneath the covers that we just haven't heard about. And I'd be shocked if there wasn't. But certainly either it's out there already, or it doesn't exist, and it's just been radio silence. I don't know which it is, Tim. In this world, it's a little too hard to say. But in terms of spurring on people, tell you what, how about we spur it on and say, folks, we'd like to know anybody out there who's doing research in quantum annealing, doing something similar to what Shor's algorithm is doing with a quantum computer. We would love to hear from you.

Tim CallanAbsolutely. Just contact me on LinkedIn, and we'd actually interview you on the program if you've got some something going on in this area. I think that would be interesting.

Jason SorokoTim, there's a part two to this.
So if quantum annealing really is all about a different method of error handling, a different method - maybe a better way of saying it is quantum annealing is it really is all about taking into account the erosion of qubits. I would say that perhaps an even more interesting story from very recently has to do with some Eureka moments, some ah-ha moments about error handling. And I would say that that is probably one of the more interesting things that is going on right now with the usage of quantum computing error correction. And there's a really great article out there right now, Hybrid Quantum Error Correction Breakthrough Advances Quantum Computing, the Korea National Research Council of Science Technology published October 16, and it is going through Korean University and other researchers from other jurisdictions, and I won't get into the details, but what I would say is this - the advance in error correction for fully gated quantum computers will probably have more effect on whenever the Q date Zed date is than maybe the article that's getting more news right now, which is the Chinese using a quantum annealing computer. Just a final point on this is even IBM themselves, who uses a similar type of quantum computer that can apply this error correction breakthrough has changed their quantum computing roadmap, Tim, to not even concentrate so much on more stable qubits, but a more and longer stable set of qubits. And I find that to be a real world change for the positive in terms of quantum computing, and probably makes the advent of real quantum computers being able to utilize Shor's algorithm that much more reliable and usable. So very, very final point is, for those of you who are thinking quantum computing using Shor's algorithm is a boogey man that will never come, the arguments that I've heard for it is the lack of really good error correction and Tim, it seems like the Eureka moments to break that have now happened.

Tim CallanThat's big. So it's interesting. The thing that has gotten a lot of attention probably isn't going to turn out to be significant but, in the meantime, the work on - I hate to use a word like traditional - but the work on just full-fledged quantum computing, that's where we're going to see the attacks against Shor's algorithm continuing.

Jason SorokoExactly, Tim. So, I really would like to speak to other people who are very much connected to the physics problem, the engineering problem around creating quantum computers. And, to ask the question, how are these recent developments affecting your thoughts about the Zed date, the Q date? Are we still talking 2029, 2030 because these kinds of Eurekas were factored in, or are we starting to reel in the date a little bit? And that's an open question for us right now.

Tim CallanI think that's an interesting question. Maybe we can get a guest on who has a perspective on that. Thank you, Jason.

Jason SorokoThank you, Tim.

Tim CallanThis has been Root Causes.

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!