Pages:
Author

Topic: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors? (Read 8352 times)

staff
Activity: 4284
Merit: 8808
It really is upsetting how many THINGS bitcoin building depends on.
Take a breath. Okay. Now, lets walk through this.

Quote
How many things a version change in some code not controlled by it can screw up or introduce vulnerabilities in.
Fairly few, in fact-- if you use the gitian build system there is no uncontrolled upgrade of any dependency in the system. You will build a bit identical binary to all other users, and all updates to dependence can be audited and tested before being deployed.

Quote
I know all the cool kids are using boost, but did a crypto project really need the vulnerability to version rot?
Boost has only ever been used in a fairly limited capacity in bitcoin, mostly importing C++ features from the future, some of which are very useful to writing safe reviewable code. (the one big exception to that is the use of boost-asio). C++11 and better have incorporated many of the features, and Bitcoin Core has been phasing out most boost usage; though a preference to retaining compatibility with older operating systems is delaying the move completely. That said, we've had fairly few issues with boost version incompatibility (presumably because so little of it is used).

Quote
I know all the cool kids are using OpenSSL but did we really have to wait until a version upgrade broke our consensus before we implemented a consensus library to get past it?
Work on libsecp256k1 began something like a year ago, along with work to isolate  the consensus behavior from openssl (as part of BIP62).  In spite of your considerable knowledge of cryptography and systems programming you have not made, as far as I can tell, a single contribution to these efforts. The fact of the matter is that only a few users care, even most of the people who regularly contribute to Bitcoin Core have not contributed to these efforts. And the work must be done very carefully. The update broke consensus was detected within hours of the openssl release through code review (not user reports), and did not effect bitcoin.org binaries or other binaries built with the gitian build system, because it captures and fixes the environments.  Which certainly made it easier to move forward with a subset of BIP62, since it validated the things that those of us who care about these things have been saying for some time and got more people willing to step up and do some review.

Quote
I know all the cool kids are using autodeps, automake, autoconf, etc, but those still change often enough to distrust them for a crypto project.
Your complaint there seems surprising. When a distribution tarfile is created all the autofoo stuff is fixed as shell scripts and doesn't even need to be installed on the host.  The pre-autotools enviroment for Bitcoin was a catastrophe. Keep in mind that Bitcoin is not some UIless library, it's a fairly complex end user application with graphical support and several optional components.  Though even without that, the autofoo stuff makes cross compilation work well-- which is important for being able to do things like the gitian build system providing binaries for three platforms from a single host.

(And pretty much no build system is going to save you from something getting screwed up here or there and needing to "make clean" to put everything right)

Quote
And then there's C++.  A language in which arbitrary and unexpected behavior can be lurking behind every overloaded operator, implicitly called constructor/destructor on procedure entry/exit, etc.
Yes, C++'s opacity is annoying, but what can you say?  Bitcoin Core never had a single remote code execution bug, in a complex codebase with a lot of moving parts. Had it all been written in C it is much less likely to have been as correct as it was, it would have been harder to understand at a high level (even if the fine details were more clear); and I say this as someone who profoundly dislikes C++.  C++'s mostly only awful when code is inflicted on you by others, it offers many sins, but they're answerable by "well, don't do that."

Quote
And the STL, which leaks copies of information in deallocated memory all over the place if you're not extremely careful.  Still, you've got explicit memory management so you CAN avoid leaking copies of information in deallocated memory if you are very careful, and that's more than I can say for most "modern" or "more convenient" languages.
Careful here, your "plain C" also spews data all over the place. Go look at your stack. The compiler optimizes out most efforts to clean it up, and randomly spills things into place you never though they'd be. You can achieve the same control over leaking data in C++ as exists in C (as in: not perfect), all the STL objects can use custom allocators that zeroize. This is used in Bitcoin Core.

Quote
And the STUPID depending for a binary format on a database that changes its binary format with EVERY new release, which has forced us to maintain our own archived copy of an obsolete database that has had security bugs fixed SINCE we did!  The only reason our wallets aren't vulnerable is because we used them to store encrypted data in the first place.
Yes, BDB is lame. Though its only new major releases which break the format. Old releases have still received fixes (especially important since the latest releases have changed software licenses).  It's not a security concern not because of encrypted data but because it's a local database for the wallet, it's not exposed to the outside world. Several abortive attempts have been made to replace it, it's a big project. (not in terms of lines of code, but in terms of cost of mistakes.)

Quote
As an old cryptogeek this is a nerve-wracking codebase.  Don't get me wrong, the code is good - but doing all this, and trying to stay secure given the limitations and version changes of all these tools, is like dancing on a tightrope over a fire.  I vastly prefer C, where every operation is visible and every operator does exactly one thing.  In C it's easy to know when things AREN'T happening.
I generally prefer C too. But I would have a hard time arguing for it for the vast majority of Bitcoin Core's code. The automatic safety possible in modern C++ has served it very well.  There are some parts, like the nitty gritty cryptographic consensus parts which already need to be so simplified, so analyzed, so straightforward in their operation, and are so important to expose to strong analysis tools (that don't generally work on C++ owing to its awful undecidable grammar) that the balance likely tilts back the other way, but we'll see how that plays out as those parts are factored out of the main codebase.

legendary
Activity: 924
Merit: 1132
It really is upsetting how many THINGS bitcoin building depends on.

How many things a version change in some code not controlled by it can screw up or introduce vulnerabilities in.

I know all the cool kids are using boost, but did a crypto project really need the vulnerability to version rot?  I know all the cool kids are using OpenSSL but did we really have to wait until a version upgrade broke our consensus before we implemented a consensus library to get past it?  I know all the cool kids are using autodeps, automake, autoconf, etc, but those still change often enough to distrust them for a crypto project.  

And then there's C++.  A language in which arbitrary and unexpected behavior can be lurking behind every overloaded operator, implicitly called constructor/destructor on procedure entry/exit, etc.  

And the STL, which leaks copies of information in deallocated memory all over the place if you're not extremely careful.  Still, you've got explicit memory management so you CAN avoid leaking copies of information in deallocated memory if you are very careful, and that's more than I can say for most "modern" or "more convenient" languages.  

And the STUPID depending for a binary format on a database that changes its binary format with EVERY new release, which has forced us to maintain our own archived copy of an obsolete database that has had security bugs fixed SINCE we did!  The only reason our wallets aren't vulnerable is because we used them to store encrypted data in the first place. 

As an old cryptogeek this is a nerve-wracking codebase.  Don't get me wrong, the code is good - but doing all this, and trying to stay secure given the limitations and version changes of all these tools, is like dancing on a tightrope over a fire.  I vastly prefer C, where every operation is visible and every operator does exactly one thing.  In C it's easy to know when things AREN'T happening.

legendary
Activity: 924
Merit: 1132
D'oh! 

I figured it out.  I had a version mismatch in my automake and needed to regenerate aclocal.m4 before configuring so it would correctly create test_driver. 
zvs
legendary
Activity: 1680
Merit: 1000
https://web.archive.org/web/*/nogleg.com
Code:
make[1]: Entering directory `/home/bleat/install/bitcoin/src'
make  check-TESTS check-local
make[2]: Entering directory `/home/bleat/install/bitcoin/src'
make[3]: Entering directory `/home/bleat/install/bitcoin/src'
PASS: test/test_bitcoin
make[4]: Entering directory `/home/bleat/install/bitcoin/src'
make[5]: Entering directory `/home/bleat/install/bitcoin/src'
make[5]: Leaving directory `/home/bleat/install/bitcoin/src'
make[4]: Leaving directory `/home/bleat/install/bitcoin/src'
============================================================================
Testsuite summary for Bitcoin Core 0.10.99
============================================================================
# TOTAL: 1
# PASS:  1
# SKIP:  0
# XFAIL: 0
# FAIL:  0
# XPASS: 0
# ERROR: 0
============================================================================
make[3]: Leaving directory `/home/bleat/install/bitcoin/src'
Running test/bitcoin-util-test.py...
make[3]: Entering directory `/home/bleat/install/bitcoin/src/secp256k1'
  CC       src/tests-tests.o
  CCLD     tests
make  check-TESTS
make[4]: Entering directory `/home/bleat/install/bitcoin/src/secp256k1'
make[5]: Entering directory `/home/bleat/install/bitcoin/src/secp256k1'
PASS: tests
make[6]: Entering directory `/home/bleat/install/bitcoin/src/secp256k1'
make[6]: Leaving directory `/home/bleat/install/bitcoin/src/secp256k1'
============================================================================
Testsuite summary for libsecp256k1 0.1
============================================================================
# TOTAL: 1
# PASS:  1
# SKIP:  0
# XFAIL: 0
# FAIL:  0
# XPASS: 0
# ERROR: 0
============================================================================
make[5]: Leaving directory `/home/bleat/install/bitcoin/src/secp256k1'
make[4]: Leaving directory `/home/bleat/install/bitcoin/src/secp256k1'
make[3]: Leaving directory `/home/bleat/install/bitcoin/src/secp256k1'
make[2]: Leaving directory `/home/bleat/install/bitcoin/src'
make[1]: Leaving directory `/home/bleat/install/bitcoin/src'

# ./test_bitcoin --t crypto.tests
Running 133 test cases...

*** No errors detected

did I miss something?

456 test cases?  3 tests?

this?

Code:
# ~/install/bitcoin/src/secp256k1/tests
test count = 64
random seed = 12071984385075897441
random run = 1544165739024864173

dont see anything else
legendary
Activity: 924
Merit: 1132
I just ran 'make check' on a freshly-built bitcoin 0.10.0 and got 2 tests passed out of 3, with 456 failed test cases. 

All of them are from src/test/crypto_tests.cpp and state "error in sha256_testvectors": check hash == out failed."

Please tell me this is because I've got something configured wrong.....   Huh
legendary
Activity: 924
Merit: 1132


C++ is hard to read, much harder than C, but not impossible.
I'm not sure of the context for this comment, libsecp2561k is plain C.
[/quote]

No , that's a real effect of using c++. I appreciate that secp is in C. 

C++ allows a lot of hidden actions and allows them to be redefined via overloading. It's very hard to be sure that nothing unintended is happening when using C++. The fact that the Bitcoin software is written in it is at best unfortunate for hardcore security reviews but it's hard to put up a good GUI app with anything better for security.
hero member
Activity: 907
Merit: 1003
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.


Hi Peter, I just saw you speak about the new lipsecp256k1 library here in this video. Thanks.

link for anyone else who wishes to hear him speak on this subject.

legendary
Activity: 924
Merit: 1132
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.

hero member
Activity: 798
Merit: 500
legendary
Activity: 1890
Merit: 1086
Ian Knowles - CIYAM Lead Developer
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)?
full member
Activity: 168
Merit: 103
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.).
legendary
Activity: 924
Merit: 1132
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.



kjj
legendary
Activity: 1302
Merit: 1026
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.
hero member
Activity: 734
Merit: 507
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.
staff
Activity: 4284
Merit: 8808
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

Quote
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.
legendary
Activity: 1072
Merit: 1181
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.....
hero member
Activity: 765
Merit: 503
I've been looking at the code, and theres quite a few magic numbers in there Sad

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]
hero member
Activity: 907
Merit: 1003
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!
sr. member
Activity: 458
Merit: 250
From nothing to nothing
Working with  libsecp256k1 is better than with openssl when we consider continuous and consisting bitcoin development in the long run.
staff
Activity: 4284
Merit: 8808
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.
Pages:
Jump to: