Technology Insights HOME | Perspectives from Our Experts on Technology Trends and Risks

Technology Insights HOME

Perspectives from Our Experts on Technology Trends and Risks.

Search

ARTICLE

3 mins to read

No, Post-Quantum Cryptography Finalist CRYSTALS-Kyber Wasn’t Hacked

Konstantinos Karagiannis

Director - Emerging Technologies

Views
Larger Font
3 minutes to read

Quantum computers are expected to cripple some types of cryptography within a decade. To prepare for this crypto apocalypse, the National Institute of Standards and Technology (NIST) has been working on selecting new ciphers to replace RSA and usher in a new era of post-quantum cryptography or PQC.

In July 2022, NIST recommended one of its first finalists in the cipher search, CRYSTALS-Kyber. There’s no standard yet — that’s expected in 2024 and will include a few final choices. However, just a few months later, researchers from the KTH Royal Institute of Technology in Stockholm, Sweden, published a paper claiming to have broken the CRYSTALS-Kyber algorithm using a combination of recursive training AI and side-channel attacks. Did an AI accomplish what a quantum computer shouldn’t be able to?

A side-channel attack

The researchers used a technique known as vertical side-channel leakage detection to analyze the decryption function of the CRYSTALS-Kyber algorithm. This technique involves analyzing the electrical signals produced by a computer when performing cryptographic operations. By analyzing these signals, the researchers identified weaknesses in the algorithm that could be exploited using a side-channel attack.

Side-channel attacks are nothing new, first introduced in the late 90s. They exploit how a protocol or algorithm is implemented, not the actual mathematical underpinnings. For example, these attacks could analyze the power consumption of a CPU running a program to reverse a cryptographic function. Side-channel attacks are one of the significant reasons NIST takes its time selecting new candidates for PQC. Implementing solid ideas from a blackboard into bulletproof cryptographic code is challenging.

To make CRYSTALS-Kyber resistant to side-channel attacks, a method known as masking will be used. Put simply, this approach randomly splits a secret into several shares, so an attacker must gather all of them to rebuild the secret. Higher-order masking is when more and more random values (i.e., masks) are used to protect a sensitive value. Specifically, an n-order masked implementation uses n+1 random values to protect each sensitive value. For example, a fifth-order masked implementation would use six random values to protect each sensitive value.

Here’s where things get interesting. As admitted in the KTH paper causing such a stir, no higher-order implementations of CRYSTALS-Kyber are publicly available. The existing C codebase is still a finalist—not production. The authors had to modify the current first-order masked C implementation of CRYSTALS-Kyber to extend it to higher orders of masking, such as fifth order. In other words, the researchers literally created the code version they attacked! Yes, the researchers are trying to spot a future weakness, but this was not an attack against code that NIST released into the world. That said, there is merit to the technique, and it will need to be considered, as all potential threats must be during the torture-testing phase of a cipher’s development.

Where does AI come in?

The researchers used a recursive training AI algorithm to analyze the data collected from power-trace side-channel leakage detection to carry out the side-channel attack. This is not the first use of a neural network in a side-channel attack. The first paper on the subject was published in 2016.

In the new paper, we learn that power traces from fourth and fifth-order masking implementations were used to train an AI with batch normalization. The impressive results show power traces in one example with prominent, clear peaks revealing the positions of two of the shares used in masking. Researchers claim this recovery of a message bit can be repeated with over 99% success in higher-order masking.

While the researchers’ findings have yet to be independently verified, they raise concerns about the security of post-quantum encryption algorithms like CRYSTALS-Kyber. The recent finalist SIKE, for example, also suffered a side-channel attack in its implementation. We can’t release final standards and code to protect against the quantum threat only to have them all fall to a bunch of AIs running on laptops that are fed juicy power traces and other side-channel information.

The most significant danger revealed here is that AI methods for enhancing side-channel attacks may continue to get better, faster than we can predict. Also, as the authors state, the recursive learning method may apply to other types of encryptions, including ones not vulnerable to a side-channel attack.

I look forward to seeing the new countermeasures they’re working on for side-channel attacks. That’s the point of vulnerability research of all types, of course, learning what we can do better in the future. For now, AI may have a virtual leg up on quantum computers in the imminent cryptographic threat race most people probably weren’t considering.

I’ll be watching this space closely as we await the NIST standards in 2024. Will vulnerability research, with AIs or not, delay this? Whenever the standards are released, that will be the real crypto apocalypse, as businesses will find regulators knocking on their doors to do something about making the switch.

To learn more about our quantum computing and emerging technology solutions, contact us.

Was this article helpful to you?

Thanks for your feedback!

Subscribe to The Protiviti View Blog

To face the future confidently, you need to be equipped with valuable insights that align with your interests and business goals.

In this Article

Find a similar article by topics

Authors

No noise.
Just insights.

Subscribe now

Related posts

Article

What is it about

Error correction typically involves a lot of physical qubits and using them to create one logical qubit. Ratios vary by...

Article

What is it about

The emergence of generative AI (GenAI) promises transformative impacts across all areas of an organization, including enterprise architecture. Since generative...

Article

What is it about

In March 2023, the U.S. Environmental Protection Agency (EPA) announced its final Good Neighbor Plan, putting protections in place for...