Merge GH #1610 Make exponentiation loop independent of exponent size

11 files changed, 119 insertions, 51 deletions

diff --git a/src/lib/math/numbertheory/monty_exp.cpp b/src/lib/math/numbertheory/monty_exp.cpp
index b32a7ab4c..b5336ef14 100644
--- a/src/lib/math/numbertheory/monty_exp.cpp
+++ b/src/lib/math/numbertheory/monty_exp.cpp
@@ -23,7 +23,7 @@ class Montgomery_Exponentation_State
                                      size_t window_bits,
                                      bool const_time);
 
-      BigInt exponentiation(const BigInt& k) const;
+      BigInt exponentiation(const BigInt& k, size_t max_k_bits) const;
 
       BigInt exponentiation_vartime(const BigInt& k) const;
    private:
@@ -71,8 +71,8 @@ Montgomery_Exponentation_State::Montgomery_Exponentation_State(std::shared_ptr<c
 namespace {
 
 void const_time_lookup(secure_vector<word>& output,
-                        const std::vector<Montgomery_Int>& g,
-                        size_t nibble)
+                       const std::vector<Montgomery_Int>& g,
+                       size_t nibble)
    {
    const size_t words = output.size();
 
@@ -94,10 +94,12 @@ void const_time_lookup(secure_vector<word>& output,
 
 }
 
-BigInt Montgomery_Exponentation_State::exponentiation(const BigInt& scalar) const
+BigInt Montgomery_Exponentation_State::exponentiation(const BigInt& scalar, size_t max_k_bits) const
    {
-   const size_t exp_nibbles = (scalar.bits() + m_window_bits - 1) / m_window_bits;
-   CT::unpoison(exp_nibbles);
+   BOTAN_DEBUG_ASSERT(scalar.bits() <= max_k_bits);
+   // TODO add a const-time implementation of above assert and use it in release builds
+
+   const size_t exp_nibbles = (max_k_bits + m_window_bits - 1) / m_window_bits;
 
    Montgomery_Int x(m_params, m_params->R1(), false);
 
@@ -159,9 +161,9 @@ monty_precompute(std::shared_ptr<const Montgomery_Params> params,
    }
 
 BigInt monty_execute(const Montgomery_Exponentation_State& precomputed_state,
-                     const BigInt& k)
+                     const BigInt& k, size_t max_k_bits)
    {
-   return precomputed_state.exponentiation(k);
+   return precomputed_state.exponentiation(k, max_k_bits);
    }
 
 BigInt monty_execute_vartime(const Montgomery_Exponentation_State& precomputed_state,
diff --git a/src/lib/math/numbertheory/monty_exp.h b/src/lib/math/numbertheory/monty_exp.h
index 61da258cc..632d7f7d6 100644
--- a/src/lib/math/numbertheory/monty_exp.h
+++ b/src/lib/math/numbertheory/monty_exp.h
@@ -28,13 +28,14 @@ monty_precompute(std::shared_ptr<const Montgomery_Params> params_p,
                  bool const_time = true);
 
 /*
-* Return g^x mod p
+* Return g^k mod p
 */
 BigInt monty_execute(const Montgomery_Exponentation_State& precomputed_state,
-                     const BigInt& k);
+                     const BigInt& k, size_t max_k_bits);
 
 /*
-* Return g^x mod p taking variable time
+* Return g^k mod p taking variable time depending on k
+* @warning only use this if k is public
 */
 BigInt monty_execute_vartime(const Montgomery_Exponentation_State& precomputed_state,
                              const BigInt& k);
diff --git a/src/lib/math/numbertheory/numthry.cpp b/src/lib/math/numbertheory/numthry.cpp
index a5c7a40ab..593abb6a7 100644
--- a/src/lib/math/numbertheory/numthry.cpp
+++ b/src/lib/math/numbertheory/numthry.cpp
@@ -524,6 +524,7 @@ bool is_prime(const BigInt& n, RandomNumberGenerator& rng,
    const BigInt n_minus_1 = n - 1;
    const size_t s = low_zero_bits(n_minus_1);
    const BigInt nm1_s = n_minus_1 >> s;
+   const size_t n_bits = n.bits();
 
    const Modular_Reducer mod_n(n);
    auto monty_n = std::make_shared<Montgomery_Params>(n, mod_n);
@@ -536,7 +537,7 @@ bool is_prime(const BigInt& n, RandomNumberGenerator& rng,
 
       auto powm_a_n = monty_precompute(monty_n, a, powm_window);
 
-      BigInt y = monty_execute(*powm_a_n, nm1_s);
+      BigInt y = monty_execute(*powm_a_n, nm1_s, n_bits);
 
       if(mr_witness(std::move(y), mod_n, n_minus_1, s))
          return false;
diff --git a/src/lib/math/numbertheory/powm_mnt.cpp b/src/lib/math/numbertheory/powm_mnt.cpp
index 5da91796f..8cb3f6a08 100644
--- a/src/lib/math/numbertheory/powm_mnt.cpp
+++ b/src/lib/math/numbertheory/powm_mnt.cpp
@@ -10,6 +10,7 @@
 #include <botan/numthry.h>
 #include <botan/monty.h>
 #include <botan/internal/monty_exp.h>
+#include <botan/internal/rounding.h>
 
 namespace Botan {
 
@@ -26,7 +27,11 @@ void Montgomery_Exponentiator::set_base(const BigInt& base)
 
 BigInt Montgomery_Exponentiator::execute() const
    {
-   return monty_execute(*m_monty, m_e);
+   /*
+   This leaks size of e via loop iterations, not possible to fix without
+   breaking this API. Round up to avoid leaking fine details.
+   */
+   return monty_execute(*m_monty, m_e, round_up(m_e.bits(), 8));
    }
 
 Montgomery_Exponentiator::Montgomery_Exponentiator(const BigInt& mod,
diff --git a/src/lib/misc/srp6/srp6.cpp b/src/lib/misc/srp6/srp6.cpp
index bf5c6ac93..cb7e3c600 100644
--- a/src/lib/misc/srp6/srp6.cpp
+++ b/src/lib/misc/srp6/srp6.cpp
@@ -82,6 +82,8 @@ srp6_client_agree(const std::string& identifier,
                   const BigInt& B,
                   RandomNumberGenerator& rng)
    {
+   const size_t a_bits = 256;
+
    DL_Group group(group_id);
    const BigInt& g = group.get_g();
    const BigInt& p = group.get_p();
@@ -93,9 +95,9 @@ srp6_client_agree(const std::string& identifier,
 
    const BigInt k = hash_seq(hash_id, p_bytes, p, g);
 
-   const BigInt a(rng, 256);
+   const BigInt a(rng, a_bits);
 
-   const BigInt A = group.power_g_p(a);
+   const BigInt A = group.power_g_p(a, a_bits);
 
    const BigInt u = hash_seq(hash_id, p_bytes, A, B);
 
@@ -117,7 +119,8 @@ BigInt generate_srp6_verifier(const std::string& identifier,
    const BigInt x = compute_x(hash_id, identifier, password, salt);
 
    DL_Group group(group_id);
-   return group.power_g_p(x);
+   // FIXME: x should be size of hash fn
+   return group.power_g_p(x, x.bits());
    }
 
 BigInt SRP6_Server_Session::step1(const BigInt& v,
@@ -125,19 +128,21 @@ BigInt SRP6_Server_Session::step1(const BigInt& v,
                                   const std::string& hash_id,
                                   RandomNumberGenerator& rng)
    {
+   const size_t b_bits = 256;
+
    DL_Group group(group_id);
    const BigInt& g = group.get_g();
    const BigInt& p = group.get_p();
 
    m_p_bytes = p.bytes();
    m_v = v;
-   m_b = BigInt(rng, 256);
+   m_b = BigInt(rng, b_bits);
    m_p = p;
    m_hash_id = hash_id;
 
    const BigInt k = hash_seq(hash_id, m_p_bytes, p, g);
 
-   m_B = group.mod_p(v*k + group.power_g_p(m_b));
+   m_B = group.mod_p(v*k + group.power_g_p(m_b, b_bits));
 
    return m_B;
    }
diff --git a/src/lib/pubkey/dh/dh.cpp b/src/lib/pubkey/dh/dh.cpp
index daa876538..ae6e9c589 100644
--- a/src/lib/pubkey/dh/dh.cpp
+++ b/src/lib/pubkey/dh/dh.cpp
@@ -40,16 +40,16 @@ DH_PrivateKey::DH_PrivateKey(RandomNumberGenerator& rng,
 
    if(x_arg == 0)
       {
-      m_x.randomize(rng, grp.exponent_bits());
+      const size_t exp_bits = grp.exponent_bits();
+      m_x.randomize(rng, exp_bits);
+      m_y = m_group.power_g_p(m_x, exp_bits);
       }
    else
       {
       m_x = x_arg;
-      }
 
-   if(m_y.is_zero())
-      {
-      m_y = m_group.power_g_p(m_x);
+      if(m_y == 0)
+         m_y = m_group.power_g_p(m_x, grp.p_bits());
       }
    }
 
@@ -62,7 +62,7 @@ DH_PrivateKey::DH_PrivateKey(const AlgorithmIdentifier& alg_id,
    {
    if(m_y.is_zero())
       {
-      m_y = m_group.power_g_p(m_x);
+      m_y = m_group.power_g_p(m_x, m_group.p_bits());
       }
    }
 
@@ -103,16 +103,16 @@ class DH_KA_Operation final : public PK_Ops::Key_Agreement_with_KDF
 
 secure_vector<uint8_t> DH_KA_Operation::raw_agree(const uint8_t w[], size_t w_len)
    {
-   BigInt x = BigInt::decode(w, w_len);
+   BigInt v = BigInt::decode(w, w_len);
 
-   if(x <= 1 || x >= m_p - 1)
+   if(v <= 1 || v >= m_p - 1)
       throw Invalid_Argument("DH agreement - invalid key provided");
 
-   x = m_blinder.blind(x);
-   x = m_powermod_x_p(x);
-   x = m_blinder.unblind(x);
+   v = m_blinder.blind(v);
+   v = m_powermod_x_p(v);
+   v = m_blinder.unblind(v);
 
-   return BigInt::encode_1363(x, m_p.bytes());
+   return BigInt::encode_1363(v, m_p.bytes());
    }
 
 }
diff --git a/src/lib/pubkey/dl_group/dl_group.cpp b/src/lib/pubkey/dl_group/dl_group.cpp
index 6a2d21c8b..75bdef6a2 100644
--- a/src/lib/pubkey/dl_group/dl_group.cpp
+++ b/src/lib/pubkey/dl_group/dl_group.cpp
@@ -26,6 +26,7 @@ class DL_Group_Data final
          m_monty_params(std::make_shared<Montgomery_Params>(m_p, m_mod_p)),
          m_monty(monty_precompute(m_monty_params, m_g, /*window bits=*/4)),
          m_p_bits(p.bits()),
+         m_q_bits(q.bits()),
          m_estimated_strength(dl_work_factor(m_p_bits)),
          m_exponent_bits(dl_exponent_size(m_p_bits))
          {}
@@ -52,11 +53,21 @@ class DL_Group_Data final
       size_t p_bits() const { return m_p_bits; }
       size_t p_bytes() const { return (m_p_bits + 7) / 8; }
 
+      size_t q_bits() const
+         {
+         if(m_q_bits == 0)
+            throw Invalid_State("DL_Group::q_bits q value is unset on this group");
+         return m_q_bits;
+         }
+
       size_t estimated_strength() const { return m_estimated_strength; }
 
       size_t exponent_bits() const { return m_exponent_bits; }
 
-      BigInt power_g_p(const BigInt& k) const { return monty_execute(*m_monty, k); }
+      BigInt power_g_p(const BigInt& k, size_t max_k_bits) const
+         {
+         return monty_execute(*m_monty, k, max_k_bits);
+         }
 
    private:
       BigInt m_p;
@@ -66,6 +77,7 @@ class DL_Group_Data final
       std::shared_ptr<const Montgomery_Params> m_monty_params;
       std::shared_ptr<const Montgomery_Exponentation_State> m_monty;
       size_t m_p_bits;
+      size_t m_q_bits;
       size_t m_estimated_strength;
       size_t m_exponent_bits;
    };
@@ -413,6 +425,11 @@ size_t DL_Group::p_bytes() const
    return data().p_bytes();
    }
 
+size_t DL_Group::q_bits() const
+   {
+   return data().q_bits();
+   }
+
 size_t DL_Group::estimated_strength() const
    {
    return data().estimated_strength();
@@ -446,7 +463,12 @@ BigInt DL_Group::multi_exponentiate(const BigInt& x, const BigInt& y, const BigI
 
 BigInt DL_Group::power_g_p(const BigInt& x) const
    {
-   return data().power_g_p(x);
+   return data().power_g_p(x, x.bits());
+   }
+
+BigInt DL_Group::power_g_p(const BigInt& x, size_t max_x_bits) const
+   {
+   return data().power_g_p(x, max_x_bits);
    }
 
 /*
diff --git a/src/lib/pubkey/dl_group/dl_group.h b/src/lib/pubkey/dl_group/dl_group.h
index 131151072..b206e5546 100644
--- a/src/lib/pubkey/dl_group/dl_group.h
+++ b/src/lib/pubkey/dl_group/dl_group.h
@@ -183,11 +183,25 @@ class BOTAN_PUBLIC_API(2,0) DL_Group final
 
       /**
       * Modular exponentiation
+      *
+      * @warning this function leaks the size of x via the number of
+      * loop iterations. Use the version taking the maximum size to
+      * avoid this.
+      *
       * @return (g^x) % p
       */
       BigInt power_g_p(const BigInt& x) const;
 
       /**
+      * Modular exponentiation
+      * @param x the exponent
+      * @param max_x_bits x is assumed to be at most this many bits long.
+      *
+      * @return (g^x) % p
+      */
+      BigInt power_g_p(const BigInt& x, size_t max_x_bits) const;
+
+      /**
       * Multi-exponentiate
       * Return (g^x * y^z) % p
       */
@@ -211,6 +225,13 @@ class BOTAN_PUBLIC_API(2,0) DL_Group final
       size_t p_bytes() const;
 
       /**
+      * Return the size of q in bits
+      * Same as get_q().bits()
+      * Throws if q is unset
+      */
+      size_t q_bits() const;
+
+      /**
       * Return size in bits of a secret exponent
       *
       * This attempts to balance between the attack costs of NFS
diff --git a/src/lib/pubkey/dsa/dsa.cpp b/src/lib/pubkey/dsa/dsa.cpp
index 7142e4788..e43c14de2 100644
--- a/src/lib/pubkey/dsa/dsa.cpp
+++ b/src/lib/pubkey/dsa/dsa.cpp
@@ -42,14 +42,14 @@ DSA_PrivateKey::DSA_PrivateKey(RandomNumberGenerator& rng,
    else
       m_x = x_arg;
 
-   m_y = m_group.power_g_p(m_x);
+   m_y = m_group.power_g_p(m_x, m_group.q_bits());
    }
 
 DSA_PrivateKey::DSA_PrivateKey(const AlgorithmIdentifier& alg_id,
                                const secure_vector<uint8_t>& key_bits) :
    DL_Scheme_PrivateKey(alg_id, key_bits, DL_Group::ANSI_X9_57)
    {
-   m_y = m_group.power_g_p(m_x);
+   m_y = m_group.power_g_p(m_x, m_group.q_bits());
    }
 
 /*
@@ -111,7 +111,7 @@ DSA_Signature_Operation::raw_sign(const uint8_t msg[], size_t msg_len,
    {
    const BigInt& q = m_group.get_q();
 
-   BigInt m(msg, msg_len, q.bits());
+   BigInt m(msg, msg_len, m_group.q_bits());
 
    while(m >= q)
       m -= q;
@@ -125,7 +125,7 @@ DSA_Signature_Operation::raw_sign(const uint8_t msg[], size_t msg_len,
 
    const BigInt k_inv = inverse_mod(k, q);
 
-   const BigInt r = m_mod_q.reduce(m_group.power_g_p(k));
+   const BigInt r = m_mod_q.reduce(m_group.power_g_p(k, m_group.q_bits()));
 
    /*
    * Blind the input message and compute x*r+m as (x*r*b + m*b)/b
diff --git a/src/lib/pubkey/elgamal/elgamal.cpp b/src/lib/pubkey/elgamal/elgamal.cpp
index 5aeeabc6c..1f62c2b1d 100644
--- a/src/lib/pubkey/elgamal/elgamal.cpp
+++ b/src/lib/pubkey/elgamal/elgamal.cpp
@@ -34,17 +34,21 @@ ElGamal_PrivateKey::ElGamal_PrivateKey(RandomNumberGenerator& rng,
 
    if(m_x.is_zero())
       {
-      m_x.randomize(rng, group.exponent_bits());
+      const size_t exp_bits = m_group.exponent_bits();
+      m_x.randomize(rng, exp_bits);
+      m_y = m_group.power_g_p(m_x, exp_bits);
+      }
+   else
+      {
+      m_y = m_group.power_g_p(m_x, m_group.p_bits());
       }
-
-   m_y = m_group.power_g_p(m_x);
    }
 
 ElGamal_PrivateKey::ElGamal_PrivateKey(const AlgorithmIdentifier& alg_id,
                                        const secure_vector<uint8_t>& key_bits) :
    DL_Scheme_PrivateKey(alg_id, key_bits, DL_Group::ANSI_X9_42)
    {
-   m_y = m_group.power_g_p(m_x);
+   m_y = m_group.power_g_p(m_x, m_group.p_bits());
    }
 
 /*
@@ -103,7 +107,7 @@ ElGamal_Encryption_Operation::raw_encrypt(const uint8_t msg[], size_t msg_len,
    const size_t k_bits = m_group.exponent_bits();
    const BigInt k(rng, k_bits);
 
-   const BigInt a = m_group.power_g_p(k);
+   const BigInt a = m_group.power_g_p(k, k_bits);
    const BigInt b = m_group.multiply_mod_p(m, m_powermod_y_p(k));
 
    return BigInt::encode_fixed_length_int_pair(a, b, m_group.p_bytes());
diff --git a/src/lib/pubkey/rsa/rsa.cpp b/src/lib/pubkey/rsa/rsa.cpp
index b58724c63..81eb55cd5 100644
--- a/src/lib/pubkey/rsa/rsa.cpp
+++ b/src/lib/pubkey/rsa/rsa.cpp
@@ -202,6 +202,8 @@ class RSA_Private_Operation
    protected:
       size_t get_max_input_bits() const { return (m_mod_bits - 1); }
 
+      const size_t exp_blinding_bits = 64;
+
       explicit RSA_Private_Operation(const RSA_PrivateKey& rsa, RandomNumberGenerator& rng) :
          m_key(rsa),
          m_mod_p(m_key.get_p()),
@@ -213,8 +215,11 @@ class RSA_Private_Operation
                    rng,
                    [this](const BigInt& k) { return m_powermod_e_n(k); },
                    [this](const BigInt& k) { return inverse_mod(k, m_key.get_n()); }),
+         m_exp_blinding_bits(64),
          m_mod_bytes(m_key.get_n().bytes()),
-         m_mod_bits(m_key.get_n().bits())
+         m_mod_bits(m_key.get_n().bits()),
+         m_max_d1_bits(m_key.get_p().bits() + m_exp_blinding_bits),
+         m_max_d2_bits(m_key.get_q().bits() + m_exp_blinding_bits)
          {
          }
 
@@ -229,10 +234,9 @@ class RSA_Private_Operation
       BigInt private_op(const BigInt& m) const
          {
          const size_t powm_window = 4;
-         const size_t exp_blinding_bits = 64;
 
-         const BigInt d1_mask(m_blinder.rng(), exp_blinding_bits);
-         const BigInt d2_mask(m_blinder.rng(), exp_blinding_bits);
+         const BigInt d1_mask(m_blinder.rng(), m_exp_blinding_bits);
+         const BigInt d2_mask(m_blinder.rng(), m_exp_blinding_bits);
 
          const BigInt masked_d1 = m_key.get_d1() + (d1_mask * (m_key.get_p() - 1));
          const BigInt masked_d2 = m_key.get_d2() + (d2_mask * (m_key.get_q() - 1));
@@ -240,18 +244,18 @@ class RSA_Private_Operation
 #if defined(BOTAN_TARGET_OS_HAS_THREADS)
          auto future_j1 = std::async(std::launch::async, [this, &m, &masked_d1, powm_window]() {
                auto powm_d1_p = monty_precompute(m_monty_p, m, powm_window);
-               return monty_execute(*powm_d1_p, masked_d1);
+               return monty_execute(*powm_d1_p, masked_d1, m_max_d1_bits);
             });
 
          auto powm_d2_q = monty_precompute(m_monty_q, m, powm_window);
-         BigInt j2 = monty_execute(*powm_d2_q, masked_d2);
+         BigInt j2 = monty_execute(*powm_d2_q, masked_d2, m_max_d2_bits);
          BigInt j1 = future_j1.get();
 #else
          auto powm_d1_p = monty_precompute(m_monty_p, m, powm_window);
          auto powm_d2_q = monty_precompute(m_monty_q, m, powm_window);
 
-         BigInt j1 = monty_execute(*powm_d1_p, masked_d1);
-         BigInt j2 = monty_execute(*powm_d2_q, masked_d2);
+         BigInt j1 = monty_execute(*powm_d1_p, masked_d1, m_max_d1_bits);
+         BigInt j2 = monty_execute(*powm_d2_q, masked_d2, m_max_d2_bits);
 #endif
 
          j1 = m_mod_p.reduce(sub_mul(j1, j2, m_key.get_c()));
@@ -269,8 +273,11 @@ class RSA_Private_Operation
 
       Fixed_Exponent_Power_Mod m_powermod_e_n;
       Blinder m_blinder;
-      size_t m_mod_bytes;
-      size_t m_mod_bits;
+      const size_t m_exp_blinding_bits;
+      const size_t m_mod_bytes;
+      const size_t m_mod_bits;
+      const size_t m_max_d1_bits;
+      const size_t m_max_d2_bits;
    };
 
 class RSA_Signature_Operation final : public PK_Ops::Signature_with_EMSA,