Add secure DSA nonce flag.

Adam Langley · benlaurie · commit 8a99cb29d1f0 · 2013-06-13T17:26:07.000+01:00
This change adds the option to calculate (EC)DSA nonces by hashing the
message and private key along with entropy to avoid leaking the private
key if the PRNG fails.
diff --git a/crypto/bn/bn.h b/crypto/bn/bn.h
@@ -676,6 +676,10 @@ const BIGNUM *BN_get0_nist_prime_521(void);
 
 int (*BN_nist_mod_func(const BIGNUM *p))(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, BN_CTX *ctx);
 
+int BN_generate_dsa_nonce(BIGNUM *out, const BIGNUM *range, const BIGNUM *priv,
+			  const unsigned char *message, size_t message_len,
+			  BN_CTX *ctx);
+
 /* library internal functions */
 
 #define bn_expand(a,bits) ((((((bits+BN_BITS2-1))/BN_BITS2)) <= (a)->dmax)?\
@@ -868,6 +872,7 @@ void ERR_load_BN_strings(void);
 #define BN_R_NOT_INITIALIZED				 107
 #define BN_R_NO_INVERSE					 108
 #define BN_R_NO_SOLUTION				 116
+#define BN_R_PRIVATE_KEY_TOO_LARGE			 117
 #define BN_R_P_IS_NOT_PRIME				 112
 #define BN_R_TOO_MANY_ITERATIONS			 113
 #define BN_R_TOO_MANY_TEMPORARY_VARIABLES		 109
diff --git a/crypto/bn/bn_err.c b/crypto/bn/bn_err.c
@@ -1,6 +1,6 @@
 /* crypto/bn/bn_err.c */
 /* ====================================================================
- * Copyright (c) 1999-2007 The OpenSSL Project.  All rights reserved.
+ * Copyright (c) 1999-2013 The OpenSSL Project.  All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -132,6 +132,7 @@ static ERR_STRING_DATA BN_str_reasons[]=
 {ERR_REASON(BN_R_NOT_INITIALIZED)        ,"not initialized"},
 {ERR_REASON(BN_R_NO_INVERSE)             ,"no inverse"},
 {ERR_REASON(BN_R_NO_SOLUTION)            ,"no solution"},
+{ERR_REASON(BN_R_PRIVATE_KEY_TOO_LARGE)  ,"private key too large"},
 {ERR_REASON(BN_R_P_IS_NOT_PRIME)         ,"p is not prime"},
 {ERR_REASON(BN_R_TOO_MANY_ITERATIONS)    ,"too many iterations"},
 {ERR_REASON(BN_R_TOO_MANY_TEMPORARY_VARIABLES),"too many temporary variables"},
diff --git a/crypto/bn/bn_rand.c b/crypto/bn/bn_rand.c
@@ -116,6 +116,7 @@
 #include "cryptlib.h"
 #include "bn_lcl.h"
 #include <openssl/rand.h>
+#include <openssl/sha.h>
 
 static int bnrand(int pseudorand, BIGNUM *rnd, int bits, int top, int bottom)
 	{
@@ -313,3 +314,72 @@ int	BN_pseudo_rand_range(BIGNUM *r, const BIGNUM *range)
 	{
 	return bn_rand_range(1, r, range);
 	}
+
+#ifndef OPENSSL_NO_SHA512
+/* 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. */
+int BN_generate_dsa_nonce(BIGNUM *out, const BIGNUM *range, const BIGNUM* priv,
+			  const unsigned char *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. */
+	unsigned char random_bytes[64];
+	unsigned char digest[SHA512_DIGEST_LENGTH];
+	unsigned done, todo;
+	/* We generate |range|+8 bytes of random output. */
+	const unsigned num_k_bytes = BN_num_bytes(range) + 8;
+	unsigned char private_bytes[96];
+	unsigned char *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 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. */
+		BNerr(BN_F_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_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))
+		goto err;
+	if (BN_mod(out, out, range, ctx) != 1)
+		goto err;
+	ret = 1;
+
+err:
+	if (k_bytes)
+		OPENSSL_free(k_bytes);
+	return ret;
+	}
+#endif  /* OPENSSL_NO_SHA512 */
diff --git a/crypto/dsa/dsa.h b/crypto/dsa/dsa.h
@@ -91,13 +91,27 @@
 #define OPENSSL_DSA_FIPS_MIN_MODULUS_BITS 1024
 
 #define DSA_FLAG_CACHE_MONT_P	0x01
-#define DSA_FLAG_NO_EXP_CONSTTIME       0x02 /* new with 0.9.7h; the built-in DSA
-                                              * implementation now uses constant time
-                                              * modular exponentiation for secret exponents
-                                              * by default. This flag causes the
-                                              * faster variable sliding window method to
-                                              * be used for all exponents.
+#define DSA_FLAG_NO_EXP_CONSTTIME       0x02 /* new with 0.9.7h; the
+                                              * built-in DSA
+                                              * implementation now
+                                              * uses constant time
+                                              * modular exponentiation
+                                              * for secret exponents
+                                              * by default. This flag
+                                              * causes the faster
+                                              * variable sliding
+                                              * window method to be
+                                              * used for all
+                                              * exponents.
                                               */
+#define DSA_FLAG_NONCE_FROM_HASH	0x04 /* Causes the DSA nonce
+					      * to be calculated from
+					      * SHA512(private_key +
+					      * H(message) +
+					      * random). This
+					      * strengthens DSA
+					      * against a weak
+					      * PRNG. */
 
 /* If this flag is set the DSA method is FIPS compliant and can be used
  * in FIPS mode. This is set in the validated module method. If an
@@ -133,8 +147,9 @@ struct dsa_method
 	{
 	const char *name;
 	DSA_SIG * (*dsa_do_sign)(const unsigned char *dgst, int dlen, DSA *dsa);
-	int (*dsa_sign_setup)(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp,
-								BIGNUM **rp);
+	int (*dsa_sign_setup)(DSA *dsa, BN_CTX *ctx_in,
+			      BIGNUM **kinvp, BIGNUM **rp,
+			      const unsigned char *dgst, int dlen);
 	int (*dsa_do_verify)(const unsigned char *dgst, int dgst_len,
 			     DSA_SIG *sig, DSA *dsa);
 	int (*dsa_mod_exp)(DSA *dsa, BIGNUM *rr, BIGNUM *a1, BIGNUM *p1,
@@ -338,6 +353,7 @@ void ERR_load_DSA_strings(void);
 #define DSA_R_MISSING_PARAMETERS			 101
 #define DSA_R_MODULUS_TOO_LARGE				 103
 #define DSA_R_NEED_NEW_SETUP_VALUES			 110
+#define DSA_R_NONCE_CANNOT_BE_PRECOMPUTED		 114
 #define DSA_R_NO_PARAMETERS_SET				 107
 #define DSA_R_PARAMETER_ENCODING_ERROR			 105
 #define DSA_R_Q_NOT_PRIME				 113
diff --git a/crypto/dsa/dsa_err.c b/crypto/dsa/dsa_err.c
@@ -1,6 +1,6 @@
 /* crypto/dsa/dsa_err.c */
 /* ====================================================================
- * Copyright (c) 1999-2010 The OpenSSL Project.  All rights reserved.
+ * Copyright (c) 1999-2013 The OpenSSL Project.  All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -112,6 +112,7 @@ static ERR_STRING_DATA DSA_str_reasons[]=
 {ERR_REASON(DSA_R_MISSING_PARAMETERS)    ,"missing parameters"},
 {ERR_REASON(DSA_R_MODULUS_TOO_LARGE)     ,"modulus too large"},
 {ERR_REASON(DSA_R_NEED_NEW_SETUP_VALUES) ,"need new setup values"},
+{ERR_REASON(DSA_R_NONCE_CANNOT_BE_PRECOMPUTED),"nonce cannot be precomputed"},
 {ERR_REASON(DSA_R_NO_PARAMETERS_SET)     ,"no parameters set"},
 {ERR_REASON(DSA_R_PARAMETER_ENCODING_ERROR),"parameter encoding error"},
 {ERR_REASON(DSA_R_Q_NOT_PRIME)           ,"q not prime"},
diff --git a/crypto/dsa/dsa_ossl.c b/crypto/dsa/dsa_ossl.c
@@ -72,7 +72,9 @@
 #endif
 
 static DSA_SIG *dsa_do_sign(const unsigned char *dgst, int dlen, DSA *dsa);
-static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp);
+static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in,
+			  BIGNUM **kinvp, BIGNUM **rp,
+			  const unsigned char *dgst, int dlen);
 static int dsa_do_verify(const unsigned char *dgst, int dgst_len, DSA_SIG *sig,
 			 DSA *dsa);
 static int dsa_init(DSA *dsa);
@@ -176,7 +178,8 @@ static DSA_SIG *dsa_do_sign(const unsigned char *dgst, int dlen, DSA *dsa)
 redo:
 	if ((dsa->kinv == NULL) || (dsa->r == NULL))
 		{
-		if (!dsa->meth->dsa_sign_setup(dsa,ctx,&kinv,&r)) goto err;
+		if (!dsa->meth->dsa_sign_setup(dsa,ctx,&kinv,&r,dgst,dlen))
+			goto err;
 		}
 	else
 		{
@@ -235,7 +238,9 @@ static DSA_SIG *dsa_do_sign(const unsigned char *dgst, int dlen, DSA *dsa)
 	return(ret);
 	}
 
-static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp)
+static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in,
+			  BIGNUM **kinvp, BIGNUM **rp,
+			  const unsigned char *dgst, int dlen)
 	{
 	BN_CTX *ctx;
 	BIGNUM k,kq,*K,*kinv=NULL,*r=NULL;
@@ -261,8 +266,22 @@ static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp)
 
 	/* Get random k */
 	do
-		if (!BN_rand_range(&k, dsa->q)) goto err;
-	while (BN_is_zero(&k));
+		{
+#ifndef OPENSSL_NO_SHA512
+		if (dsa->flags & DSA_FLAG_NONCE_FROM_HASH)
+			{
+			/* If DSA_FLAG_NONCE_FROM_HASH is set then we calculate k from
+			 * SHA512(private_key + H(message) + random). This protects the
+			 * private key from a weak PRNG. */
+			if (!BN_generate_dsa_nonce(&k, dsa->q, dsa->priv_key, dgst,
+						   dlen, ctx))
+				goto err;
+			}
+		else
+#endif
+			if (!BN_rand_range(&k, dsa->q)) goto err;
+		} while (BN_is_zero(&k));
+
 	if ((dsa->flags & DSA_FLAG_NO_EXP_CONSTTIME) == 0)
 		{
 		BN_set_flags(&k, BN_FLG_CONSTTIME);
diff --git a/crypto/dsa/dsa_sign.c b/crypto/dsa/dsa_sign.c
@@ -72,5 +72,12 @@ DSA_SIG * DSA_do_sign(const unsigned char *dgst, int dlen, DSA *dsa)
 
 int DSA_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp)
 	{
-	return dsa->meth->dsa_sign_setup(dsa, ctx_in, kinvp, rp);
+	if (dsa->flags & DSA_FLAG_NONCE_FROM_HASH)
+		{
+		/* One cannot precompute the DSA nonce if it is required to
+		 * depend on the message. */
+		DSAerr(DSA_F_DSA_SIGN_SETUP, DSA_R_NONCE_CANNOT_BE_PRECOMPUTED);
+		return 0;
+		}
+	return dsa->meth->dsa_sign_setup(dsa, ctx_in, kinvp, rp, NULL, 0);
 	}
diff --git a/crypto/ec/ec.h b/crypto/ec/ec.h
@@ -823,6 +823,17 @@ void *EC_KEY_insert_key_method_data(EC_KEY *key, void *data,
 /* wrapper functions for the underlying EC_GROUP object */
 void EC_KEY_set_asn1_flag(EC_KEY *eckey, int asn1_flag);
 
+/** Sets whether ECDSA operations with the given key will calculate their k
+ * value from SHA512(private_key + message + random) in order to protect
+ * against a weak PRNG.
+ * \param  on  Whether to calculate k from a hash or not
+ */
+void EC_KEY_set_nonce_from_hash(EC_KEY *key, int on);
+
+/** Returns the value of nonce_from_hash
+ */
+int EC_KEY_get_nonce_from_hash(const EC_KEY *key);
+
 /** Creates a table of pre-computed multiples of the generator to 
  *  accelerate further EC_KEY operations.
  *  \param  key  EC_KEY object
diff --git a/crypto/ec/ec_key.c b/crypto/ec/ec_key.c
@@ -85,6 +85,7 @@ EC_KEY *EC_KEY_new(void)
 	ret->pub_key = NULL;
 	ret->priv_key= NULL;
 	ret->enc_flag= 0; 
+	ret->nonce_from_hash_flag = 0;
 	ret->conv_form = POINT_CONVERSION_UNCOMPRESSED;
 	ret->references= 1;
 	ret->method_data = NULL;
@@ -198,6 +199,7 @@ EC_KEY *EC_KEY_copy(EC_KEY *dest, const EC_KEY *src)
 
 	/* copy the rest */
 	dest->enc_flag  = src->enc_flag;
+	dest->nonce_from_hash_flag = src->nonce_from_hash_flag;
 	dest->conv_form = src->conv_form;
 	dest->version   = src->version;
 	dest->flags = src->flags;
@@ -589,6 +591,16 @@ void EC_KEY_set_enc_flags(EC_KEY *key, unsigned int flags)
 	key->enc_flag = flags;
 	}
 
+int EC_KEY_get_nonce_from_hash(const EC_KEY *key)
+	{
+	return key->nonce_from_hash_flag;
+	}
+
+void EC_KEY_set_nonce_from_hash(EC_KEY *key, int on)
+	{
+	key->nonce_from_hash_flag = on != 0;
+	}
+
 point_conversion_form_t EC_KEY_get_conv_form(const EC_KEY *key)
 	{
 	return key->conv_form;
diff --git a/crypto/ec/ec_lcl.h b/crypto/ec/ec_lcl.h
@@ -246,6 +246,7 @@ struct ec_key_st {
 	BIGNUM	 *priv_key;
 
 	unsigned int enc_flag;
+	char nonce_from_hash_flag;
 	point_conversion_form_t conv_form;
 
 	int 	references;
diff --git a/crypto/ecdsa/ecdsa.h b/crypto/ecdsa/ecdsa.h
@@ -264,6 +264,7 @@ void ERR_load_ECDSA_strings(void);
 #define ECDSA_R_ERR_EC_LIB				 102
 #define ECDSA_R_MISSING_PARAMETERS			 103
 #define ECDSA_R_NEED_NEW_SETUP_VALUES			 106
+#define ECDSA_R_NONCE_CANNOT_BE_PRECOMPUTED		 107
 #define ECDSA_R_RANDOM_NUMBER_GENERATION_FAILED		 104
 #define ECDSA_R_SIGNATURE_MALLOC_FAILED			 105
 
diff --git a/crypto/ecdsa/ecs_err.c b/crypto/ecdsa/ecs_err.c
@@ -1,6 +1,6 @@
 /* crypto/ecdsa/ecs_err.c */
 /* ====================================================================
- * Copyright (c) 1999-2006 The OpenSSL Project.  All rights reserved.
+ * Copyright (c) 1999-2013 The OpenSSL Project.  All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -84,6 +84,7 @@ static ERR_STRING_DATA ECDSA_str_reasons[]=
 {ERR_REASON(ECDSA_R_ERR_EC_LIB)          ,"err ec lib"},
 {ERR_REASON(ECDSA_R_MISSING_PARAMETERS)  ,"missing parameters"},
 {ERR_REASON(ECDSA_R_NEED_NEW_SETUP_VALUES),"need new setup values"},
+{ERR_REASON(ECDSA_R_NONCE_CANNOT_BE_PRECOMPUTED),"nonce cannot be precomputed"},
 {ERR_REASON(ECDSA_R_RANDOM_NUMBER_GENERATION_FAILED),"random number generation failed"},
 {ERR_REASON(ECDSA_R_SIGNATURE_MALLOC_FAILED),"signature malloc failed"},
 {0,NULL}
diff --git a/crypto/ecdsa/ecs_locl.h b/crypto/ecdsa/ecs_locl.h
@@ -70,8 +70,9 @@ struct ecdsa_method
 	const char *name;
 	ECDSA_SIG *(*ecdsa_do_sign)(const unsigned char *dgst, int dgst_len, 
 			const BIGNUM *inv, const BIGNUM *rp, EC_KEY *eckey);
-	int (*ecdsa_sign_setup)(EC_KEY *eckey, BN_CTX *ctx, BIGNUM **kinv, 
-			BIGNUM **r);
+	int (*ecdsa_sign_setup)(EC_KEY *eckey, BN_CTX *ctx,
+				BIGNUM **kinv, BIGNUM **r,
+				const unsigned char *dgst, int dlen);
 	int (*ecdsa_do_verify)(const unsigned char *dgst, int dgst_len, 
 			const ECDSA_SIG *sig, EC_KEY *eckey);
 #if 0
diff --git a/crypto/ecdsa/ecs_ossl.c b/crypto/ecdsa/ecs_ossl.c
diff --git a/crypto/ecdsa/ecs_sign.c b/crypto/ecdsa/ecs_sign.c

Original file line number	Diff line number	Diff line change
`@@ -72,5 +72,12 @@ DSA_SIG * DSA_do_sign(const unsigned char dgst, int dlen, DSA dsa)`
`72`	`72`
`73`	`73`	`int DSA_sign_setup(DSA dsa, BN_CTX ctx_in, BIGNUM kinvp, BIGNUM rp)`
`74`	`74`	`{`
`75`		`- return dsa->meth->dsa_sign_setup(dsa, ctx_in, kinvp, rp);`
	`75`	`+ if (dsa->flags & DSA_FLAG_NONCE_FROM_HASH)`
	`76`	`+ {`
	`77`	`+ /* One cannot precompute the DSA nonce if it is required to`
	`78`	`+ * depend on the message. */`
	`79`	`+ DSAerr(DSA_F_DSA_SIGN_SETUP, DSA_R_NONCE_CANNOT_BE_PRECOMPUTED);`
	`80`	`+ return 0;`
	`81`	`+ }`
	`82`	`+ return dsa->meth->dsa_sign_setup(dsa, ctx_in, kinvp, rp, NULL, 0);`
`76`	`83`	`}`