aboutsummaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-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
-rw-r--r--src/lib/misc/srp6/srp6.cpp15
-rw-r--r--src/lib/pubkey/dh/dh.cpp24
-rw-r--r--src/lib/pubkey/dl_group/dl_group.cpp26
-rw-r--r--src/lib/pubkey/dl_group/dl_group.h21
-rw-r--r--src/lib/pubkey/dsa/dsa.cpp8
-rw-r--r--src/lib/pubkey/elgamal/elgamal.cpp14
-rw-r--r--src/lib/pubkey/rsa/rsa.cpp27
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,
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-22 10:49:14 +0000