Root Causes 354: CyberSlash Attack Against CRYSTALS-Kyber

Hosted by

Tim Callan

Chief Compliance Officer

Jason Soroko

Fellow

Original broadcast date

January 16, 2024

A newly published attack against common implementations of CRYSTALS-Kyber illustrates how cryptographic implementations can be vulnerable even if the cyphers themselves remain sound.

Podcast Transcript

Lightly edited for flow and brevity.

Tim CallanSo we have a breaking news item. This is in the ongoing saga of post-quantum cryptography. Date is January 7, 2024. I'm reading a BleepingComputer article. It's written by Bill Toulas – T-o-u-l-a-s and the headline reads “CyberSlash attacks put quantum encryption projects at risk”, which I'm not sure I entirely agree with this headline. Once we get into the article, the meat of the story, but basically, there are published attacks against common implementations of Kyber is the short story. Right, Jay?

Jason SorokoThat's right. And in fact, Tim, I think once we get to the root causes of this, it'll become clear what's going on.

That's one part of the story that will tell. I think, another part of the story that's interesting, and I think the title is a good one, in the sense that there are currently used and implemented systems that are out there that are actually using CRYSTALS-Kyber right now, that it's not, it's not the math. Right?

It's not a lattice map. It's not CRYSTALS-Kyber itself. It's the implementations. And these implementations have a fatal flaw that will be corrected, and we'll talk about that. But it is correct in saying that until the some of these problems in the implementations get patched, and the patches flow through all the systems and people start to understand that this fundamental flaw in how the implementations are being set out, it's going to cause this domino effect, where, you know, there are current implementations right now that are running that are problematic that need to be fixed up. But also, Tim, I think it speaks to a bigger picture of I think we're going to see a bunch of these bumps in the road along - - as new implementations of post-quantum algorithms come into place. And I think, Tim, it goes back to something we talked about really early on, which was the usage of hybrid certificates, which means we've talked about the concept of using pure PQC and we've talked about also the concept of using PQC along with a legacy algorithm as well.

And I think until we hit the quantum apocalypse, it's a really good idea to have a legacy classic algorithm backstop. And I think that's part of the lesson here.

Tim CallanRight. That's a great summary. So let's kind of break these down one by one. So what is KyberSlash?

Jason SorokoThe trick to understanding it, Tim, is right in the name – Slash. And good old division. Right? Which is, quite often, you know, when mathematic programmers, some mathematicians will represent division with a slash, and it's good old fashioned division that's the heart of the problem. It is the root cause here because timing attacks, Tim. Timing attacks, I mean everybody on this podcast remembers doing long division in school. And there were a certain number of steps you had to take in order to complete the division, and you had to show your teacher the work, and then you got your gold star. Well, computers are not a lot different in that division takes a certain amount of steps in order to complete. And therefore there is a timing associated with certain numbers. So, in other words, Tim, you can start to reverse a secret, right? If it's ultimately a cryptographic algorithm that’s doing a division in specific key parts of the implementation, if there's a secret that’s part of the equation where a divisor is in place, the time it takes to complete the calculation can actually give insight into what the actual input was. And that's a timing attack.

Tim CallanExactly. And basically, based on that you can make smart guesses about what the private key might be and you can reduce the total key space you're looking at until the point where it's practical to get it. Right?

Jason SorokoYou got it. And so Daniel J. Bernstein, right, researcher on this, who is, my goodness timing. It's kind of like the timing attack guru that's out there right now. Basically said on the 19th of December 2023, hey, we got a patch now. Don't wait to see whether this exploit can be demonstrated. It was scary enough that he said, hey, just patch, just patch. And on the 30th of December, he actually gave a demo of something called Kybers Slash 1, which successfully showed two out of three experiments that he had done actually were able to recover a key from this implementation.

This is the system working itself out. Thank goodness for guys like Daniel Bernstein, they’re true experts in an attacking a very specific kind of way. And sure enough, these implementations were giving up information. Now, there are better ways of implementing divisors within your equations. You know, it’s way beyond the scope of this podcast. But yes, there are better ways of doing it that are not based on oh, my goodness, we have to go back and change CRYSTALS-Kyber. This is about changing the implementation to simply do division better.

Tim CallanRight. And to your point, Jason, I think this kind of thing is expected, right?

Jason SorokoIt is.

Tim CallanThere's one thing to say, there's some core math, and we want to know if that math is robust, and if there's a way to attack it. There's a second point, which is to say, we're now going to take this and we're going to plug this into real world systems and it's possible that there are vulnerabilities that are in those real world systems that are in the implementations that also need to be chased down and solved and that also we need to discover them and realize, aha, this is a way that the enveloping code and technology around that core algorithm itself could be attacked. And we got to make sure that those things are structured correctly and hardened as well. Right?

Jason SorokoExactly, Tim. So let's in the spirit of accepting that this is the path, the path is to bump into these things. And thank goodness we do. Right?

Tim CallanRight.

Jason SorokoThank goodness that the white hats discover these things. And as we discover them, we have to keep our systems resilient. And thank goodness, it's not quantum apocalypse right now because we have this ability to rely on our classic legacy algorithms and implementations, which, you know, the can has been kicked very, very hard in those things. And so that's, to me is one of the big messages here is if everybody in 2024 - - in fact, I think you and I talk about this very recently on our looking forward podcast. In 2024, people are going to get their hands dirty with post-quantum stuff, and implementations. And so if you're doing that, be really careful about an implementation that doesn't have something to have as a fallback.

Because these implementations are fresh and this is a perfect reminder at the very beginning of 2024. To be honest with you, it was a 2023 story, but you know, the news media is kinda, and us, right, are reporting on this in 2024.

Tim CallanIt’s now 2024. So, there you are.

Jason SorokoBecause this research was literally happening over Christmas, it seems and so here we are now seeing the first proof of be careful about what you implement in post-quantum. I's a little too fresh to completely trust it and get ready to start patching.

Tim CallanSo Jason, question for you. So in a hybrid cert scenario, right, so I've got a certificate and it's using CRYSTALS-Kyber and it's using let's say RSA, right. The timing attack here only applies of course to CRYSTALS-Kyber, right?

Jason SorokoCorrect.

Tim CallanEven in a hybrid cert environment, even where both algorithms are sitting in the same cert, my RSA under those circumstances is still secure from private key theft, correct?

Jason SorokoWell, the big assumption you have to make, and I think it's a very safe assumption is that your systems are using classic implementations of doing what they need to do with RSA.

Tim CallanOk. Given that assumption. Now - if I'm a bad guy, though, and if the PQC implementation, if the Kyber implementation continues to have this vulnerability, RSA should be irrelevant, right? Because all I have to do is connect - - say, I want to use Kyber and then I can run the attack. And the fact that there's a parallel independent safe RSA channel, I think doesn't matter because I can still steal the Kyber key. Is that right?

Jason SorokoYeah. I hate to say it. It depends on the implementation.

So, to make a completely general statement like that would be unsafe for us to make because of the fact that it really depends on what you're doing and how you're implementing it.

Tim CallanAnd then in a hybrid cert scenario, do I have two sets of public private keys? One for each algorithm? Or do I have one private key that's giving out two public keys for the two different algorithms?

Jason SorokoTwo key pairs. One classic and one post-quantum.

Tim CallanIn that scenario, if I were to steal the Kyber key, the RSA key would remain unaffected? Right?

Jason SorokoYes. They are independent, is the best way to say it.

Tim CallanOk. Fair enough. All right, well, so hopefully, all of that will be academic. I guess the last thing is, apparently, patching is accomplished in some Kyber supporting libraries, but not all the libraries that are out there and the ones that remain, hopefully, we'll see that patching done, hopefully, we'll see it done soon. But it's not done yet.

Jason SorokoThat is correct. There is a great big long list of implementations that are affected and there's even people right now doing a pretty good job at researching, hey, who is using certain implementations and I don't think it's worth reading off, who is who and who has patched yet because this is very, this is live information.

Tim CallanYeah. It’s gonna change quickly.

Jason SorokoBut for those of you who are interested, this stuff is published, people are talking about it, it's all out there right now. We want to make you guys aware of it, you know, mostly from the practitioner standpoint of the big message being if you're gonna implement post-quantum algorithms right now that are, you know, pre-standard, you know, before the point in time at which these implementations are rock solid, which could take a long time, just have a backup, you know, as you are architecting your security don't go with something that is solely dependent on one post-quantum algorithm and one implementation. Don't make yourself fragile from the start.

Tim CallanYeah. Ok. That's good.

Jason SorokoCryptographic agility, Tim. I think that's the big title we can put on this.

Tim CallanYeah. Why didn't we. How come we haven’t recommended cryptographic agility in the past. Jason? I don't know why that didn't come up.

Jason SorokoBe amazing.

Tim CallanAmazing. All right. Thank you very much, 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!