bignum

[Michal Zalewski]

Not sure if you've seen it, but Hanno had some very interesting
results with fuzzing crypto-relevant bignum implementations. His basic
approach, I think, is to calculate the same value using two
"competing" libraries or two algorithms that should give the same
result, and then assert() if the output doesn't match.

https://blog.fuzzing-project.org/38-Miscomputations-of-elliptic-curve-scalar-multiplications-in-Nettle.html

https://blog.fuzzing-project.org/31-Fuzzing-Math-miscalculations-in-OpenSSLs-BN_mod_exp-CVE-2015-3193.html

https://blog.fuzzing-project.org/37-Mozilla-NSS-Wrong-calculation-results-in-mp_div-and-mp_exptmod.html

Peace,
/mz

[Peter Gutmann]

Michal Zalewski <lca...@gmail.com> writes:

>Not sure if you've seen it, but Hanno had some very interesting results with
>fuzzing crypto-relevant bignum implementations.

You don't know the half of it :-). Even without fuzzing, considerable bugs
have been discovered in bignum libraries. Not naming names, but look at the
code for the modmult and modexp routines used by certain libraries and see if
you'd want to feed attacker-controlled data to that stuff.

>His basic approach, I think, is to calculate the same value using two
>"competing" libraries or two algorithms that should give the same result, and
>then assert() if the output doesn't match.

This is, unfortunately, something that requires quite a bit of effort to do
(and I don't envy Hanno the amount of work he's probably had to put in). I
played with using PARI/GP (my go-to gold standard) for this, but you need to
write a pile of support code to do the A/B testing, eventually I shelved it
because there was more... outside incentivisation to re-paint the deck than to
fuzz bignum code :-).

Peter.

[Hanno Böck]

Hi,

Thanks for bringing that up here.

In case people haven't seen it, I have published some code examples,
that should give people an idea how these things worked:
https://github.com/hannob/bignum-fuzz

It might be interesting to investigate closer why afl is good at
finding these things.

One thing that I can share here: I tried to adapt the code for the
openssl modexp code to libfuzzer and it didn't find the bug after
several days. afl did so reliably after ~1 day on the same machine.

As afl and libfuzzer have relatively similar strategies and libfuzzer
should be faster I found that noteworthy.

One suspicion I have is that afl doesn't really find these bugs due to
its smart evolutionary algorithm, but due to the fact that it tends to
generate repeating patterns. If you look at the inputs for most of
these bugs they often look like this:
#define MI
"414141414141414141414127414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141414141800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000005"
#define AI "050505050505" #define BI "02"

Obviously highly repetetive patterns.

Also maybe noteworthy: I always tested with asan enabled, but I didn't
find any bug where a specific input would trigger a memory access
violation. All the bugs found where of this "corner case causes faulty
carry propagation"-type.

What I thought of doing and haven't done yet: Creating a collection of
test inputs that have triggered bugs in bignum libs in the past. That
could be used as a test suite to see whether the same bug may be
present in another library.

--
Hanno Böck
http://hboeck.de/

mail/jabber: ha...@hboeck.de
GPG: BBB51E42

[Peter Gutmann]

Hanno Böck <ha...@hboeck.de> writes:

>What I thought of doing and haven't done yet: Creating a collection of test
>inputs that have triggered bugs in bignum libs in the past. That could be
>used as a test suite to see whether the same bug may be present in another
>library.

I'm not sure if that would be overly useful because a lot of the stuff would
be code-path-dependent. That is, it can't hurt, but being able to pass fixed
test vectors isn't a guarantee that the code is OK. AFL's ability to generate
inputs as required that exercise all the code paths is quite valuable here.

Another thing that's useful is generating vectors yourself based on what you
know the code is meant to do. For my own test vectors I used awkward corner
cases like all-one or all-zero bits with a one or zero in appropriate
locations, things I knew would cause issues with carries, funny shift
quantities, that sort of thing. To take the recent non-prime prime issue in
socat as an example, the chances of randomly hitting a prime when fuzzing are
pretty low so you need to help the fuzzer along a bit in some cases.

Peter.

[Peter Gutmann]

I wrote:

>Another thing that's useful is generating vectors yourself based on what you
>know the code is meant to do.

Case in point:

In case of the BN_sqr() bug a possibility is simply to compare the result of
the squaring with a multiplication of a number by itself.

So the problem with this is that if your BN_mult() routine calls BN_sqr() if
the two input values are the same then you're really fuzzing BN_sqr() against
itself.

It's tricky to get right :-).

Peter.

[Tim Newsham]

What I thought of doing and haven't done yet: Creating a collection of
test inputs that have triggered bugs in bignum libs in the past. That
could be used as a test suite to see whether the same bug may be
present in another library.

An idea: run AFL in master-slave mode, but running each slave with a different implementation.  AFL should cross-pollinate the queues from the results of the other fuzzers.