diff options
Diffstat (limited to 'freebsd/crypto/openssl/crypto/bn')
| -rw-r--r-- | freebsd/crypto/openssl/crypto/bn/bn.h | 106 | ||||
| -rw-r--r-- | freebsd/crypto/openssl/crypto/bn/bn_div.c | 1 | ||||
| -rw-r--r-- | freebsd/crypto/openssl/crypto/bn/bn_exp.c | 69 | ||||
| -rw-r--r-- | freebsd/crypto/openssl/crypto/bn/bn_gf2m.c | 34 | ||||
| -rw-r--r-- | freebsd/crypto/openssl/crypto/bn/bn_lcl.h | 3 | ||||
| -rw-r--r-- | freebsd/crypto/openssl/crypto/bn/bn_lib.c | 57 | ||||
| -rw-r--r-- | freebsd/crypto/openssl/crypto/bn/bn_mod.c | 69 | ||||
| -rw-r--r-- | freebsd/crypto/openssl/crypto/bn/bn_mont.c | 58 | ||||
| -rw-r--r-- | freebsd/crypto/openssl/crypto/bn/bn_sqr.c | 10 |
9 files changed, 294 insertions, 113 deletions
diff --git a/freebsd/crypto/openssl/crypto/bn/bn.h b/freebsd/crypto/openssl/crypto/bn/bn.h index 633d1b1f..d4b9f27b 100644 --- a/freebsd/crypto/openssl/crypto/bn/bn.h +++ b/freebsd/crypto/openssl/crypto/bn/bn.h @@ -56,7 +56,7 @@ * [including the GNU Public Licence.] */ /* ==================================================================== - * Copyright (c) 1998-2006 The OpenSSL Project. All rights reserved. + * Copyright (c) 1998-2018 The OpenSSL Project. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions @@ -375,25 +375,76 @@ int BN_GENCB_call(BN_GENCB *cb, int a, int b); * on the size of the number */ /* - * number of Miller-Rabin iterations for an error rate of less than 2^-80 for - * random 'b'-bit input, b >= 100 (taken from table 4.4 in the Handbook of - * Applied Cryptography [Menezes, van Oorschot, Vanstone; CRC Press 1996]; - * original paper: Damgaard, Landrock, Pomerance: Average case error - * estimates for the strong probable prime test. -- Math. Comp. 61 (1993) - * 177-194) + * BN_prime_checks_for_size() returns the number of Miller-Rabin iterations + * that will be done for checking that a random number is probably prime. The + * error rate for accepting a composite number as prime depends on the size of + * the prime |b|. The error rates used are for calculating an RSA key with 2 primes, + * and so the level is what you would expect for a key of double the size of the + * prime. + * + * This table is generated using the algorithm of FIPS PUB 186-4 + * Digital Signature Standard (DSS), section F.1, page 117. + * (https://dx.doi.org/10.6028/NIST.FIPS.186-4) + * + * The following magma script was used to generate the output: + * securitybits:=125; + * k:=1024; + * for t:=1 to 65 do + * for M:=3 to Floor(2*Sqrt(k-1)-1) do + * S:=0; + * // Sum over m + * for m:=3 to M do + * s:=0; + * // Sum over j + * for j:=2 to m do + * s+:=(RealField(32)!2)^-(j+(k-1)/j); + * end for; + * S+:=2^(m-(m-1)*t)*s; + * end for; + * A:=2^(k-2-M*t); + * B:=8*(Pi(RealField(32))^2-6)/3*2^(k-2)*S; + * pkt:=2.00743*Log(2)*k*2^-k*(A+B); + * seclevel:=Floor(-Log(2,pkt)); + * if seclevel ge securitybits then + * printf "k: %5o, security: %o bits (t: %o, M: %o)\n",k,seclevel,t,M; + * break; + * end if; + * end for; + * if seclevel ge securitybits then break; end if; + * end for; + * + * It can be run online at: + * http://magma.maths.usyd.edu.au/calc + * + * And will output: + * k: 1024, security: 129 bits (t: 6, M: 23) + * + * k is the number of bits of the prime, securitybits is the level we want to + * reach. + * + * prime length | RSA key size | # MR tests | security level + * -------------+--------------|------------+--------------- + * (b) >= 6394 | >= 12788 | 3 | 256 bit + * (b) >= 3747 | >= 7494 | 3 | 192 bit + * (b) >= 1345 | >= 2690 | 4 | 128 bit + * (b) >= 1080 | >= 2160 | 5 | 128 bit + * (b) >= 852 | >= 1704 | 5 | 112 bit + * (b) >= 476 | >= 952 | 5 | 80 bit + * (b) >= 400 | >= 800 | 6 | 80 bit + * (b) >= 347 | >= 694 | 7 | 80 bit + * (b) >= 308 | >= 616 | 8 | 80 bit + * (b) >= 55 | >= 110 | 27 | 64 bit + * (b) >= 6 | >= 12 | 34 | 64 bit */ -# define BN_prime_checks_for_size(b) ((b) >= 1300 ? 2 : \ - (b) >= 850 ? 3 : \ - (b) >= 650 ? 4 : \ - (b) >= 550 ? 5 : \ - (b) >= 450 ? 6 : \ - (b) >= 400 ? 7 : \ - (b) >= 350 ? 8 : \ - (b) >= 300 ? 9 : \ - (b) >= 250 ? 12 : \ - (b) >= 200 ? 15 : \ - (b) >= 150 ? 18 : \ - /* b >= 100 */ 27) + +# define BN_prime_checks_for_size(b) ((b) >= 3747 ? 3 : \ + (b) >= 1345 ? 4 : \ + (b) >= 476 ? 5 : \ + (b) >= 400 ? 6 : \ + (b) >= 347 ? 7 : \ + (b) >= 308 ? 8 : \ + (b) >= 55 ? 27 : \ + /* b >= 6 */ 34) # define BN_num_bytes(a) ((BN_num_bits(a)+7)/8) @@ -773,6 +824,16 @@ BIGNUM *bn_dup_expand(const BIGNUM *a, int words); /* unused */ /* We only need assert() when debugging */ # include <assert.h> +/* + * The new BN_FLG_FIXED_TOP flag marks vectors that were not treated with + * bn_correct_top, in other words such vectors are permitted to have zeros + * in most significant limbs. Such vectors are used internally to achieve + * execution time invariance for critical operations with private keys. + * It's BN_DEBUG-only flag, because user application is not supposed to + * observe it anyway. Moreover, optimizing compiler would actually remove + * all operations manipulating the bit in question in non-BN_DEBUG build. + */ +# define BN_FLG_FIXED_TOP 0x10000 # ifdef BN_DEBUG_RAND /* To avoid "make update" cvs wars due to BN_DEBUG, use some tricks */ # ifndef RAND_pseudo_bytes @@ -805,8 +866,10 @@ int RAND_pseudo_bytes(unsigned char *buf, int num); do { \ const BIGNUM *_bnum2 = (a); \ if (_bnum2 != NULL) { \ - assert((_bnum2->top == 0) || \ - (_bnum2->d[_bnum2->top - 1] != 0)); \ + int _top = _bnum2->top; \ + assert((_top == 0) || \ + (_bnum2->flags & BN_FLG_FIXED_TOP) || \ + (_bnum2->d[_top - 1] != 0)); \ bn_pollute(_bnum2); \ } \ } while(0) @@ -824,6 +887,7 @@ int RAND_pseudo_bytes(unsigned char *buf, int num); # else /* !BN_DEBUG */ +# define BN_FLG_FIXED_TOP 0 # define bn_pollute(a) # define bn_check_top(a) # define bn_fix_top(a) bn_correct_top(a) diff --git a/freebsd/crypto/openssl/crypto/bn/bn_div.c b/freebsd/crypto/openssl/crypto/bn/bn_div.c index d85ac669..2888becf 100644 --- a/freebsd/crypto/openssl/crypto/bn/bn_div.c +++ b/freebsd/crypto/openssl/crypto/bn/bn_div.c @@ -292,6 +292,7 @@ int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor, wnum.neg = 0; wnum.d = &(snum->d[loop]); wnum.top = div_n; + wnum.flags = BN_FLG_STATIC_DATA; /* * only needed when BN_ucmp messes up the values between top and max */ diff --git a/freebsd/crypto/openssl/crypto/bn/bn_exp.c b/freebsd/crypto/openssl/crypto/bn/bn_exp.c index 50374334..423285dc 100644 --- a/freebsd/crypto/openssl/crypto/bn/bn_exp.c +++ b/freebsd/crypto/openssl/crypto/bn/bn_exp.c @@ -292,8 +292,8 @@ int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, bits = BN_num_bits(p); if (bits == 0) { - /* x**0 mod 1 is still zero. */ - if (BN_is_one(m)) { + /* x**0 mod 1, or x**0 mod -1 is still zero. */ + if (BN_abs_is_word(m, 1)) { ret = 1; BN_zero(r); } else { @@ -434,8 +434,8 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, } bits = BN_num_bits(p); if (bits == 0) { - /* x**0 mod 1 is still zero. */ - if (BN_is_one(m)) { + /* x**0 mod 1, or x**0 mod -1 is still zero. */ + if (BN_abs_is_word(m, 1)) { ret = 1; BN_zero(rr); } else { @@ -475,17 +475,17 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, ret = 1; goto err; } - if (!BN_to_montgomery(val[0], aa, mont, ctx)) + if (!bn_to_mont_fixed_top(val[0], aa, mont, ctx)) goto err; /* 1 */ window = BN_window_bits_for_exponent_size(bits); if (window > 1) { - if (!BN_mod_mul_montgomery(d, val[0], val[0], mont, ctx)) + if (!bn_mul_mont_fixed_top(d, val[0], val[0], mont, ctx)) goto err; /* 2 */ j = 1 << (window - 1); for (i = 1; i < j; i++) { if (((val[i] = BN_CTX_get(ctx)) == NULL) || - !BN_mod_mul_montgomery(val[i], val[i - 1], d, mont, ctx)) + !bn_mul_mont_fixed_top(val[i], val[i - 1], d, mont, ctx)) goto err; } } @@ -507,19 +507,15 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, for (i = 1; i < j; i++) r->d[i] = (~m->d[i]) & BN_MASK2; r->top = j; - /* - * Upper words will be zero if the corresponding words of 'm' were - * 0xfff[...], so decrement r->top accordingly. - */ - bn_correct_top(r); + r->flags |= BN_FLG_FIXED_TOP; } else #endif - if (!BN_to_montgomery(r, BN_value_one(), mont, ctx)) + if (!bn_to_mont_fixed_top(r, BN_value_one(), mont, ctx)) goto err; for (;;) { if (BN_is_bit_set(p, wstart) == 0) { if (!start) { - if (!BN_mod_mul_montgomery(r, r, r, mont, ctx)) + if (!bn_mul_mont_fixed_top(r, r, r, mont, ctx)) goto err; } if (wstart == 0) @@ -550,12 +546,12 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, /* add the 'bytes above' */ if (!start) for (i = 0; i < j; i++) { - if (!BN_mod_mul_montgomery(r, r, r, mont, ctx)) + if (!bn_mul_mont_fixed_top(r, r, r, mont, ctx)) goto err; } /* wvalue will be an odd number < 2^window */ - if (!BN_mod_mul_montgomery(r, r, val[wvalue >> 1], mont, ctx)) + if (!bn_mul_mont_fixed_top(r, r, val[wvalue >> 1], mont, ctx)) goto err; /* move the 'window' down further */ @@ -565,6 +561,11 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, if (wstart < 0) break; } + /* + * Done with zero-padded intermediate BIGNUMs. Final BN_from_montgomery + * removes padding [if any] and makes return value suitable for public + * API consumer. + */ #if defined(SPARC_T4_MONT) if (OPENSSL_sparcv9cap_P[0] & (SPARCV9_VIS3 | SPARCV9_PREFER_FPU)) { j = mont->N.top; /* borrow j */ @@ -683,7 +684,7 @@ static int MOD_EXP_CTIME_COPY_FROM_PREBUF(BIGNUM *b, int top, } b->top = top; - bn_correct_top(b); + b->flags |= BN_FLG_FIXED_TOP; return 1; } @@ -735,8 +736,8 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, */ bits = p->top * BN_BITS2; if (bits == 0) { - /* x**0 mod 1 is still zero. */ - if (BN_is_one(m)) { + /* x**0 mod 1, or x**0 mod -1 is still zero. */ + if (BN_abs_is_word(m, 1)) { ret = 1; BN_zero(rr); } else { @@ -854,16 +855,16 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, tmp.top = top; } else #endif - if (!BN_to_montgomery(&tmp, BN_value_one(), mont, ctx)) + if (!bn_to_mont_fixed_top(&tmp, BN_value_one(), mont, ctx)) goto err; /* prepare a^1 in Montgomery domain */ if (a->neg || BN_ucmp(a, m) >= 0) { if (!BN_mod(&am, a, m, ctx)) goto err; - if (!BN_to_montgomery(&am, &am, mont, ctx)) + if (!bn_to_mont_fixed_top(&am, &am, mont, ctx)) goto err; - } else if (!BN_to_montgomery(&am, a, mont, ctx)) + } else if (!bn_to_mont_fixed_top(&am, a, mont, ctx)) goto err; #if defined(SPARC_T4_MONT) @@ -1130,14 +1131,14 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, * performance advantage of sqr over mul). */ if (window > 1) { - if (!BN_mod_mul_montgomery(&tmp, &am, &am, mont, ctx)) + if (!bn_mul_mont_fixed_top(&tmp, &am, &am, mont, ctx)) goto err; if (!MOD_EXP_CTIME_COPY_TO_PREBUF(&tmp, top, powerbuf, 2, window)) goto err; for (i = 3; i < numPowers; i++) { /* Calculate a^i = a^(i-1) * a */ - if (!BN_mod_mul_montgomery(&tmp, &am, &tmp, mont, ctx)) + if (!bn_mul_mont_fixed_top(&tmp, &am, &tmp, mont, ctx)) goto err; if (!MOD_EXP_CTIME_COPY_TO_PREBUF(&tmp, top, powerbuf, i, window)) @@ -1161,7 +1162,7 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, /* Scan the window, squaring the result as we go */ for (i = 0; i < window; i++, bits--) { - if (!BN_mod_mul_montgomery(&tmp, &tmp, &tmp, mont, ctx)) + if (!bn_mul_mont_fixed_top(&tmp, &tmp, &tmp, mont, ctx)) goto err; wvalue = (wvalue << 1) + BN_is_bit_set(p, bits); } @@ -1174,12 +1175,16 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, goto err; /* Multiply the result into the intermediate result */ - if (!BN_mod_mul_montgomery(&tmp, &tmp, &am, mont, ctx)) + if (!bn_mul_mont_fixed_top(&tmp, &tmp, &am, mont, ctx)) goto err; } } - /* Convert the final result from montgomery to standard format */ + /* + * Done with zero-padded intermediate BIGNUMs. Final BN_from_montgomery + * removes padding [if any] and makes return value suitable for public + * API consumer. + */ #if defined(SPARC_T4_MONT) if (OPENSSL_sparcv9cap_P[0] & (SPARCV9_VIS3 | SPARCV9_PREFER_FPU)) { am.d[0] = 1; /* borrow am */ @@ -1249,8 +1254,8 @@ int BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p, bits = BN_num_bits(p); if (bits == 0) { - /* x**0 mod 1 is still zero. */ - if (BN_is_one(m)) { + /* x**0 mod 1, or x**0 mod -1 is still zero. */ + if (BN_abs_is_word(m, 1)) { ret = 1; BN_zero(rr); } else { @@ -1371,9 +1376,9 @@ int BN_mod_exp_simple(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, } bits = BN_num_bits(p); - if (bits == 0) { - /* x**0 mod 1 is still zero. */ - if (BN_is_one(m)) { + if (bits == 0) { + /* x**0 mod 1, or x**0 mod -1 is still zero. */ + if (BN_abs_is_word(m, 1)) { ret = 1; BN_zero(r); } else { diff --git a/freebsd/crypto/openssl/crypto/bn/bn_gf2m.c b/freebsd/crypto/openssl/crypto/bn/bn_gf2m.c index 74726f55..a2b29e3c 100644 --- a/freebsd/crypto/openssl/crypto/bn/bn_gf2m.c +++ b/freebsd/crypto/openssl/crypto/bn/bn_gf2m.c @@ -38,7 +38,7 @@ */ /* ==================================================================== - * Copyright (c) 1998-2002 The OpenSSL Project. All rights reserved. + * Copyright (c) 1998-2018 The OpenSSL Project. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions @@ -105,30 +105,32 @@ */ # define MAX_ITERATIONS 50 -static const BN_ULONG SQR_tb[16] = { 0, 1, 4, 5, 16, 17, 20, 21, - 64, 65, 68, 69, 80, 81, 84, 85 -}; +# define SQR_nibble(w) ((((w) & 8) << 3) \ + | (((w) & 4) << 2) \ + | (((w) & 2) << 1) \ + | ((w) & 1)) + /* Platform-specific macros to accelerate squaring. */ # if defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG) # define SQR1(w) \ - SQR_tb[(w) >> 60 & 0xF] << 56 | SQR_tb[(w) >> 56 & 0xF] << 48 | \ - SQR_tb[(w) >> 52 & 0xF] << 40 | SQR_tb[(w) >> 48 & 0xF] << 32 | \ - SQR_tb[(w) >> 44 & 0xF] << 24 | SQR_tb[(w) >> 40 & 0xF] << 16 | \ - SQR_tb[(w) >> 36 & 0xF] << 8 | SQR_tb[(w) >> 32 & 0xF] + SQR_nibble((w) >> 60) << 56 | SQR_nibble((w) >> 56) << 48 | \ + SQR_nibble((w) >> 52) << 40 | SQR_nibble((w) >> 48) << 32 | \ + SQR_nibble((w) >> 44) << 24 | SQR_nibble((w) >> 40) << 16 | \ + SQR_nibble((w) >> 36) << 8 | SQR_nibble((w) >> 32) # define SQR0(w) \ - SQR_tb[(w) >> 28 & 0xF] << 56 | SQR_tb[(w) >> 24 & 0xF] << 48 | \ - SQR_tb[(w) >> 20 & 0xF] << 40 | SQR_tb[(w) >> 16 & 0xF] << 32 | \ - SQR_tb[(w) >> 12 & 0xF] << 24 | SQR_tb[(w) >> 8 & 0xF] << 16 | \ - SQR_tb[(w) >> 4 & 0xF] << 8 | SQR_tb[(w) & 0xF] + SQR_nibble((w) >> 28) << 56 | SQR_nibble((w) >> 24) << 48 | \ + SQR_nibble((w) >> 20) << 40 | SQR_nibble((w) >> 16) << 32 | \ + SQR_nibble((w) >> 12) << 24 | SQR_nibble((w) >> 8) << 16 | \ + SQR_nibble((w) >> 4) << 8 | SQR_nibble((w) ) # endif # ifdef THIRTY_TWO_BIT # define SQR1(w) \ - SQR_tb[(w) >> 28 & 0xF] << 24 | SQR_tb[(w) >> 24 & 0xF] << 16 | \ - SQR_tb[(w) >> 20 & 0xF] << 8 | SQR_tb[(w) >> 16 & 0xF] + SQR_nibble((w) >> 28) << 24 | SQR_nibble((w) >> 24) << 16 | \ + SQR_nibble((w) >> 20) << 8 | SQR_nibble((w) >> 16) # define SQR0(w) \ - SQR_tb[(w) >> 12 & 0xF] << 24 | SQR_tb[(w) >> 8 & 0xF] << 16 | \ - SQR_tb[(w) >> 4 & 0xF] << 8 | SQR_tb[(w) & 0xF] + SQR_nibble((w) >> 12) << 24 | SQR_nibble((w) >> 8) << 16 | \ + SQR_nibble((w) >> 4) << 8 | SQR_nibble((w) ) # endif # if !defined(OPENSSL_BN_ASM_GF2m) diff --git a/freebsd/crypto/openssl/crypto/bn/bn_lcl.h b/freebsd/crypto/openssl/crypto/bn/bn_lcl.h index 00f4f099..6f7335b7 100644 --- a/freebsd/crypto/openssl/crypto/bn/bn_lcl.h +++ b/freebsd/crypto/openssl/crypto/bn/bn_lcl.h @@ -56,7 +56,7 @@ * [including the GNU Public Licence.] */ /* ==================================================================== - * Copyright (c) 1998-2000 The OpenSSL Project. All rights reserved. + * Copyright (c) 1998-2018 The OpenSSL Project. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions @@ -113,6 +113,7 @@ # define HEADER_BN_LCL_H # include <openssl/bn.h> +# include "bn_int.h" #ifdef __cplusplus extern "C" { diff --git a/freebsd/crypto/openssl/crypto/bn/bn_lib.c b/freebsd/crypto/openssl/crypto/bn/bn_lib.c index e63f6100..755322ce 100644 --- a/freebsd/crypto/openssl/crypto/bn/bn_lib.c +++ b/freebsd/crypto/openssl/crypto/bn/bn_lib.c @@ -265,8 +265,6 @@ static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words) const BN_ULONG *B; int i; - bn_check_top(b); - if (words > (INT_MAX / (4 * BN_BITS2))) { BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_BIGNUM_TOO_LONG); return NULL; @@ -400,8 +398,6 @@ BIGNUM *bn_dup_expand(const BIGNUM *b, int words) 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) @@ -435,7 +431,6 @@ BIGNUM *bn_expand2(BIGNUM *b, int words) assert(A == &(b->d[b->dmax])); } #endif - bn_check_top(b); return b; } @@ -499,12 +494,18 @@ BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b) memcpy(a->d, b->d, sizeof(b->d[0]) * b->top); #endif - a->top = b->top; a->neg = b->neg; + a->top = b->top; + a->flags |= b->flags & BN_FLG_FIXED_TOP; bn_check_top(a); return (a); } +#define FLAGS_DATA(flags) ((flags) & (BN_FLG_STATIC_DATA \ + | BN_FLG_CONSTTIME \ + | BN_FLG_FIXED_TOP)) +#define FLAGS_STRUCT(flags) ((flags) & (BN_FLG_MALLOCED)) + void BN_swap(BIGNUM *a, BIGNUM *b) { int flags_old_a, flags_old_b; @@ -532,10 +533,8 @@ void BN_swap(BIGNUM *a, BIGNUM *b) 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); + a->flags = FLAGS_STRUCT(flags_old_a) | FLAGS_DATA(flags_old_b); + b->flags = FLAGS_STRUCT(flags_old_b) | FLAGS_DATA(flags_old_a); bn_check_top(a); bn_check_top(b); } @@ -547,6 +546,7 @@ void BN_clear(BIGNUM *a) OPENSSL_cleanse(a->d, a->dmax * sizeof(a->d[0])); a->top = 0; a->neg = 0; + a->flags &= ~BN_FLG_FIXED_TOP; } BN_ULONG BN_get_word(const BIGNUM *a) @@ -567,6 +567,7 @@ int BN_set_word(BIGNUM *a, BN_ULONG w) a->neg = 0; a->d[0] = w; a->top = (w ? 1 : 0); + a->flags &= ~BN_FLG_FIXED_TOP; bn_check_top(a); return (1); } @@ -615,6 +616,41 @@ BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret) } /* ignore negative */ +static int bn2binpad(const BIGNUM *a, unsigned char *to, int tolen) +{ + int n; + size_t i, inc, lasti, j; + BN_ULONG l; + + n = BN_num_bytes(a); + if (tolen == -1) + tolen = n; + else if (tolen < n) + return -1; + + if (n == 0) { + OPENSSL_cleanse(to, tolen); + return tolen; + } + + lasti = n - 1; + for (i = 0, inc = 1, j = tolen; j > 0;) { + l = a->d[i / BN_BYTES]; + to[--j] = (unsigned char)(l >> (8 * (i % BN_BYTES)) & (0 - inc)); + inc = (i - lasti) >> (8 * sizeof(i) - 1); + i += inc; /* stay on top limb */ + } + + return tolen; +} + +int bn_bn2binpad(const BIGNUM *a, unsigned char *to, int tolen) +{ + if (tolen < 0) + return -1; + return bn2binpad(a, to, tolen); +} + int BN_bn2bin(const BIGNUM *a, unsigned char *to) { int n, i; @@ -713,6 +749,7 @@ int BN_set_bit(BIGNUM *a, int n) for (k = a->top; k < i + 1; k++) a->d[k] = 0; a->top = i + 1; + a->flags &= ~BN_FLG_FIXED_TOP; } a->d[i] |= (((BN_ULONG)1) << j); diff --git a/freebsd/crypto/openssl/crypto/bn/bn_mod.c b/freebsd/crypto/openssl/crypto/bn/bn_mod.c index e79d8209..94762168 100644 --- a/freebsd/crypto/openssl/crypto/bn/bn_mod.c +++ b/freebsd/crypto/openssl/crypto/bn/bn_mod.c @@ -6,7 +6,7 @@ * for the OpenSSL project. */ /* ==================================================================== - * Copyright (c) 1998-2000 The OpenSSL Project. All rights reserved. + * Copyright (c) 1998-2018 The OpenSSL Project. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions @@ -151,18 +151,73 @@ int BN_mod_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, /* * BN_mod_add variant that may be used if both a and b are non-negative and - * less than m + * less than m. The original algorithm was + * + * if (!BN_uadd(r, a, b)) + * return 0; + * if (BN_ucmp(r, m) >= 0) + * return BN_usub(r, r, m); + * + * which is replaced with addition, subtracting modulus, and conditional + * move depending on whether or not subtraction borrowed. */ -int BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, - const BIGNUM *m) +int bn_mod_add_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, + const BIGNUM *m) { - if (!BN_uadd(r, a, b)) + size_t i, ai, bi, mtop = m->top; + BN_ULONG storage[1024 / BN_BITS2]; + BN_ULONG carry, temp, mask, *rp, *tp = storage; + const BN_ULONG *ap, *bp; + + if (bn_wexpand(r, m->top) == NULL) return 0; - if (BN_ucmp(r, m) >= 0) - return BN_usub(r, r, m); + + if (mtop > sizeof(storage) / sizeof(storage[0]) + && (tp = OPENSSL_malloc(mtop * sizeof(BN_ULONG))) == NULL) + return 0; + + ap = a->d != NULL ? a->d : tp; + bp = b->d != NULL ? b->d : tp; + + for (i = 0, ai = 0, bi = 0, carry = 0; i < mtop;) { + mask = (BN_ULONG)0 - ((i - a->top) >> (8 * sizeof(i) - 1)); + temp = ((ap[ai] & mask) + carry) & BN_MASK2; + carry = (temp < carry); + + mask = (BN_ULONG)0 - ((i - b->top) >> (8 * sizeof(i) - 1)); + tp[i] = ((bp[bi] & mask) + temp) & BN_MASK2; + carry += (tp[i] < temp); + + i++; + ai += (i - a->dmax) >> (8 * sizeof(i) - 1); + bi += (i - b->dmax) >> (8 * sizeof(i) - 1); + } + rp = r->d; + carry -= bn_sub_words(rp, tp, m->d, mtop); + for (i = 0; i < mtop; i++) { + rp[i] = (carry & tp[i]) | (~carry & rp[i]); + ((volatile BN_ULONG *)tp)[i] = 0; + } + r->top = mtop; + r->neg = 0; + + if (tp != storage) + OPENSSL_free(tp); + return 1; } +int BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, + const BIGNUM *m) +{ + int ret = bn_mod_add_fixed_top(r, a, b, m); + + if (ret) + bn_correct_top(r); + + return ret; +} + int BN_mod_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, BN_CTX *ctx) { diff --git a/freebsd/crypto/openssl/crypto/bn/bn_mont.c b/freebsd/crypto/openssl/crypto/bn/bn_mont.c index d21a9501..7657798a 100644 --- a/freebsd/crypto/openssl/crypto/bn/bn_mont.c +++ b/freebsd/crypto/openssl/crypto/bn/bn_mont.c @@ -125,12 +125,23 @@ #define MONT_WORD /* use the faster word-based algorithm */ #ifdef MONT_WORD -static int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont); +static int bn_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont); #endif int BN_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_MONT_CTX *mont, BN_CTX *ctx) { + int ret = bn_mul_mont_fixed_top(r, a, b, mont, ctx); + + bn_correct_top(r); + bn_check_top(r); + + return ret; +} + +int bn_mul_mont_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, + BN_MONT_CTX *mont, BN_CTX *ctx) +{ BIGNUM *tmp; int ret = 0; #if defined(OPENSSL_BN_ASM_MONT) && defined(MONT_WORD) @@ -142,8 +153,8 @@ int BN_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, if (bn_mul_mont(r->d, a->d, b->d, mont->N.d, mont->n0, num)) { r->neg = a->neg ^ b->neg; r->top = num; - bn_correct_top(r); - return (1); + r->flags |= BN_FLG_FIXED_TOP; + return 1; } } #endif @@ -163,13 +174,12 @@ int BN_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, } /* reduce from aRR to aR */ #ifdef MONT_WORD - if (!BN_from_montgomery_word(r, tmp, mont)) + if (!bn_from_montgomery_word(r, tmp, mont)) goto err; #else if (!BN_from_montgomery(r, tmp, mont, ctx)) goto err; #endif - bn_check_top(r); ret = 1; err: BN_CTX_end(ctx); @@ -177,7 +187,7 @@ int BN_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, } #ifdef MONT_WORD -static int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont) +static int bn_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont) { BIGNUM *n; BN_ULONG *ap, *np, *rp, n0, v, carry; @@ -207,6 +217,7 @@ static int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont) # endif r->top = max; + r->flags |= BN_FLG_FIXED_TOP; n0 = mont->n0[0]; /* @@ -225,6 +236,7 @@ static int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont) if (bn_wexpand(ret, nl) == NULL) return (0); ret->top = nl; + ret->flags |= BN_FLG_FIXED_TOP; ret->neg = r->neg; rp = ret->d; @@ -235,20 +247,16 @@ static int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont) */ ap = &(r->d[nl]); + carry -= bn_sub_words(rp, ap, np, nl); /* - * |v| is one if |ap| - |np| underflowed or zero if it did not. Note |v| - * cannot be -1. That would imply the subtraction did not fit in |nl| words, - * and we know at most one subtraction is needed. + * |carry| is -1 if |ap| - |np| underflowed or zero if it did not. Note + * |carry| cannot be 1. That would imply the subtraction did not fit in + * |nl| words, and we know at most one subtraction is needed. */ - v = bn_sub_words(rp, ap, np, nl) - carry; - v = 0 - v; for (i = 0; i < nl; i++) { - rp[i] = (v & ap[i]) | (~v & rp[i]); + rp[i] = (carry & ap[i]) | (~carry & rp[i]); ap[i] = 0; } - bn_correct_top(r); - bn_correct_top(ret); - bn_check_top(ret); return (1); } @@ -262,8 +270,11 @@ int BN_from_montgomery(BIGNUM *ret, const BIGNUM *a, BN_MONT_CTX *mont, BIGNUM *t; BN_CTX_start(ctx); - if ((t = BN_CTX_get(ctx)) && BN_copy(t, a)) - retn = BN_from_montgomery_word(ret, t, mont); + if ((t = BN_CTX_get(ctx)) && BN_copy(t, a)) { + retn = bn_from_montgomery_word(ret, t, mont); + bn_correct_top(ret); + bn_check_top(ret); + } BN_CTX_end(ctx); #else /* !MONT_WORD */ BIGNUM *t1, *t2; @@ -301,6 +312,12 @@ int BN_from_montgomery(BIGNUM *ret, const BIGNUM *a, BN_MONT_CTX *mont, return (retn); } +int bn_to_mont_fixed_top(BIGNUM *r, const BIGNUM *a, BN_MONT_CTX *mont, + BN_CTX *ctx) +{ + return bn_mul_mont_fixed_top(r, a, &(mont->RR), mont, ctx); +} + BN_MONT_CTX *BN_MONT_CTX_new(void) { BN_MONT_CTX *ret; @@ -337,7 +354,7 @@ void BN_MONT_CTX_free(BN_MONT_CTX *mont) int BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx) { - int ret = 0; + int i, ret = 0; BIGNUM *Ri, *R; if (BN_is_zero(mod)) @@ -468,6 +485,11 @@ int BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx) if (!BN_mod(&(mont->RR), &(mont->RR), &(mont->N), ctx)) goto err; + for (i = mont->RR.top, ret = mont->N.top; i < ret; i++) + mont->RR.d[i] = 0; + mont->RR.top = ret; + mont->RR.flags |= BN_FLG_FIXED_TOP; + ret = 1; err: BN_CTX_end(ctx); diff --git a/freebsd/crypto/openssl/crypto/bn/bn_sqr.c b/freebsd/crypto/openssl/crypto/bn/bn_sqr.c index 759d5d20..bc52dfd0 100644 --- a/freebsd/crypto/openssl/crypto/bn/bn_sqr.c +++ b/freebsd/crypto/openssl/crypto/bn/bn_sqr.c @@ -137,14 +137,8 @@ int BN_sqr(BIGNUM *r, const BIGNUM *a, BN_CTX *ctx) } rr->neg = 0; - /* - * If the most-significant half of the top word of 'a' is zero, then the - * square of 'a' will max-1 words. - */ - if (a->d[al - 1] == (a->d[al - 1] & BN_MASK2l)) - rr->top = max - 1; - else - rr->top = max; + rr->top = max; + bn_correct_top(rr); if (r != rr && BN_copy(r, rr) == NULL) goto err; |