[crypto/ec] default to FLT or error

Reviewed-by: Andy Polyakov <appro@openssl.org>
Reviewed-by: Matt Caswell <matt@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/6116)

4 files changed, 41 insertions, 35 deletions

diff --git a/crypto/ec/ec_lcl.h b/crypto/ec/ec_lcl.h
index 006e3b6e16..cf29c7c70e 100644
--- a/crypto/ec/ec_lcl.h
+++ b/crypto/ec/ec_lcl.h
@@ -174,8 +174,8 @@ struct ec_method_st {
     int (*ecdh_compute_key)(unsigned char **pout, size_t *poutlen,
                             const EC_POINT *pub_key, const EC_KEY *ecdh);
     /* Inverse modulo order */
-    int (*field_inverse_mod_ord)(const EC_GROUP *, BIGNUM *r, BIGNUM *x,
-                                 BN_CTX *ctx);
+    int (*field_inverse_mod_ord)(const EC_GROUP *, BIGNUM *r,
+                                 const BIGNUM *x, BN_CTX *);
     int (*blind_coordinates)(const EC_GROUP *group, EC_POINT *p, BN_CTX *ctx);
 };
 
@@ -636,7 +636,7 @@ int X25519(uint8_t out_shared_key[32], const uint8_t private_key[32],
 void X25519_public_from_private(uint8_t out_public_value[32],
                                 const uint8_t private_key[32]);
 
-int EC_GROUP_do_inverse_ord(const EC_GROUP *group, BIGNUM *res,
-                            BIGNUM *x, BN_CTX *ctx);
+int ec_group_do_inverse_ord(const EC_GROUP *group, BIGNUM *res,
+                            const BIGNUM *x, BN_CTX *ctx);
 
 int ec_point_blind_coordinates(const EC_GROUP *group, EC_POINT *p, BN_CTX *ctx);
diff --git a/crypto/ec/ec_lib.c b/crypto/ec/ec_lib.c
index 883284b304..6a2d1b5800 100644
--- a/crypto/ec/ec_lib.c
+++ b/crypto/ec/ec_lib.c
@@ -1018,12 +1018,15 @@ int ec_group_simple_order_bits(const EC_GROUP *group)
 }
 
 static int ec_field_inverse_mod_ord(const EC_GROUP *group, BIGNUM *r,
-                                    BIGNUM *x, BN_CTX *ctx)
+                                    const BIGNUM *x, BN_CTX *ctx)
 {
     BIGNUM *e = NULL;
     BN_CTX *new_ctx = NULL;
     int ret = 0;
 
+    if (group->mont_data == NULL)
+        return 0;
+
     if (ctx == NULL && (ctx = new_ctx = BN_CTX_secure_new()) == NULL)
         return 0;
 
@@ -1031,32 +1034,22 @@ static int ec_field_inverse_mod_ord(const EC_GROUP *group, BIGNUM *r,
     if ((e = BN_CTX_get(ctx)) == NULL)
         goto err;
 
-    /* Check if optimized inverse is implemented */
-    if (group->mont_data != NULL) {
-        /*-
-         * We want inverse in constant time, therefore we utilize the fact
-         * order must be prime and use Fermats Little Theorem instead.
-         */
-        if (!BN_set_word(e, 2))
-            goto err;
-        if (!BN_sub(e, group->order, e))
-            goto err;
-        /*-
-         * Exponent e is public.
-         * No need for scatter-gather or BN_FLG_CONSTTIME.
-         */
-        if (!BN_mod_exp_mont(r, x, e, group->order, ctx, group->mont_data))
-            goto err;
-        /* Inverse of zero doesn't exist. Let the fallback catch it. */
-        ret = (BN_is_zero(r)) ? 0 : 1;
-    }
+    /*-
+     * We want inverse in constant time, therefore we utilize the fact
+     * order must be prime and use Fermats Little Theorem instead.
+     */
+    if (!BN_set_word(e, 2))
+        goto err;
+    if (!BN_sub(e, group->order, e))
+        goto err;
+    /*-
+     * Exponent e is public.
+     * No need for scatter-gather or BN_FLG_CONSTTIME.
+     */
+    if (!BN_mod_exp_mont(r, x, e, group->order, ctx, group->mont_data))
+        goto err;
 
-    /* Fallback to classic inverse */
-    if (ret == 0) {
-        if (!BN_mod_inverse(r, x, group->order, ctx))
-            goto err;
-        ret = 1;
-    }
+    ret = 1;
 
  err:
     if (ctx != NULL)
@@ -1065,8 +1058,21 @@ static int ec_field_inverse_mod_ord(const EC_GROUP *group, BIGNUM *r,
     return ret;
 }
 
-int EC_GROUP_do_inverse_ord(const EC_GROUP *group, BIGNUM *res,
-                            BIGNUM *x, BN_CTX *ctx)
+/*-
+ * Default behavior, if group->meth->field_inverse_mod_ord is NULL:
+ * - When group->order is even, this function returns an error.
+ * - When group->order is otherwise composite, the correctness
+ *   of the output is not guaranteed.
+ * - When x is outside the range [1, group->order), the correctness
+ *   of the output is not guaranteed.
+ * - Otherwise, this function returns the multiplicative inverse in the
+ *   range [1, group->order).
+ *
+ * EC_METHODs must implement their own field_inverse_mod_ord for
+ * other functionality.
+ */
+int ec_group_do_inverse_ord(const EC_GROUP *group, BIGNUM *res,
+                            const BIGNUM *x, BN_CTX *ctx)
 {
     if (group->meth->field_inverse_mod_ord != NULL)
         return group->meth->field_inverse_mod_ord(group, res, x, ctx);
diff --git a/crypto/ec/ecdsa_ossl.c b/crypto/ec/ecdsa_ossl.c
index f7f80b3a2b..277ac16bdf 100644
--- a/crypto/ec/ecdsa_ossl.c
+++ b/crypto/ec/ecdsa_ossl.c
@@ -137,7 +137,7 @@ static int ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in,
     while (BN_is_zero(r));
 
     /* compute the inverse of k */
-    if (!EC_GROUP_do_inverse_ord(group, k, k, ctx)) {
+    if (!ec_group_do_inverse_ord(group, k, k, ctx)) {
         ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB);
         goto err;
     }
@@ -425,7 +425,7 @@ int ossl_ecdsa_verify_sig(const unsigned char *dgst, int dgst_len,
         goto err;
     }
     /* calculate tmp1 = inv(S) mod order */
-    if (!EC_GROUP_do_inverse_ord(group, u2, sig->s, ctx)) {
+    if (!ec_group_do_inverse_ord(group, u2, sig->s, ctx)) {
         ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, ERR_R_BN_LIB);
         goto err;
     }
diff --git a/crypto/ec/ecp_nistz256.c b/crypto/ec/ecp_nistz256.c
index 02925616b1..045c2e71fb 100644
--- a/crypto/ec/ecp_nistz256.c
+++ b/crypto/ec/ecp_nistz256.c
@@ -1512,7 +1512,7 @@ void ecp_nistz256_ord_sqr_mont(BN_ULONG res[P256_LIMBS],
                                int rep);
 
 static int ecp_nistz256_inv_mod_ord(const EC_GROUP *group, BIGNUM *r,
-                                    BIGNUM *x, BN_CTX *ctx)
+                                    const BIGNUM *x, BN_CTX *ctx)
 {
     /* RR = 2^512 mod ord(p256) */
     static const BN_ULONG RR[P256_LIMBS]  = {