Noise-Tolerant Plaintext-Checking Oracle Attacks -- A Soft-Analytic Approach Applied to ML-KEM

Julius Hermelink; Erik Mårtensson; Maggie Tran

Paper 2025/1496

Noise-Tolerant Plaintext-Checking Oracle Attacks -- A Soft-Analytic Approach Applied to ML-KEM

Julius Hermelink

, Max Planck Institute for Security and Privacy

Erik Mårtensson

, Lund University, Advenica AB

Maggie Tran

, Lund University

Abstract

Plaintext-checking (PC) oracle attacks are among the most prominent types of attacks against NIST's recently standardized ML-KEM. Previous works have drastically reduced the number of queries needed to recover the secret key. Although this number is now close to the information-theoretic bound, current attacks have not yet been adapted to settings with increased noise and highly imperfect oracles. In attacks targeting real-world protected implementations, noisy leakage may lead to oracles that only provide a small advantage over guessing. This work shows how to efficiently exploit imperfect oracles arising from highly noisy side channels. We present several soft-analytic techniques that enable highly noise-tolerant parallel PC-oracle attacks. These techniques allow for successful attacks in relatively few traces from information that gives just a slight advantage over guessing. Additionally, we extend the generic framework for side-channel information from Eurocrypt 2025 and thereby relate our techniques to previous work. We then discuss several oracle instantiations that are based on the noisy Hamming weight model. These oracles rely on widely accepted assumptions, are easy to simulate, and allow for fair comparisons between different attacks. Furthermore, they allow countermeasures to be taken into account, and we evaluate the impact of masking. Our evaluations in these and previous models show that PC-oracle attacks are noise-tolerant on an entirely different scale compared to previous work. These improvements are of an algorithmic nature and orthogonal to the fact that the Fujisaki-Okamoto transform in ML-KEM offers a large attack surface. Finally, we discuss the implications of our findings for protected ML-KEM implementations.

Note: Completed preprint version.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: Side-Channel Attack ML-KEM Kyber PC-Oracle Attack SASCA
Contact author(s): julius hermelink @ mpi-sp org
erik martensson @ eit lth se
maggie tran @ eit lth se
History: 2025-10-03: last of 2 revisions; 2025-08-19: received; See all versions
Short URL: https://ia.cr/2025/1496
License: CC BY

BibTeX

@misc{cryptoeprint:2025/1496,
      author = {Julius Hermelink and Erik Mårtensson and Maggie Tran},
      title = {Noise-Tolerant Plaintext-Checking Oracle Attacks -- A Soft-Analytic Approach Applied to {ML}-{KEM}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1496},
      year = {2025},
      url = {https://eprint.iacr.org/2025/1496}
}