aboutsummaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/cli/speed.cpp7
-rw-r--r--src/cli/timing_tests.cpp119
-rw-r--r--src/fuzzer/ecc_helper.h8
-rw-r--r--src/lib/math/bigint/bigint.cpp2
-rw-r--r--src/lib/math/ec_gfp/point_gfp.cpp82
-rw-r--r--src/lib/math/ec_gfp/point_gfp.h90
-rw-r--r--src/lib/math/ec_gfp/point_mul.cpp175
-rw-r--r--src/lib/pubkey/ec_group/ec_group.cpp23
-rw-r--r--src/lib/pubkey/ec_group/ec_group.h11
-rw-r--r--src/lib/pubkey/ecdh/ecdh.cpp24
-rw-r--r--src/lib/pubkey/ecdsa/ecdsa.cpp6
-rw-r--r--src/lib/pubkey/ecgdsa/ecgdsa.cpp5
-rw-r--r--src/lib/pubkey/ecies/ecies.cpp18
-rw-r--r--src/lib/pubkey/eckcdsa/eckcdsa.cpp5
-rw-r--r--src/lib/pubkey/gost_3410/gost_3410.cpp5
-rw-r--r--src/lib/pubkey/sm2/sm2.cpp5
-rw-r--r--src/lib/pubkey/sm2/sm2_enc.cpp29
-rw-r--r--src/tests/data/timing/ecc_mul.vec4
-rw-r--r--src/tests/data/timing/inverse_mod.vec2
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
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-14 16:07:40 +0000