Quote from: 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, 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.