CVE‐2024‐14041

Title: ML-KEM (Kyber) decapsulation leaks private key information through non-constant-time division in message decoding and ciphertext compression (KyberSlash).

Issue affecting: BC before 1.78 (from 1.73).

Fixed versions: BC 1.78.

Platform affected: Java 8 and later.

Three routines divided secret-derived polynomial coefficients by the modulus KyberEngine.KyberQ: Poly.toMsg, which decodes the decrypted message, and the ciphertext compression routines Poly.compressPoly and PolyVec.compressPolyVec. Integer division takes a data-dependent number of cycles on most CPUs, so the time taken to execute the division reveals information about its operand. All three are reached during decapsulation (KyberEngine.kemDecrypt) on data derived from the private key — taint chains kemDecrypt[sk] -> decrypt -> toMsg and kemDecrypt[sk] -> re-encrypt -> compressPoly / compressPolyVec, the latter through the Fujisaki-Okamoto re-encryption step. An attacker able to measure the timing of a large number of decapsulations performed with the same long-term private key can recover that key.

Compression performed during encapsulation is not affected: there the compressed values become the public ciphertext.

Five division sites were involved. Poly.toMsg had one (line 257 as observed in 1.73). Ciphertext compression had four, two per file — the 4-bit and 5-bit branches of Poly.compressPoly (lines 117 and 138; all secret-dependent sites in that function: 110, 117, 131, 138) and the 10-bit and 11-bit branches of PolyVec.compressPolyVec (lines 73 and 99; all secret-dependent sites: 61, 64, 73, 87, 90, 99). Each fix replaces the division with the shift-multiply-shift sequence used by the reference implementation, e.g. t <<= 4; t += 1665; t *= 80635; t >>= 28; t &= 15 for the 4-bit compression branch.

The affected code lived in org.bouncycastle.pqc.crypto.crystals.kyber; the package has since been renamed to org.bouncycastle.pqc.crypto.mlkem, where the fixes remain in place. Poly.toMsg was hardened further after 1.78, its multiply sequence replaced by a branch-free range comparison — that is a later improvement, not part of this issue.

The fixes were introduced in commit 5adb2c5c5b46 (KyberSlash1, 16 December 2023) and commit 1590247178f2 (KyberSlash2, 5 January 2024), both first released in 1.78. See also the KyberSlash disclosure and the pqc-forum thread referenced by the latter.