Address a side channel in RSA and SM2

Barrett will branch to a different (and slower) algorithm if the input
is larger than the square of the modulus. This branch can be detected
by a side channel.

For RSA we need to compute m % p and m % q to get CRT started. Being
able to detect if m > q*q (assuming q is the smaller prime) allows a
binary search on the secret prime. This attack is blocked by input
blinding, but still seems dangerous. Unfortunately changing to use the
generic const time modulo instead of Barrett introduces a rather
severe performance regression in RSA signing.

In SM2, reduce k-r*x modulo the order before multiplying it with (x-1)^-1.
Otherwise the need for slow modulo vs Barrett leaks information about
k and/or x.

2 files changed, 4 insertions, 8 deletions

diff --git a/src/lib/pubkey/rsa/rsa.cpp b/src/lib/pubkey/rsa/rsa.cpp
index 9f14b9d6a..fd50ce539 100644
--- a/src/lib/pubkey/rsa/rsa.cpp
+++ b/src/lib/pubkey/rsa/rsa.cpp
@@ -247,7 +247,7 @@ class RSA_Private_Operation
          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, m_mod_p.reduce(m), powm_window);
+         auto powm_d1_p = monty_precompute(m_monty_p, ct_modulo(m, m_key.get_p()), powm_window);
          BigInt j1 = monty_execute(*powm_d1_p, masked_d1, m_max_d1_bits);
 
 #if defined(BOTAN_RSA_USE_ASYNC)
@@ -257,7 +257,7 @@ 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, m_mod_q.reduce(m), powm_window);
+         auto powm_d2_q = monty_precompute(m_monty_q, ct_modulo(m, m_key.get_q()), powm_window);
          const BigInt j2 = monty_execute(*powm_d2_q, masked_d2, m_max_d2_bits);
 
          /*
@@ -272,11 +272,7 @@ class RSA_Private_Operation
          BigInt j1 = future_j1.get();
 #endif
 
-         /*
-         To prevent a side channel that allows detecting case where j1 < j2,
-         add p to j1 before reducing [computing c*(p+j1-j2) mod p]
-         */
-         j1 = m_mod_p.reduce(sub_mul(m_key.get_p() + j1, j2, m_key.get_c()));
+         j1 = m_mod_p.multiply(j1 - j2, m_key.get_c());
          return mul_add(j1, m_key.get_q(), j2);
          }
 
diff --git a/src/lib/pubkey/sm2/sm2.cpp b/src/lib/pubkey/sm2/sm2.cpp
index cf08d0f1c..5ffd547cf 100644
--- a/src/lib/pubkey/sm2/sm2.cpp
+++ b/src/lib/pubkey/sm2/sm2.cpp
@@ -153,7 +153,7 @@ SM2_Signature_Operation::sign(RandomNumberGenerator& rng)
 
    const BigInt r = m_group.mod_order(
       m_group.blinded_base_point_multiply_x(k, rng, m_ws) + e);
-   const BigInt s = m_group.multiply_mod_order(m_da_inv, (k - r*m_x));
+   const BigInt s = m_group.multiply_mod_order(m_da_inv, m_group.mod_order(k - r*m_x));
 
    return BigInt::encode_fixed_length_int_pair(r, s, m_group.get_order().bytes());
    }