summaryrefslogtreecommitdiff
path: root/src/lib/libcrypto/bn (follow)
Commit message (Collapse)AuthorAgeFilesLines
...
* Remove the get_rfc*_prime_*() APItb2023-07-282-66/+2
| | | | | | | Inconsistently named with the rest of the API, so OpenSSL 1.1 introduced the same functions with a BN_ prefix. We'll keep the latter. ok jsing
* Make BN_BLINDING internaltb2023-07-283-35/+24
| | | | | | | | | | RSA is pretty bad. In my most optimistic moments I dream of a world that stopped using it. That won't happen during my lifetime, unfortunately. Blinding is one way of making it a little less leaky. Unfortunately this side-channel leak mitigation leaked out of the library for no good reason. Let's at least fix that aspect of it. ok jsing
* Mark read/write registers as non-overlapping for bn_qwmulw_{addqw_,}addw()jsing2023-07-241-3/+3
| | | | | | This does not cause an issue currently, however if called differently to their current usage, it can lead to an input being overwritten and incorrect results being generated.
* Simplify indent handling in bn_print()tb2023-07-221-6/+3
| | | | variant of a suggestion by jsing
* Cap the size of numbers we check for primalitytb2023-07-201-1/+12
| | | | | | | | | | | We refuse to generate RSA keys larger than 16k and DH keys larger than 10k. Primality checking with adversarial input is a DoS vector, so simply don't do this. Introduce a cap of 32k for numbers we try to test for primality, which should be more than large enough for use withing a non-toolkit crypto library. This is one way of mitigating the DH_check()/EVP_PKEY_param_check() issue. ok jsing miod
* Pull BIGNUM constants out of get_* function bodiestb2023-07-101-315/+331
| | | | | | | | | The get_rfc*_prime_* functions will be removed. The constants will remain for the BN_get_rfc*_prime_* functions. Make the latter call BN_bin2bn() directly on these constants rather than going through get_*. This avoids some overlong lines. Also KNF for some comments. Reduces the diff I currently carry by quite a bit.
* bn_print: string.h is no longer neededtb2023-07-101-2/+1
|
* Reimplement BN_print() and BN_print_fp()tb2023-07-092-47/+45
| | | | | | | | These can now use the internal version of BN_bn2hex() and be direct wrappers of BIO_printf() and fprintf() as they should have been all along. ok jsing
* Simplify bn_print()tb2023-07-091-5/+3
| | | | | | | We no longer need to do weird things as taking the length of the hex string and jumping over a sign we didn't need. ok jsing
* Refactor BN_bn2hex()tb2023-07-092-8/+57
| | | | | | | | | Various outputting functions are variants of BN_bn2hex(). They do not want a sign or they display the BIGNUM at nibble granularity instead of byte granularity. So add this functionality to an internal variant of BN_bn2hex(). with/ok jsing
* Provide optimised bn_subw() for riscv64.jsing2023-07-091-1/+18
|
* Provide optimised bn_addw() for riscv64.jsing2023-07-091-1/+18
|
* Hide symbols in bnbeck2023-07-0818-18/+152
| | | | ok tb@
* Provide optimised bn_mulw() for riscv64.jsing2023-07-071-7/+11
| | | | | This provides a 1.5-2x performance gain for BN multiplication, with a similar improvement being seen for RSA operations.
* Use an unsigned long long and corresponding formatstb2023-07-071-3/+3
| | | | | | Fixes build on 32 bit. Reported by claudio
* Insert leading octet if high bit of first nibble is 1tb2023-07-071-1/+7
| | | | | | | The reason the function this replaces is called ASN1_bn_print() is that it actually prints a representation of the ASN.1 encoding. ok jsing
* Add bn_printf(), a replacement for ASN1_bn_print()tb2023-07-062-1/+152
| | | | | | | | | | ASN1_bn_print() will be removed in an upcoming bump. This adds an internal API that covers the same functionality but doesn't require that the caller pass in a sufficiently large scratch space that ASN1_bn_print() may or may not use. In addition, this takes a format string, which allows us to ditch some extra dances. ok jsing
* Replace bn_sqr_words() with bn_sqr_add_words().jsing2023-07-021-35/+23
| | | | | | | | | | | | | | In order to implement efficient squaring, we compute the sum of products (omitting the squares), double the sum of products and then finally compute and add in the squares. However, for reasons unknown the final calculation was implemented as two separate steps. Replace bn_sqr_words() with bn_sqr_add_words() such that we do the computation in one step, avoid the need for temporary BN and remove needless overhead. This gives us a performance gain across most architectures (even with the loss of sse2 on i386, for example). ok tb@
* Provide additional BN primitives for BN_ULLONG architectures.jsing2023-06-251-21/+79
| | | | | | | | | | | | | | | | | On BN_ULLONG architectures, the C compiler can usually do a decent job of optimising primitives, however it struggles to see through primitive calls due to type narrowing. As such, providing explicit versions of compound primitives can result in the production of more optimal code. For example, on arm the bn_mulw_addw_addw() primitive can be replaced with a single umaal instruction, which provides significant performance gains. Rather than intermingling #ifdef/#else throughout the header, the BN_ULLONG defines are pulled up above the normal functions. This also allows complex compound primitives to be reused. The conditionals have also been changed from BN_LLONG to BN_ULLONG, since that is what really matters. ok tb@
* Add conditional around bn_mul_words() call.jsing2023-06-241-2/+4
| | | | | At least one of our bn_mul_words() assembly implementation fails to handle n = 0 correctly... *sigh*
* Assign and test.jsing2023-06-241-3/+2
|
* Check for non-zero length rather than a zero value.jsing2023-06-241-2/+2
| | | | | | This removes a data dependent timing path from BN_sqr(). ok tb@
* Rewrite and simplify bn_sqr()/bn_sqr_normal().jsing2023-06-243-39/+44
| | | | | | | | | Rework bn_sqr()/bn_sqr_normal() so that it is less convoluted and more readable. Instead of recomputing values that the caller has already computed, pass it as an argument. Avoid branching and remove duplication of variables. Consistently use a_len and r_len naming for lengths. ok tb@
* Provide optimised bn_subw() and bn_subw_subw() for arm.jsing2023-06-241-1/+50
|
* Avoid crash in BN_asc2bn()tb2023-06-231-2/+3
| | | | | | | | | | | | | | | | | | Historically (and currently in OpenSSL), BN_asc2bn() could be called with NULL, but only for positive numbers. So BN_asc2bn(NULL, "1") would succeed but BN_asc2bn(NULL, "-1"), would crash. The other *2bn functions return a length, so accepting a NULL makes some sense since it allows callers to skip over part of the string just parsed (atoi-style). For BN_asc2bn() a NULL bn makes no sense because it returns a boolean. The recent CBS rewrite makes BN_asc2bn(NULL, *) always crash which in turn made Coverity throw a fit. Another change of behavior from that rewrite pertains to accidents (or is it madness?) like -0x-11 and 0x-11 being parsed as decimal -17 (which Ingo of course spotted and diligently documented). This will be addressed later. ok jsing
* Fix return check of bn_hex2bn_cbs()tb2023-06-231-3/+3
| | | | | | | It returns a length, not a Boolean, so check for 0 explicitly. This is purely cosmetic. ok jsing
* typo: hexidecimal -> hexadecimaltb2023-06-231-2/+2
|
* Provide optimised bn_clzw() for aarch64.jsing2023-06-211-1/+15
|
* Provide and use bn_clzw() in place of bn_word_clz().jsing2023-06-213-5/+15
| | | | | | | | | | On some architectures, we can provide an optimised (often single instruction) count-leading-zero implementation. In order to do this effectively, provide bn_clzw() as a static inline that can be replaced by an architecture specific version. The default implementation defers to the bn_word_clz() function (which may also be architecture specific). ok tb@
* Make BN_num_bits() independent of bn->top.jsing2023-06-214-32/+72
| | | | | | | | Provide bn_bitsize(), which performs a constant time scan of a BN in order to determine the bit size of the BN value. Use this for BN_num_bits() such that it is no longer dependent on the bn->top value. ok tb@
* Optimise bn_mul2_mulw_addtw() for aarch64.jsing2023-06-171-1/+28
| | | | | This provides significant performance gains for bn_sqr_comba4() and bn_sqr_comba8().
* Speed up Montgomery multiplication.jsing2023-06-171-10/+37
| | | | | | | | | | Factor out and optimise the inner loop for Montgomery multiplication, making use of bn_qwmulw_addqw_addw() to perform Montgomery multiplication by one word in larger steps. This provides a significant performance gain, especially on platforms where bn_qwmulw_addqw_addw() is (or can be) optimised. ok tb@
* Disallow aliasing of return value and modulustb2023-06-131-1/+44
| | | | | | | | | | | All the functions changed in this commit would silently misbehave if the return value aliases the modulus, most of the time they would succeed and return an incorrect result of 0 in that situation. This adjusts all the functions in BN_mod.c, others and documentation will follow later. Prompted by a bug report about BN_mod_inverse() by Guido Vranken. ok jsing
* Add a BN_R_INVALID_ARGUMENT error codetb2023-06-132-2/+4
| | | | | | | | | | One problem with OpenSSL error codes is that they tend to be too specific (another problem is that they are extremely ugly). So add an EINVAL-style error code. This will be used in an upcoming commit to disallow aliasing of the 'return value' with the modulus in BN_mod_* functions and should be applicable elsewhere, outside of this one narrow use case. ok jsing
* Optimise quad word primitives on aarch64.jsing2023-06-121-1/+136
| | | | This provides a performance gain across most BN operations.
* Provide and use various quad word primitives.jsing2023-06-123-27/+120
| | | | | | | | This includes bn_qwaddqw(), bn_qwsubqw(), bn_qwmulw_addw() and bn_qwmulw_addqw_addw(). These can typically be optimised on architectures that have a reasonable number of general purpose registers. ok tb@
* Reinstate bn_isqrt.c r1.8 and crypto_lock.c r1.3tb2023-06-041-4/+2
| | | | | | | | | | | | | | | This traded local copies of CTASSERT() to the one in crypto_internal.h. This change was backed out due to SHA-512 breakage on STRICT_ALIGNMENT architectures still using Fred Flintstone's gcc without asm sha512. Original commit message: Use crypto_internal.h's CTASSERT() Now that this macro is available in a header, let's use that version rather than copies in several .c files. discussed with jsing
* Fix variable reuse in BN_mod_inverse()tb2023-06-021-21/+15
| | | | | | | | | | | | | | | | | | The somewhat strange calculation m = a^{-1} (mod m) can return 0. This breaks because of BN_nnmod() having delicate semantics of which variable can be reused. BN_nnmod(a, a, m, ctx) works and the library relies on that. Here, the code ends up doing BN_nnmod(m, a, m, ctx) and this doesn't work. If the result of the initial BN_mod() is negative, then BN_nnmod() will return 0. Problem reported by Guido Vranken in https://github.com/openssl/openssl/issues/21110 This code is well covered by regress, but it does not currently have explicit test coverage. Such will be added soon. ok beck jsing
* Provide optimised bn_mulw_{addw,addw_addw,addtw}() for aarch64.jsing2023-05-281-1/+68
| | | | | This results in bn_mul_comba4() and bn_mul_comba8() requiring ~30% less instructions than they did previously.
* Provide optimised bn_addw_addw()/bn_subw_subw() for aarch64.jsing2023-05-281-1/+43
|
* Rewrite BN_{asc,dec,hex}2bn() using CBS.jsing2023-05-281-123/+224
| | | | | | | | | | | This gives us more readable and safer code. There are two intentional changes to behaviour - firstly, all three functions zero any BN that was passed in, prior to doing any further processing. This means that a passed BN is always in a known state, regardless of what happens later. Secondly, BN_asc2bn() now fails on NULL input, rather than crashing. This brings its behaviour inline with BN_dec2bn() and BN_hex2bn(). ok tb@
* backout alignment changes (breaking at least two architectures)deraadt2023-05-191-2/+4
|
* Use crypto_internal.h's CTASSERT()tb2023-05-171-4/+2
| | | | | | | Now that this macro is available in a header, let's use that version rather than copies in several .c files. discussed with jsing
* Use is_pseudoprime instead of is_prime in bn_bpsw.ctb2023-05-101-30/+33
| | | | | | | This is more accurate and improves readability a bit. Apart from a comment tweak this is sed + knfmt (which resulted in four wrapped lines). Discussed with beck and jsing
* Add Miller-Rabin test for random bases to BPSWtb2023-05-103-33/+130
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | The behavior of the BPSW primality test for numbers > 2^64 is not very well understood. While there is no known composite that passes the test, there are heuristics that indicate that there are likely infinitely many. Therefore it seems appropriate to harden the test. Having a settable number of MR rounds before doing a version of BPSW is also the approach taken by Go's primality check in math/big. This adds a new implementation of the old MR test that runs before running the strong Lucas test. I like to imagine that it's slightly cleaner code. We're effectively at about twice the cost of what we had a year ago. In addition, it adds some non-determinism in case there actually are false positives for the BPSW test. The implementation is straightforward. It could easily be tweaked to use the additional gcds in the "enhanced" MR test of FIPS 186-5, but as long as we are only going to throw away the additional info, that's not worth much. This is a first step towards incorporating some of the considerations in "A performant misuse-resistant API for Primality Testing" by Massimo and Paterson. Further work will happen in tree. In particular, there are plans to crank the number of Miller-Rabin tests considerably so as to have a guaranteed baseline. The manual will be updated shortly. positive feedback beck ok jsing
* bn_exp: also special case -1 modulustb2023-05-091-6/+6
| | | | | | | | | | Anything taken to the power of 0 is 1, and then reduced mod 1 or mod -1 it will be 0. If "anything" includes 0 or not is a matter of convention, but it should not depend on the sign of the modulus... Reported by Guido Vranken ok jsing (who had the same diff)
* Rewrite BN_bn2hex() using CBB/CBS.jsing2023-05-091-25/+35
| | | | ok tb@
* Rewrite BN_bn2dec() using CBB/CBS.jsing2023-05-091-63/+61
| | | | ok tb@
* Garbage collect BN_zero_ex()tb2023-04-301-7/+1
|
* whitespacetb2023-04-301-2/+2
|