Hedged Dilithium Dis-Faulting | Expert Review #6

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 previous edition, check it out here.

In this review, we take a look at a key contribution to CHES 2024, the 26th edition, entitled Correction Fault Attacks on Randomized CRYSTALS-Dilithium from E. Krahmer, P. Pessl, G. Land, and T. Güneysu. This paper addresses fault attacks on the randomized/hedge ML-DSA (CRYSTALS-Dilithium) signature scheme. The work makes a significant contribution by presenting novel fault attacks that threaten the security of ML-DSA, the primary algorithm selected by NIST as its post-quantum cryptography standard for digital signatures, FIPS-204.

About the paper

ML-DSA offers two signing modes: a deterministic variant and a "hedged" variant that introduces fresh randomness in each signature generation. The hedged mode was made the default in order to increase robustness against physical attacks, such as differential fault attacks, which proved devastating for the deterministic mode. This paper challenges the perceived security of the hedged mode by introducing a powerful attack strategy that the authors summarize as "fault, then correct". Let’s dive in…

Our Expert Review

What was studied?

The paper's core methodology involves the idea of an adversary first injecting a single, targeted fault during the signing process to obtain a faulty and thus invalid signature. The attacker then leverages the public verification algorithm to computationally correct the faulty signature until it is accepted as valid. A successful correction reveals information about a secret intermediate value used during the signing process. By repeating this process, an attacker can collect enough information to solve for a portion of the secret key that is sufficient to forge legitimate signatures for any message.

The authors present two distinct attacks based on this principle. The first, the Skipping Fault Correction Attack, is a generalization of a previously known instruction-skipping fault attack. The authors adapt it to defeat the randomized signing mode by faulting a key addition that combines a secret component with a random one, and then using the correction method to find the missing secret value to recover the key. The second attack targets a computation involving only public data; the generation of a large public parameter from its small public seed. The attack injects a fault into this public parameter and uses the correction strategy to recover a secret random value that was used during that specific signing session, ultimately revealing the signer's secret key.

Why is it important?

This paper is significant because it demonstrates that the fault attack surface of ML-DSA is broader than previously understood, extending far beyond operations on secret, side-channel sensitive data. The attack on the public parameter is particularly dangerous. While fault attacks on public parameters are known for older cryptosystems, this is a novel vector for modern lattice-based signatures and challenges common assumptions about implementation security. Furthermore, the research shows that the attacks can be modified to circumvent popular countermeasures like shuffling, albeit with a moderate increase in the number of required signatures. This forces a re-evaluation of protection strategies, as developers can no longer assume that using the randomized mode and applying standard countermeasures provides a sufficient level of fault robustness.

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

The correction fault attack method is a versatile and powerful technique for exploiting faults in both the deterministic and hedged versions of ML-DSA. The work provides a significant new perspective by demonstrating that the fault attack surface extends to operations, such as public parameter generation, that are not sensitive to side-channel attacks and therefore might be left unprotected. It also shows that simply switching to the randomized signing mode does not provide sufficient fault robustness. The authors' analysis of how these attacks can bypass countermeasures, such as shuffling, highlights the need for a more careful and holistic approach to designing hardened implementations.

How practical are the results?

The attacks are demonstrated to be highly practical. The authors verified their findings using both simulated faults and real-world experiments, successfully inducing faults with clock glitches on an ARM-based microcontroller. The required number of faulty signatures is strikingly low. For the ML-DSA-44 parameter set (Dilithium2), the authors show the skipping fault attack can recover the key with 1024 faulty signatures, while the attack on the public parameter, when combined with lattice-reduction techniques, requires only 512 faulty signatures. The fault models are realistic. The first attack requires an instruction skip, a well-established technique. The second requires inducing a known perturbation at a specific location in the public parameter, which, while requiring more precision, was successfully achieved in their practical experiments.

When is the impact expected?

The paper reveals that implementations of ML-DSA that are susceptible to fault injection may already be vulnerable, even if they correctly implement the NIST-recommended randomized mode. Since the protection of public data generation has not been a primary focus, this work introduces a new and urgent consideration for any security evaluation of a device implementing ML-DSA. This research will undoubtedly drive new efforts to design more comprehensive and efficient fault countermeasures for lattice-based cryptography. The impact will certainly be felt in the immediate future!

What’s next?

Stay tuned for more reviews of other groundbreaking articles as we delve deeper into the advancements and challenges in the field of cryptography. The journey towards securing our digital infrastructure is ongoing, and we are committed to bringing you the latest insights and analyses from the forefront of cryptographic research.