ec key validation checks updated

Reviewed-by: Nicola Tuveri <nic.tuv@gmail.com>
Reviewed-by: Matt Caswell <matt@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/8564)

2 files changed, 132 insertions, 14 deletions

diff --git a/crypto/ec/ec_key.c b/crypto/ec/ec_key.c
index 416c0e08fc..76aea4f4f6 100644
--- a/crypto/ec/ec_key.c
+++ b/crypto/ec/ec_key.c
@@ -298,6 +298,58 @@ int EC_KEY_check_key(const EC_KEY *eckey)
     return eckey->group->meth->keycheck(eckey);
 }
 
+/*
+ * Check the range of the EC public key.
+ * See SP800-56A R3 Section 5.6.2.3.3 (Part 2)
+ * i.e.
+ *  - If q = odd prime p: Verify that xQ and yQ are integers in the
+ *    interval[0, p − 1], OR
+ *  - If q = 2m: Verify that xQ and yQ are bit strings of length m bits.
+ * Returns 1 if the public key has a valid range, otherwise it returns 0.
+ */
+static int ec_key_public_range_check(BN_CTX *ctx, const EC_KEY *key)
+{
+    int ret = 0;
+    BIGNUM *x, *y;
+
+    BN_CTX_start(ctx);
+    x = BN_CTX_get(ctx);
+    y = BN_CTX_get(ctx);
+    if (y == NULL)
+        goto err;
+
+    if (!EC_POINT_get_affine_coordinates(key->group, key->pub_key, x, y, ctx))
+        goto err;
+
+    if (EC_METHOD_get_field_type(key->group->meth) == NID_X9_62_prime_field) {
+        if (BN_is_negative(x)
+            || BN_cmp(x, key->group->field) >= 0
+            || BN_is_negative(y)
+            || BN_cmp(y, key->group->field) >= 0) {
+            goto err;
+        }
+    } else {
+        int m = EC_GROUP_get_degree(key->group);
+        if (BN_num_bits(x) > m || BN_num_bits(y) > m) {
+            goto err;
+        }
+    }
+    ret = 1;
+err:
+    BN_CTX_end(ctx);
+    return ret;
+}
+
+/*
+ * ECC Key validation as specified in SP800-56A R3.
+ *    Section 5.6.2.3.3 ECC Full Public-Key Validation
+ *    Section 5.6.2.1.2 Owner Assurance of Private-Key Validity
+ *    Section 5.6.2.1.4 Owner Assurance of Pair-wise Consistency
+ * NOTES:
+ *    Before calling this method in fips mode, there should be an assurance that
+ *    an approved elliptic-curve group is used.
+ * Returns 1 if the key is valid, otherwise it returns 0.
+ */
 int ec_key_simple_check_key(const EC_KEY *eckey)
 {
     int ok = 0;
@@ -310,6 +362,7 @@ int ec_key_simple_check_key(const EC_KEY *eckey)
         return 0;
     }
 
+    /* 5.6.2.3.3 (Step 1): Q != infinity */
     if (EC_POINT_is_at_infinity(eckey->group, eckey->pub_key)) {
         ECerr(EC_F_EC_KEY_SIMPLE_CHECK_KEY, EC_R_POINT_AT_INFINITY);
         goto err;
@@ -317,20 +370,28 @@ int ec_key_simple_check_key(const EC_KEY *eckey)
 
     if ((ctx = BN_CTX_new()) == NULL)
         goto err;
+
     if ((point = EC_POINT_new(eckey->group)) == NULL)
         goto err;
 
-    /* testing whether the pub_key is on the elliptic curve */
+    /* 5.6.2.3.3 (Step 2) Test if the public key is in range */
+    if (!ec_key_public_range_check(ctx, eckey)) {
+        ECerr(EC_F_EC_KEY_SIMPLE_CHECK_KEY, EC_R_COORDINATES_OUT_OF_RANGE);
+        goto err;
+    }
+
+    /* 5.6.2.3.3 (Step 3) is the pub_key on the elliptic curve */
     if (EC_POINT_is_on_curve(eckey->group, eckey->pub_key, ctx) <= 0) {
         ECerr(EC_F_EC_KEY_SIMPLE_CHECK_KEY, EC_R_POINT_IS_NOT_ON_CURVE);
         goto err;
     }
-    /* testing whether pub_key * order is the point at infinity */
+
     order = eckey->group->order;
     if (BN_is_zero(order)) {
         ECerr(EC_F_EC_KEY_SIMPLE_CHECK_KEY, EC_R_INVALID_GROUP_ORDER);
         goto err;
     }
+    /* 5.6.2.3.3 (Step 4) : pub_key * order is the point at infinity. */
     if (!EC_POINT_mul(eckey->group, point, NULL, eckey->pub_key, order, ctx)) {
         ECerr(EC_F_EC_KEY_SIMPLE_CHECK_KEY, ERR_R_EC_LIB);
         goto err;
@@ -339,15 +400,21 @@ int ec_key_simple_check_key(const EC_KEY *eckey)
         ECerr(EC_F_EC_KEY_SIMPLE_CHECK_KEY, EC_R_WRONG_ORDER);
         goto err;
     }
-    /*
-     * in case the priv_key is present : check if generator * priv_key ==
-     * pub_key
-     */
+
     if (eckey->priv_key != NULL) {
-        if (BN_cmp(eckey->priv_key, order) >= 0) {
+        /*
+         * 5.6.2.1.2 Owner Assurance of Private-Key Validity
+         * The private key is in the range [1, order-1]
+         */
+        if (BN_cmp(eckey->priv_key, BN_value_one()) < 0
+                || BN_cmp(eckey->priv_key, order) >= 0) {
             ECerr(EC_F_EC_KEY_SIMPLE_CHECK_KEY, EC_R_WRONG_ORDER);
             goto err;
         }
+        /*
+         * Section 5.6.2.1.4 Owner Assurance of Pair-wise Consistency (b)
+         * Check if generator * priv_key = pub_key
+         */
         if (!EC_POINT_mul(eckey->group, point, eckey->priv_key,
                           NULL, NULL, ctx)) {
             ECerr(EC_F_EC_KEY_SIMPLE_CHECK_KEY, ERR_R_EC_LIB);
@@ -399,12 +466,10 @@ int EC_KEY_set_public_key_affine_coordinates(EC_KEY *key, BIGNUM *x,
         goto err;
 
     /*
-     * Check if retrieved coordinates match originals and are less than field
-     * order: if not values are out of range.
+     * Check if retrieved coordinates match originals. The range check is done
+     * inside EC_KEY_check_key().
      */
-    if (BN_cmp(x, tx) || BN_cmp(y, ty)
-        || (BN_cmp(x, key->group->field) >= 0)
-        || (BN_cmp(y, key->group->field) >= 0)) {
+    if (BN_cmp(x, tx) || BN_cmp(y, ty)) {
         ECerr(EC_F_EC_KEY_SET_PUBLIC_KEY_AFFINE_COORDINATES,
               EC_R_COORDINATES_OUT_OF_RANGE);
         goto err;
diff --git a/test/ectest.c b/test/ectest.c
index 7236b43bd1..ab75acea1b 100644
--- a/test/ectest.c
+++ b/test/ectest.c
@@ -1855,7 +1855,59 @@ err:
     OPENSSL_free(buf);
     return r;
 }
-#endif
+
+static int check_ec_key_field_public_range_test(int id)
+{
+    int ret = 0, type = 0;
+    const EC_POINT *pub = NULL;
+    const EC_GROUP *group = NULL;
+    const EC_METHOD *meth = NULL;
+    const BIGNUM *field = NULL;
+    BIGNUM *x = NULL, *y = NULL;
+    EC_KEY *key = NULL;
+
+    if (!(TEST_ptr(x = BN_new())
+          && TEST_ptr(y = BN_new())
+          && TEST_ptr(key = EC_KEY_new_by_curve_name(curves[id].nid))
+          && TEST_ptr(group = EC_KEY_get0_group(key))
+          && TEST_ptr(meth = EC_GROUP_method_of(group))
+          && TEST_ptr(field = EC_GROUP_get0_field(group))
+          && TEST_int_gt(EC_KEY_generate_key(key), 0)
+          && TEST_int_gt(EC_KEY_check_key(key), 0)
+          && TEST_ptr(pub = EC_KEY_get0_public_key(key))
+          && TEST_int_gt(EC_POINT_get_affine_coordinates(group, pub, x, y,
+                                                         NULL), 0)))
+        goto err;
+
+    /*
+     * Make the public point out of range by adding the field (which will still
+     * be the same point on the curve). The add is different for char2 fields.
+     */
+    type = EC_METHOD_get_field_type(meth);
+    if (type == NID_X9_62_characteristic_two_field) {
+        /* test for binary curves */
+        if (!TEST_true(BN_GF2m_add(x, x, field)))
+            goto err;
+    } else if (type == NID_X9_62_prime_field) {
+        /* test for prime curves */
+        if (!TEST_true(BN_add(x, x, field)))
+            goto err;
+    } else {
+        /* this should never happen */
+        TEST_error("Unsupported EC_METHOD field_type");
+        goto err;
+    }
+    if (!TEST_int_le(EC_KEY_set_public_key_affine_coordinates(key, x, y), 0))
+        goto err;
+
+    ret = 1;
+err:
+    BN_free(x);
+    BN_free(y);
+    EC_KEY_free(key);
+    return ret;
+}
+#endif /* OPENSSL_NO_EC */
 
 int setup_tests(void)
 {
@@ -1880,7 +1932,8 @@ int setup_tests(void)
     ADD_TEST(group_field_test);
     ADD_ALL_TESTS(check_named_curve_test, crv_len);
     ADD_ALL_TESTS(check_named_curve_lookup_test, crv_len);
-#endif
+    ADD_ALL_TESTS(check_ec_key_field_public_range_test, crv_len);
+#endif /* OPENSSL_NO_EC */
     return 1;
 }