diff options
| author | Pieter Wuille <pieter@wuille.net> | 2020-06-09 13:39:09 -0700 |
|---|---|---|
| committer | Pieter Wuille <pieter@wuille.net> | 2020-06-09 13:39:09 -0700 |
| commit | 67f232b5d874b501c114bced5d764db7f4f5ce99 (patch) | |
| tree | 8ea0c31c64dfe0dd8f6f775c444cd22ef94d17cc /src | |
| parent | 54245985fb3c89d72e285c4db39d38ed2f5fb0de (diff) | |
Squashed 'src/secp256k1/' changes from b19c000063..2ed54da18a
2ed54da18a Merge #755: Recovery signing: add to constant time test, and eliminate non ct operators
28609507e7 Add tests for the cmov implementations
73596a85a2 Add ecdsa_sign_recoverable to the ctime tests
2876af4f8d Split ecdsa_sign logic into a new function and use it from ecdsa_sign and recovery
5e1c885efb Merge #754: Fix uninit values passed into cmov
f79a7adcf5 Add valgrind uninit check to cmovs output
05d315affe Merge #752: autoconf: Use ":" instead of "dnl" as a noop
a39c2b09de Fixed UB(arithmetics on uninit values) in cmovs
3a6fd7f636 Merge #750: Add macOS to the CI
5e8747ae2a autoconf: Use ":" instead of "dnl" as a noop
71757da5cc Explictly pass SECP256K1_BENCH_ITERS to the benchmarks in travis.sh
99bd661d71 Replace travis_wait with a loop printing "\a" to stdout every minute
bc818b160c Bump travis Ubuntu from xenial(16.04) to bionic(18.04)
0c5ff9066e Add macOS support to travis
b6807d91d8 Move travis script into a standalone sh file
f39f99be0e Merge #701: Make ec_ arithmetic more consistent and add documentation
39198a03ea Merge #732: Retry if r is zero during signing
59a8de8f64 Merge #742: Fix typo in ecmult_const_impl.h
4e284655d9 Fix typo in ecmult_const_impl.h
f862b4ca13 Merge #740: Make recovery/main_impl.h non-executable
ffef45c98a Make recovery/main_impl.h non-executable
2361b3719a Merge #735: build: fix OpenSSL EC detection on macOS
3b7d26b23c build: add SECP_TEST_INCLUDES to bench_verify CPPFLAGS
84b5fc5bc3 build: fix OpenSSL EC detection on macOS
37ed51a7ea Make ecdsa_sig_sign constant-time again after reverting 25e3cfb
93d343bfc5 Revert "ecdsa_impl: replace scalar if-checks with VERIFY_CHECKs in ecdsa_sig_sign"
7e3952ae82 Clarify documentation of tweak functions.
89853a0f2e Make tweak function documentation more consistent.
41fc785602 Make ec_privkey functions aliases for ec_seckey_negate, ec_seckey_tweak_add and ec_seckey_mul
22911ee6da Rename private key to secret key in public API (with the exception of function names)
5a73f14d6c Mention that value is unspecified for In/Out parameters if the function returns 0
f03df0e6d7 Define valid ECDSA keys in the documentation of seckey_verify
5894e1f1df Return 0 if the given seckey is invalid in privkey_negate, privkey_tweak_add and privkey_tweak_mul
8f814cddb9 Add test for boundary conditions of scalar_set_b32 with respect to overflows
3fec982608 Use scalar_set_b32_seckey in ecdsa_sign, pubkey_create and seckey_verify
9ab2cbe0eb Add scalar_set_b32_seckey which does the same as scalar_set_b32 and also returns whether it's a valid secret key
4f27e344c6 Merge #728: Suppress a harmless variable-time optimization by clang in memczero
01993878bb Add test for memczero()
52a03512c1 Suppress a harmless variable-time optimization by clang in memczero
8f78e208ad Merge #722: Context isn't freed in the ECDH benchmark
ed1b91171a Merge #700: Allow overriding default flags
85b35afa76 Add running benchmarks regularly and under valgrind in travis
ca4906b02e Pass num of iters to benchmarks as variable, and define envvar
02dd5f1bbb free the ctx at the end of bench_ecdh
e9fccd4de1 Merge #708: Constant-time behaviour test using valgrind memtest.
08fb6c4926 Run valgrind_ctime_test in travis
3d2302257f Constant-time behaviour test using valgrind memtest.
96d8ccbd16 Merge #710: Eliminate harmless non-constant time operations on secret data.
0585b8b2ee Merge #718: Clarify that a secp256k1_ecdh_hash_function must return 0 or 1
7b50483ad7 Adds a declassify operation to aid constant-time analysis.
34a67c773b Eliminate harmless non-constant time operations on secret data.
ca739cba23 Compile with optimization flag -O2 by default instead of -O3
eb45ef3384 Clarify that a secp256k1_ecdh_hash_function must return 0 or 1
856a01d6ad Merge #714: doc: document the length requirements of output parameter.
d72b9e2483 Merge #682: Remove Java Native Interface
4b48a43106 doc: document the length requirements of output parameter.
1b4d256e2e Merge #713: Docstrings
dabfea7e21 field: extend docstring of secp256k1_fe_normalize
dc7d8fd9e2 scalar: extend docstring of secp256k1_scalar_set_b32
074ab582dd Merge #704: README: add a section for test coverage
acb7f97eb8 README: add a section for test coverage
227a4f2d07 Merge #709: Remove secret-dependant non-constant time operation in ecmult_const.
d567b779fe Clarify comments about use of rzr on ge functions and abs function.
2241ae6d14 Remove secret-dependant non-constant time operation in ecmult_const.
642cd062bd Remove Java Native Interface
83fb1bcef4 Remove -O2 from default CFLAGS because this would override the -O3 flag (see AC_PROG_CC in the Autoconf manual)
ecba8138ec Append instead of Prepend user-CFLAGS to default CFLAGS allowing the user to override default variables
613c34cd86 Remove test in configure.ac because it doesn't have an effect
f45d897101 Merge #703: Overhaul README.md
2e759ec753 Overhaul README.md
d644dda5c9 Merge #689: Remove "except in benchmarks" exception for fp math
bde2a32286 Convert bench.h to fixed-point math
387d723c3f Merge #679: Add SECURITY.md
0db61d25c9 Merge #685: Fix issue where travis does not show the ./tests seed…
a0771d15e6 Explicitly disable buffering for stderr in tests
fb424fbba2 Make travis show the ./tests seed by removing stdout buffering and always cat tests.log after a travis run.
22a6031184 Merge #690: Add valgrind check to travis
544002c008 Merge #678: Preventing compiler optimizations in benchmarks without a memory fence
dd98cc988f travis: Added a valgrind test without endro and enabled recovery+ecdh
b4c1382a87 Add valgrind check to travis
0c774d89e6 Merge #688: Fix ASM setting in travis
5c5f71eea5 Fix ASM setting in travis
e2625f8a98 Merge #684: Make no-float policy explicit
bae1bea3c4 Make no-float policy explicit
78c3836341 Add SECURITY.md
362bb25608 Modified bench_scalar_split so it won't get optimized out
73a30c6b58 Added accumulators and checks on benchmarks so they won't get optimized out
770b3dcd6f Merge #677: Remove note about heap allocation in secp256k1_ecmult_odd_multiples_table_storage_var
b76142ff25 Remove note about heap allocation in secp256k1_ecmult_odd_multiples_table_storage_var which was removed in 47045270fa90f81205d989f7107769bce1e71c4d
137d304a6b Merge #647: Increase robustness against UB in secp256k1_scalar_cadd_bit
0d9540b13f Merge #664: Remove mention of ec_privkey_export because it doesn't exist
59782c68b4 Remove mention of ec_privkey_export because it doesn't exist
96cd94e385 Merge #337: variable sized precomputed table for signing
dcb2e3b3ff variable signing precompute table
b4bff99028 Merge #661: Make ./configure string consistent
a467047e11 Make ./configure string consistent
e729cc7f5a Merge #657: Fix a nit in the recovery tests
b64a2e2597 Fix a nit in the recovery tests
e028aa33d3 Merge #650: secp256k1/src/tests.c: Properly handle sscanf return value
f1e11d363d Merge #654: Fix typo (∞)
ef83281c3a Merge pull request #656 from real-or-random/patch-1
556caad2ca Fix typo in docs for _context_set_illegal_callback
0d82732a9a 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.
786dfb49f5 Merge #583: JNI: fix use sig array
e95f8ab098 Merge #644: Avoid optimizing out a verify_check
384f55606a Merge #652: README.md: update instruction to run tests
ee56accd47 Merge #651: Fix typo in secp256k1_preallocated.h
7b9b117230 Merge #640: scalar_impl.h: fix includes
d99bec2e21 Merge #655: jni: Use only Guava for hex encoding and decoding
2abcf951af jni: Use only Guava for hex encoding and decoding
271582b3b7 Fix typo
ce6d438266 README.md: update instruction to run tests
b1e68cb8e6 Fix typo in secp256k1_preallocated.h
a11c76c59a secp256k1/src/tests.c: Properly handle sscanf return value
8fe63e5654 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.
94ae7cbf83 Moved a dereference so the null check will be before the dereferencing
2cb73b1064 scalar_impl.h: fix includes
fa33017135 Merge #634: Add a descriptive comment for secp256k1_ecmult_const.
ee9e68cd30 Add a descriptive comment for secp256k1_ecmult_const.
d0d738d32d Merge #631: typo in comment for secp256k1_ec_pubkey_tweak_mul ()
6914c25276 typo in comment for secp256k1_ec_pubkey_tweak_mul ()
e541a90ef6 Merge #629: Avoid calling _is_zero when _set_b32 fails.
f34b0c3f35 Merge #630: Note intention of timing sidechannel freeness.
8d1563b0ff Note intention of timing sidechannel freeness.
1669bb2865 Merge #628: Fix ability to compile tests without -DVERIFY.
ecc94abcc8 Merge #627: Guard memcmp in tests against mixed size inputs.
544435fc90 Merge #578: Avoid implementation-defined and undefined behavior when dealing with sizes
143dc6e9ee Merge #595: Allow to use external default callbacks
e49f7991c2 Add missing #(un)defines to base-config.h
77defd2c3b Add secp256k1_ prefix to default callback functions
908bdce64e Include stdio.h and stdlib.h explicitly in secp256k1.c
5db782e655 Allow usage of external default callbacks
6095a863fa Replace CHECKs for no_precomp ctx by ARG_CHECKs without a return
cd473e02c3 Avoid calling secp256k1_*_is_zero when secp256k1_*_set_b32 fails.
6c36de7a33 Merge #600: scratch space: use single allocation
98836b11f0 scratch: replace frames with "checkpoint" system
7623cf2b97 scratch: save a couple bytes of unnecessarily-allocated memory
a7a164f2c6 scratch: rename `max_size` to `size`, document that extra will actually be allocated
5a4bc0bb95 scratch: unify allocations
c2b028a281 scratch space: thread `error_callback` into all scratch space functions
0be1a4ae62 scratch: add magic bytes to beginning of structure
92a48a764d scratch space: use single allocation
40839e21b9 Merge #592: Use trivial algorithm in ecmult_multi if scratch space is small
dcf392027b Fix ability to compile tests without -DVERIFY.
a484e0008b Merge #566: Enable context creation in preallocated memory
0522caac8f Explain caller's obligations for preallocated memory
238305fdbb Move _preallocated functions to separate header
695feb6fbd Export _preallocated functions
814cc78d71 Add tests for contexts in preallocated memory
ba12dd08da Check arguments of _preallocated functions
5feadde462 Support cloning a context into preallocated memory
c4fd5dab45 Switch to a single malloc call
ef020de16f Add size constants for preallocated memory
1bf7c056ba Prepare for manual memory management in preallocated memory
248bffb052 Guard memcmp in tests against mixed size inputs.
36698dcfee Merge #596: Make WINDOW_G configurable
a61a93ff50 Clean up ./configure help strings
2842dc523e Make WINDOW_G configurable
1a02d6ce51 Merge #626: Revert "Merge #620: Install headers automatically"
662918cb29 Revert "Merge #620: Install headers automatically"
14c7dbd444 Simplify control flow in DER parsing
ec8f20babd Avoid out-of-bound pointers and integer overflows in size comparisons
01ee1b3b3c Parse DER-enconded length into a size_t instead of an int
912680ed86 Merge #561: Respect LDFLAGS and #undef STATIC_PRECOMPUTATION if using basic config
91fae3ace0 Merge #620: Install headers automatically
5df77a0eda Merge #533: Make sure we're not using an uninitialized variable in secp256k1_wnaf_const(...)
975e51e0d9 Merge #617: Pass scalar by reference in secp256k1_wnaf_const()
735fbde04e Merge #619: Clear a copied secret key after negation
16e86150d0 Install headers automatically
069870d92a Clear a copied secret key after negation
8979ec0d9a Pass scalar by reference in secp256k1_wnaf_const()
84a808598b Merge #612: Allow field_10x26_arm.s to compile for ARMv7 architecture
d4d270a59c Allow field_10x26_arm.s to compile for ARMv7 architecture
248f046611 Make sure we're not using an uninitialized variable in secp256k1_wnaf_const(...)
9ab96f7b12 Use trivial algorithm in ecmult_multi if scratch space is small
dbed75d969 Undefine `STATIC_PRECOMPUTATION` if using the basic config
310111e093 Keep LDFLAGS if `--coverage`
74e2dbd68e JNI: fix use sig array
3cb057f842 Fix possible integer overflow in DER parsing
git-subtree-dir: src/secp256k1
git-subtree-split: 2ed54da18add295668ec71c91534b640d2cc029b
Diffstat (limited to 'src')
49 files changed, 1763 insertions, 2076 deletions
diff --git a/src/asm/field_10x26_arm.s b/src/asm/field_10x26_arm.s index 5a9cc3ffcf..9a5bd06721 100644 --- a/src/asm/field_10x26_arm.s +++ b/src/asm/field_10x26_arm.s @@ -16,15 +16,9 @@ Note: */ .syntax unified - .arch armv7-a @ eabi attributes - see readelf -A - .eabi_attribute 8, 1 @ Tag_ARM_ISA_use = yes - .eabi_attribute 9, 0 @ Tag_Thumb_ISA_use = no - .eabi_attribute 10, 0 @ Tag_FP_arch = none .eabi_attribute 24, 1 @ Tag_ABI_align_needed = 8-byte .eabi_attribute 25, 1 @ Tag_ABI_align_preserved = 8-byte, except leaf SP - .eabi_attribute 30, 2 @ Tag_ABI_optimization_goals = Aggressive Speed - .eabi_attribute 34, 1 @ Tag_CPU_unaligned_access = v6 .text @ Field constants diff --git a/src/basic-config.h b/src/basic-config.h index fc588061ca..e9be39d4ca 100644 --- a/src/basic-config.h +++ b/src/basic-config.h @@ -10,7 +10,10 @@ #ifdef USE_BASIC_CONFIG #undef USE_ASM_X86_64 +#undef USE_ECMULT_STATIC_PRECOMPUTATION #undef USE_ENDOMORPHISM +#undef USE_EXTERNAL_ASM +#undef USE_EXTERNAL_DEFAULT_CALLBACKS #undef USE_FIELD_10X26 #undef USE_FIELD_5X52 #undef USE_FIELD_INV_BUILTIN @@ -21,12 +24,14 @@ #undef USE_SCALAR_8X32 #undef USE_SCALAR_INV_BUILTIN #undef USE_SCALAR_INV_NUM +#undef ECMULT_WINDOW_SIZE #define USE_NUM_NONE 1 #define USE_FIELD_INV_BUILTIN 1 #define USE_SCALAR_INV_BUILTIN 1 #define USE_FIELD_10X26 1 #define USE_SCALAR_8X32 1 +#define ECMULT_WINDOW_SIZE 15 #endif /* USE_BASIC_CONFIG */ diff --git a/src/bench.h b/src/bench.h index 5b59783f68..9bfed903e0 100644 --- a/src/bench.h +++ b/src/bench.h @@ -7,45 +7,87 @@ #ifndef SECP256K1_BENCH_H #define SECP256K1_BENCH_H +#include <stdint.h> #include <stdio.h> #include <string.h> -#include <math.h> #include "sys/time.h" -static double gettimedouble(void) { +static int64_t gettime_i64(void) { struct timeval tv; gettimeofday(&tv, NULL); - return tv.tv_usec * 0.000001 + tv.tv_sec; + return (int64_t)tv.tv_usec + (int64_t)tv.tv_sec * 1000000LL; } -void print_number(double x) { - double y = x; - int c = 0; - if (y < 0.0) { - y = -y; +#define FP_EXP (6) +#define FP_MULT (1000000LL) + +/* Format fixed point number. */ +void print_number(const int64_t x) { + int64_t x_abs, y; + int c, i, rounding; + size_t ptr; + char buffer[30]; + + if (x == INT64_MIN) { + /* Prevent UB. */ + printf("ERR"); + return; } - while (y > 0 && y < 100.0) { - y *= 10.0; + x_abs = x < 0 ? -x : x; + + /* Determine how many decimals we want to show (more than FP_EXP makes no + * sense). */ + y = x_abs; + c = 0; + while (y > 0LL && y < 100LL * FP_MULT && c < FP_EXP) { + y *= 10LL; c++; } - printf("%.*f", c, x); + + /* Round to 'c' decimals. */ + y = x_abs; + rounding = 0; + for (i = c; i < FP_EXP; ++i) { + rounding = (y % 10) >= 5; + y /= 10; + } + y += rounding; + + /* Format and print the number. */ + ptr = sizeof(buffer) - 1; + buffer[ptr] = 0; + if (c != 0) { + for (i = 0; i < c; ++i) { + buffer[--ptr] = '0' + (y % 10); + y /= 10; + } + buffer[--ptr] = '.'; + } + do { + buffer[--ptr] = '0' + (y % 10); + y /= 10; + } while (y != 0); + if (x < 0) { + buffer[--ptr] = '-'; + } + printf("%s", &buffer[ptr]); } -void run_benchmark(char *name, void (*benchmark)(void*), void (*setup)(void*), void (*teardown)(void*), void* data, int count, int iter) { +void run_benchmark(char *name, void (*benchmark)(void*, int), void (*setup)(void*), void (*teardown)(void*, int), void* data, int count, int iter) { int i; - double min = HUGE_VAL; - double sum = 0.0; - double max = 0.0; + int64_t min = INT64_MAX; + int64_t sum = 0; + int64_t max = 0; for (i = 0; i < count; i++) { - double begin, total; + int64_t begin, total; if (setup != NULL) { setup(data); } - begin = gettimedouble(); - benchmark(data); - total = gettimedouble() - begin; + begin = gettime_i64(); + benchmark(data, iter); + total = gettime_i64() - begin; if (teardown != NULL) { - teardown(data); + teardown(data, iter); } if (total < min) { min = total; @@ -56,11 +98,11 @@ void run_benchmark(char *name, void (*benchmark)(void*), void (*setup)(void*), v sum += total; } printf("%s: min ", name); - print_number(min * 1000000.0 / iter); + print_number(min * FP_MULT / iter); printf("us / avg "); - print_number((sum / count) * 1000000.0 / iter); + print_number(((sum * FP_MULT) / count) / iter); printf("us / max "); - print_number(max * 1000000.0 / iter); + print_number(max * FP_MULT / iter); printf("us\n"); } @@ -79,4 +121,13 @@ int have_flag(int argc, char** argv, char *flag) { return 0; } +int get_iters(int default_iters) { + char* env = getenv("SECP256K1_BENCH_ITERS"); + if (env) { + return strtol(env, NULL, 0); + } else { + return default_iters; + } +} + #endif /* SECP256K1_BENCH_H */ diff --git a/src/bench_ecdh.c b/src/bench_ecdh.c index c1dd5a6ac9..f099d33884 100644 --- a/src/bench_ecdh.c +++ b/src/bench_ecdh.c @@ -28,20 +28,18 @@ static void bench_ecdh_setup(void* arg) { 0xa2, 0xba, 0xd1, 0x84, 0xf8, 0x83, 0xc6, 0x9f }; - /* create a context with no capabilities */ - data->ctx = secp256k1_context_create(SECP256K1_FLAGS_TYPE_CONTEXT); for (i = 0; i < 32; i++) { data->scalar[i] = i + 1; } CHECK(secp256k1_ec_pubkey_parse(data->ctx, &data->point, point, sizeof(point)) == 1); } -static void bench_ecdh(void* arg) { +static void bench_ecdh(void* arg, int iters) { int i; unsigned char res[32]; bench_ecdh_data *data = (bench_ecdh_data*)arg; - for (i = 0; i < 20000; i++) { + for (i = 0; i < iters; i++) { CHECK(secp256k1_ecdh(data->ctx, res, &data->point, data->scalar, NULL, NULL) == 1); } } @@ -49,6 +47,13 @@ static void bench_ecdh(void* arg) { int main(void) { bench_ecdh_data data; - run_benchmark("ecdh", bench_ecdh, bench_ecdh_setup, NULL, &data, 10, 20000); + int iters = get_iters(20000); + + /* create a context with no capabilities */ + data.ctx = secp256k1_context_create(SECP256K1_FLAGS_TYPE_CONTEXT); + + run_benchmark("ecdh", bench_ecdh, bench_ecdh_setup, NULL, &data, 10, iters); + + secp256k1_context_destroy(data.ctx); return 0; } diff --git a/src/bench_ecmult.c b/src/bench_ecmult.c index 6d0ed1f436..facd07ef31 100644 --- a/src/bench_ecmult.c +++ b/src/bench_ecmult.c @@ -18,7 +18,6 @@ #include "secp256k1.c" #define POINTS 32768 -#define ITERS 10000 typedef struct { /* Setup once in advance */ @@ -55,16 +54,16 @@ static int bench_callback(secp256k1_scalar* sc, secp256k1_ge* ge, size_t idx, vo return 1; } -static void bench_ecmult(void* arg) { +static void bench_ecmult(void* arg, int iters) { bench_data* data = (bench_data*)arg; - size_t count = data->count; int includes_g = data->includes_g; - size_t iters = 1 + ITERS / count; - size_t iter; + int iter; + int count = data->count; + iters = iters / data->count; for (iter = 0; iter < iters; ++iter) { - data->ecmult_multi(&data->ctx->ecmult_ctx, data->scratch, &data->output[iter], data->includes_g ? &data->scalars[data->offset1] : NULL, bench_callback, arg, count - includes_g); + data->ecmult_multi(&data->ctx->error_callback, &data->ctx->ecmult_ctx, data->scratch, &data->output[iter], data->includes_g ? &data->scalars[data->offset1] : NULL, bench_callback, arg, count - includes_g); data->offset1 = (data->offset1 + count) % POINTS; data->offset2 = (data->offset2 + count - 1) % POINTS; } @@ -76,10 +75,10 @@ static void bench_ecmult_setup(void* arg) { data->offset2 = (data->count * 0x7f6f537b + 0x6a1a8f49) % POINTS; } -static void bench_ecmult_teardown(void* arg) { +static void bench_ecmult_teardown(void* arg, int iters) { bench_data* data = (bench_data*)arg; - size_t iters = 1 + ITERS / data->count; - size_t iter; + int iter; + iters = iters / data->count; /* Verify the results in teardown, to avoid doing comparisons while benchmarking. */ for (iter = 0; iter < iters; ++iter) { secp256k1_gej tmp; @@ -104,10 +103,10 @@ static void generate_scalar(uint32_t num, secp256k1_scalar* scalar) { CHECK(!overflow); } -static void run_test(bench_data* data, size_t count, int includes_g) { +static void run_test(bench_data* data, size_t count, int includes_g, int num_iters) { char str[32]; static const secp256k1_scalar zero = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0); - size_t iters = 1 + ITERS / count; + size_t iters = 1 + num_iters / count; size_t iter; data->count = count; @@ -130,7 +129,7 @@ static void run_test(bench_data* data, size_t count, int includes_g) { /* Run the benchmark. */ sprintf(str, includes_g ? "ecmult_%ig" : "ecmult_%i", (int)count); - run_benchmark(str, bench_ecmult, bench_ecmult_setup, bench_ecmult_teardown, data, 10, count * (1 + ITERS / count)); + run_benchmark(str, bench_ecmult, bench_ecmult_setup, bench_ecmult_teardown, data, 10, count * iters); } int main(int argc, char **argv) { @@ -139,6 +138,8 @@ int main(int argc, char **argv) { secp256k1_gej* pubkeys_gej; size_t scratch_size; + int iters = get_iters(10000); + data.ctx = secp256k1_context_create(SECP256K1_CONTEXT_SIGN | SECP256K1_CONTEXT_VERIFY); scratch_size = secp256k1_strauss_scratch_size(POINTS) + STRAUSS_SCRATCH_OBJECTS*16; data.scratch = secp256k1_scratch_space_create(data.ctx, scratch_size); @@ -154,7 +155,7 @@ int main(int argc, char **argv) { } else if(have_flag(argc, argv, "simple")) { printf("Using simple algorithm:\n"); data.ecmult_multi = secp256k1_ecmult_multi_var; - secp256k1_scratch_space_destroy(data.scratch); + secp256k1_scratch_space_destroy(data.ctx, data.scratch); data.scratch = NULL; } else { fprintf(stderr, "%s: unrecognized argument '%s'.\n", argv[0], argv[1]); @@ -167,8 +168,8 @@ int main(int argc, char **argv) { data.scalars = malloc(sizeof(secp256k1_scalar) * POINTS); data.seckeys = malloc(sizeof(secp256k1_scalar) * POINTS); data.pubkeys = malloc(sizeof(secp256k1_ge) * POINTS); - data.expected_output = malloc(sizeof(secp256k1_gej) * (ITERS + 1)); - data.output = malloc(sizeof(secp256k1_gej) * (ITERS + 1)); + data.expected_output = malloc(sizeof(secp256k1_gej) * (iters + 1)); + data.output = malloc(sizeof(secp256k1_gej) * (iters + 1)); /* Generate a set of scalars, and private/public keypairs. */ pubkeys_gej = malloc(sizeof(secp256k1_gej) * POINTS); @@ -185,18 +186,24 @@ int main(int argc, char **argv) { free(pubkeys_gej); for (i = 1; i <= 8; ++i) { - run_test(&data, i, 1); + run_test(&data, i, 1, iters); } - for (p = 0; p <= 11; ++p) { - for (i = 9; i <= 16; ++i) { - run_test(&data, i << p, 1); + /* This is disabled with low count of iterations because the loop runs 77 times even with iters=1 + * and the higher it goes the longer the computation takes(more points) + * So we don't run this benchmark with low iterations to prevent slow down */ + if (iters > 2) { + for (p = 0; p <= 11; ++p) { + for (i = 9; i <= 16; ++i) { + run_test(&data, i << p, 1, iters); + } } } - secp256k1_context_destroy(data.ctx); + if (data.scratch != NULL) { - secp256k1_scratch_space_destroy(data.scratch); + secp256k1_scratch_space_destroy(data.ctx, data.scratch); } + secp256k1_context_destroy(data.ctx); free(data.scalars); free(data.pubkeys); free(data.seckeys); diff --git a/src/bench_internal.c b/src/bench_internal.c index 9071724331..20759127d3 100644 --- a/src/bench_internal.c +++ b/src/bench_internal.c @@ -56,263 +56,272 @@ void bench_setup(void* arg) { memcpy(data->data + 32, init_y, 32); } -void bench_scalar_add(void* arg) { - int i; +void bench_scalar_add(void* arg, int iters) { + int i, j = 0; bench_inv *data = (bench_inv*)arg; - for (i = 0; i < 2000000; i++) { - secp256k1_scalar_add(&data->scalar_x, &data->scalar_x, &data->scalar_y); + for (i = 0; i < iters; i++) { + j += secp256k1_scalar_add(&data->scalar_x, &data->scalar_x, &data->scalar_y); } + CHECK(j <= iters); } -void bench_scalar_negate(void* arg) { +void bench_scalar_negate(void* arg, int iters) { int i; bench_inv *data = (bench_inv*)arg; - for (i = 0; i < 2000000; i++) { + for (i = 0; i < iters; i++) { secp256k1_scalar_negate(&data->scalar_x, &data->scalar_x); } } -void bench_scalar_sqr(void* arg) { +void bench_scalar_sqr(void* arg, int iters) { int i; bench_inv *data = (bench_inv*)arg; - for (i = 0; i < 200000; i++) { + for (i = 0; i < iters; i++) { secp256k1_scalar_sqr(&data->scalar_x, &data->scalar_x); } } -void bench_scalar_mul(void* arg) { +void bench_scalar_mul(void* arg, int iters) { int i; bench_inv *data = (bench_inv*)arg; - for (i = 0; i < 200000; i++) { + for (i = 0; i < iters; i++) { secp256k1_scalar_mul(&data->scalar_x, &data->scalar_x, &data->scalar_y); } } #ifdef USE_ENDOMORPHISM -void bench_scalar_split(void* arg) { - int i; +void bench_scalar_split(void* arg, int iters) { + int i, j = 0; bench_inv *data = (bench_inv*)arg; - for (i = 0; i < 20000; i++) { - secp256k1_scalar l, r; - secp256k1_scalar_split_lambda(&l, &r, &data->scalar_x); - secp256k1_scalar_add(&data->scalar_x, &data->scalar_x, &data->scalar_y); + for (i = 0; i < iters; i++) { + secp256k1_scalar_split_lambda(&data->scalar_x, &data->scalar_y, &data->scalar_x); + j += secp256k1_scalar_add(&data->scalar_x, &data->scalar_x, &data->scalar_y); } + CHECK(j <= iters); } #endif -void bench_scalar_inverse(void* arg) { - int i; +void bench_scalar_inverse(void* arg, int iters) { + int i, j = 0; bench_inv *data = (bench_inv*)arg; - for (i = 0; i < 2000; i++) { + for (i = 0; i < iters; i++) { secp256k1_scalar_inverse(&data->scalar_x, &data->scalar_x); - secp256k1_scalar_add(&data->scalar_x, &data->scalar_x, &data->scalar_y); + j += secp256k1_scalar_add(&data->scalar_x, &data->scalar_x, &data->scalar_y); } + CHECK(j <= iters); } -void bench_scalar_inverse_var(void* arg) { - int i; +void bench_scalar_inverse_var(void* arg, int iters) { + int i, j = 0; bench_inv *data = (bench_inv*)arg; - for (i = 0; i < 2000; i++) { + for (i = 0; i < iters; i++) { secp256k1_scalar_inverse_var(&data->scalar_x, &data->scalar_x); - secp256k1_scalar_add(&data->scalar_x, &data->scalar_x, &data->scalar_y); + j += secp256k1_scalar_add(&data->scalar_x, &data->scalar_x, &data->scalar_y); } + CHECK(j <= iters); } -void bench_field_normalize(void* arg) { +void bench_field_normalize(void* arg, int iters) { int i; bench_inv *data = (bench_inv*)arg; - for (i = 0; i < 2000000; i++) { + for (i = 0; i < iters; i++) { secp256k1_fe_normalize(&data->fe_x); } } -void bench_field_normalize_weak(void* arg) { +void bench_field_normalize_weak(void* arg, int iters) { int i; bench_inv *data = (bench_inv*)arg; - for (i = 0; i < 2000000; i++) { + for (i = 0; i < iters; i++) { secp256k1_fe_normalize_weak(&data->fe_x); } } -void bench_field_mul(void* arg) { +void bench_field_mul(void* arg, int iters) { int i; bench_inv *data = (bench_inv*)arg; - for (i = 0; i < 200000; i++) { + for (i = 0; i < iters; i++) { secp256k1_fe_mul(&data->fe_x, &data->fe_x, &data->fe_y); } } -void bench_field_sqr(void* arg) { +void bench_field_sqr(void* arg, int iters) { int i; bench_inv *data = (bench_inv*)arg; - for (i = 0; i < 200000; i++) { + for (i = 0; i < iters; i++) { secp256k1_fe_sqr(&data->fe_x, &data->fe_x); } } -void bench_field_inverse(void* arg) { +void bench_field_inverse(void* arg, int iters) { int i; bench_inv *data = (bench_inv*)arg; - for (i = 0; i < 20000; i++) { + for (i = 0; i < iters; i++) { secp256k1_fe_inv(&data->fe_x, &data->fe_x); secp256k1_fe_add(&data->fe_x, &data->fe_y); } } -void bench_field_inverse_var(void* arg) { +void bench_field_inverse_var(void* arg, int iters) { int i; bench_inv *data = (bench_inv*)arg; - for (i = 0; i < 20000; i++) { + for (i = 0; i < iters; i++) { secp256k1_fe_inv_var(&data->fe_x, &data->fe_x); secp256k1_fe_add(&data->fe_x, &data->fe_y); } } -void bench_field_sqrt(void* arg) { - int i; +void bench_field_sqrt(void* arg, int iters) { + int i, j = 0; bench_inv *data = (bench_inv*)arg; secp256k1_fe t; - for (i = 0; i < 20000; i++) { + for (i = 0; i < iters; i++) { t = data->fe_x; - secp256k1_fe_sqrt(&data->fe_x, &t); + j += secp256k1_fe_sqrt(&data->fe_x, &t); secp256k1_fe_add(&data->fe_x, &data->fe_y); } + CHECK(j <= iters); } -void bench_group_double_var(void* arg) { +void bench_group_double_var(void* arg, int iters) { int i; bench_inv *data = (bench_inv*)arg; - for (i = 0; i < 200000; i++) { + for (i = 0; i < iters; i++) { secp256k1_gej_double_var(&data->gej_x, &data->gej_x, NULL); } } -void bench_group_add_var(void* arg) { +void bench_group_add_var(void* arg, int iters) { int i; bench_inv *data = (bench_inv*)arg; - for (i = 0; i < 200000; i++) { + for (i = 0; i < iters; i++) { secp256k1_gej_add_var(&data->gej_x, &data->gej_x, &data->gej_y, NULL); } } -void bench_group_add_affine(void* arg) { +void bench_group_add_affine(void* arg, int iters) { int i; bench_inv *data = (bench_inv*)arg; - for (i = 0; i < 200000; i++) { + for (i = 0; i < iters; i++) { secp256k1_gej_add_ge(&data->gej_x, &data->gej_x, &data->ge_y); } } -void bench_group_add_affine_var(void* arg) { +void bench_group_add_affine_var(void* arg, int iters) { int i; bench_inv *data = (bench_inv*)arg; - for (i = 0; i < 200000; i++) { + for (i = 0; i < iters; i++) { secp256k1_gej_add_ge_var(&data->gej_x, &data->gej_x, &data->ge_y, NULL); } } -void bench_group_jacobi_var(void* arg) { - int i; +void bench_group_jacobi_var(void* arg, int iters) { + int i, j = 0; bench_inv *data = (bench_inv*)arg; - for (i = 0; i < 20000; i++) { - secp256k1_gej_has_quad_y_var(&data->gej_x); + for (i = 0; i < iters; i++) { + j += secp256k1_gej_has_quad_y_var(&data->gej_x); } + CHECK(j == iters); } -void bench_ecmult_wnaf(void* arg) { - int i; +void bench_ecmult_wnaf(void* arg, int iters) { + int i, bits = 0, overflow = 0; bench_inv *data = (bench_inv*)arg; - for (i = 0; i < 20000; i++) { - secp256k1_ecmult_wnaf(data->wnaf, 256, &data->scalar_x, WINDOW_A); - secp256k1_scalar_add(&data->scalar_x, &data->scalar_x, &data->scalar_y); + for (i = 0; i < iters; i++) { + bits += secp256k1_ecmult_wnaf(data->wnaf, 256, &data->scalar_x, WINDOW_A); + overflow += secp256k1_scalar_add(&data->scalar_x, &data->scalar_x, &data->scalar_y); } + CHECK(overflow >= 0); + CHECK(bits <= 256*iters); } -void bench_wnaf_const(void* arg) { - int i; +void bench_wnaf_const(void* arg, int iters) { + int i, bits = 0, overflow = 0; bench_inv *data = (bench_inv*)arg; - for (i = 0; i < 20000; i++) { - secp256k1_wnaf_const(data->wnaf, data->scalar_x, WINDOW_A, 256); - secp256k1_scalar_add(&data->scalar_x, &data->scalar_x, &data->scalar_y); + for (i = 0; i < iters; i++) { + bits += secp256k1_wnaf_const(data->wnaf, &data->scalar_x, WINDOW_A, 256); + overflow += secp256k1_scalar_add(&data->scalar_x, &data->scalar_x, &data->scalar_y); } + CHECK(overflow >= 0); + CHECK(bits <= 256*iters); } -void bench_sha256(void* arg) { +void bench_sha256(void* arg, int iters) { int i; bench_inv *data = (bench_inv*)arg; secp256k1_sha256 sha; - for (i = 0; i < 20000; i++) { + for (i = 0; i < iters; i++) { secp256k1_sha256_initialize(&sha); secp256k1_sha256_write(&sha, data->data, 32); secp256k1_sha256_finalize(&sha, data->data); } } -void bench_hmac_sha256(void* arg) { +void bench_hmac_sha256(void* arg, int iters) { int i; bench_inv *data = (bench_inv*)arg; secp256k1_hmac_sha256 hmac; - for (i = 0; i < 20000; i++) { + for (i = 0; i < iters; i++) { secp256k1_hmac_sha256_initialize(&hmac, data->data, 32); secp256k1_hmac_sha256_write(&hmac, data->data, 32); secp256k1_hmac_sha256_finalize(&hmac, data->data); } } -void bench_rfc6979_hmac_sha256(void* arg) { +void bench_rfc6979_hmac_sha256(void* arg, int iters) { int i; bench_inv *data = (bench_inv*)arg; secp256k1_rfc6979_hmac_sha256 rng; - for (i = 0; i < 20000; i++) { + for (i = 0; i < iters; i++) { secp256k1_rfc6979_hmac_sha256_initialize(&rng, data->data, 64); secp256k1_rfc6979_hmac_sha256_generate(&rng, data->data, 32); } } -void bench_context_verify(void* arg) { +void bench_context_verify(void* arg, int iters) { int i; (void)arg; - for (i = 0; i < 20; i++) { + for (i = 0; i < iters; i++) { secp256k1_context_destroy(secp256k1_context_create(SECP256K1_CONTEXT_VERIFY)); } } -void bench_context_sign(void* arg) { +void bench_context_sign(void* arg, int iters) { int i; (void)arg; - for (i = 0; i < 200; i++) { + for (i = 0; i < iters; i++) { secp256k1_context_destroy(secp256k1_context_create(SECP256K1_CONTEXT_SIGN)); } } #ifndef USE_NUM_NONE -void bench_num_jacobi(void* arg) { - int i; +void bench_num_jacobi(void* arg, int iters) { + int i, j = 0; bench_inv *data = (bench_inv*)arg; secp256k1_num nx, norder; @@ -320,50 +329,53 @@ void bench_num_jacobi(void* arg) { secp256k1_scalar_order_get_num(&norder); secp256k1_scalar_get_num(&norder, &data->scalar_y); - for (i = 0; i < 200000; i++) { - secp256k1_num_jacobi(&nx, &norder); + for (i = 0; i < iters; i++) { + j += secp256k1_num_jacobi(&nx, &norder); } + CHECK(j <= iters); } #endif int main(int argc, char **argv) { bench_inv data; - if (have_flag(argc, argv, "scalar") || have_flag(argc, argv, "add")) run_benchmark("scalar_add", bench_scalar_add, bench_setup, NULL, &data, 10, 2000000); - if (have_flag(argc, argv, "scalar") || have_flag(argc, argv, "negate")) run_benchmark("scalar_negate", bench_scalar_negate, bench_setup, NULL, &data, 10, 2000000); - if (have_flag(argc, argv, "scalar") || have_flag(argc, argv, "sqr")) run_benchmark("scalar_sqr", bench_scalar_sqr, bench_setup, NULL, &data, 10, 200000); - if (have_flag(argc, argv, "scalar") || have_flag(argc, argv, "mul")) run_benchmark("scalar_mul", bench_scalar_mul, bench_setup, NULL, &data, 10, 200000); + int iters = get_iters(20000); + + if (have_flag(argc, argv, "scalar") || have_flag(argc, argv, "add")) run_benchmark("scalar_add", bench_scalar_add, bench_setup, NULL, &data, 10, iters*100); + if (have_flag(argc, argv, "scalar") || have_flag(argc, argv, "negate")) run_benchmark("scalar_negate", bench_scalar_negate, bench_setup, NULL, &data, 10, iters*100); + if (have_flag(argc, argv, "scalar") || have_flag(argc, argv, "sqr")) run_benchmark("scalar_sqr", bench_scalar_sqr, bench_setup, NULL, &data, 10, iters*10); + if (have_flag(argc, argv, "scalar") || have_flag(argc, argv, "mul")) run_benchmark("scalar_mul", bench_scalar_mul, bench_setup, NULL, &data, 10, iters*10); #ifdef USE_ENDOMORPHISM - if (have_flag(argc, argv, "scalar") || have_flag(argc, argv, "split")) run_benchmark("scalar_split", bench_scalar_split, bench_setup, NULL, &data, 10, 20000); + if (have_flag(argc, argv, "scalar") || have_flag(argc, argv, "split")) run_benchmark("scalar_split", bench_scalar_split, bench_setup, NULL, &data, 10, iters); #endif if (have_flag(argc, argv, "scalar") || have_flag(argc, argv, "inverse")) run_benchmark("scalar_inverse", bench_scalar_inverse, bench_setup, NULL, &data, 10, 2000); if (have_flag(argc, argv, "scalar") || have_flag(argc, argv, "inverse")) run_benchmark("scalar_inverse_var", bench_scalar_inverse_var, bench_setup, NULL, &data, 10, 2000); - if (have_flag(argc, argv, "field") || have_flag(argc, argv, "normalize")) run_benchmark("field_normalize", bench_field_normalize, bench_setup, NULL, &data, 10, 2000000); - if (have_flag(argc, argv, "field") || have_flag(argc, argv, "normalize")) run_benchmark("field_normalize_weak", bench_field_normalize_weak, bench_setup, NULL, &data, 10, 2000000); - if (have_flag(argc, argv, "field") || have_flag(argc, argv, "sqr")) run_benchmark("field_sqr", bench_field_sqr, bench_setup, NULL, &data, 10, 200000); - if (have_flag(argc, argv, "field") || have_flag(argc, argv, "mul")) run_benchmark("field_mul", bench_field_mul, bench_setup, NULL, &data, 10, 200000); - if (have_flag(argc, argv, "field") || have_flag(argc, argv, "inverse")) run_benchmark("field_inverse", bench_field_inverse, bench_setup, NULL, &data, 10, 20000); - if (have_flag(argc, argv, "field") || have_flag(argc, argv, "inverse")) run_benchmark("field_inverse_var", bench_field_inverse_var, bench_setup, NULL, &data, 10, 20000); - if (have_flag(argc, argv, "field") || have_flag(argc, argv, "sqrt")) run_benchmark("field_sqrt", bench_field_sqrt, bench_setup, NULL, &data, 10, 20000); + if (have_flag(argc, argv, "field") || have_flag(argc, argv, "normalize")) run_benchmark("field_normalize", bench_field_normalize, bench_setup, NULL, &data, 10, iters*100); + if (have_flag(argc, argv, "field") || have_flag(argc, argv, "normalize")) run_benchmark("field_normalize_weak", bench_field_normalize_weak, bench_setup, NULL, &data, 10, iters*100); + if (have_flag(argc, argv, "field") || have_flag(argc, argv, "sqr")) run_benchmark("field_sqr", bench_field_sqr, bench_setup, NULL, &data, 10, iters*10); + if (have_flag(argc, argv, "field") || have_flag(argc, argv, "mul")) run_benchmark("field_mul", bench_field_mul, bench_setup, NULL, &data, 10, iters*10); + if (have_flag(argc, argv, "field") || have_flag(argc, argv, "inverse")) run_benchmark("field_inverse", bench_field_inverse, bench_setup, NULL, &data, 10, iters); + if (have_flag(argc, argv, "field") || have_flag(argc, argv, "inverse")) run_benchmark("field_inverse_var", bench_field_inverse_var, bench_setup, NULL, &data, 10, iters); + if (have_flag(argc, argv, "field") || have_flag(argc, argv, "sqrt")) run_benchmark("field_sqrt", bench_field_sqrt, bench_setup, NULL, &data, 10, iters); - if (have_flag(argc, argv, "group") || have_flag(argc, argv, "double")) run_benchmark("group_double_var", bench_group_double_var, bench_setup, NULL, &data, 10, 200000); - if (have_flag(argc, argv, "group") || have_flag(argc, argv, "add")) run_benchmark("group_add_var", bench_group_add_var, bench_setup, NULL, &data, 10, 200000); - if (have_flag(argc, argv, "group") || have_flag(argc, argv, "add")) run_benchmark("group_add_affine", bench_group_add_affine, bench_setup, NULL, &data, 10, 200000); - if (have_flag(argc, argv, "group") || have_flag(argc, argv, "add")) run_benchmark("group_add_affine_var", bench_group_add_affine_var, bench_setup, NULL, &data, 10, 200000); - if (have_flag(argc, argv, "group") || have_flag(argc, argv, "jacobi")) run_benchmark("group_jacobi_var", bench_group_jacobi_var, bench_setup, NULL, &data, 10, 20000); + if (have_flag(argc, argv, "group") || have_flag(argc, argv, "double")) run_benchmark("group_double_var", bench_group_double_var, bench_setup, NULL, &data, 10, iters*10); + if (have_flag(argc, argv, "group") || have_flag(argc, argv, "add")) run_benchmark("group_add_var", bench_group_add_var, bench_setup, NULL, &data, 10, iters*10); + if (have_flag(argc, argv, "group") || have_flag(argc, argv, "add")) run_benchmark("group_add_affine", bench_group_add_affine, bench_setup, NULL, &data, 10, iters*10); + if (have_flag(argc, argv, "group") || have_flag(argc, argv, "add")) run_benchmark("group_add_affine_var", bench_group_add_affine_var, bench_setup, NULL, &data, 10, iters*10); + if (have_flag(argc, argv, "group") || have_flag(argc, argv, "jacobi")) run_benchmark("group_jacobi_var", bench_group_jacobi_var, bench_setup, NULL, &data, 10, iters); - if (have_flag(argc, argv, "ecmult") || have_flag(argc, argv, "wnaf")) run_benchmark("wnaf_const", bench_wnaf_const, bench_setup, NULL, &data, 10, 20000); - if (have_flag(argc, argv, "ecmult") || have_flag(argc, argv, "wnaf")) run_benchmark("ecmult_wnaf", bench_ecmult_wnaf, bench_setup, NULL, &data, 10, 20000); + if (have_flag(argc, argv, "ecmult") || have_flag(argc, argv, "wnaf")) run_benchmark("wnaf_const", bench_wnaf_const, bench_setup, NULL, &data, 10, iters); + if (have_flag(argc, argv, "ecmult") || have_flag(argc, argv, "wnaf")) run_benchmark("ecmult_wnaf", bench_ecmult_wnaf, bench_setup, NULL, &data, 10, iters); - if (have_flag(argc, argv, "hash") || have_flag(argc, argv, "sha256")) run_benchmark("hash_sha256", bench_sha256, bench_setup, NULL, &data, 10, 20000); - if (have_flag(argc, argv, "hash") || have_flag(argc, argv, "hmac")) run_benchmark("hash_hmac_sha256", bench_hmac_sha256, bench_setup, NULL, &data, 10, 20000); - if (have_flag(argc, argv, "hash") || have_flag(argc, argv, "rng6979")) run_benchmark("hash_rfc6979_hmac_sha256", bench_rfc6979_hmac_sha256, bench_setup, NULL, &data, 10, 20000); + if (have_flag(argc, argv, "hash") || have_flag(argc, argv, "sha256")) run_benchmark("hash_sha256", bench_sha256, bench_setup, NULL, &data, 10, iters); + if (have_flag(argc, argv, "hash") || have_flag(argc, argv, "hmac")) run_benchmark("hash_hmac_sha256", bench_hmac_sha256, bench_setup, NULL, &data, 10, iters); + if (have_flag(argc, argv, "hash") || have_flag(argc, argv, "rng6979")) run_benchmark("hash_rfc6979_hmac_sha256", bench_rfc6979_hmac_sha256, bench_setup, NULL, &data, 10, iters); - if (have_flag(argc, argv, "context") || have_flag(argc, argv, "verify")) run_benchmark("context_verify", bench_context_verify, bench_setup, NULL, &data, 10, 20); - if (have_flag(argc, argv, "context") || have_flag(argc, argv, "sign")) run_benchmark("context_sign", bench_context_sign, bench_setup, NULL, &data, 10, 200); + if (have_flag(argc, argv, "context") || have_flag(argc, argv, "verify")) run_benchmark("context_verify", bench_context_verify, bench_setup, NULL, &data, 10, 1 + iters/1000); + if (have_flag(argc, argv, "context") || have_flag(argc, argv, "sign")) run_benchmark("context_sign", bench_context_sign, bench_setup, NULL, &data, 10, 1 + iters/100); #ifndef USE_NUM_NONE - if (have_flag(argc, argv, "num") || have_flag(argc, argv, "jacobi")) run_benchmark("num_jacobi", bench_num_jacobi, bench_setup, NULL, &data, 10, 200000); + if (have_flag(argc, argv, "num") || have_flag(argc, argv, "jacobi")) run_benchmark("num_jacobi", bench_num_jacobi, bench_setup, NULL, &data, 10, iters*10); #endif return 0; } diff --git a/src/bench_recover.c b/src/bench_recover.c index b806eed94e..e952ed1215 100644 --- a/src/bench_recover.c +++ b/src/bench_recover.c @@ -15,13 +15,13 @@ typedef struct { unsigned char sig[64]; } bench_recover_data; -void bench_recover(void* arg) { +void bench_recover(void* arg, int iters) { int i; bench_recover_data *data = (bench_recover_data*)arg; secp256k1_pubkey pubkey; unsigned char pubkeyc[33]; - for (i = 0; i < 20000; i++) { + for (i = 0; i < iters; i++) { int j; size_t pubkeylen = 33; secp256k1_ecdsa_recoverable_signature sig; @@ -51,9 +51,11 @@ void bench_recover_setup(void* arg) { int main(void) { bench_recover_data data; + int iters = get_iters(20000); + data.ctx = secp256k1_context_create(SECP256K1_CONTEXT_VERIFY); - run_benchmark("ecdsa_recover", bench_recover, bench_recover_setup, NULL, &data, 10, 20000); + run_benchmark("ecdsa_recover", bench_recover, bench_recover_setup, NULL, &data, 10, iters); secp256k1_context_destroy(data.ctx); return 0; diff --git a/src/bench_sign.c b/src/bench_sign.c index 544b43963c..c6b2942cc0 100644 --- a/src/bench_sign.c +++ b/src/bench_sign.c @@ -26,12 +26,12 @@ static void bench_sign_setup(void* arg) { } } -static void bench_sign_run(void* arg) { +static void bench_sign_run(void* arg, int iters) { int i; bench_sign *data = (bench_sign*)arg; unsigned char sig[74]; - for (i = 0; i < 20000; i++) { + for (i = 0; i < iters; i++) { size_t siglen = 74; int j; secp256k1_ecdsa_signature signature; @@ -47,9 +47,11 @@ static void bench_sign_run(void* arg) { int main(void) { bench_sign data; + int iters = get_iters(20000); + data.ctx = secp256k1_context_create(SECP256K1_CONTEXT_SIGN); - run_benchmark("ecdsa_sign", bench_sign_run, bench_sign_setup, NULL, &data, 10, 20000); + run_benchmark("ecdsa_sign", bench_sign_run, bench_sign_setup, NULL, &data, 10, iters); secp256k1_context_destroy(data.ctx); return 0; diff --git a/src/bench_verify.c b/src/bench_verify.c index 418defa0aa..272d3e5cc4 100644 --- a/src/bench_verify.c +++ b/src/bench_verify.c @@ -17,6 +17,7 @@ #include <openssl/obj_mac.h> #endif + typedef struct { secp256k1_context *ctx; unsigned char msg[32]; @@ -30,11 +31,11 @@ typedef struct { #endif } benchmark_verify_t; -static void benchmark_verify(void* arg) { +static void benchmark_verify(void* arg, int iters) { int i; benchmark_verify_t* data = (benchmark_verify_t*)arg; - for (i = 0; i < 20000; i++) { + for (i = 0; i < iters; i++) { secp256k1_pubkey pubkey; secp256k1_ecdsa_signature sig; data->sig[data->siglen - 1] ^= (i & 0xFF); @@ -50,11 +51,11 @@ static void benchmark_verify(void* arg) { } #ifdef ENABLE_OPENSSL_TESTS -static void benchmark_verify_openssl(void* arg) { +static void benchmark_verify_openssl(void* arg, int iters) { int i; benchmark_verify_t* data = (benchmark_verify_t*)arg; - for (i = 0; i < 20000; i++) { + for (i = 0; i < iters; i++) { data->sig[data->siglen - 1] ^= (i & 0xFF); data->sig[data->siglen - 2] ^= ((i >> 8) & 0xFF); data->sig[data->siglen - 3] ^= ((i >> 16) & 0xFF); @@ -85,6 +86,8 @@ int main(void) { secp256k1_ecdsa_signature sig; benchmark_verify_t data; + int iters = get_iters(20000); + data.ctx = secp256k1_context_create(SECP256K1_CONTEXT_SIGN | SECP256K1_CONTEXT_VERIFY); for (i = 0; i < 32; i++) { @@ -100,10 +103,10 @@ int main(void) { data.pubkeylen = 33; CHECK(secp256k1_ec_pubkey_serialize(data.ctx, data.pubkey, &data.pubkeylen, &pubkey, SECP256K1_EC_COMPRESSED) == 1); - run_benchmark("ecdsa_verify", benchmark_verify, NULL, NULL, &data, 10, 20000); + run_benchmark("ecdsa_verify", benchmark_verify, NULL, NULL, &data, 10, iters); #ifdef ENABLE_OPENSSL_TESTS data.ec_group = EC_GROUP_new_by_curve_name(NID_secp256k1); - run_benchmark("ecdsa_verify_openssl", benchmark_verify_openssl, NULL, NULL, &data, 10, 20000); + run_benchmark("ecdsa_verify_openssl", benchmark_verify_openssl, NULL, NULL, &data, 10, iters); EC_GROUP_free(data.ec_group); #endif diff --git a/src/ecdsa_impl.h b/src/ecdsa_impl.h index c3400042d8..5f54b59faa 100644 --- a/src/ecdsa_impl.h +++ b/src/ecdsa_impl.h @@ -46,68 +46,73 @@ static const secp256k1_fe secp256k1_ecdsa_const_p_minus_order = SECP256K1_FE_CON 0, 0, 0, 1, 0x45512319UL, 0x50B75FC4UL, 0x402DA172UL, 0x2FC9BAEEUL ); -static int secp256k1_der_read_len(const unsigned char **sigp, const unsigned char *sigend) { - int lenleft, b1; - size_t ret = 0; +static int secp256k1_der_read_len(size_t *len, const unsigned char **sigp, const unsigned char *sigend) { + size_t lenleft; + unsigned char b1; + VERIFY_CHECK(len != NULL); + *len = 0; if (*sigp >= sigend) { - return -1; + return 0; } b1 = *((*sigp)++); if (b1 == 0xFF) { /* X.690-0207 8.1.3.5.c the value 0xFF shall not be used. */ - return -1; + return 0; } if ((b1 & 0x80) == 0) { /* X.690-0207 8.1.3.4 short form length octets */ - return b1; + *len = b1; + return 1; } if (b1 == 0x80) { /* Indefinite length is not allowed in DER. */ - return -1; + return 0; } /* X.690-207 8.1.3.5 long form length octets */ - lenleft = b1 & 0x7F; - if (lenleft > sigend - *sigp) { - return -1; + lenleft = b1 & 0x7F; /* lenleft is at least 1 */ + if (lenleft > (size_t)(sigend - *sigp)) { + return 0; } if (**sigp == 0) { /* Not the shortest possible length encoding. */ - return -1; + return 0; } - if ((size_t)lenleft > sizeof(size_t)) { + if (lenleft > sizeof(size_t)) { /* The resulting length would exceed the range of a size_t, so * certainly longer than the passed array size. */ - return -1; + return 0; } while (lenleft > 0) { - ret = (ret << 8) | **sigp; - if (ret + lenleft > (size_t)(sigend - *sigp)) { - /* Result exceeds the length of the passed array. */ - return -1; - } + *len = (*len << 8) | **sigp; (*sigp)++; lenleft--; } - if (ret < 128) { + if (*len > (size_t)(sigend - *sigp)) { + /* Result exceeds the length of the passed array. */ + return 0; + } + if (*len < 128) { /* Not the shortest possible length encoding. */ - return -1; + return 0; } - return ret; + return 1; } static int secp256k1_der_parse_integer(secp256k1_scalar *r, const unsigned char **sig, const unsigned char *sigend) { int overflow = 0; unsigned char ra[32] = {0}; - int rlen; + size_t rlen; if (*sig == sigend || **sig != 0x02) { /* Not a primitive integer (X.690-0207 8.3.1). */ return 0; } (*sig)++; - rlen = secp256k1_der_read_len(sig, sigend); - if (rlen <= 0 || (*sig) + rlen > sigend) { + if (secp256k1_der_read_len(&rlen, sig, sigend) == 0) { + return 0; + } + if (rlen == 0 || *sig + rlen > sigend) { /* Exceeds bounds or not at least length 1 (X.690-0207 8.3.1). */ return 0; } @@ -123,8 +128,11 @@ static int secp256k1_der_parse_integer(secp256k1_scalar *r, const unsigned char /* Negative. */ overflow = 1; } - while (rlen > 0 && **sig == 0) { - /* Skip leading zero bytes */ + /* There is at most one leading zero byte: + * if there were two leading zero bytes, we would have failed and returned 0 + * because of excessive 0x00 padding already. */ + if (rlen > 0 && **sig == 0) { + /* Skip leading zero byte */ rlen--; (*sig)++; } @@ -144,18 +152,16 @@ static int secp256k1_der_parse_integer(secp256k1_scalar *r, const unsigned char static int secp256k1_ecdsa_sig_parse(secp256k1_scalar *rr, secp256k1_scalar *rs, const unsigned char *sig, size_t size) { const unsigned char *sigend = sig + size; - int rlen; + size_t rlen; if (sig == sigend || *(sig++) != 0x30) { /* The encoding doesn't start with a constructed sequence (X.690-0207 8.9.1). */ return 0; } - rlen = secp256k1_der_read_len(&sig, sigend); - if (rlen < 0 || sig + rlen > sigend) { - /* Tuple exceeds bounds */ + if (secp256k1_der_read_len(&rlen, &sig, sigend) == 0) { return 0; } - if (sig + rlen != sigend) { - /* Garbage after tuple. */ + if (rlen != (size_t)(sigend - sig)) { + /* Tuple exceeds bounds or garage after tuple. */ return 0; } @@ -274,6 +280,7 @@ static int secp256k1_ecdsa_sig_sign(const secp256k1_ecmult_gen_context *ctx, sec secp256k1_ge r; secp256k1_scalar n; int overflow = 0; + int high; secp256k1_ecmult_gen(ctx, &rp, nonce); secp256k1_ge_set_gej(&r, &rp); @@ -281,15 +288,11 @@ static int secp256k1_ecdsa_sig_sign(const secp256k1_ecmult_gen_context *ctx, sec secp256k1_fe_normalize(&r.y); secp256k1_fe_get_b32(b, &r.x); secp256k1_scalar_set_b32(sigr, b, &overflow); - /* These two conditions should be checked before calling */ - VERIFY_CHECK(!secp256k1_scalar_is_zero(sigr)); - VERIFY_CHECK(overflow == 0); - if (recid) { /* The overflow condition is cryptographically unreachable as hitting it requires finding the discrete log * of some P where P.x >= order, and only 1 in about 2^127 points meet this criteria. */ - *recid = (overflow ? 2 : 0) | (secp256k1_fe_is_odd(&r.y) ? 1 : 0); + *recid = (overflow << 1) | secp256k1_fe_is_odd(&r.y); } secp256k1_scalar_mul(&n, sigr, seckey); secp256k1_scalar_add(&n, &n, message); @@ -298,16 +301,15 @@ static int secp256k1_ecdsa_sig_sign(const secp256k1_ecmult_gen_context *ctx, sec secp256k1_scalar_clear(&n); secp256k1_gej_clear(&rp); secp256k1_ge_clear(&r); - if (secp256k1_scalar_is_zero(sigs)) { - return 0; - } - if (secp256k1_scalar_is_high(sigs)) { - secp256k1_scalar_negate(sigs, sigs); - if (recid) { - *recid ^= 1; - } + high = secp256k1_scalar_is_high(sigs); + secp256k1_scalar_cond_negate(sigs, high); + if (recid) { + *recid ^= high; } - return 1; + /* P.x = order is on the curve, so technically sig->r could end up being zero, which would be an invalid signature. + * This is cryptographically unreachable as hitting it requires finding the discrete log of P.x = N. + */ + return !secp256k1_scalar_is_zero(sigr) & !secp256k1_scalar_is_zero(sigs); } #endif /* SECP256K1_ECDSA_IMPL_H */ diff --git a/src/eckey_impl.h b/src/eckey_impl.h index 7c5b789325..e2e72d9303 100644 --- a/src/eckey_impl.h +++ b/src/eckey_impl.h @@ -54,10 +54,7 @@ static int secp256k1_eckey_pubkey_serialize(secp256k1_ge *elem, unsigned char *p static int secp256k1_eckey_privkey_tweak_add(secp256k1_scalar *key, const secp256k1_scalar *tweak) { secp256k1_scalar_add(key, key, tweak); - if (secp256k1_scalar_is_zero(key)) { - return 0; - } - return 1; + return !secp256k1_scalar_is_zero(key); } static int secp256k1_eckey_pubkey_tweak_add(const secp256k1_ecmult_context *ctx, secp256k1_ge *key, const secp256k1_scalar *tweak) { @@ -75,12 +72,11 @@ static int secp256k1_eckey_pubkey_tweak_add(const secp256k1_ecmult_context *ctx, } static int secp256k1_eckey_privkey_tweak_mul(secp256k1_scalar *key, const secp256k1_scalar *tweak) { - if (secp256k1_scalar_is_zero(tweak)) { - return 0; - } + int ret; + ret = !secp256k1_scalar_is_zero(tweak); secp256k1_scalar_mul(key, key, tweak); - return 1; + return ret; } static int secp256k1_eckey_pubkey_tweak_mul(const secp256k1_ecmult_context *ctx, secp256k1_ge *key, const secp256k1_scalar *tweak) { diff --git a/src/ecmult.h b/src/ecmult.h index 3d75a960f4..c9b198239d 100644 --- a/src/ecmult.h +++ b/src/ecmult.h @@ -20,10 +20,10 @@ typedef struct { #endif } secp256k1_ecmult_context; +static const size_t SECP256K1_ECMULT_CONTEXT_PREALLOCATED_SIZE; static void secp256k1_ecmult_context_init(secp256k1_ecmult_context *ctx); -static void secp256k1_ecmult_context_build(secp256k1_ecmult_context *ctx, const secp256k1_callback *cb); -static void secp256k1_ecmult_context_clone(secp256k1_ecmult_context *dst, - const secp256k1_ecmult_context *src, const secp256k1_callback *cb); +static void secp256k1_ecmult_context_build(secp256k1_ecmult_context *ctx, void **prealloc); +static void secp256k1_ecmult_context_finalize_memcpy(secp256k1_ecmult_context *dst, const secp256k1_ecmult_context *src); static void secp256k1_ecmult_context_clear(secp256k1_ecmult_context *ctx); static int secp256k1_ecmult_context_is_built(const secp256k1_ecmult_context *ctx); @@ -43,6 +43,6 @@ typedef int (secp256k1_ecmult_multi_callback)(secp256k1_scalar *sc, secp256k1_ge * 0 if there is not enough scratch space for a single point or * callback returns 0 */ -static int secp256k1_ecmult_multi_var(const secp256k1_ecmult_context *ctx, secp256k1_scratch *scratch, secp256k1_gej *r, const secp256k1_scalar *inp_g_sc, secp256k1_ecmult_multi_callback cb, void *cbdata, size_t n); +static int secp256k1_ecmult_multi_var(const secp256k1_callback* error_callback, const secp256k1_ecmult_context *ctx, secp256k1_scratch *scratch, secp256k1_gej *r, const secp256k1_scalar *inp_g_sc, secp256k1_ecmult_multi_callback cb, void *cbdata, size_t n); #endif /* SECP256K1_ECMULT_H */ diff --git a/src/ecmult_const.h b/src/ecmult_const.h index d4804b8b68..03bb33257d 100644 --- a/src/ecmult_const.h +++ b/src/ecmult_const.h @@ -10,8 +10,11 @@ #include "scalar.h" #include "group.h" -/* Here `bits` should be set to the maximum bitlength of the _absolute value_ of `q`, plus - * one because we internally sometimes add 2 to the number during the WNAF conversion. */ +/** + * Multiply: R = q*A (in constant-time) + * Here `bits` should be set to the maximum bitlength of the _absolute value_ of `q`, plus + * one because we internally sometimes add 2 to the number during the WNAF conversion. + */ static void secp256k1_ecmult_const(secp256k1_gej *r, const secp256k1_ge *a, const secp256k1_scalar *q, int bits); #endif /* SECP256K1_ECMULT_CONST_H */ diff --git a/src/ecmult_const_impl.h b/src/ecmult_const_impl.h index 8411752eb0..6d6d354aa4 100644 --- a/src/ecmult_const_impl.h +++ b/src/ecmult_const_impl.h @@ -14,16 +14,22 @@ /* This is like `ECMULT_TABLE_GET_GE` but is constant time */ #define ECMULT_CONST_TABLE_GET_GE(r,pre,n,w) do { \ - int m; \ - int abs_n = (n) * (((n) > 0) * 2 - 1); \ - int idx_n = abs_n / 2; \ + int m = 0; \ + /* Extract the sign-bit for a constant time absolute-value. */ \ + int mask = (n) >> (sizeof(n) * CHAR_BIT - 1); \ + int abs_n = ((n) + mask) ^ mask; \ + int idx_n = abs_n >> 1; \ secp256k1_fe neg_y; \ VERIFY_CHECK(((n) & 1) == 1); \ VERIFY_CHECK((n) >= -((1 << ((w)-1)) - 1)); \ VERIFY_CHECK((n) <= ((1 << ((w)-1)) - 1)); \ VERIFY_SETUP(secp256k1_fe_clear(&(r)->x)); \ VERIFY_SETUP(secp256k1_fe_clear(&(r)->y)); \ - for (m = 0; m < ECMULT_TABLE_SIZE(w); m++) { \ + /* Unconditionally set r->x = (pre)[m].x. r->y = (pre)[m].y. because it's either the correct one \ + * or will get replaced in the later iterations, this is needed to make sure `r` is initialized. */ \ + (r)->x = (pre)[m].x; \ + (r)->y = (pre)[m].y; \ + for (m = 1; m < ECMULT_TABLE_SIZE(w); m++) { \ /* This loop is used to avoid secret data in array indices. See * the comment in ecmult_gen_impl.h for rationale. */ \ secp256k1_fe_cmov(&(r)->x, &(pre)[m].x, m == idx_n); \ @@ -44,11 +50,11 @@ * * Adapted from `The Width-w NAF Method Provides Small Memory and Fast Elliptic Scalar * Multiplications Secure against Side Channel Attacks`, Okeya and Tagaki. M. Joye (Ed.) - * CT-RSA 2003, LNCS 2612, pp. 328-443, 2003. Springer-Verlagy Berlin Heidelberg 2003 + * CT-RSA 2003, LNCS 2612, pp. 328-443, 2003. Springer-Verlag Berlin Heidelberg 2003 * * Numbers reference steps of `Algorithm SPA-resistant Width-w NAF with Odd Scalar` on pp. 335 */ -static int secp256k1_wnaf_const(int *wnaf, secp256k1_scalar s, int w, int size) { +static int secp256k1_wnaf_const(int *wnaf, const secp256k1_scalar *scalar, int w, int size) { int global_sign; int skew = 0; int word = 0; @@ -59,8 +65,12 @@ static int secp256k1_wnaf_const(int *wnaf, secp256k1_scalar s, int w, int size) int flip; int bit; - secp256k1_scalar neg_s; + secp256k1_scalar s; int not_neg_one; + + VERIFY_CHECK(w > 0); + VERIFY_CHECK(size > 0); + /* Note that we cannot handle even numbers by negating them to be odd, as is * done in other implementations, since if our scalars were specified to have * width < 256 for performance reasons, their negations would have width 256 @@ -75,12 +85,13 @@ static int secp256k1_wnaf_const(int *wnaf, secp256k1_scalar s, int w, int size) * {1, 2} we want to add to the scalar when ensuring that it's odd. Further * complicating things, -1 interacts badly with `secp256k1_scalar_cadd_bit` and * we need to special-case it in this logic. */ - flip = secp256k1_scalar_is_high(&s); + flip = secp256k1_scalar_is_high(scalar); /* We add 1 to even numbers, 2 to odd ones, noting that negation flips parity */ - bit = flip ^ !secp256k1_scalar_is_even(&s); + bit = flip ^ !secp256k1_scalar_is_even(scalar); /* We check for negative one, since adding 2 to it will cause an overflow */ - secp256k1_scalar_negate(&neg_s, &s); - not_neg_one = !secp256k1_scalar_is_one(&neg_s); + secp256k1_scalar_negate(&s, scalar); + not_neg_one = !secp256k1_scalar_is_one(&s); + s = *scalar; secp256k1_scalar_cadd_bit(&s, bit, not_neg_one); /* If we had negative one, flip == 1, s.d[0] == 0, bit == 1, so caller expects * that we added two to it and flipped it. In fact for -1 these operations are @@ -93,7 +104,7 @@ static int secp256k1_wnaf_const(int *wnaf, secp256k1_scalar s, int w, int size) /* 4 */ u_last = secp256k1_scalar_shr_int(&s, w); - while (word * w < size) { + do { int sign; int even; @@ -109,7 +120,7 @@ static int secp256k1_wnaf_const(int *wnaf, secp256k1_scalar s, int w, int size) wnaf[word++] = u_last * global_sign; u_last = u; - } + } while (word * w < size); wnaf[word] = u * global_sign; VERIFY_CHECK(secp256k1_scalar_is_zero(&s)); @@ -132,7 +143,6 @@ static void secp256k1_ecmult_const(secp256k1_gej *r, const secp256k1_ge *a, cons int wnaf_1[1 + WNAF_SIZE(WINDOW_A - 1)]; int i; - secp256k1_scalar sc = *scalar; /* build wnaf representation for q. */ int rsize = size; @@ -140,13 +150,13 @@ static void secp256k1_ecmult_const(secp256k1_gej *r, const secp256k1_ge *a, cons if (size > 128) { rsize = 128; /* split q into q_1 and q_lam (where q = q_1 + q_lam*lambda, and q_1 and q_lam are ~128 bit) */ - secp256k1_scalar_split_lambda(&q_1, &q_lam, &sc); - skew_1 = secp256k1_wnaf_const(wnaf_1, q_1, WINDOW_A - 1, 128); - skew_lam = secp256k1_wnaf_const(wnaf_lam, q_lam, WINDOW_A - 1, 128); + secp256k1_scalar_split_lambda(&q_1, &q_lam, scalar); + skew_1 = secp256k1_wnaf_const(wnaf_1, &q_1, WINDOW_A - 1, 128); + skew_lam = secp256k1_wnaf_const(wnaf_lam, &q_lam, WINDOW_A - 1, 128); } else #endif { - skew_1 = secp256k1_wnaf_const(wnaf_1, sc, WINDOW_A - 1, size); + skew_1 = secp256k1_wnaf_const(wnaf_1, scalar, WINDOW_A - 1, size); #ifdef USE_ENDOMORPHISM skew_lam = 0; #endif @@ -168,6 +178,7 @@ static void secp256k1_ecmult_const(secp256k1_gej *r, const secp256k1_ge *a, cons for (i = 0; i < ECMULT_TABLE_SIZE(WINDOW_A); i++) { secp256k1_ge_mul_lambda(&pre_a_lam[i], &pre_a[i]); } + } #endif @@ -191,7 +202,7 @@ static void secp256k1_ecmult_const(secp256k1_gej *r, const secp256k1_ge *a, cons int n; int j; for (j = 0; j < WINDOW_A - 1; ++j) { - secp256k1_gej_double_nonzero(r, r, NULL); + secp256k1_gej_double_nonzero(r, r); } n = wnaf_1[i]; diff --git a/src/ecmult_gen.h b/src/ecmult_gen.h index 7564b7015f..30815e5aa1 100644 --- a/src/ecmult_gen.h +++ b/src/ecmult_gen.h @@ -10,28 +10,35 @@ #include "scalar.h" #include "group.h" +#if ECMULT_GEN_PREC_BITS != 2 && ECMULT_GEN_PREC_BITS != 4 && ECMULT_GEN_PREC_BITS != 8 +# error "Set ECMULT_GEN_PREC_BITS to 2, 4 or 8." +#endif +#define ECMULT_GEN_PREC_B ECMULT_GEN_PREC_BITS +#define ECMULT_GEN_PREC_G (1 << ECMULT_GEN_PREC_B) +#define ECMULT_GEN_PREC_N (256 / ECMULT_GEN_PREC_B) + typedef struct { /* For accelerating the computation of a*G: * To harden against timing attacks, use the following mechanism: - * * Break up the multiplicand into groups of 4 bits, called n_0, n_1, n_2, ..., n_63. - * * Compute sum(n_i * 16^i * G + U_i, i=0..63), where: - * * U_i = U * 2^i (for i=0..62) - * * U_i = U * (1-2^63) (for i=63) - * where U is a point with no known corresponding scalar. Note that sum(U_i, i=0..63) = 0. - * For each i, and each of the 16 possible values of n_i, (n_i * 16^i * G + U_i) is - * precomputed (call it prec(i, n_i)). The formula now becomes sum(prec(i, n_i), i=0..63). + * * Break up the multiplicand into groups of PREC_B bits, called n_0, n_1, n_2, ..., n_(PREC_N-1). + * * Compute sum(n_i * (PREC_G)^i * G + U_i, i=0 ... PREC_N-1), where: + * * U_i = U * 2^i, for i=0 ... PREC_N-2 + * * U_i = U * (1-2^(PREC_N-1)), for i=PREC_N-1 + * where U is a point with no known corresponding scalar. Note that sum(U_i, i=0 ... PREC_N-1) = 0. + * For each i, and each of the PREC_G possible values of n_i, (n_i * (PREC_G)^i * G + U_i) is + * precomputed (call it prec(i, n_i)). The formula now becomes sum(prec(i, n_i), i=0 ... PREC_N-1). * None of the resulting prec group elements have a known scalar, and neither do any of * the intermediate sums while computing a*G. */ - secp256k1_ge_storage (*prec)[64][16]; /* prec[j][i] = 16^j * i * G + U_i */ + secp256k1_ge_storage (*prec)[ECMULT_GEN_PREC_N][ECMULT_GEN_PREC_G]; /* prec[j][i] = (PREC_G)^j * i * G + U_i */ secp256k1_scalar blind; secp256k1_gej initial; } secp256k1_ecmult_gen_context; +static const size_t SECP256K1_ECMULT_GEN_CONTEXT_PREALLOCATED_SIZE; static void secp256k1_ecmult_gen_context_init(secp256k1_ecmult_gen_context* ctx); -static void secp256k1_ecmult_gen_context_build(secp256k1_ecmult_gen_context* ctx, const secp256k1_callback* cb); -static void secp256k1_ecmult_gen_context_clone(secp256k1_ecmult_gen_context *dst, - const secp256k1_ecmult_gen_context* src, const secp256k1_callback* cb); +static void secp256k1_ecmult_gen_context_build(secp256k1_ecmult_gen_context* ctx, void **prealloc); +static void secp256k1_ecmult_gen_context_finalize_memcpy(secp256k1_ecmult_gen_context *dst, const secp256k1_ecmult_gen_context* src); static void secp256k1_ecmult_gen_context_clear(secp256k1_ecmult_gen_context* ctx); static int secp256k1_ecmult_gen_context_is_built(const secp256k1_ecmult_gen_context* ctx); diff --git a/src/ecmult_gen_impl.h b/src/ecmult_gen_impl.h index d64505dc00..30ac16518b 100644 --- a/src/ecmult_gen_impl.h +++ b/src/ecmult_gen_impl.h @@ -7,6 +7,7 @@ #ifndef SECP256K1_ECMULT_GEN_IMPL_H #define SECP256K1_ECMULT_GEN_IMPL_H +#include "util.h" #include "scalar.h" #include "group.h" #include "ecmult_gen.h" @@ -14,23 +15,32 @@ #ifdef USE_ECMULT_STATIC_PRECOMPUTATION #include "ecmult_static_context.h" #endif + +#ifndef USE_ECMULT_STATIC_PRECOMPUTATION + static const size_t SECP256K1_ECMULT_GEN_CONTEXT_PREALLOCATED_SIZE = ROUND_TO_ALIGN(sizeof(*((secp256k1_ecmult_gen_context*) NULL)->prec)); +#else + static const size_t SECP256K1_ECMULT_GEN_CONTEXT_PREALLOCATED_SIZE = 0; +#endif + static void secp256k1_ecmult_gen_context_init(secp256k1_ecmult_gen_context *ctx) { ctx->prec = NULL; } -static void secp256k1_ecmult_gen_context_build(secp256k1_ecmult_gen_context *ctx, const secp256k1_callback* cb) { +static void secp256k1_ecmult_gen_context_build(secp256k1_ecmult_gen_context *ctx, void **prealloc) { #ifndef USE_ECMULT_STATIC_PRECOMPUTATION - secp256k1_ge prec[1024]; + secp256k1_ge prec[ECMULT_GEN_PREC_N * ECMULT_GEN_PREC_G]; secp256k1_gej gj; secp256k1_gej nums_gej; int i, j; + size_t const prealloc_size = SECP256K1_ECMULT_GEN_CONTEXT_PREALLOCATED_SIZE; + void* const base = *prealloc; #endif if (ctx->prec != NULL) { return; } #ifndef USE_ECMULT_STATIC_PRECOMPUTATION - ctx->prec = (secp256k1_ge_storage (*)[64][16])checked_malloc(cb, sizeof(*ctx->prec)); + ctx->prec = (secp256k1_ge_storage (*)[ECMULT_GEN_PREC_N][ECMULT_GEN_PREC_G])manual_alloc(prealloc, prealloc_size, base, prealloc_size); /* get the generator */ secp256k1_gej_set_ge(&gj, &secp256k1_ge_const_g); @@ -54,39 +64,39 @@ static void secp256k1_ecmult_gen_context_build(secp256k1_ecmult_gen_context *ctx /* compute prec. */ { - secp256k1_gej precj[1024]; /* Jacobian versions of prec. */ + secp256k1_gej precj[ECMULT_GEN_PREC_N * ECMULT_GEN_PREC_G]; /* Jacobian versions of prec. */ secp256k1_gej gbase; secp256k1_gej numsbase; - gbase = gj; /* 16^j * G */ + gbase = gj; /* PREC_G^j * G */ numsbase = nums_gej; /* 2^j * nums. */ - for (j = 0; j < 64; j++) { - /* Set precj[j*16 .. j*16+15] to (numsbase, numsbase + gbase, ..., numsbase + 15*gbase). */ - precj[j*16] = numsbase; - for (i = 1; i < 16; i++) { - secp256k1_gej_add_var(&precj[j*16 + i], &precj[j*16 + i - 1], &gbase, NULL); + for (j = 0; j < ECMULT_GEN_PREC_N; j++) { + /* Set precj[j*PREC_G .. j*PREC_G+(PREC_G-1)] to (numsbase, numsbase + gbase, ..., numsbase + (PREC_G-1)*gbase). */ + precj[j*ECMULT_GEN_PREC_G] = numsbase; + for (i = 1; i < ECMULT_GEN_PREC_G; i++) { + secp256k1_gej_add_var(&precj[j*ECMULT_GEN_PREC_G + i], &precj[j*ECMULT_GEN_PREC_G + i - 1], &gbase, NULL); } - /* Multiply gbase by 16. */ - for (i = 0; i < 4; i++) { + /* Multiply gbase by PREC_G. */ + for (i = 0; i < ECMULT_GEN_PREC_B; i++) { secp256k1_gej_double_var(&gbase, &gbase, NULL); } /* Multiply numbase by 2. */ secp256k1_gej_double_var(&numsbase, &numsbase, NULL); - if (j == 62) { + if (j == ECMULT_GEN_PREC_N - 2) { /* In the last iteration, numsbase is (1 - 2^j) * nums instead. */ secp256k1_gej_neg(&numsbase, &numsbase); secp256k1_gej_add_var(&numsbase, &numsbase, &nums_gej, NULL); } } - secp256k1_ge_set_all_gej_var(prec, precj, 1024); + secp256k1_ge_set_all_gej_var(prec, precj, ECMULT_GEN_PREC_N * ECMULT_GEN_PREC_G); } - for (j = 0; j < 64; j++) { - for (i = 0; i < 16; i++) { - secp256k1_ge_to_storage(&(*ctx->prec)[j][i], &prec[j*16 + i]); + for (j = 0; j < ECMULT_GEN_PREC_N; j++) { + for (i = 0; i < ECMULT_GEN_PREC_G; i++) { + secp256k1_ge_to_storage(&(*ctx->prec)[j][i], &prec[j*ECMULT_GEN_PREC_G + i]); } } #else - (void)cb; - ctx->prec = (secp256k1_ge_storage (*)[64][16])secp256k1_ecmult_static_context; + (void)prealloc; + ctx->prec = (secp256k1_ge_storage (*)[ECMULT_GEN_PREC_N][ECMULT_GEN_PREC_G])secp256k1_ecmult_static_context; #endif secp256k1_ecmult_gen_blind(ctx, NULL); } @@ -95,27 +105,18 @@ static int secp256k1_ecmult_gen_context_is_built(const secp256k1_ecmult_gen_cont return ctx->prec != NULL; } -static void secp256k1_ecmult_gen_context_clone(secp256k1_ecmult_gen_context *dst, - const secp256k1_ecmult_gen_context *src, const secp256k1_callback* cb) { - if (src->prec == NULL) { - dst->prec = NULL; - } else { +static void secp256k1_ecmult_gen_context_finalize_memcpy(secp256k1_ecmult_gen_context *dst, const secp256k1_ecmult_gen_context *src) { #ifndef USE_ECMULT_STATIC_PRECOMPUTATION - dst->prec = (secp256k1_ge_storage (*)[64][16])checked_malloc(cb, sizeof(*dst->prec)); - memcpy(dst->prec, src->prec, sizeof(*dst->prec)); + if (src->prec != NULL) { + /* We cast to void* first to suppress a -Wcast-align warning. */ + dst->prec = (secp256k1_ge_storage (*)[ECMULT_GEN_PREC_N][ECMULT_GEN_PREC_G])(void*)((unsigned char*)dst + ((unsigned char*)src->prec - (unsigned char*)src)); + } #else - (void)cb; - dst->prec = src->prec; + (void)dst, (void)src; #endif - dst->initial = src->initial; - dst->blind = src->blind; - } } static void secp256k1_ecmult_gen_context_clear(secp256k1_ecmult_gen_context *ctx) { -#ifndef USE_ECMULT_STATIC_PRECOMPUTATION - free(ctx->prec); -#endif secp256k1_scalar_clear(&ctx->blind); secp256k1_gej_clear(&ctx->initial); ctx->prec = NULL; @@ -132,9 +133,9 @@ static void secp256k1_ecmult_gen(const secp256k1_ecmult_gen_context *ctx, secp25 /* Blind scalar/point multiplication by computing (n-b)G + bG instead of nG. */ secp256k1_scalar_add(&gnb, gn, &ctx->blind); add.infinity = 0; - for (j = 0; j < 64; j++) { - bits = secp256k1_scalar_get_bits(&gnb, j * 4, 4); - for (i = 0; i < 16; i++) { + for (j = 0; j < ECMULT_GEN_PREC_N; j++) { + bits = secp256k1_scalar_get_bits(&gnb, j * ECMULT_GEN_PREC_B, ECMULT_GEN_PREC_B); + for (i = 0; i < ECMULT_GEN_PREC_G; i++) { /** This uses a conditional move to avoid any secret data in array indexes. * _Any_ use of secret indexes has been demonstrated to result in timing * sidechannels, even when the cache-line access patterns are uniform. @@ -162,7 +163,7 @@ static void secp256k1_ecmult_gen_blind(secp256k1_ecmult_gen_context *ctx, const secp256k1_fe s; unsigned char nonce32[32]; secp256k1_rfc6979_hmac_sha256 rng; - int retry; + int overflow; unsigned char keydata[64] = {0}; if (seed32 == NULL) { /* When seed is NULL, reset the initial point and blinding value. */ @@ -182,21 +183,18 @@ static void secp256k1_ecmult_gen_blind(secp256k1_ecmult_gen_context *ctx, const } secp256k1_rfc6979_hmac_sha256_initialize(&rng, keydata, seed32 ? 64 : 32); memset(keydata, 0, sizeof(keydata)); - /* Retry for out of range results to achieve uniformity. */ - do { - secp256k1_rfc6979_hmac_sha256_generate(&rng, nonce32, 32); - retry = !secp256k1_fe_set_b32(&s, nonce32); - retry |= secp256k1_fe_is_zero(&s); - } while (retry); /* This branch true is cryptographically unreachable. Requires sha256_hmac output > Fp. */ + /* Accept unobservably small non-uniformity. */ + secp256k1_rfc6979_hmac_sha256_generate(&rng, nonce32, 32); + overflow = !secp256k1_fe_set_b32(&s, nonce32); + overflow |= secp256k1_fe_is_zero(&s); + secp256k1_fe_cmov(&s, &secp256k1_fe_one, overflow); /* Randomize the projection to defend against multiplier sidechannels. */ secp256k1_gej_rescale(&ctx->initial, &s); secp256k1_fe_clear(&s); - do { - secp256k1_rfc6979_hmac_sha256_generate(&rng, nonce32, 32); - secp256k1_scalar_set_b32(&b, nonce32, &retry); - /* A blinding value of 0 works, but would undermine the projection hardening. */ - retry |= secp256k1_scalar_is_zero(&b); - } while (retry); /* This branch true is cryptographically unreachable. Requires sha256_hmac output > order. */ + secp256k1_rfc6979_hmac_sha256_generate(&rng, nonce32, 32); + secp256k1_scalar_set_b32(&b, nonce32, NULL); + /* A blinding value of 0 works, but would undermine the projection hardening. */ + secp256k1_scalar_cmov(&b, &secp256k1_scalar_one, secp256k1_scalar_is_zero(&b)); secp256k1_rfc6979_hmac_sha256_finalize(&rng); memset(nonce32, 0, 32); secp256k1_ecmult_gen(ctx, &gb, &b); diff --git a/src/ecmult_impl.h b/src/ecmult_impl.h index 1986914a4f..f03fa9469d 100644 --- a/src/ecmult_impl.h +++ b/src/ecmult_impl.h @@ -10,6 +10,7 @@ #include <string.h> #include <stdint.h> +#include "util.h" #include "group.h" #include "scalar.h" #include "ecmult.h" @@ -30,16 +31,32 @@ # endif #else /* optimal for 128-bit and 256-bit exponents. */ -#define WINDOW_A 5 -/** larger numbers may result in slightly better performance, at the cost of - exponentially larger precomputed tables. */ -#ifdef USE_ENDOMORPHISM -/** Two tables for window size 15: 1.375 MiB. */ -#define WINDOW_G 15 -#else -/** One table for window size 16: 1.375 MiB. */ -#define WINDOW_G 16 +# define WINDOW_A 5 +/** Larger values for ECMULT_WINDOW_SIZE result in possibly better + * performance at the cost of an exponentially larger precomputed + * table. The exact table size is + * (1 << (WINDOW_G - 2)) * sizeof(secp256k1_ge_storage) bytes, + * where sizeof(secp256k1_ge_storage) is typically 64 bytes but can + * be larger due to platform-specific padding and alignment. + * If the endomorphism optimization is enabled (USE_ENDOMORMPHSIM) + * two tables of this size are used instead of only one. + */ +# define WINDOW_G ECMULT_WINDOW_SIZE #endif + +/* Noone will ever need more than a window size of 24. The code might + * be correct for larger values of ECMULT_WINDOW_SIZE but this is not + * not tested. + * + * The following limitations are known, and there are probably more: + * If WINDOW_G > 27 and size_t has 32 bits, then the code is incorrect + * because the size of the memory object that we allocate (in bytes) + * will not fit in a size_t. + * If WINDOW_G > 31 and int has 32 bits, then the code is incorrect + * because certain expressions will overflow. + */ +#if ECMULT_WINDOW_SIZE < 2 || ECMULT_WINDOW_SIZE > 24 +# error Set ECMULT_WINDOW_SIZE to an integer in range [2..24]. #endif #ifdef USE_ENDOMORPHISM @@ -121,7 +138,7 @@ static void secp256k1_ecmult_odd_multiples_table(int n, secp256k1_gej *prej, sec * It only operates on tables sized for WINDOW_A wnaf multiples. * - secp256k1_ecmult_odd_multiples_table_storage_var, which converts its * resulting point set to actually affine points, and stores those in pre. - * It operates on tables of any size, but uses heap-allocated temporaries. + * It operates on tables of any size. * * To compute a*P + b*G, we compute a table for P using the first function, * and for G using the second (which requires an inverse, but it only needs to @@ -294,6 +311,13 @@ static void secp256k1_ecmult_odd_multiples_table_storage_var(const int n, secp25 } \ } while(0) +static const size_t SECP256K1_ECMULT_CONTEXT_PREALLOCATED_SIZE = + ROUND_TO_ALIGN(sizeof((*((secp256k1_ecmult_context*) NULL)->pre_g)[0]) * ECMULT_TABLE_SIZE(WINDOW_G)) +#ifdef USE_ENDOMORPHISM + + ROUND_TO_ALIGN(sizeof((*((secp256k1_ecmult_context*) NULL)->pre_g_128)[0]) * ECMULT_TABLE_SIZE(WINDOW_G)) +#endif + ; + static void secp256k1_ecmult_context_init(secp256k1_ecmult_context *ctx) { ctx->pre_g = NULL; #ifdef USE_ENDOMORPHISM @@ -301,8 +325,10 @@ static void secp256k1_ecmult_context_init(secp256k1_ecmult_context *ctx) { #endif } -static void secp256k1_ecmult_context_build(secp256k1_ecmult_context *ctx, const secp256k1_callback *cb) { +static void secp256k1_ecmult_context_build(secp256k1_ecmult_context *ctx, void **prealloc) { secp256k1_gej gj; + void* const base = *prealloc; + size_t const prealloc_size = SECP256K1_ECMULT_CONTEXT_PREALLOCATED_SIZE; if (ctx->pre_g != NULL) { return; @@ -311,7 +337,12 @@ static void secp256k1_ecmult_context_build(secp256k1_ecmult_context *ctx, const /* get the generator */ secp256k1_gej_set_ge(&gj, &secp256k1_ge_const_g); - ctx->pre_g = (secp256k1_ge_storage (*)[])checked_malloc(cb, sizeof((*ctx->pre_g)[0]) * ECMULT_TABLE_SIZE(WINDOW_G)); + { + size_t size = sizeof((*ctx->pre_g)[0]) * ((size_t)ECMULT_TABLE_SIZE(WINDOW_G)); + /* check for overflow */ + VERIFY_CHECK(size / sizeof((*ctx->pre_g)[0]) == ((size_t)ECMULT_TABLE_SIZE(WINDOW_G))); + ctx->pre_g = (secp256k1_ge_storage (*)[])manual_alloc(prealloc, sizeof((*ctx->pre_g)[0]) * ECMULT_TABLE_SIZE(WINDOW_G), base, prealloc_size); + } /* precompute the tables with odd multiples */ secp256k1_ecmult_odd_multiples_table_storage_var(ECMULT_TABLE_SIZE(WINDOW_G), *ctx->pre_g, &gj); @@ -321,7 +352,10 @@ static void secp256k1_ecmult_context_build(secp256k1_ecmult_context *ctx, const secp256k1_gej g_128j; int i; - ctx->pre_g_128 = (secp256k1_ge_storage (*)[])checked_malloc(cb, sizeof((*ctx->pre_g_128)[0]) * ECMULT_TABLE_SIZE(WINDOW_G)); + size_t size = sizeof((*ctx->pre_g_128)[0]) * ((size_t) ECMULT_TABLE_SIZE(WINDOW_G)); + /* check for overflow */ + VERIFY_CHECK(size / sizeof((*ctx->pre_g_128)[0]) == ((size_t)ECMULT_TABLE_SIZE(WINDOW_G))); + ctx->pre_g_128 = (secp256k1_ge_storage (*)[])manual_alloc(prealloc, sizeof((*ctx->pre_g_128)[0]) * ECMULT_TABLE_SIZE(WINDOW_G), base, prealloc_size); /* calculate 2^128*generator */ g_128j = gj; @@ -333,22 +367,14 @@ static void secp256k1_ecmult_context_build(secp256k1_ecmult_context *ctx, const #endif } -static void secp256k1_ecmult_context_clone(secp256k1_ecmult_context *dst, - const secp256k1_ecmult_context *src, const secp256k1_callback *cb) { - if (src->pre_g == NULL) { - dst->pre_g = NULL; - } else { - size_t size = sizeof((*dst->pre_g)[0]) * ECMULT_TABLE_SIZE(WINDOW_G); - dst->pre_g = (secp256k1_ge_storage (*)[])checked_malloc(cb, size); - memcpy(dst->pre_g, src->pre_g, size); +static void secp256k1_ecmult_context_finalize_memcpy(secp256k1_ecmult_context *dst, const secp256k1_ecmult_context *src) { + if (src->pre_g != NULL) { + /* We cast to void* first to suppress a -Wcast-align warning. */ + dst->pre_g = (secp256k1_ge_storage (*)[])(void*)((unsigned char*)dst + ((unsigned char*)(src->pre_g) - (unsigned char*)src)); } #ifdef USE_ENDOMORPHISM - if (src->pre_g_128 == NULL) { - dst->pre_g_128 = NULL; - } else { - size_t size = sizeof((*dst->pre_g_128)[0]) * ECMULT_TABLE_SIZE(WINDOW_G); - dst->pre_g_128 = (secp256k1_ge_storage (*)[])checked_malloc(cb, size); - memcpy(dst->pre_g_128, src->pre_g_128, size); + if (src->pre_g_128 != NULL) { + dst->pre_g_128 = (secp256k1_ge_storage (*)[])(void*)((unsigned char*)dst + ((unsigned char*)(src->pre_g_128) - (unsigned char*)src)); } #endif } @@ -358,10 +384,6 @@ static int secp256k1_ecmult_context_is_built(const secp256k1_ecmult_context *ctx } static void secp256k1_ecmult_context_clear(secp256k1_ecmult_context *ctx) { - free(ctx->pre_g); -#ifdef USE_ENDOMORPHISM - free(ctx->pre_g_128); -#endif secp256k1_ecmult_context_init(ctx); } @@ -373,7 +395,7 @@ static void secp256k1_ecmult_context_clear(secp256k1_ecmult_context *ctx) { * than the number of bits in the (absolute value) of the input. */ static int secp256k1_ecmult_wnaf(int *wnaf, int len, const secp256k1_scalar *a, int w) { - secp256k1_scalar s = *a; + secp256k1_scalar s; int last_set_bit = -1; int bit = 0; int sign = 1; @@ -386,6 +408,7 @@ static int secp256k1_ecmult_wnaf(int *wnaf, int len, const secp256k1_scalar *a, memset(wnaf, 0, len * sizeof(wnaf[0])); + s = *a; if (secp256k1_scalar_get_bits(&s, 255, 1)) { secp256k1_scalar_negate(&s, &s); sign = -1; @@ -418,7 +441,7 @@ static int secp256k1_ecmult_wnaf(int *wnaf, int len, const secp256k1_scalar *a, CHECK(carry == 0); while (bit < 256) { CHECK(secp256k1_scalar_get_bits(&s, bit++, 1) == 0); - } + } #endif return last_set_bit + 1; } @@ -626,52 +649,55 @@ static size_t secp256k1_strauss_scratch_size(size_t n_points) { return n_points*point_size; } -static int secp256k1_ecmult_strauss_batch(const secp256k1_ecmult_context *ctx, secp256k1_scratch *scratch, secp256k1_gej *r, const secp256k1_scalar *inp_g_sc, secp256k1_ecmult_multi_callback cb, void *cbdata, size_t n_points, size_t cb_offset) { +static int secp256k1_ecmult_strauss_batch(const secp256k1_callback* error_callback, const secp256k1_ecmult_context *ctx, secp256k1_scratch *scratch, secp256k1_gej *r, const secp256k1_scalar *inp_g_sc, secp256k1_ecmult_multi_callback cb, void *cbdata, size_t n_points, size_t cb_offset) { secp256k1_gej* points; secp256k1_scalar* scalars; struct secp256k1_strauss_state state; size_t i; + const size_t scratch_checkpoint = secp256k1_scratch_checkpoint(error_callback, scratch); secp256k1_gej_set_infinity(r); if (inp_g_sc == NULL && n_points == 0) { return 1; } - if (!secp256k1_scratch_allocate_frame(scratch, secp256k1_strauss_scratch_size(n_points), STRAUSS_SCRATCH_OBJECTS)) { - return 0; - } - points = (secp256k1_gej*)secp256k1_scratch_alloc(scratch, n_points * sizeof(secp256k1_gej)); - scalars = (secp256k1_scalar*)secp256k1_scratch_alloc(scratch, n_points * sizeof(secp256k1_scalar)); - state.prej = (secp256k1_gej*)secp256k1_scratch_alloc(scratch, n_points * ECMULT_TABLE_SIZE(WINDOW_A) * sizeof(secp256k1_gej)); - state.zr = (secp256k1_fe*)secp256k1_scratch_alloc(scratch, n_points * ECMULT_TABLE_SIZE(WINDOW_A) * sizeof(secp256k1_fe)); + points = (secp256k1_gej*)secp256k1_scratch_alloc(error_callback, scratch, n_points * sizeof(secp256k1_gej)); + scalars = (secp256k1_scalar*)secp256k1_scratch_alloc(error_callback, scratch, n_points * sizeof(secp256k1_scalar)); + state.prej = (secp256k1_gej*)secp256k1_scratch_alloc(error_callback, scratch, n_points * ECMULT_TABLE_SIZE(WINDOW_A) * sizeof(secp256k1_gej)); + state.zr = (secp256k1_fe*)secp256k1_scratch_alloc(error_callback, scratch, n_points * ECMULT_TABLE_SIZE(WINDOW_A) * sizeof(secp256k1_fe)); #ifdef USE_ENDOMORPHISM - state.pre_a = (secp256k1_ge*)secp256k1_scratch_alloc(scratch, n_points * 2 * ECMULT_TABLE_SIZE(WINDOW_A) * sizeof(secp256k1_ge)); + state.pre_a = (secp256k1_ge*)secp256k1_scratch_alloc(error_callback, scratch, n_points * 2 * ECMULT_TABLE_SIZE(WINDOW_A) * sizeof(secp256k1_ge)); state.pre_a_lam = state.pre_a + n_points * ECMULT_TABLE_SIZE(WINDOW_A); #else - state.pre_a = (secp256k1_ge*)secp256k1_scratch_alloc(scratch, n_points * ECMULT_TABLE_SIZE(WINDOW_A) * sizeof(secp256k1_ge)); + state.pre_a = (secp256k1_ge*)secp256k1_scratch_alloc(error_callback, scratch, n_points * ECMULT_TABLE_SIZE(WINDOW_A) * sizeof(secp256k1_ge)); #endif - state.ps = (struct secp256k1_strauss_point_state*)secp256k1_scratch_alloc(scratch, n_points * sizeof(struct secp256k1_strauss_point_state)); + state.ps = (struct secp256k1_strauss_point_state*)secp256k1_scratch_alloc(error_callback, scratch, n_points * sizeof(struct secp256k1_strauss_point_state)); + + if (points == NULL || scalars == NULL || state.prej == NULL || state.zr == NULL || state.pre_a == NULL) { + secp256k1_scratch_apply_checkpoint(error_callback, scratch, scratch_checkpoint); + return 0; + } for (i = 0; i < n_points; i++) { secp256k1_ge point; if (!cb(&scalars[i], &point, i+cb_offset, cbdata)) { - secp256k1_scratch_deallocate_frame(scratch); + secp256k1_scratch_apply_checkpoint(error_callback, scratch, scratch_checkpoint); return 0; } secp256k1_gej_set_ge(&points[i], &point); } secp256k1_ecmult_strauss_wnaf(ctx, &state, r, n_points, points, scalars, inp_g_sc); - secp256k1_scratch_deallocate_frame(scratch); + secp256k1_scratch_apply_checkpoint(error_callback, scratch, scratch_checkpoint); return 1; } /* Wrapper for secp256k1_ecmult_multi_func interface */ -static int secp256k1_ecmult_strauss_batch_single(const secp256k1_ecmult_context *actx, secp256k1_scratch *scratch, secp256k1_gej *r, const secp256k1_scalar *inp_g_sc, secp256k1_ecmult_multi_callback cb, void *cbdata, size_t n) { - return secp256k1_ecmult_strauss_batch(actx, scratch, r, inp_g_sc, cb, cbdata, n, 0); +static int secp256k1_ecmult_strauss_batch_single(const secp256k1_callback* error_callback, const secp256k1_ecmult_context *actx, secp256k1_scratch *scratch, secp256k1_gej *r, const secp256k1_scalar *inp_g_sc, secp256k1_ecmult_multi_callback cb, void *cbdata, size_t n) { + return secp256k1_ecmult_strauss_batch(error_callback, actx, scratch, r, inp_g_sc, cb, cbdata, n, 0); } -static size_t secp256k1_strauss_max_points(secp256k1_scratch *scratch) { - return secp256k1_scratch_max_allocation(scratch, STRAUSS_SCRATCH_OBJECTS) / secp256k1_strauss_scratch_size(1); +static size_t secp256k1_strauss_max_points(const secp256k1_callback* error_callback, secp256k1_scratch *scratch) { + return secp256k1_scratch_max_allocation(error_callback, scratch, STRAUSS_SCRATCH_OBJECTS) / secp256k1_strauss_scratch_size(1); } /** Convert a number to WNAF notation. @@ -963,7 +989,8 @@ static size_t secp256k1_pippenger_scratch_size(size_t n_points, int bucket_windo return (sizeof(secp256k1_gej) << bucket_window) + sizeof(struct secp256k1_pippenger_state) + entries * entry_size; } -static int secp256k1_ecmult_pippenger_batch(const secp256k1_ecmult_context *ctx, secp256k1_scratch *scratch, secp256k1_gej *r, const secp256k1_scalar *inp_g_sc, secp256k1_ecmult_multi_callback cb, void *cbdata, size_t n_points, size_t cb_offset) { +static int secp256k1_ecmult_pippenger_batch(const secp256k1_callback* error_callback, const secp256k1_ecmult_context *ctx, secp256k1_scratch *scratch, secp256k1_gej *r, const secp256k1_scalar *inp_g_sc, secp256k1_ecmult_multi_callback cb, void *cbdata, size_t n_points, size_t cb_offset) { + const size_t scratch_checkpoint = secp256k1_scratch_checkpoint(error_callback, scratch); /* Use 2(n+1) with the endomorphism, n+1 without, when calculating batch * sizes. The reason for +1 is that we add the G scalar to the list of * other scalars. */ @@ -988,15 +1015,21 @@ static int secp256k1_ecmult_pippenger_batch(const secp256k1_ecmult_context *ctx, } bucket_window = secp256k1_pippenger_bucket_window(n_points); - if (!secp256k1_scratch_allocate_frame(scratch, secp256k1_pippenger_scratch_size(n_points, bucket_window), PIPPENGER_SCRATCH_OBJECTS)) { + points = (secp256k1_ge *) secp256k1_scratch_alloc(error_callback, scratch, entries * sizeof(*points)); + scalars = (secp256k1_scalar *) secp256k1_scratch_alloc(error_callback, scratch, entries * sizeof(*scalars)); + state_space = (struct secp256k1_pippenger_state *) secp256k1_scratch_alloc(error_callback, scratch, sizeof(*state_space)); + if (points == NULL || scalars == NULL || state_space == NULL) { + secp256k1_scratch_apply_checkpoint(error_callback, scratch, scratch_checkpoint); + return 0; + } + + state_space->ps = (struct secp256k1_pippenger_point_state *) secp256k1_scratch_alloc(error_callback, scratch, entries * sizeof(*state_space->ps)); + state_space->wnaf_na = (int *) secp256k1_scratch_alloc(error_callback, scratch, entries*(WNAF_SIZE(bucket_window+1)) * sizeof(int)); + buckets = (secp256k1_gej *) secp256k1_scratch_alloc(error_callback, scratch, (1<<bucket_window) * sizeof(*buckets)); + if (state_space->ps == NULL || state_space->wnaf_na == NULL || buckets == NULL) { + secp256k1_scratch_apply_checkpoint(error_callback, scratch, scratch_checkpoint); return 0; } - points = (secp256k1_ge *) secp256k1_scratch_alloc(scratch, entries * sizeof(*points)); - scalars = (secp256k1_scalar *) secp256k1_scratch_alloc(scratch, entries * sizeof(*scalars)); - state_space = (struct secp256k1_pippenger_state *) secp256k1_scratch_alloc(scratch, sizeof(*state_space)); - state_space->ps = (struct secp256k1_pippenger_point_state *) secp256k1_scratch_alloc(scratch, entries * sizeof(*state_space->ps)); - state_space->wnaf_na = (int *) secp256k1_scratch_alloc(scratch, entries*(WNAF_SIZE(bucket_window+1)) * sizeof(int)); - buckets = (secp256k1_gej *) secp256k1_scratch_alloc(scratch, sizeof(*buckets) << bucket_window); if (inp_g_sc != NULL) { scalars[0] = *inp_g_sc; @@ -1010,7 +1043,7 @@ static int secp256k1_ecmult_pippenger_batch(const secp256k1_ecmult_context *ctx, while (point_idx < n_points) { if (!cb(&scalars[idx], &points[idx], point_idx + cb_offset, cbdata)) { - secp256k1_scratch_deallocate_frame(scratch); + secp256k1_scratch_apply_checkpoint(error_callback, scratch, scratch_checkpoint); return 0; } idx++; @@ -1034,13 +1067,13 @@ static int secp256k1_ecmult_pippenger_batch(const secp256k1_ecmult_context *ctx, for(i = 0; i < 1<<bucket_window; i++) { secp256k1_gej_clear(&buckets[i]); } - secp256k1_scratch_deallocate_frame(scratch); + secp256k1_scratch_apply_checkpoint(error_callback, scratch, scratch_checkpoint); return 1; } /* Wrapper for secp256k1_ecmult_multi_func interface */ -static int secp256k1_ecmult_pippenger_batch_single(const secp256k1_ecmult_context *actx, secp256k1_scratch *scratch, secp256k1_gej *r, const secp256k1_scalar *inp_g_sc, secp256k1_ecmult_multi_callback cb, void *cbdata, size_t n) { - return secp256k1_ecmult_pippenger_batch(actx, scratch, r, inp_g_sc, cb, cbdata, n, 0); +static int secp256k1_ecmult_pippenger_batch_single(const secp256k1_callback* error_callback, const secp256k1_ecmult_context *actx, secp256k1_scratch *scratch, secp256k1_gej *r, const secp256k1_scalar *inp_g_sc, secp256k1_ecmult_multi_callback cb, void *cbdata, size_t n) { + return secp256k1_ecmult_pippenger_batch(error_callback, actx, scratch, r, inp_g_sc, cb, cbdata, n, 0); } /** @@ -1048,8 +1081,8 @@ static int secp256k1_ecmult_pippenger_batch_single(const secp256k1_ecmult_contex * a given scratch space. The function ensures that fewer points may also be * used. */ -static size_t secp256k1_pippenger_max_points(secp256k1_scratch *scratch) { - size_t max_alloc = secp256k1_scratch_max_allocation(scratch, PIPPENGER_SCRATCH_OBJECTS); +static size_t secp256k1_pippenger_max_points(const secp256k1_callback* error_callback, secp256k1_scratch *scratch) { + size_t max_alloc = secp256k1_scratch_max_allocation(error_callback, scratch, PIPPENGER_SCRATCH_OBJECTS); int bucket_window; size_t res = 0; @@ -1131,11 +1164,11 @@ static int secp256k1_ecmult_multi_batch_size_helper(size_t *n_batches, size_t *n return 1; } -typedef int (*secp256k1_ecmult_multi_func)(const secp256k1_ecmult_context*, secp256k1_scratch*, secp256k1_gej*, const secp256k1_scalar*, secp256k1_ecmult_multi_callback cb, void*, size_t); -static int secp256k1_ecmult_multi_var(const secp256k1_ecmult_context *ctx, secp256k1_scratch *scratch, secp256k1_gej *r, const secp256k1_scalar *inp_g_sc, secp256k1_ecmult_multi_callback cb, void *cbdata, size_t n) { +typedef int (*secp256k1_ecmult_multi_func)(const secp256k1_callback* error_callback, const secp256k1_ecmult_context*, secp256k1_scratch*, secp256k1_gej*, const secp256k1_scalar*, secp256k1_ecmult_multi_callback cb, void*, size_t); +static int secp256k1_ecmult_multi_var(const secp256k1_callback* error_callback, const secp256k1_ecmult_context *ctx, secp256k1_scratch *scratch, secp256k1_gej *r, const secp256k1_scalar *inp_g_sc, secp256k1_ecmult_multi_callback cb, void *cbdata, size_t n) { size_t i; - int (*f)(const secp256k1_ecmult_context*, secp256k1_scratch*, secp256k1_gej*, const secp256k1_scalar*, secp256k1_ecmult_multi_callback cb, void*, size_t, size_t); + int (*f)(const secp256k1_callback* error_callback, const secp256k1_ecmult_context*, secp256k1_scratch*, secp256k1_gej*, const secp256k1_scalar*, secp256k1_ecmult_multi_callback cb, void*, size_t, size_t); size_t n_batches; size_t n_batch_points; @@ -1152,16 +1185,18 @@ static int secp256k1_ecmult_multi_var(const secp256k1_ecmult_context *ctx, secp2 return secp256k1_ecmult_multi_simple_var(ctx, r, inp_g_sc, cb, cbdata, n); } - /* Compute the batch sizes for pippenger given a scratch space. If it's greater than a threshold - * use pippenger. Otherwise use strauss */ - if (!secp256k1_ecmult_multi_batch_size_helper(&n_batches, &n_batch_points, secp256k1_pippenger_max_points(scratch), n)) { - return 0; + /* Compute the batch sizes for Pippenger's algorithm given a scratch space. If it's greater than + * a threshold use Pippenger's algorithm. Otherwise use Strauss' algorithm. + * As a first step check if there's enough space for Pippenger's algo (which requires less space + * than Strauss' algo) and if not, use the simple algorithm. */ + if (!secp256k1_ecmult_multi_batch_size_helper(&n_batches, &n_batch_points, secp256k1_pippenger_max_points(error_callback, scratch), n)) { + return secp256k1_ecmult_multi_simple_var(ctx, r, inp_g_sc, cb, cbdata, n); } if (n_batch_points >= ECMULT_PIPPENGER_THRESHOLD) { f = secp256k1_ecmult_pippenger_batch; } else { - if (!secp256k1_ecmult_multi_batch_size_helper(&n_batches, &n_batch_points, secp256k1_strauss_max_points(scratch), n)) { - return 0; + if (!secp256k1_ecmult_multi_batch_size_helper(&n_batches, &n_batch_points, secp256k1_strauss_max_points(error_callback, scratch), n)) { + return secp256k1_ecmult_multi_simple_var(ctx, r, inp_g_sc, cb, cbdata, n); } f = secp256k1_ecmult_strauss_batch; } @@ -1169,7 +1204,7 @@ static int secp256k1_ecmult_multi_var(const secp256k1_ecmult_context *ctx, secp2 size_t nbp = n < n_batch_points ? n : n_batch_points; size_t offset = n_batch_points*i; secp256k1_gej tmp; - if (!f(ctx, scratch, &tmp, i == 0 ? inp_g_sc : NULL, cb, cbdata, nbp, offset)) { + if (!f(error_callback, ctx, scratch, &tmp, i == 0 ? inp_g_sc : NULL, cb, cbdata, nbp, offset)) { return 0; } secp256k1_gej_add_var(r, r, &tmp, NULL); diff --git a/src/field.h b/src/field.h index bb6692ad57..7993a1f11e 100644 --- a/src/field.h +++ b/src/field.h @@ -32,10 +32,12 @@ #include "util.h" -/** Normalize a field element. */ +/** Normalize a field element. This brings the field element to a canonical representation, reduces + * its magnitude to 1, and reduces it modulo field size `p`. + */ static void secp256k1_fe_normalize(secp256k1_fe *r); -/** Weakly normalize a field element: reduce it magnitude to 1, but don't fully normalize. */ +/** Weakly normalize a field element: reduce its magnitude to 1, but don't fully normalize. */ static void secp256k1_fe_normalize_weak(secp256k1_fe *r); /** Normalize a field element, without constant-time guarantee. */ @@ -123,10 +125,10 @@ static void secp256k1_fe_to_storage(secp256k1_fe_storage *r, const secp256k1_fe /** Convert a field element back from the storage type. */ static void secp256k1_fe_from_storage(secp256k1_fe *r, const secp256k1_fe_storage *a); -/** If flag is true, set *r equal to *a; otherwise leave it. Constant-time. */ +/** If flag is true, set *r equal to *a; otherwise leave it. Constant-time. Both *r and *a must be initialized.*/ static void secp256k1_fe_storage_cmov(secp256k1_fe_storage *r, const secp256k1_fe_storage *a, int flag); -/** If flag is true, set *r equal to *a; otherwise leave it. Constant-time. */ +/** If flag is true, set *r equal to *a; otherwise leave it. Constant-time. Both *r and *a must be initialized.*/ static void secp256k1_fe_cmov(secp256k1_fe *r, const secp256k1_fe *a, int flag); #endif /* SECP256K1_FIELD_H */ diff --git a/src/field_10x26_impl.h b/src/field_10x26_impl.h index 4ae4fdcec8..651500ee8e 100644 --- a/src/field_10x26_impl.h +++ b/src/field_10x26_impl.h @@ -320,6 +320,7 @@ static int secp256k1_fe_cmp_var(const secp256k1_fe *a, const secp256k1_fe *b) { } static int secp256k1_fe_set_b32(secp256k1_fe *r, const unsigned char *a) { + int ret; r->n[0] = (uint32_t)a[31] | ((uint32_t)a[30] << 8) | ((uint32_t)a[29] << 16) | ((uint32_t)(a[28] & 0x3) << 24); r->n[1] = (uint32_t)((a[28] >> 2) & 0x3f) | ((uint32_t)a[27] << 6) | ((uint32_t)a[26] << 14) | ((uint32_t)(a[25] & 0xf) << 22); r->n[2] = (uint32_t)((a[25] >> 4) & 0xf) | ((uint32_t)a[24] << 4) | ((uint32_t)a[23] << 12) | ((uint32_t)(a[22] & 0x3f) << 20); @@ -331,15 +332,17 @@ static int secp256k1_fe_set_b32(secp256k1_fe *r, const unsigned char *a) { r->n[8] = (uint32_t)a[5] | ((uint32_t)a[4] << 8) | ((uint32_t)a[3] << 16) | ((uint32_t)(a[2] & 0x3) << 24); r->n[9] = (uint32_t)((a[2] >> 2) & 0x3f) | ((uint32_t)a[1] << 6) | ((uint32_t)a[0] << 14); - if (r->n[9] == 0x3FFFFFUL && (r->n[8] & r->n[7] & r->n[6] & r->n[5] & r->n[4] & r->n[3] & r->n[2]) == 0x3FFFFFFUL && (r->n[1] + 0x40UL + ((r->n[0] + 0x3D1UL) >> 26)) > 0x3FFFFFFUL) { - return 0; - } + ret = !((r->n[9] == 0x3FFFFFUL) & ((r->n[8] & r->n[7] & r->n[6] & r->n[5] & r->n[4] & r->n[3] & r->n[2]) == 0x3FFFFFFUL) & ((r->n[1] + 0x40UL + ((r->n[0] + 0x3D1UL) >> 26)) > 0x3FFFFFFUL)); #ifdef VERIFY r->magnitude = 1; - r->normalized = 1; - secp256k1_fe_verify(r); + if (ret) { + r->normalized = 1; + secp256k1_fe_verify(r); + } else { + r->normalized = 0; + } #endif - return 1; + return ret; } /** Convert a field element to a 32-byte big endian value. Requires the input to be normalized */ @@ -1094,6 +1097,7 @@ static void secp256k1_fe_sqr(secp256k1_fe *r, const secp256k1_fe *a) { static SECP256K1_INLINE void secp256k1_fe_cmov(secp256k1_fe *r, const secp256k1_fe *a, int flag) { uint32_t mask0, mask1; + VG_CHECK_VERIFY(r->n, sizeof(r->n)); mask0 = flag + ~((uint32_t)0); mask1 = ~mask0; r->n[0] = (r->n[0] & mask0) | (a->n[0] & mask1); @@ -1107,15 +1111,16 @@ static SECP256K1_INLINE void secp256k1_fe_cmov(secp256k1_fe *r, const secp256k1_ r->n[8] = (r->n[8] & mask0) | (a->n[8] & mask1); r->n[9] = (r->n[9] & mask0) | (a->n[9] & mask1); #ifdef VERIFY - if (a->magnitude > r->magnitude) { + if (flag) { r->magnitude = a->magnitude; + r->normalized = a->normalized; } - r->normalized &= a->normalized; #endif } static SECP256K1_INLINE void secp256k1_fe_storage_cmov(secp256k1_fe_storage *r, const secp256k1_fe_storage *a, int flag) { uint32_t mask0, mask1; + VG_CHECK_VERIFY(r->n, sizeof(r->n)); mask0 = flag + ~((uint32_t)0); mask1 = ~mask0; r->n[0] = (r->n[0] & mask0) | (a->n[0] & mask1); diff --git a/src/field_5x52_impl.h b/src/field_5x52_impl.h index f4263320d5..71a38f915b 100644 --- a/src/field_5x52_impl.h +++ b/src/field_5x52_impl.h @@ -283,6 +283,7 @@ static int secp256k1_fe_cmp_var(const secp256k1_fe *a, const secp256k1_fe *b) { } static int secp256k1_fe_set_b32(secp256k1_fe *r, const unsigned char *a) { + int ret; r->n[0] = (uint64_t)a[31] | ((uint64_t)a[30] << 8) | ((uint64_t)a[29] << 16) @@ -317,15 +318,17 @@ static int secp256k1_fe_set_b32(secp256k1_fe *r, const unsigned char *a) { | ((uint64_t)a[2] << 24) | ((uint64_t)a[1] << 32) | ((uint64_t)a[0] << 40); - if (r->n[4] == 0x0FFFFFFFFFFFFULL && (r->n[3] & r->n[2] & r->n[1]) == 0xFFFFFFFFFFFFFULL && r->n[0] >= 0xFFFFEFFFFFC2FULL) { - return 0; - } + ret = !((r->n[4] == 0x0FFFFFFFFFFFFULL) & ((r->n[3] & r->n[2] & r->n[1]) == 0xFFFFFFFFFFFFFULL) & (r->n[0] >= 0xFFFFEFFFFFC2FULL)); #ifdef VERIFY r->magnitude = 1; - r->normalized = 1; - secp256k1_fe_verify(r); + if (ret) { + r->normalized = 1; + secp256k1_fe_verify(r); + } else { + r->normalized = 0; + } #endif - return 1; + return ret; } /** Convert a field element to a 32-byte big endian value. Requires the input to be normalized */ @@ -446,6 +449,7 @@ static void secp256k1_fe_sqr(secp256k1_fe *r, const secp256k1_fe *a) { static SECP256K1_INLINE void secp256k1_fe_cmov(secp256k1_fe *r, const secp256k1_fe *a, int flag) { uint64_t mask0, mask1; + VG_CHECK_VERIFY(r->n, sizeof(r->n)); mask0 = flag + ~((uint64_t)0); mask1 = ~mask0; r->n[0] = (r->n[0] & mask0) | (a->n[0] & mask1); @@ -454,15 +458,16 @@ static SECP256K1_INLINE void secp256k1_fe_cmov(secp256k1_fe *r, const secp256k1_ r->n[3] = (r->n[3] & mask0) | (a->n[3] & mask1); r->n[4] = (r->n[4] & mask0) | (a->n[4] & mask1); #ifdef VERIFY - if (a->magnitude > r->magnitude) { + if (flag) { r->magnitude = a->magnitude; + r->normalized = a->normalized; } - r->normalized &= a->normalized; #endif } static SECP256K1_INLINE void secp256k1_fe_storage_cmov(secp256k1_fe_storage *r, const secp256k1_fe_storage *a, int flag) { uint64_t mask0, mask1; + VG_CHECK_VERIFY(r->n, sizeof(r->n)); mask0 = flag + ~((uint64_t)0); mask1 = ~mask0; r->n[0] = (r->n[0] & mask0) | (a->n[0] & mask1); diff --git a/src/field_impl.h b/src/field_impl.h index 6070caccfe..485921a60e 100644 --- a/src/field_impl.h +++ b/src/field_impl.h @@ -315,4 +315,6 @@ static int secp256k1_fe_is_quad_var(const secp256k1_fe *a) { #endif } +static const secp256k1_fe secp256k1_fe_one = SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 1); + #endif /* SECP256K1_FIELD_IMPL_H */ diff --git a/src/gen_context.c b/src/gen_context.c index 87d296ebf0..539f574bfd 100644 --- a/src/gen_context.c +++ b/src/gen_context.c @@ -4,10 +4,16 @@ * file COPYING or http://www.opensource.org/licenses/mit-license.php.* **********************************************************************/ +// Autotools creates libsecp256k1-config.h, of which ECMULT_GEN_PREC_BITS is needed. +// ifndef guard so downstream users can define their own if they do not use autotools. +#if !defined(ECMULT_GEN_PREC_BITS) +#include "libsecp256k1-config.h" +#endif #define USE_BASIC_CONFIG 1 - #include "basic-config.h" + #include "include/secp256k1.h" +#include "util.h" #include "field_impl.h" #include "scalar_impl.h" #include "group_impl.h" @@ -26,6 +32,7 @@ static const secp256k1_callback default_error_callback = { int main(int argc, char **argv) { secp256k1_ecmult_gen_context ctx; + void *prealloc, *base; int inner; int outer; FILE* fp; @@ -38,26 +45,31 @@ int main(int argc, char **argv) { fprintf(stderr, "Could not open src/ecmult_static_context.h for writing!\n"); return -1; } - + fprintf(fp, "#ifndef _SECP256K1_ECMULT_STATIC_CONTEXT_\n"); fprintf(fp, "#define _SECP256K1_ECMULT_STATIC_CONTEXT_\n"); fprintf(fp, "#include \"src/group.h\"\n"); fprintf(fp, "#define SC SECP256K1_GE_STORAGE_CONST\n"); - fprintf(fp, "static const secp256k1_ge_storage secp256k1_ecmult_static_context[64][16] = {\n"); + fprintf(fp, "#if ECMULT_GEN_PREC_N != %d || ECMULT_GEN_PREC_G != %d\n", ECMULT_GEN_PREC_N, ECMULT_GEN_PREC_G); + fprintf(fp, " #error configuration mismatch, invalid ECMULT_GEN_PREC_N, ECMULT_GEN_PREC_G. Try deleting ecmult_static_context.h before the build.\n"); + fprintf(fp, "#endif\n"); + fprintf(fp, "static const secp256k1_ge_storage secp256k1_ecmult_static_context[ECMULT_GEN_PREC_N][ECMULT_GEN_PREC_G] = {\n"); + base = checked_malloc(&default_error_callback, SECP256K1_ECMULT_GEN_CONTEXT_PREALLOCATED_SIZE); + prealloc = base; secp256k1_ecmult_gen_context_init(&ctx); - secp256k1_ecmult_gen_context_build(&ctx, &default_error_callback); - for(outer = 0; outer != 64; outer++) { + secp256k1_ecmult_gen_context_build(&ctx, &prealloc); + for(outer = 0; outer != ECMULT_GEN_PREC_N; outer++) { fprintf(fp,"{\n"); - for(inner = 0; inner != 16; inner++) { + for(inner = 0; inner != ECMULT_GEN_PREC_G; inner++) { fprintf(fp," SC(%uu, %uu, %uu, %uu, %uu, %uu, %uu, %uu, %uu, %uu, %uu, %uu, %uu, %uu, %uu, %uu)", SECP256K1_GE_STORAGE_CONST_GET((*ctx.prec)[outer][inner])); - if (inner != 15) { + if (inner != ECMULT_GEN_PREC_G - 1) { fprintf(fp,",\n"); } else { fprintf(fp,"\n"); } } - if (outer != 63) { + if (outer != ECMULT_GEN_PREC_N - 1) { fprintf(fp,"},\n"); } else { fprintf(fp,"}\n"); @@ -65,10 +77,11 @@ int main(int argc, char **argv) { } fprintf(fp,"};\n"); secp256k1_ecmult_gen_context_clear(&ctx); - + free(base); + fprintf(fp, "#undef SC\n"); fprintf(fp, "#endif\n"); fclose(fp); - + return 0; } diff --git a/src/group.h b/src/group.h index 8e122ab429..863644f0f0 100644 --- a/src/group.h +++ b/src/group.h @@ -95,14 +95,13 @@ static int secp256k1_gej_is_infinity(const secp256k1_gej *a); /** Check whether a group element's y coordinate is a quadratic residue. */ static int secp256k1_gej_has_quad_y_var(const secp256k1_gej *a); -/** Set r equal to the double of a. If rzr is not-NULL, r->z = a->z * *rzr (where infinity means an implicit z = 0). - * a may not be zero. Constant time. */ -static void secp256k1_gej_double_nonzero(secp256k1_gej *r, const secp256k1_gej *a, secp256k1_fe *rzr); +/** Set r equal to the double of a, a cannot be infinity. Constant time. */ +static void secp256k1_gej_double_nonzero(secp256k1_gej *r, const secp256k1_gej *a); -/** Set r equal to the double of a. If rzr is not-NULL, r->z = a->z * *rzr (where infinity means an implicit z = 0). */ +/** Set r equal to the double of a. If rzr is not-NULL this sets *rzr such that r->z == a->z * *rzr (where infinity means an implicit z = 0). */ static void secp256k1_gej_double_var(secp256k1_gej *r, const secp256k1_gej *a, secp256k1_fe *rzr); -/** Set r equal to the sum of a and b. If rzr is non-NULL, r->z = a->z * *rzr (a cannot be infinity in that case). */ +/** Set r equal to the sum of a and b. If rzr is non-NULL this sets *rzr such that r->z == a->z * *rzr (a cannot be infinity in that case). */ static void secp256k1_gej_add_var(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_gej *b, secp256k1_fe *rzr); /** Set r equal to the sum of a and b (with b given in affine coordinates, and not infinity). */ @@ -110,7 +109,7 @@ static void secp256k1_gej_add_ge(secp256k1_gej *r, const secp256k1_gej *a, const /** Set r equal to the sum of a and b (with b given in affine coordinates). This is more efficient than secp256k1_gej_add_var. It is identical to secp256k1_gej_add_ge but without constant-time - guarantee, and b is allowed to be infinity. If rzr is non-NULL, r->z = a->z * *rzr (a cannot be infinity in that case). */ + guarantee, and b is allowed to be infinity. If rzr is non-NULL this sets *rzr such that r->z == a->z * *rzr (a cannot be infinity in that case). */ static void secp256k1_gej_add_ge_var(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_ge *b, secp256k1_fe *rzr); /** Set r equal to the sum of a and b (with the inverse of b's Z coordinate passed as bzinv). */ @@ -133,7 +132,7 @@ static void secp256k1_ge_to_storage(secp256k1_ge_storage *r, const secp256k1_ge /** Convert a group element back from the storage type. */ static void secp256k1_ge_from_storage(secp256k1_ge *r, const secp256k1_ge_storage *a); -/** If flag is true, set *r equal to *a; otherwise leave it. Constant-time. */ +/** If flag is true, set *r equal to *a; otherwise leave it. Constant-time. Both *r and *a must be initialized.*/ static void secp256k1_ge_storage_cmov(secp256k1_ge_storage *r, const secp256k1_ge_storage *a, int flag); /** Rescale a jacobian point by b which must be non-zero. Constant-time. */ diff --git a/src/group_impl.h b/src/group_impl.h index 9b93c39e92..43b039becf 100644 --- a/src/group_impl.h +++ b/src/group_impl.h @@ -303,7 +303,7 @@ static int secp256k1_ge_is_valid_var(const secp256k1_ge *a) { return secp256k1_fe_equal_var(&y2, &x3); } -static void secp256k1_gej_double_var(secp256k1_gej *r, const secp256k1_gej *a, secp256k1_fe *rzr) { +static SECP256K1_INLINE void secp256k1_gej_double_nonzero(secp256k1_gej *r, const secp256k1_gej *a) { /* Operations: 3 mul, 4 sqr, 0 normalize, 12 mul_int/add/negate. * * Note that there is an implementation described at @@ -312,29 +312,9 @@ static void secp256k1_gej_double_var(secp256k1_gej *r, const secp256k1_gej *a, s * mainly because it requires more normalizations. */ secp256k1_fe t1,t2,t3,t4; - /** For secp256k1, 2Q is infinity if and only if Q is infinity. This is because if 2Q = infinity, - * Q must equal -Q, or that Q.y == -(Q.y), or Q.y is 0. For a point on y^2 = x^3 + 7 to have - * y=0, x^3 must be -7 mod p. However, -7 has no cube root mod p. - * - * Having said this, if this function receives a point on a sextic twist, e.g. by - * a fault attack, it is possible for y to be 0. This happens for y^2 = x^3 + 6, - * since -6 does have a cube root mod p. For this point, this function will not set - * the infinity flag even though the point doubles to infinity, and the result - * point will be gibberish (z = 0 but infinity = 0). - */ - r->infinity = a->infinity; - if (r->infinity) { - if (rzr != NULL) { - secp256k1_fe_set_int(rzr, 1); - } - return; - } - if (rzr != NULL) { - *rzr = a->y; - secp256k1_fe_normalize_weak(rzr); - secp256k1_fe_mul_int(rzr, 2); - } + VERIFY_CHECK(!secp256k1_gej_is_infinity(a)); + r->infinity = 0; secp256k1_fe_mul(&r->z, &a->z, &a->y); secp256k1_fe_mul_int(&r->z, 2); /* Z' = 2*Y*Z (2) */ @@ -358,9 +338,32 @@ static void secp256k1_gej_double_var(secp256k1_gej *r, const secp256k1_gej *a, s secp256k1_fe_add(&r->y, &t2); /* Y' = 36*X^3*Y^2 - 27*X^6 - 8*Y^4 (4) */ } -static SECP256K1_INLINE void secp256k1_gej_double_nonzero(secp256k1_gej *r, const secp256k1_gej *a, secp256k1_fe *rzr) { - VERIFY_CHECK(!secp256k1_gej_is_infinity(a)); - secp256k1_gej_double_var(r, a, rzr); +static void secp256k1_gej_double_var(secp256k1_gej *r, const secp256k1_gej *a, secp256k1_fe *rzr) { + /** For secp256k1, 2Q is infinity if and only if Q is infinity. This is because if 2Q = infinity, + * Q must equal -Q, or that Q.y == -(Q.y), or Q.y is 0. For a point on y^2 = x^3 + 7 to have + * y=0, x^3 must be -7 mod p. However, -7 has no cube root mod p. + * + * Having said this, if this function receives a point on a sextic twist, e.g. by + * a fault attack, it is possible for y to be 0. This happens for y^2 = x^3 + 6, + * since -6 does have a cube root mod p. For this point, this function will not set + * the infinity flag even though the point doubles to infinity, and the result + * point will be gibberish (z = 0 but infinity = 0). + */ + if (a->infinity) { + r->infinity = 1; + if (rzr != NULL) { + secp256k1_fe_set_int(rzr, 1); + } + return; + } + + if (rzr != NULL) { + *rzr = a->y; + secp256k1_fe_normalize_weak(rzr); + secp256k1_fe_mul_int(rzr, 2); + } + + secp256k1_gej_double_nonzero(r, a); } static void secp256k1_gej_add_var(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_gej *b, secp256k1_fe *rzr) { diff --git a/src/hash_impl.h b/src/hash_impl.h index 009f26beba..782f97216c 100644 --- a/src/hash_impl.h +++ b/src/hash_impl.h @@ -131,7 +131,8 @@ static void secp256k1_sha256_transform(uint32_t* s, const uint32_t* chunk) { static void secp256k1_sha256_write(secp256k1_sha256 *hash, const unsigned char *data, size_t len) { size_t bufsize = hash->bytes & 0x3F; hash->bytes += len; - while (bufsize + len >= 64) { + VERIFY_CHECK(hash->bytes >= len); + while (len >= 64 - bufsize) { /* Fill the buffer, and process it. */ size_t chunk_len = 64 - bufsize; memcpy(((unsigned char*)hash->buf) + bufsize, data, chunk_len); diff --git a/src/java/org/bitcoin/NativeSecp256k1.java b/src/java/org/bitcoin/NativeSecp256k1.java deleted file mode 100644 index 1c67802fba..0000000000 --- a/src/java/org/bitcoin/NativeSecp256k1.java +++ /dev/null @@ -1,446 +0,0 @@ -/* - * Copyright 2013 Google Inc. - * Copyright 2014-2016 the libsecp256k1 contributors - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package org.bitcoin; - -import java.nio.ByteBuffer; -import java.nio.ByteOrder; - -import java.math.BigInteger; -import com.google.common.base.Preconditions; -import java.util.concurrent.locks.Lock; -import java.util.concurrent.locks.ReentrantReadWriteLock; -import static org.bitcoin.NativeSecp256k1Util.*; - -/** - * <p>This class holds native methods to handle ECDSA verification.</p> - * - * <p>You can find an example library that can be used for this at https://github.com/bitcoin/secp256k1</p> - * - * <p>To build secp256k1 for use with bitcoinj, run - * `./configure --enable-jni --enable-experimental --enable-module-ecdh` - * and `make` then copy `.libs/libsecp256k1.so` to your system library path - * or point the JVM to the folder containing it with -Djava.library.path - * </p> - */ -public class NativeSecp256k1 { - - private static final ReentrantReadWriteLock rwl = new ReentrantReadWriteLock(); - private static final Lock r = rwl.readLock(); - private static final Lock w = rwl.writeLock(); - private static ThreadLocal<ByteBuffer> nativeECDSABuffer = new ThreadLocal<ByteBuffer>(); - /** - * Verifies the given secp256k1 signature in native code. - * Calling when enabled == false is undefined (probably library not loaded) - * - * @param data The data which was signed, must be exactly 32 bytes - * @param signature The signature - * @param pub The public key which did the signing - */ - public static boolean verify(byte[] data, byte[] signature, byte[] pub) throws AssertFailException{ - Preconditions.checkArgument(data.length == 32 && signature.length <= 520 && pub.length <= 520); - - ByteBuffer byteBuff = nativeECDSABuffer.get(); - if (byteBuff == null || byteBuff.capacity() < 520) { - byteBuff = ByteBuffer.allocateDirect(520); - byteBuff.order(ByteOrder.nativeOrder()); - nativeECDSABuffer.set(byteBuff); - } - byteBuff.rewind(); - byteBuff.put(data); - byteBuff.put(signature); - byteBuff.put(pub); - - byte[][] retByteArray; - - r.lock(); - try { - return secp256k1_ecdsa_verify(byteBuff, Secp256k1Context.getContext(), signature.length, pub.length) == 1; - } finally { - r.unlock(); - } - } - - /** - * libsecp256k1 Create an ECDSA signature. - * - * @param data Message hash, 32 bytes - * @param key Secret key, 32 bytes - * - * Return values - * @param sig byte array of signature - */ - public static byte[] sign(byte[] data, byte[] sec) throws AssertFailException{ - Preconditions.checkArgument(data.length == 32 && sec.length <= 32); - - ByteBuffer byteBuff = nativeECDSABuffer.get(); - if (byteBuff == null || byteBuff.capacity() < 32 + 32) { - byteBuff = ByteBuffer.allocateDirect(32 + 32); - byteBuff.order(ByteOrder.nativeOrder()); - nativeECDSABuffer.set(byteBuff); - } - byteBuff.rewind(); - byteBuff.put(data); - byteBuff.put(sec); - - byte[][] retByteArray; - - r.lock(); - try { - retByteArray = secp256k1_ecdsa_sign(byteBuff, Secp256k1Context.getContext()); - } finally { - r.unlock(); - } - - byte[] sigArr = retByteArray[0]; - int sigLen = new BigInteger(new byte[] { retByteArray[1][0] }).intValue(); - int retVal = new BigInteger(new byte[] { retByteArray[1][1] }).intValue(); - - assertEquals(sigArr.length, sigLen, "Got bad signature length."); - - return retVal == 0 ? new byte[0] : sigArr; - } - - /** - * libsecp256k1 Seckey Verify - returns 1 if valid, 0 if invalid - * - * @param seckey ECDSA Secret key, 32 bytes - */ - public static boolean secKeyVerify(byte[] seckey) { - Preconditions.checkArgument(seckey.length == 32); - - ByteBuffer byteBuff = nativeECDSABuffer.get(); - if (byteBuff == null || byteBuff.capacity() < seckey.length) { - byteBuff = ByteBuffer.allocateDirect(seckey.length); - byteBuff.order(ByteOrder.nativeOrder()); - nativeECDSABuffer.set(byteBuff); - } - byteBuff.rewind(); - byteBuff.put(seckey); - - r.lock(); - try { - return secp256k1_ec_seckey_verify(byteBuff,Secp256k1Context.getContext()) == 1; - } finally { - r.unlock(); - } - } - - - /** - * libsecp256k1 Compute Pubkey - computes public key from secret key - * - * @param seckey ECDSA Secret key, 32 bytes - * - * Return values - * @param pubkey ECDSA Public key, 33 or 65 bytes - */ - //TODO add a 'compressed' arg - public static byte[] computePubkey(byte[] seckey) throws AssertFailException{ - Preconditions.checkArgument(seckey.length == 32); - - ByteBuffer byteBuff = nativeECDSABuffer.get(); - if (byteBuff == null || byteBuff.capacity() < seckey.length) { - byteBuff = ByteBuffer.allocateDirect(seckey.length); - byteBuff.order(ByteOrder.nativeOrder()); - nativeECDSABuffer.set(byteBuff); - } - byteBuff.rewind(); - byteBuff.put(seckey); - - byte[][] retByteArray; - - r.lock(); - try { - retByteArray = secp256k1_ec_pubkey_create(byteBuff, Secp256k1Context.getContext()); - } finally { - r.unlock(); - } - - byte[] pubArr = retByteArray[0]; - int pubLen = new BigInteger(new byte[] { retByteArray[1][0] }).intValue(); - int retVal = new BigInteger(new byte[] { retByteArray[1][1] }).intValue(); - - assertEquals(pubArr.length, pubLen, "Got bad pubkey length."); - - return retVal == 0 ? new byte[0]: pubArr; - } - - /** - * libsecp256k1 Cleanup - This destroys the secp256k1 context object - * This should be called at the end of the program for proper cleanup of the context. - */ - public static synchronized void cleanup() { - w.lock(); - try { - secp256k1_destroy_context(Secp256k1Context.getContext()); - } finally { - w.unlock(); - } - } - - public static long cloneContext() { - r.lock(); - try { - return secp256k1_ctx_clone(Secp256k1Context.getContext()); - } finally { r.unlock(); } - } - - /** - * libsecp256k1 PrivKey Tweak-Mul - Tweak privkey by multiplying to it - * - * @param tweak some bytes to tweak with - * @param seckey 32-byte seckey - */ - public static byte[] privKeyTweakMul(byte[] privkey, byte[] tweak) throws AssertFailException{ - Preconditions.checkArgument(privkey.length == 32); - - ByteBuffer byteBuff = nativeECDSABuffer.get(); - if (byteBuff == null || byteBuff.capacity() < privkey.length + tweak.length) { - byteBuff = ByteBuffer.allocateDirect(privkey.length + tweak.length); - byteBuff.order(ByteOrder.nativeOrder()); - nativeECDSABuffer.set(byteBuff); - } - byteBuff.rewind(); - byteBuff.put(privkey); - byteBuff.put(tweak); - - byte[][] retByteArray; - r.lock(); - try { - retByteArray = secp256k1_privkey_tweak_mul(byteBuff,Secp256k1Context.getContext()); - } finally { - r.unlock(); - } - - byte[] privArr = retByteArray[0]; - - int privLen = (byte) new BigInteger(new byte[] { retByteArray[1][0] }).intValue() & 0xFF; - int retVal = new BigInteger(new byte[] { retByteArray[1][1] }).intValue(); - - assertEquals(privArr.length, privLen, "Got bad pubkey length."); - - assertEquals(retVal, 1, "Failed return value check."); - - return privArr; - } - - /** - * libsecp256k1 PrivKey Tweak-Add - Tweak privkey by adding to it - * - * @param tweak some bytes to tweak with - * @param seckey 32-byte seckey - */ - public static byte[] privKeyTweakAdd(byte[] privkey, byte[] tweak) throws AssertFailException{ - Preconditions.checkArgument(privkey.length == 32); - - ByteBuffer byteBuff = nativeECDSABuffer.get(); - if (byteBuff == null || byteBuff.capacity() < privkey.length + tweak.length) { - byteBuff = ByteBuffer.allocateDirect(privkey.length + tweak.length); - byteBuff.order(ByteOrder.nativeOrder()); - nativeECDSABuffer.set(byteBuff); - } - byteBuff.rewind(); - byteBuff.put(privkey); - byteBuff.put(tweak); - - byte[][] retByteArray; - r.lock(); - try { - retByteArray = secp256k1_privkey_tweak_add(byteBuff,Secp256k1Context.getContext()); - } finally { - r.unlock(); - } - - byte[] privArr = retByteArray[0]; - - int privLen = (byte) new BigInteger(new byte[] { retByteArray[1][0] }).intValue() & 0xFF; - int retVal = new BigInteger(new byte[] { retByteArray[1][1] }).intValue(); - - assertEquals(privArr.length, privLen, "Got bad pubkey length."); - - assertEquals(retVal, 1, "Failed return value check."); - - return privArr; - } - - /** - * libsecp256k1 PubKey Tweak-Add - Tweak pubkey by adding to it - * - * @param tweak some bytes to tweak with - * @param pubkey 32-byte seckey - */ - public static byte[] pubKeyTweakAdd(byte[] pubkey, byte[] tweak) throws AssertFailException{ - Preconditions.checkArgument(pubkey.length == 33 || pubkey.length == 65); - - ByteBuffer byteBuff = nativeECDSABuffer.get(); - if (byteBuff == null || byteBuff.capacity() < pubkey.length + tweak.length) { - byteBuff = ByteBuffer.allocateDirect(pubkey.length + tweak.length); - byteBuff.order(ByteOrder.nativeOrder()); - nativeECDSABuffer.set(byteBuff); - } - byteBuff.rewind(); - byteBuff.put(pubkey); - byteBuff.put(tweak); - - byte[][] retByteArray; - r.lock(); - try { - retByteArray = secp256k1_pubkey_tweak_add(byteBuff,Secp256k1Context.getContext(), pubkey.length); - } finally { - r.unlock(); - } - - byte[] pubArr = retByteArray[0]; - - int pubLen = (byte) new BigInteger(new byte[] { retByteArray[1][0] }).intValue() & 0xFF; - int retVal = new BigInteger(new byte[] { retByteArray[1][1] }).intValue(); - - assertEquals(pubArr.length, pubLen, "Got bad pubkey length."); - - assertEquals(retVal, 1, "Failed return value check."); - - return pubArr; - } - - /** - * libsecp256k1 PubKey Tweak-Mul - Tweak pubkey by multiplying to it - * - * @param tweak some bytes to tweak with - * @param pubkey 32-byte seckey - */ - public static byte[] pubKeyTweakMul(byte[] pubkey, byte[] tweak) throws AssertFailException{ - Preconditions.checkArgument(pubkey.length == 33 || pubkey.length == 65); - - ByteBuffer byteBuff = nativeECDSABuffer.get(); - if (byteBuff == null || byteBuff.capacity() < pubkey.length + tweak.length) { - byteBuff = ByteBuffer.allocateDirect(pubkey.length + tweak.length); - byteBuff.order(ByteOrder.nativeOrder()); - nativeECDSABuffer.set(byteBuff); - } - byteBuff.rewind(); - byteBuff.put(pubkey); - byteBuff.put(tweak); - - byte[][] retByteArray; - r.lock(); - try { - retByteArray = secp256k1_pubkey_tweak_mul(byteBuff,Secp256k1Context.getContext(), pubkey.length); - } finally { - r.unlock(); - } - - byte[] pubArr = retByteArray[0]; - - int pubLen = (byte) new BigInteger(new byte[] { retByteArray[1][0] }).intValue() & 0xFF; - int retVal = new BigInteger(new byte[] { retByteArray[1][1] }).intValue(); - - assertEquals(pubArr.length, pubLen, "Got bad pubkey length."); - - assertEquals(retVal, 1, "Failed return value check."); - - return pubArr; - } - - /** - * libsecp256k1 create ECDH secret - constant time ECDH calculation - * - * @param seckey byte array of secret key used in exponentiaion - * @param pubkey byte array of public key used in exponentiaion - */ - public static byte[] createECDHSecret(byte[] seckey, byte[] pubkey) throws AssertFailException{ - Preconditions.checkArgument(seckey.length <= 32 && pubkey.length <= 65); - - ByteBuffer byteBuff = nativeECDSABuffer.get(); - if (byteBuff == null || byteBuff.capacity() < 32 + pubkey.length) { - byteBuff = ByteBuffer.allocateDirect(32 + pubkey.length); - byteBuff.order(ByteOrder.nativeOrder()); - nativeECDSABuffer.set(byteBuff); - } - byteBuff.rewind(); - byteBuff.put(seckey); - byteBuff.put(pubkey); - - byte[][] retByteArray; - r.lock(); - try { - retByteArray = secp256k1_ecdh(byteBuff, Secp256k1Context.getContext(), pubkey.length); - } finally { - r.unlock(); - } - - byte[] resArr = retByteArray[0]; - int retVal = new BigInteger(new byte[] { retByteArray[1][0] }).intValue(); - - assertEquals(resArr.length, 32, "Got bad result length."); - assertEquals(retVal, 1, "Failed return value check."); - - return resArr; - } - - /** - * libsecp256k1 randomize - updates the context randomization - * - * @param seed 32-byte random seed - */ - public static synchronized boolean randomize(byte[] seed) throws AssertFailException{ - Preconditions.checkArgument(seed.length == 32 || seed == null); - - ByteBuffer byteBuff = nativeECDSABuffer.get(); - if (byteBuff == null || byteBuff.capacity() < seed.length) { - byteBuff = ByteBuffer.allocateDirect(seed.length); - byteBuff.order(ByteOrder.nativeOrder()); - nativeECDSABuffer.set(byteBuff); - } - byteBuff.rewind(); - byteBuff.put(seed); - - w.lock(); - try { - return secp256k1_context_randomize(byteBuff, Secp256k1Context.getContext()) == 1; - } finally { - w.unlock(); - } - } - - private static native long secp256k1_ctx_clone(long context); - - private static native int secp256k1_context_randomize(ByteBuffer byteBuff, long context); - - private static native byte[][] secp256k1_privkey_tweak_add(ByteBuffer byteBuff, long context); - - private static native byte[][] secp256k1_privkey_tweak_mul(ByteBuffer byteBuff, long context); - - private static native byte[][] secp256k1_pubkey_tweak_add(ByteBuffer byteBuff, long context, int pubLen); - - private static native byte[][] secp256k1_pubkey_tweak_mul(ByteBuffer byteBuff, long context, int pubLen); - - private static native void secp256k1_destroy_context(long context); - - private static native int secp256k1_ecdsa_verify(ByteBuffer byteBuff, long context, int sigLen, int pubLen); - - private static native byte[][] secp256k1_ecdsa_sign(ByteBuffer byteBuff, long context); - - private static native int secp256k1_ec_seckey_verify(ByteBuffer byteBuff, long context); - - private static native byte[][] secp256k1_ec_pubkey_create(ByteBuffer byteBuff, long context); - - private static native byte[][] secp256k1_ec_pubkey_parse(ByteBuffer byteBuff, long context, int inputLen); - - private static native byte[][] secp256k1_ecdh(ByteBuffer byteBuff, long context, int inputLen); - -} diff --git a/src/java/org/bitcoin/NativeSecp256k1Test.java b/src/java/org/bitcoin/NativeSecp256k1Test.java deleted file mode 100644 index d766a1029c..0000000000 --- a/src/java/org/bitcoin/NativeSecp256k1Test.java +++ /dev/null @@ -1,226 +0,0 @@ -package org.bitcoin; - -import com.google.common.io.BaseEncoding; -import java.util.Arrays; -import java.math.BigInteger; -import javax.xml.bind.DatatypeConverter; -import static org.bitcoin.NativeSecp256k1Util.*; - -/** - * This class holds test cases defined for testing this library. - */ -public class NativeSecp256k1Test { - - //TODO improve comments/add more tests - /** - * This tests verify() for a valid signature - */ - public static void testVerifyPos() throws AssertFailException{ - boolean result = false; - byte[] data = BaseEncoding.base16().lowerCase().decode("CF80CD8AED482D5D1527D7DC72FCEFF84E6326592848447D2DC0B0E87DFC9A90".toLowerCase()); //sha256hash of "testing" - byte[] sig = BaseEncoding.base16().lowerCase().decode("3044022079BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F817980220294F14E883B3F525B5367756C2A11EF6CF84B730B36C17CB0C56F0AAB2C98589".toLowerCase()); - byte[] pub = BaseEncoding.base16().lowerCase().decode("040A629506E1B65CD9D2E0BA9C75DF9C4FED0DB16DC9625ED14397F0AFC836FAE595DC53F8B0EFE61E703075BD9B143BAC75EC0E19F82A2208CAEB32BE53414C40".toLowerCase()); - - result = NativeSecp256k1.verify( data, sig, pub); - assertEquals( result, true , "testVerifyPos"); - } - - /** - * This tests verify() for a non-valid signature - */ - public static void testVerifyNeg() throws AssertFailException{ - boolean result = false; - byte[] data = BaseEncoding.base16().lowerCase().decode("CF80CD8AED482D5D1527D7DC72FCEFF84E6326592848447D2DC0B0E87DFC9A91".toLowerCase()); //sha256hash of "testing" - byte[] sig = BaseEncoding.base16().lowerCase().decode("3044022079BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F817980220294F14E883B3F525B5367756C2A11EF6CF84B730B36C17CB0C56F0AAB2C98589".toLowerCase()); - byte[] pub = BaseEncoding.base16().lowerCase().decode("040A629506E1B65CD9D2E0BA9C75DF9C4FED0DB16DC9625ED14397F0AFC836FAE595DC53F8B0EFE61E703075BD9B143BAC75EC0E19F82A2208CAEB32BE53414C40".toLowerCase()); - - result = NativeSecp256k1.verify( data, sig, pub); - //System.out.println(" TEST " + new BigInteger(1, resultbytes).toString(16)); - assertEquals( result, false , "testVerifyNeg"); - } - - /** - * This tests secret key verify() for a valid secretkey - */ - public static void testSecKeyVerifyPos() throws AssertFailException{ - boolean result = false; - byte[] sec = BaseEncoding.base16().lowerCase().decode("67E56582298859DDAE725F972992A07C6C4FB9F62A8FFF58CE3CA926A1063530".toLowerCase()); - - result = NativeSecp256k1.secKeyVerify( sec ); - //System.out.println(" TEST " + new BigInteger(1, resultbytes).toString(16)); - assertEquals( result, true , "testSecKeyVerifyPos"); - } - - /** - * This tests secret key verify() for an invalid secretkey - */ - public static void testSecKeyVerifyNeg() throws AssertFailException{ - boolean result = false; - byte[] sec = BaseEncoding.base16().lowerCase().decode("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF".toLowerCase()); - - result = NativeSecp256k1.secKeyVerify( sec ); - //System.out.println(" TEST " + new BigInteger(1, resultbytes).toString(16)); - assertEquals( result, false , "testSecKeyVerifyNeg"); - } - - /** - * This tests public key create() for a valid secretkey - */ - public static void testPubKeyCreatePos() throws AssertFailException{ - byte[] sec = BaseEncoding.base16().lowerCase().decode("67E56582298859DDAE725F972992A07C6C4FB9F62A8FFF58CE3CA926A1063530".toLowerCase()); - - byte[] resultArr = NativeSecp256k1.computePubkey( sec); - String pubkeyString = javax.xml.bind.DatatypeConverter.printHexBinary(resultArr); - assertEquals( pubkeyString , "04C591A8FF19AC9C4E4E5793673B83123437E975285E7B442F4EE2654DFFCA5E2D2103ED494718C697AC9AEBCFD19612E224DB46661011863ED2FC54E71861E2A6" , "testPubKeyCreatePos"); - } - - /** - * This tests public key create() for a invalid secretkey - */ - public static void testPubKeyCreateNeg() throws AssertFailException{ - byte[] sec = BaseEncoding.base16().lowerCase().decode("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF".toLowerCase()); - - byte[] resultArr = NativeSecp256k1.computePubkey( sec); - String pubkeyString = javax.xml.bind.DatatypeConverter.printHexBinary(resultArr); - assertEquals( pubkeyString, "" , "testPubKeyCreateNeg"); - } - - /** - * This tests sign() for a valid secretkey - */ - public static void testSignPos() throws AssertFailException{ - - byte[] data = BaseEncoding.base16().lowerCase().decode("CF80CD8AED482D5D1527D7DC72FCEFF84E6326592848447D2DC0B0E87DFC9A90".toLowerCase()); //sha256hash of "testing" - byte[] sec = BaseEncoding.base16().lowerCase().decode("67E56582298859DDAE725F972992A07C6C4FB9F62A8FFF58CE3CA926A1063530".toLowerCase()); - - byte[] resultArr = NativeSecp256k1.sign(data, sec); - String sigString = javax.xml.bind.DatatypeConverter.printHexBinary(resultArr); - assertEquals( sigString, "30440220182A108E1448DC8F1FB467D06A0F3BB8EA0533584CB954EF8DA112F1D60E39A202201C66F36DA211C087F3AF88B50EDF4F9BDAA6CF5FD6817E74DCA34DB12390C6E9" , "testSignPos"); - } - - /** - * This tests sign() for a invalid secretkey - */ - public static void testSignNeg() throws AssertFailException{ - byte[] data = BaseEncoding.base16().lowerCase().decode("CF80CD8AED482D5D1527D7DC72FCEFF84E6326592848447D2DC0B0E87DFC9A90".toLowerCase()); //sha256hash of "testing" - byte[] sec = BaseEncoding.base16().lowerCase().decode("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF".toLowerCase()); - - byte[] resultArr = NativeSecp256k1.sign(data, sec); - String sigString = javax.xml.bind.DatatypeConverter.printHexBinary(resultArr); - assertEquals( sigString, "" , "testSignNeg"); - } - - /** - * This tests private key tweak-add - */ - public static void testPrivKeyTweakAdd_1() throws AssertFailException { - byte[] sec = BaseEncoding.base16().lowerCase().decode("67E56582298859DDAE725F972992A07C6C4FB9F62A8FFF58CE3CA926A1063530".toLowerCase()); - byte[] data = BaseEncoding.base16().lowerCase().decode("3982F19BEF1615BCCFBB05E321C10E1D4CBA3DF0E841C2E41EEB6016347653C3".toLowerCase()); //sha256hash of "tweak" - - byte[] resultArr = NativeSecp256k1.privKeyTweakAdd( sec , data ); - String sigString = javax.xml.bind.DatatypeConverter.printHexBinary(resultArr); - assertEquals( sigString , "A168571E189E6F9A7E2D657A4B53AE99B909F7E712D1C23CED28093CD57C88F3" , "testPrivKeyAdd_1"); - } - - /** - * This tests private key tweak-mul - */ - public static void testPrivKeyTweakMul_1() throws AssertFailException { - byte[] sec = BaseEncoding.base16().lowerCase().decode("67E56582298859DDAE725F972992A07C6C4FB9F62A8FFF58CE3CA926A1063530".toLowerCase()); - byte[] data = BaseEncoding.base16().lowerCase().decode("3982F19BEF1615BCCFBB05E321C10E1D4CBA3DF0E841C2E41EEB6016347653C3".toLowerCase()); //sha256hash of "tweak" - - byte[] resultArr = NativeSecp256k1.privKeyTweakMul( sec , data ); - String sigString = javax.xml.bind.DatatypeConverter.printHexBinary(resultArr); - assertEquals( sigString , "97F8184235F101550F3C71C927507651BD3F1CDB4A5A33B8986ACF0DEE20FFFC" , "testPrivKeyMul_1"); - } - - /** - * This tests private key tweak-add uncompressed - */ - public static void testPrivKeyTweakAdd_2() throws AssertFailException { - byte[] pub = BaseEncoding.base16().lowerCase().decode("040A629506E1B65CD9D2E0BA9C75DF9C4FED0DB16DC9625ED14397F0AFC836FAE595DC53F8B0EFE61E703075BD9B143BAC75EC0E19F82A2208CAEB32BE53414C40".toLowerCase()); - byte[] data = BaseEncoding.base16().lowerCase().decode("3982F19BEF1615BCCFBB05E321C10E1D4CBA3DF0E841C2E41EEB6016347653C3".toLowerCase()); //sha256hash of "tweak" - - byte[] resultArr = NativeSecp256k1.pubKeyTweakAdd( pub , data ); - String sigString = javax.xml.bind.DatatypeConverter.printHexBinary(resultArr); - assertEquals( sigString , "0411C6790F4B663CCE607BAAE08C43557EDC1A4D11D88DFCB3D841D0C6A941AF525A268E2A863C148555C48FB5FBA368E88718A46E205FABC3DBA2CCFFAB0796EF" , "testPrivKeyAdd_2"); - } - - /** - * This tests private key tweak-mul uncompressed - */ - public static void testPrivKeyTweakMul_2() throws AssertFailException { - byte[] pub = BaseEncoding.base16().lowerCase().decode("040A629506E1B65CD9D2E0BA9C75DF9C4FED0DB16DC9625ED14397F0AFC836FAE595DC53F8B0EFE61E703075BD9B143BAC75EC0E19F82A2208CAEB32BE53414C40".toLowerCase()); - byte[] data = BaseEncoding.base16().lowerCase().decode("3982F19BEF1615BCCFBB05E321C10E1D4CBA3DF0E841C2E41EEB6016347653C3".toLowerCase()); //sha256hash of "tweak" - - byte[] resultArr = NativeSecp256k1.pubKeyTweakMul( pub , data ); - String sigString = javax.xml.bind.DatatypeConverter.printHexBinary(resultArr); - assertEquals( sigString , "04E0FE6FE55EBCA626B98A807F6CAF654139E14E5E3698F01A9A658E21DC1D2791EC060D4F412A794D5370F672BC94B722640B5F76914151CFCA6E712CA48CC589" , "testPrivKeyMul_2"); - } - - /** - * This tests seed randomization - */ - public static void testRandomize() throws AssertFailException { - byte[] seed = BaseEncoding.base16().lowerCase().decode("A441B15FE9A3CF56661190A0B93B9DEC7D04127288CC87250967CF3B52894D11".toLowerCase()); //sha256hash of "random" - boolean result = NativeSecp256k1.randomize(seed); - assertEquals( result, true, "testRandomize"); - } - - public static void testCreateECDHSecret() throws AssertFailException{ - - byte[] sec = BaseEncoding.base16().lowerCase().decode("67E56582298859DDAE725F972992A07C6C4FB9F62A8FFF58CE3CA926A1063530".toLowerCase()); - byte[] pub = BaseEncoding.base16().lowerCase().decode("040A629506E1B65CD9D2E0BA9C75DF9C4FED0DB16DC9625ED14397F0AFC836FAE595DC53F8B0EFE61E703075BD9B143BAC75EC0E19F82A2208CAEB32BE53414C40".toLowerCase()); - - byte[] resultArr = NativeSecp256k1.createECDHSecret(sec, pub); - String ecdhString = javax.xml.bind.DatatypeConverter.printHexBinary(resultArr); - assertEquals( ecdhString, "2A2A67007A926E6594AF3EB564FC74005B37A9C8AEF2033C4552051B5C87F043" , "testCreateECDHSecret"); - } - - public static void main(String[] args) throws AssertFailException{ - - - System.out.println("\n libsecp256k1 enabled: " + Secp256k1Context.isEnabled() + "\n"); - - assertEquals( Secp256k1Context.isEnabled(), true, "isEnabled" ); - - //Test verify() success/fail - testVerifyPos(); - testVerifyNeg(); - - //Test secKeyVerify() success/fail - testSecKeyVerifyPos(); - testSecKeyVerifyNeg(); - - //Test computePubkey() success/fail - testPubKeyCreatePos(); - testPubKeyCreateNeg(); - - //Test sign() success/fail - testSignPos(); - testSignNeg(); - - //Test privKeyTweakAdd() 1 - testPrivKeyTweakAdd_1(); - - //Test privKeyTweakMul() 2 - testPrivKeyTweakMul_1(); - - //Test privKeyTweakAdd() 3 - testPrivKeyTweakAdd_2(); - - //Test privKeyTweakMul() 4 - testPrivKeyTweakMul_2(); - - //Test randomize() - testRandomize(); - - //Test ECDH - testCreateECDHSecret(); - - NativeSecp256k1.cleanup(); - - System.out.println(" All tests passed." ); - - } -} diff --git a/src/java/org/bitcoin/NativeSecp256k1Util.java b/src/java/org/bitcoin/NativeSecp256k1Util.java deleted file mode 100644 index 04732ba044..0000000000 --- a/src/java/org/bitcoin/NativeSecp256k1Util.java +++ /dev/null @@ -1,45 +0,0 @@ -/* - * Copyright 2014-2016 the libsecp256k1 contributors - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package org.bitcoin; - -public class NativeSecp256k1Util{ - - public static void assertEquals( int val, int val2, String message ) throws AssertFailException{ - if( val != val2 ) - throw new AssertFailException("FAIL: " + message); - } - - public static void assertEquals( boolean val, boolean val2, String message ) throws AssertFailException{ - if( val != val2 ) - throw new AssertFailException("FAIL: " + message); - else - System.out.println("PASS: " + message); - } - - public static void assertEquals( String val, String val2, String message ) throws AssertFailException{ - if( !val.equals(val2) ) - throw new AssertFailException("FAIL: " + message); - else - System.out.println("PASS: " + message); - } - - public static class AssertFailException extends Exception { - public AssertFailException(String message) { - super( message ); - } - } -} diff --git a/src/java/org/bitcoin/Secp256k1Context.java b/src/java/org/bitcoin/Secp256k1Context.java deleted file mode 100644 index 216c986a8b..0000000000 --- a/src/java/org/bitcoin/Secp256k1Context.java +++ /dev/null @@ -1,51 +0,0 @@ -/* - * Copyright 2014-2016 the libsecp256k1 contributors - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package org.bitcoin; - -/** - * This class holds the context reference used in native methods - * to handle ECDSA operations. - */ -public class Secp256k1Context { - private static final boolean enabled; //true if the library is loaded - private static final long context; //ref to pointer to context obj - - static { //static initializer - boolean isEnabled = true; - long contextRef = -1; - try { - System.loadLibrary("secp256k1"); - contextRef = secp256k1_init_context(); - } catch (UnsatisfiedLinkError e) { - System.out.println("UnsatisfiedLinkError: " + e.toString()); - isEnabled = false; - } - enabled = isEnabled; - context = contextRef; - } - - public static boolean isEnabled() { - return enabled; - } - - public static long getContext() { - if(!enabled) return -1; //sanity check - return context; - } - - private static native long secp256k1_init_context(); -} diff --git a/src/java/org_bitcoin_NativeSecp256k1.c b/src/java/org_bitcoin_NativeSecp256k1.c deleted file mode 100644 index b50970b4f2..0000000000 --- a/src/java/org_bitcoin_NativeSecp256k1.c +++ /dev/null @@ -1,379 +0,0 @@ -#include <stdlib.h> -#include <stdint.h> -#include <string.h> -#include "org_bitcoin_NativeSecp256k1.h" -#include "include/secp256k1.h" -#include "include/secp256k1_ecdh.h" -#include "include/secp256k1_recovery.h" - - -SECP256K1_API jlong JNICALL Java_org_bitcoin_NativeSecp256k1_secp256k1_1ctx_1clone - (JNIEnv* env, jclass classObject, jlong ctx_l) -{ - const secp256k1_context *ctx = (secp256k1_context*)(uintptr_t)ctx_l; - - jlong ctx_clone_l = (uintptr_t) secp256k1_context_clone(ctx); - - (void)classObject;(void)env; - - return ctx_clone_l; - -} - -SECP256K1_API jint JNICALL Java_org_bitcoin_NativeSecp256k1_secp256k1_1context_1randomize - (JNIEnv* env, jclass classObject, jobject byteBufferObject, jlong ctx_l) -{ - secp256k1_context *ctx = (secp256k1_context*)(uintptr_t)ctx_l; - - const unsigned char* seed = (unsigned char*) (*env)->GetDirectBufferAddress(env, byteBufferObject); - - (void)classObject; - - return secp256k1_context_randomize(ctx, seed); - -} - -SECP256K1_API void JNICALL Java_org_bitcoin_NativeSecp256k1_secp256k1_1destroy_1context - (JNIEnv* env, jclass classObject, jlong ctx_l) -{ - secp256k1_context *ctx = (secp256k1_context*)(uintptr_t)ctx_l; - - secp256k1_context_destroy(ctx); - - (void)classObject;(void)env; -} - -SECP256K1_API jint JNICALL Java_org_bitcoin_NativeSecp256k1_secp256k1_1ecdsa_1verify - (JNIEnv* env, jclass classObject, jobject byteBufferObject, jlong ctx_l, jint siglen, jint publen) -{ - secp256k1_context *ctx = (secp256k1_context*)(uintptr_t)ctx_l; - - unsigned char* data = (unsigned char*) (*env)->GetDirectBufferAddress(env, byteBufferObject); - const unsigned char* sigdata = { (unsigned char*) (data + 32) }; - const unsigned char* pubdata = { (unsigned char*) (data + siglen + 32) }; - - secp256k1_ecdsa_signature sig; - secp256k1_pubkey pubkey; - - int ret = secp256k1_ecdsa_signature_parse_der(ctx, &sig, sigdata, siglen); - - if( ret ) { - ret = secp256k1_ec_pubkey_parse(ctx, &pubkey, pubdata, publen); - - if( ret ) { - ret = secp256k1_ecdsa_verify(ctx, &sig, data, &pubkey); - } - } - - (void)classObject; - - return ret; -} - -SECP256K1_API jobjectArray JNICALL Java_org_bitcoin_NativeSecp256k1_secp256k1_1ecdsa_1sign - (JNIEnv* env, jclass classObject, jobject byteBufferObject, jlong ctx_l) -{ - secp256k1_context *ctx = (secp256k1_context*)(uintptr_t)ctx_l; - unsigned char* data = (unsigned char*) (*env)->GetDirectBufferAddress(env, byteBufferObject); - unsigned char* secKey = (unsigned char*) (data + 32); - - jobjectArray retArray; - jbyteArray sigArray, intsByteArray; - unsigned char intsarray[2]; - - secp256k1_ecdsa_signature sig[72]; - - int ret = secp256k1_ecdsa_sign(ctx, sig, data, secKey, NULL, NULL); - - unsigned char outputSer[72]; - size_t outputLen = 72; - - if( ret ) { - int ret2 = secp256k1_ecdsa_signature_serialize_der(ctx,outputSer, &outputLen, sig ); (void)ret2; - } - - intsarray[0] = outputLen; - intsarray[1] = ret; - - retArray = (*env)->NewObjectArray(env, 2, - (*env)->FindClass(env, "[B"), - (*env)->NewByteArray(env, 1)); - - sigArray = (*env)->NewByteArray(env, outputLen); - (*env)->SetByteArrayRegion(env, sigArray, 0, outputLen, (jbyte*)outputSer); - (*env)->SetObjectArrayElement(env, retArray, 0, sigArray); - - intsByteArray = (*env)->NewByteArray(env, 2); - (*env)->SetByteArrayRegion(env, intsByteArray, 0, 2, (jbyte*)intsarray); - (*env)->SetObjectArrayElement(env, retArray, 1, intsByteArray); - - (void)classObject; - - return retArray; -} - -SECP256K1_API jint JNICALL Java_org_bitcoin_NativeSecp256k1_secp256k1_1ec_1seckey_1verify - (JNIEnv* env, jclass classObject, jobject byteBufferObject, jlong ctx_l) -{ - secp256k1_context *ctx = (secp256k1_context*)(uintptr_t)ctx_l; - unsigned char* secKey = (unsigned char*) (*env)->GetDirectBufferAddress(env, byteBufferObject); - - (void)classObject; - - return secp256k1_ec_seckey_verify(ctx, secKey); -} - -SECP256K1_API jobjectArray JNICALL Java_org_bitcoin_NativeSecp256k1_secp256k1_1ec_1pubkey_1create - (JNIEnv* env, jclass classObject, jobject byteBufferObject, jlong ctx_l) -{ - secp256k1_context *ctx = (secp256k1_context*)(uintptr_t)ctx_l; - const unsigned char* secKey = (unsigned char*) (*env)->GetDirectBufferAddress(env, byteBufferObject); - - secp256k1_pubkey pubkey; - - jobjectArray retArray; - jbyteArray pubkeyArray, intsByteArray; - unsigned char intsarray[2]; - - int ret = secp256k1_ec_pubkey_create(ctx, &pubkey, secKey); - - unsigned char outputSer[65]; - size_t outputLen = 65; - - if( ret ) { - int ret2 = secp256k1_ec_pubkey_serialize(ctx,outputSer, &outputLen, &pubkey,SECP256K1_EC_UNCOMPRESSED );(void)ret2; - } - - intsarray[0] = outputLen; - intsarray[1] = ret; - - retArray = (*env)->NewObjectArray(env, 2, - (*env)->FindClass(env, "[B"), - (*env)->NewByteArray(env, 1)); - - pubkeyArray = (*env)->NewByteArray(env, outputLen); - (*env)->SetByteArrayRegion(env, pubkeyArray, 0, outputLen, (jbyte*)outputSer); - (*env)->SetObjectArrayElement(env, retArray, 0, pubkeyArray); - - intsByteArray = (*env)->NewByteArray(env, 2); - (*env)->SetByteArrayRegion(env, intsByteArray, 0, 2, (jbyte*)intsarray); - (*env)->SetObjectArrayElement(env, retArray, 1, intsByteArray); - - (void)classObject; - - return retArray; - -} - -SECP256K1_API jobjectArray JNICALL Java_org_bitcoin_NativeSecp256k1_secp256k1_1privkey_1tweak_1add - (JNIEnv* env, jclass classObject, jobject byteBufferObject, jlong ctx_l) -{ - secp256k1_context *ctx = (secp256k1_context*)(uintptr_t)ctx_l; - unsigned char* privkey = (unsigned char*) (*env)->GetDirectBufferAddress(env, byteBufferObject); - const unsigned char* tweak = (unsigned char*) (privkey + 32); - - jobjectArray retArray; - jbyteArray privArray, intsByteArray; - unsigned char intsarray[2]; - - int privkeylen = 32; - - int ret = secp256k1_ec_privkey_tweak_add(ctx, privkey, tweak); - - intsarray[0] = privkeylen; - intsarray[1] = ret; - - retArray = (*env)->NewObjectArray(env, 2, - (*env)->FindClass(env, "[B"), - (*env)->NewByteArray(env, 1)); - - privArray = (*env)->NewByteArray(env, privkeylen); - (*env)->SetByteArrayRegion(env, privArray, 0, privkeylen, (jbyte*)privkey); - (*env)->SetObjectArrayElement(env, retArray, 0, privArray); - - intsByteArray = (*env)->NewByteArray(env, 2); - (*env)->SetByteArrayRegion(env, intsByteArray, 0, 2, (jbyte*)intsarray); - (*env)->SetObjectArrayElement(env, retArray, 1, intsByteArray); - - (void)classObject; - - return retArray; -} - -SECP256K1_API jobjectArray JNICALL Java_org_bitcoin_NativeSecp256k1_secp256k1_1privkey_1tweak_1mul - (JNIEnv* env, jclass classObject, jobject byteBufferObject, jlong ctx_l) -{ - secp256k1_context *ctx = (secp256k1_context*)(uintptr_t)ctx_l; - unsigned char* privkey = (unsigned char*) (*env)->GetDirectBufferAddress(env, byteBufferObject); - const unsigned char* tweak = (unsigned char*) (privkey + 32); - - jobjectArray retArray; - jbyteArray privArray, intsByteArray; - unsigned char intsarray[2]; - - int privkeylen = 32; - - int ret = secp256k1_ec_privkey_tweak_mul(ctx, privkey, tweak); - - intsarray[0] = privkeylen; - intsarray[1] = ret; - - retArray = (*env)->NewObjectArray(env, 2, - (*env)->FindClass(env, "[B"), - (*env)->NewByteArray(env, 1)); - - privArray = (*env)->NewByteArray(env, privkeylen); - (*env)->SetByteArrayRegion(env, privArray, 0, privkeylen, (jbyte*)privkey); - (*env)->SetObjectArrayElement(env, retArray, 0, privArray); - - intsByteArray = (*env)->NewByteArray(env, 2); - (*env)->SetByteArrayRegion(env, intsByteArray, 0, 2, (jbyte*)intsarray); - (*env)->SetObjectArrayElement(env, retArray, 1, intsByteArray); - - (void)classObject; - - return retArray; -} - -SECP256K1_API jobjectArray JNICALL Java_org_bitcoin_NativeSecp256k1_secp256k1_1pubkey_1tweak_1add - (JNIEnv* env, jclass classObject, jobject byteBufferObject, jlong ctx_l, jint publen) -{ - secp256k1_context *ctx = (secp256k1_context*)(uintptr_t)ctx_l; -/* secp256k1_pubkey* pubkey = (secp256k1_pubkey*) (*env)->GetDirectBufferAddress(env, byteBufferObject);*/ - unsigned char* pkey = (*env)->GetDirectBufferAddress(env, byteBufferObject); - const unsigned char* tweak = (unsigned char*) (pkey + publen); - - jobjectArray retArray; - jbyteArray pubArray, intsByteArray; - unsigned char intsarray[2]; - unsigned char outputSer[65]; - size_t outputLen = 65; - - secp256k1_pubkey pubkey; - int ret = secp256k1_ec_pubkey_parse(ctx, &pubkey, pkey, publen); - - if( ret ) { - ret = secp256k1_ec_pubkey_tweak_add(ctx, &pubkey, tweak); - } - - if( ret ) { - int ret2 = secp256k1_ec_pubkey_serialize(ctx,outputSer, &outputLen, &pubkey,SECP256K1_EC_UNCOMPRESSED );(void)ret2; - } - - intsarray[0] = outputLen; - intsarray[1] = ret; - - retArray = (*env)->NewObjectArray(env, 2, - (*env)->FindClass(env, "[B"), - (*env)->NewByteArray(env, 1)); - - pubArray = (*env)->NewByteArray(env, outputLen); - (*env)->SetByteArrayRegion(env, pubArray, 0, outputLen, (jbyte*)outputSer); - (*env)->SetObjectArrayElement(env, retArray, 0, pubArray); - - intsByteArray = (*env)->NewByteArray(env, 2); - (*env)->SetByteArrayRegion(env, intsByteArray, 0, 2, (jbyte*)intsarray); - (*env)->SetObjectArrayElement(env, retArray, 1, intsByteArray); - - (void)classObject; - - return retArray; -} - -SECP256K1_API jobjectArray JNICALL Java_org_bitcoin_NativeSecp256k1_secp256k1_1pubkey_1tweak_1mul - (JNIEnv* env, jclass classObject, jobject byteBufferObject, jlong ctx_l, jint publen) -{ - secp256k1_context *ctx = (secp256k1_context*)(uintptr_t)ctx_l; - unsigned char* pkey = (*env)->GetDirectBufferAddress(env, byteBufferObject); - const unsigned char* tweak = (unsigned char*) (pkey + publen); - - jobjectArray retArray; - jbyteArray pubArray, intsByteArray; - unsigned char intsarray[2]; - unsigned char outputSer[65]; - size_t outputLen = 65; - - secp256k1_pubkey pubkey; - int ret = secp256k1_ec_pubkey_parse(ctx, &pubkey, pkey, publen); - - if ( ret ) { - ret = secp256k1_ec_pubkey_tweak_mul(ctx, &pubkey, tweak); - } - - if( ret ) { - int ret2 = secp256k1_ec_pubkey_serialize(ctx,outputSer, &outputLen, &pubkey,SECP256K1_EC_UNCOMPRESSED );(void)ret2; - } - - intsarray[0] = outputLen; - intsarray[1] = ret; - - retArray = (*env)->NewObjectArray(env, 2, - (*env)->FindClass(env, "[B"), - (*env)->NewByteArray(env, 1)); - - pubArray = (*env)->NewByteArray(env, outputLen); - (*env)->SetByteArrayRegion(env, pubArray, 0, outputLen, (jbyte*)outputSer); - (*env)->SetObjectArrayElement(env, retArray, 0, pubArray); - - intsByteArray = (*env)->NewByteArray(env, 2); - (*env)->SetByteArrayRegion(env, intsByteArray, 0, 2, (jbyte*)intsarray); - (*env)->SetObjectArrayElement(env, retArray, 1, intsByteArray); - - (void)classObject; - - return retArray; -} - -SECP256K1_API jlong JNICALL Java_org_bitcoin_NativeSecp256k1_secp256k1_1ecdsa_1pubkey_1combine - (JNIEnv * env, jclass classObject, jobject byteBufferObject, jlong ctx_l, jint numkeys) -{ - (void)classObject;(void)env;(void)byteBufferObject;(void)ctx_l;(void)numkeys; - - return 0; -} - -SECP256K1_API jobjectArray JNICALL Java_org_bitcoin_NativeSecp256k1_secp256k1_1ecdh - (JNIEnv* env, jclass classObject, jobject byteBufferObject, jlong ctx_l, jint publen) -{ - secp256k1_context *ctx = (secp256k1_context*)(uintptr_t)ctx_l; - const unsigned char* secdata = (*env)->GetDirectBufferAddress(env, byteBufferObject); - const unsigned char* pubdata = (const unsigned char*) (secdata + 32); - - jobjectArray retArray; - jbyteArray outArray, intsByteArray; - unsigned char intsarray[1]; - secp256k1_pubkey pubkey; - unsigned char nonce_res[32]; - size_t outputLen = 32; - - int ret = secp256k1_ec_pubkey_parse(ctx, &pubkey, pubdata, publen); - - if (ret) { - ret = secp256k1_ecdh( - ctx, - nonce_res, - &pubkey, - secdata, - NULL, - NULL - ); - } - - intsarray[0] = ret; - - retArray = (*env)->NewObjectArray(env, 2, - (*env)->FindClass(env, "[B"), - (*env)->NewByteArray(env, 1)); - - outArray = (*env)->NewByteArray(env, outputLen); - (*env)->SetByteArrayRegion(env, outArray, 0, 32, (jbyte*)nonce_res); - (*env)->SetObjectArrayElement(env, retArray, 0, outArray); - - intsByteArray = (*env)->NewByteArray(env, 1); - (*env)->SetByteArrayRegion(env, intsByteArray, 0, 1, (jbyte*)intsarray); - (*env)->SetObjectArrayElement(env, retArray, 1, intsByteArray); - - (void)classObject; - - return retArray; -} diff --git a/src/java/org_bitcoin_NativeSecp256k1.h b/src/java/org_bitcoin_NativeSecp256k1.h deleted file mode 100644 index fe613c9e9e..0000000000 --- a/src/java/org_bitcoin_NativeSecp256k1.h +++ /dev/null @@ -1,119 +0,0 @@ -/* DO NOT EDIT THIS FILE - it is machine generated */ -#include <jni.h> -#include "include/secp256k1.h" -/* Header for class org_bitcoin_NativeSecp256k1 */ - -#ifndef _Included_org_bitcoin_NativeSecp256k1 -#define _Included_org_bitcoin_NativeSecp256k1 -#ifdef __cplusplus -extern "C" { -#endif -/* - * Class: org_bitcoin_NativeSecp256k1 - * Method: secp256k1_ctx_clone - * Signature: (J)J - */ -SECP256K1_API jlong JNICALL Java_org_bitcoin_NativeSecp256k1_secp256k1_1ctx_1clone - (JNIEnv *, jclass, jlong); - -/* - * Class: org_bitcoin_NativeSecp256k1 - * Method: secp256k1_context_randomize - * Signature: (Ljava/nio/ByteBuffer;J)I - */ -SECP256K1_API jint JNICALL Java_org_bitcoin_NativeSecp256k1_secp256k1_1context_1randomize - (JNIEnv *, jclass, jobject, jlong); - -/* - * Class: org_bitcoin_NativeSecp256k1 - * Method: secp256k1_privkey_tweak_add - * Signature: (Ljava/nio/ByteBuffer;J)[[B - */ -SECP256K1_API jobjectArray JNICALL Java_org_bitcoin_NativeSecp256k1_secp256k1_1privkey_1tweak_1add - (JNIEnv *, jclass, jobject, jlong); - -/* - * Class: org_bitcoin_NativeSecp256k1 - * Method: secp256k1_privkey_tweak_mul - * Signature: (Ljava/nio/ByteBuffer;J)[[B - */ -SECP256K1_API jobjectArray JNICALL Java_org_bitcoin_NativeSecp256k1_secp256k1_1privkey_1tweak_1mul - (JNIEnv *, jclass, jobject, jlong); - -/* - * Class: org_bitcoin_NativeSecp256k1 - * Method: secp256k1_pubkey_tweak_add - * Signature: (Ljava/nio/ByteBuffer;JI)[[B - */ -SECP256K1_API jobjectArray JNICALL Java_org_bitcoin_NativeSecp256k1_secp256k1_1pubkey_1tweak_1add - (JNIEnv *, jclass, jobject, jlong, jint); - -/* - * Class: org_bitcoin_NativeSecp256k1 - * Method: secp256k1_pubkey_tweak_mul - * Signature: (Ljava/nio/ByteBuffer;JI)[[B - */ -SECP256K1_API jobjectArray JNICALL Java_org_bitcoin_NativeSecp256k1_secp256k1_1pubkey_1tweak_1mul - (JNIEnv *, jclass, jobject, jlong, jint); - -/* - * Class: org_bitcoin_NativeSecp256k1 - * Method: secp256k1_destroy_context - * Signature: (J)V - */ -SECP256K1_API void JNICALL Java_org_bitcoin_NativeSecp256k1_secp256k1_1destroy_1context - (JNIEnv *, jclass, jlong); - -/* - * Class: org_bitcoin_NativeSecp256k1 - * Method: secp256k1_ecdsa_verify - * Signature: (Ljava/nio/ByteBuffer;JII)I - */ -SECP256K1_API jint JNICALL Java_org_bitcoin_NativeSecp256k1_secp256k1_1ecdsa_1verify - (JNIEnv *, jclass, jobject, jlong, jint, jint); - -/* - * Class: org_bitcoin_NativeSecp256k1 - * Method: secp256k1_ecdsa_sign - * Signature: (Ljava/nio/ByteBuffer;J)[[B - */ -SECP256K1_API jobjectArray JNICALL Java_org_bitcoin_NativeSecp256k1_secp256k1_1ecdsa_1sign - (JNIEnv *, jclass, jobject, jlong); - -/* - * Class: org_bitcoin_NativeSecp256k1 - * Method: secp256k1_ec_seckey_verify - * Signature: (Ljava/nio/ByteBuffer;J)I - */ -SECP256K1_API jint JNICALL Java_org_bitcoin_NativeSecp256k1_secp256k1_1ec_1seckey_1verify - (JNIEnv *, jclass, jobject, jlong); - -/* - * Class: org_bitcoin_NativeSecp256k1 - * Method: secp256k1_ec_pubkey_create - * Signature: (Ljava/nio/ByteBuffer;J)[[B - */ -SECP256K1_API jobjectArray JNICALL Java_org_bitcoin_NativeSecp256k1_secp256k1_1ec_1pubkey_1create - (JNIEnv *, jclass, jobject, jlong); - -/* - * Class: org_bitcoin_NativeSecp256k1 - * Method: secp256k1_ec_pubkey_parse - * Signature: (Ljava/nio/ByteBuffer;JI)[[B - */ -SECP256K1_API jobjectArray JNICALL Java_org_bitcoin_NativeSecp256k1_secp256k1_1ec_1pubkey_1parse - (JNIEnv *, jclass, jobject, jlong, jint); - -/* - * Class: org_bitcoin_NativeSecp256k1 - * Method: secp256k1_ecdh - * Signature: (Ljava/nio/ByteBuffer;JI)[[B - */ -SECP256K1_API jobjectArray JNICALL Java_org_bitcoin_NativeSecp256k1_secp256k1_1ecdh - (JNIEnv* env, jclass classObject, jobject byteBufferObject, jlong ctx_l, jint publen); - - -#ifdef __cplusplus -} -#endif -#endif diff --git a/src/java/org_bitcoin_Secp256k1Context.c b/src/java/org_bitcoin_Secp256k1Context.c deleted file mode 100644 index a52939e7e7..0000000000 --- a/src/java/org_bitcoin_Secp256k1Context.c +++ /dev/null @@ -1,15 +0,0 @@ -#include <stdlib.h> -#include <stdint.h> -#include "org_bitcoin_Secp256k1Context.h" -#include "include/secp256k1.h" - -SECP256K1_API jlong JNICALL Java_org_bitcoin_Secp256k1Context_secp256k1_1init_1context - (JNIEnv* env, jclass classObject) -{ - secp256k1_context *ctx = secp256k1_context_create(SECP256K1_CONTEXT_SIGN | SECP256K1_CONTEXT_VERIFY); - - (void)classObject;(void)env; - - return (uintptr_t)ctx; -} - diff --git a/src/java/org_bitcoin_Secp256k1Context.h b/src/java/org_bitcoin_Secp256k1Context.h deleted file mode 100644 index 0d2bc84b7f..0000000000 --- a/src/java/org_bitcoin_Secp256k1Context.h +++ /dev/null @@ -1,22 +0,0 @@ -/* DO NOT EDIT THIS FILE - it is machine generated */ -#include <jni.h> -#include "include/secp256k1.h" -/* Header for class org_bitcoin_Secp256k1Context */ - -#ifndef _Included_org_bitcoin_Secp256k1Context -#define _Included_org_bitcoin_Secp256k1Context -#ifdef __cplusplus -extern "C" { -#endif -/* - * Class: org_bitcoin_Secp256k1Context - * Method: secp256k1_init_context - * Signature: ()J - */ -SECP256K1_API jlong JNICALL Java_org_bitcoin_Secp256k1Context_secp256k1_1init_1context - (JNIEnv *, jclass); - -#ifdef __cplusplus -} -#endif -#endif diff --git a/src/modules/ecdh/main_impl.h b/src/modules/ecdh/main_impl.h index 44cb68e750..07a25b80d4 100644 --- a/src/modules/ecdh/main_impl.h +++ b/src/modules/ecdh/main_impl.h @@ -10,14 +10,14 @@ #include "include/secp256k1_ecdh.h" #include "ecmult_const_impl.h" -static int ecdh_hash_function_sha256(unsigned char *output, const unsigned char *x, const unsigned char *y, void *data) { - unsigned char version = (y[31] & 0x01) | 0x02; +static int ecdh_hash_function_sha256(unsigned char *output, const unsigned char *x32, const unsigned char *y32, void *data) { + unsigned char version = (y32[31] & 0x01) | 0x02; secp256k1_sha256 sha; (void)data; secp256k1_sha256_initialize(&sha); secp256k1_sha256_write(&sha, &version, 1); - secp256k1_sha256_write(&sha, x, 32); + secp256k1_sha256_write(&sha, x32, 32); secp256k1_sha256_finalize(&sha, output); return 1; @@ -32,36 +32,40 @@ int secp256k1_ecdh(const secp256k1_context* ctx, unsigned char *output, const se secp256k1_gej res; secp256k1_ge pt; secp256k1_scalar s; + unsigned char x[32]; + unsigned char y[32]; + VERIFY_CHECK(ctx != NULL); ARG_CHECK(output != NULL); ARG_CHECK(point != NULL); ARG_CHECK(scalar != NULL); + if (hashfp == NULL) { hashfp = secp256k1_ecdh_hash_function_default; } secp256k1_pubkey_load(ctx, &pt, point); secp256k1_scalar_set_b32(&s, scalar, &overflow); - if (overflow || secp256k1_scalar_is_zero(&s)) { - ret = 0; - } else { - unsigned char x[32]; - unsigned char y[32]; - - secp256k1_ecmult_const(&res, &pt, &s, 256); - secp256k1_ge_set_gej(&pt, &res); - - /* Compute a hash of the point */ - secp256k1_fe_normalize(&pt.x); - secp256k1_fe_normalize(&pt.y); - secp256k1_fe_get_b32(x, &pt.x); - secp256k1_fe_get_b32(y, &pt.y); - - ret = hashfp(output, x, y, data); - } + overflow |= secp256k1_scalar_is_zero(&s); + secp256k1_scalar_cmov(&s, &secp256k1_scalar_one, overflow); + + secp256k1_ecmult_const(&res, &pt, &s, 256); + secp256k1_ge_set_gej(&pt, &res); + + /* Compute a hash of the point */ + secp256k1_fe_normalize(&pt.x); + secp256k1_fe_normalize(&pt.y); + secp256k1_fe_get_b32(x, &pt.x); + secp256k1_fe_get_b32(y, &pt.y); + + ret = hashfp(output, x, y, data); + + memset(x, 0, 32); + memset(y, 0, 32); secp256k1_scalar_clear(&s); - return ret; + + return !!ret & !overflow; } #endif /* SECP256K1_MODULE_ECDH_MAIN_H */ diff --git a/src/modules/recovery/main_impl.h b/src/modules/recovery/main_impl.h index 2f6691c5a1..e2576aa953 100755..100644 --- a/src/modules/recovery/main_impl.h +++ b/src/modules/recovery/main_impl.h @@ -122,48 +122,15 @@ static int secp256k1_ecdsa_sig_recover(const secp256k1_ecmult_context *ctx, cons int secp256k1_ecdsa_sign_recoverable(const secp256k1_context* ctx, secp256k1_ecdsa_recoverable_signature *signature, const unsigned char *msg32, const unsigned char *seckey, secp256k1_nonce_function noncefp, const void* noncedata) { secp256k1_scalar r, s; - secp256k1_scalar sec, non, msg; - int recid; - int ret = 0; - int overflow = 0; + int ret, recid; VERIFY_CHECK(ctx != NULL); ARG_CHECK(secp256k1_ecmult_gen_context_is_built(&ctx->ecmult_gen_ctx)); ARG_CHECK(msg32 != NULL); ARG_CHECK(signature != NULL); ARG_CHECK(seckey != NULL); - if (noncefp == NULL) { - noncefp = secp256k1_nonce_function_default; - } - secp256k1_scalar_set_b32(&sec, seckey, &overflow); - /* Fail if the secret key is invalid. */ - if (!overflow && !secp256k1_scalar_is_zero(&sec)) { - unsigned char nonce32[32]; - unsigned int count = 0; - secp256k1_scalar_set_b32(&msg, msg32, NULL); - while (1) { - ret = noncefp(nonce32, msg32, seckey, NULL, (void*)noncedata, count); - if (!ret) { - break; - } - secp256k1_scalar_set_b32(&non, nonce32, &overflow); - if (!secp256k1_scalar_is_zero(&non) && !overflow) { - if (secp256k1_ecdsa_sig_sign(&ctx->ecmult_gen_ctx, &r, &s, &sec, &msg, &non, &recid)) { - break; - } - } - count++; - } - memset(nonce32, 0, 32); - secp256k1_scalar_clear(&msg); - secp256k1_scalar_clear(&non); - secp256k1_scalar_clear(&sec); - } - if (ret) { - secp256k1_ecdsa_recoverable_signature_save(signature, &r, &s, recid); - } else { - memset(signature, 0, sizeof(*signature)); - } + ret = secp256k1_ecdsa_sign_inner(ctx, &r, &s, &recid, msg32, seckey, noncefp, noncedata); + secp256k1_ecdsa_recoverable_signature_save(signature, &r, &s, recid); return ret; } diff --git a/src/modules/recovery/tests_impl.h b/src/modules/recovery/tests_impl.h index 5c9bbe8610..38a533a755 100644 --- a/src/modules/recovery/tests_impl.h +++ b/src/modules/recovery/tests_impl.h @@ -215,7 +215,7 @@ void test_ecdsa_recovery_edge_cases(void) { }; const unsigned char sig64[64] = { /* Generated by signing the above message with nonce 'This is the nonce we will use...' - * and secret key 0 (which is not valid), resulting in recid 0. */ + * and secret key 0 (which is not valid), resulting in recid 1. */ 0x67, 0xCB, 0x28, 0x5F, 0x9C, 0xD1, 0x94, 0xE8, 0x40, 0xD6, 0x29, 0x39, 0x7A, 0xF5, 0x56, 0x96, 0x62, 0xFD, 0xE4, 0x46, 0x49, 0x99, 0x59, 0x63, diff --git a/src/scalar.h b/src/scalar.h index 59304cb66e..2a74703523 100644 --- a/src/scalar.h +++ b/src/scalar.h @@ -32,9 +32,17 @@ static unsigned int secp256k1_scalar_get_bits(const secp256k1_scalar *a, unsigne /** Access bits from a scalar. Not constant time. */ static unsigned int secp256k1_scalar_get_bits_var(const secp256k1_scalar *a, unsigned int offset, unsigned int count); -/** Set a scalar from a big endian byte array. */ +/** Set a scalar from a big endian byte array. The scalar will be reduced modulo group order `n`. + * In: bin: pointer to a 32-byte array. + * Out: r: scalar to be set. + * overflow: non-zero if the scalar was bigger or equal to `n` before reduction, zero otherwise (can be NULL). + */ static void secp256k1_scalar_set_b32(secp256k1_scalar *r, const unsigned char *bin, int *overflow); +/** Set a scalar from a big endian byte array and returns 1 if it is a valid + * seckey and 0 otherwise. */ +static int secp256k1_scalar_set_b32_seckey(secp256k1_scalar *r, const unsigned char *bin); + /** Set a scalar to an unsigned integer. */ static void secp256k1_scalar_set_int(secp256k1_scalar *r, unsigned int v); @@ -103,4 +111,7 @@ static void secp256k1_scalar_split_lambda(secp256k1_scalar *r1, secp256k1_scalar /** Multiply a and b (without taking the modulus!), divide by 2**shift, and round to the nearest integer. Shift must be at least 256. */ static void secp256k1_scalar_mul_shift_var(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b, unsigned int shift); +/** If flag is true, set *r equal to *a; otherwise leave it. Constant-time. Both *r and *a must be initialized.*/ +static void secp256k1_scalar_cmov(secp256k1_scalar *r, const secp256k1_scalar *a, int flag); + #endif /* SECP256K1_SCALAR_H */ diff --git a/src/scalar_4x64_impl.h b/src/scalar_4x64_impl.h index d378335d99..8f539c4bc6 100644 --- a/src/scalar_4x64_impl.h +++ b/src/scalar_4x64_impl.h @@ -946,4 +946,15 @@ SECP256K1_INLINE static void secp256k1_scalar_mul_shift_var(secp256k1_scalar *r, secp256k1_scalar_cadd_bit(r, 0, (l[(shift - 1) >> 6] >> ((shift - 1) & 0x3f)) & 1); } +static SECP256K1_INLINE void secp256k1_scalar_cmov(secp256k1_scalar *r, const secp256k1_scalar *a, int flag) { + uint64_t mask0, mask1; + VG_CHECK_VERIFY(r->d, sizeof(r->d)); + mask0 = flag + ~((uint64_t)0); + mask1 = ~mask0; + r->d[0] = (r->d[0] & mask0) | (a->d[0] & mask1); + r->d[1] = (r->d[1] & mask0) | (a->d[1] & mask1); + r->d[2] = (r->d[2] & mask0) | (a->d[2] & mask1); + r->d[3] = (r->d[3] & mask0) | (a->d[3] & mask1); +} + #endif /* SECP256K1_SCALAR_REPR_IMPL_H */ diff --git a/src/scalar_8x32_impl.h b/src/scalar_8x32_impl.h index 4f9ed61fea..3c372f34fe 100644 --- a/src/scalar_8x32_impl.h +++ b/src/scalar_8x32_impl.h @@ -718,4 +718,19 @@ SECP256K1_INLINE static void secp256k1_scalar_mul_shift_var(secp256k1_scalar *r, secp256k1_scalar_cadd_bit(r, 0, (l[(shift - 1) >> 5] >> ((shift - 1) & 0x1f)) & 1); } +static SECP256K1_INLINE void secp256k1_scalar_cmov(secp256k1_scalar *r, const secp256k1_scalar *a, int flag) { + uint32_t mask0, mask1; + VG_CHECK_VERIFY(r->d, sizeof(r->d)); + mask0 = flag + ~((uint32_t)0); + mask1 = ~mask0; + r->d[0] = (r->d[0] & mask0) | (a->d[0] & mask1); + r->d[1] = (r->d[1] & mask0) | (a->d[1] & mask1); + r->d[2] = (r->d[2] & mask0) | (a->d[2] & mask1); + r->d[3] = (r->d[3] & mask0) | (a->d[3] & mask1); + r->d[4] = (r->d[4] & mask0) | (a->d[4] & mask1); + r->d[5] = (r->d[5] & mask0) | (a->d[5] & mask1); + r->d[6] = (r->d[6] & mask0) | (a->d[6] & mask1); + r->d[7] = (r->d[7] & mask0) | (a->d[7] & mask1); +} + #endif /* SECP256K1_SCALAR_REPR_IMPL_H */ diff --git a/src/scalar_impl.h b/src/scalar_impl.h index fa790570ff..70cd73db06 100644 --- a/src/scalar_impl.h +++ b/src/scalar_impl.h @@ -7,8 +7,8 @@ #ifndef SECP256K1_SCALAR_IMPL_H #define SECP256K1_SCALAR_IMPL_H -#include "group.h" #include "scalar.h" +#include "util.h" #if defined HAVE_CONFIG_H #include "libsecp256k1-config.h" @@ -24,6 +24,9 @@ #error "Please select scalar implementation" #endif +static const secp256k1_scalar secp256k1_scalar_one = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 1); +static const secp256k1_scalar secp256k1_scalar_zero = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0); + #ifndef USE_NUM_NONE static void secp256k1_scalar_get_num(secp256k1_num *r, const secp256k1_scalar *a) { unsigned char c[32]; @@ -52,6 +55,12 @@ static void secp256k1_scalar_order_get_num(secp256k1_num *r) { } #endif +static int secp256k1_scalar_set_b32_seckey(secp256k1_scalar *r, const unsigned char *bin) { + int overflow; + secp256k1_scalar_set_b32(r, bin, &overflow); + return (!overflow) & (!secp256k1_scalar_is_zero(r)); +} + static void secp256k1_scalar_inverse(secp256k1_scalar *r, const secp256k1_scalar *x) { #if defined(EXHAUSTIVE_TEST_ORDER) int i; diff --git a/src/scalar_low.h b/src/scalar_low.h index 5836febc5b..2794a7f171 100644 --- a/src/scalar_low.h +++ b/src/scalar_low.h @@ -12,4 +12,6 @@ /** A scalar modulo the group order of the secp256k1 curve. */ typedef uint32_t secp256k1_scalar; +#define SECP256K1_SCALAR_CONST(d7, d6, d5, d4, d3, d2, d1, d0) (d0) + #endif /* SECP256K1_SCALAR_REPR_H */ diff --git a/src/scalar_low_impl.h b/src/scalar_low_impl.h index c80e70c5a2..b79cf1ff6c 100644 --- a/src/scalar_low_impl.h +++ b/src/scalar_low_impl.h @@ -38,8 +38,11 @@ static int secp256k1_scalar_add(secp256k1_scalar *r, const secp256k1_scalar *a, static void secp256k1_scalar_cadd_bit(secp256k1_scalar *r, unsigned int bit, int flag) { if (flag && bit < 32) - *r += (1 << bit); + *r += ((uint32_t)1 << bit); #ifdef VERIFY + VERIFY_CHECK(bit < 32); + /* Verify that adding (1 << bit) will not overflow any in-range scalar *r by overflowing the underlying uint32_t. */ + VERIFY_CHECK(((uint32_t)1 << bit) - 1 <= UINT32_MAX - EXHAUSTIVE_TEST_ORDER); VERIFY_CHECK(secp256k1_scalar_check_overflow(r) == 0); #endif } @@ -111,4 +114,12 @@ SECP256K1_INLINE static int secp256k1_scalar_eq(const secp256k1_scalar *a, const return *a == *b; } +static SECP256K1_INLINE void secp256k1_scalar_cmov(secp256k1_scalar *r, const secp256k1_scalar *a, int flag) { + uint32_t mask0, mask1; + VG_CHECK_VERIFY(r, sizeof(*r)); + mask0 = flag + ~((uint32_t)0); + mask1 = ~mask0; + *r = (*r & mask0) | (*a & mask1); +} + #endif /* SECP256K1_SCALAR_REPR_IMPL_H */ diff --git a/src/scratch.h b/src/scratch.h index fef377af0d..77b35d126b 100644 --- a/src/scratch.h +++ b/src/scratch.h @@ -7,33 +7,36 @@ #ifndef _SECP256K1_SCRATCH_ #define _SECP256K1_SCRATCH_ -#define SECP256K1_SCRATCH_MAX_FRAMES 5 - /* The typedef is used internally; the struct name is used in the public API * (where it is exposed as a different typedef) */ typedef struct secp256k1_scratch_space_struct { - void *data[SECP256K1_SCRATCH_MAX_FRAMES]; - size_t offset[SECP256K1_SCRATCH_MAX_FRAMES]; - size_t frame_size[SECP256K1_SCRATCH_MAX_FRAMES]; - size_t frame; + /** guard against interpreting this object as other types */ + unsigned char magic[8]; + /** actual allocated data */ + void *data; + /** amount that has been allocated (i.e. `data + offset` is the next + * available pointer) */ + size_t alloc_size; + /** maximum size available to allocate */ size_t max_size; - const secp256k1_callback* error_callback; } secp256k1_scratch; static secp256k1_scratch* secp256k1_scratch_create(const secp256k1_callback* error_callback, size_t max_size); -static void secp256k1_scratch_destroy(secp256k1_scratch* scratch); +static void secp256k1_scratch_destroy(const secp256k1_callback* error_callback, secp256k1_scratch* scratch); -/** Attempts to allocate a new stack frame with `n` available bytes. Returns 1 on success, 0 on failure */ -static int secp256k1_scratch_allocate_frame(secp256k1_scratch* scratch, size_t n, size_t objects); +/** Returns an opaque object used to "checkpoint" a scratch space. Used + * with `secp256k1_scratch_apply_checkpoint` to undo allocations. */ +static size_t secp256k1_scratch_checkpoint(const secp256k1_callback* error_callback, const secp256k1_scratch* scratch); -/** Deallocates a stack frame */ -static void secp256k1_scratch_deallocate_frame(secp256k1_scratch* scratch); +/** Applies a check point received from `secp256k1_scratch_checkpoint`, + * undoing all allocations since that point. */ +static void secp256k1_scratch_apply_checkpoint(const secp256k1_callback* error_callback, secp256k1_scratch* scratch, size_t checkpoint); /** Returns the maximum allocation the scratch space will allow */ -static size_t secp256k1_scratch_max_allocation(const secp256k1_scratch* scratch, size_t n_objects); +static size_t secp256k1_scratch_max_allocation(const secp256k1_callback* error_callback, const secp256k1_scratch* scratch, size_t n_objects); /** Returns a pointer into the most recently allocated frame, or NULL if there is insufficient available space */ -static void *secp256k1_scratch_alloc(secp256k1_scratch* scratch, size_t n); +static void *secp256k1_scratch_alloc(const secp256k1_callback* error_callback, secp256k1_scratch* scratch, size_t n); #endif diff --git a/src/scratch_impl.h b/src/scratch_impl.h index abed713b21..4cee700001 100644 --- a/src/scratch_impl.h +++ b/src/scratch_impl.h @@ -7,78 +7,80 @@ #ifndef _SECP256K1_SCRATCH_IMPL_H_ #define _SECP256K1_SCRATCH_IMPL_H_ +#include "util.h" #include "scratch.h" -/* Using 16 bytes alignment because common architectures never have alignment - * requirements above 8 for any of the types we care about. In addition we - * leave some room because currently we don't care about a few bytes. - * TODO: Determine this at configure time. */ -#define ALIGNMENT 16 - -static secp256k1_scratch* secp256k1_scratch_create(const secp256k1_callback* error_callback, size_t max_size) { - secp256k1_scratch* ret = (secp256k1_scratch*)checked_malloc(error_callback, sizeof(*ret)); +static secp256k1_scratch* secp256k1_scratch_create(const secp256k1_callback* error_callback, size_t size) { + const size_t base_alloc = ((sizeof(secp256k1_scratch) + ALIGNMENT - 1) / ALIGNMENT) * ALIGNMENT; + void *alloc = checked_malloc(error_callback, base_alloc + size); + secp256k1_scratch* ret = (secp256k1_scratch *)alloc; if (ret != NULL) { memset(ret, 0, sizeof(*ret)); - ret->max_size = max_size; - ret->error_callback = error_callback; + memcpy(ret->magic, "scratch", 8); + ret->data = (void *) ((char *) alloc + base_alloc); + ret->max_size = size; } return ret; } -static void secp256k1_scratch_destroy(secp256k1_scratch* scratch) { +static void secp256k1_scratch_destroy(const secp256k1_callback* error_callback, secp256k1_scratch* scratch) { if (scratch != NULL) { - VERIFY_CHECK(scratch->frame == 0); + VERIFY_CHECK(scratch->alloc_size == 0); /* all checkpoints should be applied */ + if (memcmp(scratch->magic, "scratch", 8) != 0) { + secp256k1_callback_call(error_callback, "invalid scratch space"); + return; + } + memset(scratch->magic, 0, sizeof(scratch->magic)); free(scratch); } } -static size_t secp256k1_scratch_max_allocation(const secp256k1_scratch* scratch, size_t objects) { - size_t i = 0; - size_t allocated = 0; - for (i = 0; i < scratch->frame; i++) { - allocated += scratch->frame_size[i]; - } - if (scratch->max_size - allocated <= objects * ALIGNMENT) { +static size_t secp256k1_scratch_checkpoint(const secp256k1_callback* error_callback, const secp256k1_scratch* scratch) { + if (memcmp(scratch->magic, "scratch", 8) != 0) { + secp256k1_callback_call(error_callback, "invalid scratch space"); return 0; } - return scratch->max_size - allocated - objects * ALIGNMENT; + return scratch->alloc_size; } -static int secp256k1_scratch_allocate_frame(secp256k1_scratch* scratch, size_t n, size_t objects) { - VERIFY_CHECK(scratch->frame < SECP256K1_SCRATCH_MAX_FRAMES); - - if (n <= secp256k1_scratch_max_allocation(scratch, objects)) { - n += objects * ALIGNMENT; - scratch->data[scratch->frame] = checked_malloc(scratch->error_callback, n); - if (scratch->data[scratch->frame] == NULL) { - return 0; - } - scratch->frame_size[scratch->frame] = n; - scratch->offset[scratch->frame] = 0; - scratch->frame++; - return 1; - } else { - return 0; +static void secp256k1_scratch_apply_checkpoint(const secp256k1_callback* error_callback, secp256k1_scratch* scratch, size_t checkpoint) { + if (memcmp(scratch->magic, "scratch", 8) != 0) { + secp256k1_callback_call(error_callback, "invalid scratch space"); + return; + } + if (checkpoint > scratch->alloc_size) { + secp256k1_callback_call(error_callback, "invalid checkpoint"); + return; } + scratch->alloc_size = checkpoint; } -static void secp256k1_scratch_deallocate_frame(secp256k1_scratch* scratch) { - VERIFY_CHECK(scratch->frame > 0); - scratch->frame -= 1; - free(scratch->data[scratch->frame]); +static size_t secp256k1_scratch_max_allocation(const secp256k1_callback* error_callback, const secp256k1_scratch* scratch, size_t objects) { + if (memcmp(scratch->magic, "scratch", 8) != 0) { + secp256k1_callback_call(error_callback, "invalid scratch space"); + return 0; + } + if (scratch->max_size - scratch->alloc_size <= objects * (ALIGNMENT - 1)) { + return 0; + } + return scratch->max_size - scratch->alloc_size - objects * (ALIGNMENT - 1); } -static void *secp256k1_scratch_alloc(secp256k1_scratch* scratch, size_t size) { +static void *secp256k1_scratch_alloc(const secp256k1_callback* error_callback, secp256k1_scratch* scratch, size_t size) { void *ret; - size_t frame = scratch->frame - 1; - size = ((size + ALIGNMENT - 1) / ALIGNMENT) * ALIGNMENT; + size = ROUND_TO_ALIGN(size); + + if (memcmp(scratch->magic, "scratch", 8) != 0) { + secp256k1_callback_call(error_callback, "invalid scratch space"); + return NULL; + } - if (scratch->frame == 0 || size + scratch->offset[frame] > scratch->frame_size[frame]) { + if (size > scratch->max_size - scratch->alloc_size) { return NULL; } - ret = (void *) ((unsigned char *) scratch->data[frame] + scratch->offset[frame]); + ret = (void *) ((char *) scratch->data + scratch->alloc_size); memset(ret, 0, size); - scratch->offset[frame] += size; + scratch->alloc_size += size; return ret; } diff --git a/src/secp256k1.c b/src/secp256k1.c index 15981f46e2..b03a6e6345 100644 --- a/src/secp256k1.c +++ b/src/secp256k1.c @@ -5,6 +5,7 @@ **********************************************************************/ #include "include/secp256k1.h" +#include "include/secp256k1_preallocated.h" #include "util.h" #include "num_impl.h" @@ -19,6 +20,10 @@ #include "hash_impl.h" #include "scratch_impl.h" +#if defined(VALGRIND) +# include <valgrind/memcheck.h> +#endif + #define ARG_CHECK(cond) do { \ if (EXPECT(!(cond), 0)) { \ secp256k1_callback_call(&ctx->illegal_callback, #cond); \ @@ -26,53 +31,101 @@ } \ } while(0) -static void default_illegal_callback_fn(const char* str, void* data) { +#define ARG_CHECK_NO_RETURN(cond) do { \ + if (EXPECT(!(cond), 0)) { \ + secp256k1_callback_call(&ctx->illegal_callback, #cond); \ + } \ +} while(0) + +#ifndef USE_EXTERNAL_DEFAULT_CALLBACKS +#include <stdlib.h> +#include <stdio.h> +static void secp256k1_default_illegal_callback_fn(const char* str, void* data) { (void)data; fprintf(stderr, "[libsecp256k1] illegal argument: %s\n", str); abort(); } - -static const secp256k1_callback default_illegal_callback = { - default_illegal_callback_fn, - NULL -}; - -static void default_error_callback_fn(const char* str, void* data) { +static void secp256k1_default_error_callback_fn(const char* str, void* data) { (void)data; fprintf(stderr, "[libsecp256k1] internal consistency check failed: %s\n", str); abort(); } +#else +void secp256k1_default_illegal_callback_fn(const char* str, void* data); +void secp256k1_default_error_callback_fn(const char* str, void* data); +#endif -static const secp256k1_callback default_error_callback = { - default_error_callback_fn, +static const secp256k1_callback default_illegal_callback = { + secp256k1_default_illegal_callback_fn, NULL }; +static const secp256k1_callback default_error_callback = { + secp256k1_default_error_callback_fn, + NULL +}; struct secp256k1_context_struct { secp256k1_ecmult_context ecmult_ctx; secp256k1_ecmult_gen_context ecmult_gen_ctx; secp256k1_callback illegal_callback; secp256k1_callback error_callback; + int declassify; }; static const secp256k1_context secp256k1_context_no_precomp_ = { { 0 }, { 0 }, - { default_illegal_callback_fn, 0 }, - { default_error_callback_fn, 0 } + { secp256k1_default_illegal_callback_fn, 0 }, + { secp256k1_default_error_callback_fn, 0 }, + 0 }; const secp256k1_context *secp256k1_context_no_precomp = &secp256k1_context_no_precomp_; -secp256k1_context* secp256k1_context_create(unsigned int flags) { - secp256k1_context* ret = (secp256k1_context*)checked_malloc(&default_error_callback, sizeof(secp256k1_context)); +size_t secp256k1_context_preallocated_size(unsigned int flags) { + size_t ret = ROUND_TO_ALIGN(sizeof(secp256k1_context)); + + if (EXPECT((flags & SECP256K1_FLAGS_TYPE_MASK) != SECP256K1_FLAGS_TYPE_CONTEXT, 0)) { + secp256k1_callback_call(&default_illegal_callback, + "Invalid flags"); + return 0; + } + + if (flags & SECP256K1_FLAGS_BIT_CONTEXT_SIGN) { + ret += SECP256K1_ECMULT_GEN_CONTEXT_PREALLOCATED_SIZE; + } + if (flags & SECP256K1_FLAGS_BIT_CONTEXT_VERIFY) { + ret += SECP256K1_ECMULT_CONTEXT_PREALLOCATED_SIZE; + } + return ret; +} + +size_t secp256k1_context_preallocated_clone_size(const secp256k1_context* ctx) { + size_t ret = ROUND_TO_ALIGN(sizeof(secp256k1_context)); + VERIFY_CHECK(ctx != NULL); + if (secp256k1_ecmult_gen_context_is_built(&ctx->ecmult_gen_ctx)) { + ret += SECP256K1_ECMULT_GEN_CONTEXT_PREALLOCATED_SIZE; + } + if (secp256k1_ecmult_context_is_built(&ctx->ecmult_ctx)) { + ret += SECP256K1_ECMULT_CONTEXT_PREALLOCATED_SIZE; + } + return ret; +} + +secp256k1_context* secp256k1_context_preallocated_create(void* prealloc, unsigned int flags) { + void* const base = prealloc; + size_t prealloc_size; + secp256k1_context* ret; + + VERIFY_CHECK(prealloc != NULL); + prealloc_size = secp256k1_context_preallocated_size(flags); + ret = (secp256k1_context*)manual_alloc(&prealloc, sizeof(secp256k1_context), base, prealloc_size); ret->illegal_callback = default_illegal_callback; ret->error_callback = default_error_callback; if (EXPECT((flags & SECP256K1_FLAGS_TYPE_MASK) != SECP256K1_FLAGS_TYPE_CONTEXT, 0)) { secp256k1_callback_call(&ret->illegal_callback, "Invalid flags"); - free(ret); return NULL; } @@ -80,47 +133,80 @@ secp256k1_context* secp256k1_context_create(unsigned int flags) { secp256k1_ecmult_gen_context_init(&ret->ecmult_gen_ctx); if (flags & SECP256K1_FLAGS_BIT_CONTEXT_SIGN) { - secp256k1_ecmult_gen_context_build(&ret->ecmult_gen_ctx, &ret->error_callback); + secp256k1_ecmult_gen_context_build(&ret->ecmult_gen_ctx, &prealloc); } if (flags & SECP256K1_FLAGS_BIT_CONTEXT_VERIFY) { - secp256k1_ecmult_context_build(&ret->ecmult_ctx, &ret->error_callback); + secp256k1_ecmult_context_build(&ret->ecmult_ctx, &prealloc); + } + ret->declassify = !!(flags & SECP256K1_FLAGS_BIT_CONTEXT_DECLASSIFY); + + return (secp256k1_context*) ret; +} + +secp256k1_context* secp256k1_context_create(unsigned int flags) { + size_t const prealloc_size = secp256k1_context_preallocated_size(flags); + secp256k1_context* ctx = (secp256k1_context*)checked_malloc(&default_error_callback, prealloc_size); + if (EXPECT(secp256k1_context_preallocated_create(ctx, flags) == NULL, 0)) { + free(ctx); + return NULL; } + return ctx; +} + +secp256k1_context* secp256k1_context_preallocated_clone(const secp256k1_context* ctx, void* prealloc) { + size_t prealloc_size; + secp256k1_context* ret; + VERIFY_CHECK(ctx != NULL); + ARG_CHECK(prealloc != NULL); + + prealloc_size = secp256k1_context_preallocated_clone_size(ctx); + ret = (secp256k1_context*)prealloc; + memcpy(ret, ctx, prealloc_size); + secp256k1_ecmult_gen_context_finalize_memcpy(&ret->ecmult_gen_ctx, &ctx->ecmult_gen_ctx); + secp256k1_ecmult_context_finalize_memcpy(&ret->ecmult_ctx, &ctx->ecmult_ctx); return ret; } secp256k1_context* secp256k1_context_clone(const secp256k1_context* ctx) { - secp256k1_context* ret = (secp256k1_context*)checked_malloc(&ctx->error_callback, sizeof(secp256k1_context)); - ret->illegal_callback = ctx->illegal_callback; - ret->error_callback = ctx->error_callback; - secp256k1_ecmult_context_clone(&ret->ecmult_ctx, &ctx->ecmult_ctx, &ctx->error_callback); - secp256k1_ecmult_gen_context_clone(&ret->ecmult_gen_ctx, &ctx->ecmult_gen_ctx, &ctx->error_callback); + secp256k1_context* ret; + size_t prealloc_size; + + VERIFY_CHECK(ctx != NULL); + prealloc_size = secp256k1_context_preallocated_clone_size(ctx); + ret = (secp256k1_context*)checked_malloc(&ctx->error_callback, prealloc_size); + ret = secp256k1_context_preallocated_clone(ctx, ret); return ret; } -void secp256k1_context_destroy(secp256k1_context* ctx) { - CHECK(ctx != secp256k1_context_no_precomp); +void secp256k1_context_preallocated_destroy(secp256k1_context* ctx) { + ARG_CHECK_NO_RETURN(ctx != secp256k1_context_no_precomp); if (ctx != NULL) { secp256k1_ecmult_context_clear(&ctx->ecmult_ctx); secp256k1_ecmult_gen_context_clear(&ctx->ecmult_gen_ctx); + } +} +void secp256k1_context_destroy(secp256k1_context* ctx) { + if (ctx != NULL) { + secp256k1_context_preallocated_destroy(ctx); free(ctx); } } void secp256k1_context_set_illegal_callback(secp256k1_context* ctx, void (*fun)(const char* message, void* data), const void* data) { - CHECK(ctx != secp256k1_context_no_precomp); + ARG_CHECK_NO_RETURN(ctx != secp256k1_context_no_precomp); if (fun == NULL) { - fun = default_illegal_callback_fn; + fun = secp256k1_default_illegal_callback_fn; } ctx->illegal_callback.fn = fun; ctx->illegal_callback.data = data; } void secp256k1_context_set_error_callback(secp256k1_context* ctx, void (*fun)(const char* message, void* data), const void* data) { - CHECK(ctx != secp256k1_context_no_precomp); + ARG_CHECK_NO_RETURN(ctx != secp256k1_context_no_precomp); if (fun == NULL) { - fun = default_error_callback_fn; + fun = secp256k1_default_error_callback_fn; } ctx->error_callback.fn = fun; ctx->error_callback.data = data; @@ -131,8 +217,23 @@ secp256k1_scratch_space* secp256k1_scratch_space_create(const secp256k1_context* return secp256k1_scratch_create(&ctx->error_callback, max_size); } -void secp256k1_scratch_space_destroy(secp256k1_scratch_space* scratch) { - secp256k1_scratch_destroy(scratch); +void secp256k1_scratch_space_destroy(const secp256k1_context *ctx, secp256k1_scratch_space* scratch) { + VERIFY_CHECK(ctx != NULL); + secp256k1_scratch_destroy(&ctx->error_callback, scratch); +} + +/* Mark memory as no-longer-secret for the purpose of analysing constant-time behaviour + * of the software. This is setup for use with valgrind but could be substituted with + * the appropriate instrumentation for other analysis tools. + */ +static SECP256K1_INLINE void secp256k1_declassify(const secp256k1_context* ctx, void *p, size_t len) { +#if defined(VALGRIND) + if (EXPECT(ctx->declassify,0)) VALGRIND_MAKE_MEM_DEFINED(p, len); +#else + (void)ctx; + (void)p; + (void)len; +#endif } static int secp256k1_pubkey_load(const secp256k1_context* ctx, secp256k1_ge* ge, const secp256k1_pubkey* pubkey) { @@ -366,61 +467,83 @@ static int nonce_function_rfc6979(unsigned char *nonce32, const unsigned char *m const secp256k1_nonce_function secp256k1_nonce_function_rfc6979 = nonce_function_rfc6979; const secp256k1_nonce_function secp256k1_nonce_function_default = nonce_function_rfc6979; -int secp256k1_ecdsa_sign(const secp256k1_context* ctx, secp256k1_ecdsa_signature *signature, const unsigned char *msg32, const unsigned char *seckey, secp256k1_nonce_function noncefp, const void* noncedata) { - secp256k1_scalar r, s; +static int secp256k1_ecdsa_sign_inner(const secp256k1_context* ctx, secp256k1_scalar* r, secp256k1_scalar* s, int* recid, const unsigned char *msg32, const unsigned char *seckey, secp256k1_nonce_function noncefp, const void* noncedata) { secp256k1_scalar sec, non, msg; int ret = 0; - int overflow = 0; - VERIFY_CHECK(ctx != NULL); - ARG_CHECK(secp256k1_ecmult_gen_context_is_built(&ctx->ecmult_gen_ctx)); - ARG_CHECK(msg32 != NULL); - ARG_CHECK(signature != NULL); - ARG_CHECK(seckey != NULL); + int is_sec_valid; + unsigned char nonce32[32]; + unsigned int count = 0; + /* Default initialization here is important so we won't pass uninit values to the cmov in the end */ + *r = secp256k1_scalar_zero; + *s = secp256k1_scalar_zero; + if (recid) { + *recid = 0; + } if (noncefp == NULL) { noncefp = secp256k1_nonce_function_default; } - secp256k1_scalar_set_b32(&sec, seckey, &overflow); /* Fail if the secret key is invalid. */ - if (!overflow && !secp256k1_scalar_is_zero(&sec)) { - unsigned char nonce32[32]; - unsigned int count = 0; - secp256k1_scalar_set_b32(&msg, msg32, NULL); - while (1) { - ret = noncefp(nonce32, msg32, seckey, NULL, (void*)noncedata, count); - if (!ret) { + is_sec_valid = secp256k1_scalar_set_b32_seckey(&sec, seckey); + secp256k1_scalar_cmov(&sec, &secp256k1_scalar_one, !is_sec_valid); + secp256k1_scalar_set_b32(&msg, msg32, NULL); + while (1) { + int is_nonce_valid; + ret = !!noncefp(nonce32, msg32, seckey, NULL, (void*)noncedata, count); + if (!ret) { + break; + } + is_nonce_valid = secp256k1_scalar_set_b32_seckey(&non, nonce32); + /* The nonce is still secret here, but it being invalid is is less likely than 1:2^255. */ + secp256k1_declassify(ctx, &is_nonce_valid, sizeof(is_nonce_valid)); + if (is_nonce_valid) { + ret = secp256k1_ecdsa_sig_sign(&ctx->ecmult_gen_ctx, r, s, &sec, &msg, &non, recid); + /* The final signature is no longer a secret, nor is the fact that we were successful or not. */ + secp256k1_declassify(ctx, &ret, sizeof(ret)); + if (ret) { break; } - secp256k1_scalar_set_b32(&non, nonce32, &overflow); - if (!overflow && !secp256k1_scalar_is_zero(&non)) { - if (secp256k1_ecdsa_sig_sign(&ctx->ecmult_gen_ctx, &r, &s, &sec, &msg, &non, NULL)) { - break; - } - } - count++; } - memset(nonce32, 0, 32); - secp256k1_scalar_clear(&msg); - secp256k1_scalar_clear(&non); - secp256k1_scalar_clear(&sec); + count++; } - if (ret) { - secp256k1_ecdsa_signature_save(signature, &r, &s); - } else { - memset(signature, 0, sizeof(*signature)); + /* We don't want to declassify is_sec_valid and therefore the range of + * seckey. As a result is_sec_valid is included in ret only after ret was + * used as a branching variable. */ + ret &= is_sec_valid; + memset(nonce32, 0, 32); + secp256k1_scalar_clear(&msg); + secp256k1_scalar_clear(&non); + secp256k1_scalar_clear(&sec); + secp256k1_scalar_cmov(r, &secp256k1_scalar_zero, !ret); + secp256k1_scalar_cmov(s, &secp256k1_scalar_zero, !ret); + if (recid) { + const int zero = 0; + secp256k1_int_cmov(recid, &zero, !ret); } return ret; } +int secp256k1_ecdsa_sign(const secp256k1_context* ctx, secp256k1_ecdsa_signature *signature, const unsigned char *msg32, const unsigned char *seckey, secp256k1_nonce_function noncefp, const void* noncedata) { + secp256k1_scalar r, s; + int ret; + VERIFY_CHECK(ctx != NULL); + ARG_CHECK(secp256k1_ecmult_gen_context_is_built(&ctx->ecmult_gen_ctx)); + ARG_CHECK(msg32 != NULL); + ARG_CHECK(signature != NULL); + ARG_CHECK(seckey != NULL); + + ret = secp256k1_ecdsa_sign_inner(ctx, &r, &s, NULL, msg32, seckey, noncefp, noncedata); + secp256k1_ecdsa_signature_save(signature, &r, &s); + return ret; +} + int secp256k1_ec_seckey_verify(const secp256k1_context* ctx, const unsigned char *seckey) { secp256k1_scalar sec; int ret; - int overflow; VERIFY_CHECK(ctx != NULL); ARG_CHECK(seckey != NULL); - secp256k1_scalar_set_b32(&sec, seckey, &overflow); - ret = !overflow && !secp256k1_scalar_is_zero(&sec); + ret = secp256k1_scalar_set_b32_seckey(&sec, seckey); secp256k1_scalar_clear(&sec); return ret; } @@ -429,7 +552,6 @@ int secp256k1_ec_pubkey_create(const secp256k1_context* ctx, secp256k1_pubkey *p secp256k1_gej pj; secp256k1_ge p; secp256k1_scalar sec; - int overflow; int ret = 0; VERIFY_CHECK(ctx != NULL); ARG_CHECK(pubkey != NULL); @@ -437,27 +559,35 @@ int secp256k1_ec_pubkey_create(const secp256k1_context* ctx, secp256k1_pubkey *p ARG_CHECK(secp256k1_ecmult_gen_context_is_built(&ctx->ecmult_gen_ctx)); ARG_CHECK(seckey != NULL); - secp256k1_scalar_set_b32(&sec, seckey, &overflow); - ret = (!overflow) & (!secp256k1_scalar_is_zero(&sec)); - if (ret) { - secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &pj, &sec); - secp256k1_ge_set_gej(&p, &pj); - secp256k1_pubkey_save(pubkey, &p); - } + ret = secp256k1_scalar_set_b32_seckey(&sec, seckey); + secp256k1_scalar_cmov(&sec, &secp256k1_scalar_one, !ret); + + secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &pj, &sec); + secp256k1_ge_set_gej(&p, &pj); + secp256k1_pubkey_save(pubkey, &p); + memczero(pubkey, sizeof(*pubkey), !ret); + secp256k1_scalar_clear(&sec); return ret; } -int secp256k1_ec_privkey_negate(const secp256k1_context* ctx, unsigned char *seckey) { +int secp256k1_ec_seckey_negate(const secp256k1_context* ctx, unsigned char *seckey) { secp256k1_scalar sec; + int ret = 0; VERIFY_CHECK(ctx != NULL); ARG_CHECK(seckey != NULL); - secp256k1_scalar_set_b32(&sec, seckey, NULL); + ret = secp256k1_scalar_set_b32_seckey(&sec, seckey); + secp256k1_scalar_cmov(&sec, &secp256k1_scalar_zero, !ret); secp256k1_scalar_negate(&sec, &sec); secp256k1_scalar_get_b32(seckey, &sec); - return 1; + secp256k1_scalar_clear(&sec); + return ret; +} + +int secp256k1_ec_privkey_negate(const secp256k1_context* ctx, unsigned char *seckey) { + return secp256k1_ec_seckey_negate(ctx, seckey); } int secp256k1_ec_pubkey_negate(const secp256k1_context* ctx, secp256k1_pubkey *pubkey) { @@ -475,7 +605,7 @@ int secp256k1_ec_pubkey_negate(const secp256k1_context* ctx, secp256k1_pubkey *p return ret; } -int secp256k1_ec_privkey_tweak_add(const secp256k1_context* ctx, unsigned char *seckey, const unsigned char *tweak) { +int secp256k1_ec_seckey_tweak_add(const secp256k1_context* ctx, unsigned char *seckey, const unsigned char *tweak) { secp256k1_scalar term; secp256k1_scalar sec; int ret = 0; @@ -485,19 +615,21 @@ int secp256k1_ec_privkey_tweak_add(const secp256k1_context* ctx, unsigned char * ARG_CHECK(tweak != NULL); secp256k1_scalar_set_b32(&term, tweak, &overflow); - secp256k1_scalar_set_b32(&sec, seckey, NULL); + ret = secp256k1_scalar_set_b32_seckey(&sec, seckey); - ret = !overflow && secp256k1_eckey_privkey_tweak_add(&sec, &term); - memset(seckey, 0, 32); - if (ret) { - secp256k1_scalar_get_b32(seckey, &sec); - } + ret &= (!overflow) & secp256k1_eckey_privkey_tweak_add(&sec, &term); + secp256k1_scalar_cmov(&sec, &secp256k1_scalar_zero, !ret); + secp256k1_scalar_get_b32(seckey, &sec); secp256k1_scalar_clear(&sec); secp256k1_scalar_clear(&term); return ret; } +int secp256k1_ec_privkey_tweak_add(const secp256k1_context* ctx, unsigned char *seckey, const unsigned char *tweak) { + return secp256k1_ec_seckey_tweak_add(ctx, seckey, tweak); +} + int secp256k1_ec_pubkey_tweak_add(const secp256k1_context* ctx, secp256k1_pubkey *pubkey, const unsigned char *tweak) { secp256k1_ge p; secp256k1_scalar term; @@ -522,7 +654,7 @@ int secp256k1_ec_pubkey_tweak_add(const secp256k1_context* ctx, secp256k1_pubkey return ret; } -int secp256k1_ec_privkey_tweak_mul(const secp256k1_context* ctx, unsigned char *seckey, const unsigned char *tweak) { +int secp256k1_ec_seckey_tweak_mul(const secp256k1_context* ctx, unsigned char *seckey, const unsigned char *tweak) { secp256k1_scalar factor; secp256k1_scalar sec; int ret = 0; @@ -532,18 +664,20 @@ int secp256k1_ec_privkey_tweak_mul(const secp256k1_context* ctx, unsigned char * ARG_CHECK(tweak != NULL); secp256k1_scalar_set_b32(&factor, tweak, &overflow); - secp256k1_scalar_set_b32(&sec, seckey, NULL); - ret = !overflow && secp256k1_eckey_privkey_tweak_mul(&sec, &factor); - memset(seckey, 0, 32); - if (ret) { - secp256k1_scalar_get_b32(seckey, &sec); - } + ret = secp256k1_scalar_set_b32_seckey(&sec, seckey); + ret &= (!overflow) & secp256k1_eckey_privkey_tweak_mul(&sec, &factor); + secp256k1_scalar_cmov(&sec, &secp256k1_scalar_zero, !ret); + secp256k1_scalar_get_b32(seckey, &sec); secp256k1_scalar_clear(&sec); secp256k1_scalar_clear(&factor); return ret; } +int secp256k1_ec_privkey_tweak_mul(const secp256k1_context* ctx, unsigned char *seckey, const unsigned char *tweak) { + return secp256k1_ec_seckey_tweak_mul(ctx, seckey, tweak); +} + int secp256k1_ec_pubkey_tweak_mul(const secp256k1_context* ctx, secp256k1_pubkey *pubkey, const unsigned char *tweak) { secp256k1_ge p; secp256k1_scalar factor; diff --git a/src/tests.c b/src/tests.c index f1c4db929a..374ed7dc12 100644 --- a/src/tests.c +++ b/src/tests.c @@ -16,6 +16,7 @@ #include "secp256k1.c" #include "include/secp256k1.h" +#include "include/secp256k1_preallocated.h" #include "testrand_impl.h" #ifdef ENABLE_OPENSSL_TESTS @@ -31,17 +32,6 @@ void ECDSA_SIG_get0(const ECDSA_SIG *sig, const BIGNUM **pr, const BIGNUM **ps) #include "contrib/lax_der_parsing.c" #include "contrib/lax_der_privatekey_parsing.c" -#if !defined(VG_CHECK) -# if defined(VALGRIND) -# include <valgrind/memcheck.h> -# define VG_UNDEF(x,y) VALGRIND_MAKE_MEM_UNDEFINED((x),(y)) -# define VG_CHECK(x,y) VALGRIND_CHECK_MEM_IS_DEFINED((x),(y)) -# else -# define VG_UNDEF(x,y) -# define VG_CHECK(x,y) -# endif -#endif - static int count = 64; static secp256k1_context *ctx = NULL; @@ -82,7 +72,9 @@ void random_field_element_magnitude(secp256k1_fe *fe) { secp256k1_fe_negate(&zero, &zero, 0); secp256k1_fe_mul_int(&zero, n - 1); secp256k1_fe_add(fe, &zero); - VERIFY_CHECK(fe->magnitude == n); +#ifdef VERIFY + CHECK(fe->magnitude == n); +#endif } void random_group_element_test(secp256k1_ge *ge) { @@ -137,23 +129,53 @@ void random_scalar_order(secp256k1_scalar *num) { } while(1); } -void run_context_tests(void) { +void random_scalar_order_b32(unsigned char *b32) { + secp256k1_scalar num; + random_scalar_order(&num); + secp256k1_scalar_get_b32(b32, &num); +} + +void run_context_tests(int use_prealloc) { secp256k1_pubkey pubkey; secp256k1_pubkey zero_pubkey; secp256k1_ecdsa_signature sig; unsigned char ctmp[32]; int32_t ecount; int32_t ecount2; - secp256k1_context *none = secp256k1_context_create(SECP256K1_CONTEXT_NONE); - secp256k1_context *sign = secp256k1_context_create(SECP256K1_CONTEXT_SIGN); - secp256k1_context *vrfy = secp256k1_context_create(SECP256K1_CONTEXT_VERIFY); - secp256k1_context *both = secp256k1_context_create(SECP256K1_CONTEXT_SIGN | SECP256K1_CONTEXT_VERIFY); + secp256k1_context *none; + secp256k1_context *sign; + secp256k1_context *vrfy; + secp256k1_context *both; + void *none_prealloc = NULL; + void *sign_prealloc = NULL; + void *vrfy_prealloc = NULL; + void *both_prealloc = NULL; secp256k1_gej pubj; secp256k1_ge pub; secp256k1_scalar msg, key, nonce; secp256k1_scalar sigr, sigs; + if (use_prealloc) { + none_prealloc = malloc(secp256k1_context_preallocated_size(SECP256K1_CONTEXT_NONE)); + sign_prealloc = malloc(secp256k1_context_preallocated_size(SECP256K1_CONTEXT_SIGN)); + vrfy_prealloc = malloc(secp256k1_context_preallocated_size(SECP256K1_CONTEXT_VERIFY)); + both_prealloc = malloc(secp256k1_context_preallocated_size(SECP256K1_CONTEXT_SIGN | SECP256K1_CONTEXT_VERIFY)); + CHECK(none_prealloc != NULL); + CHECK(sign_prealloc != NULL); + CHECK(vrfy_prealloc != NULL); + CHECK(both_prealloc != NULL); + none = secp256k1_context_preallocated_create(none_prealloc, SECP256K1_CONTEXT_NONE); + sign = secp256k1_context_preallocated_create(sign_prealloc, SECP256K1_CONTEXT_SIGN); + vrfy = secp256k1_context_preallocated_create(vrfy_prealloc, SECP256K1_CONTEXT_VERIFY); + both = secp256k1_context_preallocated_create(both_prealloc, SECP256K1_CONTEXT_SIGN | SECP256K1_CONTEXT_VERIFY); + } else { + none = secp256k1_context_create(SECP256K1_CONTEXT_NONE); + sign = secp256k1_context_create(SECP256K1_CONTEXT_SIGN); + vrfy = secp256k1_context_create(SECP256K1_CONTEXT_VERIFY); + both = secp256k1_context_create(SECP256K1_CONTEXT_SIGN | SECP256K1_CONTEXT_VERIFY); + } + memset(&zero_pubkey, 0, sizeof(zero_pubkey)); ecount = 0; @@ -163,14 +185,57 @@ void run_context_tests(void) { secp256k1_context_set_error_callback(sign, counting_illegal_callback_fn, NULL); CHECK(vrfy->error_callback.fn != sign->error_callback.fn); + /* check if sizes for cloning are consistent */ + CHECK(secp256k1_context_preallocated_clone_size(none) == secp256k1_context_preallocated_size(SECP256K1_CONTEXT_NONE)); + CHECK(secp256k1_context_preallocated_clone_size(sign) == secp256k1_context_preallocated_size(SECP256K1_CONTEXT_SIGN)); + CHECK(secp256k1_context_preallocated_clone_size(vrfy) == secp256k1_context_preallocated_size(SECP256K1_CONTEXT_VERIFY)); + CHECK(secp256k1_context_preallocated_clone_size(both) == secp256k1_context_preallocated_size(SECP256K1_CONTEXT_SIGN | SECP256K1_CONTEXT_VERIFY)); + /*** clone and destroy all of them to make sure cloning was complete ***/ { secp256k1_context *ctx_tmp; - ctx_tmp = none; none = secp256k1_context_clone(none); secp256k1_context_destroy(ctx_tmp); - ctx_tmp = sign; sign = secp256k1_context_clone(sign); secp256k1_context_destroy(ctx_tmp); - ctx_tmp = vrfy; vrfy = secp256k1_context_clone(vrfy); secp256k1_context_destroy(ctx_tmp); - ctx_tmp = both; both = secp256k1_context_clone(both); secp256k1_context_destroy(ctx_tmp); + if (use_prealloc) { + /* clone into a non-preallocated context and then again into a new preallocated one. */ + ctx_tmp = none; none = secp256k1_context_clone(none); secp256k1_context_preallocated_destroy(ctx_tmp); + free(none_prealloc); none_prealloc = malloc(secp256k1_context_preallocated_size(SECP256K1_CONTEXT_NONE)); CHECK(none_prealloc != NULL); + ctx_tmp = none; none = secp256k1_context_preallocated_clone(none, none_prealloc); secp256k1_context_destroy(ctx_tmp); + + ctx_tmp = sign; sign = secp256k1_context_clone(sign); secp256k1_context_preallocated_destroy(ctx_tmp); + free(sign_prealloc); sign_prealloc = malloc(secp256k1_context_preallocated_size(SECP256K1_CONTEXT_SIGN)); CHECK(sign_prealloc != NULL); + ctx_tmp = sign; sign = secp256k1_context_preallocated_clone(sign, sign_prealloc); secp256k1_context_destroy(ctx_tmp); + + ctx_tmp = vrfy; vrfy = secp256k1_context_clone(vrfy); secp256k1_context_preallocated_destroy(ctx_tmp); + free(vrfy_prealloc); vrfy_prealloc = malloc(secp256k1_context_preallocated_size(SECP256K1_CONTEXT_VERIFY)); CHECK(vrfy_prealloc != NULL); + ctx_tmp = vrfy; vrfy = secp256k1_context_preallocated_clone(vrfy, vrfy_prealloc); secp256k1_context_destroy(ctx_tmp); + + ctx_tmp = both; both = secp256k1_context_clone(both); secp256k1_context_preallocated_destroy(ctx_tmp); + free(both_prealloc); both_prealloc = malloc(secp256k1_context_preallocated_size(SECP256K1_CONTEXT_SIGN | SECP256K1_CONTEXT_VERIFY)); CHECK(both_prealloc != NULL); + ctx_tmp = both; both = secp256k1_context_preallocated_clone(both, both_prealloc); secp256k1_context_destroy(ctx_tmp); + } else { + /* clone into a preallocated context and then again into a new non-preallocated one. */ + void *prealloc_tmp; + + prealloc_tmp = malloc(secp256k1_context_preallocated_size(SECP256K1_CONTEXT_NONE)); CHECK(prealloc_tmp != NULL); + ctx_tmp = none; none = secp256k1_context_preallocated_clone(none, prealloc_tmp); secp256k1_context_destroy(ctx_tmp); + ctx_tmp = none; none = secp256k1_context_clone(none); secp256k1_context_preallocated_destroy(ctx_tmp); + free(prealloc_tmp); + + prealloc_tmp = malloc(secp256k1_context_preallocated_size(SECP256K1_CONTEXT_SIGN)); CHECK(prealloc_tmp != NULL); + ctx_tmp = sign; sign = secp256k1_context_preallocated_clone(sign, prealloc_tmp); secp256k1_context_destroy(ctx_tmp); + ctx_tmp = sign; sign = secp256k1_context_clone(sign); secp256k1_context_preallocated_destroy(ctx_tmp); + free(prealloc_tmp); + + prealloc_tmp = malloc(secp256k1_context_preallocated_size(SECP256K1_CONTEXT_VERIFY)); CHECK(prealloc_tmp != NULL); + ctx_tmp = vrfy; vrfy = secp256k1_context_preallocated_clone(vrfy, prealloc_tmp); secp256k1_context_destroy(ctx_tmp); + ctx_tmp = vrfy; vrfy = secp256k1_context_clone(vrfy); secp256k1_context_preallocated_destroy(ctx_tmp); + free(prealloc_tmp); + + prealloc_tmp = malloc(secp256k1_context_preallocated_size(SECP256K1_CONTEXT_SIGN | SECP256K1_CONTEXT_VERIFY)); CHECK(prealloc_tmp != NULL); + ctx_tmp = both; both = secp256k1_context_preallocated_clone(both, prealloc_tmp); secp256k1_context_destroy(ctx_tmp); + ctx_tmp = both; both = secp256k1_context_clone(both); secp256k1_context_preallocated_destroy(ctx_tmp); + free(prealloc_tmp); + } } /* Verify that the error callback makes it across the clone. */ @@ -229,10 +294,6 @@ void run_context_tests(void) { secp256k1_context_set_illegal_callback(vrfy, NULL, NULL); secp256k1_context_set_illegal_callback(sign, NULL, NULL); - /* This shouldn't leak memory, due to already-set tests. */ - secp256k1_ecmult_gen_context_build(&sign->ecmult_gen_ctx, NULL); - secp256k1_ecmult_context_build(&vrfy->ecmult_ctx, NULL); - /* obtain a working nonce */ do { random_scalar_order_test(&nonce); @@ -247,49 +308,95 @@ void run_context_tests(void) { CHECK(secp256k1_ecdsa_sig_verify(&both->ecmult_ctx, &sigr, &sigs, &pub, &msg)); /* cleanup */ - secp256k1_context_destroy(none); - secp256k1_context_destroy(sign); - secp256k1_context_destroy(vrfy); - secp256k1_context_destroy(both); + if (use_prealloc) { + secp256k1_context_preallocated_destroy(none); + secp256k1_context_preallocated_destroy(sign); + secp256k1_context_preallocated_destroy(vrfy); + secp256k1_context_preallocated_destroy(both); + free(none_prealloc); + free(sign_prealloc); + free(vrfy_prealloc); + free(both_prealloc); + } else { + secp256k1_context_destroy(none); + secp256k1_context_destroy(sign); + secp256k1_context_destroy(vrfy); + secp256k1_context_destroy(both); + } /* Defined as no-op. */ secp256k1_context_destroy(NULL); + secp256k1_context_preallocated_destroy(NULL); + } void run_scratch_tests(void) { + const size_t adj_alloc = ((500 + ALIGNMENT - 1) / ALIGNMENT) * ALIGNMENT; + int32_t ecount = 0; + size_t checkpoint; + size_t checkpoint_2; secp256k1_context *none = secp256k1_context_create(SECP256K1_CONTEXT_NONE); secp256k1_scratch_space *scratch; + secp256k1_scratch_space local_scratch; /* Test public API */ secp256k1_context_set_illegal_callback(none, counting_illegal_callback_fn, &ecount); + secp256k1_context_set_error_callback(none, counting_illegal_callback_fn, &ecount); scratch = secp256k1_scratch_space_create(none, 1000); CHECK(scratch != NULL); CHECK(ecount == 0); /* Test internal API */ - CHECK(secp256k1_scratch_max_allocation(scratch, 0) == 1000); - CHECK(secp256k1_scratch_max_allocation(scratch, 1) < 1000); - - /* Allocating 500 bytes with no frame fails */ - CHECK(secp256k1_scratch_alloc(scratch, 500) == NULL); - CHECK(secp256k1_scratch_max_allocation(scratch, 0) == 1000); - - /* ...but pushing a new stack frame does affect the max allocation */ - CHECK(secp256k1_scratch_allocate_frame(scratch, 500, 1 == 1)); - CHECK(secp256k1_scratch_max_allocation(scratch, 1) < 500); /* 500 - ALIGNMENT */ - CHECK(secp256k1_scratch_alloc(scratch, 500) != NULL); - CHECK(secp256k1_scratch_alloc(scratch, 500) == NULL); - - CHECK(secp256k1_scratch_allocate_frame(scratch, 500, 1) == 0); + CHECK(secp256k1_scratch_max_allocation(&none->error_callback, scratch, 0) == 1000); + CHECK(secp256k1_scratch_max_allocation(&none->error_callback, scratch, 1) == 1000 - (ALIGNMENT - 1)); + CHECK(scratch->alloc_size == 0); + CHECK(scratch->alloc_size % ALIGNMENT == 0); + + /* Allocating 500 bytes succeeds */ + checkpoint = secp256k1_scratch_checkpoint(&none->error_callback, scratch); + CHECK(secp256k1_scratch_alloc(&none->error_callback, scratch, 500) != NULL); + CHECK(secp256k1_scratch_max_allocation(&none->error_callback, scratch, 0) == 1000 - adj_alloc); + CHECK(secp256k1_scratch_max_allocation(&none->error_callback, scratch, 1) == 1000 - adj_alloc - (ALIGNMENT - 1)); + CHECK(scratch->alloc_size != 0); + CHECK(scratch->alloc_size % ALIGNMENT == 0); + + /* Allocating another 500 bytes fails */ + CHECK(secp256k1_scratch_alloc(&none->error_callback, scratch, 500) == NULL); + CHECK(secp256k1_scratch_max_allocation(&none->error_callback, scratch, 0) == 1000 - adj_alloc); + CHECK(secp256k1_scratch_max_allocation(&none->error_callback, scratch, 1) == 1000 - adj_alloc - (ALIGNMENT - 1)); + CHECK(scratch->alloc_size != 0); + CHECK(scratch->alloc_size % ALIGNMENT == 0); + + /* ...but it succeeds once we apply the checkpoint to undo it */ + secp256k1_scratch_apply_checkpoint(&none->error_callback, scratch, checkpoint); + CHECK(scratch->alloc_size == 0); + CHECK(secp256k1_scratch_max_allocation(&none->error_callback, scratch, 0) == 1000); + CHECK(secp256k1_scratch_alloc(&none->error_callback, scratch, 500) != NULL); + CHECK(scratch->alloc_size != 0); + + /* try to apply a bad checkpoint */ + checkpoint_2 = secp256k1_scratch_checkpoint(&none->error_callback, scratch); + secp256k1_scratch_apply_checkpoint(&none->error_callback, scratch, checkpoint); + CHECK(ecount == 0); + secp256k1_scratch_apply_checkpoint(&none->error_callback, scratch, checkpoint_2); /* checkpoint_2 is after checkpoint */ + CHECK(ecount == 1); + secp256k1_scratch_apply_checkpoint(&none->error_callback, scratch, (size_t) -1); /* this is just wildly invalid */ + CHECK(ecount == 2); - /* ...and this effect is undone by popping the frame */ - secp256k1_scratch_deallocate_frame(scratch); - CHECK(secp256k1_scratch_max_allocation(scratch, 0) == 1000); - CHECK(secp256k1_scratch_alloc(scratch, 500) == NULL); + /* try to use badly initialized scratch space */ + secp256k1_scratch_space_destroy(none, scratch); + memset(&local_scratch, 0, sizeof(local_scratch)); + scratch = &local_scratch; + CHECK(!secp256k1_scratch_max_allocation(&none->error_callback, scratch, 0)); + CHECK(ecount == 3); + CHECK(secp256k1_scratch_alloc(&none->error_callback, scratch, 500) == NULL); + CHECK(ecount == 4); + secp256k1_scratch_space_destroy(none, scratch); + CHECK(ecount == 5); /* cleanup */ - secp256k1_scratch_space_destroy(scratch); + secp256k1_scratch_space_destroy(none, NULL); /* no-op */ secp256k1_context_destroy(none); } @@ -965,11 +1072,31 @@ void scalar_test(void) { } +void run_scalar_set_b32_seckey_tests(void) { + unsigned char b32[32]; + secp256k1_scalar s1; + secp256k1_scalar s2; + + /* Usually set_b32 and set_b32_seckey give the same result */ + random_scalar_order_b32(b32); + secp256k1_scalar_set_b32(&s1, b32, NULL); + CHECK(secp256k1_scalar_set_b32_seckey(&s2, b32) == 1); + CHECK(secp256k1_scalar_eq(&s1, &s2) == 1); + + memset(b32, 0, sizeof(b32)); + CHECK(secp256k1_scalar_set_b32_seckey(&s2, b32) == 0); + memset(b32, 0xFF, sizeof(b32)); + CHECK(secp256k1_scalar_set_b32_seckey(&s2, b32) == 0); +} + void run_scalar_tests(void) { int i; for (i = 0; i < 128 * count; i++) { scalar_test(); } + for (i = 0; i < count; i++) { + run_scalar_set_b32_seckey_tests(); + } { /* (-1)+1 should be zero. */ @@ -985,16 +1112,43 @@ void run_scalar_tests(void) { #ifndef USE_NUM_NONE { - /* A scalar with value of the curve order should be 0. */ + /* Test secp256k1_scalar_set_b32 boundary conditions */ secp256k1_num order; - secp256k1_scalar zero; + secp256k1_scalar scalar; unsigned char bin[32]; + unsigned char bin_tmp[32]; int overflow = 0; + /* 2^256-1 - order */ + static const secp256k1_scalar all_ones_minus_order = SECP256K1_SCALAR_CONST( + 0x00000000UL, 0x00000000UL, 0x00000000UL, 0x00000001UL, + 0x45512319UL, 0x50B75FC4UL, 0x402DA173UL, 0x2FC9BEBEUL + ); + + /* A scalar set to 0s should be 0. */ + memset(bin, 0, 32); + secp256k1_scalar_set_b32(&scalar, bin, &overflow); + CHECK(overflow == 0); + CHECK(secp256k1_scalar_is_zero(&scalar)); + + /* A scalar with value of the curve order should be 0. */ secp256k1_scalar_order_get_num(&order); secp256k1_num_get_bin(bin, 32, &order); - secp256k1_scalar_set_b32(&zero, bin, &overflow); + secp256k1_scalar_set_b32(&scalar, bin, &overflow); + CHECK(overflow == 1); + CHECK(secp256k1_scalar_is_zero(&scalar)); + + /* A scalar with value of the curve order minus one should not overflow. */ + bin[31] -= 1; + secp256k1_scalar_set_b32(&scalar, bin, &overflow); + CHECK(overflow == 0); + secp256k1_scalar_get_b32(bin_tmp, &scalar); + CHECK(memcmp(bin, bin_tmp, 32) == 0); + + /* A scalar set to all 1s should overflow. */ + memset(bin, 0xFF, 32); + secp256k1_scalar_set_b32(&scalar, bin, &overflow); CHECK(overflow == 1); - CHECK(secp256k1_scalar_is_zero(&zero)); + CHECK(secp256k1_scalar_eq(&scalar, &all_ones_minus_order)); } #endif @@ -1709,24 +1863,32 @@ void run_field_misc(void) { /* Test fe conditional move; z is not normalized here. */ q = x; secp256k1_fe_cmov(&x, &z, 0); - VERIFY_CHECK(!x.normalized && x.magnitude == z.magnitude); +#ifdef VERIFY + CHECK(x.normalized && x.magnitude == 1); +#endif secp256k1_fe_cmov(&x, &x, 1); CHECK(fe_memcmp(&x, &z) != 0); CHECK(fe_memcmp(&x, &q) == 0); secp256k1_fe_cmov(&q, &z, 1); - VERIFY_CHECK(!q.normalized && q.magnitude == z.magnitude); +#ifdef VERIFY + CHECK(!q.normalized && q.magnitude == z.magnitude); +#endif CHECK(fe_memcmp(&q, &z) == 0); secp256k1_fe_normalize_var(&x); secp256k1_fe_normalize_var(&z); CHECK(!secp256k1_fe_equal_var(&x, &z)); secp256k1_fe_normalize_var(&q); secp256k1_fe_cmov(&q, &z, (i&1)); - VERIFY_CHECK(q.normalized && q.magnitude == 1); +#ifdef VERIFY + CHECK(q.normalized && q.magnitude == 1); +#endif for (j = 0; j < 6; j++) { secp256k1_fe_negate(&z, &z, j+1); secp256k1_fe_normalize_var(&q); secp256k1_fe_cmov(&q, &z, (j&1)); - VERIFY_CHECK(!q.normalized && q.magnitude == (j+2)); +#ifdef VERIFY + CHECK((q.normalized != (j&1)) && q.magnitude == ((j&1) ? z.magnitude : 1)); +#endif } secp256k1_fe_normalize_var(&z); /* Test storage conversion and conditional moves. */ @@ -2120,7 +2282,7 @@ void test_ge(void) { /* Test batch gej -> ge conversion with many infinities. */ for (i = 0; i < 4 * runs + 1; i++) { random_group_element_test(&ge[i]); - /* randomly set half the points to infinitiy */ + /* randomly set half the points to infinity */ if(secp256k1_fe_is_odd(&ge[i].x)) { secp256k1_ge_set_infinity(&ge[i]); } @@ -2572,14 +2734,13 @@ void test_ecmult_multi(secp256k1_scratch *scratch, secp256k1_ecmult_multi_func e secp256k1_gej r; secp256k1_gej r2; ecmult_multi_data data; - secp256k1_scratch *scratch_empty; data.sc = sc; data.pt = pt; secp256k1_scalar_set_int(&szero, 0); /* No points to multiply */ - CHECK(ecmult_multi(&ctx->ecmult_ctx, scratch, &r, NULL, ecmult_multi_callback, &data, 0)); + CHECK(ecmult_multi(&ctx->error_callback, &ctx->ecmult_ctx, scratch, &r, NULL, ecmult_multi_callback, &data, 0)); /* Check 1- and 2-point multiplies against ecmult */ for (ncount = 0; ncount < count; ncount++) { @@ -2595,36 +2756,31 @@ void test_ecmult_multi(secp256k1_scratch *scratch, secp256k1_ecmult_multi_func e /* only G scalar */ secp256k1_ecmult(&ctx->ecmult_ctx, &r2, &ptgj, &szero, &sc[0]); - CHECK(ecmult_multi(&ctx->ecmult_ctx, scratch, &r, &sc[0], ecmult_multi_callback, &data, 0)); + CHECK(ecmult_multi(&ctx->error_callback, &ctx->ecmult_ctx, scratch, &r, &sc[0], ecmult_multi_callback, &data, 0)); secp256k1_gej_neg(&r2, &r2); secp256k1_gej_add_var(&r, &r, &r2, NULL); CHECK(secp256k1_gej_is_infinity(&r)); /* 1-point */ secp256k1_ecmult(&ctx->ecmult_ctx, &r2, &ptgj, &sc[0], &szero); - CHECK(ecmult_multi(&ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, 1)); + CHECK(ecmult_multi(&ctx->error_callback, &ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, 1)); secp256k1_gej_neg(&r2, &r2); secp256k1_gej_add_var(&r, &r, &r2, NULL); CHECK(secp256k1_gej_is_infinity(&r)); - /* Try to multiply 1 point, but scratch space is empty */ - scratch_empty = secp256k1_scratch_create(&ctx->error_callback, 0); - CHECK(!ecmult_multi(&ctx->ecmult_ctx, scratch_empty, &r, &szero, ecmult_multi_callback, &data, 1)); - secp256k1_scratch_destroy(scratch_empty); - /* Try to multiply 1 point, but callback returns false */ - CHECK(!ecmult_multi(&ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_false_callback, &data, 1)); + CHECK(!ecmult_multi(&ctx->error_callback, &ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_false_callback, &data, 1)); /* 2-point */ secp256k1_ecmult(&ctx->ecmult_ctx, &r2, &ptgj, &sc[0], &sc[1]); - CHECK(ecmult_multi(&ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, 2)); + CHECK(ecmult_multi(&ctx->error_callback, &ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, 2)); secp256k1_gej_neg(&r2, &r2); secp256k1_gej_add_var(&r, &r, &r2, NULL); CHECK(secp256k1_gej_is_infinity(&r)); /* 2-point with G scalar */ secp256k1_ecmult(&ctx->ecmult_ctx, &r2, &ptgj, &sc[0], &sc[1]); - CHECK(ecmult_multi(&ctx->ecmult_ctx, scratch, &r, &sc[1], ecmult_multi_callback, &data, 1)); + CHECK(ecmult_multi(&ctx->error_callback, &ctx->ecmult_ctx, scratch, &r, &sc[1], ecmult_multi_callback, &data, 1)); secp256k1_gej_neg(&r2, &r2); secp256k1_gej_add_var(&r, &r, &r2, NULL); CHECK(secp256k1_gej_is_infinity(&r)); @@ -2641,7 +2797,7 @@ void test_ecmult_multi(secp256k1_scratch *scratch, secp256k1_ecmult_multi_func e random_scalar_order(&sc[i]); secp256k1_ge_set_infinity(&pt[i]); } - CHECK(ecmult_multi(&ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, sizes[j])); + CHECK(ecmult_multi(&ctx->error_callback, &ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, sizes[j])); CHECK(secp256k1_gej_is_infinity(&r)); } @@ -2651,7 +2807,7 @@ void test_ecmult_multi(secp256k1_scratch *scratch, secp256k1_ecmult_multi_func e pt[i] = ptg; secp256k1_scalar_set_int(&sc[i], 0); } - CHECK(ecmult_multi(&ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, sizes[j])); + CHECK(ecmult_multi(&ctx->error_callback, &ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, sizes[j])); CHECK(secp256k1_gej_is_infinity(&r)); } @@ -2664,7 +2820,7 @@ void test_ecmult_multi(secp256k1_scratch *scratch, secp256k1_ecmult_multi_func e pt[2 * i + 1] = ptg; } - CHECK(ecmult_multi(&ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, sizes[j])); + CHECK(ecmult_multi(&ctx->error_callback, &ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, sizes[j])); CHECK(secp256k1_gej_is_infinity(&r)); random_scalar_order(&sc[0]); @@ -2677,7 +2833,7 @@ void test_ecmult_multi(secp256k1_scratch *scratch, secp256k1_ecmult_multi_func e secp256k1_ge_neg(&pt[2*i+1], &pt[2*i]); } - CHECK(ecmult_multi(&ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, sizes[j])); + CHECK(ecmult_multi(&ctx->error_callback, &ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, sizes[j])); CHECK(secp256k1_gej_is_infinity(&r)); } @@ -2692,7 +2848,7 @@ void test_ecmult_multi(secp256k1_scratch *scratch, secp256k1_ecmult_multi_func e secp256k1_scalar_negate(&sc[i], &sc[i]); } - CHECK(ecmult_multi(&ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, 32)); + CHECK(ecmult_multi(&ctx->error_callback, &ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, 32)); CHECK(secp256k1_gej_is_infinity(&r)); } @@ -2711,7 +2867,7 @@ void test_ecmult_multi(secp256k1_scratch *scratch, secp256k1_ecmult_multi_func e } secp256k1_ecmult(&ctx->ecmult_ctx, &r2, &r, &sc[0], &szero); - CHECK(ecmult_multi(&ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, 20)); + CHECK(ecmult_multi(&ctx->error_callback, &ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, 20)); secp256k1_gej_neg(&r2, &r2); secp256k1_gej_add_var(&r, &r, &r2, NULL); CHECK(secp256k1_gej_is_infinity(&r)); @@ -2734,7 +2890,7 @@ void test_ecmult_multi(secp256k1_scratch *scratch, secp256k1_ecmult_multi_func e secp256k1_gej_set_ge(&p0j, &pt[0]); secp256k1_ecmult(&ctx->ecmult_ctx, &r2, &p0j, &rs, &szero); - CHECK(ecmult_multi(&ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, 20)); + CHECK(ecmult_multi(&ctx->error_callback, &ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, 20)); secp256k1_gej_neg(&r2, &r2); secp256k1_gej_add_var(&r, &r, &r2, NULL); CHECK(secp256k1_gej_is_infinity(&r)); @@ -2747,13 +2903,13 @@ void test_ecmult_multi(secp256k1_scratch *scratch, secp256k1_ecmult_multi_func e } secp256k1_scalar_clear(&sc[0]); - CHECK(ecmult_multi(&ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, 20)); + CHECK(ecmult_multi(&ctx->error_callback, &ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, 20)); secp256k1_scalar_clear(&sc[1]); secp256k1_scalar_clear(&sc[2]); secp256k1_scalar_clear(&sc[3]); secp256k1_scalar_clear(&sc[4]); - CHECK(ecmult_multi(&ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, 6)); - CHECK(ecmult_multi(&ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, 5)); + CHECK(ecmult_multi(&ctx->error_callback, &ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, 6)); + CHECK(ecmult_multi(&ctx->error_callback, &ctx->ecmult_ctx, scratch, &r, &szero, ecmult_multi_callback, &data, 5)); CHECK(secp256k1_gej_is_infinity(&r)); /* Run through s0*(t0*P) + s1*(t1*P) exhaustively for many small values of s0, s1, t0, t1 */ @@ -2798,7 +2954,7 @@ void test_ecmult_multi(secp256k1_scratch *scratch, secp256k1_ecmult_multi_func e secp256k1_scalar_add(&tmp1, &tmp1, &tmp2); secp256k1_ecmult(&ctx->ecmult_ctx, &expected, &ptgj, &tmp1, &szero); - CHECK(ecmult_multi(&ctx->ecmult_ctx, scratch, &actual, &szero, ecmult_multi_callback, &data, 2)); + CHECK(ecmult_multi(&ctx->error_callback, &ctx->ecmult_ctx, scratch, &actual, &szero, ecmult_multi_callback, &data, 2)); secp256k1_gej_neg(&expected, &expected); secp256k1_gej_add_var(&actual, &actual, &expected, NULL); CHECK(secp256k1_gej_is_infinity(&actual)); @@ -2809,6 +2965,24 @@ void test_ecmult_multi(secp256k1_scratch *scratch, secp256k1_ecmult_multi_func e } } +void test_ecmult_multi_batch_single(secp256k1_ecmult_multi_func ecmult_multi) { + secp256k1_scalar szero; + secp256k1_scalar sc[32]; + secp256k1_ge pt[32]; + secp256k1_gej r; + ecmult_multi_data data; + secp256k1_scratch *scratch_empty; + + data.sc = sc; + data.pt = pt; + secp256k1_scalar_set_int(&szero, 0); + + /* Try to multiply 1 point, but scratch space is empty.*/ + scratch_empty = secp256k1_scratch_create(&ctx->error_callback, 0); + CHECK(!ecmult_multi(&ctx->error_callback, &ctx->ecmult_ctx, scratch_empty, &r, &szero, ecmult_multi_callback, &data, 1)); + secp256k1_scratch_destroy(&ctx->error_callback, scratch_empty); +} + void test_secp256k1_pippenger_bucket_window_inv(void) { int i; @@ -2839,17 +3013,27 @@ void test_ecmult_multi_pippenger_max_points(void) { int bucket_window = 0; for(; scratch_size < max_size; scratch_size+=256) { + size_t i; + size_t total_alloc; + size_t checkpoint; scratch = secp256k1_scratch_create(&ctx->error_callback, scratch_size); CHECK(scratch != NULL); - n_points_supported = secp256k1_pippenger_max_points(scratch); + checkpoint = secp256k1_scratch_checkpoint(&ctx->error_callback, scratch); + n_points_supported = secp256k1_pippenger_max_points(&ctx->error_callback, scratch); if (n_points_supported == 0) { - secp256k1_scratch_destroy(scratch); + secp256k1_scratch_destroy(&ctx->error_callback, scratch); continue; } bucket_window = secp256k1_pippenger_bucket_window(n_points_supported); - CHECK(secp256k1_scratch_allocate_frame(scratch, secp256k1_pippenger_scratch_size(n_points_supported, bucket_window), PIPPENGER_SCRATCH_OBJECTS)); - secp256k1_scratch_deallocate_frame(scratch); - secp256k1_scratch_destroy(scratch); + /* allocate `total_alloc` bytes over `PIPPENGER_SCRATCH_OBJECTS` many allocations */ + total_alloc = secp256k1_pippenger_scratch_size(n_points_supported, bucket_window); + for (i = 0; i < PIPPENGER_SCRATCH_OBJECTS - 1; i++) { + CHECK(secp256k1_scratch_alloc(&ctx->error_callback, scratch, 1)); + total_alloc--; + } + CHECK(secp256k1_scratch_alloc(&ctx->error_callback, scratch, total_alloc)); + secp256k1_scratch_apply_checkpoint(&ctx->error_callback, scratch, checkpoint); + secp256k1_scratch_destroy(&ctx->error_callback, scratch); } CHECK(bucket_window == PIPPENGER_MAX_BUCKET_WINDOW); } @@ -2932,19 +3116,25 @@ void test_ecmult_multi_batching(void) { } data.sc = sc; data.pt = pt; + secp256k1_gej_neg(&r2, &r2); - /* Test with empty scratch space */ + /* Test with empty scratch space. It should compute the correct result using + * ecmult_mult_simple algorithm which doesn't require a scratch space. */ scratch = secp256k1_scratch_create(&ctx->error_callback, 0); - CHECK(!secp256k1_ecmult_multi_var(&ctx->ecmult_ctx, scratch, &r, &scG, ecmult_multi_callback, &data, 1)); - secp256k1_scratch_destroy(scratch); + CHECK(secp256k1_ecmult_multi_var(&ctx->error_callback, &ctx->ecmult_ctx, scratch, &r, &scG, ecmult_multi_callback, &data, n_points)); + secp256k1_gej_add_var(&r, &r, &r2, NULL); + CHECK(secp256k1_gej_is_infinity(&r)); + secp256k1_scratch_destroy(&ctx->error_callback, scratch); /* Test with space for 1 point in pippenger. That's not enough because - * ecmult_multi selects strauss which requires more memory. */ + * ecmult_multi selects strauss which requires more memory. It should + * therefore select the simple algorithm. */ scratch = secp256k1_scratch_create(&ctx->error_callback, secp256k1_pippenger_scratch_size(1, 1) + PIPPENGER_SCRATCH_OBJECTS*ALIGNMENT); - CHECK(!secp256k1_ecmult_multi_var(&ctx->ecmult_ctx, scratch, &r, &scG, ecmult_multi_callback, &data, 1)); - secp256k1_scratch_destroy(scratch); + CHECK(secp256k1_ecmult_multi_var(&ctx->error_callback, &ctx->ecmult_ctx, scratch, &r, &scG, ecmult_multi_callback, &data, n_points)); + secp256k1_gej_add_var(&r, &r, &r2, NULL); + CHECK(secp256k1_gej_is_infinity(&r)); + secp256k1_scratch_destroy(&ctx->error_callback, scratch); - secp256k1_gej_neg(&r2, &r2); for(i = 1; i <= n_points; i++) { if (i > ECMULT_PIPPENGER_THRESHOLD) { int bucket_window = secp256k1_pippenger_bucket_window(i); @@ -2954,10 +3144,10 @@ void test_ecmult_multi_batching(void) { size_t scratch_size = secp256k1_strauss_scratch_size(i); scratch = secp256k1_scratch_create(&ctx->error_callback, scratch_size + STRAUSS_SCRATCH_OBJECTS*ALIGNMENT); } - CHECK(secp256k1_ecmult_multi_var(&ctx->ecmult_ctx, scratch, &r, &scG, ecmult_multi_callback, &data, n_points)); + CHECK(secp256k1_ecmult_multi_var(&ctx->error_callback, &ctx->ecmult_ctx, scratch, &r, &scG, ecmult_multi_callback, &data, n_points)); secp256k1_gej_add_var(&r, &r, &r2, NULL); CHECK(secp256k1_gej_is_infinity(&r)); - secp256k1_scratch_destroy(scratch); + secp256k1_scratch_destroy(&ctx->error_callback, scratch); } free(sc); free(pt); @@ -2972,13 +3162,15 @@ void run_ecmult_multi_tests(void) { test_ecmult_multi(scratch, secp256k1_ecmult_multi_var); test_ecmult_multi(NULL, secp256k1_ecmult_multi_var); test_ecmult_multi(scratch, secp256k1_ecmult_pippenger_batch_single); + test_ecmult_multi_batch_single(secp256k1_ecmult_pippenger_batch_single); test_ecmult_multi(scratch, secp256k1_ecmult_strauss_batch_single); - secp256k1_scratch_destroy(scratch); + test_ecmult_multi_batch_single(secp256k1_ecmult_strauss_batch_single); + secp256k1_scratch_destroy(&ctx->error_callback, scratch); /* Run test_ecmult_multi with space for exactly one point */ scratch = secp256k1_scratch_create(&ctx->error_callback, secp256k1_strauss_scratch_size(1) + STRAUSS_SCRATCH_OBJECTS*ALIGNMENT); test_ecmult_multi(scratch, secp256k1_ecmult_multi_var); - secp256k1_scratch_destroy(scratch); + secp256k1_scratch_destroy(&ctx->error_callback, scratch); test_ecmult_multi_batch_size_helper(); test_ecmult_multi_batching(); @@ -3050,7 +3242,7 @@ void test_constant_wnaf(const secp256k1_scalar *number, int w) { } bits = 128; #endif - skew = secp256k1_wnaf_const(wnaf, num, w, bits); + skew = secp256k1_wnaf_const(wnaf, &num, w, bits); for (i = WNAF_SIZE_BITS(bits, w); i >= 0; --i) { secp256k1_scalar t; @@ -3786,37 +3978,57 @@ void run_eckey_edge_case_test(void) { pubkey_negone = pubkey; /* Tweak of zero leaves the value unchanged. */ memset(ctmp2, 0, 32); - CHECK(secp256k1_ec_privkey_tweak_add(ctx, ctmp, ctmp2) == 1); + CHECK(secp256k1_ec_seckey_tweak_add(ctx, ctmp, ctmp2) == 1); CHECK(memcmp(orderc, ctmp, 31) == 0 && ctmp[31] == 0x40); memcpy(&pubkey2, &pubkey, sizeof(pubkey)); CHECK(secp256k1_ec_pubkey_tweak_add(ctx, &pubkey, ctmp2) == 1); CHECK(memcmp(&pubkey, &pubkey2, sizeof(pubkey)) == 0); /* Multiply tweak of zero zeroizes the output. */ - CHECK(secp256k1_ec_privkey_tweak_mul(ctx, ctmp, ctmp2) == 0); + CHECK(secp256k1_ec_seckey_tweak_mul(ctx, ctmp, ctmp2) == 0); CHECK(memcmp(zeros, ctmp, 32) == 0); CHECK(secp256k1_ec_pubkey_tweak_mul(ctx, &pubkey, ctmp2) == 0); CHECK(memcmp(&pubkey, zeros, sizeof(pubkey)) == 0); memcpy(&pubkey, &pubkey2, sizeof(pubkey)); - /* Overflowing key tweak zeroizes. */ + /* If seckey_tweak_add or seckey_tweak_mul are called with an overflowing + seckey, the seckey is zeroized. */ + memcpy(ctmp, orderc, 32); + memset(ctmp2, 0, 32); + ctmp2[31] = 0x01; + CHECK(secp256k1_ec_seckey_verify(ctx, ctmp2) == 1); + CHECK(secp256k1_ec_seckey_verify(ctx, ctmp) == 0); + CHECK(secp256k1_ec_seckey_tweak_add(ctx, ctmp, ctmp2) == 0); + CHECK(memcmp(zeros, ctmp, 32) == 0); + memcpy(ctmp, orderc, 32); + CHECK(secp256k1_ec_seckey_tweak_mul(ctx, ctmp, ctmp2) == 0); + CHECK(memcmp(zeros, ctmp, 32) == 0); + /* If seckey_tweak_add or seckey_tweak_mul are called with an overflowing + tweak, the seckey is zeroized. */ memcpy(ctmp, orderc, 32); ctmp[31] = 0x40; - CHECK(secp256k1_ec_privkey_tweak_add(ctx, ctmp, orderc) == 0); + CHECK(secp256k1_ec_seckey_tweak_add(ctx, ctmp, orderc) == 0); CHECK(memcmp(zeros, ctmp, 32) == 0); memcpy(ctmp, orderc, 32); ctmp[31] = 0x40; - CHECK(secp256k1_ec_privkey_tweak_mul(ctx, ctmp, orderc) == 0); + CHECK(secp256k1_ec_seckey_tweak_mul(ctx, ctmp, orderc) == 0); CHECK(memcmp(zeros, ctmp, 32) == 0); memcpy(ctmp, orderc, 32); ctmp[31] = 0x40; + /* If pubkey_tweak_add or pubkey_tweak_mul are called with an overflowing + tweak, the pubkey is zeroized. */ CHECK(secp256k1_ec_pubkey_tweak_add(ctx, &pubkey, orderc) == 0); CHECK(memcmp(&pubkey, zeros, sizeof(pubkey)) == 0); memcpy(&pubkey, &pubkey2, sizeof(pubkey)); CHECK(secp256k1_ec_pubkey_tweak_mul(ctx, &pubkey, orderc) == 0); CHECK(memcmp(&pubkey, zeros, sizeof(pubkey)) == 0); memcpy(&pubkey, &pubkey2, sizeof(pubkey)); - /* Private key tweaks results in a key of zero. */ + /* If the resulting key in secp256k1_ec_seckey_tweak_add and + * secp256k1_ec_pubkey_tweak_add is 0 the functions fail and in the latter + * case the pubkey is zeroized. */ + memcpy(ctmp, orderc, 32); + ctmp[31] = 0x40; + memset(ctmp2, 0, 32); ctmp2[31] = 1; - CHECK(secp256k1_ec_privkey_tweak_add(ctx, ctmp2, ctmp) == 0); + CHECK(secp256k1_ec_seckey_tweak_add(ctx, ctmp2, ctmp) == 0); CHECK(memcmp(zeros, ctmp2, 32) == 0); ctmp2[31] = 1; CHECK(secp256k1_ec_pubkey_tweak_add(ctx, &pubkey, ctmp2) == 0); @@ -3824,7 +4036,7 @@ void run_eckey_edge_case_test(void) { memcpy(&pubkey, &pubkey2, sizeof(pubkey)); /* Tweak computation wraps and results in a key of 1. */ ctmp2[31] = 2; - CHECK(secp256k1_ec_privkey_tweak_add(ctx, ctmp2, ctmp) == 1); + CHECK(secp256k1_ec_seckey_tweak_add(ctx, ctmp2, ctmp) == 1); CHECK(memcmp(ctmp2, zeros, 31) == 0 && ctmp2[31] == 1); ctmp2[31] = 2; CHECK(secp256k1_ec_pubkey_tweak_add(ctx, &pubkey, ctmp2) == 1); @@ -3872,16 +4084,16 @@ void run_eckey_edge_case_test(void) { CHECK(ecount == 2); ecount = 0; memset(ctmp2, 0, 32); - CHECK(secp256k1_ec_privkey_tweak_add(ctx, NULL, ctmp2) == 0); + CHECK(secp256k1_ec_seckey_tweak_add(ctx, NULL, ctmp2) == 0); CHECK(ecount == 1); - CHECK(secp256k1_ec_privkey_tweak_add(ctx, ctmp, NULL) == 0); + CHECK(secp256k1_ec_seckey_tweak_add(ctx, ctmp, NULL) == 0); CHECK(ecount == 2); ecount = 0; memset(ctmp2, 0, 32); ctmp2[31] = 1; - CHECK(secp256k1_ec_privkey_tweak_mul(ctx, NULL, ctmp2) == 0); + CHECK(secp256k1_ec_seckey_tweak_mul(ctx, NULL, ctmp2) == 0); CHECK(ecount == 1); - CHECK(secp256k1_ec_privkey_tweak_mul(ctx, ctmp, NULL) == 0); + CHECK(secp256k1_ec_seckey_tweak_mul(ctx, ctmp, NULL) == 0); CHECK(ecount == 2); ecount = 0; CHECK(secp256k1_ec_pubkey_create(ctx, NULL, ctmp) == 0); @@ -3954,6 +4166,41 @@ void run_eckey_edge_case_test(void) { secp256k1_context_set_illegal_callback(ctx, NULL, NULL); } +void run_eckey_negate_test(void) { + unsigned char seckey[32]; + unsigned char seckey_tmp[32]; + + random_scalar_order_b32(seckey); + memcpy(seckey_tmp, seckey, 32); + + /* Verify negation changes the key and changes it back */ + CHECK(secp256k1_ec_seckey_negate(ctx, seckey) == 1); + CHECK(memcmp(seckey, seckey_tmp, 32) != 0); + CHECK(secp256k1_ec_seckey_negate(ctx, seckey) == 1); + CHECK(memcmp(seckey, seckey_tmp, 32) == 0); + + /* Check that privkey alias gives same result */ + CHECK(secp256k1_ec_seckey_negate(ctx, seckey) == 1); + CHECK(secp256k1_ec_privkey_negate(ctx, seckey_tmp) == 1); + CHECK(memcmp(seckey, seckey_tmp, 32) == 0); + + /* Negating all 0s fails */ + memset(seckey, 0, 32); + memset(seckey_tmp, 0, 32); + CHECK(secp256k1_ec_seckey_negate(ctx, seckey) == 0); + /* Check that seckey is not modified */ + CHECK(memcmp(seckey, seckey_tmp, 32) == 0); + + /* Negating an overflowing seckey fails and the seckey is zeroed. In this + * test, the seckey has 16 random bytes to ensure that ec_seckey_negate + * doesn't just set seckey to a constant value in case of failure. */ + random_scalar_order_b32(seckey); + memset(seckey, 0xFF, 16); + memset(seckey_tmp, 0, 32); + CHECK(secp256k1_ec_seckey_negate(ctx, seckey) == 0); + CHECK(memcmp(seckey, seckey_tmp, 32) == 0); +} + void random_sign(secp256k1_scalar *sigr, secp256k1_scalar *sigs, const secp256k1_scalar *key, const secp256k1_scalar *msg, int *recid) { secp256k1_scalar nonce; do { @@ -4093,15 +4340,22 @@ void test_ecdsa_end_to_end(void) { if (secp256k1_rand_int(3) == 0) { int ret1; int ret2; + int ret3; unsigned char rnd[32]; + unsigned char privkey_tmp[32]; secp256k1_pubkey pubkey2; secp256k1_rand256_test(rnd); - ret1 = secp256k1_ec_privkey_tweak_add(ctx, privkey, rnd); + memcpy(privkey_tmp, privkey, 32); + ret1 = secp256k1_ec_seckey_tweak_add(ctx, privkey, rnd); ret2 = secp256k1_ec_pubkey_tweak_add(ctx, &pubkey, rnd); + /* Check that privkey alias gives same result */ + ret3 = secp256k1_ec_privkey_tweak_add(ctx, privkey_tmp, rnd); CHECK(ret1 == ret2); + CHECK(ret2 == ret3); if (ret1 == 0) { return; } + CHECK(memcmp(privkey, privkey_tmp, 32) == 0); CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey2, privkey) == 1); CHECK(memcmp(&pubkey, &pubkey2, sizeof(pubkey)) == 0); } @@ -4110,15 +4364,22 @@ void test_ecdsa_end_to_end(void) { if (secp256k1_rand_int(3) == 0) { int ret1; int ret2; + int ret3; unsigned char rnd[32]; + unsigned char privkey_tmp[32]; secp256k1_pubkey pubkey2; secp256k1_rand256_test(rnd); - ret1 = secp256k1_ec_privkey_tweak_mul(ctx, privkey, rnd); + memcpy(privkey_tmp, privkey, 32); + ret1 = secp256k1_ec_seckey_tweak_mul(ctx, privkey, rnd); ret2 = secp256k1_ec_pubkey_tweak_mul(ctx, &pubkey, rnd); + /* Check that privkey alias gives same result */ + ret3 = secp256k1_ec_privkey_tweak_mul(ctx, privkey_tmp, rnd); CHECK(ret1 == ret2); + CHECK(ret2 == ret3); if (ret1 == 0) { return; } + CHECK(memcmp(privkey, privkey_tmp, 32) == 0); CHECK(secp256k1_ec_pubkey_create(ctx, &pubkey2, privkey) == 1); CHECK(memcmp(&pubkey, &pubkey2, sizeof(pubkey)) == 0); } @@ -4315,7 +4576,7 @@ int test_ecdsa_der_parse(const unsigned char *sig, size_t siglen, int certainly_ if (valid_der) { ret |= (!roundtrips_der_lax) << 12; ret |= (len_der != len_der_lax) << 13; - ret |= (memcmp(roundtrip_der_lax, roundtrip_der, len_der) != 0) << 14; + ret |= ((len_der != len_der_lax) || (memcmp(roundtrip_der_lax, roundtrip_der, len_der) != 0)) << 14; } ret |= (roundtrips_der != roundtrips_der_lax) << 15; if (parsed_der) { @@ -4356,7 +4617,7 @@ int test_ecdsa_der_parse(const unsigned char *sig, size_t siglen, int certainly_ ret |= (roundtrips_der != roundtrips_openssl) << 7; if (roundtrips_openssl) { ret |= (len_der != (size_t)len_openssl) << 8; - ret |= (memcmp(roundtrip_der, roundtrip_openssl, len_der) != 0) << 9; + ret |= ((len_der != (size_t)len_openssl) || (memcmp(roundtrip_der, roundtrip_openssl, len_der) != 0)) << 9; } #endif return ret; @@ -5016,9 +5277,188 @@ void run_ecdsa_openssl(void) { # include "modules/recovery/tests_impl.h" #endif +void run_memczero_test(void) { + unsigned char buf1[6] = {1, 2, 3, 4, 5, 6}; + unsigned char buf2[sizeof(buf1)]; + + /* memczero(..., ..., 0) is a noop. */ + memcpy(buf2, buf1, sizeof(buf1)); + memczero(buf1, sizeof(buf1), 0); + CHECK(memcmp(buf1, buf2, sizeof(buf1)) == 0); + + /* memczero(..., ..., 1) zeros the buffer. */ + memset(buf2, 0, sizeof(buf2)); + memczero(buf1, sizeof(buf1) , 1); + CHECK(memcmp(buf1, buf2, sizeof(buf1)) == 0); +} + +void int_cmov_test(void) { + int r = INT_MAX; + int a = 0; + + secp256k1_int_cmov(&r, &a, 0); + CHECK(r == INT_MAX); + + r = 0; a = INT_MAX; + secp256k1_int_cmov(&r, &a, 1); + CHECK(r == INT_MAX); + + a = 0; + secp256k1_int_cmov(&r, &a, 1); + CHECK(r == 0); + + a = 1; + secp256k1_int_cmov(&r, &a, 1); + CHECK(r == 1); + + r = 1; a = 0; + secp256k1_int_cmov(&r, &a, 0); + CHECK(r == 1); + +} + +void fe_cmov_test(void) { + static const secp256k1_fe zero = SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 0); + static const secp256k1_fe one = SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 1); + static const secp256k1_fe max = SECP256K1_FE_CONST( + 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, + 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL + ); + secp256k1_fe r = max; + secp256k1_fe a = zero; + + secp256k1_fe_cmov(&r, &a, 0); + CHECK(memcmp(&r, &max, sizeof(r)) == 0); + + r = zero; a = max; + secp256k1_fe_cmov(&r, &a, 1); + CHECK(memcmp(&r, &max, sizeof(r)) == 0); + + a = zero; + secp256k1_fe_cmov(&r, &a, 1); + CHECK(memcmp(&r, &zero, sizeof(r)) == 0); + + a = one; + secp256k1_fe_cmov(&r, &a, 1); + CHECK(memcmp(&r, &one, sizeof(r)) == 0); + + r = one; a = zero; + secp256k1_fe_cmov(&r, &a, 0); + CHECK(memcmp(&r, &one, sizeof(r)) == 0); +} + +void fe_storage_cmov_test(void) { + static const secp256k1_fe_storage zero = SECP256K1_FE_STORAGE_CONST(0, 0, 0, 0, 0, 0, 0, 0); + static const secp256k1_fe_storage one = SECP256K1_FE_STORAGE_CONST(0, 0, 0, 0, 0, 0, 0, 1); + static const secp256k1_fe_storage max = SECP256K1_FE_STORAGE_CONST( + 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, + 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL + ); + secp256k1_fe_storage r = max; + secp256k1_fe_storage a = zero; + + secp256k1_fe_storage_cmov(&r, &a, 0); + CHECK(memcmp(&r, &max, sizeof(r)) == 0); + + r = zero; a = max; + secp256k1_fe_storage_cmov(&r, &a, 1); + CHECK(memcmp(&r, &max, sizeof(r)) == 0); + + a = zero; + secp256k1_fe_storage_cmov(&r, &a, 1); + CHECK(memcmp(&r, &zero, sizeof(r)) == 0); + + a = one; + secp256k1_fe_storage_cmov(&r, &a, 1); + CHECK(memcmp(&r, &one, sizeof(r)) == 0); + + r = one; a = zero; + secp256k1_fe_storage_cmov(&r, &a, 0); + CHECK(memcmp(&r, &one, sizeof(r)) == 0); +} + +void scalar_cmov_test(void) { + static const secp256k1_scalar zero = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0); + static const secp256k1_scalar one = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 1); + static const secp256k1_scalar max = SECP256K1_SCALAR_CONST( + 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, + 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL + ); + secp256k1_scalar r = max; + secp256k1_scalar a = zero; + + secp256k1_scalar_cmov(&r, &a, 0); + CHECK(memcmp(&r, &max, sizeof(r)) == 0); + + r = zero; a = max; + secp256k1_scalar_cmov(&r, &a, 1); + CHECK(memcmp(&r, &max, sizeof(r)) == 0); + + a = zero; + secp256k1_scalar_cmov(&r, &a, 1); + CHECK(memcmp(&r, &zero, sizeof(r)) == 0); + + a = one; + secp256k1_scalar_cmov(&r, &a, 1); + CHECK(memcmp(&r, &one, sizeof(r)) == 0); + + r = one; a = zero; + secp256k1_scalar_cmov(&r, &a, 0); + CHECK(memcmp(&r, &one, sizeof(r)) == 0); +} + +void ge_storage_cmov_test(void) { + static const secp256k1_ge_storage zero = SECP256K1_GE_STORAGE_CONST(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0); + static const secp256k1_ge_storage one = SECP256K1_GE_STORAGE_CONST(0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1); + static const secp256k1_ge_storage max = SECP256K1_GE_STORAGE_CONST( + 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, + 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, + 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, + 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL + ); + secp256k1_ge_storage r = max; + secp256k1_ge_storage a = zero; + + secp256k1_ge_storage_cmov(&r, &a, 0); + CHECK(memcmp(&r, &max, sizeof(r)) == 0); + + r = zero; a = max; + secp256k1_ge_storage_cmov(&r, &a, 1); + CHECK(memcmp(&r, &max, sizeof(r)) == 0); + + a = zero; + secp256k1_ge_storage_cmov(&r, &a, 1); + CHECK(memcmp(&r, &zero, sizeof(r)) == 0); + + a = one; + secp256k1_ge_storage_cmov(&r, &a, 1); + CHECK(memcmp(&r, &one, sizeof(r)) == 0); + + r = one; a = zero; + secp256k1_ge_storage_cmov(&r, &a, 0); + CHECK(memcmp(&r, &one, sizeof(r)) == 0); +} + +void run_cmov_tests(void) { + int_cmov_test(); + fe_cmov_test(); + fe_storage_cmov_test(); + scalar_cmov_test(); + ge_storage_cmov_test(); +} + int main(int argc, char **argv) { unsigned char seed16[16] = {0}; unsigned char run32[32] = {0}; + + /* Disable buffering for stdout to improve reliability of getting + * diagnostic information. Happens right at the start of main because + * setbuf must be used before any other operation on the stream. */ + setbuf(stdout, NULL); + /* Also disable buffering for stderr because it's not guaranteed that it's + * unbuffered on all systems. */ + setbuf(stderr, NULL); + /* find iteration count */ if (argc > 1) { count = strtol(argv[1], NULL, 0); @@ -5030,7 +5470,7 @@ int main(int argc, char **argv) { const char* ch = argv[2]; while (pos < 16 && ch[0] != 0 && ch[1] != 0) { unsigned short sh; - if (sscanf(ch, "%2hx", &sh)) { + if ((sscanf(ch, "%2hx", &sh)) == 1) { seed16[pos] = sh; } else { break; @@ -5062,7 +5502,8 @@ int main(int argc, char **argv) { printf("random seed = %02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x\n", seed16[0], seed16[1], seed16[2], seed16[3], seed16[4], seed16[5], seed16[6], seed16[7], seed16[8], seed16[9], seed16[10], seed16[11], seed16[12], seed16[13], seed16[14], seed16[15]); /* initialize */ - run_context_tests(); + run_context_tests(0); + run_context_tests(1); run_scratch_tests(); ctx = secp256k1_context_create(SECP256K1_CONTEXT_SIGN | SECP256K1_CONTEXT_VERIFY); if (secp256k1_rand_bits(1)) { @@ -5119,6 +5560,9 @@ int main(int argc, char **argv) { /* EC key edge cases */ run_eckey_edge_case_test(); + /* EC key arithmetic test */ + run_eckey_negate_test(); + #ifdef ENABLE_MODULE_ECDH /* ecdh tests */ run_ecdh_tests(); @@ -5139,6 +5583,11 @@ int main(int argc, char **argv) { run_recovery_tests(); #endif + /* util tests */ + run_memczero_test(); + + run_cmov_tests(); + secp256k1_rand256(run32); printf("random run = %02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x\n", run32[0], run32[1], run32[2], run32[3], run32[4], run32[5], run32[6], run32[7], run32[8], run32[9], run32[10], run32[11], run32[12], run32[13], run32[14], run32[15]); diff --git a/src/tests_exhaustive.c b/src/tests_exhaustive.c index ab9779b02f..8cca1cef21 100644 --- a/src/tests_exhaustive.c +++ b/src/tests_exhaustive.c @@ -142,7 +142,7 @@ void test_exhaustive_addition(const secp256k1_ge *group, const secp256k1_gej *gr for (i = 0; i < order; i++) { secp256k1_gej tmp; if (i > 0) { - secp256k1_gej_double_nonzero(&tmp, &groupj[i], NULL); + secp256k1_gej_double_nonzero(&tmp, &groupj[i]); ge_equals_gej(&group[(2 * i) % order], &tmp); } secp256k1_gej_double_var(&tmp, &groupj[i], NULL); @@ -212,14 +212,14 @@ void test_exhaustive_ecmult_multi(const secp256k1_context *ctx, const secp256k1_ data.pt[0] = group[x]; data.pt[1] = group[y]; - secp256k1_ecmult_multi_var(&ctx->ecmult_ctx, scratch, &tmp, &g_sc, ecmult_multi_callback, &data, 2); + secp256k1_ecmult_multi_var(&ctx->error_callback, &ctx->ecmult_ctx, scratch, &tmp, &g_sc, ecmult_multi_callback, &data, 2); ge_equals_gej(&group[(i * x + j * y + k) % order], &tmp); } } } } } - secp256k1_scratch_destroy(scratch); + secp256k1_scratch_destroy(&ctx->error_callback, scratch); } void r_from_k(secp256k1_scalar *r, const secp256k1_ge *group, int k) { diff --git a/src/util.h b/src/util.h index e1f5b76452..8289e23e0c 100644 --- a/src/util.h +++ b/src/util.h @@ -14,6 +14,7 @@ #include <stdlib.h> #include <stdint.h> #include <stdio.h> +#include <limits.h> typedef struct { void (*fn)(const char *text, void* data); @@ -68,6 +69,25 @@ static SECP256K1_INLINE void secp256k1_callback_call(const secp256k1_callback * #define VERIFY_SETUP(stmt) #endif +/* Define `VG_UNDEF` and `VG_CHECK` when VALGRIND is defined */ +#if !defined(VG_CHECK) +# if defined(VALGRIND) +# include <valgrind/memcheck.h> +# define VG_UNDEF(x,y) VALGRIND_MAKE_MEM_UNDEFINED((x),(y)) +# define VG_CHECK(x,y) VALGRIND_CHECK_MEM_IS_DEFINED((x),(y)) +# else +# define VG_UNDEF(x,y) +# define VG_CHECK(x,y) +# endif +#endif + +/* Like `VG_CHECK` but on VERIFY only */ +#if defined(VERIFY) +#define VG_CHECK_VERIFY(x,y) VG_CHECK((x), (y)) +#else +#define VG_CHECK_VERIFY(x,y) +#endif + static SECP256K1_INLINE void *checked_malloc(const secp256k1_callback* cb, size_t size) { void *ret = malloc(size); if (ret == NULL) { @@ -84,6 +104,47 @@ static SECP256K1_INLINE void *checked_realloc(const secp256k1_callback* cb, void return ret; } +#if defined(__BIGGEST_ALIGNMENT__) +#define ALIGNMENT __BIGGEST_ALIGNMENT__ +#else +/* Using 16 bytes alignment because common architectures never have alignment + * requirements above 8 for any of the types we care about. In addition we + * leave some room because currently we don't care about a few bytes. */ +#define ALIGNMENT 16 +#endif + +#define ROUND_TO_ALIGN(size) (((size + ALIGNMENT - 1) / ALIGNMENT) * ALIGNMENT) + +/* Assume there is a contiguous memory object with bounds [base, base + max_size) + * of which the memory range [base, *prealloc_ptr) is already allocated for usage, + * where *prealloc_ptr is an aligned pointer. In that setting, this functions + * reserves the subobject [*prealloc_ptr, *prealloc_ptr + alloc_size) of + * alloc_size bytes by increasing *prealloc_ptr accordingly, taking into account + * alignment requirements. + * + * The function returns an aligned pointer to the newly allocated subobject. + * + * This is useful for manual memory management: if we're simply given a block + * [base, base + max_size), the caller can use this function to allocate memory + * in this block and keep track of the current allocation state with *prealloc_ptr. + * + * It is VERIFY_CHECKed that there is enough space left in the memory object and + * *prealloc_ptr is aligned relative to base. + */ +static SECP256K1_INLINE void *manual_alloc(void** prealloc_ptr, size_t alloc_size, void* base, size_t max_size) { + size_t aligned_alloc_size = ROUND_TO_ALIGN(alloc_size); + void* ret; + VERIFY_CHECK(prealloc_ptr != NULL); + VERIFY_CHECK(*prealloc_ptr != NULL); + VERIFY_CHECK(base != NULL); + VERIFY_CHECK((unsigned char*)*prealloc_ptr >= (unsigned char*)base); + VERIFY_CHECK(((unsigned char*)*prealloc_ptr - (unsigned char*)base) % ALIGNMENT == 0); + VERIFY_CHECK((unsigned char*)*prealloc_ptr - (unsigned char*)base + aligned_alloc_size <= max_size); + ret = *prealloc_ptr; + *((unsigned char**)prealloc_ptr) += aligned_alloc_size; + return ret; +} + /* Macro for restrict, when available and not in a VERIFY build. */ #if defined(SECP256K1_BUILD) && defined(VERIFY) # define SECP256K1_RESTRICT @@ -118,4 +179,33 @@ static SECP256K1_INLINE void *checked_realloc(const secp256k1_callback* cb, void SECP256K1_GNUC_EXT typedef unsigned __int128 uint128_t; #endif +/* Zero memory if flag == 1. Flag must be 0 or 1. Constant time. */ +static SECP256K1_INLINE void memczero(void *s, size_t len, int flag) { + unsigned char *p = (unsigned char *)s; + /* Access flag with a volatile-qualified lvalue. + This prevents clang from figuring out (after inlining) that flag can + take only be 0 or 1, which leads to variable time code. */ + volatile int vflag = flag; + unsigned char mask = -(unsigned char) vflag; + while (len) { + *p &= ~mask; + p++; + len--; + } +} + +/** If flag is true, set *r equal to *a; otherwise leave it. Constant-time. Both *r and *a must be initialized and non-negative.*/ +static SECP256K1_INLINE void secp256k1_int_cmov(int *r, const int *a, int flag) { + unsigned int mask0, mask1, r_masked, a_masked; + /* Casting a negative int to unsigned and back to int is implementation defined behavior */ + VERIFY_CHECK(*r >= 0 && *a >= 0); + + mask0 = (unsigned int)flag + ~0u; + mask1 = ~mask0; + r_masked = ((unsigned int)*r & mask0); + a_masked = ((unsigned int)*a & mask1); + + *r = (int)(r_masked | a_masked); +} + #endif /* SECP256K1_UTIL_H */ diff --git a/src/valgrind_ctime_test.c b/src/valgrind_ctime_test.c new file mode 100644 index 0000000000..60a82d599e --- /dev/null +++ b/src/valgrind_ctime_test.c @@ -0,0 +1,119 @@ +/********************************************************************** + * Copyright (c) 2020 Gregory Maxwell * + * Distributed under the MIT software license, see the accompanying * + * file COPYING or http://www.opensource.org/licenses/mit-license.php.* + **********************************************************************/ + +#include <valgrind/memcheck.h> +#include "include/secp256k1.h" +#include "util.h" + +#if ENABLE_MODULE_ECDH +# include "include/secp256k1_ecdh.h" +#endif + +#if ENABLE_MODULE_RECOVERY +# include "include/secp256k1_recovery.h" +#endif + +int main(void) { + secp256k1_context* ctx; + secp256k1_ecdsa_signature signature; + secp256k1_pubkey pubkey; + size_t siglen = 74; + size_t outputlen = 33; + int i; + int ret; + unsigned char msg[32]; + unsigned char key[32]; + unsigned char sig[74]; + unsigned char spubkey[33]; +#if ENABLE_MODULE_RECOVERY + secp256k1_ecdsa_recoverable_signature recoverable_signature; + int recid; +#endif + + if (!RUNNING_ON_VALGRIND) { + fprintf(stderr, "This test can only usefully be run inside valgrind.\n"); + fprintf(stderr, "Usage: libtool --mode=execute valgrind ./valgrind_ctime_test\n"); + exit(1); + } + + /** In theory, testing with a single secret input should be sufficient: + * If control flow depended on secrets the tool would generate an error. + */ + for (i = 0; i < 32; i++) { + key[i] = i + 65; + } + for (i = 0; i < 32; i++) { + msg[i] = i + 1; + } + + ctx = secp256k1_context_create(SECP256K1_CONTEXT_SIGN | SECP256K1_CONTEXT_DECLASSIFY); + + /* Test keygen. */ + VALGRIND_MAKE_MEM_UNDEFINED(key, 32); + ret = secp256k1_ec_pubkey_create(ctx, &pubkey, key); + VALGRIND_MAKE_MEM_DEFINED(&pubkey, sizeof(secp256k1_pubkey)); + VALGRIND_MAKE_MEM_DEFINED(&ret, sizeof(ret)); + CHECK(ret); + CHECK(secp256k1_ec_pubkey_serialize(ctx, spubkey, &outputlen, &pubkey, SECP256K1_EC_COMPRESSED) == 1); + + /* Test signing. */ + VALGRIND_MAKE_MEM_UNDEFINED(key, 32); + ret = secp256k1_ecdsa_sign(ctx, &signature, msg, key, NULL, NULL); + VALGRIND_MAKE_MEM_DEFINED(&signature, sizeof(secp256k1_ecdsa_signature)); + VALGRIND_MAKE_MEM_DEFINED(&ret, sizeof(ret)); + CHECK(ret); + CHECK(secp256k1_ecdsa_signature_serialize_der(ctx, sig, &siglen, &signature)); + +#if ENABLE_MODULE_ECDH + /* Test ECDH. */ + VALGRIND_MAKE_MEM_UNDEFINED(key, 32); + ret = secp256k1_ecdh(ctx, msg, &pubkey, key, NULL, NULL); + VALGRIND_MAKE_MEM_DEFINED(&ret, sizeof(ret)); + CHECK(ret == 1); +#endif + +#if ENABLE_MODULE_RECOVERY + /* Test signing a recoverable signature. */ + VALGRIND_MAKE_MEM_UNDEFINED(key, 32); + ret = secp256k1_ecdsa_sign_recoverable(ctx, &recoverable_signature, msg, key, NULL, NULL); + VALGRIND_MAKE_MEM_DEFINED(&recoverable_signature, sizeof(recoverable_signature)); + VALGRIND_MAKE_MEM_DEFINED(&ret, sizeof(ret)); + CHECK(ret); + CHECK(secp256k1_ecdsa_recoverable_signature_serialize_compact(ctx, sig, &recid, &recoverable_signature)); + CHECK(recid >= 0 && recid <= 3); +#endif + + VALGRIND_MAKE_MEM_UNDEFINED(key, 32); + ret = secp256k1_ec_seckey_verify(ctx, key); + VALGRIND_MAKE_MEM_DEFINED(&ret, sizeof(ret)); + CHECK(ret == 1); + + VALGRIND_MAKE_MEM_UNDEFINED(key, 32); + ret = secp256k1_ec_seckey_negate(ctx, key); + VALGRIND_MAKE_MEM_DEFINED(&ret, sizeof(ret)); + CHECK(ret == 1); + + VALGRIND_MAKE_MEM_UNDEFINED(key, 32); + VALGRIND_MAKE_MEM_UNDEFINED(msg, 32); + ret = secp256k1_ec_seckey_tweak_add(ctx, key, msg); + VALGRIND_MAKE_MEM_DEFINED(&ret, sizeof(ret)); + CHECK(ret == 1); + + VALGRIND_MAKE_MEM_UNDEFINED(key, 32); + VALGRIND_MAKE_MEM_UNDEFINED(msg, 32); + ret = secp256k1_ec_seckey_tweak_mul(ctx, key, msg); + VALGRIND_MAKE_MEM_DEFINED(&ret, sizeof(ret)); + CHECK(ret == 1); + + /* Test context randomisation. Do this last because it leaves the context tainted. */ + VALGRIND_MAKE_MEM_UNDEFINED(key, 32); + ret = secp256k1_context_randomize(ctx, key); + VALGRIND_MAKE_MEM_DEFINED(&ret, sizeof(ret)); + CHECK(ret); + + secp256k1_context_destroy(ctx); + return 0; +} |