Align BN_rand_range_ex with FIPS 186-4.
Rather than comparing against both min and max, FIPS prefers comparing
with max - min and adding min. It also does not believe in using
3*range. Align with it, though our old algorithm trivially produces the
same probability distribution on values.
Change-Id: I447cc3608b92ba93706489d702b8d6a68047f491
Reviewed-on: https://boringssl-review.googlesource.com/15045
Reviewed-by: Adam Langley <agl@google.com>
Reviewed-by: David Benjamin <davidben@google.com>
Commit-Queue: David Benjamin <davidben@google.com>
CQ-Verified: CQ bot account: commit-bot@chromium.org <commit-bot@chromium.org>
diff --git a/crypto/bn/bn_test.cc b/crypto/bn/bn_test.cc
index c0af58d..9597956 100644
--- a/crypto/bn/bn_test.cc
+++ b/crypto/bn/bn_test.cc
@@ -1105,6 +1105,49 @@
return true;
}
+static bool TestRandRange() {
+ bssl::UniquePtr<BIGNUM> bn(BN_new()), six(BN_new());
+ if (!bn || !six ||
+ !BN_set_word(six.get(), 6)) {
+ return false;
+ }
+
+ // Generate 1,000 random numbers and ensure they all stay in range. This check
+ // may flakily pass when it should have failed but will not flakily fail.
+ bool seen[6] = {false, false, false, false, false};
+ for (unsigned i = 0; i < 1000; i++) {
+ if (!BN_rand_range_ex(bn.get(), 1, six.get())) {
+ return false;
+ }
+
+ BN_ULONG word = BN_get_word(bn.get());
+ if (BN_is_negative(bn.get()) ||
+ word < 1 ||
+ word >= 6) {
+ fprintf(stderr,
+ "BN_rand_range_ex generated invalid value: " BN_DEC_FMT1 "\n",
+ word);
+ return false;
+ }
+
+ seen[word] = true;
+ }
+
+ // Test that all numbers were accounted for. Note this test is probabilistic
+ // and may flakily fail when it should have passed. As an upper-bound on the
+ // failure probability, we'll never see any one number with probability
+ // (4/5)^1000, so the probability of failure is at most 5*(4/5)^1000. This is
+ // around 1 in 2^320.
+ for (unsigned i = 1; i < 6; i++) {
+ if (!seen[i]) {
+ fprintf(stderr, "BN_rand_range failed to generate %u.\n", i);
+ return false;
+ }
+ }
+
+ return true;
+}
+
struct ASN1Test {
const char *value_ascii;
const char *der;
@@ -1775,6 +1818,7 @@
!TestLittleEndian() ||
!TestMPI() ||
!TestRand() ||
+ !TestRandRange() ||
!TestASN1() ||
!TestNegativeZero(ctx.get()) ||
!TestBadModulus(ctx.get()) ||
@@ -1784,6 +1828,7 @@
!TestBN2Dec() ||
!TestBNSetGetU64() ||
!TestBNPow2(ctx.get())) {
+ ERR_print_errors_fp(stderr);
return 1;
}
diff --git a/crypto/bn/random.c b/crypto/bn/random.c
index 6f922c0..428b4c3 100644
--- a/crypto/bn/random.c
+++ b/crypto/bn/random.c
@@ -197,58 +197,33 @@
int BN_rand_range_ex(BIGNUM *r, BN_ULONG min_inclusive,
const BIGNUM *max_exclusive) {
- unsigned n;
- unsigned count = 100;
-
if (BN_cmp_word(max_exclusive, min_inclusive) <= 0) {
OPENSSL_PUT_ERROR(BN, BN_R_INVALID_RANGE);
return 0;
}
- n = BN_num_bits(max_exclusive); /* n > 0 */
-
- /* BN_is_bit_set(range, n - 1) always holds */
- if (n == 1) {
- BN_zero(r);
- return 1;
- }
-
+ /* This function is used to implement steps 4 through 7 of FIPS 186-4
+ * appendices B.4.2 and B.5.2. When called in those contexts, |max_exclusive|
+ * is n and |min_inclusive| is one. */
+ unsigned count = 100;
+ unsigned n = BN_num_bits(max_exclusive); /* n > 0 */
do {
if (!--count) {
OPENSSL_PUT_ERROR(BN, BN_R_TOO_MANY_ITERATIONS);
return 0;
}
- if (!BN_is_bit_set(max_exclusive, n - 2) &&
- !BN_is_bit_set(max_exclusive, n - 3)) {
- /* range = 100..._2, so 3*range (= 11..._2) is exactly one bit longer
- * than range. This is a common scenario when generating a random value
- * modulo an RSA public modulus, e.g. for RSA base blinding. */
- if (!BN_rand(r, n + 1, BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY)) {
- return 0;
- }
-
- /* If r < 3*range, use r := r MOD range (which is either r, r - range, or
- * r - 2*range). Otherwise, iterate again. Since 3*range = 11..._2, each
- * iteration succeeds with probability >= .75. */
- if (BN_cmp(r, max_exclusive) >= 0) {
- if (!BN_sub(r, r, max_exclusive)) {
- return 0;
- }
- if (BN_cmp(r, max_exclusive) >= 0) {
- if (!BN_sub(r, r, max_exclusive)) {
- return 0;
- }
- }
- }
- } else {
- /* range = 11..._2 or range = 101..._2 */
- if (!BN_rand(r, n, BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY)) {
- return 0;
- }
+ if (/* steps 4 and 5 */
+ !BN_rand(r, n, BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY) ||
+ /* step 7 */
+ !BN_add_word(r, min_inclusive)) {
+ return 0;
}
- } while (BN_cmp_word(r, min_inclusive) < 0 ||
- BN_cmp(r, max_exclusive) >= 0);
+
+ /* Step 6. This loops if |r| >= |max_exclusive|. This is identical to
+ * checking |r| > |max_exclusive| - 1 or |r| - 1 > |max_exclusive| - 2, the
+ * formulation stated in FIPS 186-4. */
+ } while (BN_cmp(r, max_exclusive) >= 0);
return 1;
}
diff --git a/crypto/ec/ec_key.c b/crypto/ec/ec_key.c
index d15cca7..1be4d25 100644
--- a/crypto/ec/ec_key.c
+++ b/crypto/ec/ec_key.c
@@ -468,8 +468,7 @@
goto err;
}
- /* Generate the private key by testing candidates (FIPS 186-4 B.4.2).
- * TODO(svaldez): Fix BN_rand_range_ex to implement B.4.2. */
+ /* Generate the private key by testing candidates (FIPS 186-4 B.4.2). */
if (!BN_rand_range_ex(priv_key, 1, order)) {
goto err;
}
