(PDF) Daniel J. Bernstein, Karthikeyan Bhargavan, Shivam Bhasin, Anupam Chattopadhyay, Tee Kiah Chia, Matthias J. Kannwischer, Franziskus Kiefer, Thales Paiva, Prasanna Ravi, Goutam Tamvada. "KyberSlash: Exploiting secret-dependent division timings in Kyber implementations." Date: 2024.06.28. 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.

Two versions of the Valgrind patch are now available: version 20240730 (patching Valgrind-3.22.0) is the original version from Tee Kiah Chia used for experiments in the paper, and version 20240808 (patching current Valgrind git) has some tweaks from Daniel J. Bernstein for a revised API and for tests in Valgrind's test framework.

History

The following timeline traces public knowledge regarding the existence and exploitability of KyberSlash. See the paper for more information regarding attack techniques and detection mechanisms.

KyberSlash was first noticed by Goutam Tamvada, Karthikeyan Bhargavan, and Franziskus Kiefer as part of writing a formally verified implementation of Kyber in Rust. Tamvada, Bhargavan, and Kiefer reported their findings to the maintainer of the official pq-crystals/kyber repository. The repository was patched on 1 December 2023 to remove the KyberSlash1 code ("Updated poly_tomsg to prevent a compiler from using DIV").

KyberSlash was independently noticed by Daniel J. Bernstein as part of analyzing the reference code that various KEM design teams had submitted to the centralized SUPERCOP test framework. SUPERCOP takes code from anybody, is not a library, and does not make any security guarantees (for example, SUPERCOP benchmarks MD5, SIKE, and code submitted by NSA), but code in SUPERCOP often reflects code in libraries. Bernstein announced divisions in Kyber software on 15 December 2023 as a "possibly exploitable" security issue, saying that the divisions were taking secret inputs in "at least one case", namely the KyberSlash1 case.

The maintainer of the pq-crystals/kyber repository asked "did you check that the code executes in variable time on any particular CPU for the input ranges that are fed into the DIV instruction (if a compiler issues a DIV)?". Bernstein posted various examples of such CPUs.

On 19 December 2023, the first version of this web site's FAQ said the following regarding the question of whether KyberSlash was exploitable: "Maybe. Patch now; don't wait to see whether an exploit is demonstrated."

On 30 December 2023, Prasanna Ravi and Matthias J. Kannwischer announced that further divisions in the Kyber reference code also take secret inputs. These are the KyberSlash2 divisions.

On 30 December 2023, Daniel J. Bernstein posted a demo exploiting KyberSlash1 to often recover Kyber's complete secret key from dec timings of the end-of-November-2023 Kyber reference code running under Raspbian (gcc 8.3.0) on a Raspberry Pi 2. This demo succeeded twice in three experiments.

In June 2024, improved demos exploiting KyberSlash1 and KyberSlash2 were posted along with the KyberSlash paper.