International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Qian Guo , Department of Electrical and Information Technology, Lund University
Erik Mårtensson , Department of Electrical and Information Technology, Lund University, Selmer Center, Department of Informatics, University of Bergen, Advenica AB
Adrian Åström , Lund University
Download:
DOI: 10.62056/a3n5qj888
URL: https://cic.iacr.org//p/1/3/21
Search ePrint
Search Google
Abstract:

The Module Learning With Errors (MLWE)-based Key Encapsulation Mechanism (KEM) Kyber is NIST's new standard scheme for post-quantum encryption. As a building block, Kyber uses a Chosen Plaintext Attack (CPA)-secure Public Key Encryption (PKE) scheme, referred to as Kyber.CPAPKE. In this paper we study the robustness of Kyber.CPAPKE against key mismatch attacks.

We demonstrate that Kyber's security levels can be compromised if having access to a few mismatch queries of Kyber.CPAPKE, 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 Kyber.CPAPKE.

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 improve multi-value Plaintext-Checking (PC) oracle-based side-channel attacks and fault-injection attacks against Kyber itself.
BibTeX
@article{cic-2024-34832,
  title={The Perils of Limited Key Reuse: Adaptive and Parallel Mismatch Attacks with Post-processing Against Kyber},
  journal={cic},
  publisher={International Association for Cryptologic Research},
  volume={1, Issue 3},
  url={https://cic.iacr.org//p/1/3/21},
  doi={10.62056/a3n5qj888},
  author={Qian Guo and Erik Mårtensson and Adrian Åström},
  year=2024
}