<div dir="ltr">Hi, <div><br></div><div>"Fuzzing for equivalence" may find some interesting bugs in crypto code. <br></div><div><br></div><div>Example:</div><div><br></div>In 2015 Hanno Böck <a href="https://blog.fuzzing-project.org/31-Fuzzing-Math-miscalculations-in-OpenSSLs-BN_mod_exp-CVE-2015-3193.html">found</a> a correctness bug in openssl's BN_mod_exp by feeding <br><div>inputs into <b>BN_mod_exp</b> and libgcrypt's <b>gcry_mpi_powm</b> and comparing the results. </div><div>Inspired (?) by this bug Ben Laurie added a <a href="https://github.com/openssl/openssl/blob/OpenSSL_1_1_0-stable/fuzz/bignum.c">fuzz target</a> to openssl <br></div>that compares <b>BN_mod_exp</b> against <b>BN_mod_exp_simple</b>. <div>After several CPU years of fuzzing we've found <a href="https://github.com/google/fuzzer-test-suite/tree/master/openssl-1.1.0c">another bug</a> in </div><div>x86 assembly implementation of BN_mod_exp. </div><div><br></div><div><div>What can be improved? <br></div></div><div><br></div><div>First, fuzzing has a chance to find something only if there is something to fuzz. <br></div><div>I encourage everyone to try creating fuzz targets similar to the <a href="https://github.com/openssl/openssl/blob/OpenSSL_1_1_0-stable/fuzz/bignum.c">BN_mod_exp</a> one. </div><div>It does not have to be just bignums! Anything that has two or more implementations. </div><div>Like this:</div><div><br></div>extern "C" int LLVMFuzzerTestOneInput(const unsigned char *Data, size_t Size) {<br>   if (ImplementationA(Data,Size) != ImplementationB(Data,Size)) <div>      abort();<br>}</div><div>Once you add such fuzz target to your code base and fuzz it a bit with <a href="http://libfuzzer.info">libFuzzer</a> or <a href="http://lcamtuf.coredump.cx/afl/">AFL</a></div><div>you are welcome to add your project to <a href="https://github.com/google/oss-fuzz">OSS-Fuzz</a>, our continuous fuzzing service. </div><div><br><div>Now, such equivalence fuzzing is not always possible. </div><div>Sometimes there are two implementations of the same thing in two different libraries,</div><div>but you may not be able to link them together in one binary (e.g. openssl vs boringssl). </div><div>Sometimes a library may have two or more implementations of the same thing, </div><div>bit you can't run them together (e.g. plain C vs x86_64 assembler, and the version</div><div>is determined at configure time).</div><div><br></div><div>During HACS we tried to come up with a way to fuzz for equivalence using a client-server</div><div>model, where two binaries cooperate to find equivalence bugs.</div><div>I've implemented a prototype that works like this: </div><div>You implement *two* fuzz targets:</div><div><br></div><div>extern "C" void LLVMFuzzerAnnounceOutput(const uint8_t *Data, size_t Size);<br></div><div>extern "C" int LLVMFuzzerTestOneInput(const unsigned char *Data, size_t Size) {</div><div>   ...<br>   <b>ImplementationA</b>(Data,Size, &Output, &OutputSize);</div><div>   LLVMFuzzerAnnounceOutput(Output, OutputSize);</div><div><div>}</div></div><div>// Same for <b>ImplementationB</b><br></div><div><br></div><div>Then you build these two fuzz targets into two independent binaries (with libFuzzer)</div><div>and run them like this: </div><div><br></div><div>EquivalenceATest -run_equivalence_server=12345 &</div><div>PID=$!</div><div>sleep 1</div><div>EquivalenceBTest  -use_equivalence_server=12345</div><div>kill -9 $PID<br></div><div>(and the other way around)</div><div><br></div><div>attached is a modified openssl fuzz target that allows to fuzz for equivalence:</div><div>BN_mod_exp vs BN_mod_exp_simple and pure C vs assembler. </div><div><br></div><div>Note that this mode is not yet documented nor it is supported on OSS-Fuzz. </div><div>It's a chicken-and-egg -- before we have several real-life pairs to test, </div><div>we can't evaluate the idea & implementation. </div><div><br></div><div>So, I encourage you to try this experimental way of equivalence fuzzing.</div></div><div>I am interested in cases where two things from the same library are compared</div><div>*and* where two different libraries are compared. </div><div>Please let me know about your experiments so that I can try them too. </div><div><br></div><div>If this turns out to be interesting, we'll support equivalence fuzzing on OSS-Fuzz. </div><div><br></div><div>Thanks, </div><div><br></div><div>--kcc </div><div><br></div><div><br></div></div>