New API for blinded ECC point multiplication

No shared state

19 files changed, 451 insertions, 169 deletions

diff --git a/src/cli/speed.cpp b/src/cli/speed.cpp
index 78cbdccf6..465389dc9 100644
--- a/src/cli/speed.cpp
+++ b/src/cli/speed.cpp
@@ -1229,14 +1229,17 @@ class Speed final : public Command
 
             const Botan::BigInt scalar(rng(), group.get_p_bits());
             const Botan::PointGFp& base_point = group.get_base_point();
-            Botan::Blinded_Point_Multiply scalar_mult(base_point, group.get_order(), 4);
+
+            const Botan::PointGFp_Blinded_Multiplier scalar_mult(base_point);
+
+            std::vector<Botan::BigInt> ws;
 
             while(blinded_mult_timer.under(runtime))
                {
                const Botan::PointGFp r1 = mult_timer.run([&]() { return base_point * scalar; });
 
                const Botan::PointGFp r2 = blinded_mult_timer.run(
-               [&]() { return scalar_mult.blinded_multiply(scalar, rng()); });
+                  [&]() { return scalar_mult.mul(scalar, group.get_order(), rng(), ws); });
 
                BOTAN_ASSERT_EQUAL(r1, r2, "Same point computed by both methods");
                }
diff --git a/src/cli/timing_tests.cpp b/src/cli/timing_tests.cpp
index 86c1572ac..3e267829f 100644
--- a/src/cli/timing_tests.cpp
+++ b/src/cli/timing_tests.cpp
@@ -44,7 +44,6 @@
 
 #if defined(BOTAN_HAS_ECDSA)
    #include <botan/ecdsa.h>
-   #include <botan/reducer.h>
    #include <botan/numthry.h>
 #endif
 
@@ -251,19 +250,17 @@ class ECDSA_Timing_Test final : public Timing_Test
       ticks measure_critical_function(std::vector<uint8_t> input) override;
 
    private:
+      const Botan::EC_Group m_group;
       const Botan::ECDSA_PrivateKey m_privkey;
-      const Botan::BigInt m_order;
-      Botan::Blinded_Point_Multiply m_base_point;
-      const Botan::BigInt m_x;
-      const Botan::Modular_Reducer m_mod_order;
+      const Botan::BigInt& m_x;
+      std::vector<Botan::BigInt> m_ws;
    };
 
 ECDSA_Timing_Test::ECDSA_Timing_Test(std::string ecgroup)
-   : m_privkey(Timing_Test::timing_test_rng(), Botan::EC_Group(ecgroup))
-   , m_order(m_privkey.domain().get_order())
-   , m_base_point(m_privkey.domain().get_base_point(), m_order)
+   : m_group(ecgroup)
+   , m_privkey(Timing_Test::timing_test_rng(), m_group)
    , m_x(m_privkey.private_value())
-   , m_mod_order(m_order) {}
+   {}
 
 std::vector<uint8_t> ECDSA_Timing_Test::prepare_input(std::string input)
    {
@@ -274,16 +271,94 @@ std::vector<uint8_t> ECDSA_Timing_Test::prepare_input(std::string input)
 ticks ECDSA_Timing_Test::measure_critical_function(std::vector<uint8_t> input)
    {
    const Botan::BigInt k(input.data(), input.size());
-   const Botan::BigInt msg(Timing_Test::timing_test_rng(), m_order.bits());
+   const Botan::BigInt msg(5); // fixed message to minimize noise
 
    ticks start = get_ticks();
 
    //The following ECDSA operations involve and should not leak any information about k.
-   const Botan::PointGFp k_times_P = m_base_point.blinded_multiply(k, Timing_Test::timing_test_rng());
-   const Botan::BigInt r = m_mod_order.reduce(k_times_P.get_affine_x());
-   const Botan::BigInt s = m_mod_order.multiply(inverse_mod(k, m_order), mul_add(m_x, r, msg));
-   BOTAN_UNUSED(r);
-   BOTAN_UNUSED(s);
+
+   const Botan::BigInt k_inv = Botan::inverse_mod(k, m_group.get_order());
+   const Botan::PointGFp k_times_P = m_group.blinded_base_point_multiply(k, Timing_Test::timing_test_rng(), m_ws);
+   const Botan::BigInt r = m_group.mod_order(k_times_P.get_affine_x());
+   const Botan::BigInt s = m_group.multiply_mod_order(k_inv, mul_add(m_x, r, msg));
+
+   BOTAN_UNUSED(r, s);
+
+   ticks end = get_ticks();
+
+   return (end - start);
+   }
+
+#endif
+
+#if defined(BOTAN_HAS_EC_CURVE_GFP)
+
+class ECC_Mul_Timing_Test final : public Timing_Test
+   {
+   public:
+      ECC_Mul_Timing_Test(std::string ecgroup) :
+         m_group(ecgroup)
+         {}
+
+      std::vector<uint8_t> prepare_input(std::string input) override;
+      ticks measure_critical_function(std::vector<uint8_t> input) override;
+
+   private:
+      const Botan::EC_Group m_group;
+      std::vector<Botan::BigInt> m_ws;
+   };
+
+std::vector<uint8_t> ECC_Mul_Timing_Test::prepare_input(std::string input)
+   {
+   const std::vector<uint8_t> input_vector = Botan::hex_decode(input);
+   return input_vector;
+   }
+
+ticks ECC_Mul_Timing_Test::measure_critical_function(std::vector<uint8_t> input)
+   {
+   const Botan::BigInt k(input.data(), input.size());
+
+   ticks start = get_ticks();
+
+   const Botan::PointGFp k_times_P = m_group.blinded_base_point_multiply(k, Timing_Test::timing_test_rng(), m_ws);
+
+   ticks end = get_ticks();
+
+   return (end - start);
+   }
+
+#endif
+
+#if defined(BOTAN_HAS_NUMBERTHEORY)
+
+class Invmod_Timing_Test final : public Timing_Test
+   {
+   public:
+      Invmod_Timing_Test(size_t p_bits)
+         {
+         m_p = Botan::random_prime(timing_test_rng(), p_bits);
+         }
+
+      std::vector<uint8_t> prepare_input(std::string input) override;
+      ticks measure_critical_function(std::vector<uint8_t> input) override;
+
+   private:
+      Botan::BigInt m_p;
+   };
+
+std::vector<uint8_t> Invmod_Timing_Test::prepare_input(std::string input)
+   {
+   const std::vector<uint8_t> input_vector = Botan::hex_decode(input);
+   return input_vector;
+   }
+
+ticks Invmod_Timing_Test::measure_critical_function(std::vector<uint8_t> input)
+   {
+   const Botan::BigInt k(input.data(), input.size());
+
+   ticks start = get_ticks();
+
+   const Botan::BigInt inv = inverse_mod(k, m_p);
 
    ticks end = get_ticks();
 
@@ -458,6 +533,20 @@ std::unique_ptr<Timing_Test> Timing_Test_Command::lookup_timing_test(const std::
       }
 #endif
 
+#if defined(BOTAN_HAS_EC_CURVE_GFP)
+   if(test_type == "ecc_mul")
+      {
+      return std::unique_ptr<Timing_Test>(new ECC_Mul_Timing_Test("brainpool512r1"));
+      }
+#endif
+
+#if defined(BOTAN_HAS_NUMBERTHEORY)
+   if(test_type == "inverse_mod")
+      {
+      return std::unique_ptr<Timing_Test>(new Invmod_Timing_Test(512));
+      }
+#endif
+
 #if defined(BOTAN_HAS_TLS_CBC)
    if(test_type == "lucky13sha1sec3" || test_type == "lucky13sha1sec4")
       {
diff --git a/src/fuzzer/ecc_helper.h b/src/fuzzer/ecc_helper.h
index b427bc976..f3b212730 100644
--- a/src/fuzzer/ecc_helper.h
+++ b/src/fuzzer/ecc_helper.h
@@ -25,7 +25,7 @@ void check_ecc_math(const Botan::EC_Group& group,
    {
    // These depend only on the group, which is also static
    static const Botan::PointGFp base_point = group.get_base_point();
-   static Botan::Blinded_Point_Multiply blind(base_point, group.get_order(), 4);
+   static Botan::PointGFp_Blinded_Multiplier blind(base_point);
 
    const size_t hlen = len / 2;
    const Botan::BigInt a = Botan::BigInt::decode(in, hlen);
@@ -42,9 +42,9 @@ void check_ecc_math(const Botan::EC_Group& group,
 
    FUZZER_ASSERT_EQUAL(A1, A2);
 
-   const Botan::PointGFp P1 = blind.blinded_multiply(a, fuzzer_rng());
-   const Botan::PointGFp Q1 = blind.blinded_multiply(b, fuzzer_rng());
-   const Botan::PointGFp R1 = blind.blinded_multiply(c, fuzzer_rng());
+   const Botan::PointGFp P1 = blind.blinded_multiply(a, group.get_order(), fuzzer_rng());
+   const Botan::PointGFp Q1 = blind.blinded_multiply(b, group.get_order(), fuzzer_rng());
+   const Botan::PointGFp R1 = blind.blinded_multiply(c, group.get_order(), fuzzer_rng());
 
    const Botan::PointGFp S1 = P1 + Q1;
    const Botan::PointGFp S2 = Q1 + P1;
diff --git a/src/lib/math/bigint/bigint.cpp b/src/lib/math/bigint/bigint.cpp
index caa78de45..b63bd9be8 100644
--- a/src/lib/math/bigint/bigint.cpp
+++ b/src/lib/math/bigint/bigint.cpp
@@ -119,7 +119,7 @@ int32_t BigInt::cmp(const BigInt& other, bool check_signs) const
 uint32_t BigInt::get_substring(size_t offset, size_t length) const
    {
    if(length > 32)
-      throw Invalid_Argument("BigInt::get_substring: Substring size too big");
+      throw Invalid_Argument("BigInt::get_substring: Substring size " + std::to_string(length) + " too big");
 
    uint64_t piece = 0;
    for(size_t i = 0; i != 8; ++i)
diff --git a/src/lib/math/ec_gfp/point_gfp.cpp b/src/lib/math/ec_gfp/point_gfp.cpp
index f00f030d7..1489065a0 100644
--- a/src/lib/math/ec_gfp/point_gfp.cpp
+++ b/src/lib/math/ec_gfp/point_gfp.cpp
@@ -304,88 +304,6 @@ PointGFp operator*(const BigInt& scalar, const PointGFp& point)
    return R[0];
    }
 
-Blinded_Point_Multiply::Blinded_Point_Multiply(const PointGFp& base, const BigInt& order, size_t h) :
-   m_h(h > 0 ? h : 4), m_order(order), m_ws(9)
-   {
-   // Upper bound is a sanity check rather than hard limit
-   if(m_h < 1 || m_h > 8)
-      throw Invalid_Argument("Blinded_Point_Multiply invalid h param");
-
-   const CurveGFp& curve = base.get_curve();
-
-   const PointGFp inv = -base;
-
-   m_U.resize(6*m_h + 3);
-
-   m_U[3*m_h+0] = inv;
-   m_U[3*m_h+1] = PointGFp::zero_of(curve);
-   m_U[3*m_h+2] = base;
-
-   for(size_t i = 1; i <= 3 * m_h + 1; ++i)
-      {
-      m_U[3*m_h+1+i] = m_U[3*m_h+i];
-      m_U[3*m_h+1+i].add(base, m_ws);
-
-      m_U[3*m_h+1-i] = m_U[3*m_h+2-i];
-      m_U[3*m_h+1-i].add(inv, m_ws);
-      }
-   }
-
-PointGFp Blinded_Point_Multiply::blinded_multiply(const BigInt& scalar_in,
-                                                  RandomNumberGenerator& rng)
-   {
-   if(scalar_in.is_negative())
-      throw Invalid_Argument("Blinded_Point_Multiply scalar must be positive");
-
-#if BOTAN_POINTGFP_USE_SCALAR_BLINDING
-   // Choose a small mask m and use k' = k + m*order (Coron's 1st countermeasure)
-   const BigInt mask(rng, (m_order.bits()+1)/2, false);
-   const BigInt scalar = scalar_in + m_order * mask;
-#else
-   const BigInt& scalar = scalar_in;
-#endif
-
-   const size_t scalar_bits = scalar.bits();
-
-   // Randomize each point representation (Coron's 3rd countermeasure)
-   for(size_t i = 0; i != m_U.size(); ++i)
-      m_U[i].randomize_repr(rng);
-
-   PointGFp R = m_U.at(3*m_h + 2); // base point
-   int32_t alpha = 0;
-
-   R.randomize_repr(rng);
-
-   /*
-   Algorithm 7 from "Randomizing the Montgomery Powering Ladder"
-   Duc-Phong Le, Chik How Tan and Michael Tunstall
-   https://eprint.iacr.org/2015/657
-
-   It takes a random walk through (a subset of) the set of addition
-   chains that end in k.
-   */
-   for(size_t i = scalar_bits; i > 0; i--)
-      {
-      const int32_t ki = scalar.get_bit(i);
-
-      // choose gamma from -h,...,h
-      const int32_t gamma = static_cast<int32_t>((rng.next_byte() % (2*m_h))) - m_h;
-      const int32_t l = gamma - 2*alpha + ki - (ki ^ 1);
-
-      R.mult2(m_ws);
-      R.add(m_U.at(3*m_h + 1 + l), m_ws);
-      alpha = gamma;
-      }
-
-   const int32_t k0 = scalar.get_bit(0);
-   R.add(m_U[3*m_h + 1 - alpha - (k0 ^ 1)], m_ws);
-
-
-   //BOTAN_ASSERT(R.on_the_curve(), "Output is on the curve");
-
-   return R;
-   }
-
 BigInt PointGFp::get_affine_x() const
    {
    if(is_zero())
diff --git a/src/lib/math/ec_gfp/point_gfp.h b/src/lib/math/ec_gfp/point_gfp.h
index 2e1c626bd..db3e02baa 100644
--- a/src/lib/math/ec_gfp/point_gfp.h
+++ b/src/lib/math/ec_gfp/point_gfp.h
@@ -202,9 +202,20 @@ class BOTAN_PUBLIC_API(2,0) PointGFp final
       * Equality operator
       */
       bool operator==(const PointGFp& other) const;
-   private:
-      friend class Blinded_Point_Multiply;
 
+      /**
+      * Point addition
+      * @param workspace temp space, at least 11 elements
+      */
+      void add(const PointGFp& other, std::vector<BigInt>& workspace);
+
+      /**
+      * Point doubling
+      * @param workspace temp space, at least 9 elements
+      */
+      void mult2(std::vector<BigInt>& workspace);
+
+   private:
       BigInt curve_mult(const BigInt& x, const BigInt& y) const
          {
          BigInt z;
@@ -229,18 +240,6 @@ class BOTAN_PUBLIC_API(2,0) PointGFp final
          m_curve.sqr(z, x, m_monty_ws);
          }
 
-      /**
-      * Point addition
-      * @param workspace temp space, at least 11 elements
-      */
-      void add(const PointGFp& other, std::vector<BigInt>& workspace);
-
-      /**
-      * Point doubling
-      * @param workspace temp space, at least 9 elements
-      */
-      void mult2(std::vector<BigInt>& workspace);
-
       CurveGFp m_curve;
       BigInt m_coord_x, m_coord_y, m_coord_z;
       mutable secure_vector<word> m_monty_ws; // workspace for Montgomery
@@ -299,19 +298,68 @@ PointGFp OS2ECP(const std::vector<uint8_t, Alloc>& data, const CurveGFp& curve)
    { return OS2ECP(data.data(), data.size(), curve); }
 
 /**
-
+* Blinded ECC point multiplication
 */
-class BOTAN_PUBLIC_API(2,0) Blinded_Point_Multiply final
+class BOTAN_PUBLIC_API(2,5) PointGFp_Blinded_Multiplier final
    {
    public:
-      Blinded_Point_Multiply(const PointGFp& base, const BigInt& order, size_t h = 0);
+      /**
+      * @param base_point the point that will be multiplied (eg, the base point of the curve)
+      * @param w the window bits (leave as zero to take a default value)
+      */
+      PointGFp_Blinded_Multiplier(const PointGFp& base_point,
+                                  size_t w = 0);
+
+      /**
+      * @param base_point the point that will be multiplied (eg, the base point of the curve)
+      * @param ws a temporary workspace
+      * @param w the window bits (leave as zero to take a default value)
+      */
+      PointGFp_Blinded_Multiplier(const PointGFp& base_point,
+                                  std::vector<BigInt>& ws,
+                                  size_t w = 0);
 
-      PointGFp blinded_multiply(const BigInt& scalar, RandomNumberGenerator& rng);
+      /**
+      * Randomize the internal state. Changing the values may provide
+      * some protection against side channel attacks.
+      * @param rng a random number generator
+      */
+      void randomize(RandomNumberGenerator& rng);
+
+      /**
+      * Perform blinded point multiplication
+      * @param k the scalar
+      * @param group_order the order of the group
+      * @param rng a random number generator
+      * @param ws a temporary workspace
+      * @return base_point*k
+      */
+      PointGFp mul(const BigInt& k,
+                   const BigInt& group_order,
+                   RandomNumberGenerator& rng,
+                   std::vector<BigInt>& ws) const;
    private:
-      const size_t m_h;
-      const BigInt& m_order;
-      std::vector<BigInt> m_ws;
+      void init(const PointGFp& base_point, size_t w, std::vector<BigInt>& ws);
+
       std::vector<PointGFp> m_U;
+      size_t m_h;
+   };
+
+class BOTAN_PUBLIC_API(2,0) BOTAN_DEPRECATED("Use PointGFp_Blinded_Multiplier") Blinded_Point_Multiply final
+   {
+   public:
+      Blinded_Point_Multiply(const PointGFp& base, const BigInt& order, size_t h = 0) :
+         m_ws(9), m_order(order), m_point_mul(base, m_ws, h) {}
+
+      PointGFp blinded_multiply(const BigInt& scalar, RandomNumberGenerator& rng)
+         {
+         m_point_mul.randomize(rng);
+         return m_point_mul.mul(scalar, m_order, rng, m_ws);
+         }
+   private:
+      std::vector<BigInt> m_ws;
+      const BigInt& m_order;
+      PointGFp_Blinded_Multiplier m_point_mul;
    };
 
 }
diff --git a/src/lib/math/ec_gfp/point_mul.cpp b/src/lib/math/ec_gfp/point_mul.cpp
new file mode 100644
index 000000000..d87f83349
--- /dev/null
+++ b/src/lib/math/ec_gfp/point_mul.cpp
@@ -0,0 +1,175 @@
+/*
+* (C) 2015,2018 Jack Lloyd
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#include <botan/point_gfp.h>
+#include <botan/rng.h>
+#include <botan/internal/rounding.h>
+
+namespace Botan {
+
+PointGFp_Blinded_Multiplier::PointGFp_Blinded_Multiplier(const PointGFp& base,
+                                                         std::vector<BigInt>& ws,
+                                                         size_t w)
+   {
+   init(base, w, ws);
+   }
+
+PointGFp_Blinded_Multiplier::PointGFp_Blinded_Multiplier(const PointGFp& base,
+                                                         size_t w)
+   {
+   std::vector<BigInt> ws(9);
+   init(base, w, ws);
+   }
+
+#define USE_RANDOM_MONTY_WALK 0
+
+void PointGFp_Blinded_Multiplier::init(const PointGFp& base,
+                                       size_t w,
+                                       std::vector<BigInt>& ws)
+   {
+   m_h = (w == 0 ? 5 : w);
+
+   if(ws.size() < 9)
+      ws.resize(9);
+
+   // Upper bound is a sanity check rather than hard limit
+   if(m_h < 1 || m_h > 8)
+      throw Invalid_Argument("PointGFp_Blinded_Multiplier invalid w param");
+
+   const CurveGFp& curve = base.get_curve();
+
+   #if USE_RANDOM_MONTY_WALK
+   const PointGFp inv = -base;
+
+   m_U.resize(6*m_h + 3);
+
+   m_U[3*m_h+0] = inv;
+   m_U[3*m_h+1] = PointGFp::zero_of(curve);
+   m_U[3*m_h+2] = base;
+
+   for(size_t i = 1; i <= 3 * m_h + 1; ++i)
+      {
+      m_U[3*m_h+1+i] = m_U[3*m_h+i];
+      m_U[3*m_h+1+i].add(base, ws);
+
+      m_U[3*m_h+1-i] = m_U[3*m_h+2-i];
+      m_U[3*m_h+1-i].add(inv, ws);
+      }
+   #else
+
+   m_U.resize(1 << m_h);
+   m_U[0] = PointGFp::zero_of(curve);
+   m_U[1] = base;
+
+   for(size_t i = 2; i < m_U.size(); ++i)
+      {
+      m_U[i] = m_U[i-1];
+      m_U[i].add(base, ws);
+      }
+
+   #endif
+   }
+
+void PointGFp_Blinded_Multiplier::randomize(RandomNumberGenerator& rng)
+   {
+   // Randomize each point representation (Coron's 3rd countermeasure)
+   for(size_t i = 0; i != m_U.size(); ++i)
+      m_U[i].randomize_repr(rng);
+   }
+
+PointGFp PointGFp_Blinded_Multiplier::mul(const BigInt& k,
+                                          const BigInt& group_order,
+                                          RandomNumberGenerator& rng,
+                                          std::vector<BigInt>& ws) const
+   {
+   if(k.is_negative())
+      throw Invalid_Argument("PointGFp_Blinded_Multiplier scalar must be positive");
+
+#if BOTAN_POINTGFP_USE_SCALAR_BLINDING
+   // Choose a small mask m and use k' = k + m*order (Coron's 1st countermeasure)
+   const BigInt mask(rng, group_order.bits() / 4, false);
+   const BigInt scalar = k + group_order * mask;
+#else
+   const BigInt& scalar = k;
+#endif
+
+   if(ws.size() < 9)
+      ws.resize(9);
+
+   const size_t scalar_bits = scalar.bits();
+
+#if USE_RANDOM_MONTY_WALK
+   const size_t w = (m_U.size() - 3) / 6;
+
+   PointGFp R = m_U.at(3*w + 2); // base point
+   int32_t alpha = 0;
+
+   R.randomize_repr(rng);
+
+   /*
+   Algorithm 7 from "Randomizing the Montgomery Powering Ladder"
+   Duc-Phong Le, Chik How Tan and Michael Tunstall
+   https://eprint.iacr.org/2015/657
+
+   It takes a random walk through (a subset of) the set of addition
+   chains that end in k.
+   */
+   for(size_t i = scalar_bits; i > 0; i--)
+      {
+      const int32_t ki = scalar.get_bit(i);
+
+      // choose gamma from -h,...,h
+      const int32_t gamma = static_cast<int32_t>((rng.next_byte() % (2*w))) - w;
+      const int32_t l = gamma - 2*alpha + ki - (ki ^ 1);
+
+      R.mult2(ws);
+      R.add(m_U.at(3*w + 1 + l), ws);
+      alpha = gamma;
+      }
+
+   const int32_t k0 = scalar.get_bit(0);
+   R.add(m_U[3*w + 1 - alpha - (k0 ^ 1)], ws);
+
+   #else
+
+   size_t windows = round_up(scalar_bits, m_h) / m_h;
+
+   PointGFp R = m_U[0];
+
+   if(windows > 0)
+      {
+      windows--;
+      const uint32_t nibble = scalar.get_substring(windows*m_h, m_h);
+      R.add(m_U[nibble], ws);
+
+      /*
+      Randomize after adding the first nibble as before the addition R
+      is zero, and we cannot effectively randomize the point
+      representation of the zero point.
+      */
+      R.randomize_repr(rng);
+
+      while(windows)
+         {
+         for(size_t i = 0; i != m_h; ++i)
+            R.mult2(ws);
+
+         const uint32_t inner_nibble = scalar.get_substring((windows-1)*m_h, m_h);
+         // cache side channel here, we are relying on blinding...
+         R.add(m_U[inner_nibble], ws);
+         windows--;
+         }
+      }
+
+
+   #endif
+
+   //BOTAN_ASSERT(R.on_the_curve(), "Output is on the curve");
+
+   return R;
+   }
+
+}
diff --git a/src/lib/pubkey/ec_group/ec_group.cpp b/src/lib/pubkey/ec_group/ec_group.cpp
index 771bd4b0f..a41a59b66 100644
--- a/src/lib/pubkey/ec_group/ec_group.cpp
+++ b/src/lib/pubkey/ec_group/ec_group.cpp
@@ -17,6 +17,10 @@
 #include <botan/mutex.h>
 #include <vector>
 
+#if defined(BOTAN_HAS_SYSTEM_RNG)
+   #include <botan/system_rng.h>
+#endif
+
 namespace Botan {
 
 class EC_Group_Data final
@@ -36,10 +40,14 @@ class EC_Group_Data final
          m_order(order),
          m_cofactor(cofactor),
          m_mod_order(order),
+         m_base_mult(m_base_point, 5),
          m_oid(oid),
          m_p_bits(p.bits()),
          m_order_bits(order.bits())
          {
+#if defined(BOTAN_HAS_SYSTEM_RNG)
+         m_base_mult.randomize(system_rng());
+#endif
          }
 
       bool match(const BigInt& p, const BigInt& a, const BigInt& b,
@@ -76,12 +84,20 @@ class EC_Group_Data final
          return m_mod_order.multiply(x, y);
          }
 
+      PointGFp blinded_base_point_multiply(const BigInt& k,
+                                           RandomNumberGenerator& rng,
+                                           std::vector<BigInt>& ws) const
+         {
+         return m_base_mult.mul(k, m_order, rng, ws);
+         }
+
    private:
       CurveGFp m_curve;
       PointGFp m_base_point;
       BigInt m_order;
       BigInt m_cofactor;
       Modular_Reducer m_mod_order;
+      PointGFp_Blinded_Multiplier m_base_mult;
       OID m_oid;
       size_t m_p_bits;
       size_t m_order_bits;
@@ -429,6 +445,13 @@ PointGFp EC_Group::point_multiply(const BigInt& x, const PointGFp& pt, const Big
    return multi_exponentiate(get_base_point(), x, pt, y);
    }
 
+PointGFp EC_Group::blinded_base_point_multiply(const BigInt& k,
+                                               RandomNumberGenerator& rng,
+                                               std::vector<BigInt>& ws) const
+   {
+   return data().blinded_base_point_multiply(k, rng, ws);
+   }
+
 PointGFp EC_Group::zero_point() const
    {
    return PointGFp(data().curve());
diff --git a/src/lib/pubkey/ec_group/ec_group.h b/src/lib/pubkey/ec_group/ec_group.h
index a60c71157..0e5f352f2 100644
--- a/src/lib/pubkey/ec_group/ec_group.h
+++ b/src/lib/pubkey/ec_group/ec_group.h
@@ -206,12 +206,21 @@ class BOTAN_PUBLIC_API(2,0) EC_Group final
       PointGFp point(const BigInt& x, const BigInt& y) const;
 
       /**
-      * Multi exponentiate
+      * Multi exponentiate. Not constant time.
       * @return base_point*x + pt*y
       */
       PointGFp point_multiply(const BigInt& x, const PointGFp& pt, const BigInt& y) const;
 
       /**
+      * Blinded point multiplication, attempts resistance to side channels
+      * @param k the scalar
+      * @param rng a random number generator
+      * @param ws a temp workspace
+      * @return base_point*k
+      */
+      PointGFp blinded_base_point_multiply(const BigInt& k, RandomNumberGenerator& rng, std::vector<BigInt>& ws) const;
+
+      /**
       * Return the zero (or infinite) point on this curve
       */
       PointGFp zero_point() const;
diff --git a/src/lib/pubkey/ecdh/ecdh.cpp b/src/lib/pubkey/ecdh/ecdh.cpp
index 1850696e1..4989fa0a5 100644
--- a/src/lib/pubkey/ecdh/ecdh.cpp
+++ b/src/lib/pubkey/ecdh/ecdh.cpp
@@ -28,26 +28,30 @@ class ECDH_KA_Operation final : public PK_Ops::Key_Agreement_with_KDF
 
       ECDH_KA_Operation(const ECDH_PrivateKey& key, const std::string& kdf, RandomNumberGenerator& rng) :
          PK_Ops::Key_Agreement_with_KDF(kdf),
-         m_domain(key.domain()),
+         m_group(key.domain()),
          m_rng(rng)
          {
-         m_l_times_priv = inverse_mod(m_domain.get_cofactor(), m_domain.get_order()) * key.private_value();
+         m_l_times_priv = inverse_mod(m_group.get_cofactor(), m_group.get_order()) * key.private_value();
          }
 
       secure_vector<uint8_t> raw_agree(const uint8_t w[], size_t w_len) override
          {
-         PointGFp point = m_domain.OS2ECP(w, w_len);
-         PointGFp S = m_domain.get_cofactor() * point;
-         Blinded_Point_Multiply blinder(S, m_domain.get_order());
-         S = blinder.blinded_multiply(m_l_times_priv, m_rng);
-         BOTAN_ASSERT(S.on_the_curve(), "ECDH agreed value was on the curve");
-         return BigInt::encode_1363(S.get_affine_x(), m_domain.get_p_bytes());
+         PointGFp input_point = m_group.get_cofactor() * m_group.OS2ECP(w, w_len);
+         input_point.randomize_repr(m_rng);
+
+         PointGFp_Blinded_Multiplier blinder(input_point, m_ws);
+
+         const PointGFp S = blinder.mul(m_l_times_priv, m_group.get_order(), m_rng, m_ws);
+
+         if(S.on_the_curve() == false)
+            throw Internal_Error("ECDH agreed value was not on the curve");
+         return BigInt::encode_1363(S.get_affine_x(), m_group.get_p_bytes());
          }
    private:
-      const EC_Group& m_domain;
+      const EC_Group m_group;
       BigInt m_l_times_priv;
       RandomNumberGenerator& m_rng;
-
+      std::vector<BigInt> m_ws;
    };
 
 }
diff --git a/src/lib/pubkey/ecdsa/ecdsa.cpp b/src/lib/pubkey/ecdsa/ecdsa.cpp
index 12ccd9608..57bc197c5 100644
--- a/src/lib/pubkey/ecdsa/ecdsa.cpp
+++ b/src/lib/pubkey/ecdsa/ecdsa.cpp
@@ -53,7 +53,6 @@ class ECDSA_Signature_Operation final : public PK_Ops::Signature_with_EMSA
                                 const std::string& emsa) :
          PK_Ops::Signature_with_EMSA(emsa),
          m_group(ecdsa.domain()),
-         m_base_point(m_group.get_base_point(), m_group.get_order()),
          m_x(ecdsa.private_value())
          {
 #if defined(BOTAN_HAS_RFC6979_GENERATOR)
@@ -68,12 +67,13 @@ class ECDSA_Signature_Operation final : public PK_Ops::Signature_with_EMSA
 
    private:
       const EC_Group m_group;
-      Blinded_Point_Multiply m_base_point;
       const BigInt& m_x;
 
 #if defined(BOTAN_HAS_RFC6979_GENERATOR)
       std::string m_rfc6979_hash;
 #endif
+
+      std::vector<BigInt> m_ws;
    };
 
 secure_vector<uint8_t>
@@ -89,7 +89,7 @@ ECDSA_Signature_Operation::raw_sign(const uint8_t msg[], size_t msg_len,
 #endif
 
    const BigInt k_inv = inverse_mod(k, m_group.get_order());
-   const PointGFp k_times_P = m_base_point.blinded_multiply(k, rng);
+   const PointGFp k_times_P = m_group.blinded_base_point_multiply(k, rng, m_ws);
    const BigInt r = m_group.mod_order(k_times_P.get_affine_x());
    const BigInt s = m_group.multiply_mod_order(k_inv, mul_add(m_x, r, m));
 
diff --git a/src/lib/pubkey/ecgdsa/ecgdsa.cpp b/src/lib/pubkey/ecgdsa/ecgdsa.cpp
index f8e5744d9..6cbd3453b 100644
--- a/src/lib/pubkey/ecgdsa/ecgdsa.cpp
+++ b/src/lib/pubkey/ecgdsa/ecgdsa.cpp
@@ -38,7 +38,6 @@ class ECGDSA_Signature_Operation final : public PK_Ops::Signature_with_EMSA
                                 const std::string& emsa) :
          PK_Ops::Signature_with_EMSA(emsa),
          m_group(ecgdsa.domain()),
-         m_base_point(m_group.get_base_point(), m_group.get_order()),
          m_x(ecgdsa.private_value())
          {
          }
@@ -50,8 +49,8 @@ class ECGDSA_Signature_Operation final : public PK_Ops::Signature_with_EMSA
 
    private:
       const EC_Group m_group;
-      Blinded_Point_Multiply m_base_point;
       const BigInt& m_x;
+      std::vector<BigInt> m_ws;
    };
 
 secure_vector<uint8_t>
@@ -62,7 +61,7 @@ ECGDSA_Signature_Operation::raw_sign(const uint8_t msg[], size_t msg_len,
 
    BigInt k = BigInt::random_integer(rng, 1, m_group.get_order());
 
-   const PointGFp k_times_P = m_base_point.blinded_multiply(k, rng);
+   const PointGFp k_times_P = m_group.blinded_base_point_multiply(k, rng, m_ws);
    const BigInt r = m_group.mod_order(k_times_P.get_affine_x());
    const BigInt s = m_group.multiply_mod_order(m_x, mul_sub(k, r, m));
 
diff --git a/src/lib/pubkey/ecies/ecies.cpp b/src/lib/pubkey/ecies/ecies.cpp
index cd09b4c52..1120a850a 100644
--- a/src/lib/pubkey/ecies/ecies.cpp
+++ b/src/lib/pubkey/ecies/ecies.cpp
@@ -66,16 +66,24 @@ class ECIES_ECDH_KA_Operation final : public PK_Ops::Key_Agreement_with_KDF
 
       secure_vector<uint8_t> raw_agree(const uint8_t w[], size_t w_len) override
          {
-         PointGFp point = m_key.domain().OS2ECP(w, w_len);
-         Blinded_Point_Multiply blinder(point, m_key.domain().get_order());
-         PointGFp S = blinder.blinded_multiply(m_key.private_value(), m_rng);
-         BOTAN_ASSERT(S.on_the_curve(), "ECDH agreed value was on the curve");
-         return BigInt::encode_1363(S.get_affine_x(), m_key.domain().get_p_bytes());
+         const EC_Group& group = m_key.domain();
+
+         PointGFp input_point = group.OS2ECP(w, w_len);
+         input_point.randomize_repr(m_rng);
+
+         PointGFp_Blinded_Multiplier blinder(input_point, m_ws);
+
+         const PointGFp S = blinder.mul(m_key.private_value(), group.get_order(), m_rng, m_ws);
+
+         if(S.on_the_curve() == false)
+            throw Internal_Error("ECDH agreed value was not on the curve");
+         return BigInt::encode_1363(S.get_affine_x(), group.get_p_bytes());
          }
 
    private:
       ECIES_PrivateKey m_key;
       RandomNumberGenerator& m_rng;
+      std::vector<BigInt> m_ws;
    };
 
 std::unique_ptr<PK_Ops::Key_Agreement>
diff --git a/src/lib/pubkey/eckcdsa/eckcdsa.cpp b/src/lib/pubkey/eckcdsa/eckcdsa.cpp
index 743d5ab95..be721a6b6 100644
--- a/src/lib/pubkey/eckcdsa/eckcdsa.cpp
+++ b/src/lib/pubkey/eckcdsa/eckcdsa.cpp
@@ -45,7 +45,6 @@ class ECKCDSA_Signature_Operation final : public PK_Ops::Signature_with_EMSA
                                 const std::string& emsa) :
          PK_Ops::Signature_with_EMSA(emsa),
          m_group(eckcdsa.domain()),
-         m_base_point(m_group.get_base_point(), m_group.get_order()),
          m_x(eckcdsa.private_value()),
          m_prefix()
          {
@@ -68,9 +67,9 @@ class ECKCDSA_Signature_Operation final : public PK_Ops::Signature_with_EMSA
 
    private:
       const EC_Group m_group;
-      Blinded_Point_Multiply m_base_point;
       const BigInt& m_x;
       secure_vector<uint8_t> m_prefix;
+      std::vector<BigInt> m_ws;
    };
 
 secure_vector<uint8_t>
@@ -78,7 +77,7 @@ ECKCDSA_Signature_Operation::raw_sign(const uint8_t msg[], size_t,
                                      RandomNumberGenerator& rng)
    {
    const BigInt k = BigInt::random_integer(rng, 1, m_group.get_order());
-   const PointGFp k_times_P = m_base_point.blinded_multiply(k, rng);
+   const PointGFp k_times_P = m_group.blinded_base_point_multiply(k, rng, m_ws);
    const BigInt k_times_P_x = k_times_P.get_affine_x();
 
    secure_vector<uint8_t> to_be_hashed(k_times_P_x.bytes());
diff --git a/src/lib/pubkey/gost_3410/gost_3410.cpp b/src/lib/pubkey/gost_3410/gost_3410.cpp
index 760e667aa..79d3f204d 100644
--- a/src/lib/pubkey/gost_3410/gost_3410.cpp
+++ b/src/lib/pubkey/gost_3410/gost_3410.cpp
@@ -101,7 +101,6 @@ class GOST_3410_Signature_Operation final : public PK_Ops::Signature_with_EMSA
                                     const std::string& emsa) :
          PK_Ops::Signature_with_EMSA(emsa),
          m_group(gost_3410.domain()),
-         m_base_point(m_group.get_base_point(), m_group.get_order()),
          m_x(gost_3410.private_value())
          {}
 
@@ -112,8 +111,8 @@ class GOST_3410_Signature_Operation final : public PK_Ops::Signature_with_EMSA
 
    private:
       const EC_Group m_group;
-      Blinded_Point_Multiply m_base_point;
       const BigInt& m_x;
+      std::vector<BigInt> m_ws;
    };
 
 secure_vector<uint8_t>
@@ -133,7 +132,7 @@ GOST_3410_Signature_Operation::raw_sign(const uint8_t msg[], size_t msg_len,
    if(e == 0)
       e = 1;
 
-   const PointGFp k_times_P = m_base_point.blinded_multiply(k, rng);
+   const PointGFp k_times_P = m_group.blinded_base_point_multiply(k, rng, m_ws);
    BOTAN_ASSERT(k_times_P.on_the_curve(), "GOST 34.10 k*g is on the curve");
 
    const BigInt r = m_group.mod_order(k_times_P.get_affine_x());
diff --git a/src/lib/pubkey/sm2/sm2.cpp b/src/lib/pubkey/sm2/sm2.cpp
index 2af888bbc..9ef30d9bf 100644
--- a/src/lib/pubkey/sm2/sm2.cpp
+++ b/src/lib/pubkey/sm2/sm2.cpp
@@ -83,7 +83,6 @@ class SM2_Signature_Operation final : public PK_Ops::Signature
                               const std::string& ident,
                               const std::string& hash) :
          m_group(sm2.domain()),
-         m_base_point(m_group.get_base_point(), m_group.get_order()),
          m_x(sm2.private_value()),
          m_da_inv(sm2.get_da_inv()),
          m_hash(HashFunction::create_or_throw(hash))
@@ -102,12 +101,12 @@ class SM2_Signature_Operation final : public PK_Ops::Signature
 
    private:
       const EC_Group m_group;
-      Blinded_Point_Multiply m_base_point;
       const BigInt& m_x;
       const BigInt& m_da_inv;
 
       std::vector<uint8_t> m_za;
       std::unique_ptr<HashFunction> m_hash;
+      std::vector<BigInt> m_ws;
    };
 
 secure_vector<uint8_t>
@@ -115,7 +114,7 @@ SM2_Signature_Operation::sign(RandomNumberGenerator& rng)
    {
    const BigInt k = BigInt::random_integer(rng, 1, m_group.get_order());
 
-   const PointGFp k_times_P = m_base_point.blinded_multiply(k, rng);
+   const PointGFp k_times_P = m_group.blinded_base_point_multiply(k, rng, m_ws);
 
    const BigInt e = BigInt::decode(m_hash->final());
    const BigInt r = m_group.mod_order(k_times_P.get_affine_x() + e);
diff --git a/src/lib/pubkey/sm2/sm2_enc.cpp b/src/lib/pubkey/sm2/sm2_enc.cpp
index 462c4b968..b0d773635 100644
--- a/src/lib/pubkey/sm2/sm2_enc.cpp
+++ b/src/lib/pubkey/sm2/sm2_enc.cpp
@@ -47,8 +47,7 @@ class SM2_Encryption_Operation final : public PK_Ops::Encryption
    public:
       SM2_Encryption_Operation(const SM2_Encryption_PublicKey& key, const std::string& kdf_hash) :
          m_group(key.domain()),
-         m_base_point(m_group.get_base_point(), m_group.get_order()),
-         m_public_point(key.public_point(), m_group.get_order()),
+         m_mul_public_point(key.public_point()),
          m_kdf_hash(kdf_hash)
          {}
 
@@ -69,7 +68,7 @@ class SM2_Encryption_Operation final : public PK_Ops::Encryption
 
          const BigInt k = BigInt::random_integer(rng, 1, m_group.get_order());
 
-         const PointGFp C1 = m_base_point.blinded_multiply(k, rng);
+         const PointGFp C1 = m_group.blinded_base_point_multiply(k, rng, m_ws);
          const BigInt x1 = C1.get_affine_x();
          const BigInt y1 = C1.get_affine_y();
          std::vector<uint8_t> x1_bytes(p_bytes);
@@ -77,7 +76,7 @@ class SM2_Encryption_Operation final : public PK_Ops::Encryption
          BigInt::encode_1363(x1_bytes.data(), x1_bytes.size(), x1);
          BigInt::encode_1363(y1_bytes.data(), y1_bytes.size(), y1);
 
-         const PointGFp kPB = m_public_point.blinded_multiply(k, rng);
+         const PointGFp kPB = m_mul_public_point.mul(k, m_group.get_order(), rng, m_ws);
 
          const BigInt x2 = kPB.get_affine_x();
          const BigInt y2 = kPB.get_affine_y();
@@ -114,9 +113,9 @@ class SM2_Encryption_Operation final : public PK_Ops::Encryption
 
    private:
       const EC_Group m_group;
-      Blinded_Point_Multiply m_base_point;
-      Blinded_Point_Multiply m_public_point;
+      PointGFp_Blinded_Multiplier m_mul_public_point;
       const std::string m_kdf_hash;
+      std::vector<BigInt> m_ws;
    };
 
 class SM2_Decryption_Operation final : public PK_Ops::Decryption
@@ -134,8 +133,9 @@ class SM2_Decryption_Operation final : public PK_Ops::Decryption
                                      const uint8_t ciphertext[],
                                      size_t ciphertext_len) override
          {
-         const BigInt& cofactor = m_key.domain().get_cofactor();
-         const size_t p_bytes = m_key.domain().get_p_bytes();
+         const EC_Group& group = m_key.domain();
+         const BigInt& cofactor = group.get_cofactor();
+         const size_t p_bytes = group.get_p_bytes();
 
          valid_mask = 0x00;
 
@@ -160,18 +160,20 @@ class SM2_Decryption_Operation final : public PK_Ops::Decryption
             .end_cons()
             .verify_end();
 
-         const PointGFp C1 = m_key.domain().point(x1, y1);
+         PointGFp C1 = group.point(x1, y1);
          if(!C1.on_the_curve())
             return secure_vector<uint8_t>();
 
-         Blinded_Point_Multiply C1_mul(C1, m_key.domain().get_order());
-
-         if(cofactor > 1 && C1_mul.blinded_multiply(cofactor, m_rng).is_zero())
+         if(cofactor > 1 && (C1 * cofactor).is_zero())
             {
             return secure_vector<uint8_t>();
             }
 
-         const PointGFp dbC1 = C1_mul.blinded_multiply(m_key.private_value(), m_rng);
+         C1.randomize_repr(m_rng);
+
+         PointGFp_Blinded_Multiplier C1_mul(C1);
+
+         const PointGFp dbC1 = C1_mul.mul(m_key.private_value(), group.get_order(), m_rng, m_ws);
 
          const BigInt x2 = dbC1.get_affine_x();
          const BigInt y2 = dbC1.get_affine_y();
@@ -205,6 +207,7 @@ class SM2_Decryption_Operation final : public PK_Ops::Decryption
       const SM2_Encryption_PrivateKey& m_key;
       RandomNumberGenerator& m_rng;
       const std::string m_kdf_hash;
+      std::vector<BigInt> m_ws;
    };
 
 }
diff --git a/src/tests/data/timing/ecc_mul.vec b/src/tests/data/timing/ecc_mul.vec
new file mode 100644
index 000000000..fc703efbf
--- /dev/null
+++ b/src/tests/data/timing/ecc_mul.vec
@@ -0,0 +1,4 @@
+# leading zeros
+01
+# no leading zeros
+FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
diff --git a/src/tests/data/timing/inverse_mod.vec b/src/tests/data/timing/inverse_mod.vec
new file mode 100644
index 000000000..5ecd03f7b
--- /dev/null
+++ b/src/tests/data/timing/inverse_mod.vec
@@ -0,0 +1,2 @@
+02
+FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF