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;
}
