Don't bother retrying in bn_blinding_create_param.
The probability of stumbling on a non-invertible b->A is negligible;
it's equivalent to accidentally factoring the RSA key. Relatedly,
document the slight caveat in BN_mod_inverse_blinded.
Change-Id: I308d17d12f5d6a12c444dda8c8fcc175ef2f5d45
Reviewed-on: https://boringssl-review.googlesource.com/26344
Commit-Queue: David Benjamin <davidben@google.com>
CQ-Verified: CQ bot account: commit-bot@chromium.org <commit-bot@chromium.org>
Reviewed-by: Adam Langley <agl@google.com>
diff --git a/crypto/fipsmodule/rsa/blinding.c b/crypto/fipsmodule/rsa/blinding.c
index d956057..b05f9c9 100644
--- a/crypto/fipsmodule/rsa/blinding.c
+++ b/crypto/fipsmodule/rsa/blinding.c
@@ -215,46 +215,22 @@
static int bn_blinding_create_param(BN_BLINDING *b, const BIGNUM *e,
const BN_MONT_CTX *mont, BN_CTX *ctx) {
- int retry_counter = 32;
-
- do {
- if (!BN_rand_range_ex(b->A, 1, &mont->N)) {
- OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
- return 0;
- }
-
- // |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_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)) {
- OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
- return 0;
- }
-
- if (!BN_to_montgomery(b->A, b->A, mont, ctx)) {
+ int no_inverse;
+ if (!BN_rand_range_ex(b->A, 1, &mont->N) ||
+ // Compute |b->A|^-1 in Montgomery form. Note |BN_from_montgomery| +
+ // |BN_mod_inverse_blinded| is equivalent to, but more efficient than,
+ // |BN_mod_inverse_blinded| + |BN_to_montgomery|.
+ //
+ // We do not retry if |b->A| has no inverse. Finding a non-invertible
+ // value of |b->A| is equivalent to factoring |mont->N|. There is
+ // negligible probability of stumbling on one at random.
+ !BN_from_montgomery(b->Ai, b->A, mont, ctx) ||
+ !BN_mod_inverse_blinded(b->Ai, &no_inverse, b->Ai, mont, ctx) ||
+ // TODO(davidben): |BN_mod_exp_mont| internally computes the result in
+ // Montgomery form. Save a pair of Montgomery reductions and a
+ // multiplication by returning that value directly.
+ !BN_mod_exp_mont(b->A, b->A, e, &mont->N, ctx, mont) ||
+ !BN_to_montgomery(b->A, b->A, mont, ctx)) {
OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
return 0;
}
diff --git a/include/openssl/bn.h b/include/openssl/bn.h
index 871ba33..9fd2509 100644
--- a/include/openssl/bn.h
+++ b/include/openssl/bn.h
@@ -773,6 +773,10 @@
// value) to protect it against side-channel attacks. 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.
+//
+// Note this function may incorrectly report |a| has no inverse if the random
+// blinding value has no inverse. It should only be used when |n| has few
+// non-invertible elements, such as an RSA modulus.
int BN_mod_inverse_blinded(BIGNUM *out, int *out_no_inverse, const BIGNUM *a,
const BN_MONT_CTX *mont, BN_CTX *ctx);
