Why Bitcoin Core 0.10's release notes say “…libsecp256k1 is better than…OpenSSL”

https://www.reddit.com/r/Bitcoin/comments/2rrxq7/on_why_010s_release_notes_say_we_have_reason_to/

by bdr • 12 years ago

137 33 12 years ago

reddit.com

java-man2• 12 years ago

no software is truly safe until the amount of testing code exceeds the amount of main code...

comrade1• 12 years ago

I don't know man... I can write some pretty lame unit tests.

tribaal2• 12 years ago

Not to mention, massive amounts of lame unit tests exercising a tiny fraction of the code base :p

Of course, "java-man" is probably just trolling.

bmm6o• 12 years ago

You should make it clear if you think it's necessary but not sufficient.

mjs• 12 years ago

Interesting position on testing: "I generally don't consider my own software adequately enough tested until its tests have turned up a bug in a compiler/toolchain. So far I've not encountered a compiler bug for libsecp256k1 [...] so I may have to settle for discovering that a ubiquitous system library couldn't square correctly."

(The bug was found via comparing the output of libsecp256k1 and OpenSSL on "specially-constructed random inputs.")

illumen• 12 years ago

Comparing multiple implementations is a great way to find bugs. Even running the same code with different compilers or platforms helps find bugs.

It doesn't find cases where they are both wrong, but often finds cases where one of them is wrong.

It is a very common testing strategy with maths libraries.

nickik• 12 years ago

You might be intrested in this [1]. Its a 31C3 talk about exactly this. There idea is to write a runable spec (that only focues on correctness, instead of speed and things like that) that then can be used to test against real world application.

There idea is to do this against all the MAJOR interfaces that we all depend on TCP/IP, x86 memory model and stuff like that.

[1] http://events.ccc.de/congress/2014/Fahrplan/events/6574.html (the talk is on youtube or on ccc video streaming side)

derf_3• 12 years ago

For those not familiar with Greg's work, this presentation on the testing he did for the Opus codec is informative: https://www.ietf.org/proceedings/82/slides/codec-4.pdf

Particularly slide 20.

kosma• 12 years ago

That's only because author uses a pretty standard compiler. Try building your flawless library on ARM, Newlib, etc. and you're pretty much fighting your tools all the time. The first compiler/toolchain bug is a rite of passage, yes, but not a measure of the code quality (although they do correlate).

gcp• 12 years ago

It does say "a compiler/toolchain". Opus has both fixed point and floating point implementations. The fixed point one was extensively tested on ARM too, I'm sure.

lultimouomo• 12 years ago

The quoting is quite misguiding, the article and its title say:

we have reason to believe that libsecp256k1 is better tested and more thoroughly reviewed than the implementation in OpenSSL

which is something very different from generically being "better" (which has 0 information value, BTW).

nullc4• 12 years ago

Thanks, yes. I spoke intentionally.

bdr• 12 years ago

Sorry. I knew I was mangling it, but it was the only way to get within HN's title restrictions. Thought about leaving a pre-emptive comment to that effect, and I probably should have.

avian• 12 years ago

The incorrectly squared numbers would be expected to be found randomly with probability around one in 2^128

1:2^128 is an incredibly low probability. Universe is only around 2^86 nanoseconds old. For all practical purposes, an event with a 1:2^128 probability is impossible.

They say that they found it with randomized testing (although one that explores "a class of rare corner cases") and dismiss the claim that this is a class of bugs that can only be found by analysis of the implementation.

I think a test that manages to find a bug like this can not be called "random" (as in, throwing random inputs to a black box). Obviously I don't know the details, but I am sure their test incorporated a great deal of detailed knowledge of algorithms used in the computation.

stingraycharles• 12 years ago

While I understand where your argument is coming from, it is important to ask the question: how many times a day is this piece of code executed on all computers worldwide?

Surely the chance of one person running into this bug is extremely small, but what about all the people on earth combined?

Nevertheless, I think we can classify this method of testing as some sort of hybrid between brute force testing and auditing; I don't think the authors are dismissing that claim this either, but are merely stating that there are ways to make very informed test cases without looking at the code.

mike_hearn• 12 years ago

Reasoning about large numbers is hard. 2^128 is considered enough security in any crypto scheme to be "impossible" to break. Consider that Bitcoin uses ECDSA which gives 128 bits of security. This is not brute forceable as there isn't enough energy around to actually flip the bits that many times, let alone do the calculations.

marcusf• 12 years ago

Caveat that I might be completely off, but if, say, 10 bn people tried once a nanosecond since the inception of the universe, you'd still have only 10^10 * 2^86 ≈ 2^33 * 2^86 = 2^119 attempts, that still only cover's 2^-9 (i.e. 1/512th) of the total addressable 2^128 space, i.e. still fairly unlikely that you'll have hit that specific number.

derf_3• 12 years ago

He isn't using black box testing, he's using white box testing (knowing Greg, either KLEE [1] or AFL [2]... probably both... and probably also black box testing). The test does incorporate a great deal of knowledge of the algorithms (in fact, complete knowledge), but the point is that it's the machine that does the analysis of the implementation, not a human.

[1] https://klee.github.io/

[2] http://lcamtuf.coredump.cx/afl/

nullc4• 12 years ago

Though I use both klee and AFL, this particular instance was found with blackbox randomized tests; using numbers with low transition probabilities. E.g. 00000111111111000111000000000000.

Klee or AFL would be somewhat unlikely to find this particular problem because the error was an omitted branch, so they wouldn't know there was a case left to be satisfied.

nullc4• 12 years ago

but I am sure their test incorporated a great deal of detailed knowledge of algorithms used in the computation

Actually no. In this case it exploits the knowledge that "low frequency inputs tend to explore more program space", It was found using numbers with a low transition probability between zero and one. This is an approach also used for digital circuit verification too.

It's true that I also know the code is full of hard to hit branches for carries, which does partially motivate that selection. But importantly, "We weren't even testing for that." the OpenSSL code in general has an entirely different algorithm than the libsecp256k1 code; and I hadn't recently looked at any OpenSSL innards.

Why Bitcoin Core 0.10's release notes say “…libsecp256k1 is better than…OpenSSL”

Related Stories