SCA hardening for mod. field inversion in EC_GROUP

This commit adds a dedicated function in `EC_METHOD` to access a modular
field inversion implementation suitable for the specifics of the
implemented curve, featuring SCA countermeasures.

The new pointer is defined as:
`int (*field_inv)(const EC_GROUP*, BIGNUM *r, const BIGNUM *a, BN_CTX*)`
and computes the multiplicative inverse of `a` in the underlying field,
storing the result in `r`.

Three implementations are included, each including specific SCA
countermeasures:
  - `ec_GFp_simple_field_inv()`, featuring SCA hardening through
    blinding.
  - `ec_GFp_mont_field_inv()`, featuring SCA hardening through Fermat's
    Little Theorem (FLT) inversion.
  - `ec_GF2m_simple_field_inv()`, that uses `BN_GF2m_mod_inv()` which
    already features SCA hardening through blinding.

From a security point of view, this also helps addressing a leakage
previously affecting conversions from projective to affine coordinates.

This commit also adds a new error reason code (i.e.,
`EC_R_CANNOT_INVERT`) to improve consistency between the three
implementations as all of them could fail for the same reason but
through different code paths resulting in inconsistent error stack
states.

Co-authored-by: Nicola Tuveri <nic.tuv@gmail.com>

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

11 files changed, 141 insertions, 4 deletions

diff --git a/crypto/ec/ec2_smpl.c b/crypto/ec/ec2_smpl.c
index f9d7d0860a..7bd2a63203 100644
--- a/crypto/ec/ec2_smpl.c
+++ b/crypto/ec/ec2_smpl.c
@@ -810,7 +810,7 @@ int ec_GF2m_simple_ladder_post(const EC_GROUP *group,
         || !group->meth->field_mul(group, t2, t2, t0, ctx)
         || !BN_GF2m_add(t1, t2, t1)
         || !group->meth->field_mul(group, t2, p->X, t0, ctx)
-        || !BN_GF2m_mod_inv(t2, t2, group->field, ctx)
+        || !group->meth->field_inv(group, t2, t2, ctx)
         || !group->meth->field_mul(group, t1, t1, t2, ctx)
         || !group->meth->field_mul(group, r->X, r->Z, t2, ctx)
         || !BN_GF2m_add(t2, p->X, r->X)
@@ -889,6 +889,21 @@ int ec_GF2m_simple_points_mul(const EC_GROUP *group, EC_POINT *r,
     return ret;
 }
 
+/*-
+ * Computes the multiplicative inverse of a in GF(2^m), storing the result in r.
+ * If a is zero (or equivalent), you'll get a EC_R_CANNOT_INVERT error.
+ * SCA hardening is with blinding: BN_GF2m_mod_inv does that.
+ */
+static int ec_GF2m_simple_field_inv(const EC_GROUP *group, BIGNUM *r,
+                                    const BIGNUM *a, BN_CTX *ctx)
+{
+    int ret;
+
+    if (!(ret = BN_GF2m_mod_inv(r, a, group->field, ctx)))
+        ECerr(EC_F_EC_GF2M_SIMPLE_FIELD_INV, EC_R_CANNOT_INVERT);
+    return ret;
+}
+
 const EC_METHOD *EC_GF2m_simple_method(void)
 {
     static const EC_METHOD ret = {
@@ -929,6 +944,7 @@ const EC_METHOD *EC_GF2m_simple_method(void)
         ec_GF2m_simple_field_mul,
         ec_GF2m_simple_field_sqr,
         ec_GF2m_simple_field_div,
+        ec_GF2m_simple_field_inv,
         0, /* field_encode */
         0, /* field_decode */
         0, /* field_set_to_one */
diff --git a/crypto/ec/ec_err.c b/crypto/ec/ec_err.c
index 1ede7c2e35..b7cf95bdd8 100644
--- a/crypto/ec/ec_err.c
+++ b/crypto/ec/ec_err.c
@@ -1,6 +1,6 @@
 /*
  * Generated by util/mkerr.pl DO NOT EDIT
- * Copyright 1995-2018 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright 1995-2019 The OpenSSL Project Authors. All Rights Reserved.
  *
  * Licensed under the Apache License 2.0 (the "License").  You may not use
  * this file except in compliance with the License.  You can obtain a copy
@@ -66,6 +66,8 @@ static const ERR_STRING_DATA EC_str_functs[] = {
      "ec_asn1_group2fieldid"},
     {ERR_PACK(ERR_LIB_EC, EC_F_EC_GF2M_MONTGOMERY_POINT_MULTIPLY, 0),
      "ec_GF2m_montgomery_point_multiply"},
+    {ERR_PACK(ERR_LIB_EC, EC_F_EC_GF2M_SIMPLE_FIELD_INV, 0),
+     "ec_GF2m_simple_field_inv"},
     {ERR_PACK(ERR_LIB_EC, EC_F_EC_GF2M_SIMPLE_GROUP_CHECK_DISCRIMINANT, 0),
      "ec_GF2m_simple_group_check_discriminant"},
     {ERR_PACK(ERR_LIB_EC, EC_F_EC_GF2M_SIMPLE_GROUP_SET_CURVE, 0),
@@ -90,6 +92,8 @@ static const ERR_STRING_DATA EC_str_functs[] = {
      "ec_GFp_mont_field_decode"},
     {ERR_PACK(ERR_LIB_EC, EC_F_EC_GFP_MONT_FIELD_ENCODE, 0),
      "ec_GFp_mont_field_encode"},
+    {ERR_PACK(ERR_LIB_EC, EC_F_EC_GFP_MONT_FIELD_INV, 0),
+     "ec_GFp_mont_field_inv"},
     {ERR_PACK(ERR_LIB_EC, EC_F_EC_GFP_MONT_FIELD_MUL, 0),
      "ec_GFp_mont_field_mul"},
     {ERR_PACK(ERR_LIB_EC, EC_F_EC_GFP_MONT_FIELD_SET_TO_ONE, 0),
@@ -124,6 +128,8 @@ static const ERR_STRING_DATA EC_str_functs[] = {
      "ec_GFp_nist_group_set_curve"},
     {ERR_PACK(ERR_LIB_EC, EC_F_EC_GFP_SIMPLE_BLIND_COORDINATES, 0),
      "ec_GFp_simple_blind_coordinates"},
+    {ERR_PACK(ERR_LIB_EC, EC_F_EC_GFP_SIMPLE_FIELD_INV, 0),
+     "ec_GFp_simple_field_inv"},
     {ERR_PACK(ERR_LIB_EC, EC_F_EC_GFP_SIMPLE_GROUP_CHECK_DISCRIMINANT, 0),
      "ec_GFp_simple_group_check_discriminant"},
     {ERR_PACK(ERR_LIB_EC, EC_F_EC_GFP_SIMPLE_GROUP_SET_CURVE, 0),
@@ -287,6 +293,7 @@ static const ERR_STRING_DATA EC_str_reasons[] = {
     {ERR_PACK(ERR_LIB_EC, 0, EC_R_BAD_SIGNATURE), "bad signature"},
     {ERR_PACK(ERR_LIB_EC, 0, EC_R_BIGNUM_OUT_OF_RANGE), "bignum out of range"},
     {ERR_PACK(ERR_LIB_EC, 0, EC_R_BUFFER_TOO_SMALL), "buffer too small"},
+    {ERR_PACK(ERR_LIB_EC, 0, EC_R_CANNOT_INVERT), "cannot invert"},
     {ERR_PACK(ERR_LIB_EC, 0, EC_R_COORDINATES_OUT_OF_RANGE),
     "coordinates out of range"},
     {ERR_PACK(ERR_LIB_EC, 0, EC_R_CURVE_DOES_NOT_SUPPORT_ECDH),
diff --git a/crypto/ec/ec_lcl.h b/crypto/ec/ec_lcl.h
index 3153e4fa0d..312b538991 100644
--- a/crypto/ec/ec_lcl.h
+++ b/crypto/ec/ec_lcl.h
@@ -154,6 +154,13 @@ struct ec_method_st {
     int (*field_sqr) (const EC_GROUP *, BIGNUM *r, const BIGNUM *a, BN_CTX *);
     int (*field_div) (const EC_GROUP *, BIGNUM *r, const BIGNUM *a,
                       const BIGNUM *b, BN_CTX *);
+    /*-
+     * 'field_inv' computes the multipicative inverse of a in the field,
+     * storing the result in r.
+     *
+     * If 'a' is zero (or equivalent), you'll get an EC_R_CANNOT_INVERT error.
+     */
+    int (*field_inv) (const EC_GROUP *, BIGNUM *r, const BIGNUM *a, BN_CTX *);
     /* e.g. to Montgomery */
     int (*field_encode) (const EC_GROUP *, BIGNUM *r, const BIGNUM *a,
                          BN_CTX *);
@@ -390,6 +397,8 @@ int ec_GFp_simple_field_mul(const EC_GROUP *, BIGNUM *r, const BIGNUM *a,
                             const BIGNUM *b, BN_CTX *);
 int ec_GFp_simple_field_sqr(const EC_GROUP *, BIGNUM *r, const BIGNUM *a,
                             BN_CTX *);
+int ec_GFp_simple_field_inv(const EC_GROUP *, BIGNUM *r, const BIGNUM *a,
+                            BN_CTX *);
 int ec_GFp_simple_blind_coordinates(const EC_GROUP *group, EC_POINT *p,
                                     BN_CTX *ctx);
 int ec_GFp_simple_ladder_pre(const EC_GROUP *group,
@@ -413,6 +422,8 @@ int ec_GFp_mont_field_mul(const EC_GROUP *, BIGNUM *r, const BIGNUM *a,
                           const BIGNUM *b, BN_CTX *);
 int ec_GFp_mont_field_sqr(const EC_GROUP *, BIGNUM *r, const BIGNUM *a,
                           BN_CTX *);
+int ec_GFp_mont_field_inv(const EC_GROUP *, BIGNUM *r, const BIGNUM *a,
+                          BN_CTX *);
 int ec_GFp_mont_field_encode(const EC_GROUP *, BIGNUM *r, const BIGNUM *a,
                              BN_CTX *);
 int ec_GFp_mont_field_decode(const EC_GROUP *, BIGNUM *r, const BIGNUM *a,
diff --git a/crypto/ec/ecp_mont.c b/crypto/ec/ecp_mont.c
index d3d770d2a3..1654d59513 100644
--- a/crypto/ec/ecp_mont.c
+++ b/crypto/ec/ecp_mont.c
@@ -50,6 +50,7 @@ const EC_METHOD *EC_GFp_mont_method(void)
         ec_GFp_mont_field_mul,
         ec_GFp_mont_field_sqr,
         0 /* field_div */ ,
+        ec_GFp_mont_field_inv,
         ec_GFp_mont_field_encode,
         ec_GFp_mont_field_decode,
         ec_GFp_mont_field_set_to_one,
@@ -206,6 +207,54 @@ int ec_GFp_mont_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
     return BN_mod_mul_montgomery(r, a, a, group->field_data1, ctx);
 }
 
+/*-
+ * Computes the multiplicative inverse of a in GF(p), storing the result in r.
+ * If a is zero (or equivalent), you'll get a EC_R_CANNOT_INVERT error.
+ * We have a Mont structure, so SCA hardening is FLT inversion.
+ */
+int ec_GFp_mont_field_inv(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
+                            BN_CTX *ctx)
+{
+    BIGNUM *e = NULL;
+    BN_CTX *new_ctx = NULL;
+    int ret = 0;
+
+    if (group->field_data1 == NULL)
+        return 0;
+
+    if (ctx == NULL && (ctx = new_ctx = BN_CTX_secure_new()) == NULL)
+        return 0;
+
+    BN_CTX_start(ctx);
+    if ((e = BN_CTX_get(ctx)) == NULL)
+        goto err;
+
+    /* Inverse in constant time with Fermats Little Theorem */
+    if (!BN_set_word(e, 2))
+        goto err;
+    if (!BN_sub(e, group->field, e))
+        goto err;
+    /*-
+     * Exponent e is public.
+     * No need for scatter-gather or BN_FLG_CONSTTIME.
+     */
+    if (!BN_mod_exp_mont(r, a, e, group->field, ctx, group->field_data1))
+        goto err;
+
+    /* throw an error on zero */
+    if (BN_is_zero(r)) {
+        ECerr(EC_F_EC_GFP_MONT_FIELD_INV, EC_R_CANNOT_INVERT);
+        goto err;
+    }
+
+    ret = 1;
+
+  err:
+    BN_CTX_end(ctx);
+    BN_CTX_free(new_ctx);
+    return ret;
+}
+
 int ec_GFp_mont_field_encode(const EC_GROUP *group, BIGNUM *r,
                              const BIGNUM *a, BN_CTX *ctx)
 {
diff --git a/crypto/ec/ecp_nist.c b/crypto/ec/ecp_nist.c
index 151e8ad728..9f9045b544 100644
--- a/crypto/ec/ecp_nist.c
+++ b/crypto/ec/ecp_nist.c
@@ -52,6 +52,7 @@ const EC_METHOD *EC_GFp_nist_method(void)
         ec_GFp_nist_field_mul,
         ec_GFp_nist_field_sqr,
         0 /* field_div */ ,
+        ec_GFp_simple_field_inv,
         0 /* field_encode */ ,
         0 /* field_decode */ ,
         0,                      /* field_set_to_one */
diff --git a/crypto/ec/ecp_nistp224.c b/crypto/ec/ecp_nistp224.c
index cd8b8c42c5..653965953b 100644
--- a/crypto/ec/ecp_nistp224.c
+++ b/crypto/ec/ecp_nistp224.c
@@ -279,6 +279,7 @@ const EC_METHOD *EC_GFp_nistp224_method(void)
         ec_GFp_nist_field_mul,
         ec_GFp_nist_field_sqr,
         0 /* field_div */ ,
+        ec_GFp_simple_field_inv,
         0 /* field_encode */ ,
         0 /* field_decode */ ,
         0,                      /* field_set_to_one */
diff --git a/crypto/ec/ecp_nistp256.c b/crypto/ec/ecp_nistp256.c
index 3c6097698c..ee5508fade 100644
--- a/crypto/ec/ecp_nistp256.c
+++ b/crypto/ec/ecp_nistp256.c
@@ -1810,6 +1810,7 @@ const EC_METHOD *EC_GFp_nistp256_method(void)
         ec_GFp_nist_field_mul,
         ec_GFp_nist_field_sqr,
         0 /* field_div */ ,
+        ec_GFp_simple_field_inv,
         0 /* field_encode */ ,
         0 /* field_decode */ ,
         0,                      /* field_set_to_one */
diff --git a/crypto/ec/ecp_nistp521.c b/crypto/ec/ecp_nistp521.c
index 653b8663f4..a32f3023e0 100644
--- a/crypto/ec/ecp_nistp521.c
+++ b/crypto/ec/ecp_nistp521.c
@@ -1647,6 +1647,7 @@ const EC_METHOD *EC_GFp_nistp521_method(void)
         ec_GFp_nist_field_mul,
         ec_GFp_nist_field_sqr,
         0 /* field_div */ ,
+        ec_GFp_simple_field_inv,
         0 /* field_encode */ ,
         0 /* field_decode */ ,
         0,                      /* field_set_to_one */
diff --git a/crypto/ec/ecp_nistz256.c b/crypto/ec/ecp_nistz256.c
index 82affd6e6a..c0772ca2fe 100644
--- a/crypto/ec/ecp_nistz256.c
+++ b/crypto/ec/ecp_nistz256.c
@@ -1677,6 +1677,7 @@ const EC_METHOD *EC_GFp_nistz256_method(void)
         ec_GFp_mont_field_mul,
         ec_GFp_mont_field_sqr,
         0,                                          /* field_div */
+        ec_GFp_mont_field_inv,
         ec_GFp_mont_field_encode,
         ec_GFp_mont_field_decode,
         ec_GFp_mont_field_set_to_one,
diff --git a/crypto/ec/ecp_smpl.c b/crypto/ec/ecp_smpl.c
index 7e8fe4fbbe..f80f98a169 100644
--- a/crypto/ec/ecp_smpl.c
+++ b/crypto/ec/ecp_smpl.c
@@ -51,6 +51,7 @@ const EC_METHOD *EC_GFp_simple_method(void)
         ec_GFp_simple_field_mul,
         ec_GFp_simple_field_sqr,
         0 /* field_div */ ,
+        ec_GFp_simple_field_inv,
         0 /* field_encode */ ,
         0 /* field_decode */ ,
         0,                      /* field_set_to_one */
@@ -553,7 +554,7 @@ int ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP *group,
             }
         }
     } else {
-        if (!BN_mod_inverse(Z_1, Z_, group->field, ctx)) {
+        if (!group->meth->field_inv(group, Z_1, Z_, ctx)) {
             ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES,
                   ERR_R_BN_LIB);
             goto err;
@@ -1266,7 +1267,7 @@ int ec_GFp_simple_points_make_affine(const EC_GROUP *group, size_t num,
      * points[i]->Z by its inverse.
      */
 
-    if (!BN_mod_inverse(tmp, prod_Z[num - 1], group->field, ctx)) {
+    if (!group->meth->field_inv(group, tmp, prod_Z[num - 1], ctx)) {
         ECerr(EC_F_EC_GFP_SIMPLE_POINTS_MAKE_AFFINE, ERR_R_BN_LIB);
         goto err;
     }
@@ -1370,6 +1371,50 @@ int ec_GFp_simple_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
 }
 
 /*-
+ * Computes the multiplicative inverse of a in GF(p), storing the result in r.
+ * If a is zero (or equivalent), you'll get a EC_R_CANNOT_INVERT error.
+ * Since we don't have a Mont structure here, SCA hardening is with blinding.
+ */
+int ec_GFp_simple_field_inv(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
+                            BN_CTX *ctx)
+{
+    BIGNUM *e = 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);
+    if ((e = BN_CTX_get(ctx)) == NULL)
+        goto err;
+
+    do {
+        if (!BN_priv_rand_range(e, group->field))
+        goto err;
+    } while (BN_is_zero(e));
+
+    /* r := a * e */
+    if (!group->meth->field_mul(group, r, a, e, ctx))
+        goto err;
+    /* r := 1/(a * e) */
+    if (!BN_mod_inverse(r, r, group->field, ctx)) {
+        ECerr(EC_F_EC_GFP_SIMPLE_FIELD_INV, EC_R_CANNOT_INVERT);
+        goto err;
+    }
+    /* r := e/(a * e) = 1/a */
+    if (!group->meth->field_mul(group, r, r, e, ctx))
+        goto err;
+
+    ret = 1;
+
+ err:
+    BN_CTX_end(ctx);
+    BN_CTX_free(new_ctx);
+    return ret;
+}
+
+/*-
  * Apply randomization of EC point projective coordinates:
  *
  *   (X, Y ,Z ) = (lambda^2*X, lambda^3*Y, lambda*Z)
diff --git a/crypto/err/openssl.txt b/crypto/err/openssl.txt
index a269ac688e..8d183fb5cd 100644
--- a/crypto/err/openssl.txt
+++ b/crypto/err/openssl.txt
@@ -521,6 +521,7 @@ EC_F_ECX_PUB_ENCODE:268:ecx_pub_encode
 EC_F_EC_ASN1_GROUP2CURVE:153:ec_asn1_group2curve
 EC_F_EC_ASN1_GROUP2FIELDID:154:ec_asn1_group2fieldid
 EC_F_EC_GF2M_MONTGOMERY_POINT_MULTIPLY:208:ec_GF2m_montgomery_point_multiply
+EC_F_EC_GF2M_SIMPLE_FIELD_INV:296:ec_GF2m_simple_field_inv
 EC_F_EC_GF2M_SIMPLE_GROUP_CHECK_DISCRIMINANT:159:\
 	ec_GF2m_simple_group_check_discriminant
 EC_F_EC_GF2M_SIMPLE_GROUP_SET_CURVE:195:ec_GF2m_simple_group_set_curve
@@ -537,6 +538,7 @@ EC_F_EC_GF2M_SIMPLE_SET_COMPRESSED_COORDINATES:164:\
 	ec_GF2m_simple_set_compressed_coordinates
 EC_F_EC_GFP_MONT_FIELD_DECODE:133:ec_GFp_mont_field_decode
 EC_F_EC_GFP_MONT_FIELD_ENCODE:134:ec_GFp_mont_field_encode
+EC_F_EC_GFP_MONT_FIELD_INV:297:ec_GFp_mont_field_inv
 EC_F_EC_GFP_MONT_FIELD_MUL:131:ec_GFp_mont_field_mul
 EC_F_EC_GFP_MONT_FIELD_SET_TO_ONE:209:ec_GFp_mont_field_set_to_one
 EC_F_EC_GFP_MONT_FIELD_SQR:132:ec_GFp_mont_field_sqr
@@ -557,6 +559,7 @@ EC_F_EC_GFP_NIST_FIELD_MUL:200:ec_GFp_nist_field_mul
 EC_F_EC_GFP_NIST_FIELD_SQR:201:ec_GFp_nist_field_sqr
 EC_F_EC_GFP_NIST_GROUP_SET_CURVE:202:ec_GFp_nist_group_set_curve
 EC_F_EC_GFP_SIMPLE_BLIND_COORDINATES:287:ec_GFp_simple_blind_coordinates
+EC_F_EC_GFP_SIMPLE_FIELD_INV:298:ec_GFp_simple_field_inv
 EC_F_EC_GFP_SIMPLE_GROUP_CHECK_DISCRIMINANT:165:\
 	ec_GFp_simple_group_check_discriminant
 EC_F_EC_GFP_SIMPLE_GROUP_SET_CURVE:166:ec_GFp_simple_group_set_curve
@@ -2157,6 +2160,7 @@ EC_R_ASN1_ERROR:115:asn1 error
 EC_R_BAD_SIGNATURE:156:bad signature
 EC_R_BIGNUM_OUT_OF_RANGE:144:bignum out of range
 EC_R_BUFFER_TOO_SMALL:100:buffer too small
+EC_R_CANNOT_INVERT:165:cannot invert
 EC_R_COORDINATES_OUT_OF_RANGE:146:coordinates out of range
 EC_R_CURVE_DOES_NOT_SUPPORT_ECDH:160:curve does not support ecdh
 EC_R_CURVE_DOES_NOT_SUPPORT_SIGNING:159:curve does not support signing