Podcast
Root Causes 354: CyberSlash Attack Against CRYSTALS-Kyber
Hosted by
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.
TCTim 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?
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.
TCTim CallanRight. That's a great summary. So let's kind of break these down one by one. So what is KyberSlash?
TCTim 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?
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.
TCTim CallanRight. And to your point, Jason, I think this kind of thing is expected, right?
TCTim 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?
TCTim CallanRight.
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.
TCTim CallanIt’s now 2024. So, there you are.
TCTim 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?
TCTim 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?
TCTim 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?
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.
TCTim 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?
TCTim CallanIn that scenario, if I were to steal the Kyber key, the RSA key would remain unaffected? Right?
TCTim 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.
TCTim CallanYeah. It’s gonna change quickly.
TCTim CallanYeah. Ok. That's good.
TCTim 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.
TCTim CallanAmazing. All right. Thank you very much, Jason.
TCTim CallanThis has been Root Causes.