From bd2f3df2316b4f99143ef244d847c72101e6b7ab Mon Sep 17 00:00:00 2001 From: Jack Lloyd Date: Fri, 29 Jan 2016 14:57:10 -0500 Subject: 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 --- doc/security.rst | 35 ++++++++++++++++++++++++- src/lib/math/ec_gfp/curve_gfp.cpp | 15 ++++++++--- src/lib/math/ec_gfp/curve_nistp.cpp | 3 ++- src/lib/math/ec_gfp/point_gfp.cpp | 5 ++++ src/lib/math/mp/mp_karat.cpp | 5 ++++ src/tests/data/fuzz/pkcs8/ecc_overflow.pem | 11 ++++++++ src/tests/test_fuzzer.cpp | 41 ++++++++++++++++++++++++++++++ 7 files changed, 110 insertions(+), 5 deletions(-) create mode 100644 src/tests/data/fuzz/pkcs8/ecc_overflow.pem 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& 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 #endif +#if defined(BOTAN_HAS_PUBLIC_KEY_CRYPTO) + #include +#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 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 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() { -- cgit v1.2.3