Subject: Re: SSH non-compliance with FIPS 186

From: [email-masked] (Niels Möller)
Date: Mon, 21 Sep 2009 14:39:14 +0200

[email-masked] (Peter Gutmann) writes:

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

Now I've looked (fairly quickly) through FIPS-186-3
(http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf). It
specifies four variants for different key sizes. L is the bitsize of
p, and N is the bitsize of q and also the digest size (in bits) of the
underlying hash function.

L = 1024, N = 160
L = 2048, N = 224
L = 2048, N = 256
L = 3072, N = 256

As far as I understand, intermediate keysizes are not allowed at all
(in contrast to the original dsa, which allowed keysizes 512, 576,
640,..., 1024 with 64 bit increments.

The hash function to use is *not* specified explicitly, it is only
stated that it should be an "approved" hash function.

For N = 160, one ought to use sha1 (as this ought to be intended to
be backwards compatible).

For N = 224, one might use either SHA-224 or truncated SHA-256 (the
way SHA-224 is constructed, the only difference between these two
alternatives is the initial state), and for N = 256, one ought to use
SHA-256.

Before implementing larger DSA, I'd like to see a specification that
also specifies explicitly the hash function to use, and which provides
some test vectors. Where should I look?

Implementation-wise, I think I'd prefer to first parametrize dsa with
respect to the hash function, e.g., define "dsa-sha256" to use SHA-256,
which implies a value for N above, and then be somewhat more liberal
when it comes to allowed key size L.

Regards,
/Niels

---

From: [email-masked] (Niels Möller)
Date: Mon, 21 Sep 2009 19:22:55 +0200

James Blaisdell <[email-masked]> writes:

> I started looking into this as well.  FIPS 140-2 refers to this as
> "DSA2,"

Where, more precisely? FIPS 140-2 "Security Requirements for
Cryptographic Modules" doesn't seem to mention dsa at all. Is it in one
of the annexes?

> I believe a new draft/RFC is required for ssh-dsa2-*
> (ssh-dsa2-160/224/256/385/512) algorithms.

For me, the first step is to find a *complete* and authoritative
specification for these dsa variants, preferably including test
vectors. I'd like to have the general signature algorithm done
correctly, before worrying too much about how to use it in ssh.

For ssh, initially, I could implement it under a name like
[email-masked], next we'd have to agree on the details, and
then arrange to allocate an official name and document it as an
informational RFC, or something like that.

Are there any other Internet standards that use these updated DSA
variants?

/Niels

---

From: James Blaisdell <[email-masked]>
Date: Mon, 21 Sep 2009 09:45:18 -0700

Hi Niels,

I started looking into this as well.  FIPS 140-2 refers to this as "DSA2," same underlying DSA algorithm operations (key generation, sign, verify, etc) can use a stronger hash algorithm than SHA1.  As a result SSH is incompatible with these new "DSA2" algorithms.  I believe a new draft/RFC is required for ssh-dsa2-* (ssh-dsa2-160/224/256/385/512) algorithms.  

Thank you,

James

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Niels Möller
Sent: Monday, September 21, 2009 5:39 AM
To: Peter Gutmann
Cc: [email-masked]
Subject: Re: SSH non-compliance with FIPS 186

L = 1024, N = 160
L = 2048, N = 224
L = 2048, N = 256
L = 3072, N = 256

Regards,
/Niels

---

From: James Blaisdell <[email-masked]>
Date: Mon, 21 Sep 2009 10:31:24 -0700

Hi Niels,

Please see NIST 186-3 (June 2009):

http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf

After cursory review, it appears trivial to convert DSA1 --> DSA2, but DSA2 is incompatible with ssh-dsa.  

Thank you,

James

-----Original Message-----
From: Niels Möller [mailto:[email-masked]] 
Sent: Monday, September 21, 2009 10:23 AM
To: James Blaisdell
Cc: Peter Gutmann; [email-masked]
Subject: Re: SSH non-compliance with FIPS 186

/Niels

---

From: James Blaisdell <[email-masked]>
Date: Mon, 21 Sep 2009 11:07:11 -0700

Hi Niels,

Sorry for my short reply.  I stumbled across DSA2 while starting new round of FIPS 140-2 testing.  It's not a requirement for FIPS, but simply yet another algorithm which is FIPS-able.  The FIPS documentation refers to it as DSA2, which sounds good to me, although web searches revealed almost nothing, but the documentation did refer to NIST 186-3.  

Your idea on unique name space is great, and I wish this was practiced more especially for drafts.  I might be up for implementing this in a couple of weeks, if you want to do any interop testing.  

Thanks,

James

-----Original Message-----
From: Niels Möller [mailto:[email-masked]] 
Sent: Monday, September 21, 2009 10:23 AM
To: James Blaisdell
Cc: Peter Gutmann; [email-masked]
Subject: Re: SSH non-compliance with FIPS 186

/Niels

---

From: Peter Gutmann <[email-masked]>
Date: Tue, 22 Sep 2009 18:12:37 +1200

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

>Before implementing larger DSA, I'd like to see a specification that also
>specifies explicitly the hash function to use, and which provides some test
>vectors. Where should I look?

The only test vectors that I know of were generated by one of the OpenPGP guys
a few years ago (one of the, um, "features" of DSA2 is that since it rarely
gets used there's not much scope for interop problems :-), you can get them
from http://www.jabberwocky.com/openpgp/dsa2.tar.gz.

Peter.

---

From: Peter Gutmann <[email-masked]>
Date: Tue, 22 Sep 2009 18:18:23 +1200

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

>Are there any other Internet standards that use these updated DSA variants?

OpenPGP sort of does, in the sense that their use is covered in the RFC,
however the OpenPGP RFC has historically adopted a whole range of bleeding-
edge algorithms that it turned out no-one was really interested in, which is
why I used the phrase "covered in the RFC" rather than "used".  For example
GPG will verify DSA2 sigs but won't generate them unless you explicitly feed
it a special command-line option telling it to use DSA2.  No idea what other
implementations do.

With a bit more hindsight now that some time has passed, it may be easier to
just deprecate DSA rather than trying to specify usage rules for something
that no-one seems to be using.

Peter.

---

From: [email-masked] (Niels Möller)
Date: Tue, 22 Sep 2009 10:03:15 +0200

> that no-one seems to be using.

I'd recommend anybody to use RSA rather than DSA, since it's
obvious that you can use as large keys as you like, and you avoid
the hassle with the security of signature operation depending on the
randomness generator.[1]

Nevertheless, I see a couple of reasons to have larger DSA in the ssh
protocol.

1. Not that I expect RSA to be broken anytime soon, but I think it's
   good practice to have two different and well-respected algorithms
   that are supported by most implementations.

2. In practice, people seem to be using large out-of spec DSA keys
   with ssh-dss. Probably not realizing that the small fixed size of
   q also limits the security.

3. The security for the largest key sizes in the original (as
   currently supported in ssh) dsa algorithm, 1024/160, seem to be on
   the borderline of being too weak today. Hence, if we want to
   continue to support DSA, a spec that uses larger keys in a proper
   way seems like a good thing.

As a practical matter, if we want to have larger dsa, I'd suggest
adopting "dsa-sha256", specified to a use 256-bit q, SHA-256, and with
more or less arbitrary size of p (but recommended in the range 2048 to
3072).

> from http://www.jabberwocky.com/openpgp/dsa2.tar.gz.

Thanks. I'm surprised and disappointed if NIST really haven't
published any official test vectors. I thought everybody agreed that
that's an essential part of any specification for a cryptographic
algorithm.

[1] I think putty uses a clever trick to avoid that dependency, by
    generating the "random" number involved in DSA signing using
    hashing of the secret key and the message being signed. Probably
    difficult to prove any security, but it boils down to a problem
    somewhat like "give the attacker both H(x) and g^x mod p, and let
    the attacker try to find x". I'd expect that knowledge of H(x)
    won't be of much help in the discrete logarithm problem and
    vice versa, but that's just my gut feeling.

Regards,
/Niels

---

From: Peter Gutmann <[email-masked]>
Date: Tue, 22 Sep 2009 20:50:36 +1200

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

>people seem to be using large out-of spec DSA keys with ssh-dss.

Ahh, good point.  The precise reason why GPG doesn't support DSA2 by default
is out of concern over users who want to make a fashion statement with
stupidly large keys that nothing on the receiving end will be able to verify,
but in the case of SSH since it's negotiated interactively this won't be such
a problem since the other side can simply choose to decline that option.

>As a practical matter, if we want to have larger dsa, I'd suggest adopting
>"dsa-sha256", specified to a use 256-bit q, SHA-256, and with more or less
>arbitrary size of p (but recommended in the range 2048 to 3072).

Yup, I'd agree with choosing that as the universal-to-support standard, the
larger hashes get a bit messy on 32-bit architectures, the combination of
SHA-256 with 2K-3K keys is a nice balance.

>I'm surprised and disappointed if NIST really haven't published any official
>test vectors. I thought everybody agreed that that's an essential part of any
>specification for a cryptographic algorithm.

They tend to lag the drafts by a long, long time, so you have to scrape them
together wherever you can find them.  Usually you end up with pulling
something out of whatever the latest version of the CAVS software is on the
assumption that it must be OK.  Testing against a consensual hallucination
seems to be a somewhat unsound practice though.

>I think putty uses a clever trick to avoid that dependency, by generating the
>"random" number involved in DSA signing using hashing of the secret key and
>the message being signed.

AFAIK this was first done by the commercial PGP some years ago.  It works a
bit better for that because what's being hashed is also encrypted, so an
attacker won't have access to the preimage.

Peter.