summaryrefslogtreecommitdiff
path: root/src/lib/libcrypto/bn (follow)
Commit message (Collapse)AuthorAgeFilesLines
...
* Move BN_options() from bn_convert.c to bn_lib.cjsing2023-04-192-21/+21
|
* unifdef BN_RECURSIONjsing2023-04-195-594/+5
| | | | | | | | | | | | This removes a bunch of incomplete and scary code, which potentially leaks secrets and is not constant time. A performance gain is achieved on arm64 for sizes that we care about, while a minimal decrease in performance is noted for larger sizes on some other platforms. While we will potentially reimplement Karatsuba (or Toom-Cook) at a later date, it will be easier and safer to do it from a clean slate. ok tb@
* Tweak indent and use named registers.jsing2023-04-171-13/+13
| | | | No functional change.
* Move BN_bn2mpi()/BN_mpi2bn() into bn_convert.cjsing2023-04-172-136/+73
|
* Mark X9.31 BN API for removaltb2023-04-161-1/+4
| | | | | | | This supports a mostly forgotten, seemingly unused and long retired standard. No need for this in our public API Dyson sphere. ok jsing
* The BN reciprocal API will also become internal-onlytb2023-04-161-1/+7
| | | | | | | This is unused outside of the library and could do with some reworking. That's easier without having to care about outside consumers. ok jsing
* Various BN*init() will be removed from the public APItb2023-04-161-1/+10
| | | | | | | | With the corresponding structs now being opaque, the only thing they are good for outside the library are memory leaks. They will be removed completely or become internal only. ok jsing
* Mark public bn_nist and ec_nist API for removaltb2023-04-161-1/+3
| | | | | | | | | | | | | The faster nist code is rife with problematic C. While this is generally considered to be a pleonasm nowadays, here it specifically refers to aliasing issues and other flavors of undefined behavior. With compilers and standardization committees becoming seemingly more determined about making C even more unusable than it already is, this code has resulted in miscompilations and generally is a target rich environment for fuzzers to feast on. We're better off without it. Go look while it's still there. It's some of the very worst we have to offer. ok jsing
* Remove now unused GF2m perlasm generatorstb2023-04-153-980/+0
|
* Rename the largely misnamed bn_print.c to bn_convert.cjsing2023-04-141-1/+1
| | | | | | | | This file primarily contains the various BN_bn2*() and BN_*2bn() functions (along with BN_print() and BN_options()). More function shuffling will follow. Discussed with tb@
* Provide and use bn_copy_words() in BN_copy().jsing2023-04-141-31/+15
| | | | | | | | This is simpler than the current code, while still being well optimised by compilers, across a range of architectures. In many cases we even get a performance gain for the BN sizes that we primarily care about. Joint work with tb@
* Add a new implementation of BN_mod_sqrt()tb2023-04-112-409/+726
| | | | | | | | | | | | | | | | | | | This is a reimplementation from scratch of the Tonelli-Shanks algorithm based on Henri Cohen "A Course in Computational Algebraic Number Theory", Springer GTM 138, section 1.5.1. It is API compatible with the previous implementation, so no documentation change is required. Contrary to the old implementation, this does not have any infinite loops and has various additional sanity checks to prevent misbehavior in case the input modulus is not a prime. It contains extensive comments and the individual parts of the algorithm are split into digestible chunks instead of having one huge function. One difference of note is that it BN_mod_sqrt() now always returns the smaller of the two possible answers. In other words, while its core is non-deterministic, its answer is not. ok jsing
* Remove some doubled empty linestb2023-04-091-7/+1
|
* bn_mont: fix typo in comment divisable -> divisibletb2023-04-071-2/+2
|
* Compress euclid() a littletb2023-04-031-49/+28
| | | | | | | | | | This function is spread out over way too many lines and has too much repetition. Once this is made a little more compact, it becomes clearer that this is a somewhat obfuscated version of binary gcd (it is not constant time therefore cryptographically unsound. It is not used internally). This will likely go away later. ok jsing
* Pull static const data out of BN_value_one()tb2023-04-011-7/+11
| | | | | | Also use C99 initializers for readability. discussed with jsing
* Indent labelstb2023-04-011-6/+6
|
* Group the non-constant time gcd functions togethertb2023-04-011-45/+45
| | | | | | | | The only consumer of euclid() is BN_gcd(), which, in turn is only used by BN_gcd_nonct(). Group them together rather than having parts of the constant time implementation separate them. This moves two functions to a different place in the file.
* Copy BN_FLG flags in BN_copy()tb2023-03-311-1/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | BN_copy() forgot to copy the flags from the source to the target. Fix this by copying the flags. In fact, only copy BN_FLG_CONSTTIME since propagating BN_FLG_MALLOCED and BN_FLG_STATIC_DATA is wrong. Ignore the BN_FLG_FREE flag "used for debugging" which of course means "unused" like a lot of other debug code that somehow ended up in public headers. Also: make BN_FLG_CONSTTIME sticky on the target, i.e., don't clear the flag when copying from a non-constant time BIGNUM to a constant time one for the following reason: if a is constant time, BN_sqr(a, a, ctx) would use a BIGNUM without the flag internally, then copy the result to a in which process a would lose its constant time flag. Fixing this would be a lot of pointless work since someone had the good sense of not relying on a fragile flag for something this important. Rather, libcrypto always uses the constant time paths instead of the faster, cryptographically inadequate paths. Before this was changed, this was a pretty bad bug. The RSA code uses the horrible BN_with_flags() function to create local versions of the private moduli and set BN_FLG_CONSTTIME on them. If the RSA_FLAG_CACHE_PRIVATE for caching moduli is set on the RSA, which it is by default, it attempts to set these constant time versions on the RSA's internal Montgomery contexts. Since it is called BN_MONT_CTX_set(), the setter doesn't set a BIGNUM on the BN_MONT_CTX, rather it copies it over, losing the BN_FLG_CONSTTIME flag in the process and make all the horrible leaky RSA code leak some more. Good job. This is all harmless and is mostly a cosmetic fix. BN_FLG_CONSTTIME should be removed internally. It will be kept since various language bindings of course picked it up and expose it. ok beck jsing
* Call bn_copy() unconditionally in BN_mul() and BN_sqr()tb2023-03-302-11/+6
| | | | | | | bn_copy() does the right thing if source and target are the same, so there is no need for an additional check. Requested by jsing
* Rework BN_exp() a bittb2023-03-301-27/+28
| | | | | | | | | This mostly only cleans up the mess that it was - which doesn't stand out because of the horror that lurks in the rest of this file. It avoids copying the partial calculation out on error and does away with some other weirdness. with/ok jsing
* Replace the remaining BN_copy() with bn_copy()tb2023-03-2710-38/+38
| | | | ok jsing
* Convert BN_copy() with missing error checks to bn_copy()tb2023-03-273-9/+15
| | | | ok jsing
* Convert BN_copy() with explicit comparison against NULL to bn_copy()tb2023-03-276-23/+23
| | | | ok jsing
* Use bn_copy() rather than inlining ittb2023-03-271-2/+2
| | | | ok jsing
* Drop unnecessary parentheses.tb2023-03-271-3/+3
| | | | ok jsing
* Convert bn_nist.c to BN_copy()tb2023-03-271-6/+6
| | | | | | | Like everything else in this file, the use of BN_copy() needs to be ... special. Simplify using the new bn_copy(). ok jsing
* Add bn_copy(), a sane wrapper of BN_copy() for internal usetb2023-03-272-2/+10
| | | | ok jsing
* Minor whitespace tidyingtb2023-03-262-6/+7
|
* Make several calls to BN_nnmod() unconditionaltb2023-03-261-19/+10
| | | | | | | | This removes a potential branch in a sensitive function and makes the code a lot simpler. It is a really bad idea optimize here for what davidben aptly calls "calculator" purposes. ok jsing
* Correctly reduce negative inpot to BN_mod_exp2_mont()tb2023-03-261-3/+3
| | | | | | | | | | Negative bases could result in a negative modulus being returned. This is not strictly speaking incorrect but slightly surprising. This is all a consequence of the shortcut of defining BN_mod() as a macro using BN_div(). Fixes ossfuzz #55997 ok jsing
* bn_prime.pl: fix shebang and a couple more whitespace tweakstb2023-03-261-3/+4
|
* Use strict and warningstb2023-03-251-1/+6
|
* Make an attempt at reducing the eyebleed in bn_prime.pltb2023-03-251-24/+18
| | | | | Use a style more resembling KNF and drop lots of parentheses. Simplify a few things. No change in generated output on success.
* Use Eric Young's usual license in the proper place rather than a weirdtb2023-03-251-12/+57
| | | | commented-out license stub in a HERE document.
* Add RCSIDtb2023-03-251-1/+1
|
* Add checks to ensure the uint16_t array isn't overflowed when thistb2023-03-251-0/+4
| | | | | script is run. This is more of an issue with uint16_t now than it was with prime_t aka BN_ULONG before r1.6.
* Zap an empty linetb2023-03-251-2/+1
|
* Ensure negative input to BN_mod_exp_mont_consttime() is correctly reduced.jsing2023-03-151-7/+4
| | | | | | | | | | A negative input to BN_mod_exp_mont_consttime() is not correctly reduced, remaining negative (when it should be in the range [0, m)). Fix this by unconditionally calling BN_nnmod() on the input. Fixes ossfuzz #55997. ok tb@
* Avoid -0 in BN_div_word().jsing2023-03-111-1/+5
| | | | | | | | | Currently, the use of BN_div_word() can result in -0 - avoid this by setting negative again, at the end of the computation. Should fix oss-fuzz 56667. ok tb@
* Correct sign handling in BN_add_word().jsing2023-03-111-3/+3
| | | | | | | | | | | | A sign handling bug was introduced to BN_add_word() in bn_word.c r1.18. When handling addition to a negative bignum, the BN_sub_word() call can result in the sign being flipped, which we need to account for. Use the same code in BN_sub_word() - while not technically needed here it keeps the code consistent. Issue discovered by tb@ ok tb@
* Improve bn_montgomery_multiply_words().jsing2023-03-071-10/+13
| | | | | | | | | | | | | Rather than calling bn_mul_add_words() twice - once to multiply and once to reduce - perform the multiplication and reduction in a single pass using bn_mulw_addw_addw() directly. Also simplify the addition of the resulting carries, which in turn allows us to avoid zeroing the top half of the temporary words. This provides a ~20-25% performance improvement for RSA operations on aarch64. ok tb@
* Slightly rework bn_mulw_addtw().jsing2023-03-071-5/+3
| | | | | | | | | Call bn_mulw_addw() rather than doing bn_mulw() follow by bn_addw(). This simplifies the code slightly, plus on some platforms bn_mulw_addw() can be optimised (and bn_mulw_addtw() will then benefit from such an optimisation). ok tb@
* Call BN_free() instead of BN_clear_free().jsing2023-03-072-7/+7
| | | | | | | BN_clear_free() is a wrapper that calls BN_free() - call BN_free() directly instead. ok tb@
* Limit bn_mul_mont() usage to sizes less than or equal to 8192 bits.jsing2023-03-071-1/+9
| | | | | | | | | | | | The assembly bn_mul_mont() implementations effectively use alloca() to allocate space for computation (at up to 8x the input size), without any limitation. This means that sufficiently large inputs lead to the stack being blown. Prevent this by using the C based implementation instead. Thanks to Jiayi Lin <jlin139 at asu dot edu> for reporting this to us. ok beck@ tb@
* Implement bn_montgomery_multiply()jsing2023-03-071-3/+86
| | | | | | | | | | | Provide a constant-time-style Montgomery multiplication implementation. Use this in place of the assembly bn_mul_mont() on platforms that either do not have an assembly implementation or have not compiled it in. Also use this as the fallback version for bn_mul_mont(), rather than falling back to a non-constant time implementation. ok beck@ tb@
* Refactor BN_mod_mul_montgomery().jsing2023-03-071-20/+48
| | | | | | | | | | Pull out the simplistic implementation (using BN_mul() or BN_sqr()) into a bn_mod_mul_montgomery_simple() function. Provide bn_mod_mul_montgomery() with an implementation that changes depending on if the assembly bn_mul_mont() is available or not. Turn BN_mod_mul_montgomery() and BN_to_montgomery() into callers of bn_mod_mul_montgomery(). ok beck@ tb@
* Delete unused and unsafe bn_mul_mont() example code.jsing2023-03-071-54/+1
| | | | | | This came from bn_asm.c and did not even compile until recently. ok beck@ tb@
* Fix comment for bn_mul2_mulw_addtw()jsing2023-03-071-5/+5
|
* Rewrite/simplify BN_from_montgomery_word() and BN_from_montgomery().jsing2023-02-281-92/+85
| | | | | | | | Rename BN_from_montgomery_word() to bn_montgomery_reduce() and rewrite it to be simpler and clearer, moving further towards constant time in the process. Clean up BN_from_montgomery() in the process. ok tb@
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-08-26 16:14:38 +0000