Safe (EC)DSA nonces.
This change causes (EC)DSA nonces be to calculated by hashing the
message and private key along with entropy.
diff --git a/crypto/bn/bn.h b/crypto/bn/bn.h
index 79b918a..99e0efa 100644
--- a/crypto/bn/bn.h
+++ b/crypto/bn/bn.h
@@ -520,6 +520,16 @@
/* BN_pseudo_rand_range is an alias for BN_rand_range. */
int BN_pseudo_rand_range(BIGNUM *rnd, const BIGNUM *range);
+/* BN_generate_dsa_nonce generates a random number 0 <= out < range. Unlike
+ * BN_rand_range, it also includes the contents of |priv| and |message| in the
+ * generation so that an RNG failure isn't fatal as long as |priv| remains
+ * secret. This is intended for use in DSA and ECDSA where an RNG weakness
+ * leads directly to private key exposure unless this function is used.
+ * It returns one on success and zero on error. */
+int BN_generate_dsa_nonce(BIGNUM *out, const BIGNUM *range, const BIGNUM *priv,
+ const uint8_t *message, size_t message_len,
+ BN_CTX *ctx);
+
/* BN_GENCB holds a callback function that is used by generation functions that
* can take a very long time to complete. Use |BN_GENCB_set| to initialise a
* |BN_GENCB| structure.
@@ -769,6 +779,7 @@
#define BN_F_BN_mod_lshift_quick 119
#define BN_F_BN_CTX_new 120
#define BN_F_BN_mod_inverse_no_branch 121
+#define BN_F_BN_generate_dsa_nonce 122
#define BN_R_NOT_A_SQUARE 100
#define BN_R_TOO_MANY_ITERATIONS 101
#define BN_R_INPUT_NOT_REDUCED 102
@@ -783,5 +794,6 @@
#define BN_R_INVALID_RANGE 111
#define BN_R_ARG2_LT_ARG3 112
#define BN_R_BIGNUM_TOO_LONG 113
+#define BN_R_PRIVATE_KEY_TOO_LARGE 114
#endif /* OPENSSL_HEADER_BN_H */
diff --git a/crypto/bn/bn_error.c b/crypto/bn/bn_error.c
index a73571c..4319d88 100644
--- a/crypto/bn/bn_error.c
+++ b/crypto/bn/bn_error.c
@@ -25,6 +25,7 @@
{ERR_PACK(ERR_LIB_BN, BN_F_BN_div, 0), "BN_div"},
{ERR_PACK(ERR_LIB_BN, BN_F_BN_div_recp, 0), "BN_div_recp"},
{ERR_PACK(ERR_LIB_BN, BN_F_BN_exp, 0), "BN_exp"},
+ {ERR_PACK(ERR_LIB_BN, BN_F_BN_generate_dsa_nonce, 0), "BN_generate_dsa_nonce"},
{ERR_PACK(ERR_LIB_BN, BN_F_BN_mod_exp2_mont, 0), "BN_mod_exp2_mont"},
{ERR_PACK(ERR_LIB_BN, BN_F_BN_mod_exp_mont, 0), "BN_mod_exp_mont"},
{ERR_PACK(ERR_LIB_BN, BN_F_BN_mod_exp_mont_consttime, 0), "BN_mod_exp_mont_consttime"},
@@ -50,6 +51,7 @@
{ERR_PACK(ERR_LIB_BN, 0, BN_R_NOT_A_SQUARE), "NOT_A_SQUARE"},
{ERR_PACK(ERR_LIB_BN, 0, BN_R_NOT_INITIALIZED), "NOT_INITIALIZED"},
{ERR_PACK(ERR_LIB_BN, 0, BN_R_NO_INVERSE), "NO_INVERSE"},
+ {ERR_PACK(ERR_LIB_BN, 0, BN_R_PRIVATE_KEY_TOO_LARGE), "PRIVATE_KEY_TOO_LARGE"},
{ERR_PACK(ERR_LIB_BN, 0, BN_R_P_IS_NOT_PRIME), "P_IS_NOT_PRIME"},
{ERR_PACK(ERR_LIB_BN, 0, BN_R_TOO_MANY_ITERATIONS), "TOO_MANY_ITERATIONS"},
{ERR_PACK(ERR_LIB_BN, 0, BN_R_TOO_MANY_TEMPORARY_VARIABLES), "TOO_MANY_TEMPORARY_VARIABLES"},
diff --git a/crypto/bn/random.c b/crypto/bn/random.c
index 1f1d732..13df050 100644
--- a/crypto/bn/random.c
+++ b/crypto/bn/random.c
@@ -111,6 +111,7 @@
#include <openssl/err.h>
#include <openssl/mem.h>
#include <openssl/rand.h>
+#include <openssl/sha.h>
int BN_rand(BIGNUM *rnd, int bits, int top, int bottom) {
uint8_t *buf = NULL;
@@ -235,3 +236,68 @@
int BN_pseudo_rand_range(BIGNUM *r, const BIGNUM *range) {
return BN_rand_range(r, range);
}
+
+int BN_generate_dsa_nonce(BIGNUM *out, const BIGNUM *range, const BIGNUM *priv,
+ const uint8_t *message, size_t message_len,
+ BN_CTX *ctx) {
+ SHA512_CTX sha;
+ /* We use 512 bits of random data per iteration to
+ * ensure that we have at least |range| bits of randomness. */
+ uint8_t random_bytes[64];
+ uint8_t digest[SHA512_DIGEST_LENGTH];
+ size_t done, todo;
+ /* We generate |range|+8 bytes of random output. */
+ const unsigned num_k_bytes = BN_num_bytes(range) + 8;
+ uint8_t private_bytes[96];
+ uint8_t *k_bytes;
+ int ret = 0;
+
+ k_bytes = OPENSSL_malloc(num_k_bytes);
+ if (!k_bytes) {
+ goto err;
+ }
+
+ /* We copy |priv| into a local buffer to avoid furthur exposing its
+ * length. */
+ todo = sizeof(priv->d[0]) * priv->top;
+ if (todo > sizeof(private_bytes)) {
+ /* No reasonable DSA or ECDSA key should have a private key
+ * this large and we don't handle this case in order to avoid
+ * leaking the length of the private key. */
+ OPENSSL_PUT_ERROR(BN, BN_generate_dsa_nonce, BN_R_PRIVATE_KEY_TOO_LARGE);
+ goto err;
+ }
+ memcpy(private_bytes, priv->d, todo);
+ memset(private_bytes + todo, 0, sizeof(private_bytes) - todo);
+
+ for (done = 0; done < num_k_bytes;) {
+ if (RAND_pseudo_bytes(random_bytes, sizeof(random_bytes)) != 1) {
+ goto err;
+ }
+ SHA512_Init(&sha);
+ SHA512_Update(&sha, &done, sizeof(done));
+ SHA512_Update(&sha, private_bytes, sizeof(private_bytes));
+ SHA512_Update(&sha, message, message_len);
+ SHA512_Update(&sha, random_bytes, sizeof(random_bytes));
+ SHA512_Final(digest, &sha);
+
+ todo = num_k_bytes - done;
+ if (todo > SHA512_DIGEST_LENGTH) {
+ todo = SHA512_DIGEST_LENGTH;
+ }
+ memcpy(k_bytes + done, digest, todo);
+ done += todo;
+ }
+
+ if (!BN_bin2bn(k_bytes, num_k_bytes, out) ||
+ BN_mod(out, out, range, ctx) != 1) {
+ goto err;
+ }
+ ret = 1;
+
+err:
+ if (k_bytes) {
+ OPENSSL_free(k_bytes);
+ }
+ return ret;
+}
diff --git a/crypto/dsa/dsa.c b/crypto/dsa/dsa.c
index 4ae6876..8c66ddf 100644
--- a/crypto/dsa/dsa.c
+++ b/crypto/dsa/dsa.c
@@ -313,10 +313,10 @@
int DSA_sign_setup(const DSA *dsa, BN_CTX *ctx, BIGNUM **out_kinv,
BIGNUM **out_r) {
if (dsa->meth->sign_setup) {
- return dsa->meth->sign_setup(dsa, ctx, out_kinv, out_r);
+ return dsa->meth->sign_setup(dsa, ctx, out_kinv, out_r, NULL, 0);
}
- return DSA_default_method.sign_setup(dsa, ctx, out_kinv, out_r);
+ return DSA_default_method.sign_setup(dsa, ctx, out_kinv, out_r, NULL, 0);
}
int DSA_get_ex_new_index(long argl, void *argp, CRYPTO_EX_new *new_func,
diff --git a/crypto/dsa/dsa.h b/crypto/dsa/dsa.h
index 857edc0..09fafb0 100644
--- a/crypto/dsa/dsa.h
+++ b/crypto/dsa/dsa.h
@@ -304,7 +304,8 @@
DSA_SIG *(*sign)(const uint8_t *digest, size_t digest_len, DSA *dsa);
- int (*sign_setup)(const DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp);
+ int (*sign_setup)(const DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp,
+ const uint8_t *digest, size_t digest_len);
int (*verify)(int *out_valid, const uint8_t *digest, size_t digest_len,
DSA_SIG *sig, const DSA *dsa);
diff --git a/crypto/dsa/dsa_impl.c b/crypto/dsa/dsa_impl.c
index dacc742..27232bb 100644
--- a/crypto/dsa/dsa_impl.c
+++ b/crypto/dsa/dsa_impl.c
@@ -74,7 +74,7 @@
#define DSS_prime_checks 50
static int sign_setup(const DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp,
- BIGNUM **rp) {
+ BIGNUM **rp, const uint8_t *digest, size_t digest_len) {
BN_CTX *ctx;
BIGNUM k, kq, *K, *kinv = NULL, *r = NULL;
int ret = 0;
@@ -102,7 +102,18 @@
/* Get random k */
do {
- if (!BN_rand_range(&k, dsa->q)) {
+ /* If possible, we'll include the private key and message digest in the k
+ * generation. The |digest| argument is only empty if |DSA_sign_setup| is
+ * being used. */
+ int ok;
+
+ if (digest_len > 0) {
+ ok = BN_generate_dsa_nonce(&k, dsa->q, dsa->priv_key, digest, digest_len,
+ ctx);
+ } else {
+ ok = BN_rand_range(&k, dsa->q);
+ }
+ if (!ok) {
goto err;
}
} while (BN_is_zero(&k));
diff --git a/crypto/ecdsa/ecdsa.c b/crypto/ecdsa/ecdsa.c
index cfe9ef6..02c1a36 100644
--- a/crypto/ecdsa/ecdsa.c
+++ b/crypto/ecdsa/ecdsa.c
@@ -222,8 +222,9 @@
return ret;
}
-int ECDSA_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, BIGNUM **kinvp,
- BIGNUM **rp) {
+static int ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, BIGNUM **kinvp,
+ BIGNUM **rp, const uint8_t *digest,
+ size_t digest_len) {
BN_CTX *ctx = NULL;
BIGNUM *k = NULL, *r = NULL, *order = NULL, *X = NULL;
EC_POINT *tmp_point = NULL;
@@ -231,13 +232,13 @@
int ret = 0;
if (eckey == NULL || (group = EC_KEY_get0_group(eckey)) == NULL) {
- OPENSSL_PUT_ERROR(ECDSA, ECDSA_sign_setup, ERR_R_PASSED_NULL_PARAMETER);
+ OPENSSL_PUT_ERROR(ECDSA, ecdsa_sign_setup, ERR_R_PASSED_NULL_PARAMETER);
return 0;
}
if (ctx_in == NULL) {
if ((ctx = BN_CTX_new()) == NULL) {
- OPENSSL_PUT_ERROR(ECDSA, ECDSA_sign_setup, ERR_R_MALLOC_FAILURE);
+ OPENSSL_PUT_ERROR(ECDSA, ecdsa_sign_setup, ERR_R_MALLOC_FAILURE);
return 0;
}
} else {
@@ -249,24 +250,34 @@
order = BN_new();
X = BN_new();
if (!k || !r || !order || !X) {
- OPENSSL_PUT_ERROR(ECDSA, ECDSA_sign_setup, ERR_R_MALLOC_FAILURE);
+ OPENSSL_PUT_ERROR(ECDSA, ecdsa_sign_setup, ERR_R_MALLOC_FAILURE);
goto err;
}
tmp_point = EC_POINT_new(group);
if (tmp_point == NULL) {
- OPENSSL_PUT_ERROR(ECDSA, ECDSA_sign_setup, ERR_R_EC_LIB);
+ OPENSSL_PUT_ERROR(ECDSA, ecdsa_sign_setup, ERR_R_EC_LIB);
goto err;
}
if (!EC_GROUP_get_order(group, order, ctx)) {
- OPENSSL_PUT_ERROR(ECDSA, ECDSA_sign_setup, ERR_R_EC_LIB);
+ OPENSSL_PUT_ERROR(ECDSA, ecdsa_sign_setup, ERR_R_EC_LIB);
goto err;
}
do {
- /* get random k */
+ /* If possible, we'll include the private key and message digest in the k
+ * generation. The |digest| argument is only empty if |ECDSA_sign_setup| is
+ * being used. */
do {
- if (!BN_rand_range(k, order)) {
- OPENSSL_PUT_ERROR(ECDSA, ECDSA_sign_setup,
+ int ok;
+
+ if (digest_len > 0) {
+ ok = BN_generate_dsa_nonce(k, order, EC_KEY_get0_private_key(eckey),
+ digest, digest_len, ctx);
+ } else {
+ ok = BN_rand_range(k, order);
+ }
+ if (!ok) {
+ OPENSSL_PUT_ERROR(ECDSA, ecdsa_sign_setup,
ECDSA_R_RANDOM_NUMBER_GENERATION_FAILED);
goto err;
}
@@ -287,23 +298,23 @@
/* compute r the x-coordinate of generator * k */
if (!EC_POINT_mul(group, tmp_point, k, NULL, NULL, ctx)) {
- OPENSSL_PUT_ERROR(ECDSA, ECDSA_sign_setup, ERR_R_EC_LIB);
+ OPENSSL_PUT_ERROR(ECDSA, ecdsa_sign_setup, ERR_R_EC_LIB);
goto err;
}
if (!EC_POINT_get_affine_coordinates_GFp(group, tmp_point, X, NULL, ctx)) {
- OPENSSL_PUT_ERROR(ECDSA, ECDSA_sign_setup, ERR_R_EC_LIB);
+ OPENSSL_PUT_ERROR(ECDSA, ecdsa_sign_setup, ERR_R_EC_LIB);
goto err;
}
if (!BN_nnmod(r, X, order, ctx)) {
- OPENSSL_PUT_ERROR(ECDSA, ECDSA_sign_setup, ERR_R_BN_LIB);
+ OPENSSL_PUT_ERROR(ECDSA, ecdsa_sign_setup, ERR_R_BN_LIB);
goto err;
}
} while (BN_is_zero(r));
/* compute the inverse of k */
if (!BN_mod_inverse(k, k, order, ctx)) {
- OPENSSL_PUT_ERROR(ECDSA, ECDSA_sign_setup, ERR_R_BN_LIB);
+ OPENSSL_PUT_ERROR(ECDSA, ecdsa_sign_setup, ERR_R_BN_LIB);
goto err;
}
/* clear old values if necessary */
@@ -339,6 +350,10 @@
return ret;
}
+int ECDSA_sign_setup(EC_KEY *eckey, BN_CTX *ctx, BIGNUM **kinv, BIGNUM **rp) {
+ return ecdsa_sign_setup(eckey, ctx, kinv, rp, NULL, 0);
+}
+
ECDSA_SIG *ECDSA_do_sign_ex(const uint8_t *digest, size_t digest_len,
const BIGNUM *in_kinv, const BIGNUM *in_r,
EC_KEY *eckey) {
@@ -385,7 +400,7 @@
}
for (;;) {
if (in_kinv == NULL || in_r == NULL) {
- if (!ECDSA_sign_setup(eckey, ctx, &kinv, &ret->r)) {
+ if (!ecdsa_sign_setup(eckey, ctx, &kinv, &ret->r, digest, digest_len)) {
OPENSSL_PUT_ERROR(ECDSA, ECDSA_do_sign_ex, ERR_R_ECDSA_LIB);
goto err;
}
diff --git a/crypto/ecdsa/ecdsa.h b/crypto/ecdsa/ecdsa.h
index 6ad7ad2..8a74ecb 100644
--- a/crypto/ecdsa/ecdsa.h
+++ b/crypto/ecdsa/ecdsa.h
@@ -178,6 +178,7 @@
#define ECDSA_F_ECDSA_sign_setup 102
#define ECDSA_F_ECDSA_do_sign_ex 103
#define ECDSA_F_ECDSA_sign_ex 104
+#define ECDSA_F_ecdsa_sign_setup 105
#define ECDSA_R_RANDOM_NUMBER_GENERATION_FAILED 100
#define ECDSA_R_NEED_NEW_SETUP_VALUES 101
#define ECDSA_R_MISSING_PARAMETERS 102
diff --git a/crypto/ecdsa/ecdsa_error.c b/crypto/ecdsa/ecdsa_error.c
index 4de508a..39ba873 100644
--- a/crypto/ecdsa/ecdsa_error.c
+++ b/crypto/ecdsa/ecdsa_error.c
@@ -22,6 +22,7 @@
{ERR_PACK(ERR_LIB_ECDSA, ECDSA_F_ECDSA_sign_ex, 0), "ECDSA_sign_ex"},
{ERR_PACK(ERR_LIB_ECDSA, ECDSA_F_ECDSA_sign_setup, 0), "ECDSA_sign_setup"},
{ERR_PACK(ERR_LIB_ECDSA, ECDSA_F_digest_to_bn, 0), "digest_to_bn"},
+ {ERR_PACK(ERR_LIB_ECDSA, ECDSA_F_ecdsa_sign_setup, 0), "ecdsa_sign_setup"},
{ERR_PACK(ERR_LIB_ECDSA, 0, ECDSA_R_BAD_SIGNATURE), "BAD_SIGNATURE"},
{ERR_PACK(ERR_LIB_ECDSA, 0, ECDSA_R_MISSING_PARAMETERS), "MISSING_PARAMETERS"},
{ERR_PACK(ERR_LIB_ECDSA, 0, ECDSA_R_NEED_NEW_SETUP_VALUES), "NEED_NEW_SETUP_VALUES"},
