From 42619397eb5db1a77d077250b0841b9c9f2b8984 Mon Sep 17 00:00:00 2001 From: Kurt Roeckx Date: Sun, 6 Oct 2019 17:21:16 +0200 Subject: Add BN_check_prime() Add a new API to test for primes that can't be misused, deprecated the old APIs. Suggested by Jake Massimo and Kenneth Paterson Reviewed-by: Paul Dale GH: #9272 --- crypto/bn/bn_depr.c | 6 ++--- crypto/bn/bn_local.h | 3 +++ crypto/bn/bn_prime.c | 62 ++++++++++++++++++++++++++++++++++++++------ crypto/bn/bn_rsa_fips186_4.c | 49 +++------------------------------- crypto/bn/bn_x931p.c | 4 +-- 5 files changed, 65 insertions(+), 59 deletions(-) (limited to 'crypto/bn') diff --git a/crypto/bn/bn_depr.c b/crypto/bn/bn_depr.c index 18d02d894e..4dbbdc3814 100644 --- a/crypto/bn/bn_depr.c +++ b/crypto/bn/bn_depr.c @@ -52,7 +52,7 @@ int BN_is_prime(const BIGNUM *a, int checks, { BN_GENCB cb; BN_GENCB_set_old(&cb, callback, cb_arg); - return BN_is_prime_ex(a, checks, ctx_passed, &cb); + return bn_check_prime_int(a, checks, ctx_passed, 0, &cb); } int BN_is_prime_fasttest(const BIGNUM *a, int checks, @@ -62,7 +62,7 @@ int BN_is_prime_fasttest(const BIGNUM *a, int checks, { BN_GENCB cb; BN_GENCB_set_old(&cb, callback, cb_arg); - return BN_is_prime_fasttest_ex(a, checks, ctx_passed, - do_trial_division, &cb); + return bn_check_prime_int(a, checks, ctx_passed, do_trial_division, &cb); } + #endif diff --git a/crypto/bn/bn_local.h b/crypto/bn/bn_local.h index 4c86986804..ec90338510 100644 --- a/crypto/bn/bn_local.h +++ b/crypto/bn/bn_local.h @@ -665,4 +665,7 @@ static ossl_inline BIGNUM *bn_expand(BIGNUM *a, int bits) return bn_expand2((a),(bits+BN_BITS2-1)/BN_BITS2); } +int bn_check_prime_int(const BIGNUM *w, int checks, BN_CTX *ctx, + int do_trial_division, BN_GENCB *cb); + #endif diff --git a/crypto/bn/bn_prime.c b/crypto/bn/bn_prime.c index 7d89d321d8..fd1c3c3088 100644 --- a/crypto/bn/bn_prime.c +++ b/crypto/bn/bn_prime.c @@ -24,6 +24,8 @@ static int probable_prime(BIGNUM *rnd, int bits, int safe, prime_t *mods, static int probable_prime_dh(BIGNUM *rnd, int bits, int safe, prime_t *mods, const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx); +static int bn_is_prime_int(const BIGNUM *w, int checks, BN_CTX *ctx, + int do_trial_division, BN_GENCB *cb); #define square(x) ((BN_ULONG)(x) * (BN_ULONG)(x)) @@ -82,6 +84,20 @@ static int calc_trial_divisions(int bits) return NUMPRIMES; } +/* + * Use a minimum of 64 rounds of Miller-Rabin, which should give a false + * positive rate of 2^-128. If the size of the prime is larger than 2048 + * the user probably wants a higher security level than 128, so switch + * to 128 rounds giving a false positive rate of 2^-256. + * Returns the number of rounds. + */ +static int bn_mr_min_checks(int bits) +{ + if (bits > 2048) + return 128; + return 64; +} + int BN_GENCB_call(BN_GENCB *cb, int a, int b) { /* No callback means continue */ @@ -112,7 +128,7 @@ int BN_generate_prime_ex2(BIGNUM *ret, int bits, int safe, int found = 0; int i, j, c1 = 0; prime_t *mods = NULL; - int checks = BN_prime_checks_for_size(bits); + int checks = bn_mr_min_checks(bits); if (bits < 2) { /* There are no prime numbers this small. */ @@ -151,7 +167,7 @@ int BN_generate_prime_ex2(BIGNUM *ret, int bits, int safe, goto err; if (!safe) { - i = BN_is_prime_fasttest_ex(ret, checks, ctx, 0, cb); + i = bn_is_prime_int(ret, checks, ctx, 0, cb); if (i == -1) goto err; if (i == 0) @@ -165,13 +181,13 @@ int BN_generate_prime_ex2(BIGNUM *ret, int bits, int safe, goto err; for (i = 0; i < checks; i++) { - j = BN_is_prime_fasttest_ex(ret, 1, ctx, 0, cb); + j = bn_is_prime_int(ret, 1, ctx, 0, cb); if (j == -1) goto err; if (j == 0) goto loop; - j = BN_is_prime_fasttest_ex(t, 1, ctx, 0, cb); + j = bn_is_prime_int(t, 1, ctx, 0, cb); if (j == -1) goto err; if (j == 0) @@ -208,15 +224,45 @@ int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe, } #endif +#if !OPENSSL_API_3 int BN_is_prime_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed, BN_GENCB *cb) { - return BN_is_prime_fasttest_ex(a, checks, ctx_passed, 0, cb); + return bn_check_prime_int(a, checks, ctx_passed, 0, cb); } -/* See FIPS 186-4 C.3.1 Miller Rabin Probabilistic Primality Test. */ int BN_is_prime_fasttest_ex(const BIGNUM *w, int checks, BN_CTX *ctx, int do_trial_division, BN_GENCB *cb) +{ + return bn_check_prime_int(w, checks, ctx, do_trial_division, cb); +} +#endif + +/* Wrapper around bn_is_prime_int that sets the minimum number of checks */ +int bn_check_prime_int(const BIGNUM *w, int checks, BN_CTX *ctx, + int do_trial_division, BN_GENCB *cb) +{ + int min_checks = bn_mr_min_checks(BN_num_bits(w)); + + if (checks < min_checks) + checks = min_checks; + + return bn_is_prime_int(w, checks, ctx, do_trial_division, cb); +} + +int BN_check_prime(const BIGNUM *p, BN_CTX *ctx, BN_GENCB *cb) +{ + return bn_check_prime_int(p, 0, ctx, 1, cb); +} + +/* + * Tests that |w| is probably prime + * See FIPS 186-4 C.3.1 Miller Rabin Probabilistic Primality Test. + * + * Returns 0 when composite, 1 when probable prime, -1 on error. + */ +static int bn_is_prime_int(const BIGNUM *w, int checks, BN_CTX *ctx, + int do_trial_division, BN_GENCB *cb) { int i, status, ret = -1; #ifndef FIPS_MODE @@ -332,8 +378,8 @@ int bn_miller_rabin_is_prime(const BIGNUM *w, int iterations, BN_CTX *ctx, if (mont == NULL || !BN_MONT_CTX_set(mont, w, ctx)) goto err; - if (iterations == BN_prime_checks) - iterations = BN_prime_checks_for_size(BN_num_bits(w)); + if (iterations == 0) + iterations = bn_mr_min_checks(BN_num_bits(w)); /* (Step 4) */ for (i = 0; i < iterations; ++i) { diff --git a/crypto/bn/bn_rsa_fips186_4.c b/crypto/bn/bn_rsa_fips186_4.c index e5e4eccb22..c31b43ba8f 100644 --- a/crypto/bn/bn_rsa_fips186_4.c +++ b/crypto/bn/bn_rsa_fips186_4.c @@ -67,44 +67,6 @@ static int bn_rsa_fips186_4_aux_prime_max_sum_size_for_prob_primes(int nbits) return 0; } -/* - * FIPS 186-4 Table C.3 for error probability of 2^-100 - * Minimum number of Miller Rabin Rounds for p1, p2, q1 & q2. - * - * Params: - * aux_prime_bits The auxiliary prime size in bits. - * Returns: - * The minimum number of Miller Rabin Rounds for an auxiliary prime, or - * 0 if aux_prime_bits is invalid. - */ -static int bn_rsa_fips186_4_aux_prime_MR_min_checks(int aux_prime_bits) -{ - if (aux_prime_bits > 170) - return 27; - if (aux_prime_bits > 140) - return 32; - return 0; /* Error case */ -} - -/* - * FIPS 186-4 Table C.3 for error probability of 2^-100 - * Minimum number of Miller Rabin Rounds for p, q. - * - * Params: - * nbits The key size in bits. - * Returns: - * The minimum number of Miller Rabin Rounds required, - * or 0 if nbits is invalid. - */ -int bn_rsa_fips186_4_prime_MR_min_checks(int nbits) -{ - if (nbits >= 3072) /* > 170 */ - return 3; - if (nbits == 2048) /* > 140 */ - return 4; - return 0; /* Error case */ -} - /* * Find the first odd integer that is a probable prime. * @@ -123,9 +85,8 @@ static int bn_rsa_fips186_4_find_aux_prob_prime(const BIGNUM *Xp1, { int ret = 0; int i = 0; - int checks = bn_rsa_fips186_4_aux_prime_MR_min_checks(BN_num_bits(Xp1)); - if (checks == 0 || BN_copy(p1, Xp1) == NULL) + if (BN_copy(p1, Xp1) == NULL) return 0; /* Find the first odd number >= Xp1 that is probably prime */ @@ -133,7 +94,7 @@ static int bn_rsa_fips186_4_find_aux_prob_prime(const BIGNUM *Xp1, i++; BN_GENCB_call(cb, 0, i); /* MR test with trial division */ - if (BN_is_prime_fasttest_ex(p1, checks, ctx, 1, cb)) + if (BN_check_prime(p1, ctx, cb)) break; /* Get next odd number */ if (!BN_add_word(p1, 2)) @@ -259,11 +220,8 @@ int bn_rsa_fips186_4_derive_prime(BIGNUM *Y, BIGNUM *X, const BIGNUM *Xin, int ret = 0; int i, imax; int bits = nlen >> 1; - int checks = bn_rsa_fips186_4_prime_MR_min_checks(nlen); BIGNUM *tmp, *R, *r1r2x2, *y1, *r1x2; - if (checks == 0) - return 0; BN_CTX_start(ctx); R = BN_CTX_get(ctx); @@ -331,8 +289,7 @@ int bn_rsa_fips186_4_derive_prime(BIGNUM *Y, BIGNUM *X, const BIGNUM *Xin, || !BN_sub_word(y1, 1) || !BN_gcd(tmp, y1, e, ctx)) goto err; - if (BN_is_one(tmp) - && BN_is_prime_fasttest_ex(Y, checks, ctx, 1, cb)) + if (BN_is_one(tmp) && BN_check_prime(Y, ctx, cb)) goto end; /* (Step 8-10) */ if (++i >= imax || !BN_add(Y, Y, r1r2x2)) diff --git a/crypto/bn/bn_x931p.c b/crypto/bn/bn_x931p.c index 211886f5ee..1e4d4991b2 100644 --- a/crypto/bn/bn_x931p.c +++ b/crypto/bn/bn_x931p.c @@ -30,7 +30,7 @@ static int bn_x931_derive_pi(BIGNUM *pi, const BIGNUM *Xpi, BN_CTX *ctx, i++; BN_GENCB_call(cb, 0, i); /* NB 27 MR is specified in X9.31 */ - is_prime = BN_is_prime_fasttest_ex(pi, 27, ctx, 1, cb); + is_prime = BN_check_prime(pi, ctx, cb); if (is_prime < 0) return 0; if (is_prime) @@ -131,7 +131,7 @@ int BN_X931_derive_prime_ex(BIGNUM *p, BIGNUM *p1, BIGNUM *p2, * offering similar or better guarantees 50 MR is considerably * better. */ - int r = BN_is_prime_fasttest_ex(p, 50, ctx, 1, cb); + int r = BN_check_prime(p, ctx, cb); if (r < 0) goto err; if (r) -- cgit v1.2.3