Root Causes 354: CyberSlash Attack Against CRYSTALS-Kyber

Episode Transcript

Lightly edited for flow and brevity.

• 

  Tim Callan

  So 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 Soroko

  That'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 Callan

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

• 

  Jason Soroko

  The 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 Callan

  Exactly. 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 Soroko

  You 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 Callan

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

• 

  Jason Soroko

  It is.

• 

  Tim Callan

  There'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 Soroko

  Exactly, 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 Callan

  Right.

• 

  Jason Soroko

  Thank 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 Callan

  It’s now 2024. So, there you are.

• 

  Jason Soroko

  Because 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 Callan

  So 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 Soroko

  Correct.

• 

  Tim Callan

  Even 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 Soroko

  Well, 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 Callan

  Ok. 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 Soroko

  Yeah. 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 Callan

  And 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 Soroko

  Two key pairs. One classic and one post-quantum.

• 

  Tim Callan

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

• 

  Jason Soroko

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

• 

  Tim Callan

  Ok. 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 Soroko

  That 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 Callan

  Yeah. It’s gonna change quickly.

• 

  Jason Soroko

  But 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 Callan

  Yeah. Ok. That's good.

• 

  Jason Soroko

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

• 

  Tim Callan

  Yeah. 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 Soroko

  Be amazing.

• 

  Tim Callan

  Amazing. All right. Thank you very much, Jason.

• 

  Jason Soroko

  Thank you, Tim.

• 

  Tim Callan

  This has been Root Causes.