diff --git a/src/secp256k1/.travis.yml b/src/secp256k1/.travis.yml index 307ad1bad..93b1a7046 100644 --- a/src/secp256k1/.travis.yml +++ b/src/secp256k1/.travis.yml @@ -1,102 +1,119 @@ language: c -os: linux -dist: xenial +os: + - linux + - osx + +dist: bionic +# Valgrind currently supports upto macOS 10.13, the latest xcode of that version is 10.1 +osx_image: xcode10.1 addons: apt: packages: - gcc-multilib - libc6-dbg:i386 - libgmp-dev - libgmp-dev:i386 - libtool-bin - ninja-build - valgrind + homebrew: + packages: + - cmake + - gcc@9 + - gmp + - ninja + - valgrind + update: true install: - - ./travis/install_cmake.sh + - if [ "${TRAVIS_OS_NAME}" = "linux" ]; then ./travis/install_cmake.sh; fi cache: directories: - /opt/cmake compiler: - clang - gcc env: global: - FIELD=auto - BIGNUM=gmp - SCALAR=auto - ENDOMORPHISM=no - STATICPRECOMPUTATION=yes - ECMULTGENPRECISION=auto - ASM=no - AUTOTOOLS_TARGET=check - CMAKE_TARGET=check-secp256k1 - AUTOTOOLS_EXTRA_FLAGS= - CMAKE_EXTRA_FLAGS= - HOST= - ECDH=no - RECOVERY=no - SCHNORR=yes - EXPERIMENTAL=no - JNI=no - OPENSSL_TESTS=auto - MULTISET=no - CTIMETEST=yes - BENCH=yes - - SECP256K1_BENCH_ITERS=2 + - ITERS=2 jobs: - SCALAR=32bit RECOVERY=yes - SCALAR=32bit FIELD=32bit ECDH=yes EXPERIMENTAL=yes MULTISET=yes - SCALAR=64bit - FIELD=64bit RECOVERY=yes - FIELD=64bit ENDOMORPHISM=yes - FIELD=64bit ENDOMORPHISM=yes ECDH=yes EXPERIMENTAL=yes MULTISET=yes - FIELD=64bit ASM=x86_64 - FIELD=64bit ENDOMORPHISM=yes ASM=x86_64 - FIELD=32bit ENDOMORPHISM=yes - BIGNUM=no - BIGNUM=no ENDOMORPHISM=yes RECOVERY=yes EXPERIMENTAL=yes MULTISET=yes - BIGNUM=no STATICPRECOMPUTATION=no - AUTOTOOLS_TARGET=distcheck CMAKE_TARGET=install CTIMETEST= BENCH= - AUTOTOOLS_EXTRA_FLAGS=CPPFLAGS=-DDETERMINISTIC CMAKE_EXTRA_FLAGS=-DCMAKE_C_FLAGS=-DDETERMINISTIC - - AUTOTOOLS_EXTRA_FLAGS=CFLAGS=-O0 CMAKE_EXTRA_FLAGS=-DCMAKE_BUILD_TYPE=Debug + - AUTOTOOLS_EXTRA_FLAGS=CFLAGS=-O0 CMAKE_EXTRA_FLAGS=-DCMAKE_BUILD_TYPE=Debug CTIMETEST= - AUTOTOOLS_TARGET=check-java CMAKE_TARGET=check-secp256k1-java JNI=yes ECDH=yes EXPERIMENTAL=yes CTIMETEST= BENCH= - ECMULTGENPRECISION=2 - ECMULTGENPRECISION=8 + - VALGRIND=yes + BIGNUM=no ENDOMORPHISM=yes ASM=x86_64 EXPERIMENTAL=yes ECDH=yes RECOVERY=yes OPENSSL_TESTS=no MULTISET=yes + AUTOTOOLS_EXTRA_FLAGS=CPPFLAGS=-DVALGRIND AUTOTOOLS_TARGET= + CMAKE_EXTRA_FLAGS=-DCMAKE_C_FLAGS=-DVALGRIND CMAKE_TARGET="secp256k1-tests secp256k1-exhaustive_tests" + # The same as above but without endomorphism. + - VALGRIND=yes + BIGNUM=no ASM=x86_64 EXPERIMENTAL=yes ECDH=yes RECOVERY=yes OPENSSL_TESTS=no MULTISET=yes + AUTOTOOLS_EXTRA_FLAGS=CPPFLAGS=-DVALGRIND AUTOTOOLS_TARGET= + CMAKE_EXTRA_FLAGS=-DCMAKE_C_FLAGS=-DVALGRIND CMAKE_TARGET="secp256k1-tests secp256k1-exhaustive_tests" - SCHNORR=no jobs: fast_finish: true include: - compiler: clang + os: linux env: HOST=i686-linux-gnu ENDOMORPHISM=yes OPENSSL_TESTS=no - compiler: clang + os: linux env: HOST=i686-linux-gnu BIGNUM=no OPENSSL_TESTS=no - compiler: gcc + os: linux env: HOST=i686-linux-gnu ENDOMORPHISM=yes BIGNUM=no OPENSSL_TESTS=no - compiler: gcc + os: linux env: HOST=i686-linux-gnu OPENSSL_TESTS=no - - compiler: gcc - env: - - VALGRIND=yes - - BIGNUM=no ENDOMORPHISM=yes ASM=x86_64 EXPERIMENTAL=yes ECDH=yes RECOVERY=yes OPENSSL_TESTS=no MULTISET=yes - - AUTOTOOLS_EXTRA_FLAGS=CPPFLAGS=-DVALGRIND AUTOTOOLS_TARGET= - - CMAKE_EXTRA_FLAGS=-DCMAKE_C_FLAGS=-DVALGRIND CMAKE_TARGET="secp256k1-tests secp256k1-exhaustive_tests" - - compiler: gcc - env: # The same as above but without endomorphism. - - VALGRIND=yes - - BIGNUM=no ENDOMORPHISM=no ASM=x86_64 EXPERIMENTAL=yes ECDH=yes RECOVERY=yes OPENSSL_TESTS=no MULTISET=yes - - AUTOTOOLS_EXTRA_FLAGS=CPPFLAGS=-DVALGRIND AUTOTOOLS_TARGET= - - CMAKE_EXTRA_FLAGS=-DCMAKE_C_FLAGS=-DVALGRIND CMAKE_TARGET="secp256k1-tests secp256k1-exhaustive_tests" +before_script: + # This limits the iterations in the benchmarks below to ITER iterations. + - export SECP256K1_BENCH_ITERS="$ITERS" + +# travis auto terminates jobs that go for 10 minutes without printing to stdout, +# but travis_wait doesn't work well with forking programs like valgrind +# (https://docs.travis-ci.com/user/common-build-problems/#build-times-out-because-no-output-was-received https://github.com/bitcoin-core/secp256k1/pull/750#issuecomment-623476860) script: + - function keep_alive() { while true; do echo -en "\a"; sleep 60; done } + - keep_alive & - ./travis/build_autotools.sh - ./travis/build_cmake.sh - - # travis_wait extends the 10 minutes without output allowed (https://docs.travis-ci.com/user/common-build-problems/#build-times-out-because-no-output-was-received) - - # the `--error-exitcode` is required to make the test fail if valgrind found errors, otherwise it'll return 0 (http://valgrind.org/docs/manual/manual-core.html) - - if [ -n "$VALGRIND" ]; then - travis_wait 30 valgrind --error-exitcode=42 ./buildautotools/tests 16 && - travis_wait 30 valgrind --error-exitcode=42 ./buildautotools/exhaustive_tests; - fi - - if [ -n "$VALGRIND" ]; then - travis_wait 30 valgrind --error-exitcode=42 ./buildcmake/secp256k1-tests 16 && - travis_wait 30 valgrind --error-exitcode=42 ./buildcmake/secp256k1-exhaustive_tests; - fi + - kill %keep_alive + +after_script: + - valgrind --version diff --git a/src/secp256k1/src/modules/schnorr/schnorr_impl.h b/src/secp256k1/src/modules/schnorr/schnorr_impl.h index 818ba4489..b25d3521b 100644 --- a/src/secp256k1/src/modules/schnorr/schnorr_impl.h +++ b/src/secp256k1/src/modules/schnorr/schnorr_impl.h @@ -1,215 +1,220 @@ /*********************************************************************** * Copyright (c) 2017 Amaury SÉCHET * * Distributed under the MIT software license, see the accompanying * * file COPYING or http://www.opensource.org/licenses/mit-license.php. * ***********************************************************************/ #ifndef _SECP256K1_SCHNORR_IMPL_H_ #define _SECP256K1_SCHNORR_IMPL_H_ #include #include "schnorr.h" #include "field.h" #include "group.h" #include "hash.h" #include "ecmult.h" #include "ecmult_gen.h" /** * Custom Schnorr-based signature scheme. * * Signing: * Inputs: * 32-byte message m, * 32-byte scalar key x (!=0) * public key point P, * 32-byte scalar nonce k (!=0) * * Compute point R = k * G. Negate nonce if R.y is not a quadratic residue. * Compute scalar e = Hash(R.x || compressed(P) || m) mod n. * Compute scalar s = k + e * x. * The signature is (R.x, s). * * Verification: * Inputs: * 32-byte message m, * public key point P, * signature: (32-byte r, scalar s) * * Signature is invalid if s >= n or r >= p. * Compute scalar e = Hash(r || compressed(P) || m) mod n. * Option 1 (faster for single verification): * Compute point R = s * G - e * P. * Reject if R is infinity or R.y is not a quadratic residue. * Signature is valid if the serialization of R.x equals r. * Option 2 (allows batch validation): * Decompress x coordinate r into point R, with R.y a quadratic residue. * Reject if R is not on the curve. * Signature is valid if R + e * P - s * G == 0. */ static int secp256k1_schnorr_sig_verify( const secp256k1_ecmult_context* ctx, const unsigned char *sig64, secp256k1_ge *pubkey, const unsigned char *msg32 ) { secp256k1_gej Pj, Rj; secp256k1_fe Rx; secp256k1_scalar e, s; int overflow; VERIFY_CHECK(!secp256k1_ge_is_infinity(pubkey)); /* Extract s */ overflow = 0; secp256k1_scalar_set_b32(&s, sig64 + 32, &overflow); if (overflow) { return 0; } /* Extract R.x */ if (!secp256k1_fe_set_b32(&Rx, sig64)) { return 0; } /* Compute e */ secp256k1_schnorr_compute_e(&e, sig64, pubkey, msg32); /* Verify the signature */ secp256k1_scalar_negate(&e, &e); secp256k1_gej_set_ge(&Pj, pubkey); secp256k1_ecmult(ctx, &Rj, &Pj, &e, &s); if (secp256k1_gej_is_infinity(&Rj)) { return 0; } /* Check that R.x is what we expect */ if (!secp256k1_gej_eq_x_var(&Rx, &Rj)) { return 0; } /* Check that jacobi(R.y) is 1 */ if (!secp256k1_gej_has_quad_y_var(&Rj)) { return 0; } /* All good, we have a valid signature. */ return 1; } static int secp256k1_schnorr_compute_e( secp256k1_scalar* e, const unsigned char *r, secp256k1_ge *p, const unsigned char *msg32 ) { int overflow = 0; size_t size; secp256k1_sha256 sha; unsigned char buf[33]; secp256k1_sha256_initialize(&sha); /* R.x */ secp256k1_sha256_write(&sha, r, 32); /* compressed P */ secp256k1_eckey_pubkey_serialize(p, buf, &size, 1); VERIFY_CHECK(size == 33); secp256k1_sha256_write(&sha, buf, 33); /* msg */ secp256k1_sha256_write(&sha, msg32, 32); /* compute e */ secp256k1_sha256_finalize(&sha, buf); secp256k1_scalar_set_b32(e, buf, &overflow); return !overflow & !secp256k1_scalar_is_zero(e); } static int secp256k1_schnorr_sig_sign( const secp256k1_context* ctx, unsigned char *sig64, const unsigned char *msg32, const secp256k1_scalar *privkey, secp256k1_ge *pubkey, secp256k1_nonce_function noncefp, const void *ndata ) { secp256k1_ge R; secp256k1_gej Rj; secp256k1_scalar k, e, s; ARG_CHECK(secp256k1_ecmult_gen_context_is_built(&ctx->ecmult_gen_ctx)); VERIFY_CHECK(!secp256k1_scalar_is_zero(privkey)); VERIFY_CHECK(!secp256k1_ge_is_infinity(pubkey)); if (!secp256k1_schnorr_sig_generate_k(ctx, &k, msg32, privkey, noncefp, ndata)) { return 0; } /* Compute R */ secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &Rj, &k); secp256k1_ge_set_gej(&R, &Rj); + /* + * We declassify R to allow using it as a branch point. + * This is fine because R is not a secret. + */ + secp256k1_declassify(ctx, &R, sizeof(R)); /** Negate the nonce if R.y is not a quadratic residue. */ secp256k1_scalar_cond_negate(&k, !secp256k1_fe_is_quad_var(&R.y)); /* Compute the signature. */ secp256k1_fe_normalize(&R.x); secp256k1_fe_get_b32(sig64, &R.x); secp256k1_schnorr_compute_e(&e, sig64, pubkey, msg32); secp256k1_scalar_mul(&s, &e, privkey); secp256k1_scalar_add(&s, &s, &k); secp256k1_scalar_get_b32(sig64 + 32, &s); /* Cleanup locals that may contain private data. */ secp256k1_scalar_clear(&k); return 1; } static int secp256k1_schnorr_sig_generate_k( const secp256k1_context* ctx, secp256k1_scalar *k, const unsigned char *msg32, const secp256k1_scalar *privkey, secp256k1_nonce_function noncefp, const void *ndata ) { int ret = 0; unsigned int count = 0; unsigned char nonce32[32], seckey[32]; /* Seed used to make sure we generate different values of k for schnorr */ const unsigned char secp256k1_schnorr_algo16[17] = "Schnorr+SHA256 "; if (noncefp == NULL) { noncefp = secp256k1_nonce_function_default; } secp256k1_scalar_get_b32(seckey, privkey); while (1) { int overflow; ret = noncefp(nonce32, msg32, seckey, secp256k1_schnorr_algo16, (void*)ndata, count++); if (!ret) { break; } secp256k1_scalar_set_b32(k, nonce32, &overflow); overflow |= secp256k1_scalar_is_zero(k); /* The nonce is still secret here, but it overflowing or being zero is is less likely than 1:2^255. */ secp256k1_declassify(ctx, &overflow, sizeof(overflow)); if (!overflow) { break; } secp256k1_scalar_clear(k); } /* Cleanup locals that may contain private data. */ memset(seckey, 0, 32); memset(nonce32, 0, 32); return ret; } #endif diff --git a/src/secp256k1/travis/build_autotools.sh b/src/secp256k1/travis/build_autotools.sh index eaeff0e7c..3f5da8db6 100755 --- a/src/secp256k1/travis/build_autotools.sh +++ b/src/secp256k1/travis/build_autotools.sh @@ -1,72 +1,99 @@ #!/usr/bin/env bash export LC_ALL=C set -ex +# FIXME The java tests will fail on macOS with autotools due to the +# libsepc256k1_jni library referencing the libsecp256k1 library with an absolute +# path. This needs to be rewritten with install_name_tool to use relative paths +# via the @variables supported by the macOS loader. +if [ "$TRAVIS_OS_NAME" = "osx" ] && [ "$JNI" = "yes" ] +then + echo "Skipping the java tests built with autotools on OSX" + exit 0 +fi + if [ -n "$HOST" ]; then USE_HOST="--host=$HOST" fi if [ "x$HOST" = "xi686-linux-gnu" ]; then CC="$CC -m32" fi +if [ "$TRAVIS_OS_NAME" = "osx" ] && [ "$TRAVIS_COMPILER" = "gcc" ] +then + CC="gcc-9" +fi + +$CC --version + ./autogen.sh mkdir buildautotools pushd buildautotools ../configure \ --enable-experimental=$EXPERIMENTAL \ --enable-endomorphism=$ENDOMORPHISM \ --with-field=$FIELD \ --with-bignum=$BIGNUM \ --with-asm=$ASM \ --with-scalar=$SCALAR \ --enable-ecmult-static-precomputation=$STATICPRECOMPUTATION \ --with-ecmult-gen-precision=$ECMULTGENPRECISION \ --enable-module-ecdh=$ECDH \ --enable-module-multiset=$MULTISET \ --enable-module-recovery=$RECOVERY \ --enable-module-schnorr=$SCHNORR \ --enable-jni=$JNI \ --enable-openssl-tests=$OPENSSL_TESTS \ $AUTOTOOLS_EXTRA_FLAGS \ $USE_HOST print_logs() { cat tests.log || : cat exhaustive_tests.log || : cat valgrind_ctime_test.log || : cat bench.log || : } trap 'print_logs' ERR make -j2 $AUTOTOOLS_TARGET +if [ -n "$VALGRIND" ]; then + # the `--error-exitcode` is required to make the test fail if valgrind found + # errors, otherwise it'll return 0 + # (http://valgrind.org/docs/manual/manual-core.html) + valgrind --error-exitcode=42 ./tests 16 + valgrind --error-exitcode=42 ./exhaustive_tests +fi + if [ -n "$BENCH" ]; then if [ -n "$VALGRIND" ]; then - EXEC='libtool --mode=execute valgrind --error-exitcode=42'; + # Using the local `libtool` because on macOS the system's libtool has + # nothing to do with GNU libtool + EXEC='./libtool --mode=execute valgrind --error-exitcode=42'; else EXEC= ; fi - $EXEC ./bench_ecmult &>> bench.log - $EXEC ./bench_internal &>> bench.log - $EXEC ./bench_sign &>> bench.log - $EXEC ./bench_verify &>> bench.log + $EXEC ./bench_ecmult >> bench.log 2>&1 + $EXEC ./bench_internal >> bench.log 2>&1 + $EXEC ./bench_sign >> bench.log 2>&1 + $EXEC ./bench_verify >> bench.log 2>&1 if [ "$RECOVERY" == "yes" ]; then - $EXEC ./bench_recover &>> bench.log + $EXEC ./bench_recover >> bench.log 2>&1 fi if [ "$ECDH" == "yes" ]; then - $EXEC ./bench_ecdh &>> bench.log + $EXEC ./bench_ecdh >> bench.log 2>&1 fi if [ "$MULTISET" == "yes" ]; then - $EXEC ./bench_multiset &>> bench.log + $EXEC ./bench_multiset >> bench.log 2>&1 fi fi if [ -n "$CTIMETEST" ]; then - libtool --mode=execute valgrind ./valgrind_ctime_test &> valgrind_ctime_test.log + ./libtool --mode=execute valgrind --error-exitcode=42 ./valgrind_ctime_test > valgrind_ctime_test.log 2>&1 fi popd diff --git a/src/secp256k1/travis/build_cmake.sh b/src/secp256k1/travis/build_cmake.sh index 6eca74922..1fea07607 100755 --- a/src/secp256k1/travis/build_cmake.sh +++ b/src/secp256k1/travis/build_cmake.sh @@ -1,44 +1,61 @@ #!/usr/bin/env bash export LC_ALL=C set -ex if [ "x$HOST" = "xi686-linux-gnu" ]; then CMAKE_EXTRA_FLAGS="$CMAKE_EXTRA_FLAGS -DCMAKE_C_FLAGS=-m32" fi +if [ "$TRAVIS_OS_NAME" = "osx" ] && [ "$TRAVIS_COMPILER" = "gcc" ] +then + CMAKE_EXTRA_FLAGS="$CMAKE_EXTRA_FLAGS -DCMAKE_C_COMPILER=gcc-9" +fi # "auto" is not a valid value for SECP256K1_ECMULT_GEN_PRECISION with cmake. # In this case we use the default value instead by not setting the cache # variable on the cmake command line. if [ "x$ECMULTGENPRECISION" != "xauto" ]; then ECMULT_GEN_PRECISION_ARG="-DSECP256K1_ECMULT_GEN_PRECISION=$ECMULTGENPRECISION" fi mkdir -p buildcmake/install pushd buildcmake -# Use the cmake version installed via the install_cmake.sh script. -CMAKE_COMMAND=/opt/cmake/bin/cmake +# Use the cmake version installed via the install_cmake.sh script on linux +if [ "$TRAVIS_OS_NAME" = "linux" ] +then + CMAKE_COMMAND=/opt/cmake/bin/cmake +else + CMAKE_COMMAND=cmake +fi ${CMAKE_COMMAND} --version ${CMAKE_COMMAND} -GNinja .. \ -DCMAKE_INSTALL_PREFIX=install \ -DSECP256K1_BUILD_OPENSSL_TESTS=$OPENSSL_TESTS \ -DSECP256K1_ECMULT_STATIC_PRECOMPUTATION=$STATICPRECOMPUTATION \ -DSECP256K1_ENABLE_MODULE_ECDH=$ECDH \ -DSECP256K1_ENABLE_MODULE_MULTISET=$MULTISET \ -DSECP256K1_ENABLE_MODULE_RECOVERY=$RECOVERY \ -DSECP256K1_ENABLE_MODULE_SCHNORR=$SCHNORR \ -DSECP256K1_ENABLE_JNI=$JNI \ -DSECP256K1_ENABLE_ENDOMORPHISM=$ENDOMORPHISM \ -DSECP256K1_ENABLE_BIGNUM=$BIGNUM \ -DSECP256K1_USE_ASM=$ASM \ -DUSE_FIELD=$FIELD \ -DUSE_SCALAR=$SCALAR \ $ECMULT_GEN_PRECISION_ARG \ $CMAKE_EXTRA_FLAGS ninja $CMAKE_TARGET +if [ -n "$VALGRIND" ]; then + # the `--error-exitcode` is required to make the test fail if valgrind found + # errors, otherwise it'll return 0 + # (http://valgrind.org/docs/manual/manual-core.html) + valgrind --error-exitcode=42 ./secp256k1-tests 16 + valgrind --error-exitcode=42 ./secp256k1-exhaustive_tests +fi + popd