Paper 2024/810

The Perils of Limited Key Reuse: Adaptive and Parallel Mismatch Attacks with Post-processing Against Kyber

Qian Guo, Lund University
Erik Mårtensson, Lund University, University of Bergen
Adrian Åström, Lund University
Abstract

In this paper, we study the robustness of Kyber, the Learning With Errors (LWE)-based Key Encapsulation Mechanism (KEM) chosen for standardization by NIST, against key mismatch attacks. We demonstrate that Kyber's security levels can be compromised with a few mismatch queries by striking a balance between the parallelization level and the cost of lattice reduction for post-processing. This highlights the imperative need to strictly prohibit key reuse in CPA-secure Kyber. We further propose an adaptive method to enhance parallel mismatch attacks, initially proposed by Shao et al. at AsiaCCS 2024, thereby significantly reducing query complexity. This method combines the adaptive attack with post-processing via lattice reduction to retrieve the final secret key entries. Our method proves its efficacy by reducing query complexity by 14.6 % for Kyber512 and 7.5 % for Kyber768/Kyber1024. Furthermore, this approach has the potential to substantially improve multi-value Plaintext-Checking (PC) oracle-based side-channel attacks against the CCA-secure version of Kyber KEM.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
Lattice-based cryptographyMismatch attacksKyberPost-quantum standardizationKEM
Contact author(s)
qian guo @ eit lth se
erik martensson @ eit lth se
adrian astrom @ outlook com
History
2024-05-27: approved
2024-05-24: received
See all versions
Short URL
https://ia.cr/2024/810
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/810,
      author = {Qian Guo and Erik Mårtensson and Adrian Åström},
      title = {The Perils of Limited Key Reuse: Adaptive and Parallel Mismatch Attacks with Post-processing Against Kyber},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/810},
      year = {2024},
      url = {https://eprint.iacr.org/2024/810}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.