Repository: randombit/botan
Pull request #3160 (2023-01-05 22:24:06)

Add fuzzers for the Comba multiply and square functions


Patch:
diff --git a/configure.py b/configure.py
index 32739bf16..0c878336d 100755
--- a/configure.py
+++ b/configure.py
@@ -2243,6 +2243,7 @@ def create_template_vars(source_paths, build_paths, options, modules, cc, arch,
         'system_cert_bundle': options.system_cert_bundle,
 
         'fuzzer_mode': options.unsafe_fuzzer_mode,
+        'building_fuzzers': options.build_fuzzers,
         'fuzzer_type': options.build_fuzzers.upper() if options.build_fuzzers else '',
 
         'with_valgrind': options.with_valgrind,
diff --git a/doc/dev_ref/fuzzing.rst b/doc/dev_ref/fuzzing.rst
index 46e60fb53..888274a69 100644
--- a/doc/dev_ref/fuzzing.rst
+++ b/doc/dev_ref/fuzzing.rst
@@ -19,7 +19,7 @@ need to compile libFuzzer::
 Then build the fuzzers::
 
   $ ./configure.py --cc=clang --build-fuzzer=libfuzzer --unsafe-fuzzer-mode \
-        --enable-sanitizers=coverage,address,undefined
+        --with-debug-info --enable-sanitizers=coverage,address,undefined
   $ make fuzzers
 
 Enabling 'coverage' sanitizer flags is required for libFuzzer to work.
diff --git a/src/build-data/buildh.in b/src/build-data/buildh.in
index 67963b20e..9fa9a4bb3 100644
--- a/src/build-data/buildh.in
+++ b/src/build-data/buildh.in
@@ -54,13 +54,14 @@
 #define BOTAN_MP_WORD_BITS %{mp_bits}
 
 %{if fuzzer_mode}
-/** Disables certain validation checks to easy fuzzability of the library
+/** Disables certain validation checks to ease fuzzability of the library
  * @warning This causes the library build to be insecure, hence, it must not be
  *          used in a production environment!
  */
 #define BOTAN_UNSAFE_FUZZER_MODE
 %{endif}
 %{if fuzzer_type}
+#define BOTAN_FUZZERS_ARE_BEING_BUILT
 #define BOTAN_FUZZER_IS_%{fuzzer_type}
 %{endif}
 
diff --git a/src/fuzzer/fuzzers.h b/src/fuzzer/fuzzers.h
index 1df6e94c9..9bdf5b114 100644
--- a/src/fuzzer/fuzzers.h
+++ b/src/fuzzer/fuzzers.h
@@ -50,11 +50,11 @@ inline Botan::RandomNumberGenerator& fuzzer_rng()
    }
 
 #define FUZZER_WRITE_AND_CRASH(expr) \
-   do { std::cerr << expr; abort(); } while(0)
+   do { std::cerr << expr << " @ Line " << __LINE__ << " in " << __FILE__ << "\n"; abort(); } while(0)
 
 #define FUZZER_ASSERT_EQUAL(x, y) do {                                  \
    if(x != y) {                                                         \
-      FUZZER_WRITE_AND_CRASH(#x << " = " << x << " !=\n"                \
+      FUZZER_WRITE_AND_CRASH(#x << " = " << x << " != "                \
                              << #y << " = " << y << "\n");              \
    } } while(0)
 
diff --git a/src/fuzzer/mp_comba_mul.cpp b/src/fuzzer/mp_comba_mul.cpp
new file mode 100644
index 000000000..2da8a4162
--- /dev/null
+++ b/src/fuzzer/mp_comba_mul.cpp
@@ -0,0 +1,61 @@
+/*
+* (C) 2023 Jack Lloyd
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#include "mp_fuzzers.h"
+
+void fuzz(const uint8_t in[], size_t in_len)
+   {
+   const size_t words = (in_len + sizeof(word) - 1) / sizeof(word);
+
+   if(in_len == 0 || words > 2*16)
+      return;
+
+   word x[24] = { 0 };
+   word y[24] = { 0 };
+
+   std::memcpy(x, in, in_len / 2);
+   std::memcpy(y, in + in_len / 2, in_len - (in_len / 2));
+
+   const size_t x_words = ((in_len / 2) + sizeof(word) - 1) / sizeof(word);
+   const size_t y_words = ((in_len - (in_len / 2)) + sizeof(word) - 1) / sizeof(word);
+
+   word z4[2*4] = { 0 };
+   word z6[2*6] = { 0 };
+   word z8[2*8] = { 0 };
+   word z9[2*9] = { 0 };
+   word z16[2*16] = { 0 };
+   word z24[2*24] = { 0 };
+
+   word z_ref[2*24] = { 0 };
+
+   Botan::basecase_mul(z_ref, 2*24, x, x_words, y, y_words);
+
+   if(words <= 8)
+      Botan::bigint_comba_mul4(z4, x, y);
+   if(words <= 12)
+      Botan::bigint_comba_mul6(z6, x, y);
+   if(words <= 16)
+      Botan::bigint_comba_mul8(z8, x, y);
+   if(words <= 18)
+      Botan::bigint_comba_mul9(z9, x, y);
+   if(words <= 32)
+      Botan::bigint_comba_mul16(z16, x, y);
+   if(words <= 48)
+      Botan::bigint_comba_mul24(z24, x, y);
+
+   if(words <= 8)
+      compare_word_vec(z4, 2*4, z6, 2*6, "mul4 vs mul6");
+   if(words <= 12)
+      compare_word_vec(z6, 2*6, z8, 2*8, "mul6 vs mul8");
+   if(words <= 16)
+      compare_word_vec(z8, 2*8, z9, 2*9, "mul8 vs mul9");
+   if(words <= 18)
+      compare_word_vec(z9, 2*9, z16, 2*16, "mul9 vs mul16");
+   if(words <= 32)
+      compare_word_vec(z16, 2*16, z24, 2*24, "mul16 vs mul24");
+
+   compare_word_vec(z24, 2*24, z_ref, 2*24, "mul24 vs basecase mul");
+   }
diff --git a/src/fuzzer/mp_comba_sqr.cpp b/src/fuzzer/mp_comba_sqr.cpp
new file mode 100644
index 000000000..13b4a9a57
--- /dev/null
+++ b/src/fuzzer/mp_comba_sqr.cpp
@@ -0,0 +1,88 @@
+/*
+* (C) 2023 Jack Lloyd
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#include "mp_fuzzers.h"
+
+void fuzz(const uint8_t in[], size_t in_len)
+   {
+   const size_t words = (in_len + sizeof(word) - 1) / sizeof(word);
+
+   if(in_len == 0 || words > 24)
+      return;
+
+   word x[24] = { 0 };
+
+   std::memcpy(x, in, in_len);
+
+   word z4[2*4] = { 0 };
+   word z6[2*6] = { 0 };
+   word z8[2*8] = { 0 };
+   word z9[2*9] = { 0 };
+   word z16[2*16] = { 0 };
+   word z24[2*24] = { 0 };
+
+   word z_ref[2*24] = { 0 };
+
+   //dump_word_vec("x", x, words);
+
+   Botan::basecase_sqr(z_ref, 2*24, x, words);
+
+   if(words <= 4)
+      {
+      Botan::bigint_comba_sqr4(z4, x);
+      word z4m[2*4] = { 0 };
+      Botan::bigint_comba_mul4(z4m, x, x);
+      compare_word_vec(z4m, 2*4, z4, 2*4, "sqr4 vs mul4");
+      }
+   if(words <= 6)
+      {
+      Botan::bigint_comba_sqr6(z6, x);
+      word z6m[2*6] = { 0 };
+      Botan::bigint_comba_mul6(z6m, x, x);
+      compare_word_vec(z6m, 2*6, z6, 2*6, "sqr6 vs mul6");
+      }
+   if(words <= 8)
+      {
+      Botan::bigint_comba_sqr8(z8, x);
+      word z8m[2*8] = { 0 };
+      Botan::bigint_comba_mul8(z8m, x, x);
+      compare_word_vec(z8m, 2*8, z8, 2*8, "sqr8 vs mul8");
+      }
+   if(words <= 9)
+      {
+      Botan::bigint_comba_sqr9(z9, x);
+      word z9m[2*9] = { 0 };
+      Botan::bigint_comba_mul9(z9m, x, x);
+      compare_word_vec(z9m, 2*9, z9, 2*9, "sqr9 vs mul9");
+      }
+   if(words <= 16)
+      {
+      Botan::bigint_comba_sqr16(z16, x);
+      word z16m[2*16] = { 0 };
+      Botan::bigint_comba_mul16(z16m, x, x);
+      compare_word_vec(z16m, 2*16, z16, 2*16, "sqr16 vs mul16");
+      }
+   if(words <= 24)
+      {
+      Botan::bigint_comba_sqr24(z24, x);
+      word z24m[2*24] = { 0 };
+      Botan::bigint_comba_mul24(z24m, x, x);
+      compare_word_vec(z24m, 2*24, z24, 2*24, "sqr24 vs mul24");
+      }
+
+   if(words <= 4)
+      compare_word_vec(z4, 2*4, z6, 2*6, "sqr4 vs sqr6");
+   if(words <= 6)
+      compare_word_vec(z6, 2*6, z8, 2*8, "sqr6 vs sqr8");
+   if(words <= 8)
+      compare_word_vec(z8, 2*8, z9, 2*9, "sqr8 vs sqr9");
+   if(words <= 9)
+      compare_word_vec(z9, 2*9, z16, 2*16, "sqr9 vs sqr16");
+   if(words <= 16)
+      compare_word_vec(z16, 2*16, z24, 2*24, "sqr16 vs sqr24");
+
+   compare_word_vec(z24, 2*24, z_ref, 2*24, "sqr24 vs basecase sqr");
+   }
diff --git a/src/fuzzer/mp_fuzzers.h b/src/fuzzer/mp_fuzzers.h
new file mode 100644
index 000000000..491a325c4
--- /dev/null
+++ b/src/fuzzer/mp_fuzzers.h
@@ -0,0 +1,73 @@
+/*
+* (C) 2023 Jack Lloyd
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#ifndef BOTAN_FUZZER_MP_HELPERS_H_
+#define BOTAN_FUZZER_MP_HELPERS_H_
+
+#include "fuzzers.h"
+#include <botan/internal/mp_core.h>
+
+#if BOTAN_MP_WORD_BITS == 64
+#define WORD_FORMAT_STRING "%016lX"
+#else
+#define WORD_FORMAT_STRING "%08X"
+#endif
+
+using Botan::word;
+
+namespace {
+
+void dump_word_vec(const char* name, const word x[], size_t x_len)
+   {
+   fprintf(stderr, "%s = ", name);
+   for(size_t i = 0; i != x_len; ++i)
+      {
+      fprintf(stderr, WORD_FORMAT_STRING, x[i]);
+      fprintf(stderr, " ");
+      }
+   fprintf(stderr, "\n");
+   }
+
+void compare_word_vec(const word x[], size_t x_len,
+                      const word y[], size_t y_len,
+                      const char* comparing)
+   {
+   const size_t common_words = std::min(x_len, y_len);
+
+   for(size_t i = 0; i != common_words; ++i)
+      {
+      if(x[i] != y[i])
+         {
+         dump_word_vec("x", x, x_len);
+         dump_word_vec("y", y, y_len);
+         FUZZER_WRITE_AND_CRASH("Comparison failed " << comparing);
+         }
+      }
+
+   // all other words must be zero
+   for(size_t i = common_words; i != x_len; ++i)
+      {
+      if(x[i] != 0)
+         {
+         dump_word_vec("x", x, x_len);
+         dump_word_vec("y", y, y_len);
+         FUZZER_WRITE_AND_CRASH("Unexpected non-zero in high words of x " << comparing);
+         }
+      }
+   for(size_t i = common_words; i != y_len; ++i)
+      {
+      if(y[i] != 0)
+         {
+         dump_word_vec("x", x, x_len);
+         dump_word_vec("y", y, y_len);
+         FUZZER_WRITE_AND_CRASH("Unexpected non-zero in high words of y " << comparing);
+         }
+      }
+   }
+
+}
+
+#endif
diff --git a/src/lib/math/mp/mp_core.h b/src/lib/math/mp/mp_core.h
index 5c8ce1e95..1279c016d 100644
--- a/src/lib/math/mp/mp_core.h
+++ b/src/lib/math/mp/mp_core.h
@@ -275,7 +275,7 @@ inline word bigint_add3_nc(word z[],
 * @param x the first operand (and output)
 * @param x_size size of x
 * @param y the second operand
-* @param y_size size of y (must be >= x_size)
+* @param y_size size of y (must be <= x_size)
 */
 inline void bigint_add2(word x[], size_t x_size,
                         const word y[], size_t y_size)
@@ -338,6 +338,10 @@ inline void bigint_sub2_rev(word x[], const word y[], size_t y_size)
 
 /**
 * Three operand subtraction
+*
+* Expects that x_size >= y_size
+*
+* Writes to z[0:x_size] and returns borrow
 */
 inline word bigint_sub3(word z[],
                         const word x[], size_t x_size,
@@ -770,19 +774,19 @@ inline word bigint_modop(word n1, word n0, word d)
 /*
 * Comba Multiplication / Squaring
 */
-void bigint_comba_mul4(word z[8], const word x[4], const word y[4]);
-void bigint_comba_mul6(word z[12], const word x[6], const word y[6]);
-void bigint_comba_mul8(word z[16], const word x[8], const word y[8]);
-void bigint_comba_mul9(word z[18], const word x[9], const word y[9]);
-void bigint_comba_mul16(word z[32], const word x[16], const word y[16]);
-void bigint_comba_mul24(word z[48], const word x[24], const word y[24]);
-
-void bigint_comba_sqr4(word out[8], const word in[4]);
-void bigint_comba_sqr6(word out[12], const word in[6]);
-void bigint_comba_sqr8(word out[16], const word in[8]);
-void bigint_comba_sqr9(word out[18], const word in[9]);
-void bigint_comba_sqr16(word out[32], const word in[16]);
-void bigint_comba_sqr24(word out[48], const word in[24]);
+BOTAN_FUZZER_API void bigint_comba_mul4(word z[8], const word x[4], const word y[4]);
+BOTAN_FUZZER_API void bigint_comba_mul6(word z[12], const word x[6], const word y[6]);
+BOTAN_FUZZER_API void bigint_comba_mul8(word z[16], const word x[8], const word y[8]);
+BOTAN_FUZZER_API void bigint_comba_mul9(word z[18], const word x[9], const word y[9]);
+BOTAN_FUZZER_API void bigint_comba_mul16(word z[32], const word x[16], const word y[16]);
+BOTAN_FUZZER_API void bigint_comba_mul24(word z[48], const word x[24], const word y[24]);
+
+BOTAN_FUZZER_API void bigint_comba_sqr4(word out[8], const word in[4]);
+BOTAN_FUZZER_API void bigint_comba_sqr6(word out[12], const word in[6]);
+BOTAN_FUZZER_API void bigint_comba_sqr8(word out[16], const word in[8]);
+BOTAN_FUZZER_API void bigint_comba_sqr9(word out[18], const word in[9]);
+BOTAN_FUZZER_API void bigint_comba_sqr16(word out[32], const word in[16]);
+BOTAN_FUZZER_API void bigint_comba_sqr24(word out[48], const word in[24]);
 
 /*
 * Montgomery reduction
@@ -841,11 +845,25 @@ inline void bigint_monty_redc(word z[],
       bigint_monty_redc_generic(z, z_size, p, p_size, p_dash, ws);
    }
 
+/**
+* Basecase O(N^2) multiplication
+*/
+BOTAN_FUZZER_API
+void basecase_mul(word z[], size_t z_size,
+                  const word x[], size_t x_size,
+                  const word y[], size_t y_size);
+
+/**
+* Basecase O(N^2) squaring
+*/
+BOTAN_FUZZER_API
+void basecase_sqr(word z[], size_t z_size,
+                  const word x[], size_t x_size);
+
 
 /*
 * High Level Multiplication/Squaring Interfaces
 */
-
 void bigint_mul(word z[], size_t z_size,
                 const word x[], size_t x_size, size_t x_sw,
                 const word y[], size_t y_size, size_t y_sw,
diff --git a/src/lib/math/mp/mp_karat.cpp b/src/lib/math/mp/mp_karat.cpp
index 63885db17..c269e352b 100644
--- a/src/lib/math/mp/mp_karat.cpp
+++ b/src/lib/math/mp/mp_karat.cpp
@@ -13,11 +13,6 @@
 
 namespace Botan {
 
-namespace {
-
-const size_t KARATSUBA_MULTIPLY_THRESHOLD = 32;
-const size_t KARATSUBA_SQUARE_THRESHOLD = 32;
-
 /*
 * Simple O(N^2) Multiplication
 */
@@ -74,6 +69,11 @@ void basecase_sqr(word z[], size_t z_size,
       }
    }
 
+namespace {
+
+const size_t KARATSUBA_MULTIPLY_THRESHOLD = 32;
+const size_t KARATSUBA_SQUARE_THRESHOLD = 32;
+
 /*
 * Karatsuba Multiplication Operation
 */
diff --git a/src/lib/utils/compiler.h b/src/lib/utils/compiler.h
index 2f24e30ad..50f65f7b2 100644
--- a/src/lib/utils/compiler.h
+++ b/src/lib/utils/compiler.h
@@ -50,6 +50,19 @@
 */
 #define BOTAN_TEST_API BOTAN_DLL
 
+/**
+* Used to annotate API exports which are exported but only for the
+* purposes of fuzzing. They should not be used by applications and
+* may be removed or changed without notice.
+*
+* They are only exported if the fuzzers are being built
+*/
+#if defined(BOTAN_FUZZERS_ARE_BEING_BUILT)
+  #define BOTAN_FUZZER_API BOTAN_DLL
+#else
+  #define BOTAN_FUZZER_API
+#endif
+
 /*
 * Define BOTAN_FUNC_ISA
 */


Test patch:
diff --git a/src/scripts/test_fuzzers.py b/src/scripts/test_fuzzers.py
index 37a7dff9b..f911ab195 100755
--- a/src/scripts/test_fuzzers.py
+++ b/src/scripts/test_fuzzers.py
@@ -156,7 +156,7 @@ def main(args=None):
         # Generate a random corpus for fuzzers without a corpus
         random_corpus_dir = tempfile.mkdtemp(prefix='fuzzer_corpus_')
 
-        for i in range(100):
+        for i in range(1000):
             random_input = os.urandom(i)
             fd = open(os.path.join(random_corpus_dir, 'input_%d' % (i)), 'wb')
             fd.write(random_input)