Re: SSH non-compliance with FIPS 186

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

>From an old discussion on the FIPS 186-3 extensions of DSA...

pgut001%cs.auckland.ac.nz@localhost (Peter Gutmann) writes:

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

After looking things up (using the somewhat old Handbook of Applied
Cryptography as my main reference), it seems that the best known
algorithm for discrete logarithms in the small "q-size" subgroup is Pollard
\rho or baby-step giant-step, both of complexy O(sqrt(group size)),
so that would be roughly 2^80 steps for dsa-sha1 and 2^128 steps for
dsa-sha256.

While for the large group, the best method is index calculus / number
field sieve, which is of roughly the same complexity as factoring
numbers of the same size.

So the proper ratio between p-size and q-size is related to the relative
efficiency of the number field sieve and Pollard \rho.

To me, it seems prudent to discourage use of dsa-sha1, for 3 reasons:

  * General progress on attacking sha1.

  * 2^80 complexity of discrete logarithm in the small group having
    uncomfortably small security margin.
  
  * Likewise, if complexity of discrete logarithms in the large group is
    comparable to factoring 1024 bit numbers, that's also not a very
    large margin to what's practical (and 1024 bit RSA also is not
    recommended for keys generated today, is it?)

So I'd recommend to instead use rsa or dsa-256 with key size of at least
1536 bits. Is this a resonable interpretation of the current state of
the art?

To me, this is a strong motivation for getting some other good signature
algorithm in besides rsa, to be able to move quickly if some serios
problem is discovered with rsa (in terms of either implementation bugs
or something more fundamental).

Should we also look into rsa using some other hash function than sha1?

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

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

I'm about to implement this. Does anybody have a server that already
implements it, and a spec for the details? Otherwise, here's what I'm
considering implementing:

: Signature algorithm: DSA, as defined in FIPS 186-3, using SHA256 for
: the hash function.
: 
: Algorithm name: "ssh-dsa-sha256%lysator.liu.se@localhost" (suggested name
: "ssh-dsa-sha256" if/when registered with iana). Rational: "ssh-"
: prefix because we use ssh-specific encodings of keys and signatures.
: dsa since that's the name of the algorithm, and then "-sha256" since
: the algorithm description is parameterized by the hash function.
: 
: Public-key format:
: 
:       string    "ssh-dsa-sha256"
:       mpint     p
:       mpint     q
:       mpint     g
:       mpint     y
: 
: Except for the name, this syntax is the same as for "ssh-dss". The
: prime q must be exactly 256 bits. The prime p is expected to be of
: size between 1024 and 3072 bits (do we need to specify exactly which
: key sizes should be supported by an implementation advertising this
: signature algorithm? We don't do that for any other signature
: algorithm, as far as I know).
: 
: Signature format:
: 
:       string    "ssh-dsa-sha256"
:       string    dsa_signature_blob
: 
: The dsa_signature blob is a string with a 64-octets payload, where the
: first 32 represent r, unsigned and in network byte order, and the next
: 32 octets represent s. (I'd prefer to depart from this
: "signature_blob" thing and instead use separate mpints for r and s,
: but I think it's more important to stay consistent with the other
: signature algorithms.
: 
: As far as I'm aware, there's no need to add any local-suffix to the
: names included in the key and signature formats.

Any comments or advice appreciated.

Some other comments after implementing the signature algorithm itself:

FIPS 186-3 deprecates the old method of generating keys. The new
recommended method (for some key sizes) uses an algorithm referred to as
"Shawe-Taylor". I have not been able to find that name in the
literature. Instead, I implemented key generation based on Maurer's
algorithm (which seems to be more or less the same thing) for generating
"provable" primes, based on the simplest special case of Pocklington's
theorem.

I have not been able to find any official or agreed upon test vectors
for dsa-sha256. This is a serious problem for testing. If anybody on
this list knows about official test vectors, or can provide some test
signatures from some other implementation, I'd be grateful.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.