aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--doc/manual/side_channels.rst64
-rw-r--r--src/lib/math/bigint/bigint.cpp1
-rw-r--r--src/lib/math/numbertheory/nistp_redc.cpp18
-rw-r--r--src/lib/math/numbertheory/reducer.cpp33
-rw-r--r--src/lib/pubkey/dsa/dsa.cpp3
-rw-r--r--src/lib/pubkey/rsa/rsa.cpp10
-rw-r--r--src/lib/pubkey/sm2/sm2.cpp2
7 files changed, 79 insertions, 52 deletions
diff --git a/doc/manual/side_channels.rst b/doc/manual/side_channels.rst
index 32be498e7..8f8067004 100644
--- a/doc/manual/side_channels.rst
+++ b/doc/manual/side_channels.rst
@@ -9,6 +9,34 @@ obviously all open for future improvement.
The following text assumes the reader is already familiar with cryptographic
implementations, side channel attacks, and common countermeasures.
+Modular Exponentiation
+------------------------
+
+Modular exponentiation uses a fixed window algorithm with Montgomery
+representation. A side channel silent table lookup is used to access the
+precomputed powers. The caller provides the maximum possible bit length of the
+exponent, and the exponent is zero-padded as required. For example, in a DSA
+signature with 256-bit q, the caller will specify a maximum length of exponent
+of 256 bits, even if the k that was generated was 250 bits. This avoids leaking
+the length of the exponent through the number of loop iterations.
+See monty_exp.cpp and monty.cpp
+
+Karatsuba multiplication algorithm avoids any conditional branches; in
+cases where different operations must be performed it instead uses masked
+operations. See mp_karat.cpp for details.
+
+The Montgomery reduction is written to run in constant time.
+The final reduction is handled with a masked subtraction. See mp_monty.cpp.
+
+Barrett Reduction
+--------------------
+
+The Barrett reduction code is written to avoid input dependent branches. The
+Barrett algorithm only works for inputs that are most the square of the modulus;
+larger values fall back on a different (slower) division algorithm. This
+algorithm is also const time, but the branch allows detecting when a value
+larger than the square of the modulus was reduced.
+
RSA
----------------------
@@ -105,33 +133,6 @@ coming from the length of the RSA key (which is public information).
See eme_oaep.cpp.
-Modular Exponentiation
-------------------------
-
-Modular exponentiation uses a fixed window algorithm with Montgomery
-representation. A side channel silent table lookup is used to access the
-precomputed powers. The caller provides the maximum possible bit length of the
-exponent, and the exponent is zero-padded as required. For example, in a DSA
-signature with 256-bit q, the caller will specify a maximum length of exponent
-of 256 bits, even if the k that was generated was 250 bits. This avoids leaking
-the length of the exponent through the number of loop iterations.
-See monty_exp.cpp and monty.cpp
-
-Karatsuba multiplication algorithm avoids any conditional branches; in
-cases where different operations must be performed it instead uses masked
-operations. See mp_karat.cpp for details.
-
-The Montgomery reduction is written (and tested) to run in constant time.
-The final reduction is handled with a masked subtraction. See mp_monty.cpp.
-
-Barrett Reduction
---------------------
-
-The Barrett reduction code is written to avoid input dependent branches.
-However the Barrett algorithm only works for inputs that are most the
-square of the modulus; larger values fall back to the schoolbook
-division algorithm which is not const time.
-
ECC point decoding
----------------------
@@ -170,9 +171,12 @@ The base point multiplication algorithm is a comb-like technique which
precomputes ``P^i,(2*P)^i,(3*P)^i`` for all ``i`` in the range of valid scalars.
This means the scalar multiplication involves only point additions and no
doublings, which may help against attacks which rely on distinguishing between
-point doublings and point additions. The elements of the table are accessed
-by masked lookups, so as not to leak information about bits of the scalar
-via a cache side channel.
+point doublings and point additions. The elements of the table are accessed by
+masked lookups, so as not to leak information about bits of the scalar via a
+cache side channel. However, whenever 3 sequential bits of the scalar are all 0,
+no operation is performed in that iteration of the loop. This exposes the scalar
+multiply to a cache-based side channel attack; scalar blinding is necessary to
+prevent this attack from leaking information about the scalar.
The variable point multiplication algorithm uses a fixed-window algorithm. Since
this is normally invoked using untrusted points (eg during ECDH key exchange) it
diff --git a/src/lib/math/bigint/bigint.cpp b/src/lib/math/bigint/bigint.cpp
index 75c87e5b6..065c469b4 100644
--- a/src/lib/math/bigint/bigint.cpp
+++ b/src/lib/math/bigint/bigint.cpp
@@ -280,6 +280,7 @@ size_t BigInt::top_bits_free() const
const word top_word = word_at(words - 1);
const size_t bits_used = high_bit(top_word);
+ CT::unpoison(bits_used);
return BOTAN_MP_WORD_BITS - bits_used;
}
diff --git a/src/lib/math/numbertheory/nistp_redc.cpp b/src/lib/math/numbertheory/nistp_redc.cpp
index eca78d180..17089fcbe 100644
--- a/src/lib/math/numbertheory/nistp_redc.cpp
+++ b/src/lib/math/numbertheory/nistp_redc.cpp
@@ -176,8 +176,6 @@ void redc_p192(BigInt& x, secure_vector<word>& ws)
// No underflow possible
- BOTAN_ASSERT(S <= 2, "Expected overflow in P-192 reduce");
-
/*
This is a table of (i*P-192) % 2**192 for i in 1...3
*/
@@ -193,6 +191,9 @@ void redc_p192(BigInt& x, secure_vector<word>& ws)
#endif
};
+ CT::unpoison(S);
+ BOTAN_ASSERT(S <= 2, "Expected overflow");
+
BOTAN_ASSERT_NOMSG(x.size() == p192_limbs + 1);
word borrow = bigint_sub2(x.mutable_data(), p192_limbs + 1, p192_mults[S], p192_limbs);
BOTAN_DEBUG_ASSERT(borrow == 0 || borrow == 1);
@@ -280,8 +281,6 @@ void redc_p224(BigInt& x, secure_vector<word>& ws)
set_words(xw, 6, R0, 0);
- BOTAN_ASSERT(S >= 0 && S <= 2, "Expected overflow in P-224 reduce");
-
static const word p224_mults[3][p224_limbs] = {
#if (BOTAN_MP_WORD_BITS == 64)
{0x0000000000000001, 0xFFFFFFFF00000000, 0xFFFFFFFFFFFFFFFF, 0x00000000FFFFFFFF},
@@ -295,6 +294,9 @@ void redc_p224(BigInt& x, secure_vector<word>& ws)
};
+ CT::unpoison(S);
+ BOTAN_ASSERT(S >= 0 && S <= 2, "Expected overflow");
+
BOTAN_ASSERT_NOMSG(x.size() == p224_limbs + 1);
word borrow = bigint_sub2(x.mutable_data(), p224_limbs + 1, p224_mults[S], p224_limbs);
BOTAN_DEBUG_ASSERT(borrow == 0 || borrow == 1);
@@ -390,8 +392,6 @@ void redc_p256(BigInt& x, secure_vector<word>& ws)
S += 5; // the top digits of 6*P-256
- BOTAN_DEBUG_ASSERT(S >= 0 && S <= 10);
-
/*
This is a table of (i*P-256) % 2**256 for i in 1...10
*/
@@ -424,6 +424,7 @@ void redc_p256(BigInt& x, secure_vector<word>& ws)
};
CT::unpoison(S);
+ BOTAN_ASSERT(S >= 0 && S <= 10, "Expected overflow");
BOTAN_ASSERT_NOMSG(x.size() == p256_limbs + 1);
word borrow = bigint_sub2(x.mutable_data(), p256_limbs + 1, p256_mults[S], p256_limbs);
@@ -551,8 +552,6 @@ void redc_p384(BigInt& x, secure_vector<word>& ws)
set_words(xw, 10, R0, R1);
- BOTAN_ASSERT(S >= 0 && S <= 4, "Expected overflow in P-384 reduction");
-
/*
This is a table of (i*P-384) % 2**384 for i in 1...4
*/
@@ -578,6 +577,9 @@ void redc_p384(BigInt& x, secure_vector<word>& ws)
#endif
};
+ CT::unpoison(S);
+ BOTAN_ASSERT(S >= 0 && S <= 4, "Expected overflow");
+
BOTAN_ASSERT_NOMSG(x.size() == p384_limbs + 1);
word borrow = bigint_sub2(x.mutable_data(), p384_limbs + 1, p384_mults[S], p384_limbs);
BOTAN_DEBUG_ASSERT(borrow == 0 || borrow == 1);
diff --git a/src/lib/math/numbertheory/reducer.cpp b/src/lib/math/numbertheory/reducer.cpp
index ec0071eac..c37a1daeb 100644
--- a/src/lib/math/numbertheory/reducer.cpp
+++ b/src/lib/math/numbertheory/reducer.cpp
@@ -7,6 +7,7 @@
#include <botan/reducer.h>
#include <botan/internal/ct_utils.h>
+#include <botan/internal/mp_core.h>
#include <botan/divide.h>
namespace Botan {
@@ -41,6 +42,31 @@ BigInt Modular_Reducer::reduce(const BigInt& x) const
return r;
}
+namespace {
+
+/*
+* Like if(cnd) x.rev_sub(...) but in const time
+*/
+void cnd_rev_sub(bool cnd, BigInt& x, const word y[], size_t y_sw, secure_vector<word>& ws)
+ {
+ if(x.sign() != BigInt::Positive)
+ throw Invalid_State("BigInt::sub_rev requires this is positive");
+
+ const size_t x_sw = x.sig_words();
+
+ const size_t max_words = std::max(x_sw, y_sw);
+ ws.resize(std::max(x_sw, y_sw));
+ clear_mem(ws.data(), ws.size());
+ x.grow_to(max_words);
+
+ const int32_t relative_size = bigint_sub_abs(ws.data(), x.data(), x_sw, y, y_sw);
+
+ x.cond_flip_sign((relative_size > 0) && cnd);
+ bigint_cnd_swap(cnd, x.mutable_data(), ws.data(), max_words);
+ }
+
+}
+
void Modular_Reducer::reduce(BigInt& t1, const BigInt& x, secure_vector<word>& ws) const
{
if(&t1 == &x)
@@ -50,7 +76,7 @@ void Modular_Reducer::reduce(BigInt& t1, const BigInt& x, secure_vector<word>& w
const size_t x_sw = x.sig_words();
- if(x_sw >= (2*m_mod_words - 1) && x.cmp(m_modulus_2, false) >= 0)
+ if(x.cmp(m_modulus_2, false) >= 0)
{
// too big, fall back to slow boat division
t1 = ct_modulo(x, m_modulus);
@@ -87,10 +113,7 @@ void Modular_Reducer::reduce(BigInt& t1, const BigInt& x, secure_vector<word>& w
// Per HAC this step requires at most 2 subtractions
t1.ct_reduce_below(m_modulus, ws, 2);
- if(x.is_negative() && t1.is_nonzero())
- {
- t1.rev_sub(m_modulus.data(), m_modulus.size(), ws);
- }
+ cnd_rev_sub(t1.is_nonzero() && x.is_negative(), t1, m_modulus.data(), m_modulus.size(), ws);
}
}
diff --git a/src/lib/pubkey/dsa/dsa.cpp b/src/lib/pubkey/dsa/dsa.cpp
index 412270173..bece42d06 100644
--- a/src/lib/pubkey/dsa/dsa.cpp
+++ b/src/lib/pubkey/dsa/dsa.cpp
@@ -10,6 +10,7 @@
#include <botan/keypair.h>
#include <botan/reducer.h>
#include <botan/rng.h>
+#include <botan/divide.h>
#include <botan/internal/pk_ops_impl.h>
#if defined(BOTAN_HAS_RFC6979_GENERATOR)
@@ -124,7 +125,7 @@ DSA_Signature_Operation::raw_sign(const uint8_t msg[], size_t msg_len,
const BigInt k_inv = m_group.inverse_mod_q(k);
- const BigInt r = m_group.mod_q(m_group.power_g_p(k, m_group.q_bits()));
+ const BigInt r = ct_modulo(m_group.power_g_p(k, m_group.q_bits()), m_group.get_q());
/*
* Blind the input message and compute x*r+m as (x*r*b + m*b)/b
diff --git a/src/lib/pubkey/rsa/rsa.cpp b/src/lib/pubkey/rsa/rsa.cpp
index 9f14b9d6a..fd50ce539 100644
--- a/src/lib/pubkey/rsa/rsa.cpp
+++ b/src/lib/pubkey/rsa/rsa.cpp
@@ -247,7 +247,7 @@ class RSA_Private_Operation
auto future_j1 = std::async(std::launch::async, [this, &m, &d1_mask, powm_window]() {
#endif
const BigInt masked_d1 = m_key.get_d1() + (d1_mask * (m_key.get_p() - 1));
- auto powm_d1_p = monty_precompute(m_monty_p, m_mod_p.reduce(m), powm_window);
+ auto powm_d1_p = monty_precompute(m_monty_p, ct_modulo(m, m_key.get_p()), powm_window);
BigInt j1 = monty_execute(*powm_d1_p, masked_d1, m_max_d1_bits);
#if defined(BOTAN_RSA_USE_ASYNC)
@@ -257,7 +257,7 @@ class RSA_Private_Operation
const BigInt d2_mask(m_blinder.rng(), m_blinding_bits);
const BigInt masked_d2 = m_key.get_d2() + (d2_mask * (m_key.get_q() - 1));
- auto powm_d2_q = monty_precompute(m_monty_q, m_mod_q.reduce(m), powm_window);
+ auto powm_d2_q = monty_precompute(m_monty_q, ct_modulo(m, m_key.get_q()), powm_window);
const BigInt j2 = monty_execute(*powm_d2_q, masked_d2, m_max_d2_bits);
/*
@@ -272,11 +272,7 @@ class RSA_Private_Operation
BigInt j1 = future_j1.get();
#endif
- /*
- To prevent a side channel that allows detecting case where j1 < j2,
- add p to j1 before reducing [computing c*(p+j1-j2) mod p]
- */
- j1 = m_mod_p.reduce(sub_mul(m_key.get_p() + j1, j2, m_key.get_c()));
+ j1 = m_mod_p.multiply(j1 - j2, m_key.get_c());
return mul_add(j1, m_key.get_q(), j2);
}
diff --git a/src/lib/pubkey/sm2/sm2.cpp b/src/lib/pubkey/sm2/sm2.cpp
index cf08d0f1c..5ffd547cf 100644
--- a/src/lib/pubkey/sm2/sm2.cpp
+++ b/src/lib/pubkey/sm2/sm2.cpp
@@ -153,7 +153,7 @@ SM2_Signature_Operation::sign(RandomNumberGenerator& rng)
const BigInt r = m_group.mod_order(
m_group.blinded_base_point_multiply_x(k, rng, m_ws) + e);
- const BigInt s = m_group.multiply_mod_order(m_da_inv, (k - r*m_x));
+ const BigInt s = m_group.multiply_mod_order(m_da_inv, m_group.mod_order(k - r*m_x));
return BigInt::encode_fixed_length_int_pair(r, s, m_group.get_order().bytes());
}
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-22 23:37:32 +0000