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@

8 files changed, 111 insertions, 26 deletions

diff --git a/src/lib/libcrypto/bn/bn_prime.c b/src/lib/libcrypto/bn/bn_prime.c
index b1aba663df..fb39756de2 100644
--- a/src/lib/libcrypto/bn/bn_prime.c
+++ b/src/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/src/lib/libcrypto/bn/bn_word.c b/src/lib/libcrypto/bn/bn_word.c
index c4c6754c37..71654586a1 100644
--- a/src/lib/libcrypto/bn/bn_word.c
+++ b/src/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/src/lib/libcrypto/dh/dh_check.c b/src/lib/libcrypto/dh/dh_check.c
index 93e1003bd6..a6010f0a6d 100644
--- a/src/lib/libcrypto/dh/dh_check.c
+++ b/src/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/src/lib/libcrypto/man/BN_add_word.3 b/src/lib/libcrypto/man/BN_add_word.3
index 930aae4d32..16f2a17eb5 100644
--- a/src/lib/libcrypto/man/BN_add_word.3
+++ b/src/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/src/lib/libssl/src/crypto/bn/bn_prime.c b/src/lib/libssl/src/crypto/bn/bn_prime.c
index b1aba663df..fb39756de2 100644
--- a/src/lib/libssl/src/crypto/bn/bn_prime.c
+++ b/src/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/src/lib/libssl/src/crypto/bn/bn_word.c b/src/lib/libssl/src/crypto/bn/bn_word.c
index c4c6754c37..71654586a1 100644
--- a/src/lib/libssl/src/crypto/bn/bn_word.c
+++ b/src/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/src/lib/libssl/src/crypto/dh/dh_check.c b/src/lib/libssl/src/crypto/dh/dh_check.c
index 93e1003bd6..a6010f0a6d 100644
--- a/src/lib/libssl/src/crypto/dh/dh_check.c
+++ b/src/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/src/regress/lib/libcrypto/bn/general/bntest.c b/src/regress/lib/libcrypto/bn/general/bntest.c
index c6bd788b54..1d541778e3 100644
--- a/src/regress/lib/libcrypto/bn/general/bntest.c
+++ b/src/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);