X-Git-Url: https://git.openssl.org/?p=openssl.git;a=blobdiff_plain;f=crypto%2Fbn%2Fbn_lib.c;h=789e9aa4fb6c59c81720d662439f2cfc916efbac;hp=130a9e2db401468e83ef2747031a4056defeb1f6;hb=df11e1e921f420f4fa911df15c887d9ad2740867;hpb=cbd48ba626845170ee2b70774e881a4b50a7369d diff --git a/crypto/bn/bn_lib.c b/crypto/bn/bn_lib.c index 130a9e2db4..789e9aa4fb 100644 --- a/crypto/bn/bn_lib.c +++ b/crypto/bn/bn_lib.c @@ -62,12 +62,15 @@ #endif #include +#include #include #include "cryptlib.h" #include "bn_lcl.h" const char *BN_version="Big Number" OPENSSL_VERSION_PTEXT; +/* This stuff appears to be completely unused, so is deprecated */ +#ifndef OPENSSL_NO_DEPRECATED /* For a 32 bit machine * 2 - 4 == 128 * 3 - 8 == 256 @@ -90,28 +93,28 @@ void BN_set_params(int mult, int high, int low, int mont) { if (mult >= 0) { - if (mult > (sizeof(int)*8)-1) + if (mult > (int)(sizeof(int)*8)-1) mult=sizeof(int)*8-1; bn_limit_bits=mult; bn_limit_num=1<= 0) { - if (high > (sizeof(int)*8)-1) + if (high > (int)(sizeof(int)*8)-1) high=sizeof(int)*8-1; bn_limit_bits_high=high; bn_limit_num_high=1<= 0) { - if (low > (sizeof(int)*8)-1) + if (low > (int)(sizeof(int)*8)-1) low=sizeof(int)*8-1; bn_limit_bits_low=low; bn_limit_num_low=1<= 0) { - if (mont > (sizeof(int)*8)-1) + if (mont > (int)(sizeof(int)*8)-1) mont=sizeof(int)*8-1; bn_limit_bits_mont=mont; bn_limit_num_mont=1<top - 1; bn_check_top(a); - if (a->top == 0) return(0); - l=a->d[a->top-1]; - assert(l != 0); - i=(a->top-1)*BN_BITS2; - return(i+BN_num_bits_word(l)); + if (BN_is_zero(a)) return 0; + return ((i*BN_BITS2) + BN_num_bits_word(a->d[i])); } void BN_clear_free(BIGNUM *a) @@ -260,14 +259,15 @@ void BN_clear_free(BIGNUM *a) int i; if (a == NULL) return; + bn_check_top(a); if (a->d != NULL) { - memset(a->d,0,a->dmax*sizeof(a->d[0])); + OPENSSL_cleanse(a->d,a->dmax*sizeof(a->d[0])); if (!(BN_get_flags(a,BN_FLG_STATIC_DATA))) OPENSSL_free(a->d); } i=BN_get_flags(a,BN_FLG_MALLOCED); - memset(a,0,sizeof(BIGNUM)); + OPENSSL_cleanse(a,sizeof(BIGNUM)); if (i) OPENSSL_free(a); } @@ -275,16 +275,24 @@ void BN_clear_free(BIGNUM *a) void BN_free(BIGNUM *a) { if (a == NULL) return; + bn_check_top(a); if ((a->d != NULL) && !(BN_get_flags(a,BN_FLG_STATIC_DATA))) OPENSSL_free(a->d); - a->flags|=BN_FLG_FREE; /* REMOVE? */ if (a->flags & BN_FLG_MALLOCED) OPENSSL_free(a); + else + { +#ifndef OPENSSL_NO_DEPRECATED + a->flags|=BN_FLG_FREE; +#endif + a->d = NULL; + } } void BN_init(BIGNUM *a) { memset(a,0,sizeof(BIGNUM)); + bn_check_top(a); } BIGNUM *BN_new(void) @@ -301,27 +309,34 @@ BIGNUM *BN_new(void) ret->neg=0; ret->dmax=0; ret->d=NULL; + bn_check_top(ret); return(ret); } /* This is used both by bn_expand2() and bn_dup_expand() */ /* The caller MUST check that words > b->dmax before calling this */ -static BN_ULONG *internal_bn_expand(const BIGNUM *b, int words) +static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words) { BN_ULONG *A,*a = NULL; const BN_ULONG *B; int i; - bn_check_top(b); + bn_check_top(b); + + if (words > (INT_MAX/(4*BN_BITS2))) + { + BNerr(BN_F_BN_EXPAND_INTERNAL,BN_R_BIGNUM_TOO_LONG); + return NULL; + } if (BN_get_flags(b,BN_FLG_STATIC_DATA)) { - BNerr(BN_F_BN_EXPAND2,BN_R_EXPAND_ON_STATIC_BIGNUM_DATA); + 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_EXPAND2,ERR_R_MALLOC_FAILURE); + BNerr(BN_F_BN_EXPAND_INTERNAL,ERR_R_MALLOC_FAILURE); return(NULL); } #if 1 @@ -329,70 +344,6 @@ static BN_ULONG *internal_bn_expand(const BIGNUM *b, int words) /* Check if the previous number needs to be copied */ if (B != NULL) { -#if 0 - /* This lot is an unrolled loop to copy b->top - * BN_ULONGs from B to A - */ -/* - * I have nothing against unrolling but it's usually done for - * several reasons, namely: - * - minimize percentage of decision making code, i.e. branches; - * - avoid cache trashing; - * - make it possible to schedule loads earlier; - * Now let's examine the code below. The cornerstone of C is - * "programmer is always right" and that's what we love it for:-) - * For this very reason C compilers have to be paranoid when it - * comes to data aliasing and assume the worst. Yeah, but what - * does it mean in real life? This means that loop body below will - * be compiled to sequence of loads immediately followed by stores - * as compiler assumes the worst, something in A==B+1 style. As a - * result CPU pipeline is going to starve for incoming data. Secondly - * if A and B happen to share same cache line such code is going to - * cause severe cache trashing. Both factors have severe impact on - * performance of modern CPUs and this is the reason why this - * particular piece of code is #ifdefed away and replaced by more - * "friendly" version found in #else section below. This comment - * also applies to BN_copy function. - * - * - */ - for (i=b->top&(~7); i>0; i-=8) - { - A[0]=B[0]; A[1]=B[1]; A[2]=B[2]; A[3]=B[3]; - A[4]=B[4]; A[5]=B[5]; A[6]=B[6]; A[7]=B[7]; - A+=8; - B+=8; - } - switch (b->top&7) - { - case 7: - A[6]=B[6]; - case 6: - A[5]=B[5]; - case 5: - A[4]=B[4]; - case 4: - A[3]=B[3]; - case 3: - A[2]=B[2]; - case 2: - A[1]=B[1]; - case 1: - A[0]=B[0]; - case 0: - /* I need the 'case 0' entry for utrix cc. - * If the optimizer is turned on, it does the - * switch table by doing - * a=top&7 - * a--; - * goto jump_table[a]; - * If top is 0, this makes us jump to 0xffffffc - * which is rather bad :-(. - * eric 23-Apr-1998 - */ - ; - } -#else for (i=b->top>>2; i>0; i--,A+=4,B+=4) { /* @@ -413,23 +364,15 @@ static BN_ULONG *internal_bn_expand(const BIGNUM *b, int words) case 3: A[2]=B[2]; case 2: A[1]=B[1]; case 1: A[0]=B[0]; - case 0: ; /* ultrix cc workaround, see above */ + case 0: /* workaround for ultrix cc: without 'case 0', the optimizer does + * the switch table by doing a=top&3; a--; goto jump_table[a]; + * which fails for top== 0 */ + ; } -#endif } - /* Now need to zero any data between b->top and b->max */ - - A= &(a[b->top]); - for (i=(words - b->top)>>3; i>0; i--,A+=8) - { - A[0]=0; A[1]=0; A[2]=0; A[3]=0; - A[4]=0; A[5]=0; A[6]=0; A[7]=0; - } - for (i=(words - b->top)&7; i>0; i--,A++) - A[0]=0; #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 @@ -447,13 +390,22 @@ static BN_ULONG *internal_bn_expand(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; + bn_check_top(b); + + /* This function does not work if + * words <= b->dmax && top < words + * because BN_dup() does not preserve 'dmax'! + * (But bn_dup_expand() is not used anywhere yet.) + */ + if (words > b->dmax) { - BN_ULONG *a = internal_bn_expand(b, words); + BN_ULONG *a = bn_expand_internal(b, words); if (a) { @@ -472,54 +424,74 @@ BIGNUM *bn_dup_expand(const BIGNUM *b, int words) } } /* If a == NULL, there was an error in allocation in - internal_bn_expand(), and NULL should be returned */ + bn_expand_internal(), and NULL should be returned */ } else { r = BN_dup(b); } + 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 number. + * It ensures that 'b' has enough room for a 'words' word number + * and initialises any unused part of b->d with leading zeros. * It is mostly used by the various BIGNUM routines. If there is an error, * NULL is returned. If not, 'b' is returned. */ BIGNUM *bn_expand2(BIGNUM *b, int words) { + bn_check_top(b); + if (words > b->dmax) { - BN_ULONG *a = internal_bn_expand(b, words); + BN_ULONG *a = bn_expand_internal(b, words); + if(!a) return NULL; + if(b->d) OPENSSL_free(b->d); + b->d=a; + b->dmax=words; + } - if (a) +/* 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) + { + int i; + BN_ULONG *A = &(b->d[b->top]); + for (i=(b->dmax - b->top)>>3; i>0; i--,A+=8) { - OPENSSL_free(b->d); - b->d=a; - b->dmax=words; + A[0]=0; A[1]=0; A[2]=0; A[3]=0; + A[4]=0; A[5]=0; A[6]=0; A[7]=0; } - else - b = NULL; + for (i=(b->dmax - b->top)&7; i>0; i--,A++) + A[0]=0; + assert(A == &(b->d[b->dmax])); } +#endif + bn_check_top(b); return b; } BIGNUM *BN_dup(const BIGNUM *a) { - BIGNUM *r, *t; + BIGNUM *t; if (a == NULL) return NULL; - bn_check_top(a); t = BN_new(); - if (t == NULL) return(NULL); - r = BN_copy(t, a); - /* now r == t || r == NULL */ - if (r == NULL) + if (t == NULL) return NULL; + if(!BN_copy(t, a)) + { BN_free(t); - return r; + return NULL; + } + bn_check_top(t); + return t; } BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b) @@ -547,22 +519,98 @@ BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b) case 3: A[2]=B[2]; case 2: A[1]=B[1]; case 1: A[0]=B[0]; - case 0: ; /* ultrix cc workaround, see comments in bn_expand2 */ + case 0: ; /* ultrix cc workaround, see comments in bn_expand_internal */ } #else memcpy(a->d,b->d,sizeof(b->d[0])*b->top); #endif -/* memset(&(a->d[b->top]),0,sizeof(a->d[0])*(a->max-b->top));*/ a->top=b->top; +#ifndef BN_STRICT if ((a->top == 0) && (a->d != NULL)) a->d[0]=0; +#endif a->neg=b->neg; + bn_check_top(a); return(a); } +BIGNUM *BN_ncopy(BIGNUM *a, const BIGNUM *b, size_t n) + { + int i, min; + BN_ULONG *A; + const BN_ULONG *B; + + bn_check_top(b); + if (a == b) + return a; + + min = (b->top < (int)n)? b->top: (int)n; + if (!min) + { + BN_zero(a); + return a; + } + if (bn_wexpand(a, min) == NULL) + return NULL; + + A=a->d; + B=b->d; + for (i=min>>2; i>0; i--, A+=4, B+=4) + { + BN_ULONG a0,a1,a2,a3; + a0=B[0]; a1=B[1]; a2=B[2]; a3=B[3]; + A[0]=a0; A[1]=a1; A[2]=a2; A[3]=a3; + } + switch (min&3) + { + case 3: A[2]=B[2]; + case 2: A[1]=B[1]; + case 1: A[0]=B[0]; + case 0: ; + } + a->top = min; + a->neg = b->neg; + bn_correct_top(a); + return(a); + } + +void BN_swap(BIGNUM *a, BIGNUM *b) + { + int flags_old_a, flags_old_b; + BN_ULONG *tmp_d; + int tmp_top, tmp_dmax, tmp_neg; + + bn_check_top(a); + bn_check_top(b); + + flags_old_a = a->flags; + flags_old_b = b->flags; + + tmp_d = a->d; + tmp_top = a->top; + tmp_dmax = a->dmax; + tmp_neg = a->neg; + + a->d = b->d; + a->top = b->top; + a->dmax = b->dmax; + a->neg = b->neg; + + b->d = tmp_d; + b->top = tmp_top; + b->dmax = tmp_dmax; + b->neg = tmp_neg; + + a->flags = (flags_old_a & BN_FLG_MALLOCED) | (flags_old_b & BN_FLG_STATIC_DATA); + b->flags = (flags_old_b & BN_FLG_MALLOCED) | (flags_old_a & BN_FLG_STATIC_DATA); + bn_check_top(a); + bn_check_top(b); + } + void BN_clear(BIGNUM *a) { + bn_check_top(a); if (a->d != NULL) memset(a->d,0,a->dmax*sizeof(a->d[0])); a->top=0; @@ -571,53 +619,25 @@ void BN_clear(BIGNUM *a) BN_ULONG BN_get_word(const BIGNUM *a) { - int i,n; - BN_ULONG ret=0; - - n=BN_num_bytes(a); - if (n > sizeof(BN_ULONG)) - return(BN_MASK2); - for (i=a->top-1; i>=0; i--) - { -#ifndef SIXTY_FOUR_BIT /* the data item > unsigned long */ - ret<<=BN_BITS4; /* stops the compiler complaining */ - ret<<=BN_BITS4; -#else - ret=0; -#endif - ret|=a->d[i]; - } - return(ret); + if (a->top > 1) + return BN_MASK2; + else if (a->top == 1) + return a->d[0]; + /* a->top == 0 */ + return 0; } int BN_set_word(BIGNUM *a, BN_ULONG w) { - int i,n; - if (bn_expand(a,sizeof(BN_ULONG)*8) == NULL) return(0); - - n=sizeof(BN_ULONG)/BN_BYTES; - a->neg=0; - a->top=0; - a->d[0]=(BN_ULONG)w&BN_MASK2; - if (a->d[0] != 0) a->top=1; - for (i=1; i>=BN_BITS2 so compilers don't complain - * on builds where sizeof(long) == BN_TYPES */ -#ifndef SIXTY_FOUR_BIT /* the data item > unsigned long */ - w>>=BN_BITS4; - w>>=BN_BITS4; -#else - w=0; -#endif - a->d[i]=(BN_ULONG)w&BN_MASK2; - if (a->d[i] != 0) a->top=i+1; - } + 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); } -/* ignore negative */ BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret) { unsigned int i,m; @@ -626,6 +646,7 @@ BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret) if (ret == NULL) ret=BN_new(); if (ret == NULL) return(NULL); + bn_check_top(ret); l=0; n=len; if (n == 0) @@ -638,6 +659,7 @@ BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret) i=((n-1)/BN_BYTES)+1; m=((n-1)%(BN_BYTES)); ret->top=i; + ret->neg=0; while (n-- > 0) { l=(l<<8L)| *(s++); @@ -650,7 +672,7 @@ BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret) } /* need to call this due to clear byte at top if avoiding * having the top bit set (-ve number) */ - bn_fix_top(ret); + bn_correct_top(ret); return(ret); } @@ -660,6 +682,7 @@ int BN_bn2bin(const BIGNUM *a, unsigned char *to) int n,i; BN_ULONG l; + bn_check_top(a); n=i=BN_num_bytes(a); while (i-- > 0) { @@ -686,7 +709,7 @@ int BN_ucmp(const BIGNUM *a, const BIGNUM *b) t1= ap[i]; t2= bp[i]; if (t1 != t2) - return(t1 > t2?1:-1); + return((t1 > t2) ? 1 : -1); } return(0); } @@ -736,6 +759,9 @@ int BN_set_bit(BIGNUM *a, int n) { int i,j,k; + if (n < 0) + return 0; + i=n/BN_BITS2; j=n%BN_BITS2; if (a->top <= i) @@ -747,6 +773,7 @@ int BN_set_bit(BIGNUM *a, int n) } a->d[i]|=(((BN_ULONG)1)<top <= i) return(0); a->d[i]&=(~(((BN_ULONG)1)<top <= i) return(0); + if (a->top <= i) return 0; return((a->d[i]&(((BN_ULONG)1)<= a->top) return(0); + if (w >= a->top) return 0; if (b == 0) a->top=w; else @@ -788,7 +822,7 @@ int BN_mask_bits(BIGNUM *a, int n) a->top=w+1; a->d[w]&= ~(BN_MASK2< 0) + { + for (i=dl; i>0; i--) + { + if (a[n+i] != 0) + return 1; /* a > b */ + } + } + return bn_cmp_words(a,b,cl); + }