FIX: potential non-constant time division

reneme · FAlbertDev · atreiber94 · reneme · commit 5cfd8953f672 · 2023-12-19T14:26:45.000+01:00
Some compilers generate a non-constant time division operation for the division by KyberConstants::Q. Fix is based on the patch in the reference implementation: pq-crystals/kyber@dda29cc Found and initially reported by Goutam Tamvada, Karthikeyan Bhargavan, and Franziskus Kiefer of @cryspen. Independently reported by djb as "Kyberslash". fixes #3844 Co-Authored-By: Fabian Albert <fabian.albert@rohde-schwarz.com> Co-Authored-By: Amos Treiber <amos.treiber@rohde-schwarz.com>
diff --git a/src/lib/pubkey/kyber/kyber_common/kyber.cpp b/src/lib/pubkey/kyber/kyber_common/kyber.cpp
@@ -383,12 +383,21 @@ class Polynomial {
 
          this->csubq();
 
+         auto compress = [](uint32_t t) {
+            // (t << 1) + ((KyberConstants::Q / 2) / KyberConstants::Q) & 1
+            // Note that magic numbers assume that ::Q = 3329
+            t <<= 1;
+            t += 1665;
+            t *= 80635;
+            t >>= 28;
+            t &= 1;
+            return static_cast<uint8_t>(t);
+         };
+
          for(size_t i = 0; i < size() / 8; ++i) {
             result[i] = 0;
             for(size_t j = 0; j < 8; ++j) {
-               const uint16_t t = (((static_cast<uint16_t>(this->m_coeffs[8 * i + j]) << 1) + KyberConstants::Q / 2) /
-                                   KyberConstants::Q);
-               result[i] |= (t & 1) << j;
+               result[i] |= compress(this->m_coeffs[8 * i + j]) << j;
             }
          }
 
