Re: SSH non-compliance with FIPS 186

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

Peter Gutmann <pgut001%cs.auckland.ac.nz@localhost> writes:

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

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

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

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