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@

3 files changed, 42 insertions, 10 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