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

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.