From fe6f3fc2532579fc0941a1603d5e19a11a013179 Mon Sep 17 00:00:00 2001 From: beck <> Date: Wed, 25 Jan 2017 06:15:44 +0000 Subject: Construct a BN_gcd_nonct, based on BN_mod_inverse_no_branch, as suggested by Alejandro Cabrera to avoid the possibility of a sidechannel timing attack during RSA private key generation. Modify BN_gcd to become not visible under LIBRESSL_INTERNAL and force the use of the _ct or _nonct versions of the function only within the library. ok jsing@ --- src/lib/libcrypto/bn/bn.h | 4 +- src/lib/libcrypto/bn/bn_gcd.c | 158 +++++++++++++++++++++++++++++++++++++++- src/lib/libcrypto/bn/bn_lcl.h | 4 +- src/lib/libcrypto/bn/bn_x931p.c | 4 +- src/lib/libcrypto/rsa/rsa_chk.c | 4 +- src/lib/libcrypto/rsa/rsa_gen.c | 6 +- 6 files changed, 170 insertions(+), 10 deletions(-) (limited to 'src') diff --git a/src/lib/libcrypto/bn/bn.h b/src/lib/libcrypto/bn/bn.h index 5d5de7e43a..0dde08a368 100644 --- a/src/lib/libcrypto/bn/bn.h +++ b/src/lib/libcrypto/bn/bn.h @@ -1,4 +1,4 @@ -/* $OpenBSD: bn.h,v 1.35 2017/01/21 11:00:46 beck Exp $ */ +/* $OpenBSD: bn.h,v 1.36 2017/01/25 06:15:44 beck Exp $ */ /* Copyright (C) 1995-1997 Eric Young (eay@cryptsoft.com) * All rights reserved. * @@ -452,7 +452,9 @@ char * BN_bn2dec(const BIGNUM *a); int BN_hex2bn(BIGNUM **a, const char *str); int BN_dec2bn(BIGNUM **a, const char *str); int BN_asc2bn(BIGNUM **a, const char *str); +#ifndef LIBRESSL_INTERNAL int BN_gcd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx); +#endif int BN_kronecker(const BIGNUM *a,const BIGNUM *b,BN_CTX *ctx); /* returns -2 for error */ #ifndef LIBRESSL_INTERNAL BIGNUM *BN_mod_inverse(BIGNUM *ret, diff --git a/src/lib/libcrypto/bn/bn_gcd.c b/src/lib/libcrypto/bn/bn_gcd.c index 30896e4763..e2574c3304 100644 --- a/src/lib/libcrypto/bn/bn_gcd.c +++ b/src/lib/libcrypto/bn/bn_gcd.c @@ -1,4 +1,4 @@ -/* $OpenBSD: bn_gcd.c,v 1.13 2017/01/21 23:02:53 beck Exp $ */ +/* $OpenBSD: bn_gcd.c,v 1.14 2017/01/25 06:15:44 beck Exp $ */ /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) * All rights reserved. * @@ -114,6 +114,8 @@ #include "bn_lcl.h" static BIGNUM *euclid(BIGNUM *a, BIGNUM *b); +static BIGNUM *BN_gcd_no_branch(BIGNUM *in, const BIGNUM *a, const BIGNUM *n, + BN_CTX *ctx); int BN_gcd(BIGNUM *r, const BIGNUM *in_a, const BIGNUM *in_b, BN_CTX *ctx) @@ -156,6 +158,21 @@ err: return (ret); } +int +BN_gcd_ct(BIGNUM *r, const BIGNUM *in_a, const BIGNUM *in_b, BN_CTX *ctx) +{ + if (BN_gcd_no_branch(r, in_a, in_b, ctx) == NULL) + return 0; + return 1; +} + +int +BN_gcd_nonct(BIGNUM *r, const BIGNUM *in_a, const BIGNUM *in_b, BN_CTX *ctx) +{ + return BN_gcd(r, in_a, in_b, ctx); +} + + static BIGNUM * euclid(BIGNUM *a, BIGNUM *b) { @@ -704,3 +721,142 @@ err: bn_check_top(ret); return (ret); } + +/* + * BN_gcd_no_branch is a special version of BN_mod_inverse_no_branch. + * that returns the GCD. + */ +static BIGNUM * +BN_gcd_no_branch(BIGNUM *in, const BIGNUM *a, const BIGNUM *n, + BN_CTX *ctx) +{ + BIGNUM *A, *B, *X, *Y, *M, *D, *T, *R = NULL; + BIGNUM local_A, local_B; + BIGNUM *pA, *pB; + BIGNUM *ret = NULL; + int sign; + + if (in == NULL) + goto err; + R = in; + + bn_check_top(a); + bn_check_top(n); + + BN_CTX_start(ctx); + if ((A = BN_CTX_get(ctx)) == NULL) + goto err; + if ((B = BN_CTX_get(ctx)) == NULL) + goto err; + if ((X = BN_CTX_get(ctx)) == NULL) + goto err; + if ((D = BN_CTX_get(ctx)) == NULL) + goto err; + if ((M = BN_CTX_get(ctx)) == NULL) + goto err; + if ((Y = BN_CTX_get(ctx)) == NULL) + goto err; + if ((T = BN_CTX_get(ctx)) == NULL) + goto err; + + BN_one(X); + BN_zero(Y); + if (BN_copy(B, a) == NULL) + goto err; + if (BN_copy(A, n) == NULL) + goto err; + A->neg = 0; + + if (B->neg || (BN_ucmp(B, A) >= 0)) { + /* Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked, + * BN_div_no_branch will be called eventually. + */ + pB = &local_B; + BN_with_flags(pB, B, BN_FLG_CONSTTIME); + if (!BN_nnmod(B, pB, A, ctx)) + goto err; + } + sign = -1; + /* From B = a mod |n|, A = |n| it follows that + * + * 0 <= B < A, + * -sign*X*a == B (mod |n|), + * sign*Y*a == A (mod |n|). + */ + + while (!BN_is_zero(B)) { + BIGNUM *tmp; + + /* + * 0 < B < A, + * (*) -sign*X*a == B (mod |n|), + * sign*Y*a == A (mod |n|) + */ + + /* Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked, + * BN_div_no_branch will be called eventually. + */ + pA = &local_A; + BN_with_flags(pA, A, BN_FLG_CONSTTIME); + + /* (D, M) := (A/B, A%B) ... */ + if (!BN_div_ct(D, M, pA, B, ctx)) + goto err; + + /* Now + * A = D*B + M; + * thus we have + * (**) sign*Y*a == D*B + M (mod |n|). + */ + tmp = A; /* keep the BIGNUM object, the value does not matter */ + + /* (A, B) := (B, A mod B) ... */ + A = B; + B = M; + /* ... so we have 0 <= B < A again */ + + /* Since the former M is now B and the former B is now A, + * (**) translates into + * sign*Y*a == D*A + B (mod |n|), + * i.e. + * sign*Y*a - D*A == B (mod |n|). + * Similarly, (*) translates into + * -sign*X*a == A (mod |n|). + * + * Thus, + * sign*Y*a + D*sign*X*a == B (mod |n|), + * i.e. + * sign*(Y + D*X)*a == B (mod |n|). + * + * So if we set (X, Y, sign) := (Y + D*X, X, -sign), we arrive back at + * -sign*X*a == B (mod |n|), + * sign*Y*a == A (mod |n|). + * Note that X and Y stay non-negative all the time. + */ + + if (!BN_mul(tmp, D, X, ctx)) + goto err; + if (!BN_add(tmp, tmp, Y)) + goto err; + + M = Y; /* keep the BIGNUM object, the value does not matter */ + Y = X; + X = tmp; + sign = -sign; + } + + /* + * The while loop (Euclid's algorithm) ends when + * A == gcd(a,n); + */ + + if (!BN_copy(R, A)) + goto err; + ret = R; +err: + if ((ret == NULL) && (in == NULL)) + BN_free(R); + BN_CTX_end(ctx); + bn_check_top(ret); + return (ret); +} diff --git a/src/lib/libcrypto/bn/bn_lcl.h b/src/lib/libcrypto/bn/bn_lcl.h index 75c35499a8..c010410cd1 100644 --- a/src/lib/libcrypto/bn/bn_lcl.h +++ b/src/lib/libcrypto/bn/bn_lcl.h @@ -1,4 +1,4 @@ -/* $OpenBSD: bn_lcl.h,v 1.26 2017/01/21 11:00:46 beck Exp $ */ +/* $OpenBSD: bn_lcl.h,v 1.27 2017/01/25 06:15:44 beck Exp $ */ /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) * All rights reserved. * @@ -603,5 +603,7 @@ BIGNUM *BN_mod_inverse_ct(BIGNUM *ret, const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx); BIGNUM *BN_mod_inverse_nonct(BIGNUM *ret, const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx); +int BN_gcd_ct(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx); +int BN_gcd_nonct(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx); __END_HIDDEN_DECLS #endif diff --git a/src/lib/libcrypto/bn/bn_x931p.c b/src/lib/libcrypto/bn/bn_x931p.c index 84c998d4e1..45b61c9128 100644 --- a/src/lib/libcrypto/bn/bn_x931p.c +++ b/src/lib/libcrypto/bn/bn_x931p.c @@ -1,4 +1,4 @@ -/* $OpenBSD: bn_x931p.c,v 1.9 2017/01/21 11:00:46 beck Exp $ */ +/* $OpenBSD: bn_x931p.c,v 1.10 2017/01/25 06:15:44 beck Exp $ */ /* Written by Dr Stephen N Henson (steve@openssl.org) for the OpenSSL * project 2005. */ @@ -171,7 +171,7 @@ BN_X931_derive_prime_ex(BIGNUM *p, BIGNUM *p1, BIGNUM *p2, const BIGNUM *Xp, goto err; if (!BN_sub_word(pm1, 1)) goto err; - if (!BN_gcd(t, pm1, e, ctx)) + if (!BN_gcd_ct(t, pm1, e, ctx)) goto err; if (BN_is_one(t) /* X9.31 specifies 8 MR and 1 Lucas test or any prime test diff --git a/src/lib/libcrypto/rsa/rsa_chk.c b/src/lib/libcrypto/rsa/rsa_chk.c index 91616d17cb..dd9104f304 100644 --- a/src/lib/libcrypto/rsa/rsa_chk.c +++ b/src/lib/libcrypto/rsa/rsa_chk.c @@ -1,4 +1,4 @@ -/* $OpenBSD: rsa_chk.c,v 1.11 2017/01/21 11:00:47 beck Exp $ */ +/* $OpenBSD: rsa_chk.c,v 1.12 2017/01/25 06:15:44 beck Exp $ */ /* ==================================================================== * Copyright (c) 1999 The OpenSSL Project. All rights reserved. * @@ -129,7 +129,7 @@ RSA_check_key(const RSA *key) ret = -1; goto err; } - r = BN_gcd(m, i, j, ctx); + r = BN_gcd_ct(m, i, j, ctx); if (!r) { ret = -1; goto err; diff --git a/src/lib/libcrypto/rsa/rsa_gen.c b/src/lib/libcrypto/rsa/rsa_gen.c index 300b292b7b..e09dccb4a8 100644 --- a/src/lib/libcrypto/rsa/rsa_gen.c +++ b/src/lib/libcrypto/rsa/rsa_gen.c @@ -1,4 +1,4 @@ -/* $OpenBSD: rsa_gen.c,v 1.20 2017/01/21 11:00:47 beck Exp $ */ +/* $OpenBSD: rsa_gen.c,v 1.21 2017/01/25 06:15:44 beck Exp $ */ /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) * All rights reserved. * @@ -138,7 +138,7 @@ rsa_builtin_keygen(RSA *rsa, int bits, BIGNUM *e_value, BN_GENCB *cb) goto err; if (!BN_sub(r2, rsa->p, BN_value_one())) goto err; - if (!BN_gcd(r1, r2, rsa->e, ctx)) + if (!BN_gcd_ct(r1, r2, rsa->e, ctx)) goto err; if (BN_is_one(r1)) break; @@ -168,7 +168,7 @@ rsa_builtin_keygen(RSA *rsa, int bits, BIGNUM *e_value, BN_GENCB *cb) } if (!BN_sub(r2, rsa->q, BN_value_one())) goto err; - if (!BN_gcd(r1, r2, rsa->e, ctx)) + if (!BN_gcd_ct(r1, r2, rsa->e, ctx)) goto err; if (BN_is_one(r1)) break; -- cgit v1.2.3-55-g6feb