From 0d37be089c4168552b05ab0ee6dc55db22e44b9f Mon Sep 17 00:00:00 2001 From: tb Date: Sat, 4 Mar 2023 21:30:23 +0000 Subject: [PATCH] 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 --- lib/libcrypto/dsa/dsa_ossl.c | 17 ++++++++++++++++- 1 file changed, 16 insertions(+), 1 deletion(-) diff --git a/lib/libcrypto/dsa/dsa_ossl.c b/lib/libcrypto/dsa/dsa_ossl.c index d32168a48ea..ece1026fc9a 100644 --- a/lib/libcrypto/dsa/dsa_ossl.c +++ b/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; } -- 2.20.1