aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--doc/manual/side_channels.rst6
-rw-r--r--src/lib/pubkey/blinding.h2
-rw-r--r--src/lib/pubkey/rsa/rsa.cpp76
-rw-r--r--src/tests/test_rsa.cpp13
4 files changed, 68 insertions, 29 deletions
diff --git a/doc/manual/side_channels.rst b/doc/manual/side_channels.rst
index 6d6bd74bb..cf5f26003 100644
--- a/doc/manual/side_channels.rst
+++ b/doc/manual/side_channels.rst
@@ -13,13 +13,17 @@ RSA
----------------------
Blinding is always used to protect private key operations (there is no way to
-turn it off). As an optimization, instead of choosing a new random mask and
+turn it off). Both base blinding and exponent blinding are used.
+
+For base blinding, as an optimization, instead of choosing a new random mask and
inverse with each decryption, both the mask and its inverse are simply squared
to choose the next blinding factor. This is much faster than computing a fresh
value each time, and the additional relation is thought to provide only minimal
useful information for an attacker. Every BOTAN_BLINDING_REINIT_INTERVAL
(default 32) operations, a new starting point is chosen.
+Exponent blinding uses new values for each signature.
+
RSA signing uses the CRT optimization, which is much faster but vulnerable to
trivial fault attacks [RsaFault] which can result in the key being entirely
compromised. To protect against this (or any other computational error which
diff --git a/src/lib/pubkey/blinding.h b/src/lib/pubkey/blinding.h
index 1c3fb1444..1bdd235f0 100644
--- a/src/lib/pubkey/blinding.h
+++ b/src/lib/pubkey/blinding.h
@@ -58,6 +58,8 @@ class BOTAN_PUBLIC_API(2,0) Blinder final
Blinder& operator=(const Blinder&) = delete;
+ RandomNumberGenerator& rng() const { return m_rng; }
+
private:
BigInt blinding_nonce() const;
diff --git a/src/lib/pubkey/rsa/rsa.cpp b/src/lib/pubkey/rsa/rsa.cpp
index aa315aabf..fd95f187f 100644
--- a/src/lib/pubkey/rsa/rsa.cpp
+++ b/src/lib/pubkey/rsa/rsa.cpp
@@ -1,6 +1,6 @@
/*
* RSA
-* (C) 1999-2010,2015,2016 Jack Lloyd
+* (C) 1999-2010,2015,2016,2018 Jack Lloyd
*
* Botan is released under the Simplified BSD License (see license.txt)
*/
@@ -14,6 +14,8 @@
#include <botan/der_enc.h>
#include <botan/ber_dec.h>
#include <botan/pow_mod.h>
+#include <botan/monty.h>
+#include <botan/internal/monty_exp.h>
#if defined(BOTAN_HAS_OPENSSL)
#include <botan/internal/openssl.h>
@@ -191,26 +193,27 @@ namespace {
class RSA_Private_Operation
{
protected:
- size_t get_max_input_bits() const { return (m_n.bits() - 1); }
+ size_t get_max_input_bits() const { return (m_mod_bits - 1); }
explicit RSA_Private_Operation(const RSA_PrivateKey& rsa, RandomNumberGenerator& rng) :
- m_n(rsa.get_n()),
- m_q(rsa.get_q()),
- m_c(rsa.get_c()),
- m_powermod_e_n(rsa.get_e(), rsa.get_n()),
- m_powermod_d1_p(rsa.get_d1(), rsa.get_p()),
- m_powermod_d2_q(rsa.get_d2(), rsa.get_q()),
- m_mod_p(rsa.get_p()),
- m_blinder(m_n,
+ m_key(rsa),
+ m_mod_p(m_key.get_p()),
+ m_mod_q(m_key.get_q()),
+ m_monty_p(std::make_shared<Montgomery_Params>(m_key.get_p(), m_mod_p)),
+ m_monty_q(std::make_shared<Montgomery_Params>(m_key.get_q(), m_mod_q)),
+ m_powermod_e_n(m_key.get_e(), m_key.get_n()),
+ m_blinder(m_key.get_n(),
rng,
[this](const BigInt& k) { return m_powermod_e_n(k); },
- [this](const BigInt& k) { return inverse_mod(k, m_n); })
+ [this](const BigInt& k) { return inverse_mod(k, m_key.get_n()); }),
+ m_mod_bytes(m_key.get_n().bytes()),
+ m_mod_bits(m_key.get_n().bits())
{
}
BigInt blinded_private_op(const BigInt& m) const
{
- if(m >= m_n)
+ if(m >= m_key.get_n())
throw Invalid_Argument("RSA private op - input is too large");
return m_blinder.unblind(private_op(m_blinder.blind(m)));
@@ -218,26 +221,49 @@ 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 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));
+
#if defined(BOTAN_TARGET_OS_HAS_THREADS)
- auto future_j1 = std::async(std::launch::async, std::ref(m_powermod_d1_p), m);
- BigInt j2 = m_powermod_d2_q(m);
+ 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);
+ });
+
+ auto powm_d2_q = monty_precompute(m_monty_q, m, powm_window);
+ BigInt j2 = monty_execute(*powm_d2_q, masked_d2);
BigInt j1 = future_j1.get();
#else
- BigInt j1 = m_powermod_d1_p(m);
- BigInt j2 = m_powermod_d2_q(m);
+ 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);
#endif
- j1 = m_mod_p.reduce(sub_mul(j1, j2, m_c));
+ j1 = m_mod_p.reduce(sub_mul(j1, j2, m_key.get_c()));
- return mul_add(j1, m_q, j2);
+ return mul_add(j1, m_key.get_q(), j2);
}
- const BigInt& m_n;
- const BigInt& m_q;
- const BigInt& m_c;
- Fixed_Exponent_Power_Mod m_powermod_e_n, m_powermod_d1_p, m_powermod_d2_q;
+ const RSA_PrivateKey& m_key;
+
+ // TODO these could all be computed once and stored in the key object
Modular_Reducer m_mod_p;
+ Modular_Reducer m_mod_q;
+ std::shared_ptr<const Montgomery_Params> m_monty_p;
+ std::shared_ptr<const Montgomery_Params> m_monty_q;
+
+ Fixed_Exponent_Power_Mod m_powermod_e_n;
Blinder m_blinder;
+ size_t m_mod_bytes;
+ size_t m_mod_bits;
};
class RSA_Signature_Operation final : public PK_Ops::Signature_with_EMSA,
@@ -260,7 +286,7 @@ class RSA_Signature_Operation final : public PK_Ops::Signature_with_EMSA,
const BigInt x = blinded_private_op(m);
const BigInt c = m_powermod_e_n(x);
BOTAN_ASSERT(m == c, "RSA sign consistency check");
- return BigInt::encode_1363(x, m_n.bytes());
+ return BigInt::encode_1363(x, m_mod_bytes);
}
};
@@ -281,7 +307,7 @@ class RSA_Decryption_Operation final : public PK_Ops::Decryption_with_EME,
const BigInt x = blinded_private_op(m);
const BigInt c = m_powermod_e_n(x);
BOTAN_ASSERT(m == c, "RSA decrypt consistency check");
- return BigInt::encode_1363(x, m_n.bytes());
+ return BigInt::encode_1363(x, m_mod_bytes);
}
};
@@ -304,7 +330,7 @@ class RSA_KEM_Decryption_Operation final : public PK_Ops::KEM_Decryption_with_KD
const BigInt x = blinded_private_op(m);
const BigInt c = m_powermod_e_n(x);
BOTAN_ASSERT(m == c, "RSA KEM consistency check");
- return BigInt::encode_1363(x, m_n.bytes());
+ return BigInt::encode_1363(x, m_mod_bytes);
}
};
diff --git a/src/tests/test_rsa.cpp b/src/tests/test_rsa.cpp
index 652d5cafd..88c086812 100644
--- a/src/tests/test_rsa.cpp
+++ b/src/tests/test_rsa.cpp
@@ -288,9 +288,16 @@ class RSA_Blinding_Tests final : public Test
Botan::PK_Encryptor_EME encryptor(rsa, Test::rng(), "Raw"); // don't try this at home
- // test blinding reinit interval
- // Seed Fixed_Output_RNG only with enough bytes for the initial blinder initialization
- Botan_Tests::Fixed_Output_RNG fixed_rng(Botan::unlock(Test::rng().random_vec(rsa.get_n().bytes())));
+ /*
+ Test blinding reinit interval
+
+ Seed Fixed_Output_RNG only with enough bytes for the initial
+ blinder initialization plus the exponent blinding bits which
+ is 2*64 bits per operation.
+ */
+ const size_t rng_bytes = rsa.get_n().bytes() + (2*8*BOTAN_BLINDING_REINIT_INTERVAL);
+
+ Botan_Tests::Fixed_Output_RNG fixed_rng(Botan::unlock(Test::rng().random_vec(rng_bytes)));
Botan::PK_Decryptor_EME decryptor(rsa, fixed_rng, "Raw", "base");
for(size_t i = 1; i <= BOTAN_BLINDING_REINIT_INTERVAL ; ++i)
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-22 10:26:57 +0000