X-Git-Url: https://git.openssl.org/gitweb/?p=openssl.git;a=blobdiff_plain;f=crypto%2Fbn%2Fbn_lib.c;h=886de0d81fb0d10488842760a9037816a21e7a09;hp=87972ce7b08fcfe7c66c1e2cb408f00e971a46b8;hb=219338115bea8a0450f39af2026c281375448310;hpb=52a1bab2d9891810618569e6c744375b768fce8c diff --git a/crypto/bn/bn_lib.c b/crypto/bn/bn_lib.c index 87972ce7b0..886de0d81f 100644 --- a/crypto/bn/bn_lib.c +++ b/crypto/bn/bn_lib.c @@ -61,14 +61,19 @@ # define NDEBUG #endif + + #include -#include +#include #include "cryptlib.h" #include "bn_lcl.h" -const char *BN_version="Big Number" OPENSSL_VERSION_PTEXT; +const char BN_version[]="Big Number" OPENSSL_VERSION_PTEXT; -/* For a 32 bit machine +/* 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 * 4 - 16 == 512 @@ -90,28 +95,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<>8)]+8); else @@ -243,16 +230,11 @@ int BN_num_bits_word(BN_ULONG l) int BN_num_bits(const BIGNUM *a) { - BN_ULONG l; - int i; - + int i = a->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 +242,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 +258,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,6 +292,7 @@ BIGNUM *BN_new(void) ret->neg=0; ret->dmax=0; ret->d=NULL; + bn_check_top(ret); return(ret); } @@ -312,18 +304,33 @@ static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words) 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_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); return(NULL); } +#ifdef PURIFY + /* Valgrind complains in BN_consttime_swap because we process the whole + * array even if it's not initialised yet. This doesn't matter in that + * function - what's important is constant time operation (we're not + * actually going to use the data) + */ + memset(a, 0, sizeof(BN_ULONG)*words); +#endif + #if 1 B=b->d; /* Check if the previous number needs to be copied */ @@ -356,110 +363,70 @@ static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words) } } - /* Now need to zero any data between b->top and b->max */ - /* XXX Why? */ - - 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 return(a); } -/* This is an internal function that can be used instead of bn_expand2() - * when there is a need to copy BIGNUMs instead of only expanding the - * data part, while still expanding them. - * Especially useful when needing to expand BIGNUMs that are declared - * 'const' and should therefore not be changed. - * The reason to use this instead of a BN_dup() followed by a bn_expand2() - * is memory allocation overhead. A BN_dup() followed by a bn_expand2() - * will allocate new memory for the BIGNUM data twice, and free it once, - * while bn_dup_expand() makes sure allocation is made only once. - */ - -BIGNUM *bn_dup_expand(const BIGNUM *b, int words) - { - BIGNUM *r = NULL; - - if (words > b->dmax) - { - BN_ULONG *a = bn_expand_internal(b, words); - - if (a) - { - r = BN_new(); - if (r) - { - r->top = b->top; - r->dmax = words; - r->neg = b->neg; - r->d = a; - } - else - { - /* r == NULL, BN_new failure */ - OPENSSL_free(a); - } - } - /* If a == NULL, there was an error in allocation in - bn_expand_internal(), and NULL should be returned */ - } - else - { - r = BN_dup(b); - } - - return r; - } - /* 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 = 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) { - if (b->d) - 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) @@ -493,11 +460,9 @@ BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b) 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; - if ((a->top == 0) && (a->d != NULL)) - a->d[0]=0; a->neg=b->neg; + bn_check_top(a); return(a); } @@ -507,6 +472,9 @@ void BN_swap(BIGNUM *a, BIGNUM *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; @@ -527,11 +495,13 @@ void BN_swap(BIGNUM *a, BIGNUM *b) 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; @@ -540,49 +510,22 @@ 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); } @@ -591,9 +534,12 @@ BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret) unsigned int i,m; unsigned int n; BN_ULONG l; + BIGNUM *bn = NULL; - if (ret == NULL) ret=BN_new(); + if (ret == NULL) + ret = bn = BN_new(); if (ret == NULL) return(NULL); + bn_check_top(ret); l=0; n=len; if (n == 0) @@ -601,13 +547,16 @@ BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret) ret->top=0; return(ret); } - if (bn_expand(ret,(int)(n+2)*8) == NULL) - return(NULL); i=((n-1)/BN_BYTES)+1; m=((n-1)%(BN_BYTES)); + if (bn_wexpand(ret, (int)i) == NULL) + { + if (bn) BN_free(bn); + return NULL; + } ret->top=i; ret->neg=0; - while (n-- > 0) + while (n--) { l=(l<<8L)| *(s++); if (m-- == 0) @@ -619,7 +568,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); } @@ -629,8 +578,9 @@ 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) + while (i--) { l=a->d[i/BN_BYTES]; *(to++)=(unsigned char)(l>>(8*(i%BN_BYTES)))&0xff; @@ -655,7 +605,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); } @@ -705,6 +655,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) @@ -716,6 +669,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); - return((a->d[i]&(((BN_ULONG)1)<top <= i) return 0; + return (int)(((a->d[i])>>j)&((BN_ULONG)1)); } int BN_mask_bits(BIGNUM *a, int n) { int b,w; + bn_check_top(a); + if (n < 0) return 0; + w=n/BN_BITS2; b=n%BN_BITS2; - if (w >= a->top) return(0); + if (w >= a->top) return 0; if (b == 0) a->top=w; else @@ -757,10 +718,18 @@ int BN_mask_bits(BIGNUM *a, int n) a->top=w+1; a->d[w]&= ~(BN_MASK2<neg = 1; + else + a->neg = 0; + } + int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n) { int i; @@ -778,6 +747,13 @@ int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n) return(0); } +/* Here follows a specialised variants of bn_cmp_words(). It has the + property of performing the operation on arrays of different sizes. + The sizes of those arrays is expressed through cl, which is the + common length ( basicall, min(len(a),len(b)) ), and dl, which is the + delta between the two lengths, calculated as len(a)-len(b). + All lengths are the number of BN_ULONGs... */ + int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl) { @@ -786,9 +762,9 @@ int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, if (dl < 0) { - for (i=-dl; i>0; i++) + for (i=dl; i<0; i++) { - if (b[n+i] != 0) + if (b[n-i] != 0) return -1; /* a < b */ } } @@ -802,3 +778,206 @@ int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, } return bn_cmp_words(a,b,cl); } + +/* + * Constant-time conditional swap of a and b. + * a and b are swapped if condition is not 0. The code assumes that at most one bit of condition is set. + * nwords is the number of words to swap. The code assumes that at least nwords are allocated in both a and b, + * and that no more than nwords are used by either a or b. + * a and b cannot be the same number + */ +void BN_consttime_swap(BN_ULONG condition, BIGNUM *a, BIGNUM *b, int nwords) + { + BN_ULONG t; + int i; + + bn_wcheck_size(a, nwords); + bn_wcheck_size(b, nwords); + + assert(a != b); + assert((condition & (condition - 1)) == 0); + assert(sizeof(BN_ULONG) >= sizeof(int)); + + condition = ((condition - 1) >> (BN_BITS2 - 1)) - 1; + + t = (a->top^b->top) & condition; + a->top ^= t; + b->top ^= t; + +#define BN_CONSTTIME_SWAP(ind) \ + do { \ + t = (a->d[ind] ^ b->d[ind]) & condition; \ + a->d[ind] ^= t; \ + b->d[ind] ^= t; \ + } while (0) + + + switch (nwords) { + default: + for (i = 10; i < nwords; i++) + BN_CONSTTIME_SWAP(i); + /* Fallthrough */ + case 10: BN_CONSTTIME_SWAP(9); /* Fallthrough */ + case 9: BN_CONSTTIME_SWAP(8); /* Fallthrough */ + case 8: BN_CONSTTIME_SWAP(7); /* Fallthrough */ + case 7: BN_CONSTTIME_SWAP(6); /* Fallthrough */ + case 6: BN_CONSTTIME_SWAP(5); /* Fallthrough */ + case 5: BN_CONSTTIME_SWAP(4); /* Fallthrough */ + case 4: BN_CONSTTIME_SWAP(3); /* Fallthrough */ + case 3: BN_CONSTTIME_SWAP(2); /* Fallthrough */ + case 2: BN_CONSTTIME_SWAP(1); /* Fallthrough */ + case 1: BN_CONSTTIME_SWAP(0); + } +#undef BN_CONSTTIME_SWAP +} + +/* Bits of security, see SP800-57 */ + +int BN_security_bits(int L, int N) + { + int secbits, bits; + if (L >= 15360) + secbits = 256; + else if (L >= 7690) + secbits = 192; + else if (L >= 3072) + secbits = 128; + else if (L >= 2048) + secbits = 112; + else if (L >= 1024) + secbits = 80; + else + return 0; + if (N == -1) + return secbits; + bits = N / 2; + if (bits < 80) + return 0; + return bits >= secbits ? secbits : bits; + } + + +void BN_zero_ex(BIGNUM *a) + { + a->top = 0; + a->neg = 0; + } + +int BN_abs_is_word(const BIGNUM *a, const BN_ULONG w) + { + return ((a->top == 1) && (a->d[0] == w)) || ((w == 0) && (a->top == 0)); + } + +int BN_is_zero(const BIGNUM *a) + { + return a->top == 0; + } + +int BN_is_one(const BIGNUM *a) + { + return BN_abs_is_word(a, 1) && !a->neg; + } + +int BN_is_word(const BIGNUM *a, const BN_ULONG w) + { + return BN_abs_is_word(a, w) && (!w || !a->neg); + } + +int BN_is_odd(const BIGNUM *a) + { + return (a->top > 0) && (a->d[0] & 1); + } + +int BN_is_negative(const BIGNUM *a) + { + return (a->neg != 0); + } + +int BN_to_montgomery(BIGNUM *r,const BIGNUM *a, BN_MONT_CTX *mont, BN_CTX *ctx) + { + return BN_mod_mul_montgomery(r,a,&(mont->RR),mont,ctx); + } + +void BN_with_flags(BIGNUM *dest, const BIGNUM *b, int n) + { + dest->d=b->d; + dest->top=b->top; + dest->dmax=b->dmax; + dest->neg=b->neg; + dest->flags=((dest->flags & BN_FLG_MALLOCED) + | (b->flags & ~BN_FLG_MALLOCED) + | BN_FLG_STATIC_DATA + | n); + } + +BN_GENCB *BN_GENCB_new(void) + { + BN_GENCB *ret; + + if ((ret=(BN_GENCB *)OPENSSL_malloc(sizeof(BN_GENCB))) == NULL) + { + BNerr(BN_F_BN_GENCB_NEW,ERR_R_MALLOC_FAILURE); + return(NULL); + } + + return ret; + } + +void BN_GENCB_free(BN_GENCB *cb) + { + if (cb == NULL) return; + OPENSSL_free(cb); + } + +void BN_set_flags(BIGNUM *b, int n) + { + b->flags|=n; + } + +int BN_get_flags(const BIGNUM *b, int n) + { + return b->flags&n; + } + +/* Populate a BN_GENCB structure with an "old"-style callback */ +void BN_GENCB_set_old(BN_GENCB *gencb, void (*callback)(int, int, void *), void *cb_arg) + { + BN_GENCB *tmp_gencb = gencb; + tmp_gencb->ver = 1; + tmp_gencb->arg = cb_arg; + tmp_gencb->cb.cb_1 = callback; + } + +/* Populate a BN_GENCB structure with a "new"-style callback */ +void BN_GENCB_set(BN_GENCB *gencb, int (*callback)(int, int, BN_GENCB *), void *cb_arg) + { + BN_GENCB *tmp_gencb = gencb; + tmp_gencb->ver = 2; + tmp_gencb->arg = cb_arg; + tmp_gencb->cb.cb_2 = callback; + } + +void *BN_GENCB_get_arg(BN_GENCB *cb) + { + return cb->arg; + } + + +BIGNUM *bn_wexpand(BIGNUM *a, int words) + { + return (words <= a->dmax)?a:bn_expand2(a,words); + } + +void bn_correct_top(BIGNUM *a) + { + BN_ULONG *ftl; + int tmp_top = a->top; + + if (tmp_top > 0) + { + for (ftl= &(a->d[tmp_top-1]); tmp_top > 0; tmp_top--) + if (*(ftl--)) break; + a->top = tmp_top; + } + bn_pollute(a); + }