Re: SSH non-compliance with FIPS 186

[pgut001%cs.auckland.ac.nz@localhost (Peter Gutmann)]

nisse%lysator.liu.se@localhost (Niels =?iso-8859-1?Q?M=F6ller?=) writes:
>pgut001%cs.auckland.ac.nz@localhost (Peter Gutmann) writes:
>> Someone's just pointed out a problem with SSH's use of DSA keys: The RFC
>> claims that "signing and verifying using this key format is done according to
>> the Digital Signature Standard [FIPS-186-2]", but either the spec or many
>> (all?) implementations aren't actually compliant with FIPS 186.  RFC 4253
>> hardcodes r and s as 160 bits, but this is only valid for FIPS 186-2 with a
>> 1024-bit key size.
>
>I haven't followed the updates of DSA, so my take has been that DSA with key
>size larger than 1024 is non-standard, and of questionable value since the
>size of the q subgroup is the same.

FIPS 186 allows key sizes up to either 3072 or 4096 bits.

[Pause]

It's 3072 bits, with a corresponding subgroup size of 256 bits (I guess they
were nervous about SHA-512 and so stopped there :-).

>> Use of a key size > 1024 bits isn't allowed in FIPS 186-2. FIPS
>> 186-3 does allow keys > 1024 bits but requires a corresponding
>> increase in the size of q because increasing p while keeping q fixed
>> at 160 bits provides no increase in security.
>
>Could you give a brief description? As far as I remember, the 160 bits in DSA
>is intimately tied to the digest size of sha1.

It's a triplet { p-size, q-size, hash-size } where hash-size == q-size.  If
you increase p-size without a corresponding increase in q-size/hash-size you
get no effective increase in security.

I've always seen the details on this ascribed to an unnamed paper by Michael
Wiener, but the closest I can find is "On Diffie-Hellman Key Agreement with
Short Exponents", which Citeseer has here:
http://citeseer.ist.psu.edu/734853.html.  It doesn't provide details on
calculation of q for p > 1024 bits, although it does explain the reason for
the magic value of 160 bits.

(This is actually rather interesting, there's no original source that I can
identify for the table of p vs. q values.  As far as I can see all the online
versions were taken from the table I used in my code, and I got that from
Colin Plumb.  Hmm...).

>Do the updated DSA specify other hash functions (sha-256 or sha-512)?

Yes, you have to use a hash function of size >= the subgroup size.  So SHA-256
covers all the options up to 3072-bit keys.

>> I'd like to propose a
>> correction to the spec with a new DSA sig format:
>>
>>   string    "ssh-dss-fips"    // Or whatever
>>   mpint     r
>>   mpint     s
>>
>> to allow use with with keys generated according to FIPS 186.  Comments?
>
>It ought to get a new signature algorithm id as well.

Having looked at it again, I'd propose "ssh-dsa".  "ssh-dss" has always bugged
me because the NIST/FIPS digital signature standard (DSS) covers a whole range
of algorithms and not just DSA.  So RSA is "ssh-dss" just as much as DSA is.
"ssh-dsa" makes it explicit what the algorithm being used really is, and
updates it to be compliant with current versions of DSA.

If anyone wants to make the change and do some interop testing, let me know.
Shouldn't be too hard, just advertise "ssh-dsa" in the handshake and add
another case statement for the sig format.

Peter.