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

Mar 06, 2023Ravie LakshmananEncryption / 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^[1] in a paper.

CRYSTALS-Kyber is one of four post-quantum algorithms selected^[2]
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^[3], which randomizes^[4] 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^[5]
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.

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^[7]
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.”