"William H. Geiger III" <whgiii(_at_)invweb(_dot_)net> writes:
In <88118582801112(_at_)cs26(_dot_)cs(_dot_)auckland(_dot_)ac(_dot_)nz>, on
12/04/97
at 10:50 AM, pgut001(_at_)cs(_dot_)auckland(_dot_)ac(_dot_)nz (Peter
Gutmann) said:
DSS/DSA is only specified for key lengths between 512 and 1024, but OpenPGP
should be free to do longer keys, even though the standard doesn't actually
support them.
There's no point in moving to p > 1K bits if q is only 160 bits because
it'll be vulnerable to a small-exponent attack. Since q is governed by
the hash function associated with DSA, you then need to define a new
hash function with a larger output block size, and suddenly things get
very messy. At the moment I don't think it's sensible to use keys > 1K
bits, all it'll do is lead to confusion about the amount of security
offered.
I am not that well versed on DSA but what is involved in increasing p if a
corresponding q can be supplied?
Will a p of 2048 work with a corresponding q of 320?
Here's a table of p vs q (generated by Colin Plumb).
/* Once the DSA p goes above 1024 bits, we need to increase q correspondingly
to provide equivalent security from small-exponent attacks. The following
information for doing this was provided by Colin Plumb.
This is based on a paper by Michael Wiener on | The function defined
the difficulty of the two attacks, which has | below (not part of the
the following table: | original paper)
| produces the following
Table 1: Subgroup Sizes to Match Field Sizes | results:
Size of p Cost of each attack Size of q
(bits) (instructions or (bits)
modular multiplies)
512 9 x 10^17 119
768 6 x 10^21 145
1024 7 x 10^24 165
1280 3 x 10^27 183
1536 7 x 10^29 198
1792 9 x 10^31 212
2048 8 x 10^33 225
2304 5 x 10^35 237
2560 3 x 10^37 249
2816 1 x 10^39 259
3072 3 x 10^40 269
3328 8 x 10^41 279
3584 2 x 10^43 288
3840 4 x 10^44 296
4096 7 x 10^45 305
4352 1 x 10^47 313
4608 2 x 10^48 320
4864 2 x 10^49 328
5120 3 x 10^50 335 */
As you can see, you'd need a hash of >300 bits for keys of up to 4096 bits, so
in theory you could use some double-width variant of SHA for keys > 1K bits.
I remember someone from PGP Inc asking about wide hashes about a year ago on
some mailing list, so it looks like PGP Inc have already considered (and
rejected) something like this in the past.
Peter.