Skip to content

Commit 9d09322

Browse files
sipasipa
committed
Squashed 'src/secp256k1/' changes from 50cc6ab..1897b8e
1897b8e Merge pull request #229 efc571c Add simple testcases for signing with rfc6979 extra entropy. 1573a10 Add ability to pass extra entropy to rfc6979 3087bc4 Merge pull request #228 d9b9f11 Merge pull request #218 0065a8f Eliminate multiple-returns from secp256k1.c. 354ffa3 Make secp256k1_ec_pubkey_create reject oversized secrets. 27bc131 Silence some warnings from pedantic static analysis tools, improve compatibility with C++. 3b7ea63 Merge pull request #221 f789c5b Merge pull request #215 4bc273b Merge pull request #222 137a8ec Merge pull request #216 7c3771d Disable overlength-strings warnings. 8956111 use 128-bit hex seed 02efd06 Use RFC6979 for test PRNGs ae55e85 Use faster byteswapping and avoid alignment-increasing casts. 443cd4b Get rid of hex format and some binary conversions 0bada0e Merge #214: Improve signing API documentation & specification 8030d7c Improve signing API documentation & specification 7b2fc1c Merge #213: Removed gotos, which are hard to trace and maintain. 11690d3 Removed gotos, which are hard to trace and maintain. 122a1ec Merge pull request #205 035406d Merge pull request #206 2d4cd53 Merge pull request #161 34b898d Additional comments for the testing PRNG and a seeding fix. 6efd6e7 Some comments explaining some of the constants in the code. ffccfd2 x86_64 assembly optimization for scalar_4x64 67cbdf0 Merge pull request #207 039723d Benchmarks for all internal operations 6cc8425 Include a comment on secp256k1_ecdsa_sign explaining low-s. f88343f Merge pull request #203 d61e899 Add group operation counts 2473f17 Merge pull request #202 b5bbce6 Some readme updates, e.g. removal of the GMP field. f0d851e Merge pull request #201 a0ea884 Merge pull request #200 f735446 Convert the rest of the codebase to C89. bf2e1ac Convert tests to C89. (also fixes a use of bare "inline" in field) fc8285f Merge pull request #199 fff412e Merge pull request #197 4be8d6f Centralize the definition of uint128_t and use it uniformly. d9543c9 Switch scalar code to C89. fcc48c4 Remove the non-storage cmov 55422b6 Switch ecmult_gen to use storage types 41f8455 Use group element storage type in EC multiplications e68d720 Add group element storage type ff889f7 Field storage type 7137be8 Merge pull request #196 0768bd5 Get rid of variable-length hex string conversions e84e761 Merge pull request #195 792bcdb Covert several more files to C89. 45cdf44 Merge pull request #193 17db09e Merge pull request #194 402878a fix ifdef/ifndef 25b35c7 Convert field code to strict C89 (+ long long, +__int128) 3627437 C89 nits and dead code removal. a9f350d Merge pull request #191 4732d26 Convert the field/group/ecdsa constant initialization to static consts 19f3e76 Remove unused secp256k1_fe_inner_{start, stop} functions f1ebfe3 Convert the scalar constant initialization to static consts git-subtree-dir: src/secp256k1 git-subtree-split: 1897b8e
1 parent 7873633 commit 9d09322

38 files changed

+2525
-1465
lines changed

‎Makefile.am‎

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -49,7 +49,7 @@ libsecp256k1_la_LIBADD = $(SECP_LIBS)
4949

5050
noinst_PROGRAMS =
5151
if USE_BENCHMARK
52-
noinst_PROGRAMS += bench_verify bench_recover bench_sign bench_inv
52+
noinst_PROGRAMS += bench_verify bench_recover bench_sign bench_internal
5353
bench_verify_SOURCES = src/bench_verify.c
5454
bench_verify_LDADD = libsecp256k1.la $(SECP_LIBS)
5555
bench_verify_LDFLAGS = -static
@@ -59,10 +59,10 @@ bench_recover_LDFLAGS = -static
5959
bench_sign_SOURCES = src/bench_sign.c
6060
bench_sign_LDADD = libsecp256k1.la $(SECP_LIBS)
6161
bench_sign_LDFLAGS = -static
62-
bench_inv_SOURCES = src/bench_inv.c
63-
bench_inv_LDADD = $(SECP_LIBS)
64-
bench_inv_LDFLAGS = -static
65-
bench_inv_CPPFLAGS = $(SECP_INCLUDES)
62+
bench_internal_SOURCES = src/bench_internal.c
63+
bench_internal_LDADD = $(SECP_LIBS)
64+
bench_internal_LDFLAGS = -static
65+
bench_internal_CPPFLAGS = $(SECP_INCLUDES)
6666
endif
6767

6868
if USE_TESTS

‎README.md‎

Lines changed: 13 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -5,25 +5,29 @@ libsecp256k1
55

66
Optimized C library for EC operations on curve secp256k1.
77

8-
This library is experimental, so use at your own risk.
8+
This library is a work in progress and is being used to research best practices. Use at your own risk.
99

1010
Features:
11-
* Low-level field and group operations on secp256k1.
12-
* ECDSA signing/verification and key generation.
11+
* secp256k1 ECDSA signing/verification and key generation.
1312
* Adding/multiplying private/public keys.
1413
* Serialization/parsing of private keys, public keys, signatures.
14+
* Constant time, constant memory access signing and pubkey generation.
15+
* Derandomized DSA (via RFC6979 or with a caller provided function.)
1516
* Very efficient implementation.
1617

1718
Implementation details
1819
----------------------
1920

2021
* General
21-
* Avoid dynamic memory usage almost everywhere.
22+
* No runtime heap allocation.
23+
* Extensive testing infrastructure.
24+
* Structured to facilitate review and analysis.
25+
* Intended to be portable to any system with a C89 compiler and uint64_t support.
26+
* Expose only higher level interfaces to minimize the API surface and improve application security. ("Be difficult to use insecurely.")
2227
* Field operations
2328
* Optimized implementation of arithmetic modulo the curve's field size (2^256 - 0x1000003D1).
2429
* Using 5 52-bit limbs (including hand-optimized assembly for x86_64, by Diederik Huys).
2530
* Using 10 26-bit limbs.
26-
* Using GMP.
2731
* Field inverses and square roots using a sliding window over blocks of 1s (by Peter Dettman).
2832
* Scalar operations
2933
* Optimized implementation without data-dependent branches of arithmetic modulo the curve's order.
@@ -33,14 +37,15 @@ Implementation details
3337
* Point addition formula specifically simplified for the curve equation (y^2 = x^3 + 7).
3438
* Use addition between points in Jacobian and affine coordinates where possible.
3539
* Use a unified addition/doubling formula where necessary to avoid data-dependent branches.
40+
* Point/x comparison without a field inversion by comparison in the Jacobian coordinate space.
3641
* Point multiplication for verification (a*P + b*G).
3742
* Use wNAF notation for point multiplicands.
3843
* Use a much larger window for multiples of G, using precomputed multiples.
3944
* Use Shamir's trick to do the multiplication with the public key and the generator simultaneously.
40-
* Optionally use secp256k1's efficiently-computable endomorphism to split the multiplicands into 4 half-sized ones first.
45+
* Optionally (off by default) use secp256k1's efficiently-computable endomorphism to split the P multiplicand into 2 half-sized ones.
4146
* Point multiplication for signing
4247
* Use a precomputed table of multiples of powers of 16 multiplied with the generator, so general multiplication becomes a series of additions.
43-
* Slice the precomputed table in memory per byte, so memory access to the table becomes uniform.
48+
* Access the table with branch-free conditional moves so memory access is uniform.
4449
* No data-dependent branches
4550
* The precomputed tables add and eventually subtract points for which no known scalar (private key) is known, preventing even an attacker with control over the private key used to control the data internally.
4651

@@ -52,4 +57,5 @@ libsecp256k1 is built using autotools:
5257
$ ./autogen.sh
5358
$ ./configure
5459
$ make
60+
$ ./tests
5561
$ sudo make install # optional

‎configure.ac‎

Lines changed: 7 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -5,7 +5,7 @@ AC_CONFIG_MACRO_DIR([build-aux/m4])
55
AC_CANONICAL_HOST
66
AH_TOP([#ifndef LIBSECP256K1_CONFIG_H])
77
AH_TOP([#define LIBSECP256K1_CONFIG_H])
8-
AH_BOTTOM([#endif //LIBSECP256K1_CONFIG_H])
8+
AH_BOTTOM([#endif /*LIBSECP256K1_CONFIG_H*/])
99
AM_INIT_AUTOMAKE([foreign subdir-objects])
1010
LT_INIT
1111

@@ -22,9 +22,9 @@ if test "x$CFLAGS" = "x"; then
2222
CFLAGS="-O3 -g"
2323
fi
2424

25-
AC_PROG_CC_C99
26-
if test x"$ac_cv_prog_cc_c99" = x"no"; then
27-
AC_MSG_ERROR([c99 compiler support required])
25+
AC_PROG_CC_C89
26+
if test x"$ac_cv_prog_cc_c89" = x"no"; then
27+
AC_MSG_ERROR([c89 compiler support required])
2828
fi
2929

3030
case $host in
@@ -70,7 +70,7 @@ esac
7070

7171
CFLAGS="$CFLAGS -W"
7272

73-
warn_CFLAGS="-Wall -Wextra -Wcast-align -Wnested-externs -Wshadow -Wstrict-prototypes -Wno-unused-function"
73+
warn_CFLAGS="-std=c89 -pedantic -Wall -Wextra -Wcast-align -Wnested-externs -Wshadow -Wstrict-prototypes -Wno-unused-function -Wno-long-long -Wno-overlength-strings"
7474
saved_CFLAGS="$CFLAGS"
7575
CFLAGS="$CFLAGS $warn_CFLAGS"
7676
AC_MSG_CHECKING([if ${CC} supports ${warn_CFLAGS}])
@@ -305,6 +305,8 @@ if test x"$use_endomorphism" = x"yes"; then
305305
AC_DEFINE(USE_ENDOMORPHISM, 1, [Define this symbol to use endomorphism optimization])
306306
fi
307307

308+
AC_C_BIGENDIAN()
309+
308310
AC_MSG_NOTICE([Using assembly optimizations: $set_asm])
309311
AC_MSG_NOTICE([Using field implementation: $set_field])
310312
AC_MSG_NOTICE([Using bignum implementation: $set_bignum])

‎include/secp256k1.h‎

Lines changed: 39 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -78,7 +78,7 @@ SECP256K1_WARN_UNUSED_RESULT int secp256k1_ecdsa_verify(
7878
) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(4);
7979

8080
/** A pointer to a function to deterministically generate a nonce.
81-
* Returns: 1 if a nonce was succesfully generated. 0 will cause signing to fail.
81+
* Returns: 1 if a nonce was successfully generated. 0 will cause signing to fail.
8282
* In: msg32: the 32-byte message hash being verified (will not be NULL)
8383
* key32: pointer to a 32-byte secret key (will not be NULL)
8484
* attempt: how many iterations we have tried to find a nonce.
@@ -97,7 +97,10 @@ typedef int (*secp256k1_nonce_function_t)(
9797
const void *data
9898
);
9999

100-
/** An implementation of RFC6979 (using HMAC-SHA256) as nonce generation function. */
100+
/** An implementation of RFC6979 (using HMAC-SHA256) as nonce generation function.
101+
* If a data pointer is passed, it is assumed to be a pointer to 32 bytes of
102+
* extra entropy.
103+
*/
101104
extern const secp256k1_nonce_function_t secp256k1_nonce_function_rfc6979;
102105

103106
/** A default safe nonce generation function (currently equal to secp256k1_nonce_function_rfc6979). */
@@ -106,15 +109,43 @@ extern const secp256k1_nonce_function_t secp256k1_nonce_function_default;
106109

107110
/** Create an ECDSA signature.
108111
* Returns: 1: signature created
109-
* 0: the nonce generation function failed
112+
* 0: the nonce generation function failed, the private key was invalid, or there is not
113+
* enough space in the signature (as indicated by siglen).
110114
* In: msg32: the 32-byte message hash being signed (cannot be NULL)
111-
* seckey: pointer to a 32-byte secret key (cannot be NULL, assumed to be valid)
115+
* seckey: pointer to a 32-byte secret key (cannot be NULL)
112116
* noncefp:pointer to a nonce generation function. If NULL, secp256k1_nonce_function_default is used
113117
* ndata: pointer to arbitrary data used by the nonce generation function (can be NULL)
114118
* Out: sig: pointer to an array where the signature will be placed (cannot be NULL)
115119
* In/Out: siglen: pointer to an int with the length of sig, which will be updated
116-
* to contain the actual signature length (<=72).
120+
* to contain the actual signature length (<=72). If 0 is returned, this will be
121+
* set to zero.
117122
* Requires starting using SECP256K1_START_SIGN.
123+
*
124+
* The sig always has an s value in the lower half of the range (From 0x1
125+
* to 0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF5D576E7357A4501DDFE92F46681B20A0,
126+
* inclusive), unlike many other implementations.
127+
* With ECDSA a third-party can can forge a second distinct signature
128+
* of the same message given a single initial signature without knowing
129+
* the key by setting s to its additive inverse mod-order, 'flipping' the
130+
* sign of the random point R which is not included in the signature.
131+
* Since the forgery is of the same message this isn't universally
132+
* problematic, but in systems where message malleability or uniqueness
133+
* of signatures is important this can cause issues. This forgery can be
134+
* blocked by all verifiers forcing signers to use a canonical form. The
135+
* lower-S form reduces the size of signatures slightly on average when
136+
* variable length encodings (such as DER) are used and is cheap to
137+
* verify, making it a good choice. Security of always using lower-S is
138+
* assured because anyone can trivially modify a signature after the
139+
* fact to enforce this property. Adjusting it inside the signing
140+
* function avoids the need to re-serialize or have curve specific
141+
* constants outside of the library. By always using a canonical form
142+
* even in applications where it isn't needed it becomes possible to
143+
* impose a requirement later if a need is discovered.
144+
* No other forms of ECDSA malleability are known and none seem likely,
145+
* but there is no formal proof that ECDSA, even with this additional
146+
* restriction, is free of other malleability. Commonly used serialization
147+
* schemes will also accept various non-unique encodings, so care should
148+
* be taken when this property is required for an application.
118149
*/
119150
int secp256k1_ecdsa_sign(
120151
const unsigned char *msg32,
@@ -127,12 +158,13 @@ int secp256k1_ecdsa_sign(
127158

128159
/** Create a compact ECDSA signature (64 byte + recovery id).
129160
* Returns: 1: signature created
130-
* 0: the nonce generation function failed
161+
* 0: the nonce generation function failed, or the secret key was invalid.
131162
* In: msg32: the 32-byte message hash being signed (cannot be NULL)
132-
* seckey: pointer to a 32-byte secret key (cannot be NULL, assumed to be valid)
163+
* seckey: pointer to a 32-byte secret key (cannot be NULL)
133164
* noncefp:pointer to a nonce generation function. If NULL, secp256k1_nonce_function_default is used
134165
* ndata: pointer to arbitrary data used by the nonce generation function (can be NULL)
135166
* Out: sig: pointer to a 64-byte array where the signature will be placed (cannot be NULL)
167+
* In case 0 is returned, the returned signature length will be zero.
136168
* recid: pointer to an int, which will be updated to contain the recovery id (can be NULL)
137169
* Requires starting using SECP256K1_START_SIGN.
138170
*/

‎src/bench.h‎

Lines changed: 24 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -17,21 +17,40 @@ static double gettimedouble(void) {
1717
return tv.tv_usec * 0.000001 + tv.tv_sec;
1818
}
1919

20-
void run_benchmark(void (*benchmark)(void*), void (*setup)(void*), void (*teardown)(void*), void* data, int count, int iter) {
20+
void print_number(double x) {
21+
double y = x;
22+
int c = 0;
23+
if (y < 0.0) y = -y;
24+
while (y < 100.0) {
25+
y *= 10.0;
26+
c++;
27+
}
28+
printf("%.*f", c, x);
29+
}
30+
31+
void run_benchmark(char *name, void (*benchmark)(void*), void (*setup)(void*), void (*teardown)(void*), void* data, int count, int iter) {
32+
int i;
2133
double min = HUGE_VAL;
2234
double sum = 0.0;
2335
double max = 0.0;
24-
for (int i = 0; i < count; i++) {
36+
for (i = 0; i < count; i++) {
37+
double begin, total;
2538
if (setup) setup(data);
26-
double begin = gettimedouble();
39+
begin = gettimedouble();
2740
benchmark(data);
28-
double total = gettimedouble() - begin;
41+
total = gettimedouble() - begin;
2942
if (teardown) teardown(data);
3043
if (total < min) min = total;
3144
if (total > max) max = total;
3245
sum += total;
3346
}
34-
printf("min %.3fus / avg %.3fus / max %.3fus\n", min * 1000000.0 / iter, (sum / count) * 1000000.0 / iter, max * 1000000.0 / iter);
47+
printf("%s: min ", name);
48+
print_number(min * 1000000.0 / iter);
49+
printf("us / avg ");
50+
print_number((sum / count) * 1000000.0 / iter);
51+
printf("us / avg ");
52+
print_number(max * 1000000.0 / iter);
53+
printf("us\n");
3554
}
3655

3756
#endif

0 commit comments

Comments
 (0)