Re: libcrypto: fix BN_mod_word bug

[Bob Beck]

ok beck@, with an appropriate commit message

On Mon, Jul 04, 2016 at 06:59:28PM -0500, Brent Cook wrote:
> I copied some of the commit text here from BoringSSL, but it's wrong for 
> LibreSSL it seems.
> 
> BN_ULLONG is not defined on all 64-bit systems as far as I can tell. So, this 
> fix is more widely applicable than Win64 for LibreSSL.
> 
> Any comments?
> 
>  - Brent
> 
> > On Jun 30, 2016, at 8:40 AM, Brent Cook  wrote:
> > 
> > On systems where we do not have BN_ULLONG (notably Win64), BN_mod_word()
> > can return incorrect results if the supplied modulus is too big.
> > 
> > Note now that BN_mod_word may fail, like BN_div_word. Handle this
> > properly and document in 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
> > 
> > diff --git a/src/lib/libcrypto/man/BN_add_word.3 
> > b/src/lib/libcrypto/man/BN_add_word.3
> > index eb5874a..66fdc0a 100644
> > --- a/src/lib/libcrypto/man/BN_add_word.3
> > +++ b/src/lib/libcrypto/man/BN_add_word.3
> > @@ -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 09af6a1..1dd0153 100644
> > --- a/src/lib/libssl/src/crypto/bn/bn_prime.c
> > +++ b/src/lib/libssl/src/crypto/bn/bn_prime.c
> > @@ -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 897b06d..acc7032 100644
> > --- a/src/lib/libssl/src/crypto/bn/bn_word.c
> > +++ b/src/lib/libssl/src/crypto/bn/bn_word.c
> > @@ -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

Re: libcrypto: fix BN_mod_word bug

[Brent Cook]

I copied some of the commit text here from BoringSSL, but it's wrong for 
LibreSSL it seems.

BN_ULLONG is not defined on all 64-bit systems as far as I can tell. So, this 
fix is more widely applicable than Win64 for LibreSSL.

Any comments?

 - Brent

> On Jun 30, 2016, at 8:40 AM, Brent Cook  wrote:
> 
> On systems where we do not have BN_ULLONG (notably Win64), BN_mod_word()
> can return incorrect results if the supplied modulus is too big.
> 
> Note now that BN_mod_word may fail, like BN_div_word. Handle this
> properly and document in 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
> 
> diff --git a/src/lib/libcrypto/man/BN_add_word.3 
> b/src/lib/libcrypto/man/BN_add_word.3
> index eb5874a..66fdc0a 100644
> --- a/src/lib/libcrypto/man/BN_add_word.3
> +++ b/src/lib/libcrypto/man/BN_add_word.3
> @@ -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 09af6a1..1dd0153 100644
> --- a/src/lib/libssl/src/crypto/bn/bn_prime.c
> +++ b/src/lib/libssl/src/crypto/bn/bn_prime.c
> @@ -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 897b06d..acc7032 100644
> --- a/src/lib/libssl/src/crypto/bn/bn_word.c
> +++ b/src/lib/libssl/src/crypto/bn/bn_word.c
> @@ -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/cryp

libcrypto: fix BN_mod_word bug

[Brent Cook]

On systems where we do not have BN_ULLONG (notably Win64), BN_mod_word()
can return incorrect results if the supplied modulus is too big.

Note now that BN_mod_word may fail, like BN_div_word. Handle this
properly and document in 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

diff --git a/src/lib/libcrypto/man/BN_add_word.3 
b/src/lib/libcrypto/man/BN_add_word.3
index eb5874a..66fdc0a 100644
--- a/src/lib/libcrypto/man/BN_add_word.3
+++ b/src/lib/libcrypto/man/BN_add_word.3
@@ -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 09af6a1..1dd0153 100644
--- a/src/lib/libssl/src/crypto/bn/bn_prime.c
+++ b/src/lib/libssl/src/crypto/bn/bn_prime.c
@@ -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 897b06d..acc7032 100644
--- a/src/lib/libssl/src/crypto/bn/bn_word.c
+++ b/src/lib/libssl/src/crypto/bn/bn_word.c
@@ -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 ad827dd..c34511d 100644
--- a/src/lib/libssl/src/crypto/dh/dh_check.c
+++ b/src/lib/libssl/src/crypto/dh/dh_check.c
@@ -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)
+   got