Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?

[Jace]

Besides the particular lib that Bitcoin is using to implement its ECDSA, in hindsight would it have been better (in terms of vulnerability resistance) to choose a different curve than secp256k1?

According to this comparison: http://safecurves.cr.yp.to/ there are curves with either smaller, similar and larger key sizes, with 100% non-rigged constants (e.g. Curve1174, Curve25519, E-222, E-382, E-521, M-221, M-383, M-511) that pass certain safety criteria that secp256k1 doesn't. I understand these are no direct threat to the way secp256k1 is used in Bitcoin, but still.

Or was it purely Satoshi's consideration of ECDSA efficiency (algorithm speed) to choose secp256k1?

[fluffypony]

Besides the particular lib that Bitcoin is using to implement its ECDSA, in hindsight would it have been better (in terms of vulnerability resistance) to choose a different curve than secp256k1?

According to this comparison: http://safecurves.cr.yp.to/ there are curves with either smaller, similar and larger key sizes, with 100% non-rigged constants (e.g. Curve1174, Curve25519, E-222, E-382, E-521, M-221, M-383, M-511) that pass certain safety criteria that secp256k1 doesn't. I understand these are no direct threat to the way secp256k1 is used in Bitcoin, but still.

Or was it purely Satoshi's consideration of ECDSA efficiency (algorithm speed) to choose secp256k1?

Here's a counter-point: http://infosecurity.ch/20100926/not-every-elliptic-curve-is-the-same-trough-on-ecc-security/

According to that the only safe curves are NIST P-256 and NIST P-384. SafeCurves says those two are unsafe.

Who's right?

[gmaxwell]

Here's a counter-point:

The author of that page seems to not understand that characteristic-2 curves and GLV-capable prime curves are entirely different things; its not helpful that both get named after Koblitz. Their argument seems mostly to reduce to, by effect, "use things only from heavily NSA influenced standards bodies"-- I assume you can understand why some people may not find that very persuasive.

According to this comparison: http://safecurves.cr.yp.to/ there are curves with either smaller, similar and larger key sizes, with 100% non-rigged constants (e.g. Curve1174, Curve25519, E-222, E-382, E-521, M-221, M-383, M-511) that pass certain safety criteria that secp256k1 doesn't. I understand these are no direct threat to the way secp256k1 is used in Bitcoin, but still.

Or was it purely Satoshi's consideration of ECDSA efficiency (algorithm speed) to choose secp256k1?

None of these were available in signature systems when Bitcoin was created, many of these didn't exist at all, the few that did weren't mature or widely used.  Some of safety criteria listed there are not terribly interesting, as has been discussed several times on the forum; e.g. some  relate to how simple the fastest constant time arithmetic is to write (but thats somewhat moot once its already written), or details which change security by a bit or two (but then it ignores the curve simply being smaller and thus losing several bits). The curves that pass the criteria there fail a different criteria for "safety of implementation" which has arguably been of more practical importance... that the curves have a cofactor (which both lowers their discrete log security and makes broken protocols more likely).  To be clear they're also generally good choices, but the page leans a little bit to much towards marketing, IMO.  Insanely slow brainpool curves, or NIST curves with mystery meet suspicious seeding remain worse options no matter which way you cut it, at least for our purposes.

At the time Bitcoin was created secp256k1 was the only curve in widely available software that didn't have magic constants. With a good specialized implementation it's still one of the fastest curves available at anywhere near its security level, and more secure than many other curves in the same size range given what the best known information about discrete log security. I can only imagine that it didn't see wider adoption because specialized high speed software for it wasn't available, and because one of the more interesting performance techniques for speeding it up is potentially patented.

[colinistheman]

Hi colinistheman,

it's very good that people have concerns about the security of code, or the process used to assure it. I hope your concerns have been addressed by now.

Your post made me realize one thing though: you probably haven't seen gmaxwell's reddit post (http://www.reddit.com/r/Bitcoin/comments/2rrxq7/on_why_010s_release_notes_say_we_have_reason_to/). This explains the reason for the at the time somewhat cryptic "we have reason to believe it is better tested". I encourage you to read the details there, but in short: we found a very tricky (but most likely harmless) bug in OpenSSL itself while writing this library - because the tests did comparisons with OpenSSL and failed once. It's by no means a proof that libsecp256k1 is bug free (more review is always welcome), but it does show that its testing practices pay off.

We should probably change the language in the release notes, now that the OpenSSL bug it was referring to has been disclosed.

I've been looking at the code, and theres quite a few magic numbers in there

Most of the constants are taken directly from the secp256k1 standard, or computed using algorithms explained in code. But more comments to explain where they come from would not be a bad idea. We'll add some.

Thank you for the answer, Peter.

My concerns have been addressed, but I am glad it got some people thinking on this thread. I feel like as long as we are alert to such things then they won't happen.

I will read gmaxwell's reddit post that you suggested as well. Thanks for that. Yes, you are correct, I had no idea what actual testing went into being able to make the statement "we have reason to believe it is better tested".

It is a good thing that we are not using OpenSSL if it contains a bug. Just wanted to be sure that the thing we're replacing it with does not contain different or worse bugs

Thanks again.


Edit: I finished reading that reddit post from nullc. It was a good read, and while it answered the question of his reasoning for why he wrote "we have reason to believe it [libsecp256k1] is better tested", it raised another question in me:

nullc said "This error in OpenSSL could result in a number of cryptographic operations (for many different kinds of cryptosystems) yielding wrong results but due to good fortune the issue is not a concern for Bitcoin implementations."

If the squaring bug referenced is not a concern for Bitcoin implementations, then why was a new library required? It sounds like the bug affects things other than bitcoin, but bitcoin is safe from it.

[gmaxwell]

If the squaring bug referenced is not a concern for Bitcoin implementations, then why was a new library required? It sounds like the bug affects things other than bitcoin, but bitcoin is safe from it.

Independent of any particular bugs, OpenSSL is maintained in a way which is unsafe for consensus ( http://sourceforge.net/p/bitcoin/mailman/message/33221963/ ). OpenSSL is also on the order of >>300k lines of messy, difficult to review code (even for someone who is familiar with the algorithms in use), which-- for Bitcoin's narrow use-- can be replaced with <10k lines and get a 6-8x speed-up at the same time (and 21% of that 10k is testing code; compared to 0.9% in OpenSSL-- another reason for the reason to believe, coupled with the basically 100% branch coverage of the libsecp256k1 tests).  OpenSSL also has huge timing/cache side-channel leaks (http://eprint.iacr.org/2014/161.pdf), and can't be used with best-practices derandomized DSA without moving part the low level cryptographic code into your own application. The point about the BN squaring bug wasn't that that particular issue was a problem for Bitcoin (though it narrowly dodged being a trivial attack to fork the network), but that the tests for libsecp256k1 found it without even trying to test OpenSSL is some level of evidence that the library may be practically better tested already.

[colinistheman]

If the squaring bug referenced is not a concern for Bitcoin implementations, then why was a new library required? It sounds like the bug affects things other than bitcoin, but bitcoin is safe from it.

Independent of any particular bugs, OpenSSL is maintained in a way which is unsafe for consensus ( http://sourceforge.net/p/bitcoin/mailman/message/33221963/ ). OpenSSL is also on the order of >>300k lines of messy, difficult to review code (even for someone who is familiar with the algorithms in use), which-- for Bitcoin's narrow use-- can be replaced with <10k lines and get a 6-8x speed-up at the same time (and 21% of that 10k is testing code; compared to 0.9% in OpenSSL-- another reason for the reason to believe, coupled with the basically 100% branch coverage of the libsecp256k1 tests).  OpenSSL also has huge timing/cache side-channel leaks (http://eprint.iacr.org/2014/161.pdf), and can't be used with best-practices derandomized DSA without moving part the low level cryptographic code into your own application. The point about the BN squaring bug wasn't that that particular issue was a problem for Bitcoin (though it narrowly dodged being a trivial attack to fork the network), but that the tests for libsecp256k1 found it without even trying to test OpenSSL is some level of evidence that the library may be practically better tested already.

I see. I agree it's better to avoid depending on outside libraries because those could be compromised in the future too. If everything is done "in-house" then it's safer and simpler to review (in this case). I feel pretty much like it was the right decision. It's just a matter of testing and really making sure it's got no mathematical bugs like OpenSSL's had, which Snowden said could take years to fully verify for any new crypto tools.

Thanks for the explanations. I can see lots of thought went into it.

[andytoshi]

It's just a matter of testing and really making sure it's got no mathematical bugs like OpenSSL's had, which Snowden said could take years to fully verify for any new crypto tools.

To add to earlier comments, it's much easier to audit libsecp256k1 code than it is to audit OpenSSL code. We've seen from experience that OpenSSL is not audited nearly as well as it should; from personal experience, I think this is because so much of the code is behind so many layers of macro obfuscation and bizarre architecture that it discourages anyone who tries. So libsecp256k1 being cleaner not only means audits are more likely to uncover any funny business; it also increases the number of people willing to look at the code.

[gmaxwell]

To be fair, OpenSSL has a much wider goal. It's an apples and oranges comparison in that sense; but we don't need those extra parts.

[brituspol]

Working with  libsecp256k1 is better than with openssl when we consider continuous and consisting bitcoin development in the long run.

[colinistheman]

Working with  libsecp256k1 is better than with openssl when we consider continuous and consisting bitcoin development in the long run.

To be fair, OpenSSL has a much wider goal. It's an apples and oranges comparison in that sense; but we don't need those extra parts.

To add to earlier comments, it's much easier to audit libsecp256k1 code than it is to audit OpenSSL code. We've seen from experience that OpenSSL is not audited nearly as well as it should; from personal experience, I think this is because so much of the code is behind so many layers of macro obfuscation and bizarre architecture that it discourages anyone who tries. So libsecp256k1 being cleaner not only means audits are more likely to uncover any funny business; it also increases the number of people willing to look at the code.

All good points and I can see why this would be important for Bitcoin in the long-term. Makes sense!

[doof]

I've been looking at the code, and theres quite a few magic numbers in there

Can you clarify this? If you mean "32" that is the byte size of the field elements used for all of the arithmetic. If you mean the 32-bit hex numbers, those are parameters of the curve as defined by NIST. If you mean "0", "-1", "-2" error return values, I'd guess that a PR to #define better names for these would be welcome.

Edit: I've been reminded that the secp256k1 curve is actually defined by SECG, not NIST. My bad.

The curve constants I'm fine with.  There seems to be a few loops with arbitrary upper limits

Code:

void print_number(double x) {
    double y = x;
    int c = 0;
    if (y < 0.0) y = -y;
    while (y < 100.0) {
        y *= 10.0;
        c++;
    }
    printf("%.*f", c, x);
}
[code]
Why 100?

[code]
int secp256k1_ecdsa_verify(const unsigned char *msg32, const unsigned char *sig, int siglen, const unsigned char *pubkey, int pubkeylen) {
    secp256k1_ge_t q;
    secp256k1_ecdsa_sig_t s;
    secp256k1_scalar_t m;
    int ret = -3;
    DEBUG_CHECK(secp256k1_ecmult_consts != NULL);
    DEBUG_CHECK(msg32 != NULL);
    DEBUG_CHECK(sig != NULL);
    DEBUG_CHECK(pubkey != NULL);

    secp256k1_scalar_set_b32(&m, msg32, NULL);

    if (!secp256k1_eckey_pubkey_parse(&q, pubkey, pubkeylen)) {
        ret = -1;
        goto end;
    }
    if (!secp256k1_ecdsa_sig_parse(&s, sig, siglen)) {
        ret = -2;
        goto end;
    }
    if (!secp256k1_ecdsa_sig_verify(&s, &q, &m)) {
        ret = 0;
        goto end;
    }
    ret = 1;
end:
    return ret;
}

I guess we are just setting returns to negatives to represent errors?

Code:

void bench_scalar_sqr(void* arg) {
    int i;
    bench_inv_t *data = (bench_inv_t*)arg;

    for (i = 0; i < 200000; i++) {
        secp256k1_scalar_sqr(&data->scalar_x, &data->scalar_x);
    }
}

Why 200,000?

Sorry, just trying to understand the code better.[/code][/code]

[Pieter Wuille]

Code:

void print_number(double x) {
    double y = x;
    int c = 0;
    if (y < 0.0) y = -y;
    while (y < 100.0) {
        y *= 10.0;
        c++;
    }
    printf("%.*f", c, x);
}

Why 100?

I guess some comments here would help. It's just guaranteeing a print of 3 significant digits, so it counts how many places to shift the comma by to bring the number between 100 and 999.....

[gmaxwell]

I guess we are just setting returns to negatives to represent errors?

This is clearly documented in the interface for the function:

Code:

 *  Returns: 1: correct signature
 *           0: incorrect signature
 *          -1: invalid public key
 *          -2: invalid signature

Code:

void bench_scalar_sqr(void* arg) {
    int i;
    bench_inv_t *data = (bench_inv_t*)arg;

    for (i = 0; i < 200000; i++) {
        secp256k1_scalar_sqr(&data->scalar_x, &data->scalar_x);
    }
}

Why 200,000?
Sorry, just trying to understand the code better.

It's a benchmark. Not part of the library itself. As typical for benchmarks, it runs enough times to make the measurements have reasonable resolution.

[SteamGamesBTC.com]

This is all public.  The code is public, the comments are public.

OpenSSL is also public and we didn't avoid the Heartbleed Bug. So the OP question is valid.

[kjj]

This is all public.  The code is public, the comments are public.

OpenSSL is also public and we didn't avoid the Heartbleed Bug. So the OP question is valid.

To be valid, a question must be answerable.  This one is not.

But the process is about as good as anyone on the planet knows how to make it.  If you have patches, for either the code or the process, we'd all be glad to hear from you.

[Cryddit]

If the squaring bug referenced is not a concern for Bitcoin implementations, then why was a new library required? It sounds like the bug affects things other than bitcoin, but bitcoin is safe from it.

The squaring bug isn't a concern for Bitcoin.  We're moving away from OpenSSL for a different reason.  The purpose for which OpenSSL is implemented and maintained is not precisely the purpose for which Bitcoin was using it, and for their purposes they are free to "fix" things in a way that would result in a failure for Bitcoin. 

Before this change, we were using OpenSSL to check the validity of the crypto in encrypted blocks already in the blockchain - blocks that had been transmitted and accepted months or even years previously.  OpenSSL's purpose is in securing communications today, this hour, this minute. 

When encrypted data can appear in any of multiple possible formats, it can lead to different signatures for the "same" data.  This is a problem which could lead to some protocols leaking information, transmitting things redundantly, or letting an attacker see the same payload encrypted by closely-related keys, etc. 

OpenSSL responded to a perceived possible vulnerability that allowed things to appear in either of multiple formats  by first issuing a version of OpenSSL that would only produce a single format, then followed it up 2 months or so later with a version of OpenSSL that would reject all other formats as incorrect.  This is completely in accord with their purpose, and makes a bunch of protocols more secure.  But it didn't work for the Bitcoin protocol.

We have blocks in our blockchain, that have already been accepted, which used one or more of those other formats.  This caused Bitcoin clients which were dynamically linking against the OpenSSL library (ie, which used the latest version of OpenSSL installed on the machine) to decide that we had invalid blocks in our blockchain. 

Most people weren't affected because the downloadable executable was statically linked with an earlier OpenSSL (ie, they used a version of OpenSSL that was guaranteed not to change, but which therefore also wasn't getting updates and bugfixes) so it wasn't affected by the change.  People like me, who compiled from source and linked OpenSSL dynamically rather than statically, had to upgrade our Bitcoin clients before we upgraded our OpenSSL. 

Having had our noses rubbed in the mismatch between OpenSSL's purpose and our requirements, we realized that we needed to put crypto whose purpose is *EXACTLY* our requirements into our client rather than continuing to rely on OpenSSL for things it never promised to do.

[bcearl]

You are implying that OpenSSL is not a complete pile of shit. But it is. The new libsecp256k1 can't be worse than OpenSSL.

It can't possibly be
- documented worse
- less readable by humans
- harder to comprehend by humans
than OpenSSL.

Heartbleed was no surprise to anybody who ever worked with OpenSSL. Nobody can understand OpenSSL. It is bloated with features that have no use, which make it hard to even track the code path of a single thing that you want to analyze. And you cannot even use debugging tools on OpenSSL (because they implement their own memory management instead of malloc() etc. etc.).

[CIYAM]

Before this change, we were using OpenSSL to check the validity of the crypto in encrypted blocks already in the blockchain - blocks that had been transmitted and accepted months or even years previously.  OpenSSL's purpose is in securing communications today, this hour, this minute.  

As Bitcoin doesn't encrypt blocks this statement seems to be rather odd - care to explain (or did you just mean to say ECDSA sigs already stored in the blockchain)?

[rfcdejong]

At least v0.10 didn't cause a bitcoin fork as Peter Todd said it could 

http://www.reddit.com/r/Bitcoin/comments/2pd0zy/peter_todd_is_saying_shoddy_development_on_v010/

[Cryddit]

Before this change, we were using OpenSSL to check the validity of the crypto in encrypted blocks already in the blockchain - blocks that had been transmitted and accepted months or even years previously.  OpenSSL's purpose is in securing communications today, this hour, this minute.  

As Bitcoin doesn't encrypt blocks this statement seems to be rather odd - care to explain (or did you just mean to say ECDSA sigs already stored in the blockchain)?

Yes, I was talking about the sigs.  OpenSSL moved to a strict form requirement, which some of the signatures already recorded in blocks did not comply with.