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

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.

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.

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.

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.


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.

Here's a counter-point:

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?

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?

But they don't have to believe _me_, even if they can't review it themselves they can choose anyone else who has (or pay someone to, or learn...).

I'm not sure of the context for this comment, libsecp2561k is plain C.

You should have asked.  I was surprised people didn't. Though there are many reasons around the level of publicly visible review and software testing,  there is more elaboration available now that I couldn't include in the release notes when I wrote them: https://www.reddit.com/r/Bitcoin/comments/2rrxq7/on_why_010s_release_notes_say_we_have_reason_to/

Libsecp256k1 isn't done yet. It won't be used for consensus relevant behavior in Bitcoin core until it's more mature and reviewed. Andytoshi gave a good explanation for the why we can be reasonably comfortable with signing-- that it's verified with a separate implementation at runtime (and has been cross verified against other implementations), and the scope for attacks in signing are narrow and auditable through conventional means, though more review is always useful.

If you were going to attack cryptosystems used in Bitcoin, OpenSSL would arguably make a much better target due to its complexity, opacity, and people's habit of blindly updating it due to its frequent security issues: see also the recent issues with OpenSSL's latest update breaking Bitcoin nodes.

99,9% of the people already have to believe every other piece of code of bitcoin because they (me too) lack the skills to review it themselves.
This, in my opinion, is one of the biggest hurdles for bitcoin technology to overcome.

C++ is hard to read, much harder than C, but not impossible.

I lack the technical knowledge to give you an answer to all your other questions, but this sentence caught my attention.
I just would like to say this:

99,9% of the people already have to believe every other piece of code of bitcoin because they (me too) lack the skills to review it themselves.
This, in my opinion, is one of the biggest hurdles for bitcoin technology to overcome.

99.9% of people adopting the new version are not going to know what is in that new library or how it operates.

However, libsecp256k1 takes its nonce as input to its API, and from that point on signing and verification are deterministic functions. Any nonce skew would need to occur in the Bitcoin code which calls into libsecp256k1; however, since November nonce generation has been deterministic as well (using RFC6979). This code has been audited and replicated by myself and others; it is also unit tested.

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

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

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

Hi colinistheman,


This is a good question. I should start off by mentioning that Pieter Wuille, the author of libsecp256k1, has been involved with Bitcoin Core since 2010 and by this point has written something like half of its current code. So if he is compromised, we have much bigger problems . Also, libsecp256k1 currently only used for signing, not verification, and in this case its signatures are always verified against another implementation --- so at least today it is not a great attack vector. More eyes are always better, so if you are concerned about it I encourage you to peruse the code now, before it is used more heavily.

All that said, I don't think there is any cause for concern.

I've been following libsecp256k1 since last September, shortly after its conception, when its main purpose was experimenting with speed improvements over OpenSSL. I've never contributed code, but I've read almost all of it at some point. I've also written the Rust bindings, which have many unit tests that I wrote entirely independently of the original codebase. (I'm not a random passerby by the way; I've been programming for nearly 20 years, in progress on a Ph.D. in cryptography, been involved with Bitcoin since 2011, and have been thinking about digital signatures specifically for over a year.) I've also done thorough audits on some heavily-algebraic parts of the libsecp256k1 codebase. (The Bitcoin developers have requested I do this a couple of times specifically because of my mathematical expertise; however, I can say that there isn't much knowledge required, you just need to not be allergic to symbols ).

I am more confident that libsecp256k1 is free of backdoors (deliberate or accidentally via the intrinsic fragility of ECDSA) than I am about OpenSSL's implementation of ECDSA. The reasons are pretty general: libsecp256k1's code is simpler and cleaner; it is designed specifically for ECDSA, so it is a much much smaller codebase (less room for error and reviewers can look more closely at the specific ECDSA code); its test coverage is more thorough. The code is also written in a modular way with the explicit goal of being easy to analyze. Some parts are even written with algebraic invariants commented on every line, providing a mathematical proof of correct operation. (The proof can be checked by starting on any line and checking the invariants in both directions until you hit the ends of the function.)

Technically there is also very little room for backdooring. By far the most straightforward way to backdoor an ECDSA implementation is to affect the random nonce generation. However, libsecp256k1 takes its nonce as input to its API, and from that point on signing and verification are deterministic functions. Any nonce skew would need to occur in the Bitcoin code which calls into libsecp256k1; however, since November nonce generation has been deterministic as well (using RFC6979). This code has been audited and replicated by myself and others; it is also unit tested. So I don't believe there are any nonce-skew attacks here.

Alternate means of backdooring might be to add explicit branches (which would be very visible to auditors), clever algebraic tricks (also noticeable by auditors, given how simple the correct algebra is), exploitation of behaviour outside the C spec such as use of uninitialized memory (which would appear in tools such as valgrind). I also don't believe there are any of these for the reasons just given. A final category of backdoor might be the use of sidechannels. Explicit sidechannel usage such as saving things to disk would be immediately visible in the code, while avoiding implicit sidechannels such as CPU timing or power usage is a deliberate goal of libsecp256k1 and something we check for in audits. Further, these sidechannels are measurable by definition, and these sorts of measurements are something that the developers are very interested in.

Andrew

Also with encryption one of the things that we've seen is: given this sort of dark age mentality that you've mentioned, there really are two risks:

One is that the algorithm itself could be weak-- A weakness that we are not currently aware of.

Also the implementation could be bad. When we get new crypto tools it normally takes a number of years before we know they're robust; Before we know they're reliable. They have to be reviewed by a number of people. They have to be broken a number of times and they have to be fixed. And eventually they reach a level where they're sort of defensible.