Rearrange ECDSA implementation. The extra computation in the "setup" half is a remnant of ECDSA_sign_setup, which was designed to amortize the message-independent portion of the signature. We don't care about this amortization, but we do want some control over k for testing. Instead, have ecdsa_sign_impl take k and do the rest. In doing so, this lets us compute m and kinv slightly later, which means fewer temporaries are needed. Bug: 391 Change-Id: I398004a5388ce5b7e839db6c36edf8464643d16f Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/45866 Commit-Queue: David Benjamin <davidben@google.com> Reviewed-by: Adam Langley <agl@google.com>
diff --git a/crypto/fipsmodule/ecdsa/ecdsa.c b/crypto/fipsmodule/ecdsa/ecdsa.c index 096b615..e519a69 100644 --- a/crypto/fipsmodule/ecdsa/ecdsa.c +++ b/crypto/fipsmodule/ecdsa/ecdsa.c
@@ -198,65 +198,66 @@ return 1; } -static int ecdsa_sign_setup(const EC_KEY *eckey, EC_SCALAR *out_kinv_mont, - EC_SCALAR *out_r, const uint8_t *digest, - size_t digest_len, const EC_SCALAR *priv_key) { +static ECDSA_SIG *ecdsa_sign_impl(const EC_GROUP *group, int *out_retry, + const EC_SCALAR *priv_key, const EC_SCALAR *k, + const uint8_t *digest, size_t digest_len) { + *out_retry = 0; + // Check that the size of the group order is FIPS compliant (FIPS 186-4 // B.5.2). - const EC_GROUP *group = EC_KEY_get0_group(eckey); const BIGNUM *order = EC_GROUP_get0_order(group); if (BN_num_bits(order) < 160) { OPENSSL_PUT_ERROR(ECDSA, EC_R_INVALID_GROUP_ORDER); - return 0; + return NULL; } - int ret = 0; - EC_SCALAR k; + // Compute r, the x-coordinate of k * generator. EC_RAW_POINT tmp_point; - do { - // Include the private key and message digest in the k generation. - if (eckey->fixed_k != NULL) { - if (!ec_bignum_to_scalar(group, &k, eckey->fixed_k)) { - goto err; - } - if (ec_scalar_is_zero(group, &k)) { - OPENSSL_PUT_ERROR(ECDSA, ERR_R_INTERNAL_ERROR); - goto err; - } - } else { - // Pass a SHA512 hash of the private key and digest as additional data - // into the RBG. This is a hardening measure against entropy failure. - OPENSSL_STATIC_ASSERT(SHA512_DIGEST_LENGTH >= 32, - "additional_data is too large for SHA-512"); - SHA512_CTX sha; - uint8_t additional_data[SHA512_DIGEST_LENGTH]; - SHA512_Init(&sha); - SHA512_Update(&sha, priv_key->words, order->width * sizeof(BN_ULONG)); - SHA512_Update(&sha, digest, digest_len); - SHA512_Final(additional_data, &sha); - if (!ec_random_nonzero_scalar(group, &k, additional_data)) { - goto err; - } - } + EC_SCALAR r; + if (!ec_point_mul_scalar_base(group, &tmp_point, k) || + !ec_get_x_coordinate_as_scalar(group, &r, &tmp_point)) { + return NULL; + } - // Compute k^-1 in the Montgomery domain. This is |ec_scalar_to_montgomery| - // followed by |ec_scalar_inv0_montgomery|, but |ec_scalar_inv0_montgomery| - // followed by |ec_scalar_from_montgomery| is equivalent and slightly more - // efficient. Note k is non-zero, so the inverse must exist. - ec_scalar_inv0_montgomery(group, out_kinv_mont, &k); - ec_scalar_from_montgomery(group, out_kinv_mont, out_kinv_mont); + if (ec_scalar_is_zero(group, &r)) { + *out_retry = 1; + return NULL; + } - // Compute r, the x-coordinate of generator * k. - if (!ec_point_mul_scalar_base(group, &tmp_point, &k) || - !ec_get_x_coordinate_as_scalar(group, out_r, &tmp_point)) { - goto err; - } - } while (ec_scalar_is_zero(group, out_r)); + // s = priv_key * r. Note if only one parameter is in the Montgomery domain, + // |ec_scalar_mod_mul_montgomery| will compute the answer in the normal + // domain. + EC_SCALAR s; + ec_scalar_to_montgomery(group, &s, &r); + ec_scalar_mul_montgomery(group, &s, priv_key, &s); - ret = 1; + // s = m + priv_key * r. + EC_SCALAR tmp; + digest_to_scalar(group, &tmp, digest, digest_len); + ec_scalar_add(group, &s, &s, &tmp); -err: - OPENSSL_cleanse(&k, sizeof(k)); + // s = k^-1 * (m + priv_key * r). First, we compute k^-1 in the Montgomery + // domain. This is |ec_scalar_to_montgomery| followed by + // |ec_scalar_inv0_montgomery|, but |ec_scalar_inv0_montgomery| followed by + // |ec_scalar_from_montgomery| is equivalent and slightly more efficient. + // Then, as above, only one parameter is in the Montgomery domain, so the + // result is in the normal domain. Finally, note k is non-zero (or computing r + // would fail), so the inverse must exist. + ec_scalar_inv0_montgomery(group, &tmp, k); // tmp = k^-1 R^2 + ec_scalar_from_montgomery(group, &tmp, &tmp); // tmp = k^-1 R + ec_scalar_mul_montgomery(group, &s, &s, &tmp); + if (ec_scalar_is_zero(group, &s)) { + *out_retry = 1; + return NULL; + } + + ECDSA_SIG *ret = ECDSA_SIG_new(); + if (ret == NULL || // + !bn_set_words(ret->r, r.words, order->width) || + !bn_set_words(ret->s, s.words, order->width)) { + ECDSA_SIG_free(ret); + return NULL; + } return ret; } @@ -275,54 +276,37 @@ const BIGNUM *order = EC_GROUP_get0_order(group); const EC_SCALAR *priv_key = &eckey->priv_key->scalar; - int ok = 0; - ECDSA_SIG *ret = ECDSA_SIG_new(); - EC_SCALAR kinv_mont, r_mont, s, m, tmp; - if (ret == NULL) { - OPENSSL_PUT_ERROR(ECDSA, ERR_R_MALLOC_FAILURE); - return NULL; - } - - digest_to_scalar(group, &m, digest, digest_len); for (;;) { - if (!ecdsa_sign_setup(eckey, &kinv_mont, &r_mont, digest, digest_len, - priv_key) || - !bn_set_words(ret->r, r_mont.words, order->width)) { - goto err; + EC_SCALAR k; + if (eckey->fixed_k != NULL) { + if (!ec_bignum_to_scalar(group, &k, eckey->fixed_k)) { + return NULL; + } + if (ec_scalar_is_zero(group, &k)) { + OPENSSL_PUT_ERROR(ECDSA, ERR_R_INTERNAL_ERROR); + return NULL; + } + } else { + // Pass a SHA512 hash of the private key and digest as additional data + // into the RBG. This is a hardening measure against entropy failure. + OPENSSL_STATIC_ASSERT(SHA512_DIGEST_LENGTH >= 32, + "additional_data is too large for SHA-512"); + SHA512_CTX sha; + uint8_t additional_data[SHA512_DIGEST_LENGTH]; + SHA512_Init(&sha); + SHA512_Update(&sha, priv_key->words, order->width * sizeof(BN_ULONG)); + SHA512_Update(&sha, digest, digest_len); + SHA512_Final(additional_data, &sha); + if (!ec_random_nonzero_scalar(group, &k, additional_data)) { + return NULL; + } } - // Compute priv_key * r (mod order). Note if only one parameter is in the - // Montgomery domain, |ec_scalar_mod_mul_montgomery| will compute the answer - // in the normal domain. - ec_scalar_to_montgomery(group, &r_mont, &r_mont); - ec_scalar_mul_montgomery(group, &s, priv_key, &r_mont); - - // Compute tmp = m + priv_key * r. - ec_scalar_add(group, &tmp, &m, &s); - - // Finally, multiply s by k^-1. That was retained in Montgomery form, so the - // same technique as the previous multiplication works. - ec_scalar_mul_montgomery(group, &s, &tmp, &kinv_mont); - if (!bn_set_words(ret->s, s.words, order->width)) { - goto err; - } - if (!BN_is_zero(ret->s)) { - // s != 0 => we have a valid signature - break; + int retry; + ECDSA_SIG *sig = + ecdsa_sign_impl(group, &retry, priv_key, &k, digest, digest_len); + if (sig != NULL || !retry) { + return sig; } } - - ok = 1; - -err: - if (!ok) { - ECDSA_SIG_free(ret); - ret = NULL; - } - OPENSSL_cleanse(&kinv_mont, sizeof(kinv_mont)); - OPENSSL_cleanse(&r_mont, sizeof(r_mont)); - OPENSSL_cleanse(&s, sizeof(s)); - OPENSSL_cleanse(&tmp, sizeof(tmp)); - OPENSSL_cleanse(&m, sizeof(m)); - return ret; }