The branch OpenSSL_1_1_1-stable has been updated via acd9b16b01ad4bda015102d9ce1fa34efa15359d (commit) via d49b8889108c66b43923232a1457e4920270845f (commit) from f7a6d1122befe9cd1d3de70cb2c19595a701b9aa (commit)
- Log ----------------------------------------------------------------- commit acd9b16b01ad4bda015102d9ce1fa34efa15359d Author: Matt Caswell <m...@openssl.org> Date: Wed Mar 6 11:51:28 2019 +0000 Add a test for underflow in ecp_nistp521.c The previous commit fixed an underflow that may occur in ecp_nistp521.c. This commit adds a test for that condition. It is heavily based on an original test harness by Billy Brumley. Reviewed-by: Nicola Tuveri <nic....@gmail.com> (Merged from https://github.com/openssl/openssl/pull/8405) (cherry picked from commit 6855b496b205c067ecb276221c31c6212f4fdbae) commit d49b8889108c66b43923232a1457e4920270845f Author: Matt Caswell <m...@openssl.org> Date: Tue Mar 5 13:26:45 2019 +0000 Avoid an underflow in ecp_nistp521.c The function felem_diff_128_64 in ecp_nistp521.c substracts the number |in| from |out| mod p. In order to avoid underflow it first adds 32p mod p (which is equivalent to 0 mod p) to |out|. The comments and variable naming suggest that the original author intended to add 64p mod p. In fact it has been shown that with certain unusual co-ordinates it is possible to cause an underflow in this function when only adding 32p mod p while performing a point double operation. By changing this to 64p mod p the underflow is avoided. It turns out to be quite difficult to construct points that satisfy the underflow criteria although this has been done and the underflow demonstrated. However none of these points are actually on the curve. Finding points that satisfy the underflow criteria and are also *on* the curve is considered significantly more difficult. For this reason we do not believe that this issue is currently practically exploitable and therefore no CVE has been assigned. This only impacts builds using the enable-ec_nistp_64_gcc_128 Configure option. With thanks to Bo-Yin Yang, Billy Brumley and Dr Liu for their significant help in investigating this issue. Reviewed-by: Nicola Tuveri <nic....@gmail.com> (Merged from https://github.com/openssl/openssl/pull/8405) (cherry picked from commit 13fbce17fc9f02e2401fc3868f3f8e02d6647e5f) ----------------------------------------------------------------------- Summary of changes: crypto/ec/ecp_nistp521.c | 11 +++++--- test/ectest.c | 69 ++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 77 insertions(+), 3 deletions(-) diff --git a/crypto/ec/ecp_nistp521.c b/crypto/ec/ecp_nistp521.c index 2f47772..e31b85c 100644 --- a/crypto/ec/ecp_nistp521.c +++ b/crypto/ec/ecp_nistp521.c @@ -357,10 +357,15 @@ static void felem_diff64(felem out, const felem in) static void felem_diff_128_64(largefelem out, const felem in) { /* - * In order to prevent underflow, we add 0 mod p before subtracting. + * In order to prevent underflow, we add 64p mod p (which is equivalent + * to 0 mod p) before subtracting. p is 2^521 - 1, i.e. in binary a 521 + * digit number with all bits set to 1. See "The representation of field + * elements" comment above for a description of how limbs are used to + * represent a number. 64p is represented with 8 limbs containing a number + * with 58 bits set and one limb with a number with 57 bits set. */ - static const limb two63m6 = (((limb) 1) << 62) - (((limb) 1) << 5); - static const limb two63m5 = (((limb) 1) << 62) - (((limb) 1) << 4); + static const limb two63m6 = (((limb) 1) << 63) - (((limb) 1) << 6); + static const limb two63m5 = (((limb) 1) << 63) - (((limb) 1) << 5); out[0] += two63m6 - in[0]; out[1] += two63m5 - in[1]; diff --git a/test/ectest.c b/test/ectest.c index 2703cb4..afe8615 100644 --- a/test/ectest.c +++ b/test/ectest.c @@ -1403,6 +1403,74 @@ err: BN_CTX_free(ctx); return r; } + +/* + * Tests a point known to cause an incorrect underflow in an old version of + * ecp_nist521.c + */ +static int underflow_test(void) +{ + BN_CTX *ctx = NULL; + EC_GROUP *grp = NULL; + EC_POINT *P = NULL, *Q = NULL, *R = NULL; + BIGNUM *x1 = NULL, *y1 = NULL, *z1 = NULL, *x2 = NULL, *y2 = NULL; + BIGNUM *k = NULL; + int testresult = 0; + const char *x1str = + "1534f0077fffffe87e9adcfe000000000000000000003e05a21d2400002e031b1f4" + "b80000c6fafa4f3c1288798d624a247b5e2ffffffffffffffefe099241900004"; + const char *p521m1 = + "1ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff" + "fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe"; + + ctx = BN_CTX_new(); + if (!TEST_ptr(ctx)) + return 0; + + BN_CTX_start(ctx); + x1 = BN_CTX_get(ctx); + y1 = BN_CTX_get(ctx); + z1 = BN_CTX_get(ctx); + x2 = BN_CTX_get(ctx); + y2 = BN_CTX_get(ctx); + k = BN_CTX_get(ctx); + if (!TEST_ptr(k)) + goto err; + + grp = EC_GROUP_new_by_curve_name(NID_secp521r1); + P = EC_POINT_new(grp); + Q = EC_POINT_new(grp); + R = EC_POINT_new(grp); + if (!TEST_ptr(grp) || !TEST_ptr(P) || !TEST_ptr(Q) || !TEST_ptr(R)) + goto err; + + if (!TEST_int_gt(BN_hex2bn(&x1, x1str), 0) + || !TEST_int_gt(BN_hex2bn(&y1, p521m1), 0) + || !TEST_int_gt(BN_hex2bn(&z1, p521m1), 0) + || !TEST_int_gt(BN_hex2bn(&k, "02"), 0) + || !TEST_true(EC_POINT_set_Jprojective_coordinates_GFp(grp, P, x1, + y1, z1, ctx)) + || !TEST_true(EC_POINT_mul(grp, Q, NULL, P, k, ctx)) + || !TEST_true(EC_POINT_get_affine_coordinates(grp, Q, x1, y1, ctx)) + || !TEST_true(EC_POINT_dbl(grp, R, P, ctx)) + || !TEST_true(EC_POINT_get_affine_coordinates(grp, R, x2, y2, ctx))) + goto err; + + if (!TEST_int_eq(BN_cmp(x1, x2), 0) + || !TEST_int_eq(BN_cmp(y1, y2), 0)) + goto err; + + testresult = 1; + + err: + BN_CTX_end(ctx); + EC_POINT_free(P); + EC_POINT_free(Q); + EC_GROUP_free(grp); + BN_CTX_free(ctx); + + return testresult; +} # endif static const unsigned char p521_named[] = { @@ -1510,6 +1578,7 @@ int setup_tests(void) # endif # ifndef OPENSSL_NO_EC_NISTP_64_GCC_128 ADD_ALL_TESTS(nistp_single_test, OSSL_NELEM(nistp_tests_params)); + ADD_TEST(underflow_test); # endif ADD_ALL_TESTS(internal_curve_test, crv_len); ADD_ALL_TESTS(internal_curve_test_method, crv_len);