Researchers in Sweden say they have found a way to break a specific implementation of CRYSTALS-Kyber, one of a handful of “post-quantum” public key encryption algorithms chosen to underpin future U.S. government encryption standards.
According to a paper published by the KTH Royal Institute in Sweden, the algorithm — one of a number selected by both the U.S. National Institute for Standards and Technology and the NSA for future encryption standards and meant to withstand hacks from a future quantum computer — is vulnerable to a novel side channel attack.
Such attacks avoid directly targeting a system or hardware’s defenses, instead leveraging traces of the physical signals they emit (such as supply current, execution time or electromagnetic emissions) to extract secrets.
More recently, the advent of deep learning-based side channel analysis has made such attacks particularly relevant for breaking encryption systems and recovering secret keys. Apart from improving the effectiveness of some attacks, it has also allowed for attacks on true random number generators and physical unclonable functions, as well as non-differential message and secret key recovery attacks on post-quantum encryption algorithms.
“Deep learning based side-channel attacks can overcome conventional countermeasures such as masking, shuffling, random delays insertion, constant-weight encoding, code polymorphism, and randomized clock,” wrote researchers Elena Dubrova, Kalle Ngo and Joel Gärtner.
Encryption algorithms rely on a technique known as “masking” to prevent leakage of actionable emissions and defend against side channel attacks. Using a newly developed training method for neural networks, the researchers discovered a way to extract message bits for high-order masked implementations with the probability above 99%. They also developed a new message recovery method that manipulates ciphertexts to increase the leakage of message bits, improving the rate of message recovery and eventually extracting the algorithm’s secret key.
There are different orders of complexity for this type of masking, and previous experiments have found a way to execute successful side channel attacks against algorithms with third-order masked software implementations. The method developed by KTH was successful in breaking CRYSTALS-Kyber using fifth-order implementations.
“To the best of our knowledge, no side-channel attack on a higher than the third order masked implementation of any LWE/LWR PKE/KEM scheme has been demonstrated until now. The presented approach is not specific for CRYSTALS-Kyber and can potentially be applied to other LWE/LWR PKE/KEM schemes,” the authors wrote.
NIST official says no need for panic
CRYSTALS-Kyber is one of four post-quantum algorithms selected by NIST after a rigorous, multi-year vetting process to develop next generation encryption standards. While the other three are meant for digital signature and identity verification, CRYSTALS-Kyber is the only general purpose algorithm selected thus far.
For its part, NIST has long been aware of this possibility. Because a cryptographically-relevant quantum computer (or one capable of breaking classical encryption) has yet to be developed, researchers must base their choices on mathematical estimations of what a quantum computer might do. That’s one reason why the agency’s vetting process includes a number of backup options in case any algorithm is broken, including three possible replacements for CRYSTALS-Kyber.
That means that the algorithms we think can protect us might actually fall short, and NIST officials have noted that each round of the post-quantum cryptography selection process has revealed a previously unknown or unforeseen weakness in one of the algorithms. In fact, this isn’t even the first flaw found in a post-quantum algorithm: last year another finalist, SIKE, was removed from consideration after Belgian researchers cracked it in just over an hour using a decades-old math theory.
However, Dustin Moody, a mathematician in NIST’s computer security division, told SC Media that while the agency welcomes the new research, he does not believe it represents a fatal flaw in CRYSTALS-Kyber and said NIST currently has no plans to replace or deprioritize the algorithm.
Often, encryption schemes can be tweaked or altered to account for a newly discovered flaw, or experts can develop countermeasures that prevent the kind of leakage that could be used in a side channel attack. Moody said that while “a side channel attack can fatally kill an algorithm, with this particular paper, we don’t feel it does that in any way.”
“On this particular implementation of Kyber, we can use this [method] to break it under the circumstances in the experiment that they’re running. So it breaks a particular implementation that they’re working with, but it didn’t break the algorithm in general,” he said, later adding “It doesn’t say anything about the security of the algorithm itself. It didn’t exploit some flaw or design weakness to show that you’ll be able to attack it more generally.”
Those thoughts were echoed by Ali El Kaafarani, CEO of PQShield, which makes and sells quantum-resistant technologies. The paper appears to highlight a valid side channel attack method, but not one necessarily specific to CRYSTALS-Kyber, and it doesn't unearth any new, fundamental weaknesses in the algorithm or its underlying mathematics.
“It's important to understand the difference between an algorithm and its potentially many different implementations. Any algorithm can and will inevitably have many non-secure/broken implementations, this doesn’t mean that the algorithm itself is broken, otherwise people wouldn’t still be using RSA/ECC now," El Kaafarani said.
Still, such adjustments do come with real tradeoffs. The algorithms selected by NIST were done in part based on their efficiency. Every new protection added to account for side channel leakage slows down its performance.
“For CRYSTALS-Kyber…we asked the cryptographic community to do a lot of work here, and in the second and third rounds of our process, research seemed to show that to protect Kyber pretty well, it would be about twice as slow when you added on lots of countermeasures to protect it from side channel attacks,” said Moody.
Last year, NIST announced that it would integrate four selected post-quantum algorithms into U.S. encryption standards by 2024. They include one algorithm for general encryption purposes (CRYSTALS-Kyber) and another three for digital signatures and identity verification (CRYSTALS-Dilithium, Falcon and Sphincs+). Their use will be mandatory for most civilian federal agencies per a White House national security memorandum, and many industries and international standards bodies rely on NIST standards when developing their own encryption policies.
