No negative moduli.
https://boringssl-review.googlesource.com/31085 wasn't right. We already forbid
creating BN_MONT_CTX on negative numbers, which means almost all moduli already
don't work with BN_mod_exp_mont. Only -1 happened to not get rejected, but it
computed the wrong value. Reject it instead.
Update-Note: BN_mod_exp* will no longer work for negative moduli. It already
didn't work for all negative odd moduli other than -1, so rejecting -1 and
negative evens is unlikely to be noticed.
Bug: 71
Change-Id: I7c713d417e2e6512f3e78f402de88540809977e3
Reviewed-on: https://boringssl-review.googlesource.com/31484
Reviewed-by: Adam Langley <agl@google.com>
diff --git a/crypto/fipsmodule/bn/bn_test.cc b/crypto/fipsmodule/bn/bn_test.cc
index a932306..29b4456 100644
--- a/crypto/fipsmodule/bn/bn_test.cc
+++ b/crypto/fipsmodule/bn/bn_test.cc
@@ -1592,21 +1592,6 @@
ASSERT_TRUE(BN_mod_exp_mont_consttime(r.get(), zero.get(), zero.get(),
BN_value_one(), ctx(), nullptr));
EXPECT_TRUE(BN_is_zero(r.get()));
-
- // Historically, OpenSSL's modular exponentiation functions tolerated negative
- // moduli by ignoring the sign bit. This logic should do the same.
- ASSERT_TRUE(BN_mod_exp(r.get(), a.get(), zero.get(), minus_one.get(), ctx()));
- EXPECT_TRUE(BN_is_zero(r.get()));
- ASSERT_TRUE(BN_mod_exp_mont_word(r.get(), 0, zero.get(), minus_one.get(),
- ctx(), nullptr));
- EXPECT_TRUE(BN_is_zero(r.get()));
- ASSERT_TRUE(BN_mod_exp_mont(r.get(), zero.get(), zero.get(), minus_one.get(),
- ctx(), nullptr));
- EXPECT_TRUE(BN_is_zero(r.get()));
-
- ASSERT_TRUE(BN_mod_exp_mont_consttime(r.get(), zero.get(), zero.get(),
- minus_one.get(), ctx(), nullptr));
- EXPECT_TRUE(BN_is_zero(r.get()));
}
TEST_F(BNTest, SmallPrime) {
diff --git a/crypto/fipsmodule/bn/exponentiation.c b/crypto/fipsmodule/bn/exponentiation.c
index 7035ea7..41b2057 100644
--- a/crypto/fipsmodule/bn/exponentiation.c
+++ b/crypto/fipsmodule/bn/exponentiation.c
@@ -446,21 +446,18 @@
static int mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
const BIGNUM *m, BN_CTX *ctx) {
- int i, j, bits, ret = 0, wstart, window;
+ int i, j, ret = 0, wstart, window;
int start = 1;
BIGNUM *aa;
// Table of variables obtained from 'ctx'
BIGNUM *val[TABLE_SIZE];
BN_RECP_CTX recp;
- bits = BN_num_bits(p);
+ // This function is only called on even moduli.
+ assert(!BN_is_odd(m));
+ int bits = BN_num_bits(p);
if (bits == 0) {
- // x**0 mod 1 is still zero.
- if (BN_abs_is_word(m, 1)) {
- BN_zero(r);
- return 1;
- }
return BN_one(r);
}
@@ -586,6 +583,10 @@
int BN_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m,
BN_CTX *ctx) {
+ if (m->neg) {
+ OPENSSL_PUT_ERROR(BN, BN_R_NEGATIVE_NUMBER);
+ return 0;
+ }
if (a->neg || BN_ucmp(a, m) >= 0) {
if (!BN_nnmod(r, a, m, ctx)) {
return 0;
@@ -606,6 +607,10 @@
OPENSSL_PUT_ERROR(BN, BN_R_CALLED_WITH_EVEN_MODULUS);
return 0;
}
+ if (m->neg) {
+ OPENSSL_PUT_ERROR(BN, BN_R_NEGATIVE_NUMBER);
+ return 0;
+ }
if (a->neg || BN_ucmp(a, m) >= 0) {
OPENSSL_PUT_ERROR(BN, BN_R_INPUT_NOT_REDUCED);
return 0;
@@ -970,6 +975,10 @@
OPENSSL_PUT_ERROR(BN, BN_R_CALLED_WITH_EVEN_MODULUS);
return 0;
}
+ if (m->neg) {
+ OPENSSL_PUT_ERROR(BN, BN_R_NEGATIVE_NUMBER);
+ return 0;
+ }
if (a->neg || BN_ucmp(a, m) >= 0) {
OPENSSL_PUT_ERROR(BN, BN_R_INPUT_NOT_REDUCED);
return 0;