Fix (nearly) infinite loop in RESSOL (modular square root).

It first computed the first i for q**(2**i) == 1, then checked that i
was smaller than s. Given a composite modulus (for which the algorithm
does not work), the loop might do a very large amount of work before
returning the failure.

4 files changed, 56 insertions, 8 deletions

diff --git a/doc/security.rst b/doc/security.rst
index 84d8d49d8..a4aaa5e0d 100644
--- a/doc/security.rst
+++ b/doc/security.rst
@@ -16,6 +16,19 @@ https://keybase.io/jacklloyd and on most PGP keyservers.
 Advisories
 ----------------------------------------
 
+2016
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+* 2016-02-01 (CVE-2016-2194): Infinite loop in modulur square root algorithm
+
+  The ressol function implements the Tonelli-Shanks algorithm for
+  finding square roots could be sent into a nearly infinite loop due
+  to a misplaced conditional check. This could occur if a composite
+  modulus is provided, as this algorithm is only defined for primes.
+  This function is exposed to attacker controlled input via the OS2ECP
+  function during ECC point decompression. Found by AFL
+
+  Introduced in 1.7.15, fixed in 1.11.27
+
 2015
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
diff --git a/src/lib/math/numbertheory/ressol.cpp b/src/lib/math/numbertheory/ressol.cpp
index 834dd94ce..875d054c3 100644
--- a/src/lib/math/numbertheory/ressol.cpp
+++ b/src/lib/math/numbertheory/ressol.cpp
@@ -16,15 +16,17 @@ namespace Botan {
 */
 BigInt ressol(const BigInt& a, const BigInt& p)
    {
-   if(a < 0)
-      throw Invalid_Argument("ressol(): a to solve for must be positive");
-   if(p <= 1)
-      throw Invalid_Argument("ressol(): prime must be > 1");
-
    if(a == 0)
       return 0;
+   else if(a < 0)
+      throw Invalid_Argument("ressol(): a to solve for must be positive");
+
    if(p == 2)
       return a;
+   else if(p <= 1)
+      throw Invalid_Argument("ressol(): prime must be > 1 a");
+   else if(p.is_even())
+      throw Invalid_Argument("ressol(): invalid prime");
 
    if(jacobi(a, p) != 1) // not a quadratic residue
       return -BigInt(1);
@@ -63,10 +65,12 @@ BigInt ressol(const BigInt& a, const BigInt& p)
          {
          q = mod_p.square(q);
          ++i;
-         }
 
-      if(s <= i)
-         return -BigInt(1);
+         if(s >= i)
+            {
+            return -BigInt(1);
+            }
+         }
 
       c = power_mod(c, BigInt::power_of_2(s-i-1), p);
       r = mod_p.multiply(r, c);
diff --git a/src/tests/data/bigint.vec b/src/tests/data/bigint.vec
index bba83deb6..2445c8de4 100644
--- a/src/tests/data/bigint.vec
+++ b/src/tests/data/bigint.vec
@@ -2580,3 +2580,16 @@ IsPrime = 0
 Value = 0x53251
 IsPrime = 0
 
+[RESSOL]
+Input = 5
+Modulus = 11
+Output = 4
+
+Input = 5
+Modulus = 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151
+Output = 5128001483797946816458955548662741861156429216952843873274631897232136999791540518339021539968609345897897688700798659762992302941280478805021587896033442584
+
+# Input and composite modulus which would previously cause a (nearly) infinite loop
+Input = 4
+Modulus = 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057149
+Output = -1
diff --git a/src/tests/test_bigint.cpp b/src/tests/test_bigint.cpp
index e63be6333..33db242aa 100644
--- a/src/tests/test_bigint.cpp
+++ b/src/tests/test_bigint.cpp
@@ -278,6 +278,24 @@ class BigInt_KAT_Tests : public Text_Based_Test
 
             result.test_eq("value", Botan::is_prime(value, Test::rng()), v_is_prime);
             }
+         else if(algo == "RESSOL")
+            {
+            const Botan::BigInt a = get_req_bn(vars, "Input");
+            const Botan::BigInt p = get_req_bn(vars, "Modulus");
+            const Botan::BigInt exp = get_req_bn(vars, "Output");
+
+            const Botan::BigInt a_sqrt = Botan::ressol(a, p);
+
+            result.test_eq("result", a_sqrt, exp);
+
+            if(a_sqrt > 1)
+               {
+               const Botan::BigInt a_sqrt2 = (a_sqrt*a_sqrt) % p;
+               result.test_eq("square correct", a_sqrt2, a);
+               }
+
+            return result;
+            }
          else
             {
             result.test_failure("Unknown BigInt algorithm " + algo);