From dc55e4f70f401c5869410d6a0c068c18c3fd53ec Mon Sep 17 00:00:00 2001 From: David Benjamin Date: Wed, 28 Mar 2018 12:21:45 -0400 Subject: [PATCH] Fix a bug in ecp_nistp224.c. felem_neg does not produce an output within the tight bounds suitable for felem_contract. This affects build configurations which set enable-ec_nistp_64_gcc_128. point_double and point_add, in the non-z*_is_zero cases, tolerate and fix up the wider bounds, so this only affects point_add calls where the other point is infinity. Thus it only affects the final addition in arbitrary-point multiplication, giving the wrong y-coordinate. This is a no-op for ECDH and ECDSA, which only use the x-coordinate of arbitrary-point operations. Note: ecp_nistp521.c has the same issue in that the documented preconditions are violated by the test case. I have not addressed this in this PR. ecp_nistp521.c does not immediately produce the wrong answer; felem_contract there appears to be a bit more tolerant than its documented preconditions. However, I haven't checked the point_add property above holds. ecp_nistp521.c should either get this same fix, to be conservative, or have the bounds analysis and comments reworked for the wider bounds. Reviewed-by: Rich Salz (Merged from https://github.com/openssl/openssl/pull/5779) --- crypto/ec/ecp_nistp224.c | 28 ++++++++++++---------------- test/ectest.c | 9 +++++++++ 2 files changed, 21 insertions(+), 16 deletions(-) diff --git a/crypto/ec/ecp_nistp224.c b/crypto/ec/ecp_nistp224.c index 4ece15c952..346f84dcde 100644 --- a/crypto/ec/ecp_nistp224.c +++ b/crypto/ec/ecp_nistp224.c @@ -395,22 +395,6 @@ static void felem_sum(felem out, const felem in) out[3] += in[3]; } -/* Get negative value: out = -in */ -/* Assumes in[i] < 2^57 */ -static void felem_neg(felem out, const felem in) -{ - static const limb two58p2 = (((limb) 1) << 58) + (((limb) 1) << 2); - static const limb two58m2 = (((limb) 1) << 58) - (((limb) 1) << 2); - static const limb two58m42m2 = (((limb) 1) << 58) - - (((limb) 1) << 42) - (((limb) 1) << 2); - - /* Set to 0 mod 2^224-2^96+1 to ensure out > in */ - out[0] = two58p2 - in[0]; - out[1] = two58m42m2 - in[1]; - out[2] = two58m2 - in[2]; - out[3] = two58m2 - in[3]; -} - /* Subtract field elements: out -= in */ /* Assumes in[i] < 2^57 */ static void felem_diff(felem out, const felem in) @@ -679,6 +663,18 @@ static void felem_contract(felem out, const felem in) out[3] = tmp[3]; } +/* + * Get negative value: out = -in + * Requires in[i] < 2^63, + * ensures out[0] < 2^56, out[1] < 2^56, out[2] < 2^56, out[3] <= 2^56 + 2^16 + */ +static void felem_neg(felem out, const felem in) +{ + widefelem tmp = {0}; + felem_diff_128_64(tmp, in); + felem_reduce(out, tmp); +} + /* * Zero-check: returns 1 if input is 0, and 0 otherwise. We know that field * elements are reduced to in < 2^225, so we only need to check three cases: diff --git a/test/ectest.c b/test/ectest.c index 66d84a75cd..1c31cce8d6 100644 --- a/test/ectest.c +++ b/test/ectest.c @@ -1377,6 +1377,15 @@ static int nistp_single_test(int idx) if (!TEST_int_eq(0, EC_POINT_cmp(NISTP, Q, Q_CHECK, ctx))) goto err; + /* regression test for felem_neg bug */ + if (!TEST_true(BN_set_word(m, 32)) + || !TEST_true(BN_set_word(n, 31)) + || !TEST_true(EC_POINT_copy(P, G)) + || !TEST_true(EC_POINT_invert(NISTP, P, ctx)) + || !TEST_true(EC_POINT_mul(NISTP, Q, m, P, n, ctx)) + || !TEST_int_eq(0, EC_POINT_cmp(NISTP, Q, G, ctx))) + goto err; + r = group_order_tests(NISTP); err: EC_GROUP_free(NISTP); -- 2.25.1