From cf97742ffbfc84800478e34a8d383f39db8618e9 Mon Sep 17 00:00:00 2001 From: tb <> Date: Mon, 5 Nov 2018 20:18:21 +0000 Subject: 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 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 Co-authored-by: Billy Brumley Reviewed-by: Tim Hudson Reviewed-by: Nicola Tuveri Reviewed-by: Andy Polyakov (Merged from https://github.com/openssl/openssl/pull/6526) --- src/lib/libcrypto/ec/ec2_smpl.c | 3 +- src/lib/libcrypto/ec/ec_lcl.h | 5 ++- src/lib/libcrypto/ec/ec_lib.c | 19 +++++++++- src/lib/libcrypto/ec/ecp_mont.c | 5 +-- src/lib/libcrypto/ec/ecp_nist.c | 5 +-- src/lib/libcrypto/ec/ecp_nistp224.c | 5 +-- src/lib/libcrypto/ec/ecp_nistp256.c | 5 +-- src/lib/libcrypto/ec/ecp_nistp521.c | 5 +-- src/lib/libcrypto/ec/ecp_nistz256.c | 5 +-- src/lib/libcrypto/ec/ecp_smpl.c | 71 +++++++++++++++++++++++++++++++++++-- 10 files changed, 110 insertions(+), 18 deletions(-) diff --git a/src/lib/libcrypto/ec/ec2_smpl.c b/src/lib/libcrypto/ec/ec2_smpl.c index 1ca04194b3..936cee4898 100644 --- a/src/lib/libcrypto/ec/ec2_smpl.c +++ b/src/lib/libcrypto/ec/ec2_smpl.c @@ -1,4 +1,4 @@ -/* $OpenBSD: ec2_smpl.c,v 1.20 2018/07/16 17:32:39 tb Exp $ */ +/* $OpenBSD: ec2_smpl.c,v 1.21 2018/11/05 20:18:21 tb Exp $ */ /* ==================================================================== * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. * @@ -115,6 +115,7 @@ EC_GF2m_simple_method(void) .field_mul = ec_GF2m_simple_field_mul, .field_sqr = ec_GF2m_simple_field_sqr, .field_div = ec_GF2m_simple_field_div, + .blind_coordinates = NULL, }; return &ret; diff --git a/src/lib/libcrypto/ec/ec_lcl.h b/src/lib/libcrypto/ec/ec_lcl.h index e430b3f64d..c177246f36 100644 --- a/src/lib/libcrypto/ec/ec_lcl.h +++ b/src/lib/libcrypto/ec/ec_lcl.h @@ -1,4 +1,4 @@ -/* $OpenBSD: ec_lcl.h,v 1.10 2018/07/16 17:32:39 tb Exp $ */ +/* $OpenBSD: ec_lcl.h,v 1.11 2018/11/05 20:18:21 tb Exp $ */ /* * Originally written by Bodo Moeller for the OpenSSL project. */ @@ -182,6 +182,7 @@ struct ec_method_st { int (*field_encode)(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, BN_CTX *); /* e.g. to Montgomery */ int (*field_decode)(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, BN_CTX *); /* e.g. from Montgomery */ int (*field_set_to_one)(const EC_GROUP *, BIGNUM *r, BN_CTX *); + int (*blind_coordinates)(const EC_GROUP *group, EC_POINT *p, BN_CTX *ctx); } /* EC_METHOD */; typedef struct ec_extra_data_st { @@ -339,6 +340,7 @@ int ec_GFp_simple_make_affine(const EC_GROUP *, EC_POINT *, BN_CTX *); int ec_GFp_simple_points_make_affine(const EC_GROUP *, size_t num, EC_POINT *[], BN_CTX *); 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); int ec_GFp_simple_mul_generator_ct(const EC_GROUP *, EC_POINT *r, const BIGNUM *scalar, BN_CTX *); int ec_GFp_simple_mul_single_ct(const EC_GROUP *, EC_POINT *r, const BIGNUM *scalar, const EC_POINT *point, BN_CTX *); @@ -358,6 +360,7 @@ int ec_GFp_mont_field_encode(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, BN_CT int ec_GFp_mont_field_decode(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, BN_CTX *); int ec_GFp_mont_field_set_to_one(const EC_GROUP *, BIGNUM *r, BN_CTX *); +int ec_point_blind_coordinates(const EC_GROUP *group, EC_POINT *p, BN_CTX *ctx); /* method functions in ecp_nist.c */ int ec_GFp_nist_group_copy(EC_GROUP *dest, const EC_GROUP *src); diff --git a/src/lib/libcrypto/ec/ec_lib.c b/src/lib/libcrypto/ec/ec_lib.c index 7e0ea017f9..bf2f652fc7 100644 --- a/src/lib/libcrypto/ec/ec_lib.c +++ b/src/lib/libcrypto/ec/ec_lib.c @@ -1,4 +1,4 @@ -/* $OpenBSD: ec_lib.c,v 1.29 2018/07/16 17:32:39 tb Exp $ */ +/* $OpenBSD: ec_lib.c,v 1.30 2018/11/05 20:18:21 tb Exp $ */ /* * Originally written by Bodo Moeller for the OpenSSL project. */ @@ -533,6 +533,23 @@ EC_GROUP_cmp(const EC_GROUP * a, const EC_GROUP * b, BN_CTX * ctx) return -1; } +/* + * 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; + + return group->meth->blind_coordinates(group, p, ctx); +} /* this has 'package' visibility */ int diff --git a/src/lib/libcrypto/ec/ecp_mont.c b/src/lib/libcrypto/ec/ecp_mont.c index ba4b9cad97..f4dff9aa46 100644 --- a/src/lib/libcrypto/ec/ecp_mont.c +++ b/src/lib/libcrypto/ec/ecp_mont.c @@ -1,4 +1,4 @@ -/* $OpenBSD: ecp_mont.c,v 1.16 2018/07/16 17:32:39 tb Exp $ */ +/* $OpenBSD: ecp_mont.c,v 1.17 2018/11/05 20:18:21 tb Exp $ */ /* * Originally written by Bodo Moeller for the OpenSSL project. */ @@ -109,7 +109,8 @@ EC_GFp_mont_method(void) .field_sqr = ec_GFp_mont_field_sqr, .field_encode = ec_GFp_mont_field_encode, .field_decode = ec_GFp_mont_field_decode, - .field_set_to_one = ec_GFp_mont_field_set_to_one + .field_set_to_one = ec_GFp_mont_field_set_to_one, + .blind_coordinates = ec_GFp_simple_blind_coordinates, }; return &ret; diff --git a/src/lib/libcrypto/ec/ecp_nist.c b/src/lib/libcrypto/ec/ecp_nist.c index 6ae1170808..073c0419cf 100644 --- a/src/lib/libcrypto/ec/ecp_nist.c +++ b/src/lib/libcrypto/ec/ecp_nist.c @@ -1,4 +1,4 @@ -/* $OpenBSD: ecp_nist.c,v 1.14 2018/07/16 17:32:39 tb Exp $ */ +/* $OpenBSD: ecp_nist.c,v 1.15 2018/11/05 20:18:21 tb Exp $ */ /* * Written by Nils Larsch for the OpenSSL project. */ @@ -107,7 +107,8 @@ EC_GFp_nist_method(void) .mul_single_ct = ec_GFp_simple_mul_single_ct, .mul_double_nonct = ec_GFp_simple_mul_double_nonct, .field_mul = ec_GFp_nist_field_mul, - .field_sqr = ec_GFp_nist_field_sqr + .field_sqr = ec_GFp_nist_field_sqr, + .blind_coordinates = ec_GFp_simple_blind_coordinates, }; return &ret; diff --git a/src/lib/libcrypto/ec/ecp_nistp224.c b/src/lib/libcrypto/ec/ecp_nistp224.c index 643e9a69a6..21b431a097 100644 --- a/src/lib/libcrypto/ec/ecp_nistp224.c +++ b/src/lib/libcrypto/ec/ecp_nistp224.c @@ -1,4 +1,4 @@ -/* $OpenBSD: ecp_nistp224.c,v 1.22 2018/07/15 16:27:39 tb Exp $ */ +/* $OpenBSD: ecp_nistp224.c,v 1.23 2018/11/05 20:18:21 tb Exp $ */ /* * Written by Emilia Kasper (Google) for the OpenSSL project. */ @@ -270,7 +270,8 @@ EC_GFp_nistp224_method(void) .precompute_mult = ec_GFp_nistp224_precompute_mult, .have_precompute_mult = ec_GFp_nistp224_have_precompute_mult, .field_mul = ec_GFp_nist_field_mul, - .field_sqr = ec_GFp_nist_field_sqr + .field_sqr = ec_GFp_nist_field_sqr, + .blind_coordinates = NULL, }; return &ret; diff --git a/src/lib/libcrypto/ec/ecp_nistp256.c b/src/lib/libcrypto/ec/ecp_nistp256.c index 5c5fcde694..fc68b6cd8d 100644 --- a/src/lib/libcrypto/ec/ecp_nistp256.c +++ b/src/lib/libcrypto/ec/ecp_nistp256.c @@ -1,4 +1,4 @@ -/* $OpenBSD: ecp_nistp256.c,v 1.21 2018/07/15 16:27:39 tb Exp $ */ +/* $OpenBSD: ecp_nistp256.c,v 1.22 2018/11/05 20:18:21 tb Exp $ */ /* * Written by Adam Langley (Google) for the OpenSSL project */ @@ -1724,7 +1724,8 @@ EC_GFp_nistp256_method(void) .precompute_mult = ec_GFp_nistp256_precompute_mult, .have_precompute_mult = ec_GFp_nistp256_have_precompute_mult, .field_mul = ec_GFp_nist_field_mul, - .field_sqr = ec_GFp_nist_field_sqr + .field_sqr = ec_GFp_nist_field_sqr, + .blind_coordinates = NULL, }; return &ret; diff --git a/src/lib/libcrypto/ec/ecp_nistp521.c b/src/lib/libcrypto/ec/ecp_nistp521.c index b3525bfdad..e085610cbc 100644 --- a/src/lib/libcrypto/ec/ecp_nistp521.c +++ b/src/lib/libcrypto/ec/ecp_nistp521.c @@ -1,4 +1,4 @@ -/* $OpenBSD: ecp_nistp521.c,v 1.22 2018/07/15 16:27:39 tb Exp $ */ +/* $OpenBSD: ecp_nistp521.c,v 1.23 2018/11/05 20:18:21 tb Exp $ */ /* * Written by Adam Langley (Google) for the OpenSSL project */ @@ -1614,7 +1614,8 @@ EC_GFp_nistp521_method(void) .precompute_mult = ec_GFp_nistp521_precompute_mult, .have_precompute_mult = ec_GFp_nistp521_have_precompute_mult, .field_mul = ec_GFp_nist_field_mul, - .field_sqr = ec_GFp_nist_field_sqr + .field_sqr = ec_GFp_nist_field_sqr, + .blind_coordinates = NULL, }; return &ret; diff --git a/src/lib/libcrypto/ec/ecp_nistz256.c b/src/lib/libcrypto/ec/ecp_nistz256.c index 43010db7d0..71e0835e70 100644 --- a/src/lib/libcrypto/ec/ecp_nistz256.c +++ b/src/lib/libcrypto/ec/ecp_nistz256.c @@ -1,4 +1,4 @@ -/* $OpenBSD: ecp_nistz256.c,v 1.6 2018/07/15 16:27:39 tb Exp $ */ +/* $OpenBSD: ecp_nistz256.c,v 1.7 2018/11/05 20:18:21 tb Exp $ */ /* Copyright (c) 2014, Intel Corporation. * * Permission to use, copy, modify, and/or distribute this software for any @@ -1182,7 +1182,8 @@ EC_GFp_nistz256_method(void) .field_sqr = ec_GFp_mont_field_sqr, .field_encode = ec_GFp_mont_field_encode, .field_decode = ec_GFp_mont_field_decode, - .field_set_to_one = ec_GFp_mont_field_set_to_one + .field_set_to_one = ec_GFp_mont_field_set_to_one, + .blind_coordinates = NULL, }; return &ret; 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 * 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; -- cgit v1.2.3-55-g6feb