In ressol and modexp fuzzers, fix the prime p

For ressol this avoids very slow runtimes in situations when p
is actually a composite. This normally leads to algorithm failure
eventually but can be slow.

2 files changed, 29 insertions, 37 deletions

diff --git a/src/extra_tests/fuzzers/jigs/pow_mod.cpp b/src/extra_tests/fuzzers/jigs/pow_mod.cpp
index 65181ac93..c97dd78cd 100644
--- a/src/extra_tests/fuzzers/jigs/pow_mod.cpp
+++ b/src/extra_tests/fuzzers/jigs/pow_mod.cpp
@@ -9,7 +9,7 @@
 #include <botan/reducer.h>
 #include <botan/pow_mod.h>
 
-BigInt simple_power_mod(BigInt x, BigInt n, const BigInt& p)
+BigInt simple_power_mod(BigInt x, BigInt n, const BigInt& p, const Modular_Reducer& mod_p)
    {
    if(n == 0)
       {
@@ -18,7 +18,6 @@ BigInt simple_power_mod(BigInt x, BigInt n, const BigInt& p)
       return 1;
       }
 
-   Modular_Reducer mod_p(p);
    BigInt y = 1;
 
    while(n > 1)
@@ -35,17 +34,19 @@ BigInt simple_power_mod(BigInt x, BigInt n, const BigInt& p)
 
 void fuzz(const uint8_t in[], size_t len)
    {
-   if(len % 3 != 0 || len > 3 * (2048/8))
-      return;
+   static const size_t p_bits = 1024;
+   static const BigInt p = random_prime(fuzzer_rng(), p_bits);
+   static Modular_Reducer mod_p(p);
 
-   const size_t part_size = len / 3;
+   if(len == 0 || len > p_bits/8)
+      return;
 
    try
       {
-      const BigInt g = BigInt::decode(in, part_size);
-      const BigInt x = BigInt::decode(in + part_size, part_size);
-      const BigInt p = BigInt::decode(in + 2 * (part_size), part_size);
-      const BigInt ref = simple_power_mod(g, x, p);
+      const BigInt g = BigInt::decode(in, len / 2);
+      const BigInt x = BigInt::decode(in + len / 2, len / 2);
+
+      const BigInt ref = simple_power_mod(g, x, p, mod_p);
       const BigInt z = Botan::power_mod(g, x, p);
 
       if(ref != z)
diff --git a/src/extra_tests/fuzzers/jigs/ressol.cpp b/src/extra_tests/fuzzers/jigs/ressol.cpp
index 97130255c..6fbb85690 100644
--- a/src/extra_tests/fuzzers/jigs/ressol.cpp
+++ b/src/extra_tests/fuzzers/jigs/ressol.cpp
@@ -6,44 +6,35 @@
 
 #include "driver.h"
 #include <botan/numthry.h>
+#include <botan/reducer.h>
 
 void fuzz(const uint8_t in[], size_t len)
    {
-   /*
-   * This allows two values (a,p) up to 768 bits in length, which is
-   * sufficient to test ressol (modular square root) for since it is
-   * mostly used for ECC.
-   */
-   if(len % 2 != 0 || len > 2 * (768 / 8))
-      return;
+   // Ressol is mostly used for ECC point decompression so best to test smaller sizes
+   static const size_t p_bits = 256;
+   static const BigInt p = random_prime(fuzzer_rng(), p_bits);
+   static const Modular_Reducer mod_p(p);
 
-   const BigInt a = BigInt::decode(in, len / 2);
-   const BigInt n = BigInt::decode(in + len / 2, len / 2);
+   if(len > p_bits / 8)
+      return;
 
-   try {
-       BigInt a_sqrt = ressol(a, n);
+   try
+      {
+      const BigInt a = BigInt::decode(in, len);
+      BigInt a_sqrt = Botan::ressol(a, p);
 
       if(a_sqrt > 0)
          {
-         /*
-         * If n is not prime then the result of ressol will be bogus. But
-         * this function is exposed to untrusted inputs (via OS2ECP) so
-         * should not hang or crash even with composite modulus.
-         * If the result is incorrect, check if n is a prime: if it is
-         * then z != a is a bug.
-         */
-         BigInt z = (a_sqrt * a_sqrt) % n;
-         BigInt a_redc = a % n;
+         const BigInt a_redc = mod_p.reduce(a);
+         const BigInt z = mod_p.square(a_sqrt);
+
          if(z != a_redc)
             {
-            if(is_prime(n, fuzzer_rng(), 64))
-               {
-               std::cout << "A = " << a << "\n";
-               std::cout << "N = " << n << "\n";
-               std::cout << "Ressol = " << a_sqrt << "\n";
-               std::cout << "recomputed = " << z << "\n";
-               abort();
-               }
+            std::cout << "A = " << a << "\n";
+            std::cout << "P = " << p << "\n";
+            std::cout << "R = " << a_sqrt << "\n";
+            std::cout << "Z = " << z << "\n";
+            abort();
             }
          }
       }