Update (December 30, 2023): Additional potential variable timing issues were found and subsequently fixed.

Kyber-K2SO is Symbolic Software’s clean implementation of the Kyber IND-CCA2-secure key encapsulation mechanism (KEM), whose security is based on the hardness of solving the learning-with-errors (LWE) problem over module lattices. Kyber was recently chosen as the winning candidate algorithm of those submitted to the NIST post-quantum cryptography project.

We’ve updated Kyber-K2SO to address a variable timing logic vulnerability. This vulnerability also existed in the original Kyber reference implementation and continues to exist in many third-party implementations.

We’re proud to be among the first third-party implementations to patch the issue, and the first vendor to issue an actual security advisory. Our implemented fix is available for review on the Kyber-K2SO GitHub repository.

Background

The vulnerability was discovered by the Cryspen team two weeks ago and reported directly to the Kyber team, whereupon it was patched in the official Kyber reference implementation.

Despite fixing the issue, the Kyber team chose not to release an advisory. This lack of an advisory from the Kyber team meant that third-party implementations such as ours were not made aware of the vulnerability’s existence.

On December 16, roughly two weeks later, we were made aware of the vulnerability’s existence through a GitHub issue opened in the Kyber-K2SO repository by the Cryspen team. On December 17, we additionally received an independent email notification from Prof. Daniel J. Bernstein (who had later independently rediscovered the issue) notifying us of the vulnerability.

We then issued an update containing a software patch within 24 hours. Users are asked to update to Kyber-K2SO version 0.2.2 (or higher) to benefit from our fix for this issue.

The Vulnerability

The variable timing logic arises from how the original implementation divides by Q in the decapsulation function, as seen below in Kyber-K2SO’s original code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

// polyToMsg converts a polynomial to a 32-byte message
// and represents the inverse of polyFromMsg.
func polyToMsg(a poly) []byte {
  msg := make([]byte, paramsSymBytes)
  var t uint16
  a = polyCSubQ(a)
  for i := 0; i < paramsN/8; i++ {
    msg[i] = 0
    for j := 0; j < 8; j++ {
      // NOTE: the following assignment is responsible
      // for the variable timing issue, through the
      // division by paramsQ.
      t = (
        ((uint16(a[8*i+j]) << 1) + uint16(paramsQ/2))
        / uint16(paramsQ)
      ) & 1
      msg[i] |= byte(t << j)
    }
  }
  return msg
}

As seen below, this vulnerabilty was also present in the reference C Kyber code:

1
2
3
4
5
6
7
8

for(i=0;i<KYBER_N/8;i++) {
  msg[i] = 0;
  for(j=0;j<8;j++) {
    t  = a->coeffs[8*i+j];
    t += ((int16_t)t >> 15) & KYBER_Q;
    t  = (((t << 1) + KYBER_Q/2)/KYBER_Q) & 1;
    // Irrelevant code snipped
  }

It is unclear whether this division will be compiled into a multiplication instruction, depending on compiler optimizations. As noted by Goutam Tamvada, we can see that the output of some C compilers indeed produces a division instruction even when strong optimizations are specified:

Should a division instruction be emitted, its execution time would likely be variable and leak information about its secret input.

Most Implementations Affected

Even if you do not use Kyber-K2SO, there is a strong chance that your chosen Kyber implementation suffers from the same variable timing vulnerability. The KyberSlash website is currently tracking which libraries are vulnerable and which have issued patches or security advisories.

Impact

As far as we can tell, the impact of this vulnerability is the same as any standard variable timing vulnerability in low-level asymmetric cryptographic primitives: real-world impact can vary dramatically depending on practical use cases. However, in the worst case scenario, secret key information leakage could be possible. Therefore, we encourage everyone to examine their chosen Kyber implementations to ensure that they are protected from this issue.

Acknowledgements

We thank Goutam Tamvada, Karthikeyan Bhargavan, Franziskus Kiefer, Prof. Daniel J. Bernstein and Prof. Peter Schwabe for their valuable feedback regarding this issue.