From c11d372b3b7080dc153902f14a0d4b402e2dfc92 Mon Sep 17 00:00:00 2001
From: Billy Brumley <bbrumley@gmail.com>
Date: Fri, 27 Apr 2018 17:45:51 +0300
Subject: [PATCH] make EC_GROUP_do_inverse_ord more robust

Reviewed-by: Andy Polyakov <appro@openssl.org>
Reviewed-by: Matt Caswell <matt@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/6116)
---
 crypto/ec/ec_lib.c     | 69 +++++++++++++++++++++++++++++++++++++++++-
 crypto/ec/ecdsa_ossl.c | 41 +++++--------------------
 2 files changed, 75 insertions(+), 35 deletions(-)

diff --git a/crypto/ec/ec_lib.c b/crypto/ec/ec_lib.c
index d0393e8bad..76f05a040a 100644
--- a/crypto/ec/ec_lib.c
+++ b/crypto/ec/ec_lib.c
@@ -1017,13 +1017,80 @@ int ec_group_simple_order_bits(const EC_GROUP *group)
     return BN_num_bits(group->order);
 }
 
+static int ec_field_inverse_mod_ord(const EC_GROUP *group, BIGNUM *r,
+                                    BIGNUM *x, BN_CTX *ctx)
+{
+    BIGNUM *exp = NULL;
+    BN_CTX *new_ctx = NULL;
+    int ret = 0;
+
+    if (ctx == NULL && (ctx = new_ctx = BN_CTX_secure_new()) == NULL)
+        return 0;
+
+    BN_CTX_start(ctx);
+    exp = BN_CTX_get(ctx);
+    if (exp == 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(exp, 2))
+            goto err;
+        if (!BN_sub(exp, group->order, exp))
+            goto err;
+        /*-
+         * Exponent X is public.
+         * No need for scatter-gather or BN_FLG_CONSTTIME.
+         */
+        if (!BN_mod_exp_mont(r, x, exp, group->order, ctx, group->mont_data))
+            goto err;
+        /* Inverse of zero doesn't exist. Let the fallback catch it. */
+        if (BN_is_zero(r))
+            ret = 0;
+        else
+            ret = 1;
+    }
+
+    /*-
+     * Fallback to classic inverse, blinded.
+     * BN_FLG_CONSTTIME is a don't care here.
+     */
+    if (ret == 0) {
+        do {
+            if (!BN_priv_rand_range(exp, group->order))
+            goto err;
+        } while (BN_is_zero(exp));
+
+        /* r := x * exp */
+        if (!BN_mod_mul(r, x, exp, group->order, ctx))
+            goto err;
+        /* r := 1/(x * exp) */
+        if (!BN_mod_inverse(r, r, group->order, ctx))
+            goto err;
+        /* r := exp/(x * exp) = 1/x */
+        if (!BN_mod_mul(r, r, exp, group->order, ctx))
+            goto err;
+
+        ret = 1;
+    }
+
+ err:
+    BN_CTX_end(ctx);
+    BN_CTX_free(new_ctx);
+    return ret;
+}
+
 int EC_GROUP_do_inverse_ord(const EC_GROUP *group, BIGNUM *res,
                             BIGNUM *x, BN_CTX *ctx)
 {
     if (group->meth->field_inverse_mod_ord != NULL)
         return group->meth->field_inverse_mod_ord(group, res, x, ctx);
     else
-        return 0;
+        return ec_field_inverse_mod_ord(group, res, x, ctx);
 }
 
 /*-
diff --git a/crypto/ec/ecdsa_ossl.c b/crypto/ec/ecdsa_ossl.c
index cdd0cf0228..f7f80b3a2b 100644
--- a/crypto/ec/ecdsa_ossl.c
+++ b/crypto/ec/ecdsa_ossl.c
@@ -136,34 +136,10 @@ static int ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in,
     }
     while (BN_is_zero(r));
 
-    /* Check if optimized inverse is implemented */
-    if (EC_GROUP_do_inverse_ord(group, k, k, ctx) == 0) {
-        /* compute the inverse of k */
-        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(X, 2)) {
-                ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB);
-                goto err;
-            }
-            if (!BN_mod_sub(X, order, X, order, ctx)) {
-                ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB);
-                goto err;
-            }
-            BN_set_flags(X, BN_FLG_CONSTTIME);
-            if (!BN_mod_exp_mont_consttime(k, k, X, order, ctx,
-                                           group->mont_data)) {
-                ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB);
-                goto err;
-            }
-        } else {
-            if (!BN_mod_inverse(k, k, order, ctx)) {
-                ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB);
-                goto err;
-            }
-        }
+    /* compute the inverse of k */
+    if (!EC_GROUP_do_inverse_ord(group, k, k, ctx)) {
+        ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB);
+        goto err;
     }
 
     /* clear old values if necessary */
@@ -449,12 +425,9 @@ int ossl_ecdsa_verify_sig(const unsigned char *dgst, int dgst_len,
         goto err;
     }
     /* calculate tmp1 = inv(S) mod order */
-    /* Check if optimized inverse is implemented */
-    if (EC_GROUP_do_inverse_ord(group, u2, sig->s, ctx) == 0) {
-        if (!BN_mod_inverse(u2, sig->s, order, ctx)) {
-            ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, ERR_R_BN_LIB);
-            goto err;
-        }
+    if (!EC_GROUP_do_inverse_ord(group, u2, sig->s, ctx)) {
+        ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, ERR_R_BN_LIB);
+        goto err;
     }
     /* digest -> m */
     i = BN_num_bits(order);
-- 
2.25.1