Clean up various EC inversion functions.
This fixes two issues. First, we have been lax about whether the
low-level inversion functions fail on zero input or output zero. Fix the
documentation and call the latter inv0 or inverse0 to match the
terminology used in draft-irtf-cfrg-hash-to-curve. (Although we may not
actually need inv0 given the optimization in D.2.)
This has no actual effect because the functions were only used in
contexts where the inputs were already guaranteed to be non-zero. Still,
we should be consistent here.
Second, ec_scalar_inv_montgomery and ec_scalar_inv_montgomery_vartime
claim to perform the same operation, but they do not. First, one
computed inv0 and the other computed inv (except only in some
implementations, so fix it to be consistent). Second, the former
computes inverses in the Montgomery domain, while the latter converts to
the Montgomery domain and then inverts. Rename it to
ec_scalar_to_montgomery_inv_vartime, which is... questionably
understandable but at least looks different.
Change-Id: I9b4829ce5013bdb9528078a093f41b1b158df265
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/40526
Reviewed-by: Adam Langley <agl@google.com>
diff --git a/crypto/fipsmodule/bn/exponentiation.c b/crypto/fipsmodule/bn/exponentiation.c
index 8d4a5c8..f2c3f68 100644
--- a/crypto/fipsmodule/bn/exponentiation.c
+++ b/crypto/fipsmodule/bn/exponentiation.c
@@ -809,8 +809,8 @@
OPENSSL_cleanse(val, sizeof(val));
}
-void bn_mod_inverse_prime_mont_small(BN_ULONG *r, const BN_ULONG *a, size_t num,
- const BN_MONT_CTX *mont) {
+void bn_mod_inverse0_prime_mont_small(BN_ULONG *r, const BN_ULONG *a,
+ size_t num, const BN_MONT_CTX *mont) {
if (num != (size_t)mont->N.width || num > BN_SMALL_MAX_WORDS) {
abort();
}
diff --git a/crypto/fipsmodule/bn/internal.h b/crypto/fipsmodule/bn/internal.h
index d58a2ac..f27f3e7 100644
--- a/crypto/fipsmodule/bn/internal.h
+++ b/crypto/fipsmodule/bn/internal.h
@@ -675,13 +675,13 @@
const BN_ULONG *p, size_t num_p,
const BN_MONT_CTX *mont);
-// bn_mod_inverse_prime_mont_small sets |r| to |a|^-1 mod |mont->N|. |mont->N|
-// must be a prime. |r| and |a| are |num| words long, which must be
-// |mont->N.width| and at most |BN_SMALL_MAX_WORDS|. |a| must be fully-reduced
-// and may alias |r|. This function runs in time independent of |a|, but
-// |mont->N| is a public value.
-void bn_mod_inverse_prime_mont_small(BN_ULONG *r, const BN_ULONG *a, size_t num,
- const BN_MONT_CTX *mont);
+// bn_mod_inverse0_prime_mont_small sets |r| to |a|^-1 mod |mont->N|. If |a| is
+// zero, |r| is set to zero. |mont->N| must be a prime. |r| and |a| are |num|
+// words long, which must be |mont->N.width| and at most |BN_SMALL_MAX_WORDS|.
+// |a| must be fully-reduced and may alias |r|. This function runs in time
+// independent of |a|, but |mont->N| is a public value.
+void bn_mod_inverse0_prime_mont_small(BN_ULONG *r, const BN_ULONG *a,
+ size_t num, const BN_MONT_CTX *mont);
#if defined(__cplusplus)
diff --git a/crypto/fipsmodule/ec/ec_montgomery.c b/crypto/fipsmodule/ec/ec_montgomery.c
index 0cf1d91..5553f05 100644
--- a/crypto/fipsmodule/ec/ec_montgomery.c
+++ b/crypto/fipsmodule/ec/ec_montgomery.c
@@ -136,10 +136,10 @@
group->mont);
}
-static void ec_GFp_mont_felem_inv(const EC_GROUP *group, EC_FELEM *out,
- const EC_FELEM *a) {
- bn_mod_inverse_prime_mont_small(out->words, a->words, group->field.width,
- group->mont);
+static void ec_GFp_mont_felem_inv0(const EC_GROUP *group, EC_FELEM *out,
+ const EC_FELEM *a) {
+ bn_mod_inverse0_prime_mont_small(out->words, a->words, group->field.width,
+ group->mont);
}
void ec_GFp_mont_felem_mul(const EC_GROUP *group, EC_FELEM *r,
@@ -188,10 +188,10 @@
return 0;
}
- // Transform (X, Y, Z) into (x, y) := (X/Z^2, Y/Z^3).
-
+ // Transform (X, Y, Z into (x, y) := (X/Z^2, Y/Z^3). Note the check above
+ // ensures |point->Z| is non-zero, so the inverse always exists.
EC_FELEM z1, z2;
- ec_GFp_mont_felem_inv(group, &z2, &point->Z);
+ ec_GFp_mont_felem_inv0(group, &z2, &point->Z);
ec_GFp_mont_felem_sqr(group, &z1, &z2);
// Instead of using |ec_GFp_mont_felem_from_montgomery| to convert the |x|
@@ -477,7 +477,8 @@
out->felem_sqr = ec_GFp_mont_felem_sqr;
out->bignum_to_felem = ec_GFp_mont_bignum_to_felem;
out->felem_to_bignum = ec_GFp_mont_felem_to_bignum;
- out->scalar_inv_montgomery = ec_simple_scalar_inv_montgomery;
- out->scalar_inv_montgomery_vartime = ec_GFp_simple_mont_inv_mod_ord_vartime;
+ out->scalar_inv0_montgomery = ec_simple_scalar_inv0_montgomery;
+ out->scalar_to_montgomery_inv_vartime =
+ ec_simple_scalar_to_montgomery_inv_vartime;
out->cmp_x_coordinate = ec_GFp_mont_cmp_x_coordinate;
}
diff --git a/crypto/fipsmodule/ec/internal.h b/crypto/fipsmodule/ec/internal.h
index 4f05d1f..d076c91 100644
--- a/crypto/fipsmodule/ec/internal.h
+++ b/crypto/fipsmodule/ec/internal.h
@@ -152,15 +152,19 @@
void ec_scalar_mul_montgomery(const EC_GROUP *group, EC_SCALAR *r,
const EC_SCALAR *a, const EC_SCALAR *b);
-// ec_scalar_mul_montgomery sets |r| to |a|^-1 where inputs and outputs are in
-// Montgomery form.
-void ec_scalar_inv_montgomery(const EC_GROUP *group, EC_SCALAR *r,
- const EC_SCALAR *a);
+// ec_scalar_inv0_montgomery sets |r| to |a|^-1 where inputs and outputs are in
+// Montgomery form. If |a| is zero, |r| is set to zero.
+void ec_scalar_inv0_montgomery(const EC_GROUP *group, EC_SCALAR *r,
+ const EC_SCALAR *a);
-// ec_scalar_inv_montgomery_vartime performs the same actions as
-// |ec_scalar_inv_montgomery|, but in variable time.
-int ec_scalar_inv_montgomery_vartime(const EC_GROUP *group, EC_SCALAR *r,
- const EC_SCALAR *a);
+// ec_scalar_to_montgomery_inv_vartime sets |r| to |a|^-1 R. That is, it takes
+// in |a| not in Montgomery form and computes the inverse in Montgomery form. It
+// returns one on success and zero if |a| has no inverse. This function assumes
+// |a| is public and may leak information about it via timing.
+//
+// Note this is not the same operation as |ec_scalar_inv0_montgomery|.
+int ec_scalar_to_montgomery_inv_vartime(const EC_GROUP *group, EC_SCALAR *r,
+ const EC_SCALAR *a);
// Field elements.
@@ -318,16 +322,14 @@
int (*felem_to_bignum)(const EC_GROUP *group, BIGNUM *out,
const EC_FELEM *in);
- // scalar_inv_montgomery sets |out| to |in|^-1, where both input and output
- // are in Montgomery form.
- void (*scalar_inv_montgomery)(const EC_GROUP *group, EC_SCALAR *out,
- const EC_SCALAR *in);
+ // scalar_inv0_montgomery implements |ec_scalar_inv0_montgomery|.
+ void (*scalar_inv0_montgomery)(const EC_GROUP *group, EC_SCALAR *out,
+ const EC_SCALAR *in);
- // scalar_inv_montgomery_vartime performs the same computation as
- // |scalar_inv_montgomery|. It further assumes that the inputs are public so
- // there is no concern about leaking their values through timing.
- int (*scalar_inv_montgomery_vartime)(const EC_GROUP *group, EC_SCALAR *out,
- const EC_SCALAR *in);
+ // scalar_to_montgomery_inv_vartime implements
+ // |ec_scalar_to_montgomery_inv_vartime|.
+ int (*scalar_to_montgomery_inv_vartime)(const EC_GROUP *group, EC_SCALAR *out,
+ const EC_SCALAR *in);
// cmp_x_coordinate compares the x (affine) coordinate of |p|, mod the group
// order, with |r|. It returns one if the values match and zero if |p| is the
@@ -433,11 +435,12 @@
int ec_GFp_simple_is_on_curve(const EC_GROUP *, const EC_RAW_POINT *);
int ec_GFp_simple_cmp(const EC_GROUP *, const EC_RAW_POINT *a,
const EC_RAW_POINT *b);
-void ec_simple_scalar_inv_montgomery(const EC_GROUP *group, EC_SCALAR *r,
- const EC_SCALAR *a);
+void ec_simple_scalar_inv0_montgomery(const EC_GROUP *group, EC_SCALAR *r,
+ const EC_SCALAR *a);
-int ec_GFp_simple_mont_inv_mod_ord_vartime(const EC_GROUP *group, EC_SCALAR *r,
- const EC_SCALAR *a);
+int ec_simple_scalar_to_montgomery_inv_vartime(const EC_GROUP *group,
+ EC_SCALAR *r,
+ const EC_SCALAR *a);
int ec_GFp_simple_cmp_x_coordinate(const EC_GROUP *group, const EC_RAW_POINT *p,
const EC_SCALAR *r);
diff --git a/crypto/fipsmodule/ec/p224-64.c b/crypto/fipsmodule/ec/p224-64.c
index f8af39b..fa7ede1 100644
--- a/crypto/fipsmodule/ec/p224-64.c
+++ b/crypto/fipsmodule/ec/p224-64.c
@@ -1179,8 +1179,9 @@
out->felem_sqr = ec_GFp_nistp224_felem_sqr;
out->bignum_to_felem = ec_GFp_nistp224_bignum_to_felem;
out->felem_to_bignum = ec_GFp_nistp224_felem_to_bignum;
- out->scalar_inv_montgomery = ec_simple_scalar_inv_montgomery;
- out->scalar_inv_montgomery_vartime = ec_GFp_simple_mont_inv_mod_ord_vartime;
+ out->scalar_inv0_montgomery = ec_simple_scalar_inv0_montgomery;
+ out->scalar_to_montgomery_inv_vartime =
+ ec_simple_scalar_to_montgomery_inv_vartime;
out->cmp_x_coordinate = ec_GFp_simple_cmp_x_coordinate;
}
diff --git a/crypto/fipsmodule/ec/p256-x86_64.c b/crypto/fipsmodule/ec/p256-x86_64.c
index b4af544..3993ff4 100644
--- a/crypto/fipsmodule/ec/p256-x86_64.c
+++ b/crypto/fipsmodule/ec/p256-x86_64.c
@@ -490,8 +490,8 @@
OPENSSL_memcpy(r->Z.words, a.Z, P256_LIMBS * sizeof(BN_ULONG));
}
-static void ecp_nistz256_inv_mod_ord(const EC_GROUP *group, EC_SCALAR *out,
- const EC_SCALAR *in) {
+static void ecp_nistz256_inv0_mod_ord(const EC_GROUP *group, EC_SCALAR *out,
+ const EC_SCALAR *in) {
// table[i] stores a power of |in| corresponding to the matching enum value.
enum {
// The following indices specify the power in binary.
@@ -571,12 +571,12 @@
}
}
-static int ecp_nistz256_mont_inv_mod_ord_vartime(const EC_GROUP *group,
+static int ecp_nistz256_scalar_to_montgomery_inv_vartime(const EC_GROUP *group,
EC_SCALAR *out,
const EC_SCALAR *in) {
if ((OPENSSL_ia32cap_get()[1] & (1 << 28)) == 0) {
// No AVX support; fallback to generic code.
- return ec_GFp_simple_mont_inv_mod_ord_vartime(group, out, in);
+ return ec_simple_scalar_to_montgomery_inv_vartime(group, out, in);
}
assert(group->order.width == P256_LIMBS);
@@ -642,8 +642,9 @@
out->felem_sqr = ec_GFp_mont_felem_sqr;
out->bignum_to_felem = ec_GFp_mont_bignum_to_felem;
out->felem_to_bignum = ec_GFp_mont_felem_to_bignum;
- out->scalar_inv_montgomery = ecp_nistz256_inv_mod_ord;
- out->scalar_inv_montgomery_vartime = ecp_nistz256_mont_inv_mod_ord_vartime;
+ out->scalar_inv0_montgomery = ecp_nistz256_inv0_mod_ord;
+ out->scalar_to_montgomery_inv_vartime =
+ ecp_nistz256_scalar_to_montgomery_inv_vartime;
out->cmp_x_coordinate = ecp_nistz256_cmp_x_coordinate;
}
diff --git a/crypto/fipsmodule/ec/scalar.c b/crypto/fipsmodule/ec/scalar.c
index 4b4f874..595d3ff 100644
--- a/crypto/fipsmodule/ec/scalar.c
+++ b/crypto/fipsmodule/ec/scalar.c
@@ -108,19 +108,38 @@
group->order_mont);
}
-void ec_simple_scalar_inv_montgomery(const EC_GROUP *group, EC_SCALAR *r,
- const EC_SCALAR *a) {
+void ec_simple_scalar_inv0_montgomery(const EC_GROUP *group, EC_SCALAR *r,
+ const EC_SCALAR *a) {
const BIGNUM *order = &group->order;
- bn_mod_inverse_prime_mont_small(r->words, a->words, order->width,
- group->order_mont);
+ bn_mod_inverse0_prime_mont_small(r->words, a->words, order->width,
+ group->order_mont);
}
-void ec_scalar_inv_montgomery(const EC_GROUP *group, EC_SCALAR *r,
- const EC_SCALAR *a) {
- group->meth->scalar_inv_montgomery(group, r, a);
+int ec_simple_scalar_to_montgomery_inv_vartime(const EC_GROUP *group,
+ EC_SCALAR *out,
+ const EC_SCALAR *in) {
+ if (ec_scalar_is_zero(group, in)) {
+ return 0;
+ }
+
+ // This implementation (in fact) runs in constant time,
+ // even though for this interface it is not mandatory.
+
+ // out = in^-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.
+ ec_scalar_inv0_montgomery(group, out, in);
+ ec_scalar_from_montgomery(group, out, out);
+ return 1;
}
-int ec_scalar_inv_montgomery_vartime(const EC_GROUP *group, EC_SCALAR *r,
- const EC_SCALAR *a) {
- return group->meth->scalar_inv_montgomery_vartime(group, r, a);
+void ec_scalar_inv0_montgomery(const EC_GROUP *group, EC_SCALAR *r,
+ const EC_SCALAR *a) {
+ group->meth->scalar_inv0_montgomery(group, r, a);
+}
+
+int ec_scalar_to_montgomery_inv_vartime(const EC_GROUP *group, EC_SCALAR *r,
+ const EC_SCALAR *a) {
+ return group->meth->scalar_to_montgomery_inv_vartime(group, r, a);
}
diff --git a/crypto/fipsmodule/ec/simple.c b/crypto/fipsmodule/ec/simple.c
index c418c4e..8536b80 100644
--- a/crypto/fipsmodule/ec/simple.c
+++ b/crypto/fipsmodule/ec/simple.c
@@ -351,21 +351,6 @@
return 0;
}
-int ec_GFp_simple_mont_inv_mod_ord_vartime(const EC_GROUP *group,
- EC_SCALAR *out,
- const EC_SCALAR *in) {
- // This implementation (in fact) runs in constant time,
- // even though for this interface it is not mandatory.
-
- // out = in^-1 in the Montgomery domain. This is
- // |ec_scalar_to_montgomery| followed by |ec_scalar_inv_montgomery|, but
- // |ec_scalar_inv_montgomery| followed by |ec_scalar_from_montgomery| is
- // equivalent and slightly more efficient.
- ec_scalar_inv_montgomery(group, out, in);
- ec_scalar_from_montgomery(group, out, out);
- return 1;
-}
-
int ec_GFp_simple_cmp_x_coordinate(const EC_GROUP *group, const EC_RAW_POINT *p,
const EC_SCALAR *r) {
if (ec_GFp_simple_is_at_infinity(group, p)) {
diff --git a/crypto/fipsmodule/ecdsa/ecdsa.c b/crypto/fipsmodule/ecdsa/ecdsa.c
index 56d9f16..096b615 100644
--- a/crypto/fipsmodule/ecdsa/ecdsa.c
+++ b/crypto/fipsmodule/ecdsa/ecdsa.c
@@ -169,8 +169,11 @@
return 0;
}
- // s_inv_mont = s^-1 in the Montgomery domain. This is
- ec_scalar_inv_montgomery_vartime(group, &s_inv_mont, &s);
+ // s_inv_mont = s^-1 in the Montgomery domain.
+ if (!ec_scalar_to_montgomery_inv_vartime(group, &s_inv_mont, &s)) {
+ OPENSSL_PUT_ERROR(ECDSA, ERR_R_INTERNAL_ERROR);
+ return 0;
+ }
// u1 = m * s^-1 mod order
// u2 = r * s^-1 mod order
@@ -216,6 +219,10 @@
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.
@@ -233,10 +240,10 @@
}
// Compute k^-1 in the Montgomery domain. This is |ec_scalar_to_montgomery|
- // followed by |ec_scalar_inv_montgomery|, but |ec_scalar_inv_montgomery|
+ // followed by |ec_scalar_inv0_montgomery|, but |ec_scalar_inv0_montgomery|
// followed by |ec_scalar_from_montgomery| is equivalent and slightly more
- // efficient.
- ec_scalar_inv_montgomery(group, out_kinv_mont, &k);
+ // 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);
// Compute r, the x-coordinate of generator * k.
diff --git a/third_party/fiat/p256.c b/third_party/fiat/p256.c
index 23ec71f..dd113c4 100644
--- a/third_party/fiat/p256.c
+++ b/third_party/fiat/p256.c
@@ -1055,8 +1055,9 @@
out->felem_sqr = ec_GFp_mont_felem_sqr;
out->bignum_to_felem = ec_GFp_mont_bignum_to_felem;
out->felem_to_bignum = ec_GFp_mont_felem_to_bignum;
- out->scalar_inv_montgomery = ec_simple_scalar_inv_montgomery;
- out->scalar_inv_montgomery_vartime = ec_GFp_simple_mont_inv_mod_ord_vartime;
+ out->scalar_inv0_montgomery = ec_simple_scalar_inv0_montgomery;
+ out->scalar_to_montgomery_inv_vartime =
+ ec_simple_scalar_to_montgomery_inv_vartime;
out->cmp_x_coordinate = ec_GFp_nistp256_cmp_x_coordinate;
}
