Is PQC Broken Already? Implications of the Successful Break of a NIST Finalist

Written by Jim Gable, Shannon Gray, and Denis Mandich of the CSA Quantum-Safe Security Working Group.

Reviewed by Mehak Kalsi and Bruno Huttner.

The cybersecurity industry was shocked recently by a paper from a Swedish team that broke one of the four NIST algorithms for Post-Quantum Cryptography (PQC). Three researchers in Stockholm published a paper that described a side-channel attack coupled with recursive machine learning (ML) code to break CRYSTALS-Kyber, the key exchange algorithm approved by NIST for PQC. The paper, titled “Breaking a Fifth-Order Masked Implementation of CRYSTALS-Kyber by Copy-Paste,” was released in December 2022.

This matters. Maybe this matters a lot, because the NIST algorithms are the basis of an upcoming world-wide transition to quantum-safe algorithms. This transition will stretch across 10 to 15 years, if not more, and is simply the largest cybersecurity transition in history. The reason for this NIST project and the enormous deployment effort is the growing threat from quickly improving quantum computers. Many people rightly look forward to the benefits of quantum computers, but ironically the most dramatic speed-up quantum computers are known to have is a way to easily break today’s most commonly used cybersecurity standards, worldwide and across all industries. Today’s quantum computers are still far too small to break the most common encryption standards such as RSA and ECC. But if it takes 10-15 years to make a global encryption transition, that starts looking like a close race until the day quantum computers are “cryptographically relevant,” that is, they can break today’s cybersecurity systems. Additionally, encrypted data from industry, government, and elsewhere can be stored today in large data warehouses and then read years from now with future quantum computers.

So if the only quantum-safe key exchange algorithm approved by NIST is broken before it is even deployed, then we have a problem. However, that initial impression is not the complete story. This is a side-channel attack, which means the researchers had direct access to the hardware while it was performing the key exchange. The original paper is completely open that it’s a side-channel attack, even in the very title. They detected small variations in electrical signals from the board and could use the ML software to eventually pull out the encrypted key. Moreover, side channel attacks can break even today’s algorithms in a similar manner, even though the general consensus is that today’s algorithms, if up to date, remain unbroken. Indeed, in this paper, the mathematical underpinning for the CRYSTALS-Kyber algorithm was not broken, instead an implementation was broken where the hardware was fully available to the attacker. This kind of side-channel attack has been addressed before and it is reasonable to expect that this attack can also be countered with adjustments to the implementation of the CRYSTALS-Kyber algorithm.

Side channel attacks are almost always possible, no matter what the platform. Often, they can be shown to be effective against already-deployed systems, not just a demo implementation. For example, SGX enclave attacks have been demonstrated on nearly every Intel CPU model released since 2015, affecting systems numbering in the hundreds of millions. So it remains dangerous to oversimplify this attack by dismissing it because it requires physical access. Once attackers understand a new technique is possible, they will often find creative ways to execute them remotely. The Hertzbleed vulnerability is a good example and not unlike the power analysis side-channel attack considered here.

Patching these types of flaws and design errors can often introduce additional complexity, performance degradation and, perhaps most importantly, new vulnerabilities. PQC algorithms are much more complex than the existing AKE algorithms that they replace. These already-complex new mechanisms have not had the benefit of many decades of cryptanalysis. We should expect further unwelcome surprises. This may be especially true as almost all threat research is being directed against Kyber, the sole remaining key exchange mechanism (KEM) for standardization in 2024.

So this paper should not be taken as an emergency, but as a warning. It’s a warning to consider physical protection of networking equipment and it’s a warning to be alert to new, clever attacks on the PQC algorithms. Meanwhile, NIST continues to narrow the implementation details of the first suite of PQC algorithms. Also, NIST plans to open a call for new quantum-safe algorithms in the future.

This emphasizes that as your organization transitions to quantum-safe software and hardware, you must be able to switch between future encryption algorithms quickly and smoothly. This is commonly described as “crypto-agility.”

In summary:

“The sky is falling” is wrong. The algorithm was not broken.

“Everything is fine” is wrong. Side-channel attacks are dangerous.

Disclaimer: The purpose of this blog is to provide commentary of the implications of the paper “Breaking a Fifth-Order Masked Implementation of CRYSTALS-Kyber by Copy-Paste" and not to validate the claims made.