summaryrefslogtreecommitdiff
path: root/src/crypto/fipsmodule
diff options
context:
space:
mode:
Diffstat (limited to 'src/crypto/fipsmodule')
-rwxr-xr-xsrc/crypto/fipsmodule/bn/asm/rsaz-avx2.pl15
-rw-r--r--src/crypto/fipsmodule/bn/bn_tests.txt6
-rw-r--r--src/crypto/fipsmodule/ec/ec.c38
-rw-r--r--src/crypto/fipsmodule/ec/ec_key.c9
-rw-r--r--src/crypto/fipsmodule/ec/ec_test.cc19
-rw-r--r--src/crypto/fipsmodule/ec/internal.h16
-rw-r--r--src/crypto/fipsmodule/ecdsa/ecdsa.c109
7 files changed, 139 insertions, 73 deletions
diff --git a/src/crypto/fipsmodule/bn/asm/rsaz-avx2.pl b/src/crypto/fipsmodule/bn/asm/rsaz-avx2.pl
index 0bb50cdb..32c21673 100755
--- a/src/crypto/fipsmodule/bn/asm/rsaz-avx2.pl
+++ b/src/crypto/fipsmodule/bn/asm/rsaz-avx2.pl
@@ -232,7 +232,7 @@ $code.=<<___;
vmovdqu 32*8-128($ap), $ACC8
lea 192(%rsp), $tp0 # 64+128=192
- vpbroadcastq .Land_mask(%rip), $AND_MASK
+ vmovdqu .Land_mask(%rip), $AND_MASK
jmp .LOOP_GRANDE_SQR_1024
.align 32
@@ -1082,10 +1082,10 @@ $code.=<<___;
vpmuludq 32*6-128($np),$Yi,$TEMP1
vpaddq $TEMP1,$ACC6,$ACC6
vpmuludq 32*7-128($np),$Yi,$TEMP2
- vpblendd \$3, $ZERO, $ACC9, $ACC9 # correct $ACC3
+ vpblendd \$3, $ZERO, $ACC9, $TEMP1 # correct $ACC3
vpaddq $TEMP2,$ACC7,$ACC7
vpmuludq 32*8-128($np),$Yi,$TEMP0
- vpaddq $ACC9, $ACC3, $ACC3 # correct $ACC3
+ vpaddq $TEMP1, $ACC3, $ACC3 # correct $ACC3
vpaddq $TEMP0,$ACC8,$ACC8
mov %rbx, %rax
@@ -1098,7 +1098,9 @@ $code.=<<___;
vmovdqu -8+32*2-128($ap),$TEMP2
mov $r1, %rax
+ vpblendd \$0xfc, $ZERO, $ACC9, $ACC9 # correct $ACC3
imull $n0, %eax
+ vpaddq $ACC9,$ACC4,$ACC4 # correct $ACC3
and \$0x1fffffff, %eax
imulq 16-128($ap),%rbx
@@ -1334,15 +1336,12 @@ ___
# But as we underutilize resources, it's possible to correct in
# each iteration with marginal performance loss. But then, as
# we do it in each iteration, we can correct less digits, and
-# avoid performance penalties completely. Also note that we
-# correct only three digits out of four. This works because
-# most significant digit is subjected to less additions.
+# avoid performance penalties completely.
$TEMP0 = $ACC9;
$TEMP3 = $Bi;
$TEMP4 = $Yi;
$code.=<<___;
- vpermq \$0, $AND_MASK, $AND_MASK
vpaddq (%rsp), $TEMP1, $ACC0
vpsrlq \$29, $ACC0, $TEMP1
@@ -1790,7 +1789,7 @@ $code.=<<___;
.align 64
.Land_mask:
- .quad 0x1fffffff,0x1fffffff,0x1fffffff,-1
+ .quad 0x1fffffff,0x1fffffff,0x1fffffff,0x1fffffff
.Lscatter_permd:
.long 0,2,4,6,7,7,7,7
.Lgather_permd:
diff --git a/src/crypto/fipsmodule/bn/bn_tests.txt b/src/crypto/fipsmodule/bn/bn_tests.txt
index eb447b53..87e64e2b 100644
--- a/src/crypto/fipsmodule/bn/bn_tests.txt
+++ b/src/crypto/fipsmodule/bn/bn_tests.txt
@@ -10507,6 +10507,12 @@ A = -80000000000000000000000000000000000000000000000000000000000000000000000000
E = 61803d4973ae68cfb2ba6770dbed70d36760fa42c01a16d1482eacf0d01adf7a917bc86ece58a73b920295c1291b90f49167ef856ecad149330e1fd49ec71392fb62d47270b53e6d4f3c8f044b80a5736753364896932abc6d872c4c5e135d1edb200597a93ceb262ff6c99079177cd10808b9ed20c8cd7352d80ac7f6963103
M = b5d257b2c50b050d42f0852eff5cfa2571157c500cd0bd9aa0b2ccdd89c531c9609d520eb81d928fb52b06da25dc713561aa0bd365ee56db9e62ac6787a85936990f44438363560f7af9e0c16f378e5b83f658252390d849401817624da97ec613a1b855fd901847352f434a777e4e32af0cb4033c7547fb6437d067fcd3d965
+# Regression test for CVE-2017-3738.
+ModExp = d360792bd8210786607817c3dda64cc38c8d0f25569597cb1f363c7919a0c3587baff01a2283edaeb04fc288ac0ab3f279b2a89ffcb452d8bdf72422a9f9780f4aa702dc964cf033149d3a339883062cab8564aebdbfac0bf68985e522c6fe545b346044690c525ca85d3f4eb3e3c25cdf541545afc84a309e9b1d7807003461
+A = ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff2020202020df
+E = 2020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020FF2020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020202020
+M = ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff2020202020ff
+
# Exp tests.
#
diff --git a/src/crypto/fipsmodule/ec/ec.c b/src/crypto/fipsmodule/ec/ec.c
index 266baa24..41c2540b 100644
--- a/src/crypto/fipsmodule/ec/ec.c
+++ b/src/crypto/fipsmodule/ec/ec.c
@@ -819,20 +819,22 @@ int EC_POINT_invert(const EC_GROUP *group, EC_POINT *a, BN_CTX *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;
+ if (ec_bignum_to_scalar(group, out, in)) {
+ return 1;
}
- return ec_bignum_to_scalar(group, out, in);
+ ERR_clear_error();
+
+ // This is an unusual input, so we do not guarantee constant-time
+ // processing, even ignoring |bn_correct_top|.
+ const BIGNUM *order = &group->order;
+ BN_CTX_start(ctx);
+ BIGNUM *tmp = BN_CTX_get(ctx);
+ int ok = tmp != NULL &&
+ BN_nnmod(tmp, in, order, ctx) &&
+ ec_bignum_to_scalar_unchecked(group, out, tmp);
+ BN_CTX_end(ctx);
+ return ok;
}
int EC_POINT_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *g_scalar,
@@ -943,6 +945,18 @@ size_t EC_get_builtin_curves(EC_builtin_curve *out_curves,
int ec_bignum_to_scalar(const EC_GROUP *group, EC_SCALAR *out,
const BIGNUM *in) {
+ if (!ec_bignum_to_scalar_unchecked(group, out, in)) {
+ return 0;
+ }
+ if (!bn_less_than_words(out->words, group->order.d, group->order.top)) {
+ OPENSSL_PUT_ERROR(EC, EC_R_INVALID_SCALAR);
+ return 0;
+ }
+ return 1;
+}
+
+int ec_bignum_to_scalar_unchecked(const EC_GROUP *group, EC_SCALAR *out,
+ const BIGNUM *in) {
if (BN_is_negative(in) || in->top > group->order.top) {
OPENSSL_PUT_ERROR(EC, EC_R_INVALID_SCALAR);
return 0;
diff --git a/src/crypto/fipsmodule/ec/ec_key.c b/src/crypto/fipsmodule/ec/ec_key.c
index bba4402b..f64cb21e 100644
--- a/src/crypto/fipsmodule/ec/ec_key.c
+++ b/src/crypto/fipsmodule/ec/ec_key.c
@@ -242,7 +242,8 @@ int EC_KEY_set_group(EC_KEY *key, const EC_GROUP *group) {
}
// XXX: |BN_cmp| is not constant time.
if (key->priv_key != NULL &&
- BN_cmp(key->priv_key, EC_GROUP_get0_order(group)) >= 0) {
+ (BN_is_negative(key->priv_key) ||
+ BN_cmp(key->priv_key, EC_GROUP_get0_order(group)) >= 0)) {
return 0;
}
return 1;
@@ -255,7 +256,8 @@ const BIGNUM *EC_KEY_get0_private_key(const EC_KEY *key) {
int EC_KEY_set_private_key(EC_KEY *key, const BIGNUM *priv_key) {
// XXX: |BN_cmp| is not constant time.
if (key->group != NULL &&
- BN_cmp(priv_key, EC_GROUP_get0_order(key->group)) >= 0) {
+ (BN_is_negative(priv_key) ||
+ BN_cmp(priv_key, EC_GROUP_get0_order(key->group)) >= 0)) {
OPENSSL_PUT_ERROR(EC, EC_R_WRONG_ORDER);
return 0;
}
@@ -318,7 +320,8 @@ int EC_KEY_check_key(const EC_KEY *eckey) {
// check if generator * priv_key == pub_key
if (eckey->priv_key) {
// XXX: |BN_cmp| is not constant time.
- if (BN_cmp(eckey->priv_key, EC_GROUP_get0_order(eckey->group)) >= 0) {
+ if (BN_is_negative(eckey->priv_key) ||
+ BN_cmp(eckey->priv_key, EC_GROUP_get0_order(eckey->group)) >= 0) {
OPENSSL_PUT_ERROR(EC, EC_R_WRONG_ORDER);
goto err;
}
diff --git a/src/crypto/fipsmodule/ec/ec_test.cc b/src/crypto/fipsmodule/ec/ec_test.cc
index 139840e5..8e7a81d9 100644
--- a/src/crypto/fipsmodule/ec/ec_test.cc
+++ b/src/crypto/fipsmodule/ec/ec_test.cc
@@ -510,6 +510,25 @@ TEST_P(ECCurveTest, Mul) {
EXPECT_EQ(0, EC_POINT_cmp(group.get(), result.get(), generator, nullptr));
}
+// Test that EC_KEY_set_private_key rejects invalid values.
+TEST_P(ECCurveTest, SetInvalidPrivateKey) {
+ bssl::UniquePtr<EC_KEY> key(EC_KEY_new_by_curve_name(GetParam().nid));
+ ASSERT_TRUE(key);
+
+ bssl::UniquePtr<BIGNUM> bn(BN_new());
+ ASSERT_TRUE(BN_one(bn.get()));
+ BN_set_negative(bn.get(), 1);
+ EXPECT_FALSE(EC_KEY_set_private_key(key.get(), bn.get()))
+ << "Unexpectedly set a key of -1";
+ ERR_clear_error();
+
+ ASSERT_TRUE(
+ BN_copy(bn.get(), EC_GROUP_get0_order(EC_KEY_get0_group(key.get()))));
+ EXPECT_FALSE(EC_KEY_set_private_key(key.get(), bn.get()))
+ << "Unexpectedly set a key of the group order.";
+ ERR_clear_error();
+}
+
static std::vector<EC_builtin_curve> AllCurves() {
const size_t num_curves = EC_get_builtin_curves(nullptr, 0);
std::vector<EC_builtin_curve> curves(num_curves);
diff --git a/src/crypto/fipsmodule/ec/internal.h b/src/crypto/fipsmodule/ec/internal.h
index 7374e8b5..1b860c6b 100644
--- a/src/crypto/fipsmodule/ec/internal.h
+++ b/src/crypto/fipsmodule/ec/internal.h
@@ -91,10 +91,9 @@ extern "C" {
OPENSSL_COMPILE_ASSERT(EC_MAX_SCALAR_WORDS <= BN_SMALL_MAX_WORDS,
bn_small_functions_applicable);
-// An EC_SCALAR is a |BN_num_bits(order)|-bit integer. Only the first
+// An EC_SCALAR is an integer fully reduced modulo the order. Only the first
// |order->top| words are used. An |EC_SCALAR| is specific to an |EC_GROUP| and
-// must not be mixed between groups. Unless otherwise specified, it is fully
-// reduced modulo the |order|.
+// must not be mixed between groups.
typedef union {
// bytes is the representation of the scalar in little-endian order.
uint8_t bytes[EC_MAX_SCALAR_BYTES];
@@ -173,13 +172,16 @@ struct ec_point_st {
EC_GROUP *ec_group_new(const EC_METHOD *meth);
-// ec_bignum_to_scalar converts |in| to an |EC_SCALAR| and writes it to |*out|.
-// |in| must be non-negative and have at most |BN_num_bits(&group->order)| bits.
-// It returns one on success and zero on error. It does not ensure |in| is fully
-// reduced.
+// ec_bignum_to_scalar converts |in| to an |EC_SCALAR| and writes it to
+// |*out|. It returns one on success and zero if |in| is out of range.
int ec_bignum_to_scalar(const EC_GROUP *group, EC_SCALAR *out,
const BIGNUM *in);
+// ec_bignum_to_scalar_unchecked behaves like |ec_bignum_to_scalar| but does not
+// check |in| is fully reduced.
+int ec_bignum_to_scalar_unchecked(const EC_GROUP *group, EC_SCALAR *out,
+ const BIGNUM *in);
+
// ec_random_nonzero_scalar sets |out| to a uniformly selected random value from
// 1 to |group->order| - 1. It returns one on success and zero on error.
int ec_random_nonzero_scalar(const EC_GROUP *group, EC_SCALAR *out,
diff --git a/src/crypto/fipsmodule/ecdsa/ecdsa.c b/src/crypto/fipsmodule/ecdsa/ecdsa.c
index 319a934e..6571c941 100644
--- a/src/crypto/fipsmodule/ecdsa/ecdsa.c
+++ b/src/crypto/fipsmodule/ecdsa/ecdsa.c
@@ -66,10 +66,53 @@
#include "../../internal.h"
+// EC_LOOSE_SCALAR is like |EC_SCALAR| but is bounded by 2^|BN_num_bits(order)|
+// rather than |order|.
+typedef union {
+ // bytes is the representation of the scalar in little-endian order.
+ uint8_t bytes[EC_MAX_SCALAR_BYTES];
+ BN_ULONG words[EC_MAX_SCALAR_WORDS];
+} EC_LOOSE_SCALAR;
+
+static void scalar_add_loose(const EC_GROUP *group, EC_LOOSE_SCALAR *r,
+ const EC_LOOSE_SCALAR *a, const EC_SCALAR *b) {
+ // Add and subtract one copy of |order| if necessary. We have:
+ // |a| + |b| < 2^BN_num_bits(order) + order
+ // so this leaves |r| < 2^BN_num_bits(order).
+ const BIGNUM *order = &group->order;
+ BN_ULONG carry = bn_add_words(r->words, a->words, b->words, order->top);
+ EC_LOOSE_SCALAR tmp;
+ BN_ULONG v = bn_sub_words(tmp.words, r->words, order->d, order->top) - carry;
+ v = 0u - v;
+ for (int i = 0; i < order->top; i++) {
+ OPENSSL_COMPILE_ASSERT(sizeof(BN_ULONG) <= sizeof(crypto_word_t),
+ crypto_word_t_too_small);
+ r->words[i] = constant_time_select_w(v, r->words[i], tmp.words[i]);
+ }
+}
+
+static int scalar_mod_mul_montgomery(const EC_GROUP *group, EC_SCALAR *r,
+ const EC_SCALAR *a, const EC_SCALAR *b) {
+ const BIGNUM *order = &group->order;
+ return bn_mod_mul_montgomery_small(r->words, order->top, a->words, order->top,
+ b->words, order->top, group->order_mont);
+}
+
+static int scalar_mod_mul_montgomery_loose(const EC_GROUP *group, EC_SCALAR *r,
+ const EC_LOOSE_SCALAR *a,
+ const EC_SCALAR *b) {
+ // Although |a| is loose, |bn_mod_mul_montgomery_small| only requires the
+ // product not exceed R * |order|. |b| is fully reduced and |a| <
+ // 2^BN_num_bits(order) <= R, so this holds.
+ const BIGNUM *order = &group->order;
+ return bn_mod_mul_montgomery_small(r->words, order->top, a->words, order->top,
+ b->words, order->top, group->order_mont);
+}
+
// digest_to_scalar interprets |digest_len| bytes from |digest| as a scalar for
// ECDSA. Note this value is not fully reduced modulo the order, only the
// correct number of bits.
-static void digest_to_scalar(const EC_GROUP *group, EC_SCALAR *out,
+static void digest_to_scalar(const EC_GROUP *group, EC_LOOSE_SCALAR *out,
const uint8_t *digest, size_t digest_len) {
const BIGNUM *order = &group->order;
size_t num_bits = BN_num_bits(order);
@@ -195,15 +238,12 @@ int ECDSA_do_verify(const uint8_t *digest, size_t digest_len,
goto err;
}
- EC_SCALAR r, s, m, u1, u2, s_inv_mont;
+ EC_SCALAR r, s, u1, u2, s_inv_mont;
+ EC_LOOSE_SCALAR m;
const BIGNUM *order = EC_GROUP_get0_order(group);
if (BN_is_zero(sig->r) ||
- BN_is_negative(sig->r) ||
- BN_ucmp(sig->r, order) >= 0 ||
!ec_bignum_to_scalar(group, &r, sig->r) ||
BN_is_zero(sig->s) ||
- BN_is_negative(sig->s) ||
- BN_ucmp(sig->s, order) >= 0 ||
!ec_bignum_to_scalar(group, &s, sig->s)) {
OPENSSL_PUT_ERROR(ECDSA, ECDSA_R_BAD_SIGNATURE);
goto err;
@@ -212,26 +252,21 @@ int ECDSA_do_verify(const uint8_t *digest, size_t digest_len,
// the products below.
int no_inverse;
if (!BN_mod_inverse_odd(X, &no_inverse, sig->s, order, ctx) ||
- !ec_bignum_to_scalar(group, &s_inv_mont, X) ||
+ // TODO(davidben): Add a words version of |BN_mod_inverse_odd| and write
+ // into |s_inv_mont| directly.
+ !ec_bignum_to_scalar_unchecked(group, &s_inv_mont, X) ||
!bn_to_montgomery_small(s_inv_mont.words, order->top, s_inv_mont.words,
order->top, group->order_mont)) {
goto err;
}
- // u1 = m * s_inv_mont mod order
- // u2 = r * s_inv_mont mod order
+ // u1 = m * s^-1 mod order
+ // u2 = r * s^-1 mod order
//
// |s_inv_mont| is in Montgomery form while |m| and |r| are not, so |u1| and
- // |u2| will be taken out of Montgomery form, as desired. Note that, although
- // |m| is not fully reduced, |bn_mod_mul_montgomery_small| only requires the
- // product not exceed R * |order|. |s_inv_mont| is fully reduced and |m| <
- // 2^BN_num_bits(order) <= R, so this holds.
+ // |u2| will be taken out of Montgomery form, as desired.
digest_to_scalar(group, &m, digest, digest_len);
- if (!bn_mod_mul_montgomery_small(u1.words, order->top, m.words, order->top,
- s_inv_mont.words, order->top,
- group->order_mont) ||
- !bn_mod_mul_montgomery_small(u2.words, order->top, r.words, order->top,
- s_inv_mont.words, order->top,
- group->order_mont)) {
+ if (!scalar_mod_mul_montgomery_loose(group, &u1, &m, &s_inv_mont) ||
+ !scalar_mod_mul_montgomery(group, &u2, &r, &s_inv_mont)) {
goto err;
}
@@ -368,14 +403,17 @@ ECDSA_SIG *ECDSA_do_sign(const uint8_t *digest, size_t digest_len,
int ok = 0;
ECDSA_SIG *ret = ECDSA_SIG_new();
BN_CTX *ctx = BN_CTX_new();
- EC_SCALAR kinv_mont, priv_key, r_mont, s, tmp, m;
+ EC_SCALAR kinv_mont, priv_key, r_mont, s;
+ EC_LOOSE_SCALAR m, tmp;
if (ret == NULL || ctx == NULL) {
OPENSSL_PUT_ERROR(ECDSA, ERR_R_MALLOC_FAILURE);
return NULL;
}
digest_to_scalar(group, &m, digest, digest_len);
- if (!ec_bignum_to_scalar(group, &priv_key, priv_key_bn)) {
+ // TODO(davidben): Store the private key as an |EC_SCALAR| so this is obvious
+ // via the type system.
+ if (!ec_bignum_to_scalar_unchecked(group, &priv_key, priv_key_bn)) {
goto err;
}
for (;;) {
@@ -385,36 +423,21 @@ ECDSA_SIG *ECDSA_do_sign(const uint8_t *digest, size_t digest_len,
}
// Compute priv_key * r (mod order). Note if only one parameter is in the
- // Montgomery domain, |bn_mod_mul_montgomery_small| will compute the answer
- // in the normal domain.
+ // Montgomery domain, |scalar_mod_mul_montgomery| will compute the answer in
+ // the normal domain.
if (!ec_bignum_to_scalar(group, &r_mont, ret->r) ||
!bn_to_montgomery_small(r_mont.words, order->top, r_mont.words,
order->top, group->order_mont) ||
- !bn_mod_mul_montgomery_small(s.words, order->top, priv_key.words,
- order->top, r_mont.words, order->top,
- group->order_mont)) {
+ !scalar_mod_mul_montgomery(group, &s, &priv_key, &r_mont)) {
goto err;
}
- // Compute s += m in constant time. Reduce one copy of |order| if necessary.
- // Note this does not leave |s| fully reduced. We have
- // |m| < 2^BN_num_bits(order), so subtracting |order| leaves
- // 0 <= |s| < 2^BN_num_bits(order).
- BN_ULONG carry = bn_add_words(s.words, s.words, m.words, order->top);
- BN_ULONG v = bn_sub_words(tmp.words, s.words, order->d, order->top) - carry;
- v = 0u - v;
- for (int i = 0; i < order->top; i++) {
- s.words[i] = constant_time_select_w(v, s.words[i], tmp.words[i]);
- }
+ // Compute tmp = m + priv_key * r.
+ scalar_add_loose(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. Although the
- // previous step did not fully reduce |s|, |bn_mod_mul_montgomery_small|
- // only requires the product not exceed R * |order|. |kinv_mont| is fully
- // reduced and |s| < 2^BN_num_bits(order) <= R, so this holds.
- if (!bn_mod_mul_montgomery_small(s.words, order->top, s.words, order->top,
- kinv_mont.words, order->top,
- group->order_mont) ||
+ // same technique as the previous multiplication works.
+ if (!scalar_mod_mul_montgomery_loose(group, &s, &tmp, &kinv_mont) ||
!bn_set_words(ret->s, s.words, order->top)) {
goto err;
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-25 01:23:24 +0000