diff options
author | Jack Lloyd <[email protected]> | 2018-06-17 11:02:32 -0400 |
---|---|---|
committer | Jack Lloyd <[email protected]> | 2018-06-17 11:16:46 -0400 |
commit | f8afec45c659c870a3930a8e1b9cf26d6f0760d5 (patch) | |
tree | ff14ed9be67c649ba1b08b787e7530ed096b4c5f /src/lib/math | |
parent | b434f6a7518b65fbe5eb1b8e042d2daf10d03671 (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.cpp | 18 | ||||
-rw-r--r-- | src/lib/math/numbertheory/monty_exp.h | 7 | ||||
-rw-r--r-- | src/lib/math/numbertheory/numthry.cpp | 3 | ||||
-rw-r--r-- | src/lib/math/numbertheory/powm_mnt.cpp | 7 |
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, |