DSA keys larger than 1024 bits

[denis bider <ietf-ssh%denisbider.com@localhost>]

My colleague Wei tried to post the following message, but it didn't get through to the list.

I'm forwarding it here:


----- Original Message -----
From: Wei Dai
To: ietf-ssh%netbsd.org@localhost
Sent: Saturday, October 29, 2005 2:56 PM
Subject: DSA keys larger than 1024 bits

Some SSH2 implementations, including OpenSSH, can apparently
generate and use DSA keys larger than 1024 bits. I'm not sure about
other implementations, but at least with OpenSSH, there are two
major problems with the way this works.

1. This violates FIPS 186-2, the DSS standard, which limits the key
size to 1024.

2. Even though the size of the prime modulus, p, can exceed 1024,
the size of the subgroup order, q, is still limited to 160 bits.
(OpenSSH can not interoperate with other implementations that use
larger subgroups and complains about invalid signature size.) But
this implies 80 bit security no matter how big the key is, because
there is an attack whose running time depends exponentially on the
size of sqrt(q), but only polynomially on the size of p. [1] To
increase security, the sizes of p and q must both be increased. In
Crypto++, by default the size of q is chosen as 2*
DiscreteLogWorkFactor(modulusSize), where DiscreteLogWorkFactor is:

unsigned int DiscreteLogWorkFactor(unsigned int n)
{
  // extrapolated from the table in Odlyzko's "The Future of Integer
  // Factorization"
  // updated to reflect the factoring of RSA-130
  // assuming discrete log takes about the same time as factoring
  if (n<5) return 0;
  else return (unsigned int)(2.4 * pow((double)n, 1.0/3.0) *
    pow(log(double(n)), 2.0/3.0) - 5);
}

This translates to q sizes of 226 and 304 for p sizes of 2048 and
4096 respectively.

To fix these problems, I suggest the following:

1. Stop using "ssh-dss" with non-standard DSA key sizes.

2. Create a new algorithm name for non-standard DSA key sizes.

3. For the new algorithm, allow arbitrary key sizes as long as p
and q are at least 1024 and 160 bits respectively.

4. When generating new keys, use something like the above
DiscreteLogWorkFactor function to derive the size of q from p.

[1] http://en.wikipedia.org/wiki/Baby-step_giant-step