Root Causes 280: Did an AI Break CRYSTALS-Kyber?

Hosted by

Fellow

Original broadcast date

February 24, 2023

Recent news reports might suggest that an AI-enhanced side attack has defeated the CRYSTALS-Kyber PQC algorithm. In this episode we clarify that Kyber has not been defeated to date and exactly what did occur. We define side channel attack, discuss the broader implications of this attack, and speculate on what would happen if Kyber actually were broken.

Podcast transcript

Lightly edited for flow and brevity.

TCTim CallanSo we saw a headline. This particular article appeared, it was February 21, 2023 in Security Week, written by Kevin Townsend and I’m gonna read the headline: “AI Helps Crack NIST Recommended Post-Quantum Encryption Algorithm”. Subhead: “The CRYSTALS-Kyber public-key encryption and key encapsulation method recommended by NIST for post-quantum cryptography has been broken using AI combined with side channel attacks.”

So, Jason, when I read this headline my brain exploded because I thought, OH WOW! But I think we’ve learned that there’s more to it than this. Correct?

Jason SorokoYeah. This looks like a case of the headline being perhaps incorrect but at the absolute very least – no.

TCTim CallanSadly over-simplified.

Jason SorokoFirst of all, whenever you are reading that particular headline – and you probably will – no, CRYSTALS-Kyber as a cryptographic algorithm has not been defeated. Period.

TCTim CallanThat’s the first headline. CRYSTALS-Kyber as a cryptographic algorithm as of the time of this recording has not been defeated. So, go on, Jason. What really happened then as opposed to CRYSTALS-Kyber having been defeated?

Jason SorokoSure. Look, AI is being used in so many places. I never suspected six months ago, a year ago, you and I would even be covering AI stuff just so much. But here it is. And, of course, it is not new for AI to be used in the assistance of white hat researchers trying to break software, trying to break instances of implementations of software, and side channel attacks are a form of attack that seems to be very, very useful to have that tool to be able to make sense of the information that’s being leaked out of side channels.

TCTim CallanAnd, Jason, my brain is telling me that you and I might have done an entire episode on this, but I didn’t look it up. Just briefly, what is a side channel attack?

Jason SorokoOh, that is a category of attacks where - - maybe I’ll get real specific because then it helps to explain really what it is. It was really popular for a while for people to be listening in on radio interference or electrical impulses of computer chips, specific Intel chips, and you could tell actually what was happening on the chip because of these signals or fluctuations in electricity, or it could be – there’s so many side channels where information is leaked in some interesting way. And, of course, a human being can’t interpret these little changes in voltages or changes in noise or changes in who knows what it is. So, it really is handy to have an AI – artificial intelligence – that is able to then listen to these things and interpret the - -

TCTim CallanSo, something like power consumption or voltage or sound emitted actually is modified, changes, based on the operation that’s being run and if you can understand what these changes signify then you can help to reduce the potential possible activities that a chip is taking and narrow the field of what you need to research. Which is one of the methods that people use to sometimes cut down on the cryptographic space that they are trying to break. Is that correct?

Jason SorokoCorrect, Tim.

Jason SorokoThink about a hard token that is basically acting as a secure element. Like holding a PKI certificate. And the operation of the reading of the memory within this device shouldn’t be able to be read outside of it. Otherwise it will compromise the device. Therefore, people who create things like secure elements really do a lot of work to shield the devices from various kinds of emissions that could be interpreted. There’s a whole science to this and it’s way beyond the scope of this podcast but, yeah, there’s people out there who obsess over this stuff.

TCTim CallanSo, that’s what a side channel attack is. That was used in combination with an AI? What did they do?

Jason SorokoWell, they basically found a flaw in the author’s code. Basically, the implementation of CRYSTALS-Kyber by some software that was implementing it had a flaw. A side channel attack actually was able to determine this and be able to unravel the implementation. Without getting way, way too deep in it - because it gets deep quickly – you know, probably one the earlier papers many people have seen, and the good folks from ISARA helped me to interpret this – just to call them out – but I will tell you that the implementation of AI for a side channel attack against an implementation of PQC, that’s an early stage piece of research and it’s useful to do. What’s not useful is to say that the cryptographic algorithm has been defeated.

TCTim CallanRight. So, to be clear, there is no need to run away from CRYSTALS-Kyber. We just need to make sure that we understand what is necessary to implement this correctly. The algorithm itself is not changing in any way but we have discovered – and we will probably continue to discover – ways that implementations of this algorithm could be vulnerable. We are going to need to document those and understand those and make sure that the real implementations in the real world in authenticate secure implementations isn’t subject to those vulnerabilities. Is that right?

Jason SorokoRight on. I would say, Tim, even to push this even a little further, you might ask, well, what is the PQC community doing to aid in implementations being safer? And the argument is, look, we are already dealing with extreme latency issues. Latency is maybe one of the biggest issues in creating and renewing these certificates. These great big PQC certificates and so, therefore, everything is written so lean. And that’s just my opinion, that’s not somebody - and I have real true experts who are saying this. Therefore, in order obfuscate or to help to try to defeat side channel attacks against improper implementations of very lean software, then that’s asking the authors of these softwares just a bit too much, in my opinion.

Therefore, you are gonna see more attacks like this. What it really means is really, really good implementations that are rock solid. And it makes sense, Tim, because I mean CRYSTAL-Kyber hasn’t gone through the standardization process yet to make what is a rock-solid implementation of it standardized. That’s what we are waiting for, and it’s a good example of why we are waiting for it, and good on the white hat community for pressing AI against this and showing a weakness in implementation. Bravo. This is good work. This has to happen but it’s just up to the journalist to not be inaccurate or to sensationalize.

TCTim CallanOne more time. We’ve said this twice. We’ll say it a third time. CRYSTALS-Kyber is not itself threatened in any way. That said, one wonders, you know, AIs have gone through leaps and bounds improvements in a very short period of time and it would be easy to guess that if you tried this same attack two years ago that we might not have had the tools to make it succeed. Is there an implication here that somebody might be able to use the same methodology and go take a hack at tried-and-true implementations of other algorithms like RSA and ECC and defeat them as well? Like real stuff that’s really implemented in the real world and is this something we should be really worried about?

Jason SorokoIt has happened. I can tell you right now I’ve been in the room at Black Hat where the ARM Trust Zone. I mean it’s kind of funny, what attracted me into the room at Black Hat was because the title of the track, right, the title of the talk was ARM Trust Zone Hacked or something like that. It was similar kind of thing, and this was by the actual author of the talk and when, you know, you got to paragraph three of the presentation it kind of dawned on me, oh, this is a failure in the implementation.

It wasn’t a side channel attack. It was another form of attack, but same thing. We’ve seen poor implementations ruin very good - - bad outcomes for very good intentions, unfortunately. And, hey, that’s what the white hats do. They ruin your day but they make you better

TCTim CallanAnd I guess this is asking you to speculate, but we do some speculating on this show. I start to wonder as our use of AI as a tool to augment our work becomes more sophisticated and as the AIs become better, and as you start to look at something that’s, again, very noisy and difficult to interpret for a human, like a side channel attack that in a lot of ways is made for AI, right, like that’s the juicy kind of AI use case right there, should we be worried that more attacks are gonna emerge against the real stuff we have in the real world that’s really widely deployed that there’s gonna be a whole new breed of zero days that we haven’t yet considered that are gonna suddenly pop up because of this new methodology?

Jason SorokoI gotta say, it’s a big question. I can tell right now, in terms of malicious use, AI has been used to just augment the productivity of the malware writer. We had a podcast about this. So, that would be the mainstay. But in terms of new classes of zero days, I don’t know. I don’t know. I think, geez, if things are moving so fast that it is speculation to suspect not. However, if AI systems start to learn patterns in how operating systems are made and they start to be able to be trained on things such as fuzzing, which leads to zero days, you know, an AI fuzzing software - - and I’m not even sure what AI would give you that would make it just that much better. I can tell you that potentially, potentially, AI could go off to start to look at patterns of prime numbers.

TCTim CallanYeah.

Jason SorokoAnd because human beings, mathematicians do this. What happens if you train an AI on patterns of large prime numbers and the AI goes Eureka. Oh I know how to find - - I know what the prime number of this and this is given this. And therefore, all of the sudden RSA, right, could be knocked out. It has not been done yet. I haven’t seen a lot of people talking about it yet but if I really try to use my imagination, Tim, you might be onto something. I just haven’t seen it yet.

TCTim CallanYeah. This particular combination of factors going into this particular attack was not something that had occurred to me until I just learned about it empirically and it just makes me wonder can you extrapolate that idea to other aspects of not even cryptography, just security in general? And maybe that’s too broad for this podcast but it’s an interesting thing to think about.

Now my next point that I come to out of this is, again, my initial response when I looked at this was HOLY MOSES, has CRYSTALS-Kyber been broken and if so, what are the implications of that. So I thought maybe it would be fun for you and I to talk about it. Let’s suppose that the headline and subhead as read were what I originally interpreted them to be. Someone had used an AI to determine that CRYSTALS-Kyber was fundamentally not secure as an algorithm. What would the implications of that be?

Just as a reminder for the listener, CRYSTALS-Kyber really is the de facto KEM in the NIST – key encryption module – in the NIST recommendations that we expect to be in use almost all of the time. So, hypothetically, if CRYSTALS-Kyber had to be taken out of the mix the way let’s say SIKE was last year or Rainbow was last year, what would that mean?

Jason SorokoWe definitely would have to then start to take a look at some of the others. The lucky thing is, CRYSTALS-Dilithium, Dilithium, for digital signature algorithms - - if I’m not mistaken was it Falcon or one of the others that - - I think there was at least two others that were chosen as special case cryptographic algorithms to be able to go to standardization. And so, you at least had options. It might have been awkward because it might not have fit every use case or it might have had high latency or whatever the issues are. But when it comes to KEMs, you don’t have a lot and that’s unfortunate because it’s such a wide needed area. Heck, I would love for somebody from the PQC community to answer that question, but I would say you are probably looking at, you know, Classic McEliece being brought to the - -

TCTim CallanProbably go to somewhere around four candidates in an awful hurry. Right.

Jason SorokoIn an awful hurry. In an awful, awful hurry.

TCTim CallanAnd try and see if you can feel good about one of these as the go forward algorithm. Classic McEliece would probably have to be the one just because it’s so well understood. We’d have to go, go, go because standards bodies are already talking about are they going to incorporate CRYSTALS-Kyber into their standards. Like they are doing that now. And if we have to switch to a different algorithm, maybe not all that work is lost but surely some of that work is lost.

Jason SorokoWell, it’s like, all the different isogeny candidates that are out there, they’re going through that right now. They’re going through that whole, oh crap. You know. They knew their biggest Achilles heels were hit with an arrow. That’s what happened to them. And so they are going back to the drawing board. They are not dead by any means. In fact, I think even folks that are out at NIST really want some success there because it starts to bring something other than, you know, you don’t want to have monoculture in your number systems in PQC. You want to have diversity, and isogeny will bring you that.

TCTim CallanWe’ve talked about this in the past, too. Having all your eggs in that one basket just makes it really scary in case something bad happens to that basket. Especially since so much of these cryptographic strategies that we are talking about are relatively young and so they haven’t been in production for the last 40 years the way RSA has - 45 years. Such that there’s been a lot of time for people to pound on it. And these are just newer. And that makes us nervous. And what if we fundamentally misunderstood the only basket we have, and it turns out it has no bottom?

Jason SorokoThis is what everybody should be thinking about, and if there’s anything to be worried about, it would be that. You know, on the flip side, if something does fail, thank goodness it failed in the hands of the good guys.

TCTim CallanYes. Thank goodness it failed before it was implemented on every single chip in production in the world.

Jason SorokoBoy oh boy, Tim, I tell ya. Cryptographic agility. Important.

TCTim CallanAbsolutely. And of course, the thing is, to some degree unless it can be mathematically proven that it’s unbreakable and even then you have to know are the boundaries of that mathematical proof really broad enough to cover all the possible attacks? And it’s ultimately a Black Swan problem, right? Like we are never going to know for sure that somebody tomorrow isn’t going to discover what wasn’t discovered today, and that’s just something we are stuck with. And, you know, this question about is something bad gonna happen? Are we gonna standardize on a PQC and roll it out super broad and then one day a genius at a whiteboard just ruins it all for everybody? That lurking possibility is never gonna really go away.

Jason SorokoNot for a long time. Not for a very long time. I gotta tell you – what I’m probably most realistically worried about right now - - because there’s a lot to worry about. Hard for your brain to worry about all of it even though the reality is that you could worry about all of it, I would say that more realistically as of right now, RSA is out there massively, around the world, laid on thick. It’s so ubiquitous it’s crazy just how much the RSA cryptographic algorithm is out there and oh my goodness, that’s the one that if some really brilliant white hat comes out - when I say white hat, I mean probably a mathematician of some kind – that’s the one that worries me because I think prime number factorization, as hard as it’s been over the years, people are getting better and better and better. And we saw that Chinese paper that came out recently that claimed that the usage of a quantum computer with so low number of stable qbits, that number of stable qbits actually exists today. The claim was you could potentially theoretically break RSA with it. Well, I’m wincing at like, ok, somebody is gonna try it.

And we are gonna report on that here as soon as that’s announced. You know it.

TCTim CallanYou bet.

Jason SorokoYou bet. And that’s the one where it’s like, oh crap, what happened? Like that’s the one that seems the closest.

TCTim CallanThat would be enormous. If it turned out that you could use an existing quantum computer with an existing number of stable qbits and you could actually break an RSA session, a 2048-bit RSA session, gee, that would be the ultimate game changer

Jason SorokoEven, Tim, if it only took a year. Right? If it took a year, we’re in trouble.

TCTim CallanAbsolutely. There’s all kinds of secrets that you don’t want to have revealed in a year. 100%. That would be big trouble even if it took a full year.

Wow. Ok. Well, anyway, this headlines as you can see, it got our attention real quick, but we will say for the fourth time in this podcast, the CRYSTALS-Kyber encryption algorithm has not been defeated. Rather, this is important progress in understanding how to implement CRYSTALS-Kyber correctly so it cannot be defeated and that’s the research to take away. It’s very important research but don’t worry, we are still good with Kyber for now.

Jason SorokoWe are still good with Kyber for now, thank goodness and away you go. Let’s get that thing standardized, get really good implementations out there. Thank you to the white hat community and all the people who work hard at this because I’ll tell you, that kind of research is not easy. AI keeps doing more and more interesting things. There’s a lot to watch here.

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!