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"},