KyberSlash attacks put quantum encryption projects at risk

Multiple implementations of the Kyber key encapsulation mechanism for quantum-safe encryption, are vulnerable to a set of flaws collectively referred to as KyberSlash, which could allow the recovery of secret keys.

CRYSTALS-Kyber is the official implementation of the Kyber key encapsulation mechanism (KEM) for quantum-safe algorithm (QSA) and part of the CRYSTALS (Cryptographic Suite for Algebraic Lattices) suite of algorithms.

It is designed for general encryption and part of the National Institute of Standards and Technology (NIST) selection of algorithms designed to withstand attacks from quantum computers.

Some popular projects using implementations of Kyber are Mullvad VPN and Signal messenger. The latter announced last year that it adopted the CRYSTALS-Kyber KEM as an additional layer that attackers must break to compute the keys that protect the users' communications.

The KyberSlash flaws are timing-based attacks arising from how Kyber performs certain division operations in the decapsulation process, allowing attackers to analyze the execution time and derive secrets that could compromise the encryption.

If a service implementing Kyber allows multiple operation requests towards the same key pair, an attacker can measure timing differences and gradually compute the secret key.

The problematic pieces of code that make the KyberSlash vulnerabilities (KyberSplash1 and KyberSplash2) were discovered by Goutam Tamvada, Karthikeyan Bhargavan, and Franziskus Kiefer - researchers at Cryspen, a provider of verification tools and mathematically proven software.

In a KyberSlash1 demo on a Raspberry Pi system, the researchers recovered Kyber's secret key from decryption timings in two out of three attempts.

Fixing effort underway

Cryspen analysts discovered KyberSlash1 late last November, and reported it to Kyber's developers, who pushed a patch for KyberSlash1 on December 1, 2023.

However, the fix wasn't labeled as a security issue, and it wasn't until December 15 that Cryspen took a more public approach and started informing impacted projects they needed to upgrade their Kyber implementations.

On December 30, KyberSlash2 was patched following its discovery and responsible reporting by Prasanna Ravi, a researcher at the Nanyang Technological University in Singapore, and Matthias Kannwischer, who works at the Quantum Safe Migration Center.

As of January 2, 2024, the list of projects below were identified as impacted by the issue and had the following fixing status:

• pq-crystals/kyber/ref – fully patched
• symbolicsoft/kyber-k2so – fully patched
• aws/aws-lc/crypto/kyber, main branch – fully patched
• zig/lib/std/crypto/kyber_d00.zig – fully patched
• liboqs/src/kem/kyber – patched only for KyberSlash1
• aws/aws-lc/crypto/kyber, fips-2022-11-02 branch – patched only for KyberSlash1
• randombit/botan – patched only for KyberSlash1
• mupq/pqm4/crypto_kem/kyber – patched only for KyberSlash1
• kudelskisecurity/crystals-go – patched on January 10
• antontutoveanu/crystals-kyber-javascript – unpatched
• Argyle-Software/kyber – unpatched
• debian/src/liboqs/unstable/src/kem/kyber – unpatched
• PQClean/PQClean/crypto_kem/kyber/aarch64 – unpatched
• PQClean/PQClean/crypto_kem/kyber/clean – unpatched
• rustpq/pqcrypto/pqcrypto-kyber (used in Signal) – unpatched

Also, the following libraries are tagged as not impacted because they do not have divisions with secret inputs:

• boringssl/crypto/kyber
• filippo.io/mlkem768
• formosa-crypto/libjade/tree/main/src/crypto_kem/kyber/common/amd64/avx2
• formosa-crypto/libjade/tree/main/src/crypto_kem/kyber/common/amd64/ref
• pq-crystals/kyber/avx2
• pqclean/crypto_kem/kyber/avx2

The worst case scenario is leaking of the secret key but this doesn't mean that all projects using Kyber are vulnerable to key leaks.

The repercussions of KyberSlash depend on the Kyber implementation and can vary depending on the practical use cases and additional security measures.

For example, Mullvad says KyberSlash does not impact its VPN product because they're using unique key pairs for each new tunnel connection, making it impossible to perform a series of timing attacks against the same pair.

BleepingComputer has contacted Signal to learn about the actual impact of KyberSlash on its cryptography and users' communications, as well as the project's remediation plans, but a comment wasn't immediately available.