Variety of belt-tightenings in the bignum code. (Please help test this!)

- Remove some unnecessary "+1"-like fudges. Sizes should be handled
  exactly, as enlarging size parameters causes needless bloat and may just
  make bugs less likely rather than fixing them: bn_expand() macro,
  bn_expand_internal(), and BN_sqr().
- Deprecate bn_dup_expand() - it's new since 0.9.7, unused, and not that
  useful.
- Remove unnecessary zeroing of unused bytes in bn_expand2().
- Rewrite BN_set_word() - it should be much simpler, the previous
  complexities probably date from old mismatched type issues.
- Add missing bn_check_top() macros in bn_word.c
- Improve some degenerate case handling in BN_[add|sub]_word(), add
  comments, and avoid a bignum expansion if an overflow isn't possible.

4 files changed, 48 insertions, 18 deletions

diff --git a/crypto/bn/bn.h b/crypto/bn/bn.h
index a01f193daa..dac794b600 100644
--- a/crypto/bn/bn.h
+++ b/crypto/bn/bn.h
@@ -617,10 +617,12 @@ const BIGNUM *BN_get0_nist_prime_521(void);
 /* library internal functions */
 
 #define bn_expand(a,bits) ((((((bits+BN_BITS2-1))/BN_BITS2)) <= (a)->dmax)?\
-	(a):bn_expand2((a),(bits)/BN_BITS2+1))
+	(a):bn_expand2((a),(bits+BN_BITS2-1)/BN_BITS2))
 #define bn_wexpand(a,words) (((words) <= (a)->dmax)?(a):bn_expand2((a),(words)))
 BIGNUM *bn_expand2(BIGNUM *a, int words);
-BIGNUM *bn_dup_expand(const BIGNUM *a, int words);
+#ifndef OPENSSL_NO_DEPRECATED
+BIGNUM *bn_dup_expand(const BIGNUM *a, int words); /* unused */
+#endif
 
 /* Bignum consistency macros
  * There is one "API" macro, bn_fix_top(), for stripping leading zeroes from
diff --git a/crypto/bn/bn_lib.c b/crypto/bn/bn_lib.c
index 3f607cd532..0cc20d9239 100644
--- a/crypto/bn/bn_lib.c
+++ b/crypto/bn/bn_lib.c
@@ -330,7 +330,7 @@ static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words)
 		BNerr(BN_F_BN_EXPAND_INTERNAL,BN_R_EXPAND_ON_STATIC_BIGNUM_DATA);
 		return(NULL);
 		}
-	a=A=(BN_ULONG *)OPENSSL_malloc(sizeof(BN_ULONG)*(words+1));
+	a=A=(BN_ULONG *)OPENSSL_malloc(sizeof(BN_ULONG)*words);
 	if (A == NULL)
 		{
 		BNerr(BN_F_BN_EXPAND_INTERNAL,ERR_R_MALLOC_FAILURE);
@@ -369,7 +369,7 @@ static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words)
 		}
 
 #else
-	memset(A,0,sizeof(BN_ULONG)*(words+1));
+	memset(A,0,sizeof(BN_ULONG)*words);
 	memcpy(A,b->d,sizeof(b->d[0])*b->top);
 #endif
 		
@@ -387,6 +387,7 @@ static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words)
  * while bn_dup_expand() makes sure allocation is made only once.
  */
 
+#ifndef OPENSSL_NO_DEPRECATED
 BIGNUM *bn_dup_expand(const BIGNUM *b, int words)
 	{
 	BIGNUM *r = NULL;
@@ -430,6 +431,7 @@ BIGNUM *bn_dup_expand(const BIGNUM *b, int words)
 	bn_check_top(r);
 	return r;
 	}
+#endif
 
 /* This is an internal function that should not be used in applications.
  * It ensures that 'b' has enough room for a 'words' word number
@@ -439,9 +441,6 @@ BIGNUM *bn_dup_expand(const BIGNUM *b, int words)
 
 BIGNUM *bn_expand2(BIGNUM *b, int words)
 	{
-	BN_ULONG *A;
-	int i;
-
 	bn_check_top(b);
 
 	if (words > b->dmax)
@@ -453,10 +452,13 @@ BIGNUM *bn_expand2(BIGNUM *b, int words)
 		b->dmax=words;
 		}
 
+/* None of this should be necessary because of what b->top means! */
+#if 0
 	/* NB: bn_wexpand() calls this only if the BIGNUM really has to grow */
 	if (b->top < b->dmax)
 		{
-		A = &(b->d[b->top]);
+		int i;
+		BN_ULONG *A = &(b->d[b->top]);
 		for (i=(b->dmax - b->top)>>3; i>0; i--,A+=8)
 			{
 			A[0]=0; A[1]=0; A[2]=0; A[3]=0;
@@ -466,6 +468,7 @@ BIGNUM *bn_expand2(BIGNUM *b, int words)
 			A[0]=0;
 		assert(A == &(b->d[b->dmax]));
 		}
+#endif
 	bn_check_top(b);
 	return b;
 	}
@@ -632,6 +635,7 @@ BN_ULONG BN_get_word(const BIGNUM *a)
 	return(ret);
 	}
 
+#if 0 /* a->d[0] is a BN_ULONG, w is a BN_ULONG, what's the big deal? */
 int BN_set_word(BIGNUM *a, BN_ULONG w)
 	{
 	int i,n;
@@ -660,6 +664,18 @@ int BN_set_word(BIGNUM *a, BN_ULONG w)
 	bn_check_top(a);
 	return(1);
 	}
+#else
+int BN_set_word(BIGNUM *a, BN_ULONG w)
+	{
+	bn_check_top(a);
+	if (bn_expand(a,(int)sizeof(BN_ULONG)*8) == NULL) return(0);
+	a->neg = 0;
+	a->d[0] = w;
+	a->top = (w ? 1 : 0);
+	bn_check_top(a);
+	return(1);
+	}
+#endif
 
 BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret)
 	{
diff --git a/crypto/bn/bn_sqr.c b/crypto/bn/bn_sqr.c
index 8831daa390..3b4b3f0d38 100644
--- a/crypto/bn/bn_sqr.c
+++ b/crypto/bn/bn_sqr.c
@@ -86,7 +86,7 @@ int BN_sqr(BIGNUM *r, const BIGNUM *a, BN_CTX *ctx)
 	if (!rr || !tmp) goto err;
 
 	max = 2 * al; /* Non-zero (from above) */
-	if (bn_wexpand(rr,max+1) == NULL) goto err;
+	if (bn_wexpand(rr,max) == NULL) goto err;
 
 	if (al == 4)
 		{
diff --git a/crypto/bn/bn_word.c b/crypto/bn/bn_word.c
index a241150157..7aa2a33d2d 100644
--- a/crypto/bn/bn_word.c
+++ b/crypto/bn/bn_word.c
@@ -69,6 +69,7 @@ BN_ULONG BN_mod_word(const BIGNUM *a, BN_ULONG w)
 #endif
 	int i;
 
+	bn_check_top(a);
 	w&=BN_MASK2;
 	for (i=a->top-1; i>=0; i--)
 		{
@@ -88,6 +89,7 @@ BN_ULONG BN_div_word(BIGNUM *a, BN_ULONG w)
 	BN_ULONG ret = 0;
 	int i;
 
+	bn_check_top(a);
 	w &= BN_MASK2;
 
 	if (!w)
@@ -116,11 +118,14 @@ int BN_add_word(BIGNUM *a, BN_ULONG w)
 	BN_ULONG l;
 	int i;
 
+	bn_check_top(a);
 	w &= BN_MASK2;
 
-	if (!w)
-		return 1;
-
+	/* degenerate case: w is zero */
+	if (!w) return 1;
+	/* degenerate case: a is zero */
+	if(BN_is_zero(a)) return BN_set_word(a, w);
+	/* handle 'a' when negative */
 	if (a->neg)
 		{
 		a->neg=0;
@@ -129,14 +134,17 @@ int BN_add_word(BIGNUM *a, BN_ULONG w)
 			a->neg=!(a->neg);
 		return(i);
 		}
-	if (bn_wexpand(a,a->top+1) == NULL) return(0);
+	/* Only expand (and risk failing) if it's possibly necessary */
+	if (((BN_ULONG)(a->d[a->top - 1] + 1) == 0) &&
+			(bn_wexpand(a,a->top+1) == NULL))
+		return(0);
 	i=0;
 	for (;;)
 		{
 		if (i >= a->top)
 			l=w;
 		else
-			l=(a->d[i]+(BN_ULONG)w)&BN_MASK2;
+			l=(a->d[i]+w)&BN_MASK2;
 		a->d[i]=l;
 		if (w > l)
 			w=1;
@@ -154,12 +162,15 @@ int BN_sub_word(BIGNUM *a, BN_ULONG w)
 	{
 	int i;
 
+	bn_check_top(a);
 	w &= BN_MASK2;
 
-	if (!w)
-		return 1;
-
-	if (BN_is_zero(a) || a->neg)
+	/* degenerate case: w is zero */
+	if (!w) return 1;
+	/* degenerate case: a is zero */
+	if(BN_is_zero(a)) return BN_set_word(a,w);
+	/* handle 'a' when negative */
+	if (a->neg)
 		{
 		a->neg=0;
 		i=BN_add_word(a,w);
@@ -198,6 +209,7 @@ int BN_mul_word(BIGNUM *a, BN_ULONG w)
 	{
 	BN_ULONG ll;
 
+	bn_check_top(a);
 	w&=BN_MASK2;
 	if (a->top)
 		{