Subject: Re: Bigger DSA keys

From: [email-masked] ("Hal Finney")
Date: Sat, 17 Sep 2005 17:13:03 -0700 (PDT)

Ian Grigg writes:
> (assuming we do it,) I would suggest we ditch the 2048/224
> and just implement the 3072/256.
>
> (We could add the other one as a MAY ... but I can't see
> the point of it.  Sure NIST may split hairs on it, but
> let's save ourselves the doco and the discussion and
> just do the better one.)
> ...
> I don't think it is that easy.  SHAs are under a cloud,
> and until we get some more definitive info on the new
> hardware factoring, even the numbers suggested above
> won't satisfy all the extremists.  Consider that the
> extreme community considers 4096 to be a minimum, and
> all the news is supporting them at the moment;  also,
> NIST's hash work has been controversial (SHA0, SHA2
> being just an "extension" ...), I'd like to see what
> the crypto community comes up with in hash research as
> that feeds into DSS.

I'm not sure why there is not a plan for larger key sizes.  A possible
clue is in this NIST document, "Recommendation for Key Management",
http://csrc.nist.gov/publications/nistpubs/800-57/SP800-57-Part1.pdf .
Table 2 on page 63 shows the following correspondences between hash size
and modulus size: 160/1024; 224/2048; 256/3072; 384/7680; and 512/15360.

This fits what we know, with SHA-1 and a 1024 bit modulus as the
traditional DSS; SHA-224 and a 2048 bit modulus, and SHA-256 and a 3072
bit modulus in this new DSS that I have been told about.  It implies that
the natural next size would be SHA-384 and a 7680 bit modulus.  But that
modulus is too big for most people's convenience.

You might say, just use SHA-384 and a 4096 bit modulus, but that is not
such a nice fit.  The hash is a lot stronger than the modulus and so it
is not well balanced.  Perhaps such esthetic considerations motivated
NIST's decision.

Hal Finney

---

From: [email-masked] (Daniel A. Nagy)
Date: Sun, 18 Sep 2005 14:34:39 +0200

It's important to keep in mind that DSS-style signatures are twice the hash
size. This is one of their nicest features; they do not grow with the
modulus. A signature of a 3072/256 key will be 512 bits (plus overhead).

As for generating long modulae, it's not that big a problem, altough it has
to be noted that generating a modulus for DSA takes more than just
generating a prime that big; DSA moduli p are such that p-1 is divisible by
some large (hash-sized) q. The generation of such moduli takes substantially
longer than generating primes. For 3072/256 on a 500MHz intel, it would take
approx. three minutes, provided that the random stream is available without
waiting.

On the other hand, the overwhelming majority of DSS implementations use
pre-calculated moduli, as there are no security hazards associated with
using a common modulus for DSS. When keys need to be generated frequently,
a pre-calculated modulus is the way to go. If one just needs to generate a
personal signature key for the next five years, one can wait three minutes,
in case they want to show off a self-generated modulus.

-- 
Daniel

---

From: Ben Laurie <[email-masked]>
Date: Tue, 20 Sep 2005 18:30:53 +0100

> in case they want to show off a self-generated modulus.

Good point.

-- 
http://www.apache-ssl.org/ben.html       http://www.thebunker.net/

"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff