Compute p - q in constant time.
Expose the constant-time abs_sub functions from the fixed Karatsuba code
in BIGNUM form for RSA to call into. RSA key generation involves
checking if |p - q| is above some lower bound.
BN_sub internally branches on which of p or q is bigger. For any given
iteration, this is not secret---one of p or q is necessarily the larger,
and whether we happened to pick the larger or smaller first is
irrelevant. Accordingly, there is no need to perform the p/q swap at the
end in constant-time.
However, this stage of the algorithm picks p first, sticks with it, and
then computes |p - q| for various q candidates. The distribution of
comparisons leaks information about p. The leak is unlikely to be
problematic, but plug it anyway.
Median of 29 RSA keygens: 0m0.210s -> 0m0.212s
(Accuracy beyond 0.1s is questionable.)
Bug: 238
Change-Id: I024b4e51b364f5ca2bcb419a0393e7be13249aec
Reviewed-on: https://boringssl-review.googlesource.com/26368
Reviewed-by: Adam Langley <alangley@gmail.com>
diff --git a/crypto/fipsmodule/bn/bn_test.cc b/crypto/fipsmodule/bn/bn_test.cc
index 52eb5a9..41b0066 100644
--- a/crypto/fipsmodule/bn/bn_test.cc
+++ b/crypto/fipsmodule/bn/bn_test.cc
@@ -239,8 +239,7 @@
// having. Note that these functions are frequently used when the
// prerequisites don't hold. In those cases, they are supposed to work as if
// the prerequisite hold, but we don't test that yet. TODO: test that.
- if (!BN_is_negative(a.get()) &&
- !BN_is_negative(b.get()) && BN_cmp(a.get(), b.get()) >= 0) {
+ if (!BN_is_negative(a.get()) && !BN_is_negative(b.get())) {
ASSERT_TRUE(BN_uadd(ret.get(), a.get(), b.get()));
EXPECT_BIGNUMS_EQUAL("A +u B", sum.get(), ret.get());
@@ -276,6 +275,16 @@
ASSERT_TRUE(BN_copy(ret.get(), b.get()));
ASSERT_TRUE(BN_usub(ret.get(), sum.get(), ret.get()));
EXPECT_BIGNUMS_EQUAL("Sum -u B (r is b)", a.get(), ret.get());
+
+ ASSERT_TRUE(bn_abs_sub_consttime(ret.get(), sum.get(), a.get(), ctx));
+ EXPECT_BIGNUMS_EQUAL("|Sum - A|", b.get(), ret.get());
+ ASSERT_TRUE(bn_abs_sub_consttime(ret.get(), a.get(), sum.get(), ctx));
+ EXPECT_BIGNUMS_EQUAL("|A - Sum|", b.get(), ret.get());
+
+ ASSERT_TRUE(bn_abs_sub_consttime(ret.get(), sum.get(), b.get(), ctx));
+ EXPECT_BIGNUMS_EQUAL("|Sum - B|", a.get(), ret.get());
+ ASSERT_TRUE(bn_abs_sub_consttime(ret.get(), b.get(), sum.get(), ctx));
+ EXPECT_BIGNUMS_EQUAL("|B - Sum|", a.get(), ret.get());
}
// Test with |BN_add_word| and |BN_sub_word| if |b| is small enough.
diff --git a/crypto/fipsmodule/bn/internal.h b/crypto/fipsmodule/bn/internal.h
index 1515594..309c0c6 100644
--- a/crypto/fipsmodule/bn/internal.h
+++ b/crypto/fipsmodule/bn/internal.h
@@ -402,6 +402,11 @@
// |r->width| = |a->width|.
int bn_usub_consttime(BIGNUM *r, const BIGNUM *a, const BIGNUM *b);
+// bn_abs_sub_consttime sets |r| to the absolute value of |a| - |b|, treating
+// both inputs as secret. It returns one on success and zero on error.
+OPENSSL_EXPORT int bn_abs_sub_consttime(BIGNUM *r, const BIGNUM *a,
+ const BIGNUM *b, BN_CTX *ctx);
+
// bn_mul_consttime behaves like |BN_mul|, but it rejects negative inputs and
// pessimally sets |r->width| to |a->width| + |b->width|, to avoid leaking
// information about |a| and |b|.
diff --git a/crypto/fipsmodule/bn/mul.c b/crypto/fipsmodule/bn/mul.c
index a3ff854..4a0711d 100644
--- a/crypto/fipsmodule/bn/mul.c
+++ b/crypto/fipsmodule/bn/mul.c
@@ -306,6 +306,24 @@
return borrow;
}
+int bn_abs_sub_consttime(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
+ BN_CTX *ctx) {
+ int cl = a->width < b->width ? a->width : b->width;
+ int dl = a->width - b->width;
+ int r_len = a->width < b->width ? b->width : a->width;
+ BN_CTX_start(ctx);
+ BIGNUM *tmp = BN_CTX_get(ctx);
+ int ok = tmp != NULL &&
+ bn_wexpand(r, r_len) &&
+ bn_wexpand(tmp, r_len);
+ if (ok) {
+ bn_abs_sub_part_words(r->d, a->d, b->d, cl, dl, tmp->d);
+ r->width = r_len;
+ }
+ BN_CTX_end(ctx);
+ return ok;
+}
+
// Karatsuba recursive multiplication algorithm
// (cf. Knuth, The Art of Computer Programming, Vol. 2)
diff --git a/crypto/fipsmodule/rsa/rsa_impl.c b/crypto/fipsmodule/rsa/rsa_impl.c
index 66b59f0..6ddfa0d 100644
--- a/crypto/fipsmodule/rsa/rsa_impl.c
+++ b/crypto/fipsmodule/rsa/rsa_impl.c
@@ -968,10 +968,9 @@
if (p != NULL) {
// If |p| and |out| are too close, try again (step 5.4).
- if (!BN_sub(tmp, out, p)) {
+ if (!bn_abs_sub_consttime(tmp, out, p, ctx)) {
goto err;
}
- BN_set_negative(tmp, 0);
if (BN_cmp(tmp, pow2_bits_100) <= 0) {
continue;
}
