Tim Ruffing [Tue, 21 Jul 2020 12:05:56 +0000 (14:05 +0200)]
Use preprocessor macros instead of autoconf to detect endianness
This does not fix any particular issue but it's preferable to not
rely on autoconf. This avoids endianness mess for users on BE hosts
if they use their build without autoconf.
The macros are carefully written to err on the side of the caution,
e.g., we #error if the user manually configures a different endianness
than what we detect.
fanquake [Mon, 29 Jun 2020 05:17:24 +0000 (13:17 +0800)]
remove dead store in ecdsa_signature_parse_der_lax
This change was made in bitcoin/bitcoin without upstreaming. So this is
a followup to the comment here:
https://github.com/bitcoin/bitcoin/pull/19228#issuecomment-641795558.
See also: https://github.com/bitcoin/bitcoin/pull/11073.
Hi,
The recovery module was overlooked in #708 and #710, so this adds it to the `valgrind_ctime_test` and replaces the secret dependent branching with the cmovs,
I created a new function `secp256k1_ecdsa_sign_inner` (feel free to bikeshed) which does the logic both for ecdsa_sign and for ecdsa_sign_recoverable, such that next time when things get changed/improved in ecdsa it will affect the recoverable signing too.
This should fix #753.
Used @peterdettman's solution here for the `ECMULT_CONST_TABLE_GET_GE` https://github.com/bitcoin-core/secp256k1/issues/753#issuecomment-631316091
and in ecdsa_sign I initialize `s` and `r` to a zero scalar.
The second commit adds a valgrind check to the cmovs that could've caught this (in ecdsa_sign, not in ecmult_const because there's a scalar clear there under `VERIFY_SETUP`)
This PR unifies handling of invalid secret keys by introducing a new function `scalar_set_b32_secret` which returns false if the b32 overflows or is 0. By using this in `privkey_{negate, tweak_add, tweak_mul}` these function will now return 0 if the secret key is invalid which matches the behavior of `ecdsa_sign` and `pubkey_create`.
Instead of deciding whether to zeroize the secret key on failure, I only added documentation for now that the value is undefined on failure.
Tim Ruffing [Tue, 31 Mar 2020 12:28:48 +0000 (14:28 +0200)]
Revert "ecdsa_impl: replace scalar if-checks with VERIFY_CHECKs in ecdsa_sig_sign"
This reverts commit 25e3cfbf9b52d2f5afa543f967a73aa8850d2038. The reverted
commit was probably based on the assumption that this is about the touched
checks cover the secret nonce k instead of r, which is the x-coord of the public
nonce. A signature with a zero r is invalid by the spec, so we should return 0
to make the caller retry with a different nonce. Overflow is not an issue.
Tim Ruffing [Wed, 25 Mar 2020 15:04:49 +0000 (16:04 +0100)]
Suppress a harmless variable-time optimization by clang in memczero
This has been not been caught by the new constant-time tests because
valgrind currently gives us a zero exit code even if finds errors, see
https://github.com/bitcoin-core/secp256k1/pull/723#discussion_r388246806 .
This commit also simplifies the arithmetic in memczero.
Note that the timing leak here was the bit whether a secret key was
out of range. This leak is harmless and not exploitable. It is just
our overcautious practice to prefer constant-time code even here.
Right now, it's not easy to reduce the optimization level with `CFLAGS` because `configure` overwrites any optimization flag with `-O3`. The [automake documentation](https://www.gnu.org/software/automake/manual/html_node/Flag-Variables-Ordering.html) states that:
> The reason ‘$(CPPFLAGS)’ appears after ‘$(AM_CPPFLAGS)’ or ‘$(mumble_CPPFLAGS)’ in the compile command is that users should always have the last say.
and also that it's incorrect to redefine CFLAGS in the first place
> You should never redefine a user variable such as CPPFLAGS in Makefile.am. [...] You should not add options to these user variables within configure either, for the same reason
With this PR `CFLAGS` is still redefined, but user-provided flags appear after the default `CFLAGS` which means that they override the default flags (at least in clang and gcc). Otherwise, the default configuration is not changed. This also means that if CFLAGS are defined by the user, then -g is not added (which does not seem to make much sense). In order to keep the `-O3` despite the reordering we need to explicitly tell autoconf to not append `-O2` by setting the default to `-g` with `: ${CFLAGS="-g"}` as per [the manual](https://www.gnu.org/savannah-checkouts/gnu/autoconf/manual/autoconf-2.69/autoconf.html#C-Compiler) (EDIT: link fix).
Valgrind does bit-level tracking of the "uninitialized" status of memory,
property tracks memory which is tainted by any uninitialized memory, and
warns if any branch or array access depends on an uninitialized bit.
That is exactly the verification we need on secret data to test for
constant-time behaviour. All we need to do is tell valgrind our
secret key is actually uninitialized memory.
This adds a valgrind_ctime_test which is compiled if valgrind is installed:
Run it with libtool --mode=execute:
$ libtool --mode=execute valgrind ./valgrind_ctime_test
Gregory Maxwell [Wed, 8 Jan 2020 11:56:15 +0000 (11:56 +0000)]
Constant-time behaviour test using valgrind memtest.
Valgrind does bit-level tracking of the "uninitialized" status of memory,
property tracks memory which is tainted by any uninitialized memory, and
warns if any branch or array access depends on an uninitialized bit.
That is exactly the verification we need on secret data to test for
constant-time behaviour. All we need to do is tell valgrind our
secret key is actually uninitialized memory.
This adds a valgrind_ctime_test which is compiled if valgrind is installed:
Run it with libtool --mode=execute:
$ libtool --mode=execute valgrind ./valgrind_ctime_test
There were several places where the code was non-constant time
for invalid secret inputs. These are harmless under sane use
but get in the way of automatic const-time validation.
(Nonce overflow in signing is not addressed, nor is s==0 in signing)
Gregory Maxwell [Sat, 11 Jan 2020 13:31:50 +0000 (13:31 +0000)]
Adds a declassify operation to aid constant-time analysis.
ECDSA signing has a retry loop for the exceptionally unlikely case
that S==0. S is not a secret at this point and this case is so
rare that it will never be observed but branching on it will trip
up tools analysing if the code is constant time with respect to
secrets.
Derandomized ECDSA can also loop on k being zero or overflowing,
and while k is a secret these cases are too rare (1:2^255) to
ever observe and are also of no concern.
This adds a function for marking memory as no-longer-secret and
sets it up for use with the valgrind memcheck constant-time
test.
Gregory Maxwell [Sat, 11 Jan 2020 01:01:05 +0000 (01:01 +0000)]
Eliminate harmless non-constant time operations on secret data.
There were several places where the code was non-constant time
for invalid secret inputs. These are harmless under sane use
but get in the way of automatic const-time validation.
(Nonce overflow in signing is not addressed, nor is s==0 in
signing)
This was discussed in #508. The main reasons are that the existing Java Native Interface (JNI) bindings would need way more work to remain useful to Java developers but the maintainers and regular contributors of libsecp are not very familiar with Java (and evidently are motivated enough to improve the situation). We don't know who relies on these bindings with the exception of ACINQ who have their own fork at https://github.com/ACINQ/secp256k1/tree/jni-embed/src/java (@sstone). Bitcoinj can optionally use the libsecp bindings.
Ideally, there would be a separate repository owned by Java developers with just the bindings. Until this exists, Java developers relying on libsecp can use ACINQs fork or an older commit of libsecp.
ECMULT_CONST_TABLE_GET_GE was branching on its secret input.
Also makes secp256k1_gej_double_var implemented as a wrapper
on secp256k1_gej_double_nonzero instead of the other way
around. This wasn't a constant time bug but it was fragile
and could easily become one in the future if the double_var
algorithm is changed.
Gregory Maxwell [Wed, 8 Jan 2020 14:58:28 +0000 (14:58 +0000)]
Remove secret-dependant non-constant time operation in ecmult_const.
ECMULT_CONST_TABLE_GET_GE was branching on its secret input.
Also makes secp256k1_gej_double_var implemented as a wrapper
on secp256k1_gej_double_nonzero instead of the other way
around. This wasn't a constant time bug but it was fragile
and could easily become one in the future if the double_var
algorithm is changed.
* Update feature list
* Be more positive about the state and quality of the library
* Mention ECDSA key operations explicitly in short library description
* Say "secret key" instead of "private key"
cc @gmaxwell who suggested a similar wording for the disclaimer.
Tim Ruffing [Fri, 20 Dec 2019 16:25:14 +0000 (17:25 +0100)]
Overhaul README.md
* Update feature list
* Be more positive about the state and quality of the library
* Mention ECDSA key operations explicitly in short library description
* Say "secret key" instead of "private key
* Define "experimental"
ACKs for top commit:
real-or-random:
ACK bde2a32286c697dd1056aa3eb1ea2a5353f0bede I've read the code in detail and I've tested it. I haven't explicitly tested the formatting function with known/hardcoded inputs.
WIP because the [email protected] email address doesn't exist yet. But it seems like the right place for vulnerability reports. [email protected] would have the downside that it perhaps reaches more people than necessary. Ideally secp256k1-security would just forward to the three maintainers listed in SECURITY.md. @sipa @apoelstra is it okay to put you there? Fwiw I'm opting out for now because three people should be enough.
@sipa do you know who to talk to about adding [email protected] and the specifics about how it would work?
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
projects / secp256k1.git / log