Re: DSA keys larger than 1024 bits

[nisse%lysator.liu.se@localhost (Niels Möller)]

denis bider <ietf-ssh%denisbider.com@localhost> writes:

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

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

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

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

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.

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

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