Side-Channel Attack Protection For Quantum Safe Cryptography

A recent Reuters Special Report discussed the race between the US and China to protect digital assets and communications from the potential threat posed by quantum computers. Cryptographically relevant quantum computers, those that are powerful enough to crack existing public key-based encryption methods, could compromise military, economic, and personal information across the globe. While the race is on to harness the benefits of quantum computers in science, industry, and medical applications, so too is the race to protect our data against attacks from quantum computers.

Quantum Defen5e (QD5), a Canadian cybersecurity firm, predicts a critical moment known as “Q-day” around 2025, when quantum computers may render current encryption useless. As we start a new year, 2025 suddenly doesn’t seem that far away, and we can no doubt expect the conversation around Quantum Safe Cryptography to continue the momentum that we have seen recently.

In August 2023, NIST published the first three draft standards for general-purpose encryption algorithms that can resist attack by quantum computers. These draft standards are FIPS 203 for ML-KEM (based on the CRYSTALS-Kyber algorithm), FIPS 204 for ML-DSA (based on the CRYSTALS-Dilithium algorithm), and FIPS 205 for SLH-DSA (based on the SPHINCS+ algorithm).

Deep learning-based side-channel analysis methods have already shown a protected CRYSTALS-Kyber hardware implementation to be vulnerable to profiling attacks (as detailed here and here) leading to successful key recovery. Similarly, side-channel attacks on CRYSTALS-Dilithium have been attempted. In this blog, I’ll be covering side-channel attacks in the context of Quantum Safe Cryptography as robust side-channel attack protection will remain an important security consideration in the quantum era.

The individual components of ML-KEM and ML-DSA are relatively straightforward to protect against side-channel attacks with countermeasures such as Boolean and arithmetic masking. However, in both, the full algorithms are more difficult and expensive to protect than the individual components due to their constructions. The first point is that both algorithms frequently switch between operations that require Boolean masking and operations that require arithmetic masking, so costly mask conversion algorithms are required. Furthermore, mask conversions have a long history of being tricky to implement securely; in the past it was always a good idea to avoid mask conversions altogether. This is not possible for ML-KEM and ML-DSA.

Protecting ML-KEM

ML-KEM, like many other KEM proposal algorithms in NIST’s PQC competition, uses the Fujisaki-Okamoto (FO) transform to construct an IND-CCA2 secure KEM from a simpler, IND-CPA secure public key encryption scheme. This includes a re-encryption step after decryption in order to protect against chosen ciphertext attacks. Unfortunately, it was discovered that the re-encryption can leak information about the private key (source) despite not using the private key. ML-KEM is based on the Module Learning With Errors (MLWE) problems, which contains a certain error correcting capability. MLWE is not an error correcting code but can correct some errors. After decrypting a faulty ciphertext, the information about what kind of error is present in the underlying message or whether the error was corrected depends on the private key used for decryption and can leak during the re-encryption step. Combining such observations from multiple faulty ciphertexts then allows mathematical deductions of the private key.

This is like message-recovery attacks on generic public-key encryption, so it’s not entirely new, but it significantly increases the attack surface for the ML-KEM decapsulation routine. Furthermore, it has emerged that profiled attacks on the FO transform are significantly easier for KEMs based on the FO transform as the profiling can be done on the encapsulation operation. Thus, powerful machine learning attacks (either classical template attacks or more novel deep learning attacks) have quickly become the most popular side-channel attack against ML-KEM. More classical side-channel attacks such as differential power analysis (DPA) are still relevant, but the profiled attacks are more powerful without the usual difficulty to perform profiling.

Protecting ML-DSA

ML-DSA, on the other hand, introduces novel difficulty for side-channel security assessments. Since the runtime of the algorithm is inherently probabilistic and message dependent without a fixed upper bound, security labs need to decide how to deal with the runtime differences. Small runtime differences are well known from some countermeasures (e.g., dummy cycles and clock jitter) and methods to deal with them are well established. Similarly, key recovery attacks that target specific intermediate values have well established alignment methods to ensure maximum efficiency for minimal certification cost. However, more generic methods such as TVLA struggle with the more pronounced probabilistic runtimes, and methods to rule out false positives from unlucky runtime outliers need to be studied more carefully. It is not clear that simply discarding outlier traces to avoid false positives doesn’t risk discarding real leakage. Initially, a combination of increased code review and layered evaluation will need to be followed, but further research may clarify under what conditions discarding outliers during the test is perfectly safe and lead to simpler test procedures.

Implementing side-channel attack protection is an important component for establishing an overall Quantum Safe design. The Rambus Quantum Safe IP Portfolio offers solutions that combine Quantum Safe Cryptography and DPA resistance. The Rambus QSE-IP-86 Quantum Safe Engine is a standalone cryptographic core that supports the NIST draft standards FIPS 203 ML-KEM and FIPS 204 ML-DSA. A DPA version of the core includes DPA-resistant cryptographic accelerators. Offering a secure basis for hardware-level security, the RT-65x and RT-66x Root of Trust families offer Quantum Safe Cryptography and protect against a wide range of hardware and software attacks through state-of-the-art side-channel attack countermeasures and anti-tamper security techniques.

Additional resources

• Product Brief: Rambus QSE-IP-86 Quantum Safe Engine IP
• Product Brief: Rambus RT-654 Quantum Safe Root of Trust
• Product Brief: Rambus RT-664 Quantum Safe Root of Trust
• White Paper: Protecting Data and Devices Now and in the Quantum Computing Era