Tim Ruffing [Mon, 25 Nov 2019 14:03:15 +0000 (15:03 +0100)]
Merge #685: Fix issue where travis does not show the ./tests seed…
a0771d1 Explicitly disable buffering for stderr in tests (Jonas Nick) fb424fb Make travis show the ./tests seed by removing stdout buffering and always cat tests.log after a travis run. (Jonas Nick)
Pull request description:
…by removing stdout buffering and always cat tests.log after a travis run. Fixes #645.
I noticed that according to the [doc](https://www.gnu.org/software/automake/manual/html_node/Parallel-Test-Harness.html) tests.log should contain stdout as well as stderr. But it doesn't because stdout isn't flushed. I removed buffering completely to avoid having to call `fflush` twice.
Travis is instructed to always show the seed which seems helpful with `after_script` by `cat`ing `./tests.log`. In case the tests fail it looks like https://travis-ci.org/jonasnick/secp256k1/jobs/606446234.
As discussed in https://github.com/bitcoin-core/secp256k1/pull/687
This adds valgrind check to the repo.
It doesn't run on recovery+ecdh because of the time.
No openssl because of uninitialized mem.
I debated between with and without ASM, but decided with ASM because it might be more fragile(?).
I wasn't sure if I should pass `-DVALGRIND` via `CFLAGS` or `CPPFLAGS`, it seems like because this is only C then there shouldn't even be `CPPFLAGS` but looks like we use `CPPFLAGS` in other places for the preprocessor definitions.
If people are worried about the time it takes we can mark it as `allow_failure` although I don't think it's a problem here because there's only a handful of PRs and they're usually open for weeks.
As asked https://github.com/bitcoin-core/secp256k1/pull/667#issuecomment-546885951 this is the parts of #667 that don't require an assembly memory fence.
I splitted them to 2 commits, one with obvious easy ones. and another that changes the logic a bit to achieve this (See https://github.com/bitcoin-core/secp256k1/pull/667#discussion_r337248398 )
We don't want floating types for various reasons, e.g.,
- Their representation and often their behavior is implementation-defined.
- Many targets don't support them.
Tim Ruffing [Fri, 1 Nov 2019 09:39:41 +0000 (10:39 +0100)]
Make no-float policy explicit
We don't want floating types for various reasons, e.g.,
- Their representation and often their behavior is implementation-defined.
- Many targets don't support them.
Tim Ruffing [Mon, 28 Oct 2019 10:53:46 +0000 (11:53 +0100)]
Merge #647: Increase robustness against UB in secp256k1_scalar_cadd_bit
0d82732 Improve VERIFY_CHECK of overflow in secp256k1_scalar_cadd_bit. This added check ensures that any curve order overflow doesn't go undetected due a uint32_t overflow. (Russell O'Connor) 8fe63e5 Increase robustness against UB. Thanks to elichai2 who noted that the literal '1' is a signed integer, and that shifting a signed 32-bit integer by 31 bits causes an overflow and yields undefined behaviour. While 'scalar_low_impl''s 'secp256k1_scalar_cadd_bit' is only used for testing purposes and currently the 'bit' parameter is only 0 or 1, it is better to avoid undefined behaviour in case the used domain of 'secp256k1_scalar_cadd_bit' expands. (roconnor-blockstream)
Pull request description:
Avoid possible, but unlikely undefined behaviour in `scalar_low_impl`'s `secp256k1_scalar_cadd_bit`.
Thanks to elichai2 who noted that the literal `1` is a signed integer, and that shifting a signed 32-bit integer by 31 bits causes an overflow and yields undefined behaviour.
Using the unsigned literal `1u` addresses the issue.
This pull request gives an option to reduce the precomputed table size for the signing context (`ctx`) by setting `#define ECMULT_GEN_PREC_BITS [N_BITS]`.
Motivation: Per #251 and #254, the static table can be reduced to 64kB. However, this is still too big for some of my embedded applications. Setting `#define ECMULT_GEN_PREC_BITS 2` produces a 32kB table at a tradeoff of about 75% of the signing speed. Not defining this value will default to the existing implementation of 4 bits. Statistics:
```
ECMULT_GEN_PREC_BITS = 1
Precomputed table size: 32kB
./bench_sign
ecdsa_sign: min 195us / avg 200us / max 212us
ECMULT_GEN_PREC_BITS = 2
Precomputed table size: 32kB
./bench_sign
ecdsa_sign: min 119us / avg 126us / max 134us
ECMULT_GEN_PREC_BITS = 4 (default)
Precomputed table size: 64kB
./bench_sign
ecdsa_sign: min 83.5us / avg 89.6us / max 95.3us
ECMULT_GEN_PREC_BITS = 8
Precomputed table size: 512kB
./bench_sign
ecdsa_sign: min 96.4us / avg 99.4us / max 104us
```
Only values of 2 and 4 make sense. 8 bits causes a larger table size with no increase in speed. 1 bit runs, actually, but does not reduce table size and is slower than 2 bits.
djb [Sun, 18 Oct 2015 08:35:16 +0000 (10:35 +0200)]
variable signing precompute table
make ECMULT_GEN_PREC_BITS configurable
ecmult_static_context.h: add compile time config assertion (#3) - Prevents accidentally using a file which was generated with a
different configuration.
README: mention valgrind issue
With --with-ecmult-gen-precision=8, valgrind needs a max stack size
adjustment to not run into a stack switching heuristic:
http://valgrind.org/docs/manual/manual-core.html
> -max-stackframe= [default: 2000000]
> The maximum size of a stack frame. If the stack pointer moves by more than this amount then Valgrind will assume that the program is switching to a different stack.
You may need to use this option if your program has large stack-allocated arrays.
basic-config: undef ECMULT_WINDOW_SIZE before (re-)defining it
Source: https://github.com/bitcoin-core/secp256k1/blob/master/src/modules/recovery/tests_impl.h#L247
(it passes only when the sig is parsed with recid 1)
Improve VERIFY_CHECK of overflow in secp256k1_scalar_cadd_bit.
This added check ensures that any curve order overflow doesn't go undetected due a uint32_t overflow.
Pieter Wuille [Tue, 6 Aug 2019 22:28:48 +0000 (15:28 -0700)]
Merge #644: Avoid optimizing out a verify_check
94ae7cb Moved a dereference so the null check will be before the dereferencing (Elichai Turkel)
Pull request description:
Before that even on debug the compiler could've assumed `a` isn't null and optimized `VERIFY_CHECK(a != NULL);` out.
This put the dereference after the check
Resolves #643
Increase robustness against UB.
Thanks to elichai2 who noted that the literal '1' is a signed integer, and that shifting a signed 32-bit integer by 31 bits causes an overflow and yields undefined behaviour.
While 'scalar_low_impl''s 'secp256k1_scalar_cadd_bit' is only used for testing purposes and currently the 'bit' parameter is only 0 or 1, it is better to avoid undefined behaviour in case the used domain of 'secp256k1_scalar_cadd_bit' expands.
Gregory Maxwell [Wed, 29 May 2019 21:46:31 +0000 (21:46 +0000)]
Merge #629: Avoid calling _is_zero when _set_b32 fails.
cd473e0 Avoid calling secp256k1_*_is_zero when secp256k1_*_set_b32 fails. (Gregory Maxwell)
Pull request description:
Most of the codebase correctly used short-cutting to avoid calling
_is_zero on possibly incompletely initialized elements, but a few
places were missed.
It's important that the tests are also run without -DVERIFY due to
the possibility that side-effects of a VERIFY_CHECK fix a bug that
would otherwise be detected.
Use of the verify_check macro in tests isn't sufficient.
Gregory Maxwell [Wed, 29 May 2019 10:35:10 +0000 (10:35 +0000)]
Merge #578: Avoid implementation-defined and undefined behavior when dealing with sizes
14c7dbd Simplify control flow in DER parsing (Tim Ruffing) ec8f20b Avoid out-of-bound pointers and integer overflows in size comparisons (Tim Ruffing) 01ee1b3 Parse DER-enconded length into a size_t instead of an int (Tim Ruffing) 3cb057f Fix possible integer overflow in DER parsing (Tim Ruffing)
Pull request description:
This is a result of auditing the code for overflow issues at random places. None of this is critical but I think all of it should be fixed.
I know this touches "red" code. I double-checked and triple-checked this but I can understand if some of the changes are not desirable because they change well-tested code.
Gregory Maxwell [Mon, 27 May 2019 07:30:33 +0000 (07:30 +0000)]
Merge #595: Allow to use external default callbacks
e49f799 Add missing #(un)defines to base-config.h (Tim Ruffing) 77defd2 Add secp256k1_ prefix to default callback functions (Tim Ruffing) 908bdce Include stdio.h and stdlib.h explicitly in secp256k1.c (Tim Ruffing) 5db782e Allow usage of external default callbacks (Tim Ruffing) 6095a86 Replace CHECKs for no_precomp ctx by ARG_CHECKs without a return (Tim Ruffing)
Pull request description:
This is intended for environments without implementations for `abort()`, `fprintf()`, and `stderr`. e.g., embedded systems. Those can provide their own implementations of `default_illegal_callback_fn` and `default_error_callback_fn` at compile time.
If you want to use your own default callback, things will be somewhat inconsistent unfortunately: We cannot make the callback data `extern` too, because then the initialization lists for `default_illegal_callback` won't contain only constants. (`const` variables are not compile-time constants). So you cannot take callback data in your own default callback function.
As a more drastic/breaking alternative I suggest to remove the callback data entirely. I don't think it's a big loss and I would be surprised if anyone uses it. Additionally, we could even remove the possibility to set the callback function at runtime after this PR. This will simplify things a lot, and again I don't think it's a big loss.
Note that `abort()`, `fprintf()`, and `stderr` are also used in `CHECK`, which is still used in production code if we rely on gmp for scalar and field inversions (e.g., https://github.com/bitcoin-core/secp256k1/blob/master/src/scalar_impl.h#L240). This is not an issue for embedded system which probably don't want to use gmp anyway, but it is probably an issue for the reasons explained in https://github.com/bitcoin-core/secp256k1/pull/566#issuecomment-469111901.
Gregory Maxwell [Sun, 26 May 2019 10:22:38 +0000 (10:22 +0000)]
Avoid calling secp256k1_*_is_zero when secp256k1_*_set_b32 fails.
Most of the codebase correctly used short-cutting to avoid calling
_is_zero on possibly incompletely initialized elements, but a few
places were missed.
Gregory Maxwell [Sun, 26 May 2019 07:37:54 +0000 (07:37 +0000)]
Merge #600: scratch space: use single allocation
98836b1 scratch: replace frames with "checkpoint" system (Andrew Poelstra) 7623cf2 scratch: save a couple bytes of unnecessarily-allocated memory (Andrew Poelstra) a7a164f scratch: rename `max_size` to `size`, document that extra will actually be allocated (Andrew Poelstra) 5a4bc0b scratch: unify allocations (Andrew Poelstra) c2b028a scratch space: thread `error_callback` into all scratch space functions (Andrew Poelstra) 0be1a4a scratch: add magic bytes to beginning of structure (Andrew Poelstra) 92a48a7 scratch space: use single allocation (Andrew Poelstra)
Gregory Maxwell [Sat, 25 May 2019 22:34:47 +0000 (22:34 +0000)]
Merge #592: Use trivial algorithm in ecmult_multi if scratch space is small
9ab96f7 Use trivial algorithm in ecmult_multi if scratch space is small (Jonas Nick)
Pull request description:
`ecmult_multi` already selects the trivial algorithm if the scratch space is NULL. With this PR the trivial algorithm is also selected if the scratch space is too small to use pippenger or strauss instead of returning 0. That makes it more easier to avoid consensus relevant inconsistencies just because scratch space construction was messed up.
ACKs for commit 9ab96f:
real-or-random:
utACK 9ab96f7
It's important that the tests are also run without -DVERIFY due to
the possibility that side-effects of a VERIFY_CHECK fix a bug that
would otherwise be detected.
Use of the verify_check macro in tests isn't sufficient.
Gregory Maxwell [Sat, 25 May 2019 21:16:07 +0000 (21:16 +0000)]
Merge #566: Enable context creation in preallocated memory
0522caa Explain caller's obligations for preallocated memory (Tim Ruffing) 238305f Move _preallocated functions to separate header (Tim Ruffing) 695feb6 Export _preallocated functions (Tim Ruffing) 814cc78 Add tests for contexts in preallocated memory (Tim Ruffing) ba12dd0 Check arguments of _preallocated functions (Tim Ruffing) 5feadde Support cloning a context into preallocated memory (Tim Ruffing) c4fd5da Switch to a single malloc call (Tim Ruffing) ef020de Add size constants for preallocated memory (Tim Ruffing) 1bf7c05 Prepare for manual memory management in preallocated memory (Tim Ruffing)
Pull request description:
@apoelstra
This builds on #557.
Manually managing memory is always a pain in the ass in some way. I tried to keep the pain manageable. I'm open to suggestions to make this less ugly or error-prone.
Gregory Maxwell [Sat, 25 May 2019 10:15:59 +0000 (10:15 +0000)]
Merge #596: Make WINDOW_G configurable
a61a93f Clean up ./configure help strings (Tim Ruffing) 2842dc5 Make WINDOW_G configurable (Tim Ruffing)
Pull request description:
This makes WINDOW_G a configurable value in the range of [2..24].
The upper limit of 24 is a defensive choice. The code is probably
correct for values up to 33 but those larger values yield in huge
tables (>= 256MiB), which are i) unlikely to be really beneficial
in practice and ii) increasingly difficult to test.
The main point of this is not to make the window size configurable (using ./configure) but rather to use an external #define for the window size, which makes it configurable for embedded system that rely on their own build system (like in #595).
Tim Ruffing [Wed, 6 Mar 2019 12:12:33 +0000 (13:12 +0100)]
Make WINDOW_G configurable
This makes WINDOW_G a configurable value in the range of [2..24].
The upper limit of 24 is a defensive choice. The code is probably
correct for values up to 27 but those larger values yield in huge
tables (>= 256MiB), which are i) unlikely to be really beneficial
in practice and ii) increasingly difficult to test.
Tim Ruffing [Wed, 7 Nov 2018 15:17:57 +0000 (16:17 +0100)]
Avoid out-of-bound pointers and integer overflows in size comparisons
This changes pointer calculations in size comparions to a form that
ensures that no out-of-bound pointers are computed, because even their
computation yields undefined behavior.
Also, this changes size comparions to a form that ensures that neither
the left-hand side nor the right-hand side can overflow.
Gregory Maxwell [Thu, 23 May 2019 00:36:27 +0000 (00:36 +0000)]
Merge #561: Respect LDFLAGS and #undef STATIC_PRECOMPUTATION if using basic config
dbed75d Undefine `STATIC_PRECOMPUTATION` if using the basic config (DesWurstes) 310111e Keep LDFLAGS if `--coverage` (DesWurstes)
Pull request description:
Update: **This is a trimmed pull request with strong rationale.**
- Adding `--coverage` shouldn't reset `LDFLAGS`, this is definitely a typo
- The basic configuration should undefine `STATIC_PRECOMPUTATION`, as generating it is not supported and it complicates #549
This fix install all the headers under include/ into
/usr/local/include. The fix solves problems that arise
when building libraries that depend on secp256k1 such
as libbitcoin-system which require all the headers
Gregory Maxwell [Wed, 22 May 2019 04:43:53 +0000 (04:43 +0000)]
Merge #533: Make sure we're not using an uninitialized variable in secp256k1_wnaf_const(...)
248f046 Make sure we're not using an uninitialized variable in secp256k1_wnaf_const(...) (practicalswift)
Pull request description:
Make sure we're not using an uninitialized variable in `secp256k1_wnaf_const(...)`:
```
In file included from src/secp256k1.c:15:0,
from src/tests.c:17:
src/ecmult_const_impl.h: In function ‘secp256k1_wnaf_const’:
src/ecmult_const_impl.h:117:20: warning: ‘u’ may be used uninitialized in this function [-Wmaybe-uninitialized]
wnaf[word] = u * global_sign;
^
```
**Note to reviewers:** Perhaps an `assert(…);` is a bit drastic. What would be a more graceful way to handle this? :-)
This fix install all the headers under include/ into
/usr/local/include. The fix solves problems that arise
when building libraries that depend on secp256k1 such
as bitcoin-system which require all the headers
Gregory Maxwell [Thu, 9 May 2019 22:23:41 +0000 (22:23 +0000)]
Merge #612: Allow field_10x26_arm.s to compile for ARMv7 architecture
d4d270a Allow field_10x26_arm.s to compile for ARMv7 architecture (Roman Zeyde)
Pull request description:
It would allow using optimized field operations on the TREZOR device, which is using ARMv7 Cortex-M4.
Following https://github.com/trezor/trezor-core/pull/500 and part of https://github.com/trezor/trezor-firmware/issues/66.
projects / secp256k1.git / log