Add secure DSA nonce flag.
authorAdam Langley <agl@chromium.org>
Thu, 24 Jan 2013 21:27:28 +0000 (16:27 -0500)
committerBen Laurie <ben@links.org>
Thu, 13 Jun 2013 16:26:07 +0000 (17:26 +0100)
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.

15 files changed:
crypto/bn/bn.h
crypto/bn/bn_err.c
crypto/bn/bn_rand.c
crypto/dsa/dsa.h
crypto/dsa/dsa_err.c
crypto/dsa/dsa_ossl.c
crypto/dsa/dsa_sign.c
crypto/ec/ec.h
crypto/ec/ec_key.c
crypto/ec/ec_lcl.h
crypto/ecdsa/ecdsa.h
crypto/ecdsa/ecs_err.c
crypto/ecdsa/ecs_locl.h
crypto/ecdsa/ecs_ossl.c
crypto/ecdsa/ecs_sign.c

index d7397ca..7c23c01 100644 (file)
@@ -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
index cdc15e6..18a28ec 100644 (file)
@@ -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"},
index 8d74895..d550f49 100644 (file)
 #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 */
index 408ee11..28aa8a3 100644 (file)
 #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
index a46fade..353d81a 100644 (file)
@@ -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"},
index 485cff0..d1f8060 100644 (file)
@@ -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 @@ err:
        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);
index 599093a..b7e4caa 100644 (file)
@@ -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);
        }
index 0dcad23..17fc91c 100644 (file)
@@ -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
index a91b9dc..7a15e5f 100644 (file)
@@ -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;
index da7967d..6f714c7 100644 (file)
@@ -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;
index cd6d19c..865c330 100644 (file)
@@ -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
 
index 98e38d5..17ccb40 100644 (file)
@@ -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}
index cb3be13..46f7ad9 100644 (file)
@@ -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
index 8336bce..113e60c 100644 (file)
 #include <openssl/err.h>
 #include <openssl/obj_mac.h>
 #include <openssl/bn.h>
+#include <openssl/rand.h>
 
 static ECDSA_SIG *ecdsa_do_sign(const unsigned char *dgst, int dlen, 
                const BIGNUM *, const BIGNUM *, EC_KEY *eckey);
-static 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 unsigned char *dgst, int dlen);
 static int ecdsa_do_verify(const unsigned char *dgst, int dgst_len, 
                const ECDSA_SIG *sig, EC_KEY *eckey);
 
@@ -88,8 +90,9 @@ const ECDSA_METHOD *ECDSA_OpenSSL(void)
        return &openssl_ecdsa_meth;
 }
 
-static 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 unsigned char *dgst, int dlen)
 {
        BN_CTX   *ctx = NULL;
        BIGNUM   *k = NULL, *r = NULL, *order = NULL, *X = NULL;
@@ -143,11 +146,26 @@ static int ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, BIGNUM **kinvp,
        {
                /* get random k */      
                do
-                       if (!BN_rand_range(k, order))
+#ifndef OPENSSL_NO_SHA512
+                       if (EC_KEY_get_nonce_from_hash(eckey))
                        {
-                               ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP,
-                                ECDSA_R_RANDOM_NUMBER_GENERATION_FAILED);      
-                               goto err;
+                               if (!BN_generate_dsa_nonce(k, order, EC_KEY_get0_private_key(eckey),
+                                                          dgst, dlen, ctx))
+                                       {
+                                       ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP,
+                                                ECDSA_R_RANDOM_NUMBER_GENERATION_FAILED);
+                                       goto err;
+                                       }
+                       }
+                       else
+#endif
+                       {
+                               if (!BN_rand_range(k, order))
+                               {
+                                       ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP,
+                                                ECDSA_R_RANDOM_NUMBER_GENERATION_FAILED);
+                                       goto err;
+                               }
                        }
                while (BN_is_zero(k));
 
@@ -302,8 +320,7 @@ static ECDSA_SIG *ecdsa_do_sign(const unsigned char *dgst, int dgst_len,
        {
                if (in_kinv == NULL || in_r == NULL)
                {
-                       if (!ecdsa->meth->ecdsa_sign_setup(eckey, ctx,
-                                                               &kinv, &ret->r))
+                       if (!ecdsa->meth->ecdsa_sign_setup(eckey, ctx, &kinv, &ret->r, dgst, dgst_len))
                        {
                                ECDSAerr(ECDSA_F_ECDSA_DO_SIGN,ERR_R_ECDSA_LIB);
                                goto err;
index 353d5af..ea79a24 100644 (file)
@@ -58,6 +58,7 @@
 #include <openssl/engine.h>
 #endif
 #include <openssl/rand.h>
+#include <openssl/err.h>
 
 ECDSA_SIG *ECDSA_do_sign(const unsigned char *dgst, int dlen, EC_KEY *eckey)
 {
@@ -102,5 +103,12 @@ int ECDSA_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, BIGNUM **kinvp,
        ECDSA_DATA *ecdsa = ecdsa_check(eckey);
        if (ecdsa == NULL)
                return 0;
-       return ecdsa->meth->ecdsa_sign_setup(eckey, ctx_in, kinvp, rp); 
+       if (EC_KEY_get_nonce_from_hash(eckey))
+               {
+               /* You cannot precompute the ECDSA nonce if it is required to
+                * depend on the message. */
+               ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ECDSA_R_NONCE_CANNOT_BE_PRECOMPUTED);
+               return 0;
+               }
+       return ecdsa->meth->ecdsa_sign_setup(eckey, ctx_in, kinvp, rp, NULL, 0);
 }