This PR does two things:
* It removes the ability to select the 5x52 field with a 8x32 scalar, or the 10x26 field with a 4x64 scalar. It's both 128-bit wide versions, or neither.
* The choice is made automatically by the C code, unless overridden by a USE_FORCE_WIDEMUL_INT{64,128} define (which is available through `configure` with a hidden option --with-test-override-wide-multiplication={auto,int64,int128}).
This reduces the reliance on autoconf for this performance-critical configuration option, and also reduces the number of different combinations to test.
This removes one theoretically useful combination: if you had x86_64 asm but no __int128 support in your compiler, it was possible to use the 64-bit field before but the 32-bit scalar. I think this doesn't matter as all compilers/systems that support (our) x86_64 asm also support __int128. Furthermore, #767 will break this.
As an unexpected side effect, this also means the `gen_context` static precomputation tool will now use __int128 based implementations when available (which required an addition to the 5x52 field; see first commit).
Pieter Wuille [Sun, 9 Aug 2020 17:58:40 +0000 (10:58 -0700)]
Autodetect __int128 availability on the C side
Instead of supporting configuration of the field and scalar size independently,
both are now controlled by the availability of a 64x64->128 bit multiplication
(currently only through __int128). This is autodetected from the C code through
__SIZEOF_INT128__, but can be overridden using configure's
--with-test-override-wide-multiply, or by defining
USE_FORCE_WIDEMUL_{INT64,INT128} manually.
Tim Ruffing [Wed, 29 Jul 2020 06:50:42 +0000 (08:50 +0200)]
travis: Fix argument quoting for ./configure
When $USE_HOST or $EXTRAFLAGS are empty, we pass (due to quoting) an
empty string as a parameter to ./configure, which then believes we want
to use a deprecated syntax for specifing a host or a target and yells at us:
> configure: WARNING: you should use --build, --host, --target
The fixes are:
- $EXTRAFLAGS could contain multiple flags and should not be quoted at all.
- We can get rid of $USE_HOST by specifying --host="$HOST" directly.
There currently is a single branch in the `ecmul_const` function that is not being exercised by the tests. This branch is unreachable and therefore I'm suggesting to remove it.
For your convenience the paper the wnaf algorithm can be found [here (The Width-w NAF Method Provides Small Memory and Fast Elliptic Scalar Multiplications Secure against Side Channel Attacks)](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.563.1267&rep=rep1&type=pdf). Similarly, unless I'm missing something important, I don't see how their algorithm needs to consider `sign(u[i-1])` unless `d` can be negative - which doesn't make much sense to me either.
ACKs for top commit:
real-or-random:
ACK 37dba329c6cb0f7a4228a11dc26aa3a342a3a5d0 I verified the correctness of the change and claimed invariant by manual inspection. I tested the code, both with 32bit and 64bit scalars.
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.
Jonas Nick [Fri, 17 Apr 2020 18:05:50 +0000 (18:05 +0000)]
Fix test_constant_wnaf for -1 and add a test for it.
Before, test_constant_wnaf used scalar_cadd_bit to correct for the skew. But
this function does not correctly deal with overflows which is why num = -1
couldn't be tested.
This commit also adds tests for 0, 1/2 and 1/2-1 as they are corner cases
in constant_wnaf.
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?
projects / secp256k1.git / log