From 40e48e54582e46c1a01e184ecf5bd31f4f7f8294 Mon Sep 17 00:00:00 2001 From: Billy Brumley Date: Thu, 19 Apr 2018 12:21:51 +0300 Subject: [PATCH] Elliptic curve scalar multiplication with timing attack defenses Co-authored-by: Nicola Tuveri Co-authored-by: Cesar Pereida Garcia Co-authored-by: Sohaib ul Hassan Reviewed-by: Andy Polyakov Reviewed-by: Matt Caswell (Merged from https://github.com/openssl/openssl/pull/6009) --- crypto/bn/bn_lib.c | 13 ++++ crypto/ec/ec_mult.c | 182 ++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 195 insertions(+) diff --git a/crypto/bn/bn_lib.c b/crypto/bn/bn_lib.c index 57fe45288b..a446880ec7 100644 --- a/crypto/bn/bn_lib.c +++ b/crypto/bn/bn_lib.c @@ -739,6 +739,19 @@ void BN_consttime_swap(BN_ULONG condition, BIGNUM *a, BIGNUM *b, int nwords) a->top ^= t; b->top ^= t; + t = (a->neg ^ b->neg) & condition; + a->neg ^= t; + b->neg ^= t; + + /* + * cannot just arbitrarily swap flags. + * The way a->d is allocated etc. + * BN_FLG_MALLOCED, BN_FLG_STATIC_DATA, ... + */ + t = (a->flags ^ b->flags) & condition & BN_FLG_CONSTTIME; + a->flags ^= t; + b->flags ^= t; + #define BN_CONSTTIME_SWAP(ind) \ do { \ t = (a->d[ind] ^ b->d[ind]) & condition; \ diff --git a/crypto/ec/ec_mult.c b/crypto/ec/ec_mult.c index ed26b68c30..1b9a4cf2ae 100644 --- a/crypto/ec/ec_mult.c +++ b/crypto/ec/ec_mult.c @@ -101,6 +101,166 @@ void EC_ec_pre_comp_free(EC_PRE_COMP *pre) OPENSSL_free(pre); } +#define EC_POINT_set_flags(P, flags) do { \ + BN_set_flags((P)->X, (flags)); \ + BN_set_flags((P)->Y, (flags)); \ + BN_set_flags((P)->Z, (flags)); \ +} while(0) + +/* + * This functions computes (in constant time) a point multiplication over the + * EC group. + * + * It performs either a fixed scalar point multiplication + * (scalar * generator) + * when point is NULL, or a generic scalar point multiplication + * (scalar * point) + * when point is not NULL. + * + * scalar should be in the range [0,n) otherwise all constant time bets are off. + * + * NB: This says nothing about EC_POINT_add and EC_POINT_dbl, + * which of course are not constant time themselves. + * + * The product is stored in r. + * + * Returns 1 on success, 0 otherwise. + */ +static int ec_mul_consttime(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar, + const EC_POINT *point, BN_CTX *ctx) +{ + int i, order_bits, group_top, kbit, pbit, Z_is_one, ret; + ret = 0; + EC_POINT *s = NULL; + BIGNUM *k = NULL; + BIGNUM *lambda = NULL; + BN_CTX *new_ctx = NULL; + + if (ctx == NULL) + if ((ctx = new_ctx = BN_CTX_secure_new()) == NULL) + return 0; + + if ((group->order == NULL) || (group->field == NULL)) + goto err; + + order_bits = BN_num_bits(group->order); + + s = EC_POINT_new(group); + if (s == NULL) + goto err; + + if (point == NULL) { + if (group->generator == NULL) + goto err; + if (!EC_POINT_copy(s, group->generator)) + goto err; + } else { + if (!EC_POINT_copy(s, point)) + goto err; + } + + EC_POINT_set_flags(s, BN_FLG_CONSTTIME); + + BN_CTX_start(ctx); + lambda = BN_CTX_get(ctx); + k = BN_CTX_get(ctx); + if (k == NULL) + goto err; + + /* + * Group orders are often on a word boundary. + * So when we pad the scalar, some timing diff might + * pop if it needs to be expanded due to carries. + * So expand ahead of time. + */ + group_top = bn_get_top(group->order); + if ((bn_wexpand(k, group_top + 1) == NULL) + || (bn_wexpand(lambda, group_top + 1) == NULL)) + goto err; + + if (!BN_copy(k, scalar)) + goto err; + + BN_set_flags(k, BN_FLG_CONSTTIME); + + if ((BN_num_bits(k) > order_bits) || (BN_is_negative(k))) { + /* + * this is an unusual input, and we don't guarantee + * constant-timeness + */ + if(!BN_nnmod(k, k, group->order, ctx)) + goto err; + } + + if (!BN_add(lambda, k, group->order)) + goto err; + BN_set_flags(lambda, BN_FLG_CONSTTIME); + if (!BN_add(k, lambda, group->order)) + goto err; + /* + * lambda := scalar + order + * k := scalar + 2*order + */ + kbit = BN_is_bit_set(lambda, order_bits); + BN_consttime_swap(kbit, k, lambda, group_top + 1); + + group_top = bn_get_top(group->field); + if ((bn_wexpand(s->X, group_top) == NULL) + || (bn_wexpand(s->Y, group_top) == NULL) + || (bn_wexpand(s->Z, group_top) == NULL) + || (bn_wexpand(r->X, group_top) == NULL) + || (bn_wexpand(r->Y, group_top) == NULL) + || (bn_wexpand(r->Z, group_top) == NULL)) + goto err; + + /* top bit is a 1, in a fixed pos */ + if (!EC_POINT_copy(r, s)) + goto err; + + EC_POINT_set_flags(r, BN_FLG_CONSTTIME); + + if (!EC_POINT_dbl(group, s, s, ctx)) + goto err; + + pbit = 0; + +#define EC_POINT_CSWAP(c, a, b, w, t) do { \ + BN_consttime_swap(c, (a)->X, (b)->X, w); \ + BN_consttime_swap(c, (a)->Y, (b)->Y, w); \ + BN_consttime_swap(c, (a)->Z, (b)->Z, w); \ + t = ((a)->Z_is_one ^ (b)->Z_is_one) & (c); \ + (a)->Z_is_one ^= (t); \ + (b)->Z_is_one ^= (t); \ +} while(0) + + for (i = order_bits - 1; i >= 0; i--) { + kbit = BN_is_bit_set(k, i) ^ pbit; + EC_POINT_CSWAP(kbit, r, s, group_top, Z_is_one); + if (!EC_POINT_add(group, s, r, s, ctx)) + goto err; + if (!EC_POINT_dbl(group, r, r, ctx)) + goto err; + /* + * pbit logic merges this cswap with that of the + * next iteration + */ + pbit ^= kbit; + } + /* one final cswap to move the right value into r */ + EC_POINT_CSWAP(pbit, r, s, group_top, Z_is_one); +#undef EC_POINT_CSWAP + + ret = 1; + +err: + EC_POINT_free(s); + BN_CTX_end(ctx); + BN_CTX_free(new_ctx); + + return ret; +} +#undef EC_POINT_set_flags + /* * TODO: table should be optimised for the wNAF-based implementation, * sometimes smaller windows will give better performance (thus the @@ -126,6 +286,28 @@ int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar, size_t num, const EC_POINT *points[], const BIGNUM *scalars[], BN_CTX *ctx) { + if ((scalar != NULL) && (num == 0)) { + /* In this case we want to compute scalar * GeneratorPoint: + * this codepath is reached most prominently by (ephemeral) key + * generation of EC cryptosystems (i.e. ECDSA keygen and sign setup, + * ECDH keygen/first half), where the scalar is always secret. + * This is why we ignore if BN_FLG_CONSTTIME is actually set and we + * always call the constant time version. + */ + return ec_mul_consttime(group, r, scalar, NULL, ctx); + } + + if ((scalar == NULL) && (num == 1)) { + /* In this case we want to compute scalar * GenericPoint: + * this codepath is reached most prominently by the second half of + * ECDH, where the secret scalar is multiplied by the peer's public + * point. + * To protect the secret scalar, we ignore if BN_FLG_CONSTTIME is + * actually set and we always call the constant time version. + */ + return ec_mul_consttime(group, r, scalars[0], points[0], ctx); + } + BN_CTX *new_ctx = NULL; const EC_POINT *generator = NULL; EC_POINT *tmp = NULL; -- 2.25.1