Merge GH #1797 Fix Barrett reduction upper bound

4 files changed, 28 insertions, 17 deletions

diff --git a/doc/manual/side_channels.rst b/doc/manual/side_channels.rst
index 8f8067004..f58269d01 100644
--- a/doc/manual/side_channels.rst
+++ b/doc/manual/side_channels.rst
@@ -32,10 +32,11 @@ Barrett Reduction
 --------------------
 
 The Barrett reduction code is written to avoid input dependent branches. The
-Barrett algorithm only works for inputs that are most the square of the modulus;
-larger values fall back on a different (slower) division algorithm. This
-algorithm is also const time, but the branch allows detecting when a value
-larger than the square of the modulus was reduced.
+Barrett algorithm only works for inputs up to a certain size, and larger values
+fall back on a different (slower) division algorithm. This secondary algorithm
+is also const time, but the branch allows detecting when a value larger than
+2^{2k} was reduced, where k is the word length of the modulus. This leaks only
+the size of the two values, and not anything else about their value.
 
 RSA
 ----------------------
diff --git a/src/lib/math/numbertheory/reducer.cpp b/src/lib/math/numbertheory/reducer.cpp
index c37a1daeb..deb3874d3 100644
--- a/src/lib/math/numbertheory/reducer.cpp
+++ b/src/lib/math/numbertheory/reducer.cpp
@@ -28,9 +28,9 @@ Modular_Reducer::Modular_Reducer(const BigInt& mod)
       m_modulus = mod;
       m_mod_words = m_modulus.sig_words();
 
-      m_modulus_2 = Botan::square(m_modulus);
-
-      m_mu = ct_divide(BigInt::power_of_2(2 * BOTAN_MP_WORD_BITS * m_mod_words), m_modulus);
+      // Compute mu = floor(2^{2k} / m)
+      m_mu.set_bit(2 * BOTAN_MP_WORD_BITS * m_mod_words);
+      m_mu = ct_divide(m_mu, m_modulus);
       }
    }
 
@@ -76,7 +76,7 @@ void Modular_Reducer::reduce(BigInt& t1, const BigInt& x, secure_vector<word>& w
 
    const size_t x_sw = x.sig_words();
 
-   if(x.cmp(m_modulus_2, false) >= 0)
+   if(x_sw > 2*m_mod_words)
       {
       // too big, fall back to slow boat division
       t1 = ct_modulo(x, m_modulus);
diff --git a/src/lib/math/numbertheory/reducer.h b/src/lib/math/numbertheory/reducer.h
index 5276adbbc..65d9956f2 100644
--- a/src/lib/math/numbertheory/reducer.h
+++ b/src/lib/math/numbertheory/reducer.h
@@ -54,7 +54,7 @@ class BOTAN_PUBLIC_API(2,0) Modular_Reducer
       Modular_Reducer() { m_mod_words = 0; }
       explicit Modular_Reducer(const BigInt& mod);
    private:
-      BigInt m_modulus, m_modulus_2, m_mu;
+      BigInt m_modulus, m_mu;
       size_t m_mod_words;
    };
 
diff --git a/src/lib/pubkey/rsa/rsa.cpp b/src/lib/pubkey/rsa/rsa.cpp
index fd50ce539..441127984 100644
--- a/src/lib/pubkey/rsa/rsa.cpp
+++ b/src/lib/pubkey/rsa/rsa.cpp
@@ -234,6 +234,12 @@ class RSA_Private_Operation
 
       BigInt private_op(const BigInt& m) const
          {
+         /*
+         TODO
+           Consider using Montgomery reduction instead of Barrett, using
+           the "Smooth RSA-CRT" method. https://eprint.iacr.org/2007/039.pdf
+         */
+
          const size_t powm_window = 4;
 
          const BigInt d1_mask(m_blinder.rng(), m_blinding_bits);
@@ -242,12 +248,11 @@ class RSA_Private_Operation
    #define BOTAN_RSA_USE_ASYNC
 #endif
 
-
 #if defined(BOTAN_RSA_USE_ASYNC)
          auto future_j1 = std::async(std::launch::async, [this, &m, &d1_mask, powm_window]() {
 #endif
          const BigInt masked_d1 = m_key.get_d1() + (d1_mask * (m_key.get_p() - 1));
-         auto powm_d1_p = monty_precompute(m_monty_p, ct_modulo(m, m_key.get_p()), powm_window);
+         auto powm_d1_p = monty_precompute(m_monty_p, m_mod_p.reduce(m), powm_window);
          BigInt j1 = monty_execute(*powm_d1_p, masked_d1, m_max_d1_bits);
 
 #if defined(BOTAN_RSA_USE_ASYNC)
@@ -257,22 +262,27 @@ class RSA_Private_Operation
 
          const BigInt d2_mask(m_blinder.rng(), m_blinding_bits);
          const BigInt masked_d2 = m_key.get_d2() + (d2_mask * (m_key.get_q() - 1));
-         auto powm_d2_q = monty_precompute(m_monty_q, ct_modulo(m, m_key.get_q()), powm_window);
+         auto powm_d2_q = monty_precompute(m_monty_q, m_mod_q.reduce(m), powm_window);
          const BigInt j2 = monty_execute(*powm_d2_q, masked_d2, m_max_d2_bits);
 
+#if defined(BOTAN_RSA_USE_ASYNC)
+         BigInt j1 = future_j1.get();
+#endif
+
          /*
          * To recover the final value from the CRT representation (j1,j2)
          * we use Garner's algorithm:
          * c = q^-1 mod p (this is precomputed)
          * h = c*(j1-j2) mod p
          * m = j2 + h*q
+         *
+         * We must avoid leaking if j1 >= j2 or not, as doing so allows deriving
+         * information about the secret prime. Do this by first adding p to j1,
+         * which should ensure the subtraction of j2 does not underflow. But
+         * this may still underflow if p and q are imbalanced in size.
          */
 
-#if defined(BOTAN_RSA_USE_ASYNC)
-         BigInt j1 = future_j1.get();
-#endif
-
-         j1 = m_mod_p.multiply(j1 - j2, m_key.get_c());
+         j1 = m_mod_p.multiply(m_mod_p.reduce((m_key.get_p() + j1) - j2), m_key.get_c());
          return mul_add(j1, m_key.get_q(), j2);
          }