Cap the number of iterations in DSA signing
authortb <tb@openbsd.org>
Sat, 4 Mar 2023 21:30:23 +0000 (21:30 +0000)
committertb <tb@openbsd.org>
Sat, 4 Mar 2023 21:30:23 +0000 (21:30 +0000)
commit0d37be089c4168552b05ab0ee6dc55db22e44b9f
treeb0f521ef8209442f7306793c9455ebed37432210
parent5f7fe693f69a769e97d438ec6fd2d74ee8350f79
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