From c17ab57a969b3bfe7c63593bff1702d965461175 Mon Sep 17 00:00:00 2001 From: bcook Date: Tue, 5 Jul 2016 02:54:35 +0000 Subject: [PATCH] On systems where we do not have BN_ULLONG defined (most 64-bit systems), BN_mod_word() can return incorrect results if the supplied modulus is too big, so we need to fall back to BN_div_word. Now that BN_mod_word may fail, handle errors properly update the man page. Thanks to Brian Smith for pointing out these fixes from BoringSSL: https://boringssl.googlesource.com/boringssl/+/67cb49d045f04973ddba0f92fe8a8ad483c7da89 https://boringssl.googlesource.com/boringssl/+/44bedc348d9491e63c7ed1438db100a4b8a830be ok beck@ --- lib/libcrypto/bn/bn_prime.c | 30 +++++++++++++++++------ lib/libcrypto/bn/bn_word.c | 16 +++++++++++- lib/libcrypto/dh/dh_check.c | 6 ++++- lib/libcrypto/man/BN_add_word.3 | 5 ++-- lib/libssl/src/crypto/bn/bn_prime.c | 30 +++++++++++++++++------ lib/libssl/src/crypto/bn/bn_word.c | 16 +++++++++++- lib/libssl/src/crypto/dh/dh_check.c | 6 ++++- regress/lib/libcrypto/bn/general/bntest.c | 28 ++++++++++++++++++--- 8 files changed, 111 insertions(+), 26 deletions(-) diff --git a/lib/libcrypto/bn/bn_prime.c b/lib/libcrypto/bn/bn_prime.c index b1aba663dfc..fb39756de24 100644 --- a/lib/libcrypto/bn/bn_prime.c +++ b/lib/libcrypto/bn/bn_prime.c @@ -1,4 +1,4 @@ -/* $OpenBSD: bn_prime.c,v 1.14 2015/10/21 19:02:22 miod Exp $ */ +/* $OpenBSD: bn_prime.c,v 1.15 2016/07/05 02:54:35 bcook Exp $ */ /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) * All rights reserved. * @@ -277,9 +277,13 @@ BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed, /* a is even => a is prime if and only if a == 2 */ return BN_is_word(a, 2); if (do_trial_division) { - for (i = 1; i < NUMPRIMES; i++) - if (BN_mod_word(a, primes[i]) == 0) + for (i = 1; i < NUMPRIMES; i++) { + BN_ULONG mod = BN_mod_word(a, primes[i]); + if (mod == (BN_ULONG)-1) + goto err; + if (mod == 0) return 0; + } if (!BN_GENCB_call(cb, 1, -1)) goto err; } @@ -398,8 +402,12 @@ again: if (!BN_rand(rnd, bits, 1, 1)) return (0); /* we now have a random number 'rand' to test. */ - for (i = 1; i < NUMPRIMES; i++) - mods[i] = (prime_t)BN_mod_word(rnd, (BN_ULONG)primes[i]); + for (i = 1; i < NUMPRIMES; i++) { + BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]); + if (mod == (BN_ULONG)-1) + return (0); + mods[i] = (prime_t)mod; + } maxdelta = BN_MASK2 - primes[NUMPRIMES - 1]; delta = 0; loop: @@ -452,7 +460,10 @@ probable_prime_dh(BIGNUM *rnd, int bits, const BIGNUM *add, const BIGNUM *rem, loop: for (i = 1; i < NUMPRIMES; i++) { /* check that rnd is a prime */ - if (BN_mod_word(rnd, (BN_ULONG)primes[i]) <= 1) { + BN_LONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]); + if (mod == (BN_ULONG)-1) + goto err; + if (mod <= 1) { if (!BN_add(rnd, rnd, add)) goto err; goto loop; @@ -514,8 +525,11 @@ loop: /* check that p and q are prime */ /* check that for p and q * gcd(p-1,primes) == 1 (except for 2) */ - if ((BN_mod_word(p, (BN_ULONG)primes[i]) == 0) || - (BN_mod_word(q, (BN_ULONG)primes[i]) == 0)) { + BN_ULONG pmod = BN_mod_word(p, (BN_ULONG)primes[i]); + BN_ULONG qmod = BN_mod_word(q, (BN_ULONG)primes[i]); + if (pmod == (BN_ULONG)-1 || qmod == (BN_ULONG)-1) + goto err; + if (pmod == 0 || qmod == 0) { if (!BN_add(p, p, padd)) goto err; if (!BN_add(q, q, qadd)) diff --git a/lib/libcrypto/bn/bn_word.c b/lib/libcrypto/bn/bn_word.c index c4c6754c374..71654586a1b 100644 --- a/lib/libcrypto/bn/bn_word.c +++ b/lib/libcrypto/bn/bn_word.c @@ -1,4 +1,4 @@ -/* $OpenBSD: bn_word.c,v 1.12 2014/07/11 08:44:48 jsing Exp $ */ +/* $OpenBSD: bn_word.c,v 1.13 2016/07/05 02:54:35 bcook Exp $ */ /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) * All rights reserved. * @@ -73,6 +73,20 @@ BN_mod_word(const BIGNUM *a, BN_ULONG w) if (w == 0) return (BN_ULONG) - 1; +#ifndef BN_ULLONG + /* If |w| is too long and we don't have |BN_ULLONG| then we need to fall back + * to using |BN_div_word|. */ + if (w > ((BN_ULONG)1 << BN_BITS4)) { + BIGNUM *tmp = BN_dup(a); + if (tmp == NULL) { + return (BN_ULONG)-1; + } + ret = BN_div_word(tmp, w); + BN_free(tmp); + return ret; + } +#endif + bn_check_top(a); w &= BN_MASK2; for (i = a->top - 1; i >= 0; i--) { diff --git a/lib/libcrypto/dh/dh_check.c b/lib/libcrypto/dh/dh_check.c index 93e1003bd64..a6010f0a6dc 100644 --- a/lib/libcrypto/dh/dh_check.c +++ b/lib/libcrypto/dh/dh_check.c @@ -1,4 +1,4 @@ -/* $OpenBSD: dh_check.c,v 1.15 2015/02/07 13:19:15 doug Exp $ */ +/* $OpenBSD: dh_check.c,v 1.16 2016/07/05 02:54:35 bcook Exp $ */ /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) * All rights reserved. * @@ -89,10 +89,14 @@ DH_check(const DH *dh, int *ret) if (BN_is_word(dh->g, DH_GENERATOR_2)) { l = BN_mod_word(dh->p, 24); + if (l == (BN_ULONG)-1) + goto err; if (l != 11) *ret |= DH_NOT_SUITABLE_GENERATOR; } else if (BN_is_word(dh->g, DH_GENERATOR_5)) { l = BN_mod_word(dh->p, 10); + if (l == (BN_ULONG)-1) + goto err; if (l != 3 && l != 7) *ret |= DH_NOT_SUITABLE_GENERATOR; } else diff --git a/lib/libcrypto/man/BN_add_word.3 b/lib/libcrypto/man/BN_add_word.3 index 930aae4d320..16f2a17eb57 100644 --- a/lib/libcrypto/man/BN_add_word.3 +++ b/lib/libcrypto/man/BN_add_word.3 @@ -1,4 +1,4 @@ -.Dd $Mdocdate: February 23 2015 $ +.Dd $Mdocdate: July 5 2016 $ .Dt BN_ADD_WORD 3 .Os .Sh NAME @@ -75,7 +75,8 @@ returns the remainder of .Fa a divided by .Fa w -.Pq Li a%w . +.Pq Li a%w +or (BN_ULONG)-1 on error. .Pp For .Fn BN_div_word diff --git a/lib/libssl/src/crypto/bn/bn_prime.c b/lib/libssl/src/crypto/bn/bn_prime.c index b1aba663dfc..fb39756de24 100644 --- a/lib/libssl/src/crypto/bn/bn_prime.c +++ b/lib/libssl/src/crypto/bn/bn_prime.c @@ -1,4 +1,4 @@ -/* $OpenBSD: bn_prime.c,v 1.14 2015/10/21 19:02:22 miod Exp $ */ +/* $OpenBSD: bn_prime.c,v 1.15 2016/07/05 02:54:35 bcook Exp $ */ /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) * All rights reserved. * @@ -277,9 +277,13 @@ BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx_passed, /* a is even => a is prime if and only if a == 2 */ return BN_is_word(a, 2); if (do_trial_division) { - for (i = 1; i < NUMPRIMES; i++) - if (BN_mod_word(a, primes[i]) == 0) + for (i = 1; i < NUMPRIMES; i++) { + BN_ULONG mod = BN_mod_word(a, primes[i]); + if (mod == (BN_ULONG)-1) + goto err; + if (mod == 0) return 0; + } if (!BN_GENCB_call(cb, 1, -1)) goto err; } @@ -398,8 +402,12 @@ again: if (!BN_rand(rnd, bits, 1, 1)) return (0); /* we now have a random number 'rand' to test. */ - for (i = 1; i < NUMPRIMES; i++) - mods[i] = (prime_t)BN_mod_word(rnd, (BN_ULONG)primes[i]); + for (i = 1; i < NUMPRIMES; i++) { + BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]); + if (mod == (BN_ULONG)-1) + return (0); + mods[i] = (prime_t)mod; + } maxdelta = BN_MASK2 - primes[NUMPRIMES - 1]; delta = 0; loop: @@ -452,7 +460,10 @@ probable_prime_dh(BIGNUM *rnd, int bits, const BIGNUM *add, const BIGNUM *rem, loop: for (i = 1; i < NUMPRIMES; i++) { /* check that rnd is a prime */ - if (BN_mod_word(rnd, (BN_ULONG)primes[i]) <= 1) { + BN_LONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]); + if (mod == (BN_ULONG)-1) + goto err; + if (mod <= 1) { if (!BN_add(rnd, rnd, add)) goto err; goto loop; @@ -514,8 +525,11 @@ loop: /* check that p and q are prime */ /* check that for p and q * gcd(p-1,primes) == 1 (except for 2) */ - if ((BN_mod_word(p, (BN_ULONG)primes[i]) == 0) || - (BN_mod_word(q, (BN_ULONG)primes[i]) == 0)) { + BN_ULONG pmod = BN_mod_word(p, (BN_ULONG)primes[i]); + BN_ULONG qmod = BN_mod_word(q, (BN_ULONG)primes[i]); + if (pmod == (BN_ULONG)-1 || qmod == (BN_ULONG)-1) + goto err; + if (pmod == 0 || qmod == 0) { if (!BN_add(p, p, padd)) goto err; if (!BN_add(q, q, qadd)) diff --git a/lib/libssl/src/crypto/bn/bn_word.c b/lib/libssl/src/crypto/bn/bn_word.c index c4c6754c374..71654586a1b 100644 --- a/lib/libssl/src/crypto/bn/bn_word.c +++ b/lib/libssl/src/crypto/bn/bn_word.c @@ -1,4 +1,4 @@ -/* $OpenBSD: bn_word.c,v 1.12 2014/07/11 08:44:48 jsing Exp $ */ +/* $OpenBSD: bn_word.c,v 1.13 2016/07/05 02:54:35 bcook Exp $ */ /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) * All rights reserved. * @@ -73,6 +73,20 @@ BN_mod_word(const BIGNUM *a, BN_ULONG w) if (w == 0) return (BN_ULONG) - 1; +#ifndef BN_ULLONG + /* If |w| is too long and we don't have |BN_ULLONG| then we need to fall back + * to using |BN_div_word|. */ + if (w > ((BN_ULONG)1 << BN_BITS4)) { + BIGNUM *tmp = BN_dup(a); + if (tmp == NULL) { + return (BN_ULONG)-1; + } + ret = BN_div_word(tmp, w); + BN_free(tmp); + return ret; + } +#endif + bn_check_top(a); w &= BN_MASK2; for (i = a->top - 1; i >= 0; i--) { diff --git a/lib/libssl/src/crypto/dh/dh_check.c b/lib/libssl/src/crypto/dh/dh_check.c index 93e1003bd64..a6010f0a6dc 100644 --- a/lib/libssl/src/crypto/dh/dh_check.c +++ b/lib/libssl/src/crypto/dh/dh_check.c @@ -1,4 +1,4 @@ -/* $OpenBSD: dh_check.c,v 1.15 2015/02/07 13:19:15 doug Exp $ */ +/* $OpenBSD: dh_check.c,v 1.16 2016/07/05 02:54:35 bcook Exp $ */ /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) * All rights reserved. * @@ -89,10 +89,14 @@ DH_check(const DH *dh, int *ret) if (BN_is_word(dh->g, DH_GENERATOR_2)) { l = BN_mod_word(dh->p, 24); + if (l == (BN_ULONG)-1) + goto err; if (l != 11) *ret |= DH_NOT_SUITABLE_GENERATOR; } else if (BN_is_word(dh->g, DH_GENERATOR_5)) { l = BN_mod_word(dh->p, 10); + if (l == (BN_ULONG)-1) + goto err; if (l != 3 && l != 7) *ret |= DH_NOT_SUITABLE_GENERATOR; } else diff --git a/regress/lib/libcrypto/bn/general/bntest.c b/regress/lib/libcrypto/bn/general/bntest.c index c6bd788b541..1d541778e36 100644 --- a/regress/lib/libcrypto/bn/general/bntest.c +++ b/regress/lib/libcrypto/bn/general/bntest.c @@ -514,7 +514,7 @@ int test_div_word(BIO *bp) { BIGNUM a, b; - BN_ULONG r, s; + BN_ULONG r, rmod, s; int i; int rc = 1; @@ -523,14 +523,34 @@ test_div_word(BIO *bp) for (i = 0; i < num0; i++) { do { - BN_bntest_rand(&a, 512, -1, 0); - BN_bntest_rand(&b, BN_BITS2, -1, 0); + if (!BN_bntest_rand(&a, 512, -1, 0) || + !BN_bntest_rand(&b, BN_BITS2, -1, 0)) { + rc = 0; + break; + } s = b.d[0]; } while (!s); - BN_copy(&b, &a); + if (!BN_copy(&b, &a)) { + rc = 0; + break; + } + + s = b.d[0]; + rmod = BN_mod_word(&b, s); r = BN_div_word(&b, s); + if (r == (BN_ULONG)-1 || rmod == (BN_ULONG)-1) { + rc = 0; + break; + } + + if (rmod != r) { + fprintf(stderr, "Mod (word) test failed!\n"); + rc = 0; + break; + } + if (bp != NULL) { if (!results) { BN_print(bp, &a); -- 2.20.1