A key post-quantum algorithm may be vulnerable to side-channel attacks

As companies and governments around the world work on creating usable quantum computers, security researchers are also devising ways to protect data once those machines are available.

Quantum computers have the potential to crack the cryptographic algorithms in use today, which is why "post-quantum" cryptographic algorithms are designed to be so strong that they can survive huge leaps in computing power. 

A team in Sweden, however, says it’s possible to attack some of the new algorithms with other methods. 

Researchers at the KTH Royal Institute say they found a vulnerability in a specific implementation of CRYSTALS-Kyber — a “quantum safe” algorithm that the U.S. National Institute of Standards and Technology has selected as part of its potential standards for future cryptographic systems.

According to the Swedish team, CRYSTALS-Kyber is vulnerable to side-channel attacks, which use information leaked by a computer system to gain unauthorized access or extract sensitive information. Instead of trying to guess a secret key, a side-channel technique analyzes data such as small variations in power consumption or electromagnetic radiation to reconstruct what the machine is doing and find clues that would enable access.

CRYSTALS-Kyber was designed to be resistant to side-channel attacks, but the researchers said they had success using machine learning as part of their experiment, calling it a “breakthrough” in testing quantum-safe technology.

Machine learning “can overcome conventional countermeasures,” such as “masking,” which involves hiding the secret key using random numbers. Even if someone observes the encryption process, they can't discover the key.

Previous research on CRYSTALS-Kyber analyzed the algorithm with up to three “orders” of masking, but the Swedish team said it demonstrated its technique on fifth-order masking.

“The presented approach is not specific for CRYSTALS-Kyber and can potentially be applied to other schemes,” the researchers said.

New approach

The machine learning in the side-channel attack involved a neural network training method called recursive learning. This method made it possible to extract the smallest data units with high probability, the researchers said.

“This is a very notable, and novel, aspect of the research,” said Lukasz Olejnik, an independent cybersecurity researcher and consultant who did not participate in the study.

According to him, machine learning can be used to efficiently analyze data and learn patterns that reveal security weaknesses of the system. The researchers also said they could use machine learning to test algorithms for resistance to other types of attacks.

The attack targeted the specific implementation of CRYSTALS-Kyber, not its principles. A specific implementation of a post-quantum algorithm refers to its practical application in a software or hardware system.

“As long as the core principles stand and remain robust, we'll live with those,” Olejnik said.

A NIST official, Dustin Moody, told SC Magazine that this distinction is important, because the Swedish research “breaks a particular implementation that they’re working with, but it didn’t break the algorithm in general.” NIST is sticking with CRYSTALS-Kyber for its program, he said.

The agency did not respond to The Record’s request for comment.

According to Olejnik, it is necessary to research such attacks because they help create secure methods for implementing, deploying and utilizing the new cryptosystems.

CRYSTALS-Kyber is the only general-purpose algorithm selected so far for the NIST program. Three others are used for digital signature and identity verification.

Researchers need several post-quantum algorithms because it is currently unclear which ones will be most effective and secure against quantum computers.

Correction: A previous version of this story misstated the first name of NIST's Dustin Moody.