Implement deterministic ECDSA sign (RFC6979)

This PR is based off the contributions in PR #9223 by Jemmy1228.

It has been modified and reworked to:
(1) Work with providers
(2) Support ECDSA and DSA
(3) Add a KDF HMAC_DRBG implementation that shares code with the RAND HMAC_DRBG.

A nonce_type is passed around inside the Signing API's, in order to support any
future deterministic algorithms.

Reviewed-by: Tomas Mraz <tomas@openssl.org>
Reviewed-by: Paul Dale <pauli@openssl.org>
Reviewed-by: Hugo Landau <hlandau@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/18809)

3 files changed, 44 insertions, 17 deletions

diff --git a/crypto/dsa/dsa_local.h b/crypto/dsa/dsa_local.h
index cb7f903a04..38cb64a829 100644
--- a/crypto/dsa/dsa_local.h
+++ b/crypto/dsa/dsa_local.h
@@ -69,4 +69,6 @@ struct dsa_method {
     int (*dsa_keygen) (DSA *dsa);
 };
 
-DSA_SIG *ossl_dsa_do_sign_int(const unsigned char *dgst, int dlen, DSA *dsa);
+DSA_SIG *ossl_dsa_do_sign_int(const unsigned char *dgst, int dlen, DSA *dsa,
+                              unsigned int nonce_type, const char *digestname,
+                              OSSL_LIB_CTX *libctx, const char *propq);
diff --git a/crypto/dsa/dsa_ossl.c b/crypto/dsa/dsa_ossl.c
index 86d89f4c72..888e415724 100644
--- a/crypto/dsa/dsa_ossl.c
+++ b/crypto/dsa/dsa_ossl.c
@@ -20,12 +20,15 @@
 #include <openssl/sha.h>
 #include "dsa_local.h"
 #include <openssl/asn1.h>
+#include "internal/deterministic_nonce.h"
 
 static DSA_SIG *dsa_do_sign(const unsigned char *dgst, int dlen, DSA *dsa);
 static int dsa_sign_setup_no_digest(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);
+                          BIGNUM **rp, const unsigned char *dgst, int dlen,
+                          unsigned int nonce_type, const char *digestname,
+                          OSSL_LIB_CTX *libctx, const char *propq);
 static int dsa_do_verify(const unsigned char *dgst, int dgst_len,
                          DSA_SIG *sig, DSA *dsa);
 static int dsa_init(DSA *dsa);
@@ -67,7 +70,9 @@ const DSA_METHOD *DSA_OpenSSL(void)
     return &openssl_dsa_meth;
 }
 
-DSA_SIG *ossl_dsa_do_sign_int(const unsigned char *dgst, int dlen, DSA *dsa)
+DSA_SIG *ossl_dsa_do_sign_int(const unsigned char *dgst, int dlen, DSA *dsa,
+                              unsigned int nonce_type, const char *digestname,
+                              OSSL_LIB_CTX *libctx, const char *propq)
 {
     BIGNUM *kinv = NULL;
     BIGNUM *m, *blind, *blindm, *tmp;
@@ -106,7 +111,8 @@ DSA_SIG *ossl_dsa_do_sign_int(const unsigned char *dgst, int dlen, DSA *dsa)
         goto err;
 
  redo:
-    if (!dsa_sign_setup(dsa, ctx, &kinv, &ret->r, dgst, dlen))
+    if (!dsa_sign_setup(dsa, ctx, &kinv, &ret->r, dgst, dlen,
+                        nonce_type, digestname, libctx, propq))
         goto err;
 
     if (dlen > BN_num_bytes(dsa->params.q))
@@ -185,18 +191,22 @@ DSA_SIG *ossl_dsa_do_sign_int(const unsigned char *dgst, int dlen, DSA *dsa)
 
 static DSA_SIG *dsa_do_sign(const unsigned char *dgst, int dlen, DSA *dsa)
 {
-    return ossl_dsa_do_sign_int(dgst, dlen, dsa);
+    return ossl_dsa_do_sign_int(dgst, dlen, dsa,
+                                0, NULL, NULL, NULL);
 }
 
 static int dsa_sign_setup_no_digest(DSA *dsa, BN_CTX *ctx_in,
                                     BIGNUM **kinvp, BIGNUM **rp)
 {
-    return dsa_sign_setup(dsa, ctx_in, kinvp, rp, NULL, 0);
+    return dsa_sign_setup(dsa, ctx_in, kinvp, rp, NULL, 0,
+                          0, NULL, NULL, NULL);
 }
 
 static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in,
                           BIGNUM **kinvp, BIGNUM **rp,
-                          const unsigned char *dgst, int dlen)
+                          const unsigned char *dgst, int dlen,
+                          unsigned int nonce_type, const char *digestname,
+                          OSSL_LIB_CTX *libctx, const char *propq)
 {
     BN_CTX *ctx = NULL;
     BIGNUM *k, *kinv = NULL, *r = *rp;
@@ -243,13 +253,24 @@ static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in,
     /* Get random k */
     do {
         if (dgst != NULL) {
-            /*
-             * 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->params.q, dsa->priv_key, dgst,
-                                       dlen, ctx))
-                goto err;
+            if (nonce_type == 1) {
+#ifndef FIPS_MODULE
+                if (!ossl_gen_deterministic_nonce_rfc6979(k, dsa->params.q,
+                                                          dsa->priv_key,
+                                                          dgst, dlen,
+                                                          digestname,
+                                                          libctx, propq))
+#endif
+                    goto err;
+            } else {
+                /*
+                 * 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->params.q, dsa->priv_key, dgst,
+                                           dlen, ctx))
+                    goto err;
+            }
         } else if (!BN_priv_rand_range_ex(k, dsa->params.q, 0, ctx))
             goto err;
     } while (BN_is_zero(k));
diff --git a/crypto/dsa/dsa_sign.c b/crypto/dsa/dsa_sign.c
index d942fa2afe..96d103d6f2 100644
--- a/crypto/dsa/dsa_sign.c
+++ b/crypto/dsa/dsa_sign.c
@@ -151,7 +151,9 @@ int DSA_SIG_set0(DSA_SIG *sig, BIGNUM *r, BIGNUM *s)
 }
 
 int ossl_dsa_sign_int(int type, const unsigned char *dgst, int dlen,
-                      unsigned char *sig, unsigned int *siglen, DSA *dsa)
+                      unsigned char *sig, unsigned int *siglen, DSA *dsa,
+                      unsigned int nonce_type, const char *digestname,
+                      OSSL_LIB_CTX *libctx, const char *propq)
 {
     DSA_SIG *s;
 
@@ -159,7 +161,8 @@ int ossl_dsa_sign_int(int type, const unsigned char *dgst, int dlen,
     if (dsa->libctx == NULL || dsa->meth != DSA_get_default_method())
         s = DSA_do_sign(dgst, dlen, dsa);
     else
-        s = ossl_dsa_do_sign_int(dgst, dlen, dsa);
+        s = ossl_dsa_do_sign_int(dgst, dlen, dsa,
+                                 nonce_type, digestname, libctx, propq);
     if (s == NULL) {
         *siglen = 0;
         return 0;
@@ -172,7 +175,8 @@ int ossl_dsa_sign_int(int type, const unsigned char *dgst, int dlen,
 int DSA_sign(int type, const unsigned char *dgst, int dlen,
              unsigned char *sig, unsigned int *siglen, DSA *dsa)
 {
-    return ossl_dsa_sign_int(type, dgst, dlen, sig, siglen, dsa);
+    return ossl_dsa_sign_int(type, dgst, dlen, sig, siglen, dsa,
+                             0, NULL, NULL, NULL);
 }
 
 /* data has already been hashed (probably with SHA or SHA-1). */