From: Bodo Möller <bodo@openssl.org>
Date: Mon, 18 Sep 2006 14:00:49 +0000 (+0000)
Subject: Ensure that the addition mods[i]+delta cannot overflow in probable_prime().
X-Git-Tag: OpenSSL_0_9_8k^2~1142
X-Git-Url: https://git.openssl.org/gitweb/?p=openssl.git;a=commitdiff_plain;h=a53cdc5b0834dd23072ea20e546d55ca4f43a0c8;ds=sidebyside

Ensure that the addition mods[i]+delta cannot overflow in probable_prime().

[Problem pointed out by Adam Young <adamy (at) acm.org>]
---

diff --git a/crypto/bn/bn_prime.c b/crypto/bn/bn_prime.c
index d57f658211..5bab019553 100644
--- a/crypto/bn/bn_prime.c
+++ b/crypto/bn/bn_prime.c
@@ -378,13 +378,14 @@ static int probable_prime(BIGNUM *rnd, int bits)
 	{
 	int i;
 	BN_ULONG mods[NUMPRIMES];
-	BN_ULONG delta,d;
+	BN_ULONG delta,maxdelta;
 
 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]=BN_mod_word(rnd,(BN_ULONG)primes[i]);
+	maxdelta=BN_MASK2 - primes[NUMPRIMES-1];
 	delta=0;
 	loop: for (i=1; i<NUMPRIMES; i++)
 		{
@@ -392,12 +393,8 @@ again:
 		 * that gcd(rnd-1,primes) == 1 (except for 2) */
 		if (((mods[i]+delta)%primes[i]) <= 1)
 			{
-			d=delta;
 			delta+=2;
-			/* perhaps need to check for overflow of
-			 * delta (but delta can be up to 2^32)
-			 * 21-May-98 eay - added overflow check */
-			if (delta < d) goto again;
+			if (delta > maxdelta) goto again;
 			goto loop;
 			}
 		}