The Perils of Limited Key Reuse: Adaptive and Parallel Mismatch Attacks with Post-processing Against Kyber
Authors
Qian Guo, Erik Mårtensson, Adrian Åström
Qian Guo
Department of Electrical and Information Technology, Lund University, Lund, Sweden
qian dot guo at eit dot lth dot se
qian dot guo at eit dot lth dot se
Erik Mårtensson
Department of Electrical and Information Technology, Lund University, Lund, Sweden
Selmer Center, Department of Informatics, University of Bergen, Bergen, Norway
Advenica AB, Malmö, Sweden
erik dot martensson at eit dot lth dot se
Selmer Center, Department of Informatics, University of Bergen, Bergen, Norway
Advenica AB, Malmö, Sweden
erik dot martensson at eit dot lth dot se
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.
References
[AD97]
Miklós Ajtai and Cynthia Dwork. A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 284-293, New York, NY, USA. 1997. Association for Computing Machinery. DOI: 10.1145/258533.258604
[APS15]
Martin R Albrecht, Rachel Player, and Sam Scott. On the concrete hardness of learning with errors. Journal of Mathematical Cryptology, 9(3):169–203, 2015. DOI: 10.1515/jmc-2015-0016
[BBLP18]
Daniel J. Bernstein, Leon Groot Bruinderink, Tanja Lange, and Lorenz Panny. HILA5 Pindakaas: On the CCA Security of Lattice-Based Encryption with Error Correction. In Antoine Joux, Abderrahmane Nitaj, and Tajjeeddine Rachidi, editors, AFRICACRYPT 18, volume 10831 of LNCS, pages 203–216. May 2018. Springer, Heidelberg. DOI: 10.1007/978-3-319-89339-6_12
[BDH+19]
Ciprian Băetu, F. Betül Durak, Loïs Huguenin-Dumittan, Abdullah Talayhan, and Serge Vaudenay. Misuse Attacks on Post-quantum Cryptosystems. In Yuval Ishai and Vincent Rijmen, editors, EUROCRYPT 2019, Part II, volume 11477 of LNCS, pages 747–776. May 2019. Springer, Heidelberg. DOI: 10.1007/978-3-030-17656-3_26
[BGRR19]
Aurélie Bauer, Henri Gilbert, Guénaël Renault, and Mélissa Rossi. Assessment of the Key-Reuse Resilience of NewHope. In Mitsuru Matsui, editor, CT-RSA 2019, volume 11405 of LNCS, pages 272–292. March 2019. Springer, Heidelberg. DOI: 10.1007/978-3-030-12612-4_14
[DDGR20]
Dana Dachman-Soled, Léo Ducas, Huijing Gong, and Mélissa Rossi. LWE with Side Information: Attacks and Concrete Security Estimation. In Daniele Micciancio and Thomas Ristenpart, editors, CRYPTO 2020, Part II, volume 12171 of LNCS, pages 329–358. August 2020. Springer, Heidelberg. DOI: 10.1007/978-3-030-56880-1_12
[DFR18]
Jintai Ding, Scott R. Fluhrer, and Saraswathy RV. Complete Attack on RLWE Key Exchange with Reused Keys, Without Signal Leakage. In Willy Susilo and Guomin Yang, editors, ACISP 18, volume 10946 of LNCS, pages 467–486. July 2018. Springer, Heidelberg. DOI: 10.1007/978-3-319-93638-3_27
[DGK24]
Nir Drucker, Shay Gueron, and Dusan Kostic. A lean BIKE KEM design for ephemeral key agreement. In 5th NIST Post-Quantum Cryptography Standardization Conference. 2024. National Institute of Standards and Technology.
[Flu16]
Scott Fluhrer. Cryptanalysis of ring-LWE based key exchange with key share reuse. https://eprint.iacr.org/2016/085. Cryptology ePrint Archive, Report 2016/085. 2016.
[FO99]
Eiichiro Fujisaki and Tatsuaki Okamoto. Secure Integration of Asymmetric and Symmetric Encryption Schemes. In Michael J. Wiener, editor, CRYPTO'99, volume 1666 of LNCS, pages 537–554. August 1999. Springer, Heidelberg. DOI: 10.1007/3-540-48405-1_34
[GJN20]
Qian Guo, Thomas Johansson, and Alexander Nilsson. A Key-Recovery Timing Attack on Post-quantum Primitives Using the Fujisaki-Okamoto Transformation and Its Application on FrodoKEM. In Daniele Micciancio and Thomas Ristenpart, editors, CRYPTO 2020, Part II, volume 12171 of LNCS, pages 359–386. August 2020. Springer, Heidelberg. DOI: 10.1007/978-3-030-56880-1_13
[GM23]
Qian Guo and Erik Mårtensson. Do Not Bound to a Single Position: Near-Optimal Multi-positional Mismatch Attacks Against Kyber and Saber. In Thomas Johansson and Daniel Smith-Tone, editors, Post-Quantum Cryptography, pages 291–320, Cham. 2023. Springer Nature Switzerland. DOI: 10.1007/978-3-031-40003-2_11
[GMR20]
Aurélien Greuet, Simon Montoya, and Guénaël Renault. Attack on LAC Key Exchange in Misuse Situation. In Stephan Krenn, Haya Shulman, and Serge Vaudenay, editors, CANS 20, volume 12579 of LNCS, pages 549–569. December 2020. Springer, Heidelberg. DOI: 10.1007/978-3-030-65411-5_27
[HDV22]
Loïs Huguenin-Dumittan and Serge Vaudenay. On IND-qCCA security in the ROM and its applications: CPA security is sufficient for TLS 1.3. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2022), pages 613–642. 2022. Springer. DOI: 10.1007/978-3-031-07082-2_22
[HPP21]
Julius Hermelink, Peter Pessl, and Thomas Pöppelmann. Fault-Enabled Chosen-Ciphertext Attacks on Kyber. In Avishek Adhikari, Ralf Küsters, and Bart Preneel, editors, Progress in Cryptology – INDOCRYPT 2021, pages 311–334, Cham. 2021. Springer International Publishing. DOI: 10.1007/978-3-030-92518-5_15
[HV20]
Loïs Huguenin-Dumittan and Serge Vaudenay. Classical Misuse Attacks on NIST Round 2 PQC - The Power of Rank-Based Schemes. In Mauro Conti, Jianying Zhou, Emiliano Casalicchio, and Angelo Spognardi, editors, ACNS 20, Part I, volume 12146 of LNCS, pages 208–227. October 2020. Springer, Heidelberg. DOI: 10.1007/978-3-030-57808-4_11
[JMZ23]
Haodong Jiang, Zhi Ma, and Zhenfeng Zhang. Post-quantum Security of Key Encapsulation Mechanism Against CCA Attacks with a Single Decapsulation Query. In International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2023), pages 434–468. 2023. Springer. DOI: 10.1007/978-981-99-8730-6_14
[MJZ22]
Ruiqi Mi, Haodong Jiang, and Zhenfeng Zhang. Lattice Reduction Meets Key-Mismatch: New Misuse Attack on Lattice-Based NIST Candidate KEMs. Cryptology ePrint Archive, Paper 2022/1064. 2022.
[MKB+24]
Puja Mondal, Suparna Kundu, Sarani Bhattacharya, Angshuman Karmakar, and Ingrid Verbauwhede. A Practical Key-Recovery Attack on LWE-Based Key-Encapsulation Mechanism Schemes Using Rowhammer. In Christina Pöpper and Lejla Batina, editors, Applied Cryptography and Network Security, pages 271–300, Cham. 2024. Springer Nature Switzerland. DOI: 10.1007/978-3-031-54776-8_11
[MN23]
Alexander May and Julian Nowakowski. Too Many Hints – When LLL Breaks LWE. In Advances in Cryptology – ASIACRYPT 2023: 29th International Conference on the Theory and Application of Cryptology and Information Security, Guangzhou, China, December 4–8, 2023, Proceedings, Part IV, pages 106–137, Berlin, Heidelberg. 2023. Springer-Verlag. DOI: 10.1007/978-981-99-8730-6_4
[{Nat}23]
National Institute of Standards and Technology. Module-Lattice-based Key-Encapsulation Mechanism Standard. Technical report, Department of Commerce, Washington, D.C.. Federal Information Processing Standards Publication (FIPS) NIST FIPS 203 ipd. https://doi.org/10.6028/NIST.FIPS.203.ipd. 2023.
[OWT20]
Satoshi Okada, Yuntao Wang, and Tsuyoshi Takagi. Improving Key Mismatch Attack on NewHope with Fewer Queries. In Joseph K. Liu and Hui Cui, editors, ACISP 20, volume 12248 of LNCS, pages 505–524. 2020. Springer, Heidelberg. DOI: 10.1007/978-3-030-55304-3_26
[QCD19]
Yue Qin, Chi Cheng, and Jintai Ding. A Complete and Optimized Key Mismatch Attack on NIST Candidate NewHope. In Kazue Sako, Steve Schneider, and Peter Y. A. Ryan, editors, ESORICS 2019, Part II, volume 11736 of LNCS, pages 504–520. September 2019. Springer, Heidelberg. DOI: 10.1007/978-3-030-29962-0_24
[QCZ+21]
Yue Qin, Chi Cheng, Xiaohan Zhang, Yanbin Pan, Lei Hu, and Jintai Ding. A Systematic Approach and Analysis of Key Mismatch Attacks on Lattice-Based NIST Candidate KEMs. In Mehdi Tibouchi and Huaxiong Wang, editors, Advances in Cryptology - ASIACRYPT 2021 - 27th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 6-10, 2021, Proceedings, Part IV, volume 13093 of Lecture Notes in Computer Science, pages 92–121. 2021. Springer. DOI: 10.1007/978-3-030-92068-5_4
[Reg05]
Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In Harold N. Gabow and Ronald Fagin, editors, 37th ACM STOC, pages 84–93. May 2005. ACM Press. DOI: 10.1145/1060590.1060603
[RRCB20]
Prasanna Ravi, Sujoy Sinha Roy, Anupam Chattopadhyay, and Shivam Bhasin. Generic Side-channel attacks on CCA-secure lattice-based PKE and KEMs. IACR TCHES, 2020(3):307–335, 2020. https://tches.iacr.org/index.php/TCHES/article/view/8592 DOI: 10.13154/tches.v2020.i3.307-335
[RRD+23]
Gokulnath Rajendran, Prasanna Ravi, Jan-Pieter D’Anvers, Shivam Bhasin, and Anupam Chattopadhyay. Pushing the Limits of Generic Side-Channel Attacks on LWE-based KEMs - Parallel PC Oracle Attacks on Kyber KEM and Beyond. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2023(2):418–446, Mar. 2023. DOI: 10.46586/tches.v2023.i2.418-446
[SAB+20]
Peter Schwabe, Roberto Avanzi, Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Gregor Seiler, and Damien Stehlé. CRYSTALS-KYBER. Technical report, National Institute of Standards and Technology. available at https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-3-submissions. 2020.
[SLZ24]
Mingyao Shao, Yuejun Liu, and Yongbin Zhou. Pairwise and Parallel: Enhancing the Key Mismatch Attacks on Kyber and Beyond. ACM ASIA CCS 2024. 2024.
[TUX+23]
Yutaro Tanaka, Rei Ueno, Keita Xagawa, Akira Ito, Junko Takahashi, and Naofumi Homma. Multiple-Valued Plaintext-Checking Side-Channel Attacks on Post-Quantum KEMs. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2023(3):473–503, Jun. 2023. DOI: 10.46586/tches.v2023.i3.473-503
[UXT+22]
Rei Ueno, Keita Xagawa, Yutaro Tanaka, Akira Ito, Junko Takahashi, and Naofumi Homma. Curse of Re-encryption: A Generic Power/EM Analysis on Post-Quantum KEMs. IACR TCHES, 2022(1):296–322, 2022. DOI: 10.46586/tches.v2022.i1.296-322
[XIU+21]
Keita Xagawa, Akira Ito, Rei Ueno, Junko Takahashi, and Naofumi Homma. Fault-Injection Attacks Against NIST's Post-Quantum Cryptography Round 3 KEM Candidates. In Mehdi Tibouchi and Huaxiong Wang, editors, ASIACRYPT 2021, Part II, volume 13091 of LNCS, pages 33–61. December 2021. Springer, Heidelberg. DOI: 10.1007/978-3-030-92075-3_2
[ZJZ24]
Biming Zhou, Haodong Jiang, and Yunlei Zhao. CPA-secure KEMs are also sufficient for Post-Quantum TLS 1.3. In 30th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2024). 2024.
PDF
History
Submitted: 2024-07-08
Accepted: 2024-09-02
Published: 2024-10-07
Accepted: 2024-09-02
Published: 2024-10-07
How to cite
Qian Guo, Erik Mårtensson, and Adrian Åström, The Perils of Limited Key Reuse: Adaptive and Parallel Mismatch Attacks with Post-processing Against Kyber. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/a3n5qj888.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.