It seems that the following 4 lines should be wrapped in an #ifdef USE_ENDOMORPHISM:

https://github.com/bitcoin/secp256k1/blob/master/src/group_impl.h#L396-L399

An API which actually does end-to-end key derivation, ECDSA, Schnorr signatures, ....

it will probably need a accept a struct with function pointers for generating random bytes, hashing, ...

From #26, this needs support for deterministic signing.

When running on arm/ios, secp256k1_start() fails with assertion:
#4 0x0002878a in secp256k1_num_mod_inverse at /path/secp256k1/impl/num_gmp.h:134
#5 0x00028516 in secp256k1_fe_inv_var at /path/secp256k1/impl/field.h:138
#6 0x0002691e in secp256k1_ge_set_gej at /path/secp256k1/impl/group.h:58
#7 0x00025f3e in secp256k1_ecmult_start at /path/secp256k1/impl/ecmult.h:89
#8 0x00025db0 in secp256k1_start at /path/secp256k1/secp256k1.c:22

Assertion fails in secp256k1_num_mod_inverse():
mp_size_t sn = NUM_LIMBS+1;
mp_size_t gn = mpn_gcdext(g, r->data, &sn, u, m->limbs, v, m->limbs);
assert(gn == 1); <==

Compiled with std=gnu99, USE_NUM_GMP, USE_FIELD_GMP, and USE_FIELD_INV_NUM.

What's the significance of USE_FIELD_INV_NUM and Field settings? Any thoughts on compile settings for arm?

POSIX reserves the ends-with-_t-namespace, libsecp256k1's internal types should be called something else.

I've just read the abstract to Just a Little Bit More,
Joop van de Pol and Nigel P. Smart and Yuval Yarom.

I'm not well versed in side-channel analysis, and I cannot tell from the abstract if that method could feasibly compromise secret bits when this library is used to generate signatures. I'm hoping for an explanation and/or discussion here about that.

I propose these end results to close this ticket:

If this library is vulnerable to this kind of side-channel analysis, document why in the README, then put the best mitigation on the roadmap.

If this library is not vulnerable to that kind of analysis, then a concise comparison between OpenSSL and this library could motivate a transition in Bitcoin (or perhaps even improvements to OpenSSL or the wider ecosystem, if you're an optimist).

Environment:

clang version 3.4 (tags/RELEASE_34/final)
Target: x86_64-unknown-linux-gnu

Warnings:

  CC     src/libsecp256k1_la-secp256k1.lo
In file included from src/secp256k1.c:13:
In file included from ./src/field_impl.h:19:
In file included from ./src/field_5x52_impl.h:20:
./src/field_5x52_asm_impl.h:29:5: warning: string literal of length 3425 exceeds
      maximum length 509 that C90 compilers are required to support
      [-Woverlength-strings]
    "movq 0(%%rsi),%%r10\n"
    ^~~~~~~~~~~~~~~~~~~~~~~
./src/field_5x52_asm_impl.h:299:5: warning: string literal of length 2541
      exceeds maximum length 509 that C90 compilers are required to support
      [-Woverlength-strings]
    "movq 0(%%rsi),%%r10\n"
    ^~~~~~~~~~~~~~~~~~~~~~~
In file included from src/secp256k1.c:14:
In file included from ./src/scalar_impl.h:20:
./src/scalar_4x64_impl.h:262:5: warning: string literal of length 1191 exceeds
      maximum length 509 that C90 compilers are required to support
      [-Woverlength-strings]
    "movq 32(%%rsi), %%r11\n"
    ^~~~~~~~~~~~~~~~~~~~~~~~~
./src/scalar_4x64_impl.h:368:5: warning: string literal of length 821 exceeds
      maximum length 509 that C90 compilers are required to support
      [-Woverlength-strings]
    "movq %q9, %%r11\n"
    ^~~~~~~~~~~~~~~~~~~
./src/scalar_4x64_impl.h:567:5: warning: string literal of length 1643 exceeds
      maximum length 509 that C90 compilers are required to support
      [-Woverlength-strings]
    "movq 0(%%rdi), %%r15\n"
    ^~~~~~~~~~~~~~~~~~~~~~~~
./src/scalar_4x64_impl.h:733:5: warning: string literal of length 1383 exceeds
      maximum length 509 that C90 compilers are required to support
      [-Woverlength-strings]
    "movq 0(%%rdi), %%r11\n"
    ^~~~~~~~~~~~~~~~~~~~~~~~
6 warnings generated.
  CCLD   libsecp256k1.la

Hi,

I'm working on Rust language bindings for bitcoin-secp256k1 and I can't get tests verifing the compact signatures to work:

The code is here:
https://github.com/dpc/bitcoin-secp256k1-rs/blob/master/src/secp256k1.rs#L354

The results are here:

running 8 tests
test sign_and_verify ... ok
test sign_compact ... FAILED
test valid_pubkey_compressed ... ok
test sign ... ok
test invalid_pubkey ... ok
test valid_pubkey_uncompressed ... ok
test sign_and_verify_fail ... ok
test sign_compact_with_recovery ... FAILED

failures:

---- sign_compact stdout ----
        task 'sign_compact' failed at 'assertion failed: `(left == right) && (right == left)` (left: `Err(InvalidSignature)`, right: `Ok(true)`)', src/secp256k1.rs:370


---- sign_compact_with_recovery stdout ----
        task 'sign_compact_with_recovery' failed at 'assertion failed: `(left == right) && (right == left)` (left: `Err(InvalidSignature)`, right: `Ok(true)`)', src/secp256k1.rs:392



failures:
    sign_compact
    sign_compact_with_recovery

test result: FAILED. 6 passed; 2 failed; 0 ignored; 0 measured

task '<main>' failed at 'Some tests failed', /home/dpc/opt/src/rust/src/libtest/lib.rs:242
An unknown error occurred

make: *** [test] Error 1

Am I missing something obvious?

In https://github.com/bitcoin/secp256k1/blob/master/src/ecdsa_impl.h the public key recovery method ends with:
secp256k1_ecmult(&qj, &xj, &u2, &u1);
secp256k1_ge_set_gej_var(pubkey, &qj);
secp256k1_num_free(&rn);
secp256k1_num_free(&u1);
secp256k1_num_free(&u2);
return 1;
}
The public key is stored in qj. And, afterward, always returns 1 (success). Nevertheless it is possible to choose the values r,s of the ECDSA signature so that qj end up being the point-of-infinity. qj is copied to pubkey and transformed from Jacobian coordinates into affine coordinates. In the current version of secp256k1_ge_set_gej_var(), only the infinity field is copied, so the remaining fields are left in an undefined (platform-dependent) state. If Bitcoin (using a new opcode) or other cryptocurrency were to rely on this method to obtain a pubkey, the blockchain could be forked by including in a block a transaction containing a specially crafted signature what is valid on one platform but invalid on another.
The solution is to insert the appropriate infinity check between ecmult and set_qej:

secp256k1_ecmult(&qj, &xj, &u2, &u1);
If (secp256k1_gej_is_infinity(&qj)) {
return 0;
}
secp256k1_ge_set_gej_var(pubkey, &qj);

In Bitcoin this method is used in the by verifymessage RPC method or GUI dialog. This means that it may be possible in theory to verify an incorrect signature.
Nevertheless, I see it very hard that by chance (pubkey.GetID() == keyID) in rpcmisc.cpp, In other words, the contents of the memory area of qj overlaps with pubkey, which is not expanded in the stack (only the KeyID is stored). Something similar happens with (!(CBitcoinAddress(pubkey.GetID()) == addr)) in signverifymessagedialog.cpp.

But a vulnerability must not be ruled out without an complete analysis of the stack state during the execution of secp256k1_ecdsa_sig_recover()

As both tests.c and bench.c include the the _impl.h h headers, they should be self-contained, and not need linking with libsecp256k1.la.

They do need the assembly code though, if it is used.

Ping @theuni?

It seems that when you first built with assembly code, and later without, the .a file with the assembly object is still linked into the binary.

Would #70 fix this as well?

Sorry if this is a silly question but after compilation how do I use it? I found the static lib in /usr/local/lib/libsecp256k1.a and I am able to reference it, are there any examples on how to use it from Xcode?

So far we have manually checkable proofs for the field mul and square inner loops, and machine verification (via frama-c) of overflow-freeness for 10x26 (5x52 requires hacking on frama-c to get a 128 bit type into it.)

I believe know how to machine check the field and scalar in a reasonable amount of time, but not straight from the C; so the effort would be one-time and rot, and I'm not sure it's worth the time.

There may be other areas of the code that are good targets for formal methods. I'd hoped previously to get some researchers working in this space interested; but so far no luck.

when i run this program i get a segfault:
http://paste.ubuntu.com/7908084/
in line 76,
I just cant get this to work, any help is greatly appreciated

./autogen.sh

Makefile.am:3: Libtool library used but LIBTOOL' is undefined Makefile.am:3: The usual way to defineLIBTOOL' is to add LT_INIT' Makefile.am:3: toconfigure.ac' and run aclocal' andautoconf' again.
Makefile.am:3: If LT_INIT' is inconfigure.ac', make sure
Makefile.am:3: its definition is in aclocal's search path.
autoreconf: automake failed with exit status: 1

Any idea?

I'm creating this issue to contain some of the assorted ongoing plans for review pipeline work to achieve a initial non-experimental release. We're still a considerable way off from potentially using this software in production for verification in Bitcoin (deployment first /requires/ a canonical signatures soft-fork), but when that time comes to avoid delays we need to make sure we're not stuck waiting on an assurance process.

We have funding available we can use for both external review, as well as bounties. I'm somewhat concerned that there is a non-trivial equality issue with respect to the hardworking ongoing contributors, who've delivered demonstrated results, not getting paid when we'd think of paying a drive by review; so we need to think carefully about what value we're getting.

One of the things that I've said I'd like to do with respect to bounties is to turn it around: Part of the reason that review on mature software is often unrewarding is because the probability of finding something is fairly low. By release time our testing infrastructure alone should be (and perhaps already is) close to a point where any the possibility of any plausible bug is excluded. To test that theory, we could have a bounty not (just) for bugs in the software, but for the ability to add any plausible mistake in the software which the tests are unable to detect. Since, for the most part, the tests are inherently not sound it should at least be theoretically possible to do this, and at least the odds may be better, so it may be more fun to participate.

Some of the announcements with respect to things like performance may also bring in some more participants in the project, so we ought to think about how best to time that.

ae9c5916ffe9cb5bca3d6bb5b2afbacd9b690dc880e1918ae4d5261f35d371db

On OSX using GCC 4.8, numerous warning: expression result unused [-Wunused-value] from VERIFY_CHECK and ECMULT_TABLE_GET_GE

Constant time, constant memory access operations for secret data should make additional blinding unnecessary. But at least init-time static blinding can be done basically at no cost by baking it into the tables; and may afford some protection against EMI/power side-channels or timing in cases where a compiler has undermined the constant time operation.

We already do the novel unknown discrete log blinding. I'd held off previously adding more because we didn't have a hash function (e.g. to generate random unknown points for each table row). But we do now. Peter has also expressed some interest here.

When running autogen:

Makefile.am:45: warning: source file 'src/secp256k1.c' is in a subdirectory,
Makefile.am:45: but option 'subdir-objects' is disabled
automake: warning: possible forward-incompatibility.
automake: At least a source file is in a subdirectory, but the 'subdir-objects'
automake: automake option hasn't been enabled.  For now, the corresponding output
automake: object file(s) will be placed in the top-level directory.  However,
automake: this behaviour will change in future Automake versions: they will
automake: unconditionally cause object files to be placed in the same subdirectory
automake: of the corresponding sources.
automake: You are advised to start using 'subdir-objects' option throughout your
automake: project, to avoid future incompatibilities.
Makefile.am:62: warning: source file 'src/bench_inv.c' is in a subdirectory,
Makefile.am:62: but option 'subdir-objects' is disabled
Makefile.am:56: warning: source file 'src/bench_recover.c' is in a subdirectory,
Makefile.am:56: but option 'subdir-objects' is disabled
Makefile.am:59: warning: source file 'src/bench_sign.c' is in a subdirectory,
Makefile.am:59: but option 'subdir-objects' is disabled
Makefile.am:53: warning: source file 'src/bench_verify.c' is in a subdirectory,
Makefile.am:53: but option 'subdir-objects' is disabled
Makefile.am:70: warning: source file 'src/tests.c' is in a subdirectory,
Makefile.am:70: but option 'subdir-objects' is disabled

Existing 'best effort' zeriozation for private data is hardly even best effort. At a minimum we should consider doing this via an extern-ed function and memset_s if available. No guarantees can still be provided, of course.

We might also consider wrapping the API entrance of private data handling functions like:

handle_data(){
ret=handle_data_impl();
handle_data_zero_stack();
return ret;
}

Where _zero_stack uses slightly more stack than the whole callgraph for _impl and zeros it, in order to catch private data spilled onto the stack during execution before returning outside of our control.

I'm not sure where exactly where the line between best effort and security theatre is... there is only so much that can really be done (esp in portable code) here.

Does signing a messge using secp256k1_ecdsa_sign in this library require a random number generator? Are there any plans to implement RFC 6979 which describes a scheme that would make the signing process completeley determinisitc? That would make the library useful for signing messages on embedded systems where there isn't sufficient entropy such as the recently released trezor.

I'm wondering if it would be possible to get a performance improvement using vector processor acceleration for scalar math, either directly with NEON/SSE instructions, or using math libraries like vecLib/MKL/ACML

I don't know too much about it myself, or what security issues their might be when handling private key data, but presumably the security concerns would be less of an issue when verifying signatures.

A native (and perhaps naive) num implementation would be nice, so libsecp256k1 can be built entirely dependencyless.

The largest challenge is probably a fast modular inverse.

When exporting a private key, the compressed flag is required to create the correct DER key.

I noticed that secp256k1_ec_privkey_import() only takes a pointer for a secret key. I think it should take an int * to inform whether the key should be serialized to its compressed representation.

I'll try have a look see if it's a straightforward change, though my C isn't the best. Does this seem worthwhile, or was there perhaps a reason it doesn't do this?

typo here:
https://github.com/bitcoin/secp256k1/blob/master/src/field_5x52_int128_impl.h#L18

s/RESTICT/RESTRICT

https://github.com/bitcoin/secp256k1/blob/master/src/group.h#L37

Particularly being able to access the generator point is useful.

We've seen some people attempting to use the library calling into random internal functions. That should be harder to do now... but now that the basic signature interface is relatively safe to use (as such things go) there should be some easy copy and paste examples for correct usage.

The group operations seem to generally assume input x,y,z can be multiplied directly i.e. there is an implicit mag 8 requirement, which could be worth adding verification for. In some group operations (broadly speaking those where special z values are in play, either gej_add_ge or coz) the input field values are normalized, usually to ensure that they are mag 6 or so (I am presupposing zero tests for h/i replacing u?/s? equality checks), but it varies. In practice the group ops don't produce higher than 6 mag anyway, so there's some waste here (and some performance-neutral jiggling might lower the output mags).

So I'm proposing to i) add pre/post verification for the current mag 8 assumptions, then ii) explore whether tightening the requirements can improve performance. At this stage, I'm only envisaging a simple global requirement, not op-specific bounds.

Thoughts?

What is the recommended way to add 2 points?

I see:

Create point: void static secp256k1_gej_set_xy(secp256k1_gej_t *r, const secp256k1_fe_t *x, const secp256k1_fe_t *y);

Add both points: void static secp256k1_gej_add(secp256k1_gej_t *r, const secp256k1_gej_t *a, const secp256k1_gej_t *b);

And then finally convert the jacobian point back into a cartesian value (0x04, x, y) as used in Bitcoin.

(using x/z^2 and y/z^3 as it says in group.h)

GCC -fstack-usage can return the usage per function, now that we've eliminated the var arrays.

We should probably commit to some value as part of the interface. If we do, some thought should be given to future batch/semi-batch verification.

Hello,

I started to dig deeper into the implementation and stumbled over a small issue with the magnitudes.

From field_10x26_impl.h, the function secp256k1_fe_verify

    r &= (a->magnitude >= 0);
    r &= (a->magnitude <= 32);

while in field_5x52_impl.h the function is

    r &= (a->magnitude >= 0);
    r &= (a->magnitude <= 2048);

This means that multiplying a number with the constant value 100 is totally fine on a 64-bit machine, but will lead to an error on 32-bit machines, which IMHO is bad. The two implementation should have the same external interface.

Finally, is there a good reason for the 2 * in the second line of secp256k1_fe_verify? Why is the magnitude given in multiple of 2's? Doesn't the code work with odd magnitudes? This also means that one cannot express that magnitude should be 1 without having a fully normalized number.

This library is experimental, use at your own risk, ...

Yuval Yarom pointed us to this presentation https://cryptojedi.org/peter/data/chesrump-20130822.pdf
which suggests that on at least some hardware uniform cacheline access is not enough, presumably because the loads have multi-cycle delays and earlier bytes are being made available earlier (?).

The obvious defense is to read all the bytes, which is what we expected cacheline colocation to do so doing it explicitly shouldn't require more memory bandwidth, and then extract the data we want.

A kludgy implementation given our current memory layout (and typedefs, pardon the typepunning) is:

diff --git a/src/ecmult_gen_impl.h b/src/ecmult_gen_impl.h
index 07859ab..157ab05 100644
--- a/src/ecmult_gen_impl.h
+++ b/src/ecmult_gen_impl.h
@@ -104,14 +104,32 @@ static void secp256k1_ecmult_gen(secp256k1_gej_t *r, const secp256k1_scalar_t *g
     const secp256k1_ecmult_gen_consts_t *c = secp256k1_ecmult_gen_consts;
     secp256k1_gej_set_infinity(r);
     secp256k1_ge_t add;
-    int bits;
+    uint32_t bits;
+    uint32_t bpos;
     for (int j=0; j<64; j++) {
         bits = secp256k1_scalar_get_bits(gn, j * 4, 4);
+        bpos = (1<<((bits&3)<<3))*255;
+        int b2 = (bits>>2)&1;
+        int b3 = (bits>>3)&1;
+        uint32_t maska = bpos*!(b2|b3);
+        uint32_t maskb = bpos*(b2&!b3);
+        uint32_t maskc = bpos*(b3&!b2);
+        uint32_t maskd = bpos*(b2&b3);
+        bits = (bits&3)<<3;
         for (size_t k=0; k<sizeof(secp256k1_ge_t); k++)
-            ((unsigned char*)(&add))[k] = c->prec[j][k][bits];
+        {
+            uint32_t *p;
+            p = (uint32_t *)c->prec[j][k];
+            uint32_t ra = maska & p[0];
+            uint32_t rb = maskb & p[1];
+            uint32_t rc = maskc & p[2];
+            uint32_t rd = maskd & p[3];
+            ((unsigned char*)(&add))[k] = (ra|rb|rc|rd)>>bits;
+        }
         secp256k1_gej_add_ge(r, r, &add);
     }
     bits = 0;
+    bpos = 0;
     secp256k1_ge_clear(&add);
 }

Is something like this something we'd like to do?

There should be a public interface offering a constant-time generic multiexp, e.g. out_point = s1_P1 + s2_P2 + ... + sn*Pn, for use in ECDH and ECDH with forward secrecy. (unless there is some speedup I'm not thinking of which only works for the non-multiexp case).

Maybe API wise it could split precomputation and the multiply, for applications where points are reused? e.g. pass in a set of precomputed tables?

checking for yasm... no
checking gmp.h usability... no
checking gmp.h presence... no
checking for gmp.h... no
configure: error: no working bignum implementation found

on Ubuntu 14.04
no problems checking out #ae2679b

In (see the note "MISSING"):

int secp256k1_ecdsa_sign(const unsigned char *msg32, unsigned char *signature, int *signaturelen, const unsigned char *seckey, const unsigned char *nonce) {

.....
if (ret) {
ret = secp256k1_ecdsa_sig_sign(&sig, &sec, &msg, &non, NULL);
}
if (ret) {
// MISSING "ret = "
secp256k1_ecdsa_sig_serialize(signature, signaturelen, &sig);
}
...
return ret;
}

The existing tests are generally pretty powerful but have relatively few static vectors, and mostly depend on lots of cycles to get good coverage. For deployment, it would be good to have a acceptably compact (maybe even small enough to just go in the production lib and run as part of _start()) vectors that achieve relative (as much as tests can) completeness on every use.

Locally I have an enormous collection of random (from various strategies) and white-box constructed vectors from many cpu months, about 30 gigabytes worth since I started saving 'effective' ones which so far have mostly just been used to check agreement with OpenSSL. I'm currently measuring branch/condition hits for each of them in each of our compile configurations, and then I plan on running a set-cover solver to reduce them to a (hopefully!) small set.

I'm a tad stuck now using secp256k1 on Windows which makes life harder. I have compiled GMP-6.0.0a and used the static lib to compile secp256k1. Everything goes without fault. However when I use the secp256k1 in a coin I get the errors below when compiling. Any help with this would be appreciated, I have tried linking lgmp straight into the client to see if this resolves the issue without joy.

C:/deps/secp256k1/.libs\libsecp256k1.a(libsecp256k1_la-secp256k1.o): In function _gmpn_sub': c:/mingw32/i686-w64-mingw32/include/gmp.h:2168: undefined reference to__gmpn_sub_n'
c:/mingw32/i686-w64-mingw32/include/gmp.h:2168: undefined reference to __gmpn_sub_n' C:/deps/secp256k1/.libs\libsecp256k1.a(libsecp256k1_la-secp256k1.o): In functionsecp256k1_num_set_bin':
c:\deps\secp256k1/src/num_gmp_impl.h:73: undefined reference to __gmpn_set_str' C:/deps/secp256k1/.libs\libsecp256k1.a(libsecp256k1_la-secp256k1.o): In functionsecp256k1_num_shift':
c:\deps\secp256k1/src/num_gmp_impl.h:267: undefined reference to __gmpn_rshift' C:/deps/secp256k1/.libs\libsecp256k1.a(libsecp256k1_la-secp256k1.o): In function_gmpn_add':
Makefile.Release:303: recipe for target 'release\deepcoin-qt.exe' failed
mingw32-make[1]: Leaving directory 'E:/GitHub/build-deepcoin-qt-Desktop_4_8_5-Release'
Makefile:34: recipe for target 'release' failed
c:/mingw32/i686-w64-mingw32/include/gmp.h:2129: undefined reference to __gmpn_add_n' C:/deps/secp256k1/.libs\libsecp256k1.a(libsecp256k1_la-secp256k1.o): In functionsecp256k1_fe_reduce':
c:\deps\secp256k1/src/field_gmp_impl.h:133: undefined reference to __gmpn_addmul_1' c:\deps\secp256k1/src/field_gmp_impl.h:134: undefined reference to__gmpn_addmul_1'
c:\deps\secp256k1/src/field_gmp_impl.h:137: undefined reference to __gmpn_mul_1' c:\deps\secp256k1/src/field_gmp_impl.h:140: undefined reference to__gmpn_addmul_1'
C:/deps/secp256k1/.libs\libsecp256k1.a(libsecp256k1_la-secp256k1.o): In function _gmpn_add': c:/mingw32/i686-w64-mingw32/include/gmp.h:2129: undefined reference to__gmpn_add_n'
C:/deps/secp256k1/.libs\libsecp256k1.a(libsecp256k1_la-secp256k1.o): In function secp256k1_fe_sqr': c:\deps\secp256k1/src/field_gmp_impl.h:159: undefined reference to__gmpn_sqr'
C:/deps/secp256k1/.libs\libsecp256k1.a(libsecp256k1_la-secp256k1.o): In function secp256k1_fe_mul': c:\deps\secp256k1/src/field_gmp_impl.h:151: undefined reference to__gmpn_mul_n'
C:/deps/secp256k1/.libs\libsecp256k1.a(libsecp256k1_la-secp256k1.o): In function secp256k1_num_mod_inverse': c:\deps\secp256k1/src/num_gmp_impl.h:144: undefined reference to__gmpn_gcdext'
C:/deps/secp256k1/.libs\libsecp256k1.a(libsecp256k1_la-secp256k1.o): In function _gmpn_sub': c:/mingw32/i686-w64-mingw32/include/gmp.h:2168: undefined reference to__gmpn_sub_n'
C:/deps/secp256k1/.libs\libsecp256k1.a(libsecp256k1_la-secp256k1.o): In function secp256k1_num_get_bin': c:\deps\secp256k1/src/num_gmp_impl.h:58: undefined reference to__gmpn_get_str'
C:/deps/secp256k1/.libs\libsecp256k1.a(libsecp256k1_la-secp256k1.o): In function secp256k1_num_mul': c:\deps\secp256k1/src/num_gmp_impl.h:231: undefined reference to__gmpn_mul'
c:\deps\secp256k1/src/num_gmp_impl.h:235: undefined reference to __gmpn_copyi' c:\deps\secp256k1/src/num_gmp_impl.h:229: undefined reference to__gmpn_mul'
C:/deps/secp256k1/.libs\libsecp256k1.a(libsecp256k1_la-secp256k1.o): In function secp256k1_num_mod': c:\deps\secp256k1/src/num_gmp_impl.h:108: undefined reference to__gmpn_tdiv_qr'
C:/deps/secp256k1/.libs\libsecp256k1.a(libsecp256k1_la-secp256k1.o): In function _gmpn_add': c:/mingw32/i686-w64-mingw32/include/gmp.h:2129: undefined reference to__gmpn_add_n'
c:/mingw32/i686-w64-mingw32/include/gmp.h:2129: undefined reference to __gmpn_add_n' c:/mingw32/i686-w64-mingw32/include/gmp.h:2129: undefined reference to__gmpn_add_n'
C:/deps/secp256k1/.libs\libsecp256k1.a(libsecp256k1_la-secp256k1.o): In function secp256k1_fe_mul_int': c:\deps\secp256k1/src/field_gmp_impl.h:116: undefined reference to__gmpn_mul_1'
C:/deps/secp256k1/.libs\libsecp256k1.a(libsecp256k1_la-secp256k1.o): In function _gmpn_add': c:/mingw32/i686-w64-mingw32/include/gmp.h:2129: undefined reference to__gmpn_add_n'
C:/deps/secp256k1/.libs\libsecp256k1.a(libsecp256k1_la-secp256k1.o): In function secp256k1_fe_mul_int': c:\deps\secp256k1/src/field_gmp_impl.h:116: undefined reference to__gmpn_mul_1'
c:\deps\secp256k1/src/field_gmp_impl.h:116: undefined reference to __gmpn_mul_1' C:/deps/secp256k1/.libs\libsecp256k1.a(libsecp256k1_la-secp256k1.o): In function_gmpn_add':
c:/mingw32/i686-w64-mingw32/include/gmp.h:2129: undefined reference to __gmpn_add_n' c:/mingw32/i686-w64-mingw32/include/gmp.h:2129: undefined reference to__gmpn_add_n'
C:/deps/secp256k1/.libs\libsecp256k1.a(libsecp256k1_la-secp256k1.o): In function secp256k1_fe_mul_int': c:\deps\secp256k1/src/field_gmp_impl.h:116: undefined reference to__gmpn_mul_1'
c:\deps\secp256k1/src/field_gmp_impl.h:116: undefined reference to __gmpn_mul_1' c:\deps\secp256k1/src/field_gmp_impl.h:116: undefined reference to__gmpn_mul_1'
C:/deps/secp256k1/.libs\libsecp256k1.a(libsecp256k1_la-secp256k1.o): In function _gmpn_add': c:/mingw32/i686-w64-mingw32/include/gmp.h:2129: undefined reference to__gmpn_add_n'
C:/deps/secp256k1/.libs\libsecp256k1.a(libsecp256k1_la-secp256k1.o): In function secp256k1_fe_mul_int': c:\deps\secp256k1/src/field_gmp_impl.h:116: undefined reference to__gmpn_mul_1'
C:/deps/secp256k1/.libs\libsecp256k1.a(libsecp256k1_la-secp256k1.o): In function _gmpn_add': c:/mingw32/i686-w64-mingw32/include/gmp.h:2129: undefined reference to__gmpn_add_n'
c:/mingw32/i686-w64-mingw32/include/gmp.h:2129: undefined reference to __gmpn_add_n' C:/deps/secp256k1/.libs\libsecp256k1.a(libsecp256k1_la-secp256k1.o): In functionsecp256k1_fe_mul_int':
c:\deps\secp256k1/src/field_gmp_impl.h:116: undefined reference to __gmpn_mul_1' c:\deps\secp256k1/src/field_gmp_impl.h:116: undefined reference to__gmpn_mul_1'
c:\deps\secp256k1/src/field_gmp_impl.h:116: undefined reference to __gmpn_mul_1' c:\deps\secp256k1/src/field_gmp_impl.h:116: undefined reference to__gmpn_mul_1'
c:\deps\secp256k1/src/field_gmp_impl.h:116: undefined reference to __gmpn_mul_1' C:/deps/secp256k1/.libs\libsecp256k1.a(libsecp256k1_la-secp256k1.o): In function_gmpn_add':
c:/mingw32/i686-w64-mingw32/include/gmp.h:2129: undefined reference to __gmpn_add_n' C:/deps/secp256k1/.libs\libsecp256k1.a(libsecp256k1_la-secp256k1.o): In functionsecp256k1_fe_mul_int':
c:\deps\secp256k1/src/field_gmp_impl.h:116: undefined reference to __gmpn_mul_1' C:/deps/secp256k1/.libs\libsecp256k1.a(libsecp256k1_la-secp256k1.o): In function_gmpn_add':
c:/mingw32/i686-w64-mingw32/include/gmp.h:2129: undefined reference to __gmpn_add_n' c:/mingw32/i686-w64-mingw32/include/gmp.h:2129: undefined reference to__gmpn_add_n'
c:/mingw32/i686-w64-mingw32/include/gmp.h:2129: undefined reference to __gmpn_add_n' C:/deps/secp256k1/.libs\libsecp256k1.a(libsecp256k1_la-secp256k1.o): In functionsecp256k1_fe_add':
c:/mingw32/i686-w64-mingw32/include/gmp.h:2129: undefined reference to __gmpn_add_n' C:/deps/secp256k1/.libs\libsecp256k1.a(libsecp256k1_la-secp256k1.o): In functionsecp256k1_fe_mul_int':
c:\deps\secp256k1/src/field_gmp_impl.h:116: undefined reference to __gmpn_mul_1' C:/deps/secp256k1/.libs\libsecp256k1.a(libsecp256k1_la-secp256k1.o): In function_gmpn_add':
c:/mingw32/i686-w64-mingw32/include/gmp.h:2129: undefined reference to __gmpn_add_n' c:/mingw32/i686-w64-mingw32/include/gmp.h:2129: undefined reference to__gmpn_add_n'
c:/mingw32/i686-w64-mingw32/include/gmp.h:2129: undefined reference to __gmpn_add_n' c:/mingw32/i686-w64-mingw32/include/gmp.h:2129: undefined reference to__gmpn_add_n'
c:/mingw32/i686-w64-mingw32/include/gmp.h:2129: undefined reference to __gmpn_add_n' C:/deps/secp256k1/.libs\libsecp256k1.a(libsecp256k1_la-secp256k1.o):c:/mingw32/i686-w64-mingw32/include/gmp.h:2129: more undefined references to__gmpn_add_n' follow
C:/deps/secp256k1/.libs\libsecp256k1.a(libsecp256k1_la-secp256k1.o): In function secp256k1_fe_mul_int': c:\deps\secp256k1/src/field_gmp_impl.h:116: undefined reference to__gmpn_mul_1'
C:/deps/secp256k1/.libs\libsecp256k1.a(libsecp256k1_la-secp256k1.o): In function _gmpn_add': c:/mingw32/i686-w64-mingw32/include/gmp.h:2129: undefined reference to__gmpn_add_n'
c:/mingw32/i686-w64-mingw32/include/gmp.h:2129: undefined reference to __gmpn_add_n' c:/mingw32/i686-w64-mingw32/include/gmp.h:2129: undefined reference to__gmpn_add_n'
c:/mingw32/i686-w64-mingw32/include/gmp.h:2129: undefined reference to __gmpn_add_n' C:/deps/secp256k1/.libs\libsecp256k1.a(libsecp256k1_la-secp256k1.o): In functionsecp256k1_num_split':
c:\deps\secp256k1/src/num_gmp_impl.h:350: undefined reference to __gmpn_copyi' C:/deps/secp256k1/.libs\libsecp256k1.a(libsecp256k1_la-secp256k1.o): In function_gmpn_add':
c:/mingw32/i686-w64-mingw32/include/gmp.h:2129: undefined reference to __gmpn_add_n' c:/mingw32/i686-w64-mingw32/include/gmp.h:2129: undefined reference to__gmpn_add_n'
c:/mingw32/i686-w64-mingw32/include/gmp.h:2129: undefined reference to __gmpn_add_n' C:/deps/secp256k1/.libs\libsecp256k1.a(libsecp256k1_la-secp256k1.o): In function_gmpn_sub':
c:/mingw32/i686-w64-mingw32/include/gmp.h:2168: undefined reference to `__gmpn_sub_n'

Hi,

I'm trying to write Rust (rust-lang.org) wrappers for this library. I'm not a cryptography expert and Rust is still under heavy development, so this might not be problem with a secp256k1 library itself, but when I'm giving random array as inputs like this (Rust syntax):

  #[test]                                                                                           
  fn sign_and_verify_fail() {                                                                       
      let s = Secp256k1::new();                                                                     

      let mut msg = Vec::from_elem(64, 0u8);                                                        
      let mut seckey = [0u8, ..32];                                                                 
      let mut nonce = [0u8, ..32];                                                                  
      rand::task_rng().fill_bytes(msg.as_mut_slice());                                              
      rand::task_rng().fill_bytes(nonce);                                                           
      rand::task_rng().fill_bytes(seckey);                                                          

      let pubkey = s.pubkey_create(seckey, false).unwrap();                                         
      let sig = s.sign(&msg, seckey, nonce).unwrap();                                               

      rand::task_rng().fill_bytes(msg.as_mut_slice());                                              
      assert_eq!(s.verify(msg, sig, pubkey), Ok(false));                                            
  } 

I'm getting assert abort:

secp256k1: src/num_gmp_impl.h:200: secp256k1_num_mul: Assertion `a->limbs + b->limbs <= 2*((256+(64 - 0)-1)/(64 - 0))+1' failed.

Generally, it seems the randomness of msg is triggering the problem. Are there some messages / private keys that are not valid? Is this assert ringing a bell what is possibly wrong?

The current strategy is optimized for large fast chips with huge cache. Especially signing would be useful on some embedded devices where multiple megabytes of pre-computation is not acceptable. Reasonably low memory can be accomplished just by lowering window usage, but we could also consider a separate compile-time low-footprint option.

Something of a long term hygiene issue. The internal functions have some implicit contracts (e.g. scaling) which are not yet completely documented. This may present hazards for third-party or future changes which could be avoided now by documenting more of them while they're fresh.

Having something pulltester-like would be nice for libsecp256k1, especially if it tried a build with multiple combinations of the various options (with/without endomorphism, with the 4 different field implementations, with the 2 different scalar implementations).

The library should provide clear documentation of the strong assumptions that the libraries security rest on. E.g.

• Secret keys are chosen uniformly at random and in an unpredictable way.
• Message hashes are the output of a cryptographic hash. (In particular, you can't be caused to sign 0 or verify the signature of 0 (which can be trivially forged))
• You correctly check the return values of the functions, and correctly supply their inputs
• The C compiler or computer has not undermined the operation of the software
• The authors and reviewers of the software made no errors which are not detected by the included tests
• You obtained a faithful copy of the software
• Your computers operation is not excessively observable or modifiable by an attacker.
• The discrete Log problem is hard for the secp256k1 algebraic group
• The ECDSA signature algorithm is as strong as the discrete log problem

etc.

https://github.com/bitcoin/secp256k1/blob/master/include/secp256k1.h#L113

int secp256k1_ecdsa_pubkey_tweak_add(unsigned char *pubkey, int pubkeylen, const unsigned char *tweak);

Looking at the source code for this function, it seems like tweak is a 32 byte number. Is this valid?

What is the way to add 2 points together then if this function doesn't work.

We're under-covered currently for tests that simulate crazy callers. The practise of asserting on statically wrong use limits the space of things that can / need to be tested here, but there is still some freedom.

This should be less "test" and more "mechanical verification that the interface we present to callers isn't unintentionally changed".

(As an example, libopus' test_opus_api, calls into the library about 116 million times. I'd say that libopus has an API surface area of about 50x larger that libsecp256k1)

@theuni it seems -O3 performs significantly better (at least on my system) compared to -O2. Is there a way to make that default?

secp256k1_ge_t prec[1024];
secp256k1_gej_t precj[1024]; /* Jacobian versions of prec. */

Microcontrollers have expensive SRAM and cheap Flash. These should be turned into precomputed tables, at least as an option.

I know this is not officially released yet but I have made a FreeBSD port skeleton that I would like to submit into the official ports tree since some other projects are starting to require it as a dependency..

https://github.com/tuaris/secp256k1-freebsd

Is there a specific commit I should reference or is the latest okay?
What would a proper version number be at this point?

It seems there used to be a make target to create a shared library for native use in Bitcoinj (make libjavasecp256k1.so) some time ago, but the latest repo seems to only create a static library. Is there a way to create a shared library that can be used for Java applications?

The tests are burring some of actual test inside an ordinary assert macro. The tests shouldn't silently get eliminated when the compile options change.

Things that we don't want get getting removed when compiled with NDEBUG should have a library specific assert function or the like.

It seems only bench is compiled with -DNDEBUG defined. The object used in the .a and .so file should be also be built with -DNDEBUG.

Ping @theuni?