Experts Discover Flaw in U.S. Govt's Chosen Quantum-Resistant Encryption Algorithm

Encryption / Cybersecurity

A group of researchers has revealed what it says is a vulnerability in a specific implementation of CRYSTALS-Kyber, one of the encryption algorithms chosen by the U.S. government as quantum-resistant last year.

The exploit relates to “side-channel attacks on up to the fifth-order masked implementations of CRYSTALS-Kyber in ARM Cortex-M4 CPU,” Elena Dubrova, Kalle Ngo, and Joel Gärtner of KTH Royal Institute of Technology said in a paper.

CRYSTALS-Kyber is one of four post-quantum algorithms selected by the U.S. National Institute of Standards and Technology (NIST) after a rigorous multi-year effort to identify the next-generation encryption standards that can withstand huge leaps in computing power.

A side-channel attack, as the name implies, involves extracting secrets from a cryptosystem through measurement and analysis of physical parameters. Some examples of such parameters include supply current, execution time, and electromagnetic emission.

The underlying idea is that the physical effects introduced as a result of a cryptographic implementation can be used to decode and deduce sensitive information, such as ciphertext and encryption keys.

One of the popular countermeasures to harden cryptographic implementations against physical attacks is masking, which randomizes the computation and detaches the side-channel information from the secret-dependent cryptographic variables.

“The basic principle of masking is to split each sensitive intermediate variable of the cryptographic algorithm into multiple shares using secret sharing, and to perform computations on these shares,” another group of researchers explained in 2016.

“From the moment that the input is split until the shared output of the cryptographic algorithm is released, shares of the sensitive intermediate variables are never combined in a way that these variables are unmasked, i.e. the unshared sensitive variables are never revealed. Only after the calculation has finished, the shared output is reconstructed to disclose its unmasked value.”

The attack method devised by the researchers involves a neural network training method called recursive learning to help recover message bits with a high probability of success.

“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,” the researchers said.

Discover the Latest Malware Evasion Tactics and Prevention Strategies

Ready to bust the 9 most dangerous myths about file-based attacks? Join our upcoming webinar and become a hero in the fight against patient zero infections and zero-day security events!

RESERVE YOUR SEAT

The researchers also developed a new message recovery method called cyclic rotation that manipulates ciphertexts to increase the leakage of message bits, thereby increasing the success rate of message recovery.

“Such a method allows us to train neural networks that can recover a message bit with the probability above 99% from high-order masked implementations,” they added.

When reached for comment, NIST told The Hacker News that the approach does not break the algorithm itself and that the findings don’t affect the standardization process of CRYSTALS-Kyber.

"Side-channel work was part of the evaluation, and will continue to be studied going forward, "NIST’s Dustin Moody was quoted as saying to Inside Quantum Technology (IQT) News. “It highlights the need to have protected implementations.”

“There exist papers that attack pretty much every cryptographic algorithm using side-channels. Countermeasures are developed, and many of the attacks aren’t realistic or practical in real-world scenarios.”

Found this article interesting? Follow us on Twitter  and LinkedIn to read more exclusive content we post.