This is a rebased and squashed version of #767, adding safegcd-based implementations of constant-time and variable-time modular inverses for scalars and field elements, by Peter Dettman. The PR is organized as follows:
* **Add secp256k1_ctz{32,64}_var functions** Introduction of ctz functions to util.h (which use `__builtin_ctz` on recent GCC and Clang, but fall back to using a software emulation using de Bruijn on other platforms). This isn't used anywhere in this commit, but does include tests.
* **Add safegcd based modular inverse modules** Add Peter Dettman's safegcd code from #767 (without some of his optimizations, which are moved to later commits), turned into separate modules by me.
* **Add extensive comments on the safegcd algorithm and implementation** Add a long description of the algorithm and optimizations to `doc/safegcd_implementation.md`, as well as additional comments to the code itself. It is probably best to review this together with the previous commit (they're separated to keep authorship).
* **Add tests for modinv modules** Adds tests on the modinv interface directly, for arbitrary moduli.
* **Improve bounds checks in modinv modules** Adds a lot of sanity checking to the modinv modules.
* **Move secp256k1_scalar_{inverse{_var},is_even} to per-impl files** A pure refactor to prepare for switching the field and scalar code to modinv.
* **Make field/scalar code use the new modinv modules for inverses** Actually switch over.
* **Add extra modular inverse tests** This adds modular inverse tests through the field/scalar interface, now that those use modinv.
* **Remove unused Jacobi symbol support** No longer needed.
* **Remove num/gmp support** Bye-bye.
* 3 commits with further optimizations.
Peter Dettman [Wed, 16 Dec 2020 02:17:19 +0000 (18:17 -0800)]
Optimization: track f,g limb count and pass to new variable-time update_fg_var
The magnitude of the f and g variables generally goes down as the algorithm
progresses. Make use of this by keeping tracking how many limbs are used, and
when the number becomes small enough, make use of this to reduce the complexity
of arithmetic on them.
Pieter Wuille [Sat, 28 Nov 2020 23:58:22 +0000 (15:58 -0800)]
Optimization: special-case zero modulus limbs in modinv64
Both the field and scalar modulus can be written in signed{30,62} notation
with one or more zero limbs. Make use of this in the update_de function to
avoid a few wide multiplications when that is the case.
This doesn't appear to be a win in the 32-bit implementation, so only
do it for the 64-bit one.
Pieter Wuille [Mon, 12 Oct 2020 06:20:32 +0000 (23:20 -0700)]
Improve field/scalar inverse tests
Add a new run_inverse_tests that replaces all existing field/scalar inverse tests,
and tests a few identities for fixed inputs, small numbers (-999...999), random
inputs (structured and unstructured), as well as comparing with the output of
secp256k1_fe_inv_all_var.
Pieter Wuille [Wed, 23 Dec 2020 19:13:57 +0000 (11:13 -0800)]
Improve bounds checks in modinv modules
This commit adds functions to verify and compare numbers in signed{30,62} notation,
and uses that to do more extensive bounds checking on various variables in the modinv
code.
Pieter Wuille [Wed, 23 Dec 2020 02:24:36 +0000 (18:24 -0800)]
Add tests for modinv modules
This adds tests for the modinv{32,64}_impl.h directly (before the functions are used
inside the field/scalar code). It uses a naive implementation of modular multiplication
and gcds in order to verify the modular inverses themselves.
Tim Ruffing [Fri, 26 Feb 2021 14:52:40 +0000 (15:52 +0100)]
ci: Switch all Linux builds to Debian
The experiment of using Nix Shell was not really successful. Most
notably, Nix uses a bunch of wrapper scripts around compilers, which
make the build much less "pure". This may be useful but it's exactly
not what we want for CI. In particular, this resulted in gcc being used
for the "clang" builds because a wrapper script redefined the CC env
variable.
This now builds a single docker image (Debian) for all architectures
that we test in CI on Linux.
PiRK [Sun, 31 Jan 2021 17:41:35 +0000 (18:41 +0100)]
print warnings for conditional-uninitialized
This compiler flag is available for clang but not gcc.
Test plan:
```
autogen.sh
./configure
make check
CC=clang ./configure
make check
```
If a variable is used uninitialized, the warning should look something
like:
```
CC src/tests-tests.o
src/tests.c:4336:15: warning: variable 'recid' may be uninitialized when used here [-Wconditional-uninitialized]
CHECK(recid >= 0 && recid < 4);
^~~~~
./src/util.h:54:18: note: expanded from macro 'CHECK'
if (EXPECT(!(cond), 0)) { \
^~~~
./src/util.h:41:39: note: expanded from macro 'EXPECT'
^
src/tests.c:4327:14: note: initialize the variable 'recid' to silence this warning
int recid;
^
= 0
1 warning generated.
```
Tim Ruffing [Tue, 26 Jan 2021 08:36:14 +0000 (09:36 +0100)]
Merge #880: Add parens around ROUND_TO_ALIGN's parameter.
b6f649889ae78573f1959f04172a8e1fe15beab7 Add parens around ROUND_TO_ALIGN's parameter. This makes the macro robust against a hypothetical ROUND_TO_ALIGN(foo ? sizeA : size B) invocation. (Russell O'Connor)
Pull request description:
This makes the macro robust against a hypothetical `ROUND_TO_ALIGN(foo ? sizeA : size B)` invocation.
See also <https://wiki.sei.cmu.edu/confluence/display/c/PRE01-C.+Use+parentheses+within+macros+around+parameter+names>.
Jonas Nick [Mon, 25 Jan 2021 13:57:35 +0000 (13:57 +0000)]
Merge #874: Remove underscores from header defs.
fb390c5299e999e06b7dff9e77e373600fae9fdf Remove underscores from header defs. This makes them consistent with other files and avoids reserved identifiers. (Russell O'Connor)
See individual commit messages. These are improvements in preparation of the switch to Cirrus CI. (Maybe I'll just open a PR on top of this one.)
The first commit made the difference between successful build https://cirrus-ci.com/task/6740575057608704 and unsuccessful build https://cirrus-ci.com/task/4909571074424832.
I've tested the second commit without cross-compilation and with cross-compilation for android (https://github.com/bitcoin-core/secp256k1/issues/621#issuecomment-495703399)
When working on the autoconf stuff, I noticed two things that I just want to write down here:
- At some point we should update [build-aux/m4/ax_prog_cc_for_build.m4](https://www.gnu.org/software/autoconf-archive/ax_prog_cc_for_build.html). This is outdated, and [there have been a lot of fixes](https://github.com/autoconf-archive/autoconf-archive/pull/207) But the latest version is [broken](https://lists.gnu.org/archive/html/autoconf-archive-maintainers/2020-06/msg00002.html), so now is probably not the time.
- The latest autoconf 2.70 deprecates `AC_PROG_CC_C89`. It's not needed anymore because `AC_PROG_CC` cares about testing for version support. This makes autoconf 2.70 output a warning that we should probably just ignore. We don't want to force users onto 2.70...
With schnorrsig if you need to tweak the secret key (for BIP32) you must use the keypair API to get compatible secret/public keys which you do by calling `secp256k1_keypair_xonly_tweak_add()`, but after that there's no currently a way to extract the secret key back for storage.
so I added a `secp256k1_keypair_seckey` function to extract the key
Tim Ruffing [Sat, 2 Jan 2021 14:15:21 +0000 (15:15 +0100)]
Improve CC_FOR_BUILD detection
This commits simply uses CC as CC_FOR_BUILD and the same for
corresponding flags if we're not cross-compiling. This has a number of
benefits in this common case:
- It avoids strange cases where very old compilers are used (#768).
- Flags are consistently set for CC and CC_FOR_BUILD.
- ./configure is faster.
- You get compiler x consistently if you set CC=x; we got this wrong
in CI in the past.
./configure warns if a _FOR_BUILD variable is set but ignored because
we're not cross-compiling.
The change exposed that //-style comments are used in gen_context.c,
which is also fixed by this commit.
This commit also reorganizes code in configure.ac to have a cleaner
separation of sections.
Tim Ruffing [Wed, 23 Dec 2020 21:08:03 +0000 (22:08 +0100)]
Ask brew for valgrind include path
Valgrind is typically installed using brew on macOS. This commit
makes ./configure detect this case set the appropriate include
directory (in the same way as we already do for openssl and gmp).
I added all the openssl functions that we call in `tests.c` and in `bench_verify.c` to the m4 check, that way if any of them are missing it won't enable openssl.
I also modified it a little to prevent a segmentation fault when running that program (not that it really matters for autotools)
Tim Ruffing [Mon, 26 Oct 2020 13:38:30 +0000 (14:38 +0100)]
Return NULL early in context_preallocated_create if flags invalid
If the user passes invalid flags to _context_create, and the default
illegal callback does not abort the program (which is possible), then we
work with the result of malloc(0), which may be undefined behavior. This
violates the promise that a library function won't crash after the
illegal callback has been called.
This commit fixes this issue by returning NULL early in _context_create
in that case.
Fabien [Tue, 27 Oct 2020 07:43:10 +0000 (08:43 +0100)]
Run the undefined behaviour sanitizer on Travis
Run UBSAN with both GCC and Clang, on Linux and macOS.
The `halt_on_error=1` option is required to make the build fail if the
sanitizer finds an issue.
Fabien [Mon, 26 Oct 2020 11:29:00 +0000 (12:29 +0100)]
Prevent arithmetic on NULL pointer if the scratch space is too small
If the scratch space is too small when calling
`secp256k1_ecmult_strauss_batch()`, the `state.pre_a` allocation will
fail and the pointer will be `NULL`. This causes `state.pre_a_lam` to be
computed from the `NULL` pointer.
It is also possible that the first allocation to fail is for `state.ps`,
which will cause the failure to occur when in
`secp256k1_ecmult_strauss_wnaf()`.
The issue has been detected by UBSAN using Clang 10:
```
CC=clang \
CFLAGS="-fsanitize=undefined -fno-omit-frame-pointer" \
LDFLAGS="-fsanitize=undefined -fno-omit-frame-pointer" \
../configure
UBSAN_OPTIONS=print_stacktrace=1:halt_on_error=1 make check
```
Elichai Turkel [Wed, 21 Oct 2020 11:39:52 +0000 (14:39 +0300)]
Modify bitcoin_secp.m4's openssl check to call all the functions that we
use in the tests/benchmarks.
That way linking will fail if those symbols are missing
This is a rebased/combined version of the following pull requests/commits with minor changes:
* #825 Switch to our own memcmp function
* Modification: `secp256k1_memcmp_var` is marked static inline
* Modification: also replace `memcmp` with `secp256k1_memcmp_var` in exhaustive tests
* Modification: add reference to GCC bug 95189
* #822 Increase precision of g1 and g2
* Modification: use the new `secp256k1_memcmp_var` function instead of `memcmp` (see https://github.com/bitcoin-core/secp256k1/pull/822#issuecomment-706610361)
* Modification: drop the " Allow secp256k1_split_lambda_verify to pass even in the presence of GCC bug https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95189." commit, as it's dealt with using `secp256k1_memcmp_var`.
* Modification: rename secp256k1_gej_mul_lambda -> secp256k1_ge_mul_lambda
* A new commit that moves the `lambda` constant out of `secp256k1_scalar_split_lambda` and (`_verify`).
* The test commit suggested here: https://github.com/bitcoin-core/secp256k1/pull/822#issuecomment-706610276
* Modification: use the new accessible `secp256k1_const_lambda` instead of duplicating it.
* #826 Rip out non-endomorphism code
* A new commit that reduces the size of the WNAF output to 129, as we now have proof that the split output is always 128 bits or less.
* A new commit to more consistently use input:`k`, integer outputs:`k1`,`k2`, modulo n outputs:`r1`,`r2`
Gregory Maxwell [Sat, 10 Oct 2020 20:46:36 +0000 (20:46 +0000)]
Check correctness of lambda split without -DVERIFY
The VERIFY macro turns on various paranoid consistency checks, but
the complete functionality should still be tested without it.
This also adds a couple of static test points for extremely small
split inputs/outputs. The existing bounds vectors already check
extremely large outputs.
projects / secp256k1.git / log