Bitcoin Forum

Bitcoin => Development & Technical Discussion => Topic started by: colinistheman on January 26, 2015, 10:01:13 PM



Title: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: colinistheman on January 26, 2015, 10:01:13 PM
Note: Pardon me if I have any of the wording or concepts of this post incorrect.


With the recent release of the beta version of Bitcoin Core v0.10, a new library was introduced, libsecp256k1.

In the release notes it says, "we have reason to believe that libsecp256k1 is better tested and more thoroughly reviewed than the implementation in OpenSSL"

The introduction of a new library with functions as important as this could be manipulated to have mathematically introduced back-doors which would enable backward engineering of keys or other manipulations (perhaps seeming to be random when in fact having patterns to the numbers which could be used by NSA-type organizations to "infiltrate" bitcoin security). I am not saying this has happened, but just saying that this would be a sneaky and effective way to implant backdoors into bitcoin.

If I was an enemy organization (NSA, PRISM, etc) and I wanted to infiltrate bitcoin, this is how I would do it. I would handsomely pay off some coder(s) to introduce a backdoor or predictable mathematical weakness and implement it into some obscure aspect of the code, such as the elliptic curve functions in libsecp256k1. Has this possibility been considered?

While I do not have the knowledge to verify the security of this new library, does anyone else have proof that it is secure? What assurance do we have that it is as secure or more secure than the library it replaced? 99.9% of people adopting the new version are not going to know what is in that new library or how it operates.

I just wanted to voice this concern because it had been on my mind.

----------------------------------------------------

To illustrate the point further, here are two quotes from a recent Edward Snowden interview (conducted around Jan 23rd, 2015):

Edward Snowden talking about cryptography and how it takes a few years to fully vindicate that it's safe:

https://www.youtube.com/watch?x-yt-ts=1422327029&v=7Ui3tLbzIgQ&feature=player_embedded&x-yt-cl=84838260#t=713 (https://www.youtube.com/watch?x-yt-ts=1422327029&v=7Ui3tLbzIgQ&feature=player_embedded&x-yt-cl=84838260#t=713)

time: 11:53-12:24

Quote
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.
-Edward Snowden, Jan 23 2015.


Also, a little bit later in the same video, Bruce Schneier talks about backdoor entered into linux code that almost got through.

(time: 13:31-15:53)

----------------------------------------------------

These are the same kind of concerns that entered my mind. My intent of this thread is twofold: 1.) to pass this knowledge on to raise community awareness (as bitcoin is open source), and 2.) To see if any individuals can come forth to provide information that the new library is safe. And how we can know that so quickly when Snowden himself says it can take years to fully prove it (as in the first quoted passage above).

I want it to be clear that there is no present threat to Bitcoin that I'm aware of. I am being preemptive.

My logic is that if we can all spot this kind of infiltration, then it will be less likely to happen in the future. And I want a safe Bitcoin for years to come.

----------------------------------------------------

Feb 19, 2015 UPDATE:

Bitcoin Developer Peter Wuille speaks about the new lipsecp256k1 library here in this video (http://youtu.be/asC_kVJ6sig?t=22m30s).


Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: kjj on January 27, 2015, 03:49:48 AM
This is all public.  The code is public, the comments are public.

A library like this is pretty specialized.  Not a whole lot of people are competent to review it, and I think that a good fraction of them already have.  If you have specific questions, gmaxwell could probably answer them.  General paranoia probably won't get you much attention though.


Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: colinistheman on January 27, 2015, 04:10:52 AM
Yes I'm aware it's public. Just wanted to know that it's been reviewed. It's not paranoia, just a legit question. Either the new library has or it hasn't been thoroughly reviewed.

The reason I feel that any mathematical vulnerabilities could get past a casual review is because the library uses different cryptographic functions which are highly mathematical. So it would require a very sharp individual to competently say it's 100% good.


Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: andytoshi on January 27, 2015, 02:07:22 PM
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 (https://github.com/apoelstra/bitcoin-secp256k1-rs), 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 (https://dl.acm.org/citation.cfm?id=746920)) 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


Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: unamis76 on January 27, 2015, 04:58:42 PM
I thought about what the OP is saying myself when I read the release notes on the 0.10 RC... But since the code is always public, I've discarded these thoughts :D

andytoshi, thank you for your insight, it's pretty clear even for non techies :)


Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: RodeoX on January 27, 2015, 05:02:37 PM
That's the right question Collin. Fortunately, because this is all open source you can get a definitive answer.


Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: gmaxwell on January 27, 2015, 06:32:46 PM
I thought about what the OP is saying myself when I read the release notes on the 0.10 RC... But since the code is always public, I've discarded these thoughts :D
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.



Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: colinistheman on January 28, 2015, 05:35:33 AM
Yes and just because libsecp256k1 is publicly visible doesn't mean that many public understand it or can see that it's incorrect, which is why I made this thread.

To illustrate the point further, here are two quotes from a recent Edward Snowden interview (conducted around Jan 23rd, 2015):

Edward Snowden talking about cryptography and how it takes a few years to fully vindicate that it's safe:

https://www.youtube.com/watch?x-yt-ts=1422327029&v=7Ui3tLbzIgQ&feature=player_embedded&x-yt-cl=84838260#t=713 (https://www.youtube.com/watch?x-yt-ts=1422327029&v=7Ui3tLbzIgQ&feature=player_embedded&x-yt-cl=84838260#t=713)

(time: 11:53-12:24)

Quote
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.
-Edward Snowden, Jan 23 2015.


Also, a little bit later in the same video, Bruce Schneier talks about backdoor entered into linux code that almost got through.

(time: 13:31-15:53)

----------------------------------------------------

These are the same kind of concerns that entered my mind. My intent of this thread is twofold: 1.) to pass this knowledge on to raise community awareness (as bitcoin is open source), and 2.) To see if any individuals can come forth to provide information that the new library is safe. And how we can know that so quickly when Snowden himself says it can take years to fully prove it (as in the first quoted passage above).

I want it to be clear that there is no present threat to Bitcoin that I'm aware of. I am being preemptive.

My logic is that if we can all spot this kind of infiltration, then it will be less likely to happen in the future. And I want a safe Bitcoin for years to come.


Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: colinistheman on January 28, 2015, 05:48:34 AM
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 (https://github.com/apoelstra/bitcoin-secp256k1-rs), 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 (https://dl.acm.org/citation.cfm?id=746920)) 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

Thank you for that very thorough and concise answer to my original question, Andrew. Your reply has provided the most comforting answer I've heard. I feel a bit more relaxed, especially with the parts I bolded in your statement above. Thanks again.


Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: doof on January 28, 2015, 05:57:30 AM
I've been looking at the code, and theres quite a few magic numbers  (http://en.wikipedia.org/wiki/Magic_number_%28programming%29#Unnamed_numerical_constants)in there :(


Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: colinistheman on January 28, 2015, 06:13:07 AM
I've been looking at the code, and theres quite a few magic numbers  (http://en.wikipedia.org/wiki/Magic_number_%28programming%29#Unnamed_numerical_constants)in there :(

Did you see andytoshi's post (https://bitcointalk.org/index.php?topic=937058.msg10278072#msg10278072)? After you've read it, does that make you feel any better, or no?


Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: andytoshi on January 28, 2015, 02:22:04 PM
I've been looking at the code, and theres quite a few magic numbers  (http://en.wikipedia.org/wiki/Magic_number_%28programming%29#Unnamed_numerical_constants)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.


Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: Pieter Wuille on January 29, 2015, 03:15:54 AM
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  (http://en.wikipedia.org/wiki/Magic_number_%28programming%29#Unnamed_numerical_constants)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.


Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: Pieter Wuille on January 29, 2015, 03:26:53 AM
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.

This is not technically true anymore. Since recently, there is a full RFC6979 implementation inside libsecp256k1, with test vectors that were generated by another implementation (feel free to review it; it's too recent to go in Bitcoin Core v0.10.0 still, though). The reason for this change was making sure that the easiest way for using the library is always safe - the old API allowed you to shoot yourself in the foot if you passed in a bad nonce.


Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: findftp on January 29, 2015, 10:58:24 AM
99.9% of people adopting the new version are not going to know what is in that new library or how it operates.

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.


Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: kjj on January 29, 2015, 01:03:53 PM
99.9% of people adopting the new version are not going to know what is in that new library or how it operates.

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.

C++ is hard to read, much harder1 than C, but not impossible.  I have a hell of a time with it myself, but I've walked people into the code so that they could personally verify some issues that they were concerned with.

Checking that the code does what it says is much easier than checking that the math does what it should.  Large integer multiplication, for example, is not implemented in a straightforward way.  If you've never seen it before, you have some (math) homework to do before you trust it.  Same with modular fields.  Same with discrete elliptic curves.

Anyone looking for a project?  A guide, with references and links to examples and tutorials, that takes the reader through the background material and into the code would be fantastic.

1 C++ has much more implicit behavior than C.  For example, in C, you always know when a function was called, and which one.  A grep will get you there every time.  In C++, it isn't always so simple for the layman.


Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: gmaxwell on January 29, 2015, 01:29:49 PM
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.
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...).

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.


Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: unamis76 on January 29, 2015, 02:05:25 PM
I thought about what the OP is saying myself when I read the release notes on the 0.10 RC... But since the code is always public, I've discarded these thoughts :D
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.



Yes, it's true, I should have asked. It's an important topic that I managed to ignore after quite some time using bitcoind and Bitcoin-QT without issues... :)

I seem to have missed that post on reddit. After that post and this thread, I feel like my initial concerns have been addressed, so thank you for that and thanks for the hardwork on developing Bitcoin Core :)


Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: kjj on January 29, 2015, 03:47:41 PM
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.

Yeah, I was talking about the rest of the bitcoin code.


Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: findftp on January 29, 2015, 07:52:58 PM
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.
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...).

Of course it's not about you personally, we all know you are highly credible  ::) ;)

So in short it comes to the question if people want to have a free choice? (to find/pay/trust/learn the skills to review the code)
I'm sorry to go philosophical and might get marked as a troll but your simple one-liner made me think about this. (thanks for that, food for weeks! ;) )





Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: Jace on January 30, 2015, 10:30:07 AM
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?


Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: fluffypony on January 30, 2015, 12:01:01 PM
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?


Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: gmaxwell on January 31, 2015, 03:50:20 AM
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.


Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: colinistheman on January 31, 2015, 04:16:07 AM
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  (http://en.wikipedia.org/wiki/Magic_number_%28programming%29#Unnamed_numerical_constants)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.


Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: gmaxwell on January 31, 2015, 12:19:17 PM
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.


Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: colinistheman on January 31, 2015, 05:35:47 PM
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.


Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: andytoshi on February 01, 2015, 03:50:26 AM
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.


Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: gmaxwell on February 01, 2015, 09:40:56 AM
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.


Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: brituspol on February 01, 2015, 08:53:56 PM
Working with  libsecp256k1 is better than with openssl when we consider continuous and consisting bitcoin development in the long run.


Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: colinistheman on February 03, 2015, 10:15:45 PM
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!


Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: doof on February 05, 2015, 06:33:48 AM
I've been looking at the code, and theres quite a few magic numbers  (http://en.wikipedia.org/wiki/Magic_number_%28programming%29#Unnamed_numerical_constants)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]


Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: Pieter Wuille on February 05, 2015, 06:48:35 AM
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.....


Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: gmaxwell on February 05, 2015, 07:44:07 AM
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.


Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: SteamGamesBTC.com on February 08, 2015, 11:59:56 AM
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.


Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: kjj on February 10, 2015, 05:50:25 AM
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.


Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: Cryddit on February 12, 2015, 02:46:18 AM
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.





Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: bcearl on February 17, 2015, 03:36:54 PM
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.).


Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: CIYAM on February 17, 2015, 03:44:15 PM
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)?


Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: rfcdejong on February 17, 2015, 09:33:00 PM
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/


Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: Cryddit on February 17, 2015, 09:45:28 PM
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.



Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: colinistheman on February 19, 2015, 07:01:58 PM
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 (http://youtu.be/asC_kVJ6sig?t=22m30s). Thanks.

link for anyone else who wishes to hear him speak on this subject. (http://youtu.be/asC_kVJ6sig?t=22m30s)



Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: Cryddit on February 26, 2015, 06:08:54 PM


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.


Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: Cryddit on February 26, 2015, 09:56:55 PM
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.....   ???


Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: zvs on February 26, 2015, 10:58:01 PM
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


Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: Cryddit on February 27, 2015, 05:51:48 AM
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. 


Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: Cryddit on February 27, 2015, 06:01:15 AM
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.



Title: Re: Is bitcoin v0.10's new libsecp256k1 safe & without mathematical backdoors?
Post by: gmaxwell on February 27, 2015, 11:11:22 AM
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.