summaryrefslogtreecommitdiff
path: root/src/lib/libcrypto/bn (follow)
Commit message (Collapse)AuthorAgeFilesLines
...
* Fix an off-by-one bug in BN_GF2m_poly2arr(3).schwarze2022-11-201-4/+3
| | | | | | | | | | | | | | | | | | | | | If the last argument, the size of the output array, is too small to contain all degrees present in the input polynomial plus one for the terminating -1, the function is documented to return the size of the output array that would be needed (in comments in the source code, in the new manual page, and by the way how the function is used by other functions in the same file). However, in case of overflow, the existing code failed to include the element needed for the terminating -1 in the return value, wrongly indicating success if everything but the -1 did fit and reporting failure with a size that was still too small otherwise. According to tb@, this is very unlikely to cause vulnerabilities in practical applications because there is no real reason to pick a reducing polynomial longer than a pentanomial, because all known callers use either fixed size arrays of size 6 or dynamic allocation, because use of GF(2^m) is rare in practice, and GF(2^m) with custom reducing polynomials even more so. OK tb@
* Fix comment describing BN_mod_sqrt()tb2022-11-191-7/+9
| | | | | It was placed and formatted weirdly. Fix the title of the book referenced and complete the reference's information.
* Move bn_prime.h to the public domain.tb2022-11-101-57/+4
| | | | | | It's entirely trivial. ok beck
* Move table in bn_primes.h to a .c file and get rid of prime_ttb2022-11-094-333/+290
| | | | | | | This way we deduplicate two inclusions of the same big table and eliminate lots of stupid casts. input and ok many
* Inline use of bn_is_prime_bpsw()tb2022-11-091-24/+20
| | | | | | | | | Instead of using the BN_is_prime_fasttime_ex() API, use a direct call to bn_is_prime_bpsw(). This increases readability and simplifies error handling. Also put a division by two to the natural place now that we no longer need to do Miller-Rabin rounds. ok beck jsing
* Next pass of bn_prime.c cleanuptb2022-11-091-39/+29
| | | | | | | Garbage collect a few pointless variables and remove a loop that wasn't really a loop. Simplify BN_CTX handling and drop some stupid comments. ok jsing miod
* Drop some dead codetb2022-11-091-136/+1
| | | | ok jsing
* Fix possible memory leak in BN_mpi2bn() if BN_bin2bn() fails.tobhe2022-11-091-3/+7
| | | | | | found with CodeChecker feedback from millert@ ok tb@
* Fix path of mentioned regress testtb2022-10-111-2/+2
|
* Add an empty line for consistency.tb2022-08-311-1/+2
|
* missing periodtb2022-08-291-2/+2
|
* Tidy up some of BN_nist_mod_*jsing2022-07-311-22/+30
| | | | | | | Shuffle variables around for consistency, also ensuring appropriate and consistent initialisation. ok tb@
* Use named initialisers for BIGNUMs.jsing2022-07-301-61/+65
| | | | | | | Also move the _bignum_nist_p_.*_sqr static BIGNUMs out of individual functions. ok tb@
* Having a perfect square at this point is not an error. Rather it istb2022-07-291-2/+2
| | | | | a shortcut bypassing expensive computation, so change goto err to goto done. Bug introduced in last refactoring before commit.
* Tweak some comments and whitespace around commentstb2022-07-291-9/+32
|
* Avoid unnecessary loops in BN_generate_prime_ex()tb2022-07-191-4/+6
| | | | | | | | | Since there is nothing randomized in bn_is_prime_bpsw(), the concept of rounds makes no sense. Apply a minimal change for now that avoids expensive loops that won't change the outcome in case we found a probable prime. ok jsing
* Expand the comment explaining the for loop with bn_lucas_step() a bit.tb2022-07-151-3/+3
|
* Comment for factorization of n - 1 = k * 2^s in bn_miller_rabin_base_2()tb2022-07-151-1/+2
|
* Rename is_perfect_square to out_perfect in prototype to matchtb2022-07-151-2/+2
| | | | the code in bn_isqrt.c.
* Do not make tables static so we can access them from regress.tb2022-07-131-5/+5
|
* Enable BPSW primality test.tb2022-07-131-1/+3
| | | | ok jsing
* Hook BPSW into BN_is_prime_fasttest_ex()tb2022-07-131-3/+13
| | | | ok jsing
* Implement the Baillie-PSW primality testtb2022-07-132-1/+423
| | | | | | | | | | | | | | | | | | | | | | | | | | | It has long been known that pure Miller-Rabin primality tests are insufficient. "Prime and Prejudice: Primality Testing Under Adversarial Conditions" https://eprint.iacr.org/2018/749 points out severe flaws in many widely used libraries. In particular, they exhibited a method to generate 2048-bit composites that bypass the default OpenSSL (and hence LibreSSL) primality test with a probability of 1/16 (!). As a remedy, the authors recommend switching to using BPSW wherever possible. This possibility has always been there, but someone had to sit down and actually implement a properly licensed piece of code. Fortunately, espie suggested to Martin Grenouilloux to do precisely this after asking us whether we would be interested. Of course we were! After a good first implementation from Martin and a lot of back and forth, we came up with the present version. This implementation is ~50% slower than the current default Miller-Rabin test, but that is a small price to pay given the improvements. Thanks to Martin Grenouilloux <martin.grenouilloux () lse ! epita ! fr> for this awesome work, to espie without whom it wouldn't have happened, and to djm for pointing us at this problem a long time back. ok jsing
* Integer square root and perfect square testtb2022-07-132-1/+241
| | | | | | | | | | | | | | This adds an implementation of the integer square root using a variant of Newton's method with adaptive precision. The implementation is based on a pure Python description of cpython's math.isqrt(). This algorithm is proven to be correct with a tricky but very neat loop invariant: https://github.com/mdickinson/snippets/blob/master/proofs/isqrt/src/isqrt.lean Using this algorithm instead of Newton method, implement Algorithm 1.7.3 (square test) from H. Cohen, "A course in computational algebraic number theory" to detect perfect squares. ok jsing
* Move BN_lsw() to bn_lcl.h so that other code can use it.tb2022-07-122-5/+5
| | | | ok jsing
* Remove mkerr.pl remnants from LibreSSLkn2022-07-122-12/+2
| | | | | | | This script is not used at all and files are edited by hand instead. Thus remove misleading comments incl. the obsolete script/config. Feedback OK jsing tb
* Expose new API in headers.tb2022-07-071-3/+1
| | | | | | | These are mostly security-level related, but there are also ASN1_TIME and ASN_INTEGER functions here, as well as some missing accessors. ok jsing
* Prepare to provide BN_security_bits()tb2022-06-272-2/+37
| | | | ok beck jsing
* Error out on negative shifts in BN_{r,l}shift()tb2022-06-221-1/+13
| | | | | | | | | | Without these checks in both functions nw = n / BN_BITS2 will be negative and this leads to out-of-bounds accesses via negative array indices and memset with a negative size. Pointed out by cheloha ok jsing
* Tweak a commenttb2022-06-201-2/+2
|
* Flip roles of lowercase and uppercase A and B.tb2022-06-201-44/+44
| | | | | | | This matches Cohen's text better and makes the entire thing easier to read. suggested by jsing
* Clean up BN_kronecker()tb2022-06-201-73/+88
| | | | | | | | | | Instead of "Cohen's step N" explain in words what is being done. Things such as (A & B & 2) != 0 being equivalent to (-1)^((A-1)(B-1)/4) being negative are not entirely obvious... Remove the strange error dance and adjust variable names to what Cohen's book uses. Simplify various curly bits. ok jsing
* Fix some bizarre indentation and line breaks.tb2022-06-201-8/+7
|
* Fix prime recognition when doing trial divisionstb2022-06-181-2/+2
| | | | | | | | | If gcd(a, primes[i]) == 0 then a could still be a prime, namely in the case that a == primes[i], so check for that case as well. Problem noted by Martin Grenouilloux ok jsing
* Avoid strict aliasing violations in BN_nist_mod_*()jsing2022-05-071-86/+137
| | | | | | | | | | | | | | | | | | | | | | | The optimised code path switches from processing data via unsigned long to processing data via unsigned int, which requires type punning. This is currently attempted via a union (for one case), however this fails since a pointer to a union member is passed to another function (these unions were added to "fix strict-aliasing compiler warning" - it would seem the warnings stopped but the undefined behaviour remained). The second case does not use a union and simply casts from one type to another. Undefined behaviour is currently triggered when compiling with clang 14 using -03 and -fstrict-aliasing, while disabling assembly (in order to use this C code). The resulting binary produces incorrect results. Avoid strict aliasing violations by copying from an unsigned long array to an unsigned int array, then copying back the result. Any sensible compiler will omit the copies, while avoiding undefined behaviour that would result from unsafe type punning via pointer type casting. Thanks to Guido Vranken for reporting the issue and testing the fix. ok tb@
* Avoid use of uninitialized in BN_mod_exp_recp()tb2022-04-201-2/+3
| | | | | | | | | | If either of the two initial BN_CTX_get() fails, we will call BN_RECP_CTX_free() on the uninitialized recp, which won't end well, so hoist the BN_RECP_CTX_init() call a few lines up. From Pauli, OpenSSL ad249412 ok inoguchi jsing
* Fix infinite loop in BN_mod_sqrt()tb2022-03-151-14/+15
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | A bug in the implementation of the Tonelli-Shanks algorithm can lead to an infinite loop. This loop can be hit in various ways, in particular on decompressing an elliptic curve public key via EC_POINT_oct2point() - to do this, one must solve y^2 = x^3 + ax + b for y, given x. If a certificate uses explicit encoding for elliptic curve parameters, this operation needs to be done during certificate verification, leading to a DoS. In particular, everything dealing with untrusted certificates is affected, notably TLS servers explicitly configured to request client certificates (httpd, smtpd, various VPN implementations, ...). Ordinary TLS servers do not consume untrusted certificates. The problem is that we cannot assume that x^3 + ax + b is actually a square on untrusted input and neither can we assume that the modulus p is a prime. Ensuring that p is a prime is too expensive (it would likely itself lead to a DoS). To avoid the infinite loop, fix the logic to be more resilient and explicitly limit the number of iterations that can be done. The bug is such that the infinite loop can also be hit for primes = 3 (mod 4) but fortunately that case is optimized earlier. It's also worth noting that there is a size bound on the field size enforced via OPENSSL_ECC_MAX_FIELD_BITS (= 661), which help mitigate further DoS vectors in presence of this fix. Reported by Tavis Ormandy and David Benjamin, Google Patch based on the fixes by David Benjamin and Tomas Mraz, OpenSSL ok beck inoguchi
* Avoid a NULL dereference in BN_mod_exp2_mont()tb2022-02-071-2/+2
| | | | | | | | | | This is a very rarely used function and the crash is hard to reach in practice. Instead of implementing BN_is_odd() badly by hand, just call the real thing. Reported by Guido Vranken ok beck jsing
* Check for zero modulus in BN_MONT_CTX_set().tb2022-02-071-1/+4
| | | | | | From OpenSSL 6a009812, prompted by a report by Guido Vranken ok beck jsing
* Add and fix check for BN functions return valueinoguchi2022-01-201-4/+5
| | | | ok jsing@ millert@ tb@
* Add check for BN functions return valueinoguchi2022-01-201-3/+5
| | | | | | | CID 21665 24835 comment from jsing@ and tb@ ok jsing@ millert@ tb@
* Move BN structs to bn_lcl.htb2022-01-142-50/+46
| | | | | | This makes all structs in bn.h opaque that are also opaque in OpenSSL. ok inoguchi jsing
* Unifdef LIBRESSL_OPAQUE_* and LIBRESSL_NEXT_APItb2022-01-141-65/+1
| | | | | This marks the start of major surgery in libcrypto. Do not attempt to build the tree for a while (~50 commits).
* Pull BN_{new,init,clear,clear_free,free} up to the top of bn_lib.cjsing2021-12-271-58/+58
| | | | Discussed with tb@
* Consistently call BN_init() before BN_with_flags()tb2021-12-261-13/+27
| | | | | | | | | | | | | | | | BN_with_flags() preserves the BN_FLG_MALLOCED flag of the destination which results in a potential use of an uninitialized bit. In practice this doesn't matter since we don't free the cloned BIGNUMs anyway. As jsing points out, these are mostly pointless noise and should be garbage collected. I'll leave that for another rainy day. Coverity flagged one instance BN_gcd_no_branch(), the rest was found by the ever so helpful grep(1). CID 345122 ok jsing
* Annotate the structs to be moved to bn_lcl.h in the next bumptb2021-12-041-1/+5
| | | | ok inoguchi jsing
* Use BN_is_negative(p) instead of p->neg in one place.tb2021-12-041-2/+2
|
* Implement the BN_to_montgomery() macro as a functiontb2021-12-042-2/+13
| | | | ok inoguchi jsing
* Implement the BN_is_negative macro as a functiontb2021-12-042-2/+13
| | | | ok inoguchi jsing
* Provide function implementations for various BN_* macrostb2021-12-042-4/+54
| | | | | | | | BN_abs_is_word, BN_is_{zero,one,word,odd}, BN_one, BN_zero_ex are now implemented as functions for internal use. They will be exposed publicly to replace the macros reaching into BIGNUM in the next bump. ok inoguchi jsing
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-08-26 23:33:02 +0000