[hacs] fuzzing for equivalence

[Kostya Serebryany]

Hi,

"Fuzzing for equivalence" may find some interesting bugs in crypto code.

Example:

In 2015 Hanno Böck found
<https://blog.fuzzing-project.org/31-Fuzzing-Math-miscalculations-in-OpenSSLs-BN_mod_exp-CVE-2015-3193.html>
a correctness bug in openssl's BN_mod_exp by feeding
inputs into *BN_mod_exp* and libgcrypt's *gcry_mpi_powm* and comparing the
results.
Inspired (?) by this bug Ben Laurie added a fuzz target
<https://github.com/openssl/openssl/blob/OpenSSL_1_1_0-stable/fuzz/bignum.c>
to openssl
that compares *BN_mod_exp* against *BN_mod_exp_simple*.
After several CPU years of fuzzing we've found another bug
<https://github.com/google/fuzzer-test-suite/tree/master/openssl-1.1.0c> in
x86 assembly implementation of BN_mod_exp.

What can be improved?

First, fuzzing has a chance to find something only if there is something to
fuzz.
I encourage everyone to try creating fuzz targets similar to the BN_mod_exp
<https://github.com/openssl/openssl/blob/OpenSSL_1_1_0-stable/fuzz/bignum.c>
one.
It does not have to be just bignums! Anything that has two or more
implementations.
Like this:

extern "C" int LLVMFuzzerTestOneInput(const unsigned char *Data, size_t
Size) {
   if (ImplementationA(Data,Size) != ImplementationB(Data,Size))
      abort();
}
Once you add such fuzz target to your code base and fuzz it a bit with
libFuzzer <http://libfuzzer.info> or AFL <http://lcamtuf.coredump.cx/afl/>
you are welcome to add your project to OSS-Fuzz
<https://github.com/google/oss-fuzz>, our continuous fuzzing service.

Now, such equivalence fuzzing is not always possible.
Sometimes there are two implementations of the same thing in two different
libraries,
but you may not be able to link them together in one binary (e.g. openssl
vs boringssl).
Sometimes a library may have two or more implementations of the same thing,
bit you can't run them together (e.g. plain C vs x86_64 assembler, and the
version
is determined at configure time).

During HACS we tried to come up with a way to fuzz for equivalence using a
client-server
model, where two binaries cooperate to find equivalence bugs.
I've implemented a prototype that works like this:
You implement *two* fuzz targets:

extern "C" void LLVMFuzzerAnnounceOutput(const uint8_t *Data, size_t Size);
extern "C" int LLVMFuzzerTestOneInput(const unsigned char *Data, size_t
Size) {
   ...
   *ImplementationA*(Data,Size, &Output, &OutputSize);
   LLVMFuzzerAnnounceOutput(Output, OutputSize);
}
// Same for *ImplementationB*

Then you build these two fuzz targets into two independent binaries (with
libFuzzer)
and run them like this:

EquivalenceATest -run_equivalence_server=12345 &
PID=$!
sleep 1
EquivalenceBTest  -use_equivalence_server=12345
kill -9 $PID
(and the other way around)

attached is a modified openssl fuzz target that allows to fuzz for
equivalence:
BN_mod_exp vs BN_mod_exp_simple and pure C vs assembler.

Note that this mode is not yet documented nor it is supported on OSS-Fuzz.
It's a chicken-and-egg -- before we have several real-life pairs to test,
we can't evaluate the idea & implementation.

So, I encourage you to try this experimental way of equivalence fuzzing.
I am interested in cases where two things from the same library are compared
*and* where two different libraries are compared.
Please let me know about your experiments so that I can try them too.

If this turns out to be interesting, we'll support equivalence fuzzing on
OSS-Fuzz.

Thanks,

--kcc
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/hacs/attachments/20170202/5861abf9/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: bn_eq.c
Type: text/x-csrc
Size: 2173 bytes
Desc: not available
URL: <http://moderncrypto.org/mail-archive/hacs/attachments/20170202/5861abf9/attachment.c>