Implement coordinate blinding for EC_POINT.

Based on OpenSSL commit 875ba8b21ecc65ad9a6bdc66971e50
by Billy Brumley, Sohaib ul Hassan and Nicola Tuveri.

ok beck jsing

commit 875ba8b21ecc65ad9a6bdc66971e50461660fcbb
Author: Sohaib ul Hassan <soh.19.hassan@gmail.com>
Date:   Sat Jun 16 17:07:40 2018 +0300

    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: Tim Hudson <tjh@openssl.org>
    Reviewed-by: Nicola Tuveri <nic.tuv@gmail.com>
    Reviewed-by: Andy Polyakov <appro@openssl.org>
    (Merged from https://github.com/openssl/openssl/pull/6526)

1 files changed, 68 insertions, 3 deletions

diff --git a/src/lib/libcrypto/ec/ecp_smpl.c b/src/lib/libcrypto/ec/ecp_smpl.c
index a25fd1df84..fe935251d9 100644
--- a/src/lib/libcrypto/ec/ecp_smpl.c
+++ b/src/lib/libcrypto/ec/ecp_smpl.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: ecp_smpl.c,v 1.22 2018/07/16 17:32:39 tb Exp $ */
+/* $OpenBSD: ecp_smpl.c,v 1.23 2018/11/05 20:18:21 tb Exp $ */
 /* Includes code written by Lenka Fibikova <fibikova@exp-math.uni-essen.de>
  * for the OpenSSL project.
  * Includes code written by Bodo Moeller for the OpenSSL project.
@@ -107,7 +107,8 @@ EC_GFp_simple_method(void)
                 .mul_single_ct = ec_GFp_simple_mul_single_ct,
                 .mul_double_nonct = ec_GFp_simple_mul_double_nonct,
                 .field_mul = ec_GFp_simple_field_mul,
-                .field_sqr = ec_GFp_simple_field_sqr
+                .field_sqr = ec_GFp_simple_field_sqr,
+                .blind_coordinates = ec_GFp_simple_blind_coordinates,
         };
 
         return &ret;
@@ -1406,13 +1407,70 @@ ec_GFp_simple_field_mul(const EC_GROUP * group, BIGNUM * r, const BIGNUM * a, co
         return BN_mod_mul(r, a, b, &group->field, ctx);
 }
 
-
 int 
 ec_GFp_simple_field_sqr(const EC_GROUP * group, BIGNUM * r, const BIGNUM * a, BN_CTX * ctx)
 {
         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)
+ * 
+ * where lambda is in the interval [1, group->field).
+ */
+int
+ec_GFp_simple_blind_coordinates(const EC_GROUP *group, EC_POINT *p, BN_CTX *ctx)
+{
+        BIGNUM *lambda = NULL;
+        BIGNUM *tmp = NULL;
+        int ret = 0;
+
+        BN_CTX_start(ctx);
+        if ((lambda = BN_CTX_get(ctx)) == NULL)
+                goto err;
+        if ((tmp = BN_CTX_get(ctx)) == NULL)
+                goto err;
+
+        /* Generate lambda in [1, group->field - 1] */
+        do {
+                if (!BN_rand_range(lambda, &group->field))
+                        goto err;
+        } while (BN_is_zero(lambda));
+
+        if (group->meth->field_encode != NULL &&
+            !group->meth->field_encode(group, lambda, lambda, ctx))
+                goto err;
+
+        /* Z = lambda * Z */
+        if (!group->meth->field_mul(group, &p->Z, lambda, &p->Z, ctx))
+                goto err;
+
+        /* tmp = lambda^2 */
+        if (!group->meth->field_sqr(group, tmp, lambda, ctx))
+                goto err;
+
+        /* X = lambda^2 * X */
+        if (!group->meth->field_mul(group, &p->X, tmp, &p->X, ctx))
+                goto err;
+
+        /* tmp = lambda^3 */
+        if (!group->meth->field_mul(group, tmp, tmp, lambda, ctx))
+                goto err;
+
+        /* Y = lambda^3 * Y */
+        if (!group->meth->field_mul(group, &p->Y, tmp, &p->Y, ctx))
+                goto err;
+
+        ret = 1;
+
+ err:
+        BN_CTX_end(ctx);
+        return ret;
+}
+
+
 #define EC_POINT_BN_set_flags(P, flags) do {                            \
         BN_set_flags(&(P)->X, (flags));                                 \
         BN_set_flags(&(P)->Y, (flags));                                 \
@@ -1537,6 +1595,13 @@ ec_GFp_simple_mul_ct(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
             (bn_wexpand(&r->Z, group_top) == NULL))
                 goto err;
 
+        /*
+         * Apply coordinate blinding for EC_POINT if the underlying EC_METHOD
+         * implements it.
+         */
+        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;