Subject: Bigger DSA keys

From: [email-masked] ("Hal Finney")
Date: Fri, 16 Sep 2005 15:41:13 -0700 (PDT)

I have it on good authority that NIST will be announcing larger size
DSS keys soon.  According to my source, the date will be by the end
of October.

Currently, DSS keys have two problems.  First, they can be no bigger
than 1024 bits.  Recent results show that keys of this size can no
longer be considered safe from large scale attackers.  See for example
http://lists.virus.org/cryptography-0509/msg00080.html (although this
is for RSA keys, DSS keys of a similar size are not thought to be too
much more difficult).  Second, DSS keys are locked into using SHA-1,
for which attacks have been published.

The new DSS keys will, according to what I have heard, be for two sizes:
2048 and 3072 bits, and will use SHA-224 and SHA-256 respectively.
(SHA-224 is not presently an OpenPGP algorithm; it is basically a
truncated version of SHA-256 with a different internal initial value).
This will allow for larger keys and use a different hash than SHA-1.

If this report is correct, it would be good to see these new key sizes
in RFC2440bis.  Otherwise the DSS support in the spec will be essentially
"dead on arrival".  Rather than publishing a spec with a major class
of keys that has no future utility, I think it makes sense to wait six
weeks and see if we can incorporate the new information, making the
spec much more robust and long-lasting.

For those who say we have waited too long already, I will just note that
the weeks and months drift by without much reason for delay but without
much progress either.  Now that there is a good reason to hold off a
bit more, I would hate to see us suddenly rush to close the door.

One issue is how best to incorporate these new key sizes.  As I see it,
there are three alternatives.

1. Just use the new sizes with the existing DSA keys.  Instead of only
512-1024 bits, let DSA keys also be 2048 and 3072 bits, and enforce the
proper hash algorithms in software.

2. Use a new algorithm ID for the new DSA keys, which would be only
for 2048 and 3072 bits.  The old algorithm ID would continue to be
used for old DSA keys.

3. Use a new key packet version number for the new DSA keys, V5.
Perhaps V5 keys could use a SHA-256 based fingerprint.  This would
represent a clean break from the old way.

The first alternative would involve the least change to the spec, just
changes to the information about how to sign and verify with DSA keys.
The second alternative would require adding much the same material
but with the handling of the new algorithm ID called out separately.
It would probably duplicate some of the information on old-style DSA keys.

The third alternative is the most ambitious and is not feasible for
RFC2440bis IMO.  We could still go to a V5 key packet at some point in
the future anyway, and perhaps do other improvements at that time.

Between the first two, I would propose to decide largely on the basis of
backwards compatibility.  Obviously signatures made with new-style DSA
keys will not be verifiable in old code.  The question is how gracefully
existing implementations will fail when presented with such keys and
signatures, in either the first or second form.  Testing on current
implementations could provide guidance as to which way of making the
change will cause the least trouble.

Hal Finney

---

From: Ian G <[email-masked]>
Date: Sun, 18 Sep 2005 00:46:17 +0100

> This will allow for larger keys and use a different hash than SHA-1.

(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.)

> spec much more robust and long-lasting.

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.

Which rambling means to say that even after the October
date, I suspect it will be all too easy to say "let's
wait a bit more..."

> for 2048 and 3072 bits.  The old algorithm ID would continue to be

I think I'd lean towards this one.  This would allow
us to deprecate DSA-old just as soon as we can.

> represent a clean break from the old way.

I'd go against this (for the same reason you
outline below).

> It would probably duplicate some of the information on old-style DSA keys.

Ah, good point.  But unless by some miracle all the
implementations can handle #1 without blowing up,
then I can't see how we'd countenance an incompatible
change?

> the future anyway, and perhaps do other improvements at that time.

Right.

> change will cause the least trouble.

Certainly interesting times for DSS fans.  I use it
in a lot of my stuff and have pretty much made up my
mind to move to RSA when and as I can.  Mostly this
is because NIST have moved too little, too late on
this one, and the numbers above are already looking
like we'll be into a change again in about 2-3 years
when the new Hash research settles into a new generation
of algorithms.

iang

---

From: Ben Laurie <[email-masked]>
Date: Sun, 18 Sep 2005 12:27:15 +0100

> let's save ourselves the doco and the discussion and

How about because generating 2048 bit primes already takes long enough, 
and 3072 takes ages?

-- 
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

---

From: Ian G <[email-masked]>
Date: Sun, 18 Sep 2005 14:52:45 +0100

> How about because generating 2048 bit primes already takes long enough, 

Numbers?

iang

---

From: Ben Laurie <[email-masked]>
Date: Sun, 18 Sep 2005 13:10:30 +0100

Ian G wrote:
>> How about because generating 2048 bit primes already takes long 
>> enough, and 3072 takes ages?
> 
> 
> Numbers?

I was going to provide them, but accurate numbers for DSA is difficult, 
because it requires modifying the core code in OpenSSL (or some other 
DSA generator), and I couldn't be bothered.

One can get a feel for it with:

time openssl gendh <number of bits>

which takes a long time. Long enough that I didn't wait for it to finish 
before hitting send.

---

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

> This will allow for larger keys and use a different hash than SHA-1.

For this reason, I'd agree with Ian and just ignore the 2048/224 key
specification. Too much trouble for no gain.

> proper hash algorithms in software.

I like this solution. If old implementations do not do very silly things
when encountering such signatures (e.g. claiming them to be bad signatures
as opposed to unverifiable), it is the cleanest way to go about it.

> for 2048 and 3072 bits.  The old algorithm ID would continue to be

This approach would eat up the algorithm identifier space and provide very
little advantage. It is reasonable to expect new DSS key specifications
every decade, if NIST continues its current practices.

> represent a clean break from the old way.

Let's wait with that. There are several problems with the v4 key formats and
using SHA-256 for fingerprinting is not necessarily a good idea, given that
its design is quickly becoming obsolete. 

> change will cause the least trouble.

That's a very reasonable suggestion.

-- 
Daniel

---

From: Werner Koch <[email-masked]>
Date: Mon, 19 Sep 2005 10:32:25 +0200

> Numbers?

A quick test shows about 4 seconds for 2048 bit and 21 seconds for
3072.  However this includes the time required to gather enough
randomness; further tests took much longer very likely due to a lack
of entropy in the machine.  Most applications don't need to generate
keys very ofthen, thus this should not be a problem.

OTOH, verification is used very often.  Here are number from
Libgcrypt:

DSA 100 times    sign  verify
-----------------------------
DSA 1024/160    910ms   430ms
DSA 2048/224   1560ms  1890ms
DSA 3072/256   3610ms  4380ms

(The numbers for sign are not very reliable because it employs the
RNG and I could not adjust for it)

3072 takes more more than double the time of 2048 which is not too
bad.  Compared to 1024 this is a real slowdown and would make key
signature verification a very time consuming operation.  On slow
machines (embedded devices, older hardware) this would be very
annoying.

Shalom-Salam,

   Werner

---

From: David Shaw <[email-masked]>
Date: Mon, 19 Sep 2005 09:01:37 -0400

> the future anyway, and perhaps do other improvements at that time.

I am a big fan of V5 keys (see
http://www.imc.org/ietf-openpgp/mail-archive/msg09274.html), and I
love the clean break, but I feel that if the new DSA was tied to V5
then discussions and design for a good V5 key format would delay
availability of the new DSA in the field for an excessively long
amount of time.  People have been asking for a better DSA for a long
time now, so it seems a shame to delay it further.  I'm all for
planning V5 of course, just not tied to the new DSA.

> change will cause the least trouble.

Presuming that the size of q will change from 160 to 224 or 256 in the
new key, importing a DSA key to GnuPG with the current algorithm
number and a q that is not 160 bits or importing a new-style DSA key
with a new algorithm number fails more or less gracefully in either
case.

So at least from the graceful failure perspective in GnuPG, it doesn't
really matter much which way we go.  I prefer the first option (using
the current algorithm number) since it seems cleanest in both code and
standard.

David

---

From: Werner Koch <[email-masked]>
Date: Mon, 19 Sep 2005 16:45:31 +0200

> the current algorithm number) since it seems cleanest in both code and

However this does also means that another hash algorithm needs to be a
MUST algorithm - unless we limit the MUST support for DSA to 1024 bits
keys.

The need for another algorithm makes a big difference for emdedded
applications.  Ofen the threat model does not require
high budget spook proof algorithms.

Shalom-Salam,

   Werner

---

From: David Shaw <[email-masked]>
Date: Mon, 19 Sep 2005 11:08:07 -0400

> MUST algorithm - unless we limit the MUST support for DSA to 1024 bits

Yes.  I'm not against limiting the MUST support to 1024/160 DSA.

David

---

From: [email-masked]
Date: Mon, 19 Sep 2005 19:34:20 +0200

> high budget spook proof algorithms.

I fully agree with that. I would limit the MUST support to plain old SHA1
and 1024bit DSA for the time being.

-- 
Daniel

---

From: [email-masked]
Date: Mon, 19 Sep 2005 19:34:20 +0200

-- 
Daniel

---

From: Jon Callas <[email-masked]>
Date: Mon, 19 Sep 2005 10:59:54 -0700

> DSS keys soon.  According to my source, the date will be by the end

We've been waiting for this for years.

I think it's important enough to warrant a change in last call for.

     Jon

---

From: Ian G <[email-masked]>
Date: Tue, 20 Sep 2005 15:30:04 +0100

> DSA 100 times    sign  verify

Ah, ok, so this last point about slow / small hardware
platforms makes sense.  So we might be tempted to suggest
that implementations SHOULD verify any of the three lengths,
and let them choose which length to deliver for signing
beyond the MUST of 1024/160.

(Which is after all a minor side discussion in Hal's
thread of whether to wait or not.)

iang

---

From: Bill Frantz <[email-masked]>
Date: Wed, 21 Sep 2005 09:36:37 -0700

>time openssl gendh <number of bits>

I'm not sure, based on these numbers, that this benchmark procedure is reproducible enough to give valid data with only one sample per prime size.  However, here is what I got.

On a Mac G4/450MHz running OS 10.3.9:

[G4:~] billfran% time openssl gendh 512
  ...
9.850u 0.170s 0:18.39 54.4%     0+0k 3+7io 0pf+0w

[G4:~] billfran% time openssl gendh 1024
  ...
11.920u 0.070s 0:13.19 90.9%    0+0k 0+3io 0pf+0w

[G4:~] billfran% time openssl gendh 2048
  ...
5909.970u 24.060s 1:45:08.60 94.0%      0+0k 0+4io 0pf+0w

[G4:~] billfran% time openssl gendh 3072
  ...
21017.450u 166.540s 6:42:28.96 87.7%    0+0k 0+3io 0pf+0w

Cheers - Bill

-----------------------------------------------------------------------
Bill Frantz        | gets() remains as a monument | Periwinkle 
(408)356-8506      | to C's continuing support of | 16345 Englewood Ave
www.pwpconsult.com | buffer overruns.             | Los Gatos, CA 95032