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.

diff --git a/crypto/bn/bn.h b/crypto/bn/bn.h
index a01f193daaf212b8b16333280e2f465eb73032ec..dac794b600b78cfc66c48df5aab6eb745cf6b674 100644 (file)
--- 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 3f607cd53249b3e4ff5695933a9ed3b907852c30..0cc20d9239887ec7624a3ab7982f82ae64ca331b 100644 (file)
--- 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 8831daa390a7be5cdbb0bc7815cfb6ebe0efb6b1..3b4b3f0d38350d642c0e83b6597e218dea3766da 100644 (file)
--- 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 a241150157ca385d65306105c645067023103023..7aa2a33d2d092e803024f00467558be7ff5b3257 100644 (file)
--- 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)
                {