Fix infinite loops in DSA sign code.

Fixes #20268

Values such as q=1 or priv=0 caused infinite loops when calling
DSA_sign() without these changes.

There are other cases where bad domain parameters may have caused
infinite loops where the retry counter has been added. The simpler case
of priv=0 also hits this case. q=1 caused an infinite loop in the setup.

The max retry value has been set to an arbitrary value of 8 (it is
unlikely to ever do a single retry for valid values).

The minimum q bits was set to an arbitrary value of 128 (160 is still
used for legacy reasons when using 512 bit keys).

Thanks @guidovranken for detecting this, and @davidben for his
insightful analysis.

Reviewed-by: Matt Caswell <matt@openssl.org>
Reviewed-by: Paul Dale <pauli@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/20384)

3 files changed, 24 insertions, 10 deletions

diff --git a/crypto/dsa/dsa_err.c b/crypto/dsa/dsa_err.c
index 5685d5e83e..a92ca61664 100644
--- a/crypto/dsa/dsa_err.c
+++ b/crypto/dsa/dsa_err.c
@@ -1,6 +1,6 @@
 /*
  * Generated by util/mkerr.pl DO NOT EDIT
- * Copyright 1995-2021 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright 1995-2023 The OpenSSL Project Authors. All Rights Reserved.
  *
  * Licensed under the Apache License 2.0 (the "License").  You may not use
  * this file except in compliance with the License.  You can obtain a copy
@@ -36,6 +36,7 @@ static const ERR_STRING_DATA DSA_str_reasons[] = {
     {ERR_PACK(ERR_LIB_DSA, 0, DSA_R_Q_NOT_PRIME), "q not prime"},
     {ERR_PACK(ERR_LIB_DSA, 0, DSA_R_SEED_LEN_SMALL),
     "seed_len is less than the length of q"},
+    {ERR_PACK(ERR_LIB_DSA, 0, DSA_R_TOO_MANY_RETRIES), "too many retries"},
     {0, NULL}
 };
 
diff --git a/crypto/dsa/dsa_ossl.c b/crypto/dsa/dsa_ossl.c
index 888e415724..822e51786a 100644
--- a/crypto/dsa/dsa_ossl.c
+++ b/crypto/dsa/dsa_ossl.c
@@ -22,6 +22,9 @@
 #include <openssl/asn1.h>
 #include "internal/deterministic_nonce.h"
 
+#define MIN_DSA_SIGN_QBITS   128
+#define MAX_DSA_SIGN_RETRIES 8
+
 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);
@@ -80,6 +83,7 @@ DSA_SIG *ossl_dsa_do_sign_int(const unsigned char *dgst, int dlen, DSA *dsa,
     int reason = ERR_R_BN_LIB;
     DSA_SIG *ret = NULL;
     int rv = 0;
+    int retries = 0;
 
     if (dsa->params.p == NULL
         || dsa->params.q == NULL
@@ -135,7 +139,10 @@ DSA_SIG *ossl_dsa_do_sign_int(const unsigned char *dgst, int dlen, DSA *dsa,
      *   s := blind^-1 * k^-1 * (blind * m + blind * r * priv_key) mod q
      */
 
-    /* Generate a blinding value */
+    /*
+     * Generate a blinding value
+     * The size of q is tested in dsa_sign_setup() so there should not be an infinite loop here.
+     */
     do {
         if (!BN_priv_rand_ex(blind, BN_num_bits(dsa->params.q) - 1,
                              BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY, 0, ctx))
@@ -170,14 +177,19 @@ DSA_SIG *ossl_dsa_do_sign_int(const unsigned char *dgst, int dlen, DSA *dsa,
         goto err;
 
     /*
-     * Redo if r or s is zero as required by FIPS 186-3: this is very
-     * unlikely.
+     * Redo if r or s is zero as required by FIPS 186-4: Section 4.6
+     * This is very unlikely.
+     * Limit the retries so there is no possibility of an infinite
+     * loop for bad domain parameter values.
      */
-    if (BN_is_zero(ret->r) || BN_is_zero(ret->s))
+    if (BN_is_zero(ret->r) || BN_is_zero(ret->s)) {
+        if (retries++ > MAX_DSA_SIGN_RETRIES) {
+            reason = DSA_R_TOO_MANY_RETRIES;
+            goto err;
+        }
         goto redo;
-
+    }
     rv = 1;
-
  err:
     if (rv == 0) {
         ERR_raise(ERR_LIB_DSA, reason);
@@ -230,7 +242,6 @@ static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in,
         ERR_raise(ERR_LIB_DSA, DSA_R_MISSING_PRIVATE_KEY);
         return 0;
     }
-
     k = BN_new();
     l = BN_new();
     if (k == NULL || l == NULL)
@@ -246,7 +257,8 @@ static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in,
     /* Preallocate space */
     q_bits = BN_num_bits(dsa->params.q);
     q_words = bn_get_top(dsa->params.q);
-    if (!bn_wexpand(k, q_words + 2)
+    if (q_bits < MIN_DSA_SIGN_QBITS
+        || !bn_wexpand(k, q_words + 2)
         || !bn_wexpand(l, q_words + 2))
         goto err;
 
diff --git a/crypto/err/openssl.txt b/crypto/err/openssl.txt
index 3c44e32f38..83d67ab1ce 100644
--- a/crypto/err/openssl.txt
+++ b/crypto/err/openssl.txt
@@ -1,4 +1,4 @@
-# Copyright 1999-2022 The OpenSSL Project Authors. All Rights Reserved.
+# Copyright 1999-2023 The OpenSSL Project Authors. All Rights Reserved.
 #
 # Licensed under the Apache License 2.0 (the "License").  You may not use
 # this file except in compliance with the License.  You can obtain a copy
@@ -545,6 +545,7 @@ DSA_R_PARAMETER_ENCODING_ERROR:105:parameter encoding error
 DSA_R_P_NOT_PRIME:115:p not prime
 DSA_R_Q_NOT_PRIME:113:q not prime
 DSA_R_SEED_LEN_SMALL:110:seed_len is less than the length of q
+DSA_R_TOO_MANY_RETRIES:116:too many retries
 DSO_R_CTRL_FAILED:100:control command failed
 DSO_R_DSO_ALREADY_LOADED:110:dso already loaded
 DSO_R_EMPTY_FILE_STRUCTURE:113:empty file structure