Fiddling the Twiddle Constants | Expert Review #2

Introduction

Welcome back to the Expert Review series, where, together with PQShield, we delve into the dynamic world of cybersecurity to bring you unbiased and detailed analyses from seasoned professionals. If you missed our first edition, check it out here.

Today we are going to look back on CHES 2023, where P. Ravi presented “Fiddling the Twiddle Constants - Fault Injection Analysis of the Number Theoretic Transform”. The article takes advantage of a generic fault injection that threatens implementations of the coming NIST Post Quantum Cryptography standards, ML-KEM FIPS-203 (Kyber) and ML-DSA FIPS-204 (Dilithium).

About the paper

The paper titled “Fiddling the Twiddle Constants - Fault Injection Analysis of the Number Theoretic Transform” has been featured in the 2023 Volume, Issue 2 of the CHES publication, dated March 2023. It is a collaborative effort by authors Prasanna Ravi, Shivam Bhasin, and Anupam Chattopadhyay from Nanyang Technological University, along with Bolin Yang and Fan Zhang from Zhejiang University.

This research stands out for its critical examination of fault injection vulnerabilities within the Number Theoretic Transform (NTT), an essential element of lattice-based cryptographic primitives. The significance of its findings lies in the potential impact on the security of post quantum cryptographic implementations. Let’s dive in.

Our Expert Review

What was studied?

The NTT (Number Theoretic Transform) is at the heart of many structured lattice-based algorithms, enabling fast computation of polynomial arithmetic. The so-called ‘twiddle factors’, a set of constants, play an important role in the computation of the NTT. The key idea from Ravi et al. is to look at the consequences of the zeroization of these constants in both Kyber and Dilithium. This zeroization significantly lowers the entropy of secret data involved in the algorithm, revealing, in the case of Kyber, the private key or the shared secret, and allowing signature forgery or bypass of verification in the case of Dilithium. The authors of the article analysed several proposed implementations, including some that are protected by popular masking techniques.

Why is it important?

The fault model of this attack is certainly valid for many implementations in which the twiddle factors are pre-computed and stored in a table. Usually, integrity of these constants is not protected by the implementation. The fault attack applies to several implementations, including masked implementations of Kyber key generation and encapsulation, and Dilithium signature verification. It applies not only to the deterministic variant but also to the randomised (hedged) variant of Dilithium signature generation, which is generally thought to be easier to protect against physical attacks.

Protected implementations using masking in n shares are also vulnerable, but these challenge the attacker to make n faults. When applied to an SCA-protected implementation of Dilithium signature generation or verification, one single fault could suffice, because the targeted variables are not typical targets for power analysis, and they may not be well protected. Even if the effect of the zeroization of twiddle factors differs between Kyber and Dilithium, the exploitation of the vulnerability will be very similar on the same platform because it targets the same mechanism: the corruption of memory access. The authors prove the relevance of this vulnerability on a software implementation with an ElectroMagnetic Fault Injection (EMFI) setup. From the standpoint of an attacker, an EMFI bench able to fault a commonly-used SoC is under the bar of 1k€, which makes this kind of attack very attractive.

Which new insights have been contributed, and how significant are they?

The paper proposes a generic fault attack approach on RLWE/MLWE-based KEMs and digital signature schemes that use the NTT. The attack principle is simple to understand when looking at the NTT as a black box that one can corrupt to lower the entropy of its output. If this output is related to key-dependent data, then the reduced entropy can be exploited by analysing the result of a faulted computation. Applied to signature generation, for instance, the fault injection reduces the entropy of the randomness that hides the secret key. By analysing the generated faulty signature, the secret key can be recovered by solving some equations.

All it takes for the attacker to succeed is to gain access to a fault injection bench. As soon as faulting memory access on the target device is within reach, the game is over. Although the attack seems devastating, the authors propose several countermeasures that could be implemented with limited performance overhead.

How practical are the results?

The authors of the paper conducted practical experiments that illustrate attack results on software implementations with and without countermeasures. According to their analysis, almost all analysed implementations are at risk. However, due to the nature of the injected fault, it is not guaranteed that the attack path remains valid for secure ICs or hardware implementations where the twiddle factors are not stored into memory and accessed via a pointer mechanism. In this case, zeroization of the twiddle factors might be hard to achieve. A careful characterization of the device in question will determine whether or not the described vulnerability can be exploited.

When might the impact happen?

Since two of the coming NIST standards FIPS203 and FIPS204 are based on structured lattices leveraging the NTT, any and all cryptanalysis leveraging faults or side-channel analysis on the NTT are very relevant. The impact will certainly be felt in the immediate future!

In this article, attacks are conducted on side-channel secure implementations of these proposed standards, using masking and shuffling protections - meaning new and/or different protection methods should be implemented to ensure this fault injection attack can not be exploited by an attacker.

What’s next?

As we've seen, the critical vulnerabilities identified in the Number Theoretic Transform (NTT) and the subsequent attacks on cryptographic implementations underscore a significant concern in the security domain. The urgency to develop and implement robust countermeasures against these vulnerabilities cannot be overstated. This work not only highlights the need for continuous vigilance but also sets the stage for an ongoing exploration of implementation security in cryptographic algorithms.

Stay tuned for more reviews of other articles as we delve deeper into the advancements and challenges in the field of cryptography.