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/8262)

diff --git a/CHANGES b/CHANGES
index ff77c1b4b7b9011e5824882831db3a110e30492e..cc7502d456edce993464cc96cb26b68ce3bd136a 100644 (file)
--- a/CHANGES
+++ b/CHANGES
@@ -9,6 +9,12 @@
 
  Changes between 1.1.1a and 1.1.1b [xx XXX xxxx]
 
 
  Changes between 1.1.1a and 1.1.1b [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]
+

   *) Change the info callback signals for the start and end of a post-handshake
      message exchange in TLSv1.3. In 1.1.1/1.1.1a we used SSL_CB_HANDSHAKE_START
      and SSL_CB_HANDSHAKE_DONE. Experience has shown that many applications get
   *) Change the info callback signals for the start and end of a post-handshake
      message exchange in TLSv1.3. In 1.1.1/1.1.1a we used SSL_CB_HANDSHAKE_START
      and SSL_CB_HANDSHAKE_DONE. Experience has shown that many applications get

diff --git a/crypto/ec/ec2_smpl.c b/crypto/ec/ec2_smpl.c
index 87f7ce56911d9c23bf9b27cf5f8f4e1a8c1adffb..0a05a7aeea61c66e774122f05c44b78cdc168f63 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.

  * Copyright (c) 2002, Oracle and/or its affiliates. All rights reserved
  *
  * Licensed under the OpenSSL license (the "License").  You may not use
  * Copyright (c) 2002, Oracle and/or its affiliates. All rights reserved
  *
  * Licensed under the OpenSSL license (the "License").  You may not use


@@ -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)
         || !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)
         || !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;
 }
 
     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 = {
 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_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 */
         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 8f4911abec79a02050012894b4934bb4cbcc2c9b..ce3493823218f37c4a73380e2a3b0396e3b9075c 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
 /*
  * 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
  *
  * Licensed under the OpenSSL license (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"},
      "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),
     {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"},
      "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),
     {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"},
      "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),
     {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_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),
     {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 e055ddab1c76e0a1d6194530879e1a706cc3c75b..b3b7b28ca4d45ff32c8f81ed9f9258999b1554b4 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.

  * Copyright (c) 2002, Oracle and/or its affiliates. All rights reserved
  *
  * Licensed under the OpenSSL license (the "License").  You may not use
  * Copyright (c) 2002, Oracle and/or its affiliates. All rights reserved
  *
  * Licensed under the OpenSSL license (the "License").  You may not use


@@ -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 *);
     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 *);
     /* 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 *);
                             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,
 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 *);
                           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,
 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 36682e5cfbd184bd471c636f179870eec7fdb513..252e66ef3791cbf2cf1061fa14de70a6a35c62d0 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.

  * Copyright (c) 2002, Oracle and/or its affiliates. All rights reserved
  *
  * Licensed under the OpenSSL license (the "License").  You may not use
  * Copyright (c) 2002, Oracle and/or its affiliates. All rights reserved
  *
  * Licensed under the OpenSSL license (the "License").  You may not use


@@ -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_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,
         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);
 }
 
     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)
 {
 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 f53de1a1638bd4c5e6f4405d4b74884a469d526e..5eaa99d8402b6c3325de017124e20f4d416dda8f 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.

  * Copyright (c) 2002, Oracle and/or its affiliates. All rights reserved
  *
  * Licensed under the OpenSSL license (the "License").  You may not use
  * Copyright (c) 2002, Oracle and/or its affiliates. All rights reserved
  *
  * Licensed under the OpenSSL license (the "License").  You may not use


@@ -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_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 */
         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 555bf307dd031af61775500718359e294b1b26af..025273a1444087f708a1ab43a63da1b8fd25759a 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
  *
  * 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_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 */
         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 c87a5e548d369bd81c519b7faf704118899d697c..a21e5f78fc9065370f1a3744b06d8cf1685a5fa1 100644 (file)
--- a/crypto/ec/ecp_nistp256.c
+++ b/crypto/ec/ecp_nistp256.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
  *
  * 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_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 */
         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 14f2feeb6999624c888e9e496810827c9b626eef..2f47772a3477f3ab470c8f1674b8e8afd6d8e54b 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
  *
  * Licensed under the OpenSSL license (the "License").  You may not use
  * this file except in compliance with the License.  You can obtain a copy


@@ -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_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 */
         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 b0564bdbd04c56f9dc1bd63e3fd5ad9e5e9c5d8b..aea6394169ce9b69b858504c267e7bb2a9ad6edd 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.

  * Copyright (c) 2014, Intel Corporation. All Rights Reserved.
  * Copyright (c) 2015, CloudFlare, Inc.
  *
  * Copyright (c) 2014, Intel Corporation. All Rights Reserved.
  * Copyright (c) 2015, CloudFlare, Inc.
  *


@@ -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_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,
         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 d0c5557ff4ddaf52c2d7389d7114a0abf012377a..f6a6cedb0ae36a5ea19937b91e7d08a5b70bdfc6 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.

  * Copyright (c) 2002, Oracle and/or its affiliates. All rights reserved
  *
  * Licensed under the OpenSSL license (the "License").  You may not use
  * Copyright (c) 2002, Oracle and/or its affiliates. All rights reserved
  *
  * Licensed under the OpenSSL license (the "License").  You may not use


@@ -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_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 */
         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 {
             }
         }
     } 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;
             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.
      */
 
      * 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;
     }
         ECerr(EC_F_EC_GFP_SIMPLE_POINTS_MAKE_AFFINE, ERR_R_BN_LIB);
         goto err;
     }


@@ -1369,6 +1370,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);
 }
 
     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_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:
  *
 /*-
  * Apply randomization of EC point projective coordinates:
  *

diff --git a/crypto/err/openssl.txt b/crypto/err/openssl.txt
index 3864bf92020cedf12743858a363cb27485f78f9f..6b5f7dbef68ccff940e9ab07e60ddf4bdaad1578 100644 (file)
--- a/crypto/err/openssl.txt
+++ b/crypto/err/openssl.txt
@@ -519,6 +519,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_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
 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


@@ -535,6 +536,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_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
 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


@@ -555,6 +557,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_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
 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


@@ -2116,6 +2119,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_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
 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

diff --git a/include/openssl/ecerr.h b/include/openssl/ecerr.h
index 8d429387a2a29e5205858c95a7a6bd54349a3df3..be313d2856b89ab5a24e0c9c7604a2168f9b6a29 100644 (file)
--- a/include/openssl/ecerr.h
+++ b/include/openssl/ecerr.h
@@ -1,6 +1,6 @@
 /*
  * Generated by util/mkerr.pl DO NOT EDIT
 /*
  * 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
  *
  * Licensed under the OpenSSL license (the "License").  You may not use
  * this file except in compliance with the License.  You can obtain a copy


@@ -62,6 +62,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_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_LADDER_POST                  285
 #  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_LADDER_POST                  285


@@ -74,6 +75,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_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
 #  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


@@ -91,6 +93,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_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
 #  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


@@ -202,6 +205,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_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
 #  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