Tim Ruffing [Thu, 19 Aug 2021 10:22:36 +0000 (12:22 +0200)]
tests: Rewrite code to circument potential bug in clang
clang 7 to 11 (and maybe earlier versions) warn about recid being
potentially unitiliazed in "CHECK(recid >= 0 [...]", which was mitigated
in commit 3d2cf6c5bd35b0d72716b47bdd7e3892388aafc4 by initializing recid
to make clang happy but VG_UNDEF'ing the variable after initializiation
in order to ensure valgrind's memcheck analysis will still be sound and
complain if recid is not actually written to when creating a signature.
However, it turns out that at least for binaries produced by clang 11
(but not clang 7), valgrind complains about a branch on unitialized data
in the recid variable in that line before *and* after the aforementioned
commit. While the complaint after the commit could be spurious (clang
knows that recid is initialized, so it's fine to access it even though
the access is stupid), the complaint before the commit indicates a real
problem: it might be the case that clang is performing a wrong
optimization that leads to a situation where recid is really not
guaranteed to be initialized when it's accessed. As a result, clang
warns about this and generates code that just accesses the variable.
I'm not going to bother with this further because this is fixed in
clang 12 and the problem is just in our test code, not in the tested
code.
This commit rewrites the code in a way that groups the signing together
with the CHECK such that it's very easy to figure out for clang that
recid will be initialized properly. This seems to circument the issue.
Tim Ruffing [Sun, 4 Jul 2021 00:03:18 +0000 (02:03 +0200)]
Don't use string literals for char arrays without NUL termination
unsigned char foo[4] = "abcd" is not valid C++ because the string
literal "abcd" does not fit into foo due to the terminating NUL
character. This is valid in C, it will just omit the NUL character.
This is a work in progress because I wanted to put this up for discussion before writing tests. It addresses the TODOs that didn't make it in the schnorrsig PR and changes the APIs of `schnorrsig_sign`, `schnorrsig_verify` and `hardened_nonce_function`.
- Ideally, the new `aux_rand32` argument for `sign` would be const, but didn't find a solution I was happy with.
- Support for variable length message signing and verification supports the [suggested BIP amendment](https://github.com/sipa/bips/issues/207#issuecomment-673681901) for such messages.
- ~~`sign_custom` with its opaque config object allows adding more arguments later without having to change the API again. Perhaps there are other sensible customization options, but I'm thinking of [sign-to-contract/covert-channel](https://github.com/bitcoin-core/secp256k1/pull/590) in particular. It would require adding the fields `unsigned char *s2c_data32` and `secp256k1_s2c_opening *s2c_opening` to the config struct. The former is the data to commit to and the latter is written to by `sign_custom`.~~ (EDIT: see below)
In `test_exhaustive_sign`, if `secp256k1_ecdsa_sign` fails, the signature which is then loaded by `secp256k1_ecdsa_signature_load` is garbage. Exit early with an error when this occurs.
By the way, I am wondering whether attribute `SECP256K1_WARN_UNUSED_RESULT` should be added to function `secp256k1_ecdsa_sign`: as (according to the documentation of this function) the nonce generation function may fail, it seems to be a good idea to force callers to check the value returned by this function. What do you think about this?
Nicolas Iooss [Mon, 28 Jun 2021 13:44:19 +0000 (15:44 +0200)]
tests_exhaustive: check the result of secp256k1_ecdsa_sign
If `secp256k1_ecdsa_sign` fails, the signature which is then loaded by
`secp256k1_ecdsa_signature_load` is garbage. Exit early with an error
when this occurs.
Tim Ruffing [Thu, 13 May 2021 15:06:16 +0000 (17:06 +0200)]
build: Use own variable SECP_CFLAGS instead of touching user CFLAGS
Fixes one of the items in #923, namely the warnings of the form
'_putenv' redeclared without dllimport attribute:
previous dllimport ignored [-Wattributes]
This also cleans up the way we add CFLAGS, in particular flags enabling
warnings. Now we perform some more fine-grained checking for flag
support, which is not strictly necessary but the changes also help to
document autoconf.ac.
The two sides of the condition are the same function. This seems to be
an error, as there also exists a non-var function, named
`secp256k1_scalar_inverse`.
Make `test_inverse_scalar` use this other function when `var` is false.
This issue was found using clang's static analyzer, which reported a
"Logic error: Identical expressions in conditional expression" (with
checker `alpha.core.IdenticalExpr`).
Jonas Nick [Fri, 15 Jan 2021 21:19:34 +0000 (21:19 +0000)]
schnorrsig: allow signing and verification of variable length msgs
Varlen message support for the default sign function comes from recommending
tagged_sha256. sign_custom on the other hand gets the ability to directly sign
message of any length. This also implies signing and verification support for
the empty message (NULL) with msglen 0.
Tests for variable lengths follow in a later commit.
UdjinM6 [Tue, 15 Jun 2021 16:33:57 +0000 (19:33 +0300)]
configure: replace AC_PATH_PROG to AC_CHECK_PROG
Bitcoin Core's `configure` script uses `AC_CHECK_PROG` to find brew in the `PATH` [1]. If found, this macro will set `BREW=brew`. When building with dependencies however the `BREW` variable is set to `no` on macOS via `depends/<host_prefix>/share/config.site` [2] and this overrides `AC_CHECK_PROG` results [3]. Ideally, secp256k1's `configure` script should follow the same logic but this is not what happens because secp256k1's `configure` uses `AC_PATH_PROG` instead which respects preset variable values (in this case for variable `BREW`) only if they are a valid path (i.e., they match `[\\/*] | ?:[\\/]*` [4]), and `no` is not a path.
This commit changes `AC_PATH_PROG` to `AC_CHECK_PROG` to be consistent with Core's `AC_CHECK_PROG`. Both of these macros are supposed to find executables in the `PATH` but the difference is that former is supposed to return the full path whereas the latter is supposed to find only the program. As a result, the latter will accept even non-paths `no` as an override. Not knowing the full path is not an issue for the `configure` script because it will only execute `BREW` immediately afterwards, which works fine without the full path. (In particular, `PATH` cannot have changed in between [5].)
I was trying to determine the impact of ecmult_gen in schnorrsig signing and noticed that there is no way to bench this right now. The new benchmarks look like this:
```
$ ./bench_ecmult
ecmult_gen: min 20.9us / avg 21.2us / max 21.7us
ecmult_const: min 63.9us / avg 64.3us / max 64.8us
ecmult 1: min 49.4us / avg 49.7us / max 50.3us
ecmult 1g: min 39.8us / avg 40.0us / max 40.3us
ecmult 2g: min 27.2us / avg 27.3us / max 27.8us
ecmult_multi 1g: min 39.8us / avg 40.0us / max 40.2us
ecmult_multi 2g: min 27.2us / avg 27.4us / max 27.7us
ecmult_multi 3g: min 22.8us / avg 22.9us / max 23.1us
ecmult_multi 4g: min 20.6us / avg 20.8us / max 21.1us
ecmult_multi 5g: min 19.3us / avg 19.5us / max 19.7us
```
(Turns out ecmult_gen is 37% of the 55.8us that schnorrsig sign takes)
Tim Ruffing [Wed, 12 May 2021 09:49:36 +0000 (11:49 +0200)]
Clean up git tree
This removes the ununsed `obj` directory. It also suggests in the README
to create the "coverage" files in a separate directory and adds the
coverage files to .gitignore.
The same file says that the illegal callback will only triger for violations
explicitly mentioned, which is not true without this commit because we often
don't mention that an argument is not allowed to be NULL.
This line is extracted from #783 in the hope that it gets merged faster because other PRs depend on it.
Tim Ruffing [Thu, 6 May 2021 07:38:18 +0000 (09:38 +0200)]
Merge #937: Have ge_set_gej_var, gej_double_var and ge_set_all_gej_var initialize all fields of their outputs.
14c9739a1fb485bb56dbe3447132a37bcbef4e22 tests: Improve secp256k1_ge_set_all_gej_var for some infinity inputs (Tim Ruffing) 4a19668c37bc77d0165f4a1c0e626e321e9c4a09 tests: Test secp256k1_ge_set_all_gej_var for all infinity inputs (Tim Ruffing) 45b6468d7e3ed9849ed474c71e9a9479de1a77db Have secp256k1_ge_set_all_gej_var initialize all fields. Previous behaviour would not initialize r->y values in the case where infinity is passed in. Furthermore, the previous behaviour wouldn't initialize anything in the case where all inputs were infinity. (Russell O'Connor) 31c0f6de413e521731ad0e63424431b3dd49cec8 Have secp256k1_gej_double_var initialize all fields. Previous behaviour would not initialize r->x and r->y values in the case where infinity is passed in. (Russell O'Connor) dd6c3de322740a3054cf6a1994a38dc8f201b473 Have secp256k1_ge_set_gej_var initialize all fields. Previous behaviour would not initialize r->x and r->y values in the case where infinity is passed in. (Russell O'Connor)
Pull request description:
Previous behaviour would not initialize `r->x` and `r->y` values in the case where infinity is passed in.
Referencing #924 , this PR splits the two issues brought on to a smaller to digest change. What this does is removes the prefix "include/" when referencing the local library header files.
Rationale besides styling and consistency across other files in the repo, it makes it easier for outside builds to properly locate the headers.
A live example seen here when attempting to build this library within bitcoin repo:
```sh
[ 14%] Building CXX object leveldb/CMakeFiles/leveldb.dir/util/bloom.cc.o
/tmp/bitcoin/src/secp256k1/src/secp256k1.c:7:10: fatal error: include/secp256k1.h: No such file or directory
7 | #include "include/secp256k1.h"
| ^~~~~~~~~~~~~~~~~~~~~
compilation terminated.
make[2]: *** [secp256k1/CMakeFiles/Secp256k1.dir/build.make:76: secp256k1/CMakeFiles/Secp256k1.dir/src/secp256k1.c.o] Error 1
make[1]: *** [CMakeFiles/Makefile2:537: secp256k1/CMakeFiles/Secp256k1.dir/all] Error 2
make[1]: *** Waiting for unfinished jobs....
Have secp256k1_ge_set_all_gej_var initialize all fields.
Previous behaviour would not initialize r->y values in the case where infinity is passed in.
Furthermore, the previous behaviour wouldn't initialize anything in the case where all inputs were infinity.
Have secp256k1_gej_double_var initialize all fields.
Previous behaviour would not initialize r->x and r->y values in the case where infinity is passed in.
Have secp256k1_ge_set_gej_var initialize all fields.
Previous behaviour would not initialize r->x and r->y values in the case where infinity is passed in.
ACKs for top commit:
gmaxwell:
ACK c8483520c9077905a1dc8b9adb88b6ea2a3bd9ef looks good and works here. Undefign is kinda yuck, but it is already doing it and it's cleaner than the obvious alternatives.
sipa:
utACK c8483520c9077905a1dc8b9adb88b6ea2a3bd9ef. I verified that building still works on ARM64, but without asm of course.
Jonas Nick [Wed, 28 Apr 2021 16:57:49 +0000 (16:57 +0000)]
secp256k1.h: clarify that by default arguments must be != NULL
The same file says that the illegal callback will only triger for violations
explicitly mentioned, which is not true without this commit because we often
don't mention that an argument is not allowed to be NULL.
This updates the divsteps-based modular inverse code to use the modified version which starts with delta=1/2. For variable time, the delta=1 variant is still used as it appears to be faster.
See https://github.com/sipa/safegcd-bounds/tree/master/coq and https://medium.com/blockstream/a-formal-proof-of-safegcd-bounds-695e1735a348 for a proof of correctness of this variant.
TODO:
* [x] Update unit tests to include edge cases specific to this variant
I'm still running the Coq proof verification for the 590 bound in non-native mode. It's unclear how long this will take.
Tim Ruffing [Thu, 15 Apr 2021 14:17:53 +0000 (16:17 +0200)]
gen_context: Don't include basic-config.h
Before this commit, gen_context.c both included libsecp256k1-config.h
and basic-config.h: The former only to obtain ECMULT_GEN_PREC_BITS
and the latter to obtain a basic working configuration to be able to
use the library.
This was inelegant and confusing: It meant that basic-config.h needs
to #undef all the macros defined in libsecp256k1-config.h. Moreover,
it meant that basic-config.h cannot define ECMULT_GEN_PREC_BITS,
essentially making this file specific for use in gen_context.c.
After this commit, gen_context.c include only libsecp256k1-config.h.
basic-config.h is not necessary anymore for the modules used in
gen_context.c because 79f1f7a made the preprocessor detect all the
relevant config options.
On the way, we remove an unused #define in basic-config.h.
Pieter Wuille [Fri, 1 Jan 2021 19:15:10 +0000 (11:15 -0800)]
Use modified divsteps with initial delta=1/2 for constant-time
Instead of using eta=-delta, use zeta=-(delta+1/2) to represent
delta. This variant only needs at most 590 iterations for 256-bit
inputs rather than 724 (by convex hull bounds analysis).
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.
projects / secp256k1.git / log