From ec3cb3adbcdf03b1017f5f9d14943e1ad6bc13b7 Mon Sep 17 00:00:00 2001 From: Brian Smith Date: Mon, 25 Jul 2016 15:35:20 -1000 Subject: Add |BN_mod_inverse_blinded| and use it in RSA blinding. Yo dawg I herd you like blinding so I put inversion blinding in your RSA blinding so you can randomly mask your random mask. This improves upon the current situation where we pretend that |BN_mod_inverse_no_branch| is constant-time, and it avoids the need to exert a lot of effort to make a actually-constant-time modular inversion function just for RSA blinding. Note that if the random number generator weren't working correctly then the blinding of the inversion wouldn't be very effective, but in that case the RSA blinding itself would probably be completely busted, so we're not really losing anything by relying on blinding to blind the blinding. Change-Id: I771100f0ad8ed3c24e80dd859ec22463ef2a194f Reviewed-on: https://boringssl-review.googlesource.com/8923 Reviewed-by: Adam Langley Commit-Queue: Adam Langley CQ-Verified: CQ bot account: commit-bot@chromium.org --- crypto/bn/gcd.c | 67 +++++++++++++++++++++++++++++++++++++++++---------- crypto/rsa/blinding.c | 35 ++++++++++++--------------- 2 files changed, 70 insertions(+), 32 deletions(-) (limited to 'crypto') diff --git a/crypto/bn/gcd.c b/crypto/bn/gcd.c index 52db5698..0cc18d91 100644 --- a/crypto/bn/gcd.c +++ b/crypto/bn/gcd.c @@ -227,17 +227,13 @@ static BIGNUM *BN_mod_inverse_no_branch(BIGNUM *out, int *out_no_inverse, const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx); -BIGNUM *BN_mod_inverse_ex(BIGNUM *out, int *out_no_inverse, const BIGNUM *a, - const BIGNUM *n, BN_CTX *ctx) { +static BIGNUM *bn_mod_inverse_ex(BIGNUM *out, int *out_no_inverse, + const BIGNUM *a, const BIGNUM *n, + BN_CTX *ctx) { BIGNUM *A, *B, *X, *Y, *M, *D, *T, *R = NULL; BIGNUM *ret = NULL; int sign; - if ((a->flags & BN_FLG_CONSTTIME) != 0 || - (n->flags & BN_FLG_CONSTTIME) != 0) { - return BN_mod_inverse_no_branch(out, out_no_inverse, a, n, ctx); - } - *out_no_inverse = 0; BN_CTX_start(ctx); @@ -266,11 +262,6 @@ BIGNUM *BN_mod_inverse_ex(BIGNUM *out, int *out_no_inverse, const BIGNUM *a, goto err; } A->neg = 0; - if (B->neg || (BN_ucmp(B, A) >= 0)) { - if (!BN_nnmod(B, B, A, ctx)) { - goto err; - } - } sign = -1; /* From B = a mod |n|, A = |n| it follows that * @@ -543,7 +534,57 @@ err: BIGNUM *BN_mod_inverse(BIGNUM *out, const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx) { int no_inverse; - return BN_mod_inverse_ex(out, &no_inverse, a, n, ctx); + + if ((a->flags & BN_FLG_CONSTTIME) != 0 || + (n->flags & BN_FLG_CONSTTIME) != 0) { + return BN_mod_inverse_no_branch(out, &no_inverse, a, n, ctx); + } + + if (!a->neg && BN_ucmp(a, n) < 0) { + return bn_mod_inverse_ex(out, &no_inverse, a, n, ctx); + } + + BIGNUM a_reduced; + BN_init(&a_reduced); + BIGNUM *ret = NULL; + + if (!BN_nnmod(&a_reduced, a, n, ctx)) { + goto err; + } + + ret = bn_mod_inverse_ex(out, &no_inverse, &a_reduced, n, ctx); + +err: + BN_free(&a_reduced); + return ret; +} + +int BN_mod_inverse_blinded(BIGNUM *out, int *out_no_inverse, const BIGNUM *a, + const BN_MONT_CTX *mont, BN_CTX *ctx) { + *out_no_inverse = 0; + + if (BN_is_negative(a) || BN_cmp(a, &mont->N) >= 0) { + OPENSSL_PUT_ERROR(BN, BN_R_INPUT_NOT_REDUCED); + return 0; + } + + int ret = 0; + BIGNUM blinding_factor; + BN_init(&blinding_factor); + + if (!BN_rand_range_ex(&blinding_factor, 1, &mont->N) || + !BN_mod_mul_montgomery(out, &blinding_factor, a, mont, ctx) || + bn_mod_inverse_ex(out, out_no_inverse, out, &mont->N, ctx) == NULL || + !BN_mod_mul_montgomery(out, &blinding_factor, out, mont, ctx)) { + OPENSSL_PUT_ERROR(BN, ERR_R_BN_LIB); + goto err; + } + + ret = 1; + +err: + BN_free(&blinding_factor); + return ret; } /* BN_mod_inverse_no_branch is a special version of BN_mod_inverse. diff --git a/crypto/rsa/blinding.c b/crypto/rsa/blinding.c index 71f2e6f8..0a485ee9 100644 --- a/crypto/rsa/blinding.c +++ b/crypto/rsa/blinding.c @@ -216,9 +216,6 @@ int BN_BLINDING_invert(BIGNUM *n, const BN_BLINDING *b, BN_MONT_CTX *mont, static int bn_blinding_create_param(BN_BLINDING *b, const BIGNUM *e, const BN_MONT_CTX *mont, BN_CTX *ctx) { - BIGNUM mont_N_consttime; - BN_init(&mont_N_consttime); - BN_with_flags(&mont_N_consttime, &mont->N, BN_FLG_CONSTTIME); int retry_counter = 32; do { @@ -227,30 +224,30 @@ static int bn_blinding_create_param(BN_BLINDING *b, const BIGNUM *e, return 0; } - /* |BN_from_montgomery| + |BN_mod_inverse_no_branch| is equivalent to, but - * more efficient than, |BN_mod_inverse_no_branch| + |BN_to_montgomery|. */ + /* |BN_from_montgomery| + |BN_mod_inverse_blinded| is equivalent to, but + * more efficient than, |BN_mod_inverse_blinded| + |BN_to_montgomery|. */ if (!BN_from_montgomery(b->Ai, b->A, mont, ctx)) { OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR); return 0; } int no_inverse; - if (BN_mod_inverse_ex(b->Ai, &no_inverse, b->Ai, &mont_N_consttime, ctx) == - NULL) { - /* this should almost never happen for good RSA keys */ - if (no_inverse) { - if (retry_counter-- == 0) { - OPENSSL_PUT_ERROR(RSA, RSA_R_TOO_MANY_ITERATIONS); - return 0; - } - ERR_clear_error(); - } else { - OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR); - return 0; - } - } else { + if (BN_mod_inverse_blinded(b->Ai, &no_inverse, b->Ai, mont, ctx)) { break; } + + if (!no_inverse) { + OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR); + return 0; + } + + /* For reasonably-sized RSA keys, it should almost never be the case that a + * random value doesn't have an inverse. */ + if (retry_counter-- == 0) { + OPENSSL_PUT_ERROR(RSA, RSA_R_TOO_MANY_ITERATIONS); + return 0; + } + ERR_clear_error(); } while (1); if (!BN_mod_exp_mont(b->A, b->A, e, &mont->N, ctx, mont)) { -- cgit v1.2.3