diff options
| -rw-r--r-- | doc/security.rst | 13 | ||||
| -rw-r--r-- | src/lib/math/numbertheory/ressol.cpp | 20 | ||||
| -rw-r--r-- | src/tests/data/bigint.vec | 13 | ||||
| -rw-r--r-- | src/tests/test_bigint.cpp | 18 |
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); |