diff options
author | Billy Brumley <bbrumley@gmail.com> | 2019-02-02 10:53:29 +0200 |
---|---|---|
committer | Nicola Tuveri <nic.tuv@gmail.com> | 2019-02-17 21:02:36 +0200 |
commit | e0033efc30b0f00476bba8f0fa5512be5dc8a3f1 (patch) | |
tree | f7c0b994162419bf3040d4608d0f28397941772a /crypto | |
parent | db42bb440e76399b89fc8ae04644441a2a5f6821 (diff) |
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>
Reviewed-by: Matt Caswell <matt@openssl.org>
Reviewed-by: Nicola Tuveri <nic.tuv@gmail.com>
(Merged from https://github.com/openssl/openssl/pull/8254)
Diffstat (limited to 'crypto')
-rw-r--r-- | crypto/ec/ec2_smpl.c | 18 | ||||
-rw-r--r-- | crypto/ec/ec_err.c | 9 | ||||
-rw-r--r-- | crypto/ec/ec_lcl.h | 11 | ||||
-rw-r--r-- | crypto/ec/ecp_mont.c | 49 | ||||
-rw-r--r-- | crypto/ec/ecp_nist.c | 1 | ||||
-rw-r--r-- | crypto/ec/ecp_nistp224.c | 1 | ||||
-rw-r--r-- | crypto/ec/ecp_nistp256.c | 1 | ||||
-rw-r--r-- | crypto/ec/ecp_nistp521.c | 1 | ||||
-rw-r--r-- | crypto/ec/ecp_nistz256.c | 1 | ||||
-rw-r--r-- | crypto/ec/ecp_smpl.c | 49 | ||||
-rw-r--r-- | crypto/err/openssl.txt | 4 |
11 files changed, 141 insertions, 4 deletions
diff --git a/crypto/ec/ec2_smpl.c b/crypto/ec/ec2_smpl.c index f9d7d0860a..7bd2a63203 100644 --- a/crypto/ec/ec2_smpl.c +++ b/crypto/ec/ec2_smpl.c @@ -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) - || !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) @@ -889,6 +889,21 @@ int ec_GF2m_simple_points_mul(const EC_GROUP *group, EC_POINT *r, 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 = { @@ -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_inv, 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 1ede7c2e35..b7cf95bdd8 100644 --- 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 Apache License 2.0 (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"}, + {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), @@ -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"}, + {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), @@ -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"}, + {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), @@ -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_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), diff --git a/crypto/ec/ec_lcl.h b/crypto/ec/ec_lcl.h index 3153e4fa0d..312b538991 100644 --- a/crypto/ec/ec_lcl.h +++ b/crypto/ec/ec_lcl.h @@ -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 *); + /*- + * '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 *); @@ -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 *); +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, @@ -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 *); +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 d3d770d2a3..1654d59513 100644 --- a/crypto/ec/ecp_mont.c +++ b/crypto/ec/ecp_mont.c @@ -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_inv, 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); } +/*- + * 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 151e8ad728..9f9045b544 100644 --- a/crypto/ec/ecp_nist.c +++ b/crypto/ec/ecp_nist.c @@ -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_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 cd8b8c42c5..653965953b 100644 --- a/crypto/ec/ecp_nistp224.c +++ b/crypto/ec/ecp_nistp224.c @@ -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 3c6097698c..ee5508fade 100644 --- a/crypto/ec/ecp_nistp256.c +++ b/crypto/ec/ecp_nistp256.c @@ -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 653b8663f4..a32f3023e0 100644 --- a/crypto/ec/ecp_nistp521.c +++ b/crypto/ec/ecp_nistp521.c @@ -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_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 82affd6e6a..c0772ca2fe 100644 --- a/crypto/ec/ecp_nistz256.c +++ b/crypto/ec/ecp_nistz256.c @@ -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_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 7e8fe4fbbe..f80f98a169 100644 --- a/crypto/ec/ecp_smpl.c +++ b/crypto/ec/ecp_smpl.c @@ -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_inv, 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 { - 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; @@ -1266,7 +1267,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, } /*- + * 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: * * (X, Y ,Z ) = (lambda^2*X, lambda^3*Y, lambda*Z) diff --git a/crypto/err/openssl.txt b/crypto/err/openssl.txt index a269ac688e..8d183fb5cd 100644 --- a/crypto/err/openssl.txt +++ b/crypto/err/openssl.txt @@ -521,6 +521,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_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 @@ -537,6 +538,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_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 @@ -557,6 +559,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_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 @@ -2157,6 +2160,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_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 |