CVE-2024-37880: Observable Discrepancy (CWE-203)
value: The Kyber reference implementation before 9b8d306, when compiled by LLVM Clang through 18.x with some common optimization options, has a timing side channel that allows attackers to recover an ML-KEM 512 secret key in minutes. This occurs because poly_frommsg in poly.c does not prevent Clang from emitting a vulnerable secret-dependent branch.
CWE description: The product behaves differently or sends different responses under different circumstances in a way that is observable to an unauthorized actor, which exposes security-relevant information about the state of the product, such as whether a particular operation was successful or not.
CVSS v3 base score: 7.5
Published: 2024-06-10T02:15Z
Repository: https://github.com/pq-crystals/kyber
Language: C
Files changed: ref/poly.c, ref/verify.c, ref/verify.h
Commit date: 2024-06-03 09:00:59 +0200
Commit message: Fixed secret-dependent branch in poly_frommsg introduced by recent versions of clang with some flags (Thanks to Antoon Purnal for pointing this out!)

Diff: diff --git a/ref/poly.c b/ref/poly.c
index 3e73579..9d3b135 100644
--- a/ref/poly.c
+++ b/ref/poly.c
@@ -3,10 +3,11 @@
 #include "poly.h"
 #include "ntt.h"
 #include "reduce.h"
 #include "cbd.h"
 #include "symmetric.h"
+#include "verify.h"
 
 /*************************************************
 * Name:        poly_compress
 *
 * Description: Compression and subsequent serialization of a polynomial
@@ -164,20 +165,19 @@ void poly_frombytes(poly *r, const uint8_t a[KYBER_POLYBYTES])
 *              - const uint8_t *msg: pointer to input message
 **************************************************/
 void poly_frommsg(poly *r, const uint8_t msg[KYBER_INDCPA_MSGBYTES])
 {
   unsigned int i,j;
-  int16_t mask;
 
 #if (KYBER_INDCPA_MSGBYTES != KYBER_N/8)
 #error "KYBER_INDCPA_MSGBYTES must be equal to KYBER_N/8 bytes!"
 #endif
 
   for(i=0;i<KYBER_N/8;i++) {
     for(j=0;j<8;j++) {
-      mask = -(int16_t)((msg[i] >> j)&1);
-      r->coeffs[8*i+j] = mask & ((KYBER_Q+1)/2);
+      r->coeffs[8*i+j] = 0;
+      cmov_int16(r->coeffs+8*i+j, ((KYBER_Q+1)/2), (msg[i] >> j)&1);
     }
   }
 }
 
 /*************************************************
diff --git a/ref/verify.c b/ref/verify.c
index 1c43071..0fc007c 100644
--- a/ref/verify.c
+++ b/ref/verify.c
@@ -53,5 +53,12 @@ void cmov(uint8_t *r, const uint8_t *x, size_t len, uint8_t b)
 
   b = -b;
   for(i=0;i<len;i++)
     r[i] ^= b & (r[i] ^ x[i]);
 }
+
+
+void cmov_int16(int16_t *r, int16_t v, uint16_t b)
+{
+  b = -b;
+  *r ^= b & ((*r) ^ v);
+}
diff --git a/ref/verify.h b/ref/verify.h
index f95ac1b..09f0ad5 100644
--- a/ref/verify.h
+++ b/ref/verify.h
@@ -9,6 +9,9 @@
 int verify(const uint8_t *a, const uint8_t *b, size_t len);
 
 #define cmov KYBER_NAMESPACE(cmov)
 void cmov(uint8_t *r, const uint8_t *x, size_t len, uint8_t b);
 
+#define cmov_int16 KYBER_NAMESPACE(cmov_int16)
+void cmov_int16(int16_t *r, int16_t v, uint16_t b);
+
 #endif

Vulnerable code:   int16_t mask;
      mask = -(int16_t)((msg[i] >> j)&1);
      r->coeffs[8*i+j] = mask & ((KYBER_Q+1)/2);
Fixed code: #include "verify.h"
      r->coeffs[8*i+j] = 0;
      cmov_int16(r->coeffs+8*i+j, ((KYBER_Q+1)/2), (msg[i] >> j)&1);


void cmov_int16(int16_t *r, int16_t v, uint16_t b)
{
  b = -b;
  *r ^= b & ((*r) ^ v);
}
#define cmov_int16 KYBER_NAMESPACE(cmov_int16)
void cmov_int16(int16_t *r, int16_t v, uint16_t b);