Cap the number of iterations in DSA signing

The DSA standard specifies an infinite loop: if either r or s is zero
in the signature calculation, a new random number k shall be generated
and the whole thing is to be redone. The rationale is that, as the
standard puts it, "[i]t is extremely unlikely that r = 0 or s = 0 if
signatures are generated properly."

The problem is... There is no cheap way to know that the DSA domain
parameters we are handed are actually DSA domain parameters, so even
if all our calculations are carefully done to do all the checks needed,
we cannot know if we generate the signatures properly. For this we would
need to do two primality checks as well as various congruences and
divisibility properties. Doing this easily leads to DoS, so nobody does
it.

Unfortunately, it is relatively easy to generate parameters that pass
all sorts of sanity checks and will always compute s = 0 since g
is nilpotent. Thus, as unlikely as it is, if we are in the mathematical
model, in practice it is very possible to ensure that s = 0.

Read David Benjamin's glorious commit message for more information
https://boringssl-review.googlesource.com/c/boringssl/+/57228

Thanks to Guido Vranken for reporting this issue, also thanks to
Hanno Boeck who apparently found and reported similar problems earlier.

ok beck jsing

1 files changed, 16 insertions, 1 deletions

diff --git a/src/lib/libcrypto/dsa/dsa_ossl.c b/src/lib/libcrypto/dsa/dsa_ossl.c
index d32168a48e..ece1026fc9 100644
--- a/src/lib/libcrypto/dsa/dsa_ossl.c
+++ b/src/lib/libcrypto/dsa/dsa_ossl.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: dsa_ossl.c,v 1.49 2023/03/04 21:06:17 tb Exp $ */
+/* $OpenBSD: dsa_ossl.c,v 1.50 2023/03/04 21:30:23 tb Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -92,6 +92,16 @@ DSA_OpenSSL(void)
         return &openssl_dsa_meth;
 }
 
+/*
+ * Since DSA parameters are entirely arbitrary and checking them to be
+ * consistent is very expensive, we cannot do so on every sign operation.
+ * Instead, cap the number of retries so we do not loop indefinitely if
+ * the generator of the multiplicative group happens to be nilpotent.
+ * The probability of needing a retry with valid parameters is negligible,
+ * so trying 32 times is amply enough.
+ */
+#define DSA_MAX_SIGN_ITERATIONS         32
+
 static DSA_SIG *
 dsa_do_sign(const unsigned char *dgst, int dlen, DSA *dsa)
 {
@@ -100,6 +110,7 @@ dsa_do_sign(const unsigned char *dgst, int dlen, DSA *dsa)
         BN_CTX *ctx = NULL;
         int reason = ERR_R_BN_LIB;
         DSA_SIG *ret = NULL;
+        int attempts = 0;
         int noredo = 0;
 
         if (!dsa_check_key(dsa)) {
@@ -187,6 +198,10 @@ dsa_do_sign(const unsigned char *dgst, int dlen, DSA *dsa)
                         reason = DSA_R_NEED_NEW_SETUP_VALUES;
                         goto err;
                 }
+                if (++attempts > DSA_MAX_SIGN_ITERATIONS) {
+                        reason = DSA_R_INVALID_PARAMETERS;
+                        goto err;
+                }
                 goto redo;
         }