11 files changed, 158 insertions, 58 deletions

diff --git a/src/lib/libcrypto/bn/Makefile.ssl b/src/lib/libcrypto/bn/Makefile.ssl
index 17b72d577f..526d7adb5c 100644
--- a/src/lib/libcrypto/bn/Makefile.ssl
+++ b/src/lib/libcrypto/bn/Makefile.ssl
@@ -68,7 +68,8 @@ bnbug: bnbug.c ../../libcrypto.a top
 
 lib:    $(LIBOBJ)
         $(AR) $(LIB) $(LIBOBJ)
-        $(RANLIB) $(LIB)
+        @echo You may get an error following this line.  Please ignore.
+        - $(RANLIB) $(LIB)
         @touch lib
 
 # elf
diff --git a/src/lib/libcrypto/bn/asm/mips3.s b/src/lib/libcrypto/bn/asm/mips3.s
index 2df4dcd4b0..45786c00a5 100644
--- a/src/lib/libcrypto/bn/asm/mips3.s
+++ b/src/lib/libcrypto/bn/asm/mips3.s
@@ -586,13 +586,13 @@ LEAF(bn_div_3_words)
         ld      a0,(a3)
         move    ta2,a1
         ld      a1,-8(a3)
-        move    ta3,ra
-        move    v1,zero
+        bne     a0,a2,.L_bn_div_3_words_proceed
         li      v0,-1
-        beq     a0,a2,.L_bn_div_3_words_skip_div
+        jr      ra
+.L_bn_div_3_words_proceed:
+        move    ta3,ra
         bal     bn_div_words
         move    ra,ta3
-.L_bn_div_3_words_skip_div:
         dmultu  ta2,v0
         ld      t2,-16(a3)
         move    ta0,zero
diff --git a/src/lib/libcrypto/bn/asm/pa-risc2.s b/src/lib/libcrypto/bn/asm/pa-risc2.s
index 7239aa2c76..af9730d062 100644
--- a/src/lib/libcrypto/bn/asm/pa-risc2.s
+++ b/src/lib/libcrypto/bn/asm/pa-risc2.s
@@ -1611,7 +1611,7 @@ bn_mul_comba4
         .IMPORT $global$,DATA
         .SPACE  $TEXT$
         .SUBSPA $CODE$
-        .SUBSPA $LIT$,QUAD=0,ALIGN=8,ACCESS=0x2c,SORT=16
+        .SUBSPA $LIT$,ACCESS=0x2c
 C$7
         .ALIGN  8
         .STRINGZ        "Division would overflow (%d)\n"
diff --git a/src/lib/libcrypto/bn/asm/pa-risc2W.s b/src/lib/libcrypto/bn/asm/pa-risc2W.s
index 54b6606252..a99545754d 100644
--- a/src/lib/libcrypto/bn/asm/pa-risc2W.s
+++ b/src/lib/libcrypto/bn/asm/pa-risc2W.s
@@ -1598,7 +1598,7 @@ bn_mul_comba4
         .IMPORT $global$,DATA
         .SPACE  $TEXT$
         .SUBSPA $CODE$
-        .SUBSPA $LIT$,QUAD=0,ALIGN=8,ACCESS=0x2c,SORT=16
+        .SUBSPA $LIT$,ACCESS=0x2c
 C$4
         .ALIGN  8
         .STRINGZ        "Division would overflow (%d)\n"
diff --git a/src/lib/libcrypto/bn/bn.h b/src/lib/libcrypto/bn/bn.h
index 1eb8395b25..b232c2ceae 100644
--- a/src/lib/libcrypto/bn/bn.h
+++ b/src/lib/libcrypto/bn/bn.h
@@ -239,7 +239,7 @@ typedef struct bignum_st
         } BIGNUM;
 
 /* Used for temp variables */
-#define BN_CTX_NUM      12
+#define BN_CTX_NUM      16
 #define BN_CTX_NUM_POS  12
 typedef struct bignum_ctx
         {
@@ -328,6 +328,7 @@ BIGNUM *BN_CTX_get(BN_CTX *ctx);
 void    BN_CTX_end(BN_CTX *ctx);
 int     BN_rand(BIGNUM *rnd, int bits, int top,int bottom);
 int     BN_pseudo_rand(BIGNUM *rnd, int bits, int top,int bottom);
+int     BN_rand_range(BIGNUM *rnd, BIGNUM *range);
 int     BN_num_bits(const BIGNUM *a);
 int     BN_num_bits_word(BN_ULONG);
 BIGNUM *BN_new(void);
@@ -467,6 +468,8 @@ BN_ULONG bn_sub_words(BN_ULONG *rp, BN_ULONG *ap, BN_ULONG *bp,int num);
 # define bn_dump(a,b)
 #endif
 
+int BN_bntest_rand(BIGNUM *rnd, int bits, int top,int bottom);
+
 /* BEGIN ERROR CODES */
 /* The following lines are auto generated by the script mkerr.pl. Any changes
  * made after this point may be overwritten when the script is next run.
@@ -493,16 +496,19 @@ BN_ULONG bn_sub_words(BN_ULONG *rp, BN_ULONG *ap, BN_ULONG *bp,int num);
 #define BN_F_BN_MPI2BN                                   112
 #define BN_F_BN_NEW                                      113
 #define BN_F_BN_RAND                                     114
+#define BN_F_BN_RAND_RANGE                               122
 #define BN_F_BN_USUB                                     115
 
 /* Reason codes. */
 #define BN_R_ARG2_LT_ARG3                                100
 #define BN_R_BAD_RECIPROCAL                              101
+#define BN_R_BIGNUM_TOO_LONG                             114
 #define BN_R_CALLED_WITH_EVEN_MODULUS                    102
 #define BN_R_DIV_BY_ZERO                                 103
 #define BN_R_ENCODING_ERROR                              104
 #define BN_R_EXPAND_ON_STATIC_BIGNUM_DATA                105
 #define BN_R_INVALID_LENGTH                              106
+#define BN_R_INVALID_RANGE                               115
 #define BN_R_NOT_INITIALIZED                             107
 #define BN_R_NO_INVERSE                                  108
 #define BN_R_TOO_MANY_TEMPORARY_VARIABLES                109
diff --git a/src/lib/libcrypto/bn/bn_div.c b/src/lib/libcrypto/bn/bn_div.c
index c3772c243b..c328b5b411 100644
--- a/src/lib/libcrypto/bn/bn_div.c
+++ b/src/lib/libcrypto/bn/bn_div.c
@@ -180,13 +180,13 @@ int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor,
 
         BN_CTX_start(ctx);
         tmp=BN_CTX_get(ctx);
-        tmp->neg=0;
         snum=BN_CTX_get(ctx);
         sdiv=BN_CTX_get(ctx);
         if (dv == NULL)
                 res=BN_CTX_get(ctx);
         else    res=dv;
-        if (res == NULL) goto err;
+        if (sdiv==NULL || res == NULL) goto err;
+        tmp->neg=0;
 
         /* First we normalise the numbers */
         norm_shift=BN_BITS2-((BN_num_bits(divisor))%BN_BITS2);
@@ -237,7 +237,8 @@ int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor,
         for (i=0; i<loop-1; i++)
                 {
                 BN_ULONG q,l0;
-#ifdef BN_DIV3W
+#if defined(BN_DIV3W) && !defined(NO_ASM)
+                BN_ULONG bn_div_3_words(BN_ULONG*,BN_ULONG,BN_ULONG);
                 q=bn_div_3_words(wnump,d1,d0);
 #else
                 BN_ULONG n0,n1,rem=0;
diff --git a/src/lib/libcrypto/bn/bn_err.c b/src/lib/libcrypto/bn/bn_err.c
index 86550c4c21..adc6a214fc 100644
--- a/src/lib/libcrypto/bn/bn_err.c
+++ b/src/lib/libcrypto/bn/bn_err.c
@@ -84,6 +84,7 @@ static ERR_STRING_DATA BN_str_functs[]=
 {ERR_PACK(0,BN_F_BN_MPI2BN,0),  "BN_mpi2bn"},
 {ERR_PACK(0,BN_F_BN_NEW,0),     "BN_new"},
 {ERR_PACK(0,BN_F_BN_RAND,0),    "BN_rand"},
+{ERR_PACK(0,BN_F_BN_RAND_RANGE,0),      "BN_rand_range"},
 {ERR_PACK(0,BN_F_BN_USUB,0),    "BN_usub"},
 {0,NULL}
         };
@@ -92,11 +93,13 @@ static ERR_STRING_DATA BN_str_reasons[]=
         {
 {BN_R_ARG2_LT_ARG3                       ,"arg2 lt arg3"},
 {BN_R_BAD_RECIPROCAL                     ,"bad reciprocal"},
+{BN_R_BIGNUM_TOO_LONG                    ,"bignum too long"},
 {BN_R_CALLED_WITH_EVEN_MODULUS           ,"called with even modulus"},
 {BN_R_DIV_BY_ZERO                        ,"div by zero"},
 {BN_R_ENCODING_ERROR                     ,"encoding error"},
 {BN_R_EXPAND_ON_STATIC_BIGNUM_DATA       ,"expand on static bignum data"},
 {BN_R_INVALID_LENGTH                     ,"invalid length"},
+{BN_R_INVALID_RANGE                      ,"invalid range"},
 {BN_R_NOT_INITIALIZED                    ,"not initialized"},
 {BN_R_NO_INVERSE                         ,"no inverse"},
 {BN_R_TOO_MANY_TEMPORARY_VARIABLES       ,"too many temporary variables"},
diff --git a/src/lib/libcrypto/bn/bn_lib.c b/src/lib/libcrypto/bn/bn_lib.c
index b6b0ce4b3c..7767d65170 100644
--- a/src/lib/libcrypto/bn/bn_lib.c
+++ b/src/lib/libcrypto/bn/bn_lib.c
@@ -62,6 +62,7 @@
 #endif
 
 #include <assert.h>
+#include <limits.h>
 #include <stdio.h>
 #include "cryptlib.h"
 #include "bn_lcl.h"
@@ -319,6 +320,12 @@ BIGNUM *bn_expand2(BIGNUM *b, int words)
 
         if (words > b->dmax)
                 {
+                if (words > (INT_MAX/(4*BN_BITS2)))
+                        {
+                        BNerr(BN_F_BN_EXPAND2,BN_R_BIGNUM_TOO_LONG);
+                        return NULL;
+                        }
+                        
                 bn_check_top(b);        
                 if (BN_get_flags(b,BN_FLG_STATIC_DATA))
                         {
diff --git a/src/lib/libcrypto/bn/bn_rand.c b/src/lib/libcrypto/bn/bn_rand.c
index 21ecbc04ed..acd0619921 100644
--- a/src/lib/libcrypto/bn/bn_rand.c
+++ b/src/lib/libcrypto/bn/bn_rand.c
@@ -76,7 +76,7 @@ static int bnrand(int pseudorand, BIGNUM *rnd, int bits, int top, int bottom)
 
         bytes=(bits+7)/8;
         bit=(bits-1)%8;
-        mask=0xff<<bit;
+        mask=0xff<<(bit+1);
 
         buf=(unsigned char *)OPENSSL_malloc(bytes);
         if (buf == NULL)
@@ -100,25 +100,48 @@ static int bnrand(int pseudorand, BIGNUM *rnd, int bits, int top, int bottom)
                         goto err;
                 }
 
-        if (top)
+#if 1
+        if (pseudorand == 2)
                 {
-                if (bit == 0)
+                /* generate patterns that are more likely to trigger BN
+                   library bugs */
+                int i;
+                unsigned char c;
+
+                for (i = 0; i < bytes; i++)
+                        {
+                        RAND_pseudo_bytes(&c, 1);
+                        if (c >= 128 && i > 0)
+                                buf[i] = buf[i-1];
+                        else if (c < 42)
+                                buf[i] = 0;
+                        else if (c < 84)
+                                buf[i] = 255;
+                        }
+                }
+#endif
+
+        if (top != -1)
+                {
+                if (top)
                         {
-                        buf[0]=1;
-                        buf[1]|=0x80;
+                        if (bit == 0)
+                                {
+                                buf[0]=1;
+                                buf[1]|=0x80;
+                                }
+                        else
+                                {
+                                buf[0]|=(3<<(bit-1));
+                                }
                         }
                 else
                         {
-                        buf[0]|=(3<<(bit-1));
-                        buf[0]&= ~(mask<<1);
+                        buf[0]|=(1<<bit);
                         }
                 }
-        else
-                {
-                buf[0]|=(1<<bit);
-                buf[0]&= ~(mask<<1);
-                }
-        if (bottom) /* set bottom bits to whatever odd is */
+        buf[0] &= ~mask;
+        if (bottom) /* set bottom bit if requested */
                 buf[bytes-1]|=1;
         if (!BN_bin2bn(buf,bytes,rnd)) goto err;
         ret=1;
@@ -140,3 +163,61 @@ int     BN_pseudo_rand(BIGNUM *rnd, int bits, int top, int bottom)
         {
         return bnrand(1, rnd, bits, top, bottom);
         }
+
+#if 1
+int     BN_bntest_rand(BIGNUM *rnd, int bits, int top, int bottom)
+        {
+        return bnrand(2, rnd, bits, top, bottom);
+        }
+#endif
+
+/* random number r:  0 <= r < range */
+int     BN_rand_range(BIGNUM *r, BIGNUM *range)
+        {
+        int n;
+
+        if (range->neg || BN_is_zero(range))
+                {
+                BNerr(BN_F_BN_RAND_RANGE, BN_R_INVALID_RANGE);
+                return 0;
+                }
+
+        n = BN_num_bits(range); /* n > 0 */
+
+        if (n == 1)
+                {
+                if (!BN_zero(r)) return 0;
+                }
+        else if (BN_is_bit_set(range, n - 2))
+                {
+                do
+                        {
+                        /* range = 11..._2, so each iteration succeeds with probability >= .75 */
+                        if (!BN_rand(r, n, -1, 0)) return 0;
+                        }
+                while (BN_cmp(r, range) >= 0);
+                }
+        else
+                {
+                /* range = 10..._2,
+                 * so  3*range (= 11..._2)  is exactly one bit longer than  range */
+                do
+                        {
+                        if (!BN_rand(r, n + 1, -1, 0)) return 0;
+                        /* If  r < 3*range,  use  r := r MOD range
+                         * (which is either  r, r - range,  or  r - 2*range).
+                         * Otherwise, iterate once more.
+                         * Since  3*range = 11..._2, each iteration succeeds with
+                         * probability >= .75. */
+                        if (BN_cmp(r ,range) >= 0)
+                                {
+                                if (!BN_sub(r, r, range)) return 0;
+                                if (BN_cmp(r, range) >= 0)
+                                        if (!BN_sub(r, r, range)) return 0;
+                                }
+                        }
+                while (BN_cmp(r, range) >= 0);
+                }
+
+        return 1;
+        }
diff --git a/src/lib/libcrypto/bn/bn_shift.c b/src/lib/libcrypto/bn/bn_shift.c
index 0883247384..c2608f9f4a 100644
--- a/src/lib/libcrypto/bn/bn_shift.c
+++ b/src/lib/libcrypto/bn/bn_shift.c
@@ -172,6 +172,11 @@ int BN_rshift(BIGNUM *r, BIGNUM *a, int n)
                 r->neg=a->neg;
                 if (bn_wexpand(r,a->top-nw+1) == NULL) return(0);
                 }
+        else
+                {
+                if (n == 0)
+                        return 1; /* or the copying loop will go berserk */
+                }
 
         f= &(a->d[nw]);
         t=r->d;
diff --git a/src/lib/libcrypto/bn/bntest.c b/src/lib/libcrypto/bn/bntest.c
index 0a97af69c5..af0c2629e8 100644
--- a/src/lib/libcrypto/bn/bntest.c
+++ b/src/lib/libcrypto/bn/bntest.c
@@ -107,11 +107,9 @@ static const char rnd_seed[] = "string to make the random number generator think
 static void message(BIO *out, char *m)
         {
         fprintf(stderr, "test %s\n", m);
-#if defined(linux) || defined(__FreeBSD__) /* can we use GNU bc features? */
         BIO_puts(out, "print \"test ");
         BIO_puts(out, m);
         BIO_puts(out, "\\n\"\n");
-#endif
         }
 
 int main(int argc, char *argv[])
@@ -122,9 +120,7 @@ int main(int argc, char *argv[])
 
         results = 0;
 
-        RAND_seed(rnd_seed, sizeof rnd_seed); /* or BN_rand may fail, and we don't
-                                               * even check its return value
-                                               * (which we should) */
+        RAND_seed(rnd_seed, sizeof rnd_seed); /* or BN_generate_prime may fail */
 
         argc--;
         argv++;
@@ -253,10 +249,10 @@ int test_add(BIO *bp)
         BN_init(&b);
         BN_init(&c);
 
-        BN_rand(&a,512,0,0);
+        BN_bntest_rand(&a,512,0,0);
         for (i=0; i<num0; i++)
                 {
-                BN_rand(&b,450+i,0,0);
+                BN_bntest_rand(&b,450+i,0,0);
                 a.neg=rand_neg();
                 b.neg=rand_neg();
                 if (bp == NULL)
@@ -305,14 +301,14 @@ int test_sub(BIO *bp)
                 {
                 if (i < num1)
                         {
-                        BN_rand(&a,512,0,0);
+                        BN_bntest_rand(&a,512,0,0);
                         BN_copy(&b,&a);
                         if (BN_set_bit(&a,i)==0) return(0);
                         BN_add_word(&b,i);
                         }
                 else
                         {
-                        BN_rand(&b,400+i-num1,0,0);
+                        BN_bntest_rand(&b,400+i-num1,0,0);
                         a.neg=rand_neg();
                         b.neg=rand_neg();
                         }
@@ -362,13 +358,13 @@ int test_div(BIO *bp, BN_CTX *ctx)
                 {
                 if (i < num1)
                         {
-                        BN_rand(&a,400,0,0);
+                        BN_bntest_rand(&a,400,0,0);
                         BN_copy(&b,&a);
                         BN_lshift(&a,&a,i);
                         BN_add_word(&a,i);
                         }
                 else
-                        BN_rand(&b,50+3*(i-num1),0,0);
+                        BN_bntest_rand(&b,50+3*(i-num1),0,0);
                 a.neg=rand_neg();
                 b.neg=rand_neg();
                 if (bp == NULL)
@@ -432,13 +428,13 @@ int test_div_recp(BIO *bp, BN_CTX *ctx)
                 {
                 if (i < num1)
                         {
-                        BN_rand(&a,400,0,0);
+                        BN_bntest_rand(&a,400,0,0);
                         BN_copy(&b,&a);
                         BN_lshift(&a,&a,i);
                         BN_add_word(&a,i);
                         }
                 else
-                        BN_rand(&b,50+3*(i-num1),0,0);
+                        BN_bntest_rand(&b,50+3*(i-num1),0,0);
                 a.neg=rand_neg();
                 b.neg=rand_neg();
                 BN_RECP_CTX_set(&recp,&b,ctx);
@@ -509,11 +505,11 @@ int test_mul(BIO *bp)
                 {
                 if (i <= num1)
                         {
-                        BN_rand(&a,100,0,0);
-                        BN_rand(&b,100,0,0);
+                        BN_bntest_rand(&a,100,0,0);
+                        BN_bntest_rand(&b,100,0,0);
                         }
                 else
-                        BN_rand(&b,i-num1,0,0);
+                        BN_bntest_rand(&b,i-num1,0,0);
                 a.neg=rand_neg();
                 b.neg=rand_neg();
                 if (bp == NULL)
@@ -562,7 +558,7 @@ int test_sqr(BIO *bp, BN_CTX *ctx)
 
         for (i=0; i<num0; i++)
                 {
-                BN_rand(&a,40+i*10,0,0);
+                BN_bntest_rand(&a,40+i*10,0,0);
                 a.neg=rand_neg();
                 if (bp == NULL)
                         for (j=0; j<100; j++)
@@ -613,15 +609,15 @@ int test_mont(BIO *bp, BN_CTX *ctx)
 
         mont=BN_MONT_CTX_new();
 
-        BN_rand(&a,100,0,0); /**/
-        BN_rand(&b,100,0,0); /**/
+        BN_bntest_rand(&a,100,0,0); /**/
+        BN_bntest_rand(&b,100,0,0); /**/
         for (i=0; i<num2; i++)
                 {
                 int bits = (200*(i+1))/num2;
 
                 if (bits == 0)
                         continue;
-                BN_rand(&n,bits,0,1);
+                BN_bntest_rand(&n,bits,0,1);
                 BN_MONT_CTX_set(mont,&n,ctx);
 
                 BN_to_montgomery(&A,&a,mont,ctx);
@@ -683,10 +679,10 @@ int test_mod(BIO *bp, BN_CTX *ctx)
         d=BN_new();
         e=BN_new();
 
-        BN_rand(a,1024,0,0); /**/
+        BN_bntest_rand(a,1024,0,0); /**/
         for (i=0; i<num0; i++)
                 {
-                BN_rand(b,450+i*10,0,0); /**/
+                BN_bntest_rand(b,450+i*10,0,0); /**/
                 a->neg=rand_neg();
                 b->neg=rand_neg();
                 if (bp == NULL)
@@ -732,11 +728,11 @@ int test_mod_mul(BIO *bp, BN_CTX *ctx)
         d=BN_new();
         e=BN_new();
 
-        BN_rand(c,1024,0,0); /**/
+        BN_bntest_rand(c,1024,0,0); /**/
         for (i=0; i<num0; i++)
                 {
-                BN_rand(a,475+i*10,0,0); /**/
-                BN_rand(b,425+i*11,0,0); /**/
+                BN_bntest_rand(a,475+i*10,0,0); /**/
+                BN_bntest_rand(b,425+i*11,0,0); /**/
                 a->neg=rand_neg();
                 b->neg=rand_neg();
         /*      if (bp == NULL)
@@ -794,11 +790,11 @@ int test_mod_exp(BIO *bp, BN_CTX *ctx)
         d=BN_new();
         e=BN_new();
 
-        BN_rand(c,30,0,1); /* must be odd for montgomery */
+        BN_bntest_rand(c,30,0,1); /* must be odd for montgomery */
         for (i=0; i<num2; i++)
                 {
-                BN_rand(a,20+i*5,0,0); /**/
-                BN_rand(b,2+i,0,0); /**/
+                BN_bntest_rand(a,20+i*5,0,0); /**/
+                BN_bntest_rand(b,2+i,0,0); /**/
 
                 if (!BN_mod_exp(d,a,b,c,ctx))
                         return(00);
@@ -848,8 +844,8 @@ int test_exp(BIO *bp, BN_CTX *ctx)
 
         for (i=0; i<num2; i++)
                 {
-                BN_rand(a,20+i*5,0,0); /**/
-                BN_rand(b,2+i,0,0); /**/
+                BN_bntest_rand(a,20+i*5,0,0); /**/
+                BN_bntest_rand(b,2+i,0,0); /**/
 
                 if (!BN_exp(d,a,b,ctx))
                         return(00);
@@ -899,7 +895,7 @@ int test_lshift(BIO *bp,BN_CTX *ctx,BIGNUM *a_)
         else
             {
             a=BN_new();
-            BN_rand(a,200,0,0); /**/
+            BN_bntest_rand(a,200,0,0); /**/
             a->neg=rand_neg();
             }
         for (i=0; i<num0; i++)
@@ -951,7 +947,7 @@ int test_lshift1(BIO *bp)
         b=BN_new();
         c=BN_new();
 
-        BN_rand(a,200,0,0); /**/
+        BN_bntest_rand(a,200,0,0); /**/
         a->neg=rand_neg();
         for (i=0; i<num0; i++)
                 {
@@ -995,7 +991,7 @@ int test_rshift(BIO *bp,BN_CTX *ctx)
         e=BN_new();
         BN_one(c);
 
-        BN_rand(a,200,0,0); /**/
+        BN_bntest_rand(a,200,0,0); /**/
         a->neg=rand_neg();
         for (i=0; i<num0; i++)
                 {
@@ -1038,7 +1034,7 @@ int test_rshift1(BIO *bp)
         b=BN_new();
         c=BN_new();
 
-        BN_rand(a,200,0,0); /**/
+        BN_bntest_rand(a,200,0,0); /**/
         a->neg=rand_neg();
         for (i=0; i<num0; i++)
                 {