From 0dae8bafceabc8966383aa1f11ee8622f7dbde2f Mon Sep 17 00:00:00 2001 From: Billy Brumley Date: Tue, 24 Apr 2018 16:03:42 +0300 Subject: [PATCH] Add blinding in BN_GF2m_mod_inv for binary field inversions Reviewed-by: Richard Levitte Reviewed-by: Andy Polyakov Reviewed-by: Rich Salz (Merged from https://github.com/openssl/openssl/pull/6070) --- CHANGES | 4 ++ crypto/bn/bn_gf2m.c | 132 ++++++++++++++------------------------------ 2 files changed, 46 insertions(+), 90 deletions(-) diff --git a/CHANGES b/CHANGES index 742b673aa6..f0e23ca765 100644 --- a/CHANGES +++ b/CHANGES @@ -9,6 +9,10 @@ Changes between 1.1.0h and 1.1.1 [xx XXX xxxx] + *) Apply blinding to binary field modular inversion and remove patent + pending (OPENSSL_SUN_GF2M_DIV) BN_GF2m_mod_div implementation. + [Billy Bob Brumley] + *) Deprecate ec2_mult.c and unify scalar multiplication code paths for binary and prime elliptic curves. [Billy Bob Brumley] diff --git a/crypto/bn/bn_gf2m.c b/crypto/bn/bn_gf2m.c index 16868f79a0..287adf305a 100644 --- a/crypto/bn/bn_gf2m.c +++ b/crypto/bn/bn_gf2m.c @@ -547,7 +547,8 @@ int BN_GF2m_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) * Hernandez, J.L., and Menezes, A. "Software Implementation of Elliptic * Curve Cryptography Over Binary Fields". */ -int BN_GF2m_mod_inv(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) +static int BN_GF2m_mod_inv_vartime(BIGNUM *r, const BIGNUM *a, + const BIGNUM *p, BN_CTX *ctx) { BIGNUM *b, *c = NULL, *u = NULL, *v = NULL, *tmp; int ret = 0; @@ -713,6 +714,46 @@ int BN_GF2m_mod_inv(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) return ret; } +/*- + * Wrapper for BN_GF2m_mod_inv_vartime that blinds the input before calling. + * This is not constant time. + * But it does eliminate first order deduction on the input. + */ +int BN_GF2m_mod_inv(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) +{ + BIGNUM *b = NULL; + int ret = 0; + + BN_CTX_start(ctx); + if ((b = BN_CTX_get(ctx)) == NULL) + goto err; + + /* generate blinding value */ + do { + if (!BN_priv_rand(b, BN_num_bits(p) - 1, + BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY)) + goto err; + } while (BN_is_zero(b)); + + /* r := a * b */ + if (!BN_GF2m_mod_mul(r, a, b, p, ctx)) + goto err; + + /* r := 1/(a * b) */ + if (!BN_GF2m_mod_inv_vartime(r, r, p, ctx)) + goto err; + + /* r := b/(a * b) = 1/a */ + if (!BN_GF2m_mod_mul(r, r, b, p, ctx)) + goto err; + + ret = 1; + + err: + BN_CTX_end(ctx); + return ret; +} + /* * Invert xx, reduce modulo p, and store the result in r. r could be xx. * This function calls down to the BN_GF2m_mod_inv implementation; this @@ -740,7 +781,6 @@ int BN_GF2m_mod_inv_arr(BIGNUM *r, const BIGNUM *xx, const int p[], return ret; } -# ifndef OPENSSL_SUN_GF2M_DIV /* * Divide y by x, reduce modulo p, and store the result in r. r could be x * or y, x could equal y. @@ -771,94 +811,6 @@ int BN_GF2m_mod_div(BIGNUM *r, const BIGNUM *y, const BIGNUM *x, BN_CTX_end(ctx); return ret; } -# else -/* - * Divide y by x, reduce modulo p, and store the result in r. r could be x - * or y, x could equal y. Uses algorithm Modular_Division_GF(2^m) from - * Chang-Shantz, S. "From Euclid's GCD to Montgomery Multiplication to the - * Great Divide". - */ -int BN_GF2m_mod_div(BIGNUM *r, const BIGNUM *y, const BIGNUM *x, - const BIGNUM *p, BN_CTX *ctx) -{ - BIGNUM *a, *b, *u, *v; - int ret = 0; - - bn_check_top(y); - bn_check_top(x); - bn_check_top(p); - - BN_CTX_start(ctx); - - a = BN_CTX_get(ctx); - b = BN_CTX_get(ctx); - u = BN_CTX_get(ctx); - v = BN_CTX_get(ctx); - if (v == NULL) - goto err; - - /* reduce x and y mod p */ - if (!BN_GF2m_mod(u, y, p)) - goto err; - if (!BN_GF2m_mod(a, x, p)) - goto err; - if (!BN_copy(b, p)) - goto err; - - while (!BN_is_odd(a)) { - if (!BN_rshift1(a, a)) - goto err; - if (BN_is_odd(u)) - if (!BN_GF2m_add(u, u, p)) - goto err; - if (!BN_rshift1(u, u)) - goto err; - } - - do { - if (BN_GF2m_cmp(b, a) > 0) { - if (!BN_GF2m_add(b, b, a)) - goto err; - if (!BN_GF2m_add(v, v, u)) - goto err; - do { - if (!BN_rshift1(b, b)) - goto err; - if (BN_is_odd(v)) - if (!BN_GF2m_add(v, v, p)) - goto err; - if (!BN_rshift1(v, v)) - goto err; - } while (!BN_is_odd(b)); - } else if (BN_abs_is_word(a, 1)) - break; - else { - if (!BN_GF2m_add(a, a, b)) - goto err; - if (!BN_GF2m_add(u, u, v)) - goto err; - do { - if (!BN_rshift1(a, a)) - goto err; - if (BN_is_odd(u)) - if (!BN_GF2m_add(u, u, p)) - goto err; - if (!BN_rshift1(u, u)) - goto err; - } while (!BN_is_odd(a)); - } - } while (1); - - if (!BN_copy(r, u)) - goto err; - bn_check_top(r); - ret = 1; - - err: - BN_CTX_end(ctx); - return ret; -} -# endif /* * Divide yy by xx, reduce modulo p, and store the result in r. r could be xx -- 2.39.5