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 <rsalz@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/5779)

diff --git a/crypto/ec/ecp_nistp224.c b/crypto/ec/ecp_nistp224.c
index 4ece15c952c9c393130aa6a4983611e13e9bf731..346f84dcde2ed37bacc28f268c980349ad4d0dbe 100644 (file)
--- 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 66d84a75cd789265bdc45074d47d73cf0eae3ad0..1c31cce8d6c17cc086d16e4ddcd5a62f5470e9da 100644 (file)
--- 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);