aboutsummaryrefslogtreecommitdiffstats
path: root/src/lib/math
diff options
context:
space:
mode:
authorJack Lloyd <[email protected]>2018-06-17 11:02:32 -0400
committerJack Lloyd <[email protected]>2018-06-17 11:16:46 -0400
commitf8afec45c659c870a3930a8e1b9cf26d6f0760d5 (patch)
treeff14ed9be67c649ba1b08b787e7530ed096b4c5f /src/lib/math
parentb434f6a7518b65fbe5eb1b8e042d2daf10d03671 (diff)
Avoid leaking size of exponent
See #1606 for discussion
Diffstat (limited to 'src/lib/math')
-rw-r--r--src/lib/math/numbertheory/monty_exp.cpp18
-rw-r--r--src/lib/math/numbertheory/monty_exp.h7
-rw-r--r--src/lib/math/numbertheory/numthry.cpp3
-rw-r--r--src/lib/math/numbertheory/powm_mnt.cpp7
4 files changed, 22 insertions, 13 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,