Solving Concealed ILWE and Its Application for Breaking Masked Dilithium

Simon Damm, Asja Fischer, Alexander May, Soundes Marzougui, Leander Schwarz, Henning Seidler, Jean-Pierre Seifert, Jonas Thietke, Vincent Quentin Ulitzsch

TL;DR

This paper introduces "Concealed ILWE" (CILWE), a new problem that models realistic scenarios in side-channel attacks on lattice-based cryptography like Dilithium. The authors develop novel regression-based methods (Huber and Cauchy) that efficiently solve CILWE, outperforming existing techniques and enabling a practical attack on masked Dilithium implementations.

What Problem Does This Paper Address?

Lattice-based cryptography, particularly signature schemes like Dilithium, relies on the hardness of problems like Integer Learning With Errors (ILWE). The security of these schemes often depends on "zero-knowledge" samples, which are designed to reveal no information about the secret key. However, side-channel attacks can leak information about the secret randomness used to generate these samples, leading to "zero-error" samples or a mixture of both. This mixture, termed "Concealed ILWE" (CILWE) by the authors, makes the standard ILWE problem tractable for attackers. Existing methods like Ordinary Least Squares (OLS) and Integer Linear Programming (ILP) struggle with CILWE, either requiring an impractical number of samples or lacking efficiency guarantees. This paper aims to bridge this gap by developing efficient and robust methods to solve CILWE and demonstrate their effectiveness against masked Dilithium.

Methods

The core contribution is the introduction of two novel regression methods for solving CILWE:

  • Huber Regression: This method moderates the influence of outliers (zero-knowledge samples) by using a quadratic loss function within a certain range and a linear loss function outside. This provides theoretical guarantees for solving CILWE.
  • Cauchy Regression: This method further dampens the effect of outliers by using a logarithmic loss function. While it lacks theoretical convergence guarantees to a global optimum, it demonstrates superior practical performance.

Both methods are implemented using an iterative reweighted least squares (IRLS) algorithm. The authors also provide a theoretical analysis of Huber regression's sample complexity for Dilithium.

Datasets

The paper uses synthetic datasets generated to simulate CILWE instances, mimicking the characteristics of side-channel attacks on Dilithium. These datasets are generated with varying concealment rates and for different NIST security levels (2, 3, and 5). The authors also utilize real-world power trace data from a masked Dilithium implementation for their end-to-end attack demonstration.

Key Insights and Ideas

  • CILWE is a realistic threat: The paper convincingly argues that side-channel attacks naturally lead to CILWE instances, making it a crucial problem to address for the security of post-quantum cryptography.
  • OLS and ILP are insufficient for CILWE: The authors demonstrate through simulations and theoretical arguments why standard methods fail to efficiently solve CILWE, especially at higher concealment rates.
  • Regression is the key: Huber and Cauchy regression offer a powerful alternative, effectively balancing the influence of zero-error and zero-knowledge samples.
  • Cauchy regression excels in practice: While Huber regression has theoretical backing, Cauchy regression consistently requires fewer samples and handles higher concealment rates, making it the preferred method for practical attacks.
  • Micro-architectural leakage is exploitable: The paper details a specific micro-architectural leakage in the masked Dilithium implementation that enables the classification of coefficients, leading to CILWE samples.

Key Results

  • Superior performance: Huber and Cauchy regression significantly outperform OLS and ILP in terms of the number of samples required to recover the secret key, especially at higher concealment rates.
  • High concealment rates handled: Cauchy regression can successfully recover the secret key with concealment rates up to 90%.
  • Practical attack on masked Dilithium: The authors demonstrate a successful end-to-end profiling side-channel attack on a masked Dilithium implementation, recovering the secret key in minutes using Cauchy regression. This attack works across all NIST security levels.
  • Reduced sample complexity: Compared to prior work (e.g., UMTS24), their methods require fewer signatures for a successful attack.

Limitations and Future Work

  • Cauchy regression's lack of theoretical guarantees: While practically superior, Cauchy regression doesn't offer formal proof of convergence to a global optimum.
  • Classifier limitations: The authors note that their machine learning classifier, while effective for distinguishing between positive and negative coefficients, struggled to differentiate between intermediate values with very small Hamming weights.
  • Future work: The paper suggests generalizing the theoretical analysis of Huber regression and exploring its application to other lattice-based schemes. Further research into more robust machine learning classifiers for side-channel analysis is also implied.

Summary updated

BibTeX
@article{damm2025solving,
  author = {Simon Damm and Asja Fischer and Alexander May and Soundes Marzougui and Leander Schwarz and Henning Seidler and Jean-Pierre Seifert and Jonas Thietke and Vincent Quentin Ulitzsch},
  title = {{Solving Concealed ILWE and Its Application for Breaking Masked Dilithium}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2025},
}

Loading related content...

Figure