CVE‐2026‐18036

Title: NTRU leaks private key information by reducing secret values with a non-constant-time integer division.

Issue affecting: BC before 1.86 (from 1.73).

Fixed versions: BC 1.86.

Platform affected: Java 8 and later.

NTRU reduced secret values with the % operator in three helpers, each of which is a port of a reference-implementation routine that is deliberately division-free. Integer division takes a data-dependent number of cycles on most CPUs, so the reduction leaked its operand through timing.

Polynomial.modQ(int x, int q) — x % q, with q supplied as a parameter. A constant divisor can be strength-reduced to a multiply by the JIT; a variable one cannot, so this emitted a genuine hardware division on every call, in every execution tier. It is on the decapsulation path (NTRUKEMExtractor.extractSecret -> decrypt -> rqToS3 -> modQ, and also trinaryZqToZ3), where the dividend derives from the private key. Now x & (q - 1), restoring the reference's #define MODQ(X) ((X) & (NTRU_Q-1)). This is exact rather than approximate: NTRUParameterSet.q() returns 1 << logQ so q is always a power of two (logQ is 11, 12, 13 or 14 across the six parameter sets), and every call site passes a dividend already masked to 16 bits, so it is never negative.

Polynomial.mod3(short), Polynomial.mod3(byte) and NTRUSampling.mod3(int) — % 3 applied to the secret key polynomials f and g during key generation, to the message polynomials r and m during encapsulation (sampleIid over SHAKE(rmSeed)), and to coefficients recovered during decapsulation. These now use the reference implementation's division-free routine: fold by 255, then 15, then 3 (each step preserves the residue mod 3, since 3 divides 255 and 15 and 4 = 1 mod 3), leaving a value of at most 5, then one masked conditional subtraction to reach 0..2.

All four sites produce results identical to the previous code across their entire input domain — verified exhaustively over every short and every byte for mod3, and over every 16-bit dividend against each of the four q values for modQ — so keys, ciphertexts, shared secrets and the known-answer vectors are unchanged.

Unlike HQC, NTRU is a first-class algorithm in the default provider: it appears in BouncyCastleProvider.ASYMMETRIC_CIPHERS, is registered by BouncyCastlePQCProvider, and has NTRUEncapsulatorSpi / NTRUDecapsulatorSpi under the JDK 17+ multi-release overlay, so it is reachable through the standard javax.crypto.KEM API as well as the lightweight API.

The fix was introduced in commit 9c9ad88b6003.

Credit: The Robusta team: Deepak Bhargavan Pillai, Anirban Chakraborty, Chitchanok Chuengsatiansup, Matthew Roughan, Peter Schwabe, and Yuval Yarom.