Make EC_POINT_mul work with arbitrary BIGNUMs again.
Rejecting values where we'd previous called BN_nnmod may have been
overly ambitious. In the long run, all the supported ECC APIs (ECDSA*,
ECDH_compute_key, and probably some additional new ECDH API) will be
using the EC_SCALAR version anyway, so this doesn't really matter.
Change-Id: I79cd4015f2d6daf213e4413caa2a497608976f93
Reviewed-on: https://boringssl-review.googlesource.com/23584
Commit-Queue: Adam Langley <agl@google.com>
Reviewed-by: Adam Langley <agl@google.com>
CQ-Verified: CQ bot account: commit-bot@chromium.org <commit-bot@chromium.org>
diff --git a/crypto/fipsmodule/ec/ec.c b/crypto/fipsmodule/ec/ec.c
index 977cd26..266baa2 100644
--- a/crypto/fipsmodule/ec/ec.c
+++ b/crypto/fipsmodule/ec/ec.c
@@ -817,6 +817,24 @@
return ec_GFp_simple_invert(group, a, ctx);
}
+static int arbitrary_bignum_to_scalar(const EC_GROUP *group, EC_SCALAR *out,
+ const BIGNUM *in, BN_CTX *ctx) {
+ const BIGNUM *order = EC_GROUP_get0_order(group);
+ if (BN_is_negative(in) || BN_num_bits(in) > BN_num_bits(order)) {
+ // This is an unusual input, so we do not guarantee constant-time
+ // processing, even ignoring |bn_correct_top|.
+ BN_CTX_start(ctx);
+ BIGNUM *tmp = BN_CTX_get(ctx);
+ int ok = tmp != NULL &&
+ BN_nnmod(tmp, in, order, ctx) &&
+ ec_bignum_to_scalar(group, out, tmp);
+ BN_CTX_end(ctx);
+ return ok;
+ }
+
+ return ec_bignum_to_scalar(group, out, in);
+}
+
int EC_POINT_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *g_scalar,
const EC_POINT *p, const BIGNUM *p_scalar, BN_CTX *ctx) {
// Previously, this function set |r| to the point at infinity if there was
@@ -828,30 +846,27 @@
return 0;
}
- // We cannot easily process arbitrary scalars in constant-time, and there is
- // no need to do so. Require that scalars be the same size as the order.
- //
- // One could require they be fully reduced, but some consumers try to check
- // that |order| * |pubkey| is the identity. This comes from following NIST SP
- // 800-56A section 5.6.2.3.2. (Though all our curves have cofactor one, so
- // this check isn't useful.)
int ret = 0;
EC_SCALAR g_scalar_storage, p_scalar_storage;
EC_SCALAR *g_scalar_arg = NULL, *p_scalar_arg = NULL;
- unsigned order_bits = BN_num_bits(&group->order);
+ BN_CTX *new_ctx = NULL;
+ if (ctx == NULL) {
+ new_ctx = BN_CTX_new();
+ if (new_ctx == NULL) {
+ goto err;
+ }
+ ctx = new_ctx;
+ }
+
if (g_scalar != NULL) {
- if (BN_is_negative(g_scalar) || BN_num_bits(g_scalar) > order_bits ||
- !ec_bignum_to_scalar(group, &g_scalar_storage, g_scalar)) {
- OPENSSL_PUT_ERROR(EC, EC_R_INVALID_SCALAR);
+ if (!arbitrary_bignum_to_scalar(group, &g_scalar_storage, g_scalar, ctx)) {
goto err;
}
g_scalar_arg = &g_scalar_storage;
}
if (p_scalar != NULL) {
- if (BN_is_negative(p_scalar) || BN_num_bits(p_scalar) > order_bits ||
- !ec_bignum_to_scalar(group, &p_scalar_storage, p_scalar)) {
- OPENSSL_PUT_ERROR(EC, EC_R_INVALID_SCALAR);
+ if (!arbitrary_bignum_to_scalar(group, &p_scalar_storage, p_scalar, ctx)) {
goto err;
}
p_scalar_arg = &p_scalar_storage;
@@ -860,6 +875,7 @@
ret = ec_point_mul_scalar(group, r, g_scalar_arg, p, p_scalar_arg, ctx);
err:
+ BN_CTX_free(new_ctx);
OPENSSL_cleanse(&g_scalar_storage, sizeof(g_scalar_storage));
OPENSSL_cleanse(&p_scalar_storage, sizeof(p_scalar_storage));
return ret;
diff --git a/crypto/fipsmodule/ec/ec_test.cc b/crypto/fipsmodule/ec/ec_test.cc
index 5e5ce94..139840e 100644
--- a/crypto/fipsmodule/ec/ec_test.cc
+++ b/crypto/fipsmodule/ec/ec_test.cc
@@ -439,6 +439,52 @@
<< "p * order did not return point at infinity.";
}
+// Test that |EC_POINT_mul| works with out-of-range scalars. Even beyond the
+// usual |bn_correct_top| disclaimer, we completely disclaim all hope here as a
+// reduction is needed, but we'll compute the right answer.
+TEST_P(ECCurveTest, MulOutOfRange) {
+ bssl::UniquePtr<EC_GROUP> group(EC_GROUP_new_by_curve_name(GetParam().nid));
+ ASSERT_TRUE(group);
+
+ bssl::UniquePtr<BIGNUM> n_minus_one(BN_dup(EC_GROUP_get0_order(group.get())));
+ ASSERT_TRUE(n_minus_one);
+ ASSERT_TRUE(BN_sub_word(n_minus_one.get(), 1));
+
+ bssl::UniquePtr<BIGNUM> minus_one(BN_new());
+ ASSERT_TRUE(minus_one);
+ ASSERT_TRUE(BN_one(minus_one.get()));
+ BN_set_negative(minus_one.get(), 1);
+
+ bssl::UniquePtr<BIGNUM> seven(BN_new());
+ ASSERT_TRUE(seven);
+ ASSERT_TRUE(BN_set_word(seven.get(), 7));
+
+ bssl::UniquePtr<BIGNUM> ten_n_plus_seven(
+ BN_dup(EC_GROUP_get0_order(group.get())));
+ ASSERT_TRUE(ten_n_plus_seven);
+ ASSERT_TRUE(BN_mul_word(ten_n_plus_seven.get(), 10));
+ ASSERT_TRUE(BN_add_word(ten_n_plus_seven.get(), 7));
+
+ bssl::UniquePtr<EC_POINT> point1(EC_POINT_new(group.get())),
+ point2(EC_POINT_new(group.get()));
+ ASSERT_TRUE(point1);
+ ASSERT_TRUE(point2);
+
+ ASSERT_TRUE(EC_POINT_mul(group.get(), point1.get(), n_minus_one.get(),
+ nullptr, nullptr, nullptr));
+ ASSERT_TRUE(EC_POINT_mul(group.get(), point2.get(), minus_one.get(), nullptr,
+ nullptr, nullptr));
+ EXPECT_EQ(0, EC_POINT_cmp(group.get(), point1.get(), point2.get(), nullptr))
+ << "-1 * G and (n-1) * G did not give the same result";
+
+ ASSERT_TRUE(EC_POINT_mul(group.get(), point1.get(), seven.get(), nullptr,
+ nullptr, nullptr));
+ ASSERT_TRUE(EC_POINT_mul(group.get(), point2.get(), ten_n_plus_seven.get(),
+ nullptr, nullptr, nullptr));
+ EXPECT_EQ(0, EC_POINT_cmp(group.get(), point1.get(), point2.get(), nullptr))
+ << "7 * G and (10n + 7) * G did not give the same result";
+}
+
// Test that 10×∞ + G = G.
TEST_P(ECCurveTest, Mul) {
bssl::UniquePtr<EC_GROUP> group(EC_GROUP_new_by_curve_name(GetParam().nid));
