Subject: DSA keys larger than 1024 bits

From: denis bider <[email-masked]>
Date: Tue, 1 Nov 2005 18:54:57 +0100

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: [email-masked]
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

---

From: [email-masked] (Niels Möller)
Date: 01 Nov 2005 20:09:09 +0100

> major problems with the way this works.

I recently got reports on interoperation problems between lsh and an
openssh server using 4096 bit or so dsa key. lsh currently allows keys
that are a bit larger than specified by the standard (the limit is
around 2048 bits or so), but I don't think it's a good idea to use
non-standard DSA key sizes (and then, I think all the key sizes but
1024 bits have been deprecated because they're too small today).

> the size of the subgroup order, q, is still limited to 160 bits.

And it's not clear how to generalize the specification of dsa to use a
larger q; if you use a p larger than the hash size, you're using an
algorithm that's quite different from dsa. May be it would make sense
to use 256 or 512 bits for q, together with sha256 or sha512. But the
point is that there's no single obvious way to generalize dsa to
larger groups, and it's no longer the standardized "dsa" algorithm.

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

I'm not sure if step 2 really is important. I meen, if a 1024 bit key
is too small, why not use rsa instead? That's simple, standardized,
and fairly well understood. Sure, ssh-dss is REQUIRED while ssh-rsa is
only RECOMMENDED, but as far as I'm aware, using non-standard dsa key
sizes is not supported at all according to the ssh spec and FIPS-186-2. So
just sticking to rsa keys seems like a better choice, both for
practical interoperability, and formal standards compliance.

I suspect that most ssh users that have generated a 4096 bit dsa key
are unaware that the security is tied to the 160 bit subgroup, and
that most would be better served by using a large rsa key instead. By
supporting huge dsa keys, one confuses the users.

If you want to spend time and energy on developing a new signature
algorithm for use in ssh, instead of constructing a parametrized
variant of dsa, perhaps it would make more sense to investigate
elliptic curve techniques. I'm not very familiar with that area, since
it appears to be a patent marsh, but perhaps there's some good well
studied signature scheme in there that's not encumbered by patents?
(The only obvious advantage of dsa over rsa seems to be the shorter
signatures, hence my association to eliptic curves).

Regards,
/Niels

---

From: [email-masked] (Peter Gutmann)
Date: Wed, 02 Nov 2005 17:06:14 +1300

>supporting huge dsa keys, one confuses the users.

I know that at least some users are aware that they're not getting any
extra security, but are using 4Kbit keys anyway for warm fuzzies (hey,
don't look at me, they probably wear tinfoil hats too :-).  The real
fault though is with the software and/or the documentation, it shouldn't
let you generate illogical key sizes, or should warn against doing so.

Peter.