diff options
| -rw-r--r-- | crypto/bn/gcd.c | 67 | ||||
| -rw-r--r-- | crypto/rsa/blinding.c | 35 | ||||
| -rw-r--r-- | include/openssl/bn.h | 31 |
3 files changed, 90 insertions, 43 deletions
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)) { diff --git a/include/openssl/bn.h b/include/openssl/bn.h index 0b5af6a0..a8536ef3 100644 --- a/include/openssl/bn.h +++ b/include/openssl/bn.h @@ -722,20 +722,29 @@ OPENSSL_EXPORT int BN_is_prime_ex(const BIGNUM *candidate, int checks, OPENSSL_EXPORT int BN_gcd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx); -/* BN_mod_inverse sets |out| equal to |a|^-1, mod |n|. If either of |a| or |n| - * have |BN_FLG_CONSTTIME| set then the operation is performed in constant - * time. If |out| is NULL, a fresh BIGNUM is allocated. It returns the result - * or NULL on error. */ +/* BN_mod_inverse sets |out| equal to |a|^-1, mod |n|. If |out| is NULL, a + * fresh BIGNUM is allocated. It returns the result or NULL on error. + * + * If either of |a| or |n| have |BN_FLG_CONSTTIME| set then the operation is + * performed using an algorithm that avoids some branches but which isn't + * constant-time. This function shouldn't be used for secret values, even + * with |BN_FLG_CONSTTIME|; use |BN_mod_inverse_blinded| instead. Or, if + * |n| is guaranteed to be prime, use + * |BN_mod_exp_mont_consttime(out, a, m_minus_2, m, ctx, m_mont)|, taking + * advantage of Fermat's Little Theorem. */ OPENSSL_EXPORT BIGNUM *BN_mod_inverse(BIGNUM *out, const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx); -/* BN_mod_inverse_ex acts like |BN_mod_inverse| except that, when it returns - * zero, it will set |*out_no_inverse| to one if the failure was caused because - * |a| has no inverse mod |n|. Otherwise it will set |*out_no_inverse| to - * zero. */ -OPENSSL_EXPORT BIGNUM *BN_mod_inverse_ex(BIGNUM *out, int *out_no_inverse, - const BIGNUM *a, const BIGNUM *n, - BN_CTX *ctx); +/* BN_mod_inverse_blinded sets |out| equal to |a|^-1, mod |n|, where |n| is the + * Montgomery modulus for |mont|. |a| must be non-negative and must be less + * than |n|. |n| must be greater than 1. |a| is blinded (masked by a random + * value) to protect it against side-channel attacks. |BN_mod_inverse_blinded| + * may or may not ignore the |BN_FLG_CONSTTIME| flag on any/all of its inputs. + * It returns one on success or zero on failure. On failure, if the failure was + * caused by |a| having no inverse mod |n| then |*out_no_inverse| will be set + * to one; otherwise it will be set to zero. */ +int BN_mod_inverse_blinded(BIGNUM *out, int *out_no_inverse, const BIGNUM *a, + const BN_MONT_CTX *mont, BN_CTX *ctx); /* BN_kronecker returns the Kronecker symbol of |a| and |b| (which is -1, 0 or * 1), or -2 on error. */ |