Fix heap overflow in ECC point multiplication

If affine coordinates larger than the prime modulus were given,
a later multiplication could overflow the size of an allocated
output buffer, which was sized based on the size of the prime.

This will cause an overflow into either the system heap or if the
mlock/mmap pool allocator is in use, then into the adjacent key
material stored in the pool.

Reported by Alex Gaynor who found it with AFL

Also fix a one word overwrite in P-521 reduction. Found with AFL

7 files changed, 110 insertions, 5 deletions

diff --git a/doc/security.rst b/doc/security.rst
index a4aaa5e0d..2552d6751 100644
--- a/doc/security.rst
+++ b/doc/security.rst
@@ -18,6 +18,39 @@ Advisories
 
 2016
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+* 2016-06-01 (CVE-2016-2196): Overwrite in P-521 reduction
+
+  The P-521 reduction function would overwrite zero to one word
+  following the allocated block. This could potentially result
+  in remote code execution or a crash. Found with AFL
+
+* 2016-02-01 (CVE-2016-2195): Heap overflow on invalid ECC point
+
+  The PointGFp constructor did not check that the affine coordinate
+  arguments were less than the prime, but then in curve multiplication
+  assumed that both arguments if multiplied would fit into an integer
+  twice the size of the prime.
+
+  The bigint_mul and bigint_sqr functions received the size of the
+  output buffer, but only used it to dispatch to a faster algorithm in
+  cases where there was sufficient output space to call an unrolled
+  multiplication function.
+
+  The result is a heap overflow accessible via ECC point decoding,
+  which accepted untrusted inputs. This is likely exploitable for
+  remote code execution.
+
+  On systems which use the mlock pool allocator, it would allow an
+  attacker to overwrite memory held in secure_vector objects. After
+  this point the write will hit the guard page at the end of the
+  mmap'ed region so it probably could not be used for code execution
+  directly, but would allow overwriting adjacent key material.
+
+  Found by Alex Gaynor fuzzing with AFL
+
+  Versions affected: all before 1.11.27 and 1.10.11
+
 * 2016-02-01 (CVE-2016-2194): Infinite loop in modulur square root algorithm
 
   The ressol function implements the Tonelli-Shanks algorithm for
@@ -27,7 +60,7 @@ Advisories
   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
+  Versions affected: all before 1.11.27 and 1.10.11
 
 2015
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
diff --git a/src/lib/math/ec_gfp/curve_gfp.cpp b/src/lib/math/ec_gfp/curve_gfp.cpp
index 66614c5c5..52e5b0b56 100644
--- a/src/lib/math/ec_gfp/curve_gfp.cpp
+++ b/src/lib/math/ec_gfp/curve_gfp.cpp
@@ -80,6 +80,12 @@ void CurveGFp_Montgomery::curve_mul(BigInt& z, const BigInt& x, const BigInt& y,
       return;
       }
 
+   const size_t x_sw = x.sig_words();
+   const size_t y_sw = y.sig_words();
+
+   BOTAN_ASSERT(x_sw <= m_p_words, "Input in range");
+   BOTAN_ASSERT(y_sw <= m_p_words, "Input in range");
+
    const size_t output_size = 2*m_p_words + 1;
    ws.resize(2*(m_p_words+2));
 
@@ -87,8 +93,8 @@ void CurveGFp_Montgomery::curve_mul(BigInt& z, const BigInt& x, const BigInt& y,
    z.clear();
 
    bigint_monty_mul(z.mutable_data(), output_size,
-                    x.data(), x.size(), x.sig_words(),
-                    y.data(), y.size(), y.sig_words(),
+                    x.data(), x.size(), x_sw,
+                    y.data(), y.size(), y_sw,
                     m_p.data(), m_p_words, m_p_dash,
                     ws.data());
    }
@@ -102,6 +108,9 @@ void CurveGFp_Montgomery::curve_sqr(BigInt& z, const BigInt& x,
       return;
       }
 
+   const size_t x_sw = x.sig_words();
+   BOTAN_ASSERT(x_sw <= m_p_words, "Input in range");
+
    const size_t output_size = 2*m_p_words + 1;
 
    ws.resize(2*(m_p_words+2));
@@ -110,7 +119,7 @@ void CurveGFp_Montgomery::curve_sqr(BigInt& z, const BigInt& x,
    z.clear();
 
    bigint_monty_sqr(z.mutable_data(), output_size,
-                    x.data(), x.size(), x.sig_words(),
+                    x.data(), x.size(), x_sw,
                     m_p.data(), m_p_words, m_p_dash,
                     ws.data());
    }
diff --git a/src/lib/math/ec_gfp/curve_nistp.cpp b/src/lib/math/ec_gfp/curve_nistp.cpp
index bbc11ff21..6a98d9588 100644
--- a/src/lib/math/ec_gfp/curve_nistp.cpp
+++ b/src/lib/math/ec_gfp/curve_nistp.cpp
@@ -72,7 +72,8 @@ void redc_p521(BigInt& x, secure_vector<word>& ws)
 
    x.mask_bits(521);
 
-   bigint_add3(x.mutable_data(), x.data(), p_words, ws.data(), p_words);
+   word carry = bigint_add3_nc(x.mutable_data(), x.data(), p_words, ws.data(), p_words);
+   BOTAN_ASSERT_EQUAL(carry, 0, "Final final carry in P-521 reduction");
 
    normalize(prime_p521(), x, ws, 1);
    }
diff --git a/src/lib/math/ec_gfp/point_gfp.cpp b/src/lib/math/ec_gfp/point_gfp.cpp
index ca6448782..5e8b3b4ef 100644
--- a/src/lib/math/ec_gfp/point_gfp.cpp
+++ b/src/lib/math/ec_gfp/point_gfp.cpp
@@ -32,6 +32,11 @@ PointGFp::PointGFp(const CurveGFp& curve, const BigInt& x, const BigInt& y) :
    m_coord_y(y),
    m_coord_z(1)
    {
+   if(x <= 0 || x >= curve.get_p())
+      throw Invalid_Argument("Invalid PointGFp affine x");
+   if(y <= 0 || y >= curve.get_p())
+      throw Invalid_Argument("Invalid PointGFp affine y");
+
    m_curve.to_rep(m_coord_x, m_monty_ws);
    m_curve.to_rep(m_coord_y, m_monty_ws);
    m_curve.to_rep(m_coord_z, m_monty_ws);
diff --git a/src/lib/math/mp/mp_karat.cpp b/src/lib/math/mp/mp_karat.cpp
index c7f179191..9135fdd6a 100644
--- a/src/lib/math/mp/mp_karat.cpp
+++ b/src/lib/math/mp/mp_karat.cpp
@@ -256,6 +256,9 @@ void bigint_mul(word z[], size_t z_size, word workspace[],
                 const word x[], size_t x_size, size_t x_sw,
                 const word y[], size_t y_size, size_t y_sw)
    {
+   // checking that z_size >= x_sw + y_sw without overflow
+   BOTAN_ASSERT(z_size > x_sw && z_size > y_sw && z_size-x_sw >= y_sw, "Output size is sufficient");
+
    if(x_sw == 1)
       {
       bigint_linmul3(z, y, y_sw, x[0]);
@@ -312,6 +315,8 @@ void bigint_mul(word z[], size_t z_size, word workspace[],
 void bigint_sqr(word z[], size_t z_size, word workspace[],
                 const word x[], size_t x_size, size_t x_sw)
    {
+   BOTAN_ASSERT(z_size/2 >= x_sw, "Output size is sufficient");
+
    if(x_sw == 1)
       {
       bigint_linmul3(z, x, x_sw, x[0]);
diff --git a/src/tests/data/fuzz/pkcs8/ecc_overflow.pem b/src/tests/data/fuzz/pkcs8/ecc_overflow.pem
new file mode 100644
index 000000000..3b52a3ee0
--- /dev/null
+++ b/src/tests/data/fuzz/pkcs8/ecc_overflow.pem
@@ -0,0 +1,11 @@
+-----BEGIN PRIVATE KEY-----
+MIIBjQIBADCCAU0GByqGSM49AgEwggFAAgEBMDwGByqGSM49AQECMQCMuR6Cozht
+KA9db35Q5kHfFS9xCe1UVrQSsdoZf7cRI6zTpymQHRpxh0cAEzEH7FMwZAQwe8OC
+xj2MFQw8cggKzgWvoMK+oo5PsieHE5Fl77qR+Q+KpYFKUDrU6wSox90izigmBDAE
+qMfdIs4oJos5tVQW8ER8L7d94Qfc0qYuiA6lPuti1Xy0OQKV28mUOreGlvpQTBEE
+YQPdHGTwaM9F/6KmOoG3wT9riEej537xT+Pbf8r+DL0Q6Ogm4DQ21kaq74ey4kfU
+rx6Kvh11IPnCpFyx646Vz9VSYrcLKf7sWGThnAVP+ZEpKA5GRiF3kYERQoIDQSY8
+UxUCMQCMuR6CozhtKA9db35Q5kHfFS9xCe1UVrMfFm5srAQlp886tq9rf8MQO4gy
+AukEZWUCAQEENzA1AgEBBDB5HVMmAiyXDGqBKoKEHNIk02EMVKKdHqXG6kDInWC/
+R4ZVuXK3T8DqJrRX7RHxndk=
+-----END PRIVATE KEY-----
diff --git a/src/tests/test_fuzzer.cpp b/src/tests/test_fuzzer.cpp
index 3a5dcc47c..18516a68c 100644
--- a/src/tests/test_fuzzer.cpp
+++ b/src/tests/test_fuzzer.cpp
@@ -14,6 +14,10 @@
   #include <botan/internal/filesystem.h>
 #endif
 
+#if defined(BOTAN_HAS_PUBLIC_KEY_CRYPTO)
+  #include <botan/pkcs8.h>
+#endif
+
 namespace Botan_Tests {
 
 namespace {
@@ -27,11 +31,48 @@ class Fuzzer_Input_Tests : public Test
 #if defined(BOTAN_HAS_X509_CERTIFICATES)
          results.push_back(test_x509_fuzz());
 #endif
+
+#if defined(BOTAN_HAS_PUBLIC_KEY_CRYPTO)
+         results.push_back(test_pkcs8());
+#endif
          return results;
          }
 
    private:
 
+#if defined(BOTAN_HAS_PUBLIC_KEY_CRYPTO)
+      Test::Result test_pkcs8()
+         {
+         std::vector<std::string> files;
+
+         Test::Result result("PKCS #8 fuzzing");
+
+         try
+            {
+            files = Botan::get_files_recursive(Test::data_dir() + "/fuzz/pkcs8");
+            }
+         catch(Botan::No_Filesystem_Access)
+            {
+            result.note_missing("Filesystem readdir wrapper not implemented");
+            return result;
+            }
+
+         for(auto vec_file: files)
+            {
+            try
+               {
+               std::unique_ptr<Botan::Private_Key> key(Botan::PKCS8::load_key(vec_file, Test::rng()));
+               Botan::X509_Certificate cert(vec_file);
+               }
+            catch(std::exception&) {}
+
+            result.test_success();
+            }
+
+         return result;
+         }
+#endif
+
 #if defined(BOTAN_HAS_X509_CERTIFICATES)
       Test::Result test_x509_fuzz()
          {