KyberSlash: Exploiting secret-dependent division timings in Kyber implementations

Daniel J. Bernstein; Karthikeyan Bhargavan; Shivam Bhasin; Anupam Chattopadhyay; Tee Kiah Chia; Matthias J. Kannwischer; Franziskus Kiefer; Thales Paiva; Prasanna Ravi; Goutam Tamvada

Paper 2024/1049

KyberSlash: Exploiting secret-dependent division timings in Kyber implementations

Daniel J. Bernstein, University of Illinois at Chicago, Chicago, IL 60607-7045, USA, Academia Sinica, Taiwan

Karthikeyan Bhargavan, Inria, Paris, France, Cryspen, Berlin, Germany

Shivam Bhasin, National Integrated Centre for Evaluation, Nanyang Technological University, Singapore, Temasek Labs, Nanyang Technological University, Singapore

Anupam Chattopadhyay, College of Computing and Data Science, Nanyang Technological University, Singapore, Temasek Labs, Nanyang Technological University, Singapore

Tee Kiah Chia, Temasek Labs, Nanyang Technological University, Singapore

Matthias J. Kannwischer, Quantum Safe Migration Center, Chelpis Quantum Tech, Taipei, Taiwan

Franziskus Kiefer, Cryspen, Berlin, Germany

Thales Paiva, University of Sao Paulo, Brazil, Fundep, Brazil, CASNAV, Brazil

Prasanna Ravi, College of Computing and Data Science, Nanyang Technological University, Singapore, Temasek Labs, Nanyang Technological University, Singapore

Goutam Tamvada, Cryspen, Berlin, Germany

Abstract

This paper presents KyberSlash1 and KyberSlash2 – two timing vulnerabilities in several implementations (including the official reference code) of the Kyber Post-Quantum Key Encapsulation Mechanism, currently undergoing standardization as ML-KEM. We demonstrate the exploitability of both KyberSlash1 and KyberSlash2 on two popular platforms: the Raspberry Pi 2 (Arm Cortex-A7) and the Arm Cortex-M4 microprocessor. Kyber secret keys are reliably recovered within minutes for KyberSlash2 and a few hours for KyberSlash1. We responsibly disclosed these vulnerabilities to maintainers of various libraries and they have swiftly been patched. We present two approaches for detecting and avoiding similar vulnerabilities. First, we patch the dynamic analysis tool Valgrind to allow detection of variable-time instructions operating on secret data, and apply it to more than 1000 implementations of cryptographic primitives in SUPERCOP. We report multiple findings. Second, we propose a more rigid approach to guarantee the absence of variable-time instructions in cryptographic software using formal methods.

Note: https://kyberslash.cr.yp.to/

Metadata

Available format(s): PDF
Category: Implementation
Publication info: Preprint.
Contact author(s): authorcontact-kyberslash @ box cr yp to
History: 2024-06-30: approved; 2024-06-28: received; See all versions
Short URL: https://ia.cr/2024/1049
License: CC BY

BibTeX

@misc{cryptoeprint:2024/1049,
      author = {Daniel J. Bernstein and Karthikeyan Bhargavan and Shivam Bhasin and Anupam Chattopadhyay and Tee Kiah Chia and Matthias J. Kannwischer and Franziskus Kiefer and Thales Paiva and Prasanna Ravi and Goutam Tamvada},
      title = {{KyberSlash}: Exploiting secret-dependent division timings in Kyber implementations},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1049},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1049}
}