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

[colinistheman]

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

time: 11:53-12:24

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.

[1714554931]

1714554931

[1714554931]

1714554931

[1714554931]

1714554931

[1714554931]

1714554931

[1714554931]

1714554931

[1714554931]

1714554931

[kjj]

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.

[colinistheman]

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.

[andytoshi]

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

[unamis76]

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

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

[RodeoX]

That's the right question Collin. Fortunately, because this is all open source you can get a definitive answer.

[gmaxwell]

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

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.

[colinistheman]

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

(time: 11:53-12:24)

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.

[colinistheman]

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

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.

[doof]

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

[colinistheman]

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

Did you see andytoshi's post? After you've read it, does that make you feel any better, or no?

[andytoshi]

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

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

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

[Pieter Wuille]

Hi colinistheman,

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

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

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

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

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

[Pieter Wuille]

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.

[findftp]

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.

[kjj]

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 harder¹ 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.

¹ 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.

[gmaxwell]

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.

[unamis76]

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

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

[kjj]

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.

[findftp]

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! )