Subject: SSH non-compliance with FIPS 186

From: [email-masked] (Peter Gutmann)
Date: Tue, 15 Apr 2008 19:16:03 +1200

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

The real problem is the problematic use of 'dss_signature_blob', which (unlike
all other public-key related formats) uses a fixed size for the fields, with
no provision for specifying length information.  Since it's unlikely that
everyone will change their implementations to limit DSA keys to 1024 bits as
is required for FIPS compliance when q = 160 bits, 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?

Peter.

---

From: [email-masked] (Niels Möller)
Date: Tue, 15 Apr 2008 14:22:53 +0200

[email-masked] (Peter Gutmann) writes:

> 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. I'd recommend
anybody who needs larger keys to use RSA instead.

> 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. Do the updated
DSA specify other hash functions (sha-256 or sha-512)?

> no provision for specifying length information.

I remember I commented on that wart in the early days of the wg, and
that it was motivated by compatibility with some existing crypto
toolkits.

> I'd like to propose a

It ought to get a new signature algorithm id as well.

Regards,
/Niels

---

From: [email-masked] (Peter Gutmann)
Date: Wed, 16 Apr 2008 01:36:18 +1200

[email-masked] (Niels =?iso-8859-1?Q?M=F6ller?=) writes:
>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 :-).

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

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

---

From: Damien Miller <[email-masked]>
Date: Wed, 16 Apr 2008 09:33:24 +1000 (EST)

On Tue, 15 Apr 2008, Peter Gutmann wrote:

> The real problem is the problematic use of 'dss_signature_blob', which
> (unlike all other public-key related formats) uses a fixed size for
> the fields, with no provision for specifying length information. Since
> it's unlikely that everyone will change their implementations to limit
> DSA keys to 1024 bits as is required for FIPS compliance when q = 160
> bits, I'd like to propose a correction to the spec with a new DSA sig
> format:
>

Should this include the hash algorithm too? You could figure it out from
the lengths of r and s, but things could become ambiguous if a future DSA
spec lists new hashes with 160 or 256 bit digest lengths.

-d

---

From: [email-masked] (Peter Gutmann)
Date: Wed, 16 Apr 2008 18:06:09 +1200

Damien Miller <[email-masked]> writes:
>Should this include the hash algorithm too? You could figure it out from the
>lengths of r and s, but things could become ambiguous if a future DSA spec
>lists new hashes with 160 or 256 bit digest lengths.

Good point, the current DSA spec (FIPS 186-3 [0]) already lists hashes other
than SHA-1 so yes, there should be a provision for extra hashes (this also
provides an escape hatch if the ongoing gnawing at SHA-1 is finally
successful).  At the moment there's only SHA-1 and SHA-256 specified, so I'd
suggest:

  "ssh-dsa"        // Implies the traditional "with SHA-1"
  "ssh-dsa-sha256" // Self-explanatory

with possibly a note to implementors to expect "ssh-dsa-sha512" at some point
in the future, and then "ssh-dsa-ahs" in 2011 when the Advanced Hash Standard
appears.  SHA-512 is awkward to implement on non-64-bit processors so I
wouldn't make it mandatory, as indeed FIPS 186 doesn't.

(If people don't object to excessive tinkering, defining an equivalent for RSA
by slipping in a "ssh-rsa-sha256" might also be useful).

Peter.

[0] The NIST web pages are somewhat out of date in places, the current 186-3
    is listed as a draft with comments closing in June 2006, but the
    rumblings I've heard are that either you need to be 186-3 ready now or
    very shortly.

---

From: [email-masked] (Niels Möller)
Date: Wed, 16 Apr 2008 08:32:37 +0200

>>lists new hashes with 160 or 256 bit digest lengths.

Agree, I was just about to suggest that.

And if r and s are coded as mpint, rather than fixed size strings,
then you can't infer the hash size from the sizes of r and s in a 100%
reliable manner, only with a very high probability...

> At the moment there's only SHA-1 and SHA-256 specified, so I'd
> suggest:
>

I'm not sure it makes much sense to introduce this alternative to the
old "ssh-dss" now, even if we all agree the old way is ugly. And if
you really want to introduce it, why not use "ssh-dsa-sha1", to be
explicit?

>   "ssh-dsa-sha256" // Self-explanatory

This makes a lot of sense, and seems like a useful addition.

And about the details of the naming (one of the great unsolved
problems in CS ;-), the "ssh-"-prefix seems somewhat redundant, but
maybe it's good for consistency.

/Niels

---

From: der Mouse <[email-masked]>
Date: Wed, 16 Apr 2008 02:30:45 -0400 (EDT)

> SHA-512 is awkward to implement on non-64-bit processors

Hmm?  I didn't find it so.  It would have been awkward without an
at-least-64-bit integer data type, but, given that, it doesn't much
matter - well, not to awkwardness, at least - how much juggling the
compiler has to do behind the scenes to implement that data type.

/~\ The ASCII				der Mouse
\ / Ribbon Campaign
 X  Against HTML	       [email-masked]
/ \ Email!	     7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B

---

From: [email-masked] (Peter Gutmann)
Date: Thu, 17 Apr 2008 03:21:46 +1200

[email-masked] (Niels =?iso-8859-1?Q?M=F6ller?=) writes:

>I'm not sure it makes much sense to introduce this alternative to the old
>"ssh-dss" now, even if we all agree the old way is ugly.

I can think of two reasons, firstly it's a general-purpose mechanism so the
only extra overhead in supporting "ssh-dsa-sha1" alongside "ssh-dsa-sha256" is
the addition of an extra string to a lookup table (that is, the same code that
does "ssh-dsa-sha256" also does "ssh-dsa-sha1"), and secondly because FIPS 186
doesn't say that the hash size has to match q exactly but merely that you use
the leftmost (sizeof-q) bits of the hash, so that you could use e.g. a 1536-
bit DSA key with SHA-1.  Another way of looking at this is that you need about
2800 bits of key to match 256 bits of security in your hash function, so you
may not want to default to SHA-256 for all keys over 1024 bits.

(Actually I'm not terribly fussed over this, it just seemed that since support
for "ssh-dsa-sha1" comes free with "ssh-dsa-sha256" there didn't seem to be a
strong reason not to do it).

>And if you really want to introduce it, why not use "ssh-dsa-sha1", to be
>explicit?

Sure, sounds good to me.

der Mouse <[email-masked]> writes:

>Hmm?  I didn't find it so.  It would have been awkward without an at-
>least-64-bit integer data type, but, given that, it doesn't much matter -
>well, not to awkwardness, at least - how much juggling the compiler has to do

Sorry, I meant "systems where the compiler can't fake 64-bit support".  There
are still quite a number of non-mainstream and embedded systems where the
largest supported data type is 32 bits, and trying to build this yourself
using toothpicks and rubber bands isn't much fun.  It also becomes quite a
maintenance hassle because you end up having to support two lots of code, one
of which mostly only gets built on wierd platforms with limited debugging
support.

Peter.