Implement coordinate blinding for EC_POINT

This commit implements coordinate blinding, i.e., it randomizes the
representative of an elliptic curve point in its equivalence class, for
prime curves implemented through EC_GFp_simple_method,
EC_GFp_mont_method, and EC_GFp_nist_method.

This commit is derived from the patch
https://marc.info/?l=openssl-dev&m=131194808413635 by Billy Brumley.

Coordinate blinding is a generally useful side-channel countermeasure
and is (mostly) free. The function itself takes a few field
multiplicationss, but is usually only necessary at the beginning of a
scalar multiplication (as implemented in the patch). When used this way,
it makes the values that variables take (i.e., field elements in an
algorithm state) unpredictable.

For instance, this mitigates chosen EC point side-channel attacks for
settings such as ECDH and EC private key decryption, for the
aforementioned curves.

For EC_METHODs using different coordinate representations this commit
does nothing, but the corresponding coordinate blinding function can be
easily added in the future to extend these changes to such curves.

Co-authored-by: Nicola Tuveri <nic.tuv@gmail.com>
Co-authored-by: Billy Brumley <bbrumley@gmail.com>
Reviewed-by: Andy Polyakov <appro@openssl.org>
Reviewed-by: Matt Caswell <matt@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/6501)

diff --git a/CHANGES b/CHANGES
index fe3e13aa0d8e792b51e8a11a0fffc40a335b8829..a4beda66dd49e161f341cf501714390b8695f7d5 100644 (file)
--- a/CHANGES
+++ b/CHANGES
@@ -8,6 +8,11 @@
  release branch.
 
  Changes between 1.1.0h and 1.1.1 [xx XXX xxxx]
+  *) Add coordinate blinding for EC_POINT and implement projective
+     coordinate blinding for generic prime curves as a countermeasure to
+     chosen point SCA attacks.
+     [Sohaib ul Hassan, Nicola Tuveri, Billy Bob Brumley]
+
   *) Add blinding to an ECDSA signature to protect against side channel attacks
      discovered by Keegan Ryan (NCC Group).
      [Matt Caswell]

diff --git a/crypto/ec/ec2_smpl.c b/crypto/ec/ec2_smpl.c
index b79e60b8b536dafd1e10708e504f732672b0c06f..cef6ba4c655d7a2fed553d811aabfc2e76e992a3 100644 (file)
--- a/crypto/ec/ec2_smpl.c
+++ b/crypto/ec/ec2_smpl.c
@@ -64,7 +64,9 @@ const EC_METHOD *EC_GF2m_simple_method(void)
         ec_key_simple_generate_public_key,
         0, /* keycopy */
         0, /* keyfinish */
-        ecdh_simple_compute_key
+        ecdh_simple_compute_key,
+        0, /* field_inverse_mod_ord */
+        0  /* blind_coordinates */
     };
 
     return &ret;

diff --git a/crypto/ec/ec_err.c b/crypto/ec/ec_err.c
index 6a1be2eb3ba677f16cfa57a26447100284e62aba..342b84fecb02c13f6737535b3c61d39bc1e9ac99 100644 (file)
--- a/crypto/ec/ec_err.c
+++ b/crypto/ec/ec_err.c
@@ -116,6 +116,8 @@ static const ERR_STRING_DATA EC_str_functs[] = {
      "ec_GFp_nist_field_sqr"},
     {ERR_PACK(ERR_LIB_EC, EC_F_EC_GFP_NIST_GROUP_SET_CURVE, 0),
      "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_GROUP_CHECK_DISCRIMINANT, 0),
      "ec_GFp_simple_group_check_discriminant"},
     {ERR_PACK(ERR_LIB_EC, EC_F_EC_GFP_SIMPLE_GROUP_SET_CURVE, 0),

diff --git a/crypto/ec/ec_lcl.h b/crypto/ec/ec_lcl.h
index 5e14071aecd68f34ff648238fc0c7f116cd2fa3e..006e3b6e16d69e79002ebbf7b578a0286ddd0318 100644 (file)
--- a/crypto/ec/ec_lcl.h
+++ b/crypto/ec/ec_lcl.h
@@ -176,6 +176,7 @@ struct ec_method_st {
     /* Inverse modulo order */
     int (*field_inverse_mod_ord)(const EC_GROUP *, BIGNUM *r, BIGNUM *x,
                                  BN_CTX *ctx);
+    int (*blind_coordinates)(const EC_GROUP *group, EC_POINT *p, BN_CTX *ctx);
 };
 
 /*
@@ -382,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_blind_coordinates(const EC_GROUP *group, EC_POINT *p,
+                                   BN_CTX *ctx);
 
 /* method functions in ecp_mont.c */
 int ec_GFp_mont_group_init(EC_GROUP *);
@@ -635,3 +638,5 @@ void X25519_public_from_private(uint8_t out_public_value[32],
 
 int EC_GROUP_do_inverse_ord(const EC_GROUP *group, BIGNUM *res,
                             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 30b11f75e99821380e45c0b229f1a5e400633251..d0393e8badf2c5790dea69f13e23e2ae029b670a 100644 (file)
--- a/crypto/ec/ec_lib.c
+++ b/crypto/ec/ec_lib.c
@@ -1025,3 +1025,21 @@ int EC_GROUP_do_inverse_ord(const EC_GROUP *group, BIGNUM *res,
     else
         return 0;
 }
+
+/*-
+ * Coordinate blinding for EC_POINT.
+ *
+ * The underlying EC_METHOD can optionally implement this function:
+ * underlying implementations should return 0 on errors, or 1 on
+ * success.
+ *
+ * This wrapper returns 1 in case the underlying EC_METHOD does not
+ * support coordinate blinding.
+ */
+int ec_point_blind_coordinates(const EC_GROUP *group, EC_POINT *p, BN_CTX *ctx)
+{
+    if (group->meth->blind_coordinates == NULL)
+        return 1; /* ignore if not implemented */
+
+    return group->meth->blind_coordinates(group, p, ctx);
+}

diff --git a/crypto/ec/ec_mult.c b/crypto/ec/ec_mult.c
index 05a3aca0a402d1188792839b4a91e601d2db5da8..b668e87ff7cd2befd496b4409496604a671e4c4b 100644 (file)
--- a/crypto/ec/ec_mult.c
+++ b/crypto/ec/ec_mult.c
@@ -211,6 +211,17 @@ static int ec_mul_consttime(const EC_GROUP *group, EC_POINT *r,
         || (bn_wexpand(r->Z, group_top) == NULL))
         goto err;
 
+    /*-
+     * Apply coordinate blinding for EC_POINT.
+     *
+     * The underlying EC_METHOD can optionally implement this function:
+     * ec_point_blind_coordinates() returns 0 in case of errors or 1 on
+     * success or if coordinate blinding is not implemented for this
+     * group.
+     */
+    if (!ec_point_blind_coordinates(group, s, ctx))
+        goto err;
+
     /* top bit is a 1, in a fixed pos */
     if (!EC_POINT_copy(r, s))
         goto err;

diff --git a/crypto/ec/ecp_mont.c b/crypto/ec/ecp_mont.c
index 1a760d123912a0c32804a89c0174a68beaaf9d0a..27ece3b43cb0acba0dc8fb35092b7fd2b4b65050 100644 (file)
--- a/crypto/ec/ecp_mont.c
+++ b/crypto/ec/ecp_mont.c
@@ -61,7 +61,9 @@ const EC_METHOD *EC_GFp_mont_method(void)
         ec_key_simple_generate_public_key,
         0, /* keycopy */
         0, /* keyfinish */
-        ecdh_simple_compute_key
+        ecdh_simple_compute_key,
+        0, /* field_inverse_mod_ord */
+        ec_GFp_simple_blind_coordinates
     };
 
     return &ret;

diff --git a/crypto/ec/ecp_nist.c b/crypto/ec/ecp_nist.c
index 16c4cce313f32a2bf02b3dab689beb5cf840c3f2..aaa73d62d7b9dc3938f05380376d9ea191899045 100644 (file)
--- a/crypto/ec/ecp_nist.c
+++ b/crypto/ec/ecp_nist.c
@@ -63,7 +63,9 @@ const EC_METHOD *EC_GFp_nist_method(void)
         ec_key_simple_generate_public_key,
         0, /* keycopy */
         0, /* keyfinish */
-        ecdh_simple_compute_key
+        ecdh_simple_compute_key,
+        0, /* field_inverse_mod_ord */
+        ec_GFp_simple_blind_coordinates
     };
 
     return &ret;

diff --git a/crypto/ec/ecp_nistp224.c b/crypto/ec/ecp_nistp224.c
index 364b7f246d7b72d237c058094d9cc2a25a98a129..6e7c687c43c884f85781a9a9bf0cbf900fdec7bf 100644 (file)
--- a/crypto/ec/ecp_nistp224.c
+++ b/crypto/ec/ecp_nistp224.c
@@ -290,7 +290,9 @@ const EC_METHOD *EC_GFp_nistp224_method(void)
         ec_key_simple_generate_public_key,
         0, /* keycopy */
         0, /* keyfinish */
-        ecdh_simple_compute_key
+        ecdh_simple_compute_key,
+        0, /* field_inverse_mod_ord */
+        0  /* blind_coordinates */
     };
 
     return &ret;

diff --git a/crypto/ec/ecp_nistp521.c b/crypto/ec/ecp_nistp521.c
index 3f68ae3c1c62cd7990a290f162578c232184d120..43f3e2d9eef34ac601ea1732157b69828960128d 100644 (file)
--- a/crypto/ec/ecp_nistp521.c
+++ b/crypto/ec/ecp_nistp521.c
@@ -1658,7 +1658,9 @@ const EC_METHOD *EC_GFp_nistp521_method(void)
         ec_key_simple_generate_public_key,
         0, /* keycopy */
         0, /* keyfinish */
-        ecdh_simple_compute_key
+        ecdh_simple_compute_key,
+        0, /* field_inverse_mod_ord */
+        0  /* blind_coordinates */
     };
 
     return &ret;

diff --git a/crypto/ec/ecp_nistz256.c b/crypto/ec/ecp_nistz256.c
index d3603fbbecd9d3a7263158b67de9374deb40011f..02925616b15f5b75aa20518fd99019defb0078ff 100644 (file)
--- a/crypto/ec/ecp_nistz256.c
+++ b/crypto/ec/ecp_nistz256.c
@@ -1730,7 +1730,8 @@ const EC_METHOD *EC_GFp_nistz256_method(void)
         0, /* keycopy */
         0, /* keyfinish */
         ecdh_simple_compute_key,
-        ecp_nistz256_inv_mod_ord                    /* can be #define-d NULL */
+        ecp_nistz256_inv_mod_ord,                   /* can be #define-d NULL */
+        0                                           /* blind_coordinates */
     };
 
     return &ret;

diff --git a/crypto/ec/ecp_smpl.c b/crypto/ec/ecp_smpl.c
index 35d15a68821642a98ca628e04a8fb2700d78a3ba..e0e4996cfd6d80ea1ed929b26f990d5a52eda4df 100644 (file)
--- a/crypto/ec/ecp_smpl.c
+++ b/crypto/ec/ecp_smpl.c
@@ -62,7 +62,9 @@ const EC_METHOD *EC_GFp_simple_method(void)
         ec_key_simple_generate_public_key,
         0, /* keycopy */
         0, /* keyfinish */
-        ecdh_simple_compute_key
+        ecdh_simple_compute_key,
+        0, /* field_inverse_mod_ord */
+        ec_GFp_simple_blind_coordinates
     };
 
     return &ret;
@@ -1363,3 +1365,57 @@ int ec_GFp_simple_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
 {
     return BN_mod_sqr(r, a, group->field, ctx);
 }
+
+/*-
+ * Apply randomization of EC point projective coordinates:
+ *
+ *   (X, Y ,Z ) = (lambda^2*X, lambda^3*Y, lambda*Z)
+ *   lambda = [1,group->field)
+ *
+ */
+int ec_GFp_simple_blind_coordinates(const EC_GROUP *group, EC_POINT *p,
+                                    BN_CTX *ctx)
+{
+    int ret = 0;
+    BIGNUM *lambda = NULL;
+    BIGNUM *temp = NULL;
+
+    BN_CTX_start(ctx);
+    lambda = BN_CTX_get(ctx);
+    temp = BN_CTX_get(ctx);
+    if (temp == NULL) {
+        ECerr(EC_F_EC_GFP_SIMPLE_BLIND_COORDINATES, ERR_R_MALLOC_FAILURE);
+        goto err;
+    }
+
+    /* make sure lambda is not zero */
+    do {
+        if (!BN_priv_rand_range(lambda, group->field)) {
+            ECerr(EC_F_EC_GFP_SIMPLE_BLIND_COORDINATES, ERR_R_BN_LIB);
+            goto err;
+        }
+    } while (BN_is_zero(lambda));
+
+    /* if field_encode defined convert between representations */
+    if (group->meth->field_encode != NULL
+        && !group->meth->field_encode(group, lambda, lambda, ctx))
+        goto err;
+    if (!group->meth->field_mul(group, p->Z, p->Z, lambda, ctx))
+        goto err;
+    if (!group->meth->field_sqr(group, temp, lambda, ctx))
+        goto err;
+    if (!group->meth->field_mul(group, p->X, p->X, temp, ctx))
+        goto err;
+    if (!group->meth->field_mul(group, temp, temp, lambda, ctx))
+        goto err;
+    if (!group->meth->field_mul(group, p->Y, p->Y, temp, ctx))
+        goto err;
+    p->Z_is_one = 0;
+
+    ret = 1;
+
+ err:
+     BN_CTX_end(ctx);
+     return ret;
+}
+

diff --git a/crypto/err/openssl.txt b/crypto/err/openssl.txt
index 23671a0f26b861034139bd64ca4b6e468a3df4a2..e0580a871d90b673b3b2046980b051740a34d668 100644 (file)
--- a/crypto/err/openssl.txt
+++ b/crypto/err/openssl.txt
@@ -550,6 +550,7 @@ EC_F_EC_GFP_NISTP521_POINT_GET_AFFINE_COORDINATES:235:\
 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_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

diff --git a/include/openssl/ecerr.h b/include/openssl/ecerr.h
index 603efccaa37176b9555fed12e4c0dbee724b5229..8db7967697eafe00c0dcf5ba1debd27ae21fedd4 100644 (file)
--- a/include/openssl/ecerr.h
+++ b/include/openssl/ecerr.h
@@ -87,6 +87,7 @@ int ERR_load_EC_strings(void);
 #  define EC_F_EC_GFP_NIST_FIELD_MUL                       200
 #  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_GROUP_CHECK_DISCRIMINANT      165
 #  define EC_F_EC_GFP_SIMPLE_GROUP_SET_CURVE               166
 #  define EC_F_EC_GFP_SIMPLE_MAKE_AFFINE                   102