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>
(cherry picked from commit e0033efc30b0f00476bba8f0fa5512be5dc8a3f1)

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

diff --git a/CHANGES b/CHANGES
index d6342524f7b3fc0692b02f1fcdc0a21956806126..d0b6fd7f2f1f0c1b4185890362df31a2e100fe3e 100644 (file)
--- a/CHANGES
+++ b/CHANGES
@@ -9,6 +9,12 @@
 
  Changes between 1.1.0j and 1.1.0k [xx XXX xxxx]
 
+  *) Added SCA hardening for modular field inversion in EC_GROUP through
+     a new dedicated field_inv() pointer in EC_METHOD.
+     This also addresses a leakage affecting conversions from projective
+     to affine coordinates.
+     [Billy Bob Brumley, Nicola Tuveri]
+
   *) Fix a use after free bug in d2i_X509_PUBKEY when overwriting a
      re-used X509_PUBKEY object if the second PUBKEY is malformed.
      [Bernd Edlinger]

diff --git a/crypto/ec/ec2_smpl.c b/crypto/ec/ec2_smpl.c
index cdacce61acf97b473d399e2a619630d51417d8d7..6cb6d1bbb64c66ac2179514fd442667e9b77fd20 100644 (file)
--- a/crypto/ec/ec2_smpl.c
+++ b/crypto/ec/ec2_smpl.c
@@ -1,5 +1,5 @@
 /*
- * Copyright 2002-2018 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright 2002-2019 The OpenSSL Project Authors. All Rights Reserved.
  *
  * Licensed under the OpenSSL license (the "License").  You may not use
  * this file except in compliance with the License.  You can obtain a copy
@@ -29,67 +29,6 @@
 
 #ifndef OPENSSL_NO_EC2M
 
-const EC_METHOD *EC_GF2m_simple_method(void)
-{
-    static const EC_METHOD ret = {
-        EC_FLAGS_DEFAULT_OCT,
-        NID_X9_62_characteristic_two_field,
-        ec_GF2m_simple_group_init,
-        ec_GF2m_simple_group_finish,
-        ec_GF2m_simple_group_clear_finish,
-        ec_GF2m_simple_group_copy,
-        ec_GF2m_simple_group_set_curve,
-        ec_GF2m_simple_group_get_curve,
-        ec_GF2m_simple_group_get_degree,
-        ec_group_simple_order_bits,
-        ec_GF2m_simple_group_check_discriminant,
-        ec_GF2m_simple_point_init,
-        ec_GF2m_simple_point_finish,
-        ec_GF2m_simple_point_clear_finish,
-        ec_GF2m_simple_point_copy,
-        ec_GF2m_simple_point_set_to_infinity,
-        0 /* set_Jprojective_coordinates_GFp */ ,
-        0 /* get_Jprojective_coordinates_GFp */ ,
-        ec_GF2m_simple_point_set_affine_coordinates,
-        ec_GF2m_simple_point_get_affine_coordinates,
-        0, 0, 0,
-        ec_GF2m_simple_add,
-        ec_GF2m_simple_dbl,
-        ec_GF2m_simple_invert,
-        ec_GF2m_simple_is_at_infinity,
-        ec_GF2m_simple_is_on_curve,
-        ec_GF2m_simple_cmp,
-        ec_GF2m_simple_make_affine,
-        ec_GF2m_simple_points_make_affine,
-
-        /*
-         * the following three method functions are defined in ec2_mult.c
-         */
-        ec_GF2m_simple_mul,
-        ec_GF2m_precompute_mult,
-        ec_GF2m_have_precompute_mult,
-
-        ec_GF2m_simple_field_mul,
-        ec_GF2m_simple_field_sqr,
-        ec_GF2m_simple_field_div,
-        0 /* field_encode */ ,
-        0 /* field_decode */ ,
-        0,                      /* field_set_to_one */
-        ec_key_simple_priv2oct,
-        ec_key_simple_oct2priv,
-        0, /* set private */
-        ec_key_simple_generate_key,
-        ec_key_simple_check_key,
-        ec_key_simple_generate_public_key,
-        0, /* keycopy */
-        0, /* keyfinish */
-        ecdh_simple_compute_key,
-        0  /* blind_coordinates */
-    };
-
-    return &ret;
-}
-
 /*
  * Initialize a GF(2^m)-based EC_GROUP structure. Note that all other members
  * are handled by EC_GROUP_new.
@@ -757,4 +696,81 @@ int ec_GF2m_simple_field_div(const EC_GROUP *group, BIGNUM *r,
     return BN_GF2m_mod_div(r, a, b, group->field, ctx);
 }
 
+/*-
+ * 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 = {
+        EC_FLAGS_DEFAULT_OCT,
+        NID_X9_62_characteristic_two_field,
+        ec_GF2m_simple_group_init,
+        ec_GF2m_simple_group_finish,
+        ec_GF2m_simple_group_clear_finish,
+        ec_GF2m_simple_group_copy,
+        ec_GF2m_simple_group_set_curve,
+        ec_GF2m_simple_group_get_curve,
+        ec_GF2m_simple_group_get_degree,
+        ec_group_simple_order_bits,
+        ec_GF2m_simple_group_check_discriminant,
+        ec_GF2m_simple_point_init,
+        ec_GF2m_simple_point_finish,
+        ec_GF2m_simple_point_clear_finish,
+        ec_GF2m_simple_point_copy,
+        ec_GF2m_simple_point_set_to_infinity,
+        0 /* set_Jprojective_coordinates_GFp */ ,
+        0 /* get_Jprojective_coordinates_GFp */ ,
+        ec_GF2m_simple_point_set_affine_coordinates,
+        ec_GF2m_simple_point_get_affine_coordinates,
+        0, 0, 0,
+        ec_GF2m_simple_add,
+        ec_GF2m_simple_dbl,
+        ec_GF2m_simple_invert,
+        ec_GF2m_simple_is_at_infinity,
+        ec_GF2m_simple_is_on_curve,
+        ec_GF2m_simple_cmp,
+        ec_GF2m_simple_make_affine,
+        ec_GF2m_simple_points_make_affine,
+
+        /*
+         * the following three method functions are defined in ec2_mult.c
+         */
+        ec_GF2m_simple_mul,
+        ec_GF2m_precompute_mult,
+        ec_GF2m_have_precompute_mult,
+
+        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 */
+        ec_key_simple_priv2oct,
+        ec_key_simple_oct2priv,
+        0, /* set private */
+        ec_key_simple_generate_key,
+        ec_key_simple_check_key,
+        ec_key_simple_generate_public_key,
+        0, /* keycopy */
+        0, /* keyfinish */
+        ecdh_simple_compute_key,
+        0  /* blind_coordinates */
+    };
+
+    return &ret;
+}
+
 #endif

diff --git a/crypto/ec/ec_err.c b/crypto/ec/ec_err.c
index 717c92e984591643a6a78b9750a81b3e3b31a787..aeee2e8f4cf8a8293e87cdb2fd1c65d73e99b00a 100644 (file)
--- 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 OpenSSL license (the "License").  You may not use
  * this file except in compliance with the License.  You can obtain a copy
@@ -58,6 +58,7 @@ static ERR_STRING_DATA EC_str_functs[] = {
     {ERR_FUNC(EC_F_EC_ASN1_GROUP2FIELDID), "ec_asn1_group2fieldid"},
     {ERR_FUNC(EC_F_EC_GF2M_MONTGOMERY_POINT_MULTIPLY),
      "ec_GF2m_montgomery_point_multiply"},
+    {ERR_FUNC(EC_F_EC_GF2M_SIMPLE_FIELD_INV), "ec_GF2m_simple_field_inv"},
     {ERR_FUNC(EC_F_EC_GF2M_SIMPLE_GROUP_CHECK_DISCRIMINANT),
      "ec_GF2m_simple_group_check_discriminant"},
     {ERR_FUNC(EC_F_EC_GF2M_SIMPLE_GROUP_SET_CURVE),
@@ -72,6 +73,7 @@ static ERR_STRING_DATA EC_str_functs[] = {
      "ec_GF2m_simple_set_compressed_coordinates"},
     {ERR_FUNC(EC_F_EC_GFP_MONT_FIELD_DECODE), "ec_GFp_mont_field_decode"},
     {ERR_FUNC(EC_F_EC_GFP_MONT_FIELD_ENCODE), "ec_GFp_mont_field_encode"},
+    {ERR_FUNC(EC_F_EC_GFP_MONT_FIELD_INV), "ec_GFp_mont_field_inv"},
     {ERR_FUNC(EC_F_EC_GFP_MONT_FIELD_MUL), "ec_GFp_mont_field_mul"},
     {ERR_FUNC(EC_F_EC_GFP_MONT_FIELD_SET_TO_ONE),
      "ec_GFp_mont_field_set_to_one"},
@@ -99,6 +101,7 @@ static ERR_STRING_DATA EC_str_functs[] = {
      "ec_GFp_nist_group_set_curve"},
     {ERR_FUNC(EC_F_EC_GFP_SIMPLE_BLIND_COORDINATES),
      "ec_GFp_simple_blind_coordinates"},
+    {ERR_FUNC(EC_F_EC_GFP_SIMPLE_FIELD_INV), "ec_GFp_simple_field_inv"},
     {ERR_FUNC(EC_F_EC_GFP_SIMPLE_GROUP_CHECK_DISCRIMINANT),
      "ec_GFp_simple_group_check_discriminant"},
     {ERR_FUNC(EC_F_EC_GFP_SIMPLE_GROUP_SET_CURVE),
@@ -211,6 +214,7 @@ static ERR_STRING_DATA EC_str_reasons[] = {
     {ERR_REASON(EC_R_BAD_SIGNATURE), "bad signature"},
     {ERR_REASON(EC_R_BIGNUM_OUT_OF_RANGE), "bignum out of range"},
     {ERR_REASON(EC_R_BUFFER_TOO_SMALL), "buffer too small"},
+    {ERR_REASON(EC_R_CANNOT_INVERT), "cannot invert"},
     {ERR_REASON(EC_R_COORDINATES_OUT_OF_RANGE), "coordinates out of range"},
     {ERR_REASON(EC_R_CURVE_DOES_NOT_SUPPORT_ECDH),
      "curve does not support ecdh"},

diff --git a/crypto/ec/ec_lcl.h b/crypto/ec/ec_lcl.h
index ca1776efdb1f720d6f4a2cccd3ecf9256641383c..2e85597f6bb426ce3d0435f76ded05569b792195 100644 (file)
--- a/crypto/ec/ec_lcl.h
+++ b/crypto/ec/ec_lcl.h
@@ -1,5 +1,5 @@
 /*
- * Copyright 2001-2018 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright 2001-2019 The OpenSSL Project Authors. All Rights Reserved.
  *
  * Licensed under the OpenSSL license (the "License").  You may not use
  * this file except in compliance with the License.  You can obtain a copy
@@ -150,6 +150,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 *);
@@ -376,6 +383,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);
 
@@ -390,6 +399,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 d837d4d465ab92663af9b366a7aa13ba2920800c..8ecd53ad559ab6a4eda3168753376f9eb3145b8b 100644 (file)
--- a/crypto/ec/ecp_mont.c
+++ b/crypto/ec/ecp_mont.c
@@ -1,5 +1,5 @@
 /*
- * Copyright 2001-2018 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright 2001-2019 The OpenSSL Project Authors. All Rights Reserved.
  *
  * Licensed under the OpenSSL license (the "License").  You may not use
  * this file except in compliance with the License.  You can obtain a copy
@@ -55,6 +55,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,
@@ -207,6 +208,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 143f21f3f9bb7353494a0b99657d6099efd7e631..c874380203807628462e00e8da3cad2e02dbde18 100644 (file)
--- a/crypto/ec/ecp_nist.c
+++ b/crypto/ec/ecp_nist.c
@@ -1,5 +1,5 @@
 /*
- * Copyright 2001-2018 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright 2001-2019 The OpenSSL Project Authors. All Rights Reserved.
  *
  * Licensed under the OpenSSL license (the "License").  You may not use
  * this file except in compliance with the License.  You can obtain a copy
@@ -57,6 +57,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 52056ff591006e600292e60680afcbb78363ce73..651dcb10a055ebfc89a95267943072b742f6d757 100644 (file)
--- a/crypto/ec/ecp_nistp224.c
+++ b/crypto/ec/ecp_nistp224.c
@@ -1,5 +1,5 @@
 /*
- * Copyright 2010-2018 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright 2010-2019 The OpenSSL Project Authors. All Rights Reserved.
  *
  * Licensed under the OpenSSL license (the "License").  You may not use
  * this file except in compliance with the License.  You can obtain a copy
@@ -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 ffd2a7d93a065bab44ad3fa0a23a70437c3bf7ed..dfd98c62feb6b7b1cc782af8d6aa7c98b0598019 100644 (file)
--- a/crypto/ec/ecp_nistp256.c
+++ b/crypto/ec/ecp_nistp256.c
@@ -1,5 +1,5 @@
 /*
- * Copyright 2011-2016 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright 2011-2019 The OpenSSL Project Authors. All Rights Reserved.
  *
  * Licensed under the OpenSSL license (the "License").  You may not use
  * this file except in compliance with the License.  You can obtain a copy
@@ -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 0a82abca1b00f4ac119c3d50f1fb67dabcc9ef57..ddfef91bda029f8baf07cf49c330cefb7811dbf2 100644 (file)
--- a/crypto/ec/ecp_nistp521.c
+++ b/crypto/ec/ecp_nistp521.c
@@ -1,5 +1,5 @@
 /*
- * Copyright 2011-2018 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright 2011-2019 The OpenSSL Project Authors. All Rights Reserved.
  *
  * Licensed under the OpenSSL license (the "License").  You may not use
  * this file except in compliance with the License.  You can obtain a copy
@@ -1631,6 +1631,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 7eafce649b451798ef734db08b4a90bd4523dd60..e1170b4d3986e17ba74973b3781ae63b7c9c80eb 100644 (file)
--- a/crypto/ec/ecp_nistz256.c
+++ b/crypto/ec/ecp_nistz256.c
@@ -1,5 +1,5 @@
 /*
- * Copyright 2014-2018 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright 2014-2019 The OpenSSL Project Authors. All Rights Reserved.
  *
  * Licensed under the OpenSSL license (the "License").  You may not use
  * this file except in compliance with the License.  You can obtain a copy
@@ -1525,6 +1525,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 2015f1173bf71742a8ef969cffcecce96e261cd4..d8db1ea3942e858b99fb7341075b134341b28f60 100644 (file)
--- a/crypto/ec/ecp_smpl.c
+++ b/crypto/ec/ecp_smpl.c
@@ -1,5 +1,5 @@
 /*
- * Copyright 2001-2018 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright 2001-2019 The OpenSSL Project Authors. All Rights Reserved.
  *
  * Licensed under the OpenSSL license (the "License").  You may not use
  * this file except in compliance with the License.  You can obtain a copy
@@ -56,6 +56,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 */
@@ -554,7 +555,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;
@@ -1267,7 +1268,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,
     return BN_mod_sqr(r, a, group->field, 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.
+ * 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_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:
  *

diff --git a/include/openssl/ec.h b/include/openssl/ec.h
index d6b36c77c09e454adb966f87f778704e5b5a3e07..bea6b8c372e9438730decbe59d57232fbdf3076a 100644 (file)
--- a/include/openssl/ec.h
+++ b/include/openssl/ec.h
@@ -1,5 +1,5 @@
 /*
- * Copyright 2002-2018 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright 2002-2019 The OpenSSL Project Authors. All Rights Reserved.
  *
  * Licensed under the OpenSSL license (the "License").  You may not use
  * this file except in compliance with the License.  You can obtain a copy
@@ -1399,6 +1399,7 @@ int ERR_load_EC_strings(void);
 # define EC_F_EC_ASN1_GROUP2CURVE                         153
 # define EC_F_EC_ASN1_GROUP2FIELDID                       154
 # define EC_F_EC_GF2M_MONTGOMERY_POINT_MULTIPLY           208
+# define EC_F_EC_GF2M_SIMPLE_FIELD_INV                    296
 # define EC_F_EC_GF2M_SIMPLE_GROUP_CHECK_DISCRIMINANT     159
 # define EC_F_EC_GF2M_SIMPLE_GROUP_SET_CURVE              195
 # define EC_F_EC_GF2M_SIMPLE_OCT2POINT                    160
@@ -1408,6 +1409,7 @@ int ERR_load_EC_strings(void);
 # define EC_F_EC_GF2M_SIMPLE_SET_COMPRESSED_COORDINATES   164
 # define EC_F_EC_GFP_MONT_FIELD_DECODE                    133
 # define EC_F_EC_GFP_MONT_FIELD_ENCODE                    134
+# define EC_F_EC_GFP_MONT_FIELD_INV                       297
 # define EC_F_EC_GFP_MONT_FIELD_MUL                       131
 # define EC_F_EC_GFP_MONT_FIELD_SET_TO_ONE                209
 # define EC_F_EC_GFP_MONT_FIELD_SQR                       132
@@ -1425,6 +1427,7 @@ int ERR_load_EC_strings(void);
 # define EC_F_EC_GFP_NIST_FIELD_SQR                       201
 # define EC_F_EC_GFP_NIST_GROUP_SET_CURVE                 202
 # define EC_F_EC_GFP_SIMPLE_BLIND_COORDINATES             287
+# define EC_F_EC_GFP_SIMPLE_FIELD_INV                     298
 # define EC_F_EC_GFP_SIMPLE_GROUP_CHECK_DISCRIMINANT      165
 # define EC_F_EC_GFP_SIMPLE_GROUP_SET_CURVE               166
 # define EC_F_EC_GFP_SIMPLE_MAKE_AFFINE                   102
@@ -1514,6 +1517,7 @@ int ERR_load_EC_strings(void);
 # define EC_R_BAD_SIGNATURE                               156
 # define EC_R_BIGNUM_OUT_OF_RANGE                         144
 # define EC_R_BUFFER_TOO_SMALL                            100
+# define EC_R_CANNOT_INVERT                               165
 # define EC_R_COORDINATES_OUT_OF_RANGE                    146
 # define EC_R_CURVE_DOES_NOT_SUPPORT_ECDH                 160
 # define EC_R_CURVE_DOES_NOT_SUPPORT_SIGNING              159