Comments on DH-GEX draft

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

I've been meaning to send these in for awhile, seeing the latest draft (which
adds the changed-format request message) finally motivated me to type up the
comments I had.

There are two main problem areas, the first is the new-format message (I'll
call it new-gex here) using { min, preferred, max } rather than the original
{ preferred } format (I'll call it gex).  This looks like it's been bolted on
recently without updating the rest of the text, which still describes the
behaviour for gex.  In fact I couldn't actually find a server that would
accept the new-gex format, only the old gex one (they just rejected requests
with the new-gex message).

As it stands now, the new-gex doesn't actually serve any purpose, and in fact
the overall mechanism is somewhat confused.  The text says:

  The server can constantly compute new groups in the back-ground.

However it can't really do this because the group size is chosen by the
client!  In order to be able to usefully do this, it would have to maintain
and constantly update a smorgasbord of group sizes to handle any request the
client might decide to make.  In order to avoid this problem the text says:

  The server should return the smallest group it knows that is larger than the
  size the client requested.  If the server does not know a group that is
  larger than the client request, then it SHOULD return the largest group it
  knows.

This avoids the need to maintain a whole array of possible key sizes to match
any eventuality, but also means the server can more or less completely ignore
what the client requests.  Depending on how silly you want to get, you could
either always return the default built-in DH key, or generate some
outrageously large key which is guaranteed to always be larger than what the
client asks for and return that, both of which are fully compliant with the
spec.  In any case, the new-gex format is at best completely redundant and at
worst misleading, since the message format implies some sort of choice while
the text says the server can do anything it feels like:

         Servers and clients SHOULD support groups with a modulus
         length of k bits, where 1024 <= k <= 8192.  The recommended
         values for min and max are 1024 and 8192 respectively.

which is synonymous with "you can use any (safe) key size you feel like".

The problem here is that the server is the one to make the choice, but the
client is supposed to somehow know what appropriate requests to match the
choice should be.  For example if the client really needs to use a 1Kbit key
for performance reasons and all the server has is a 2Kbit key, the client
would be better off choosing the built-in default DH key rather than asking
for a 1K gex key and getting back a 2K one.  The negotiation is being done the
wrong way round.

The fix is simple: Instead of saying:

  "diffie-hellman-group-exchange-sha1"

the server says:

  "diffie-hellman-group-exchange-<size1>-sha1,diffie-hellman-group-
  exchange-<sizeN>-sha1,diffie-hellman-group1-sha1"

and the client can then choose what it wants.  Standard/permitted sizes would
be "1024", "2048", and "4096" (and "8192" if you really want to get silly,
from the Skip code an 8K key took two days of CPU time on the fastest Alpha
server they had available, so I doubt many of these would be generated in the
background by servers), in practice it's expected that N would never exceed 1
or 2.  If there's a need to be backwards-compatible with existing
implementations, you could add a "diffie-hellman-group-exchange-sha1" after
the initial entries and accept the current hit-or-miss semantics for that
entry.

For example if the server does a background keygen of 1K and 2K keys it could
advertise:

  "diffie-hellman-group-exchange-1024-sha1,diffie-hellman-group-
  exchange-2048-sha1,diffie-hellman-group1-sha1"

If it only generates 2K keys:

  "diffie-hellman-group-exchange-2048-sha1,diffie-hellman-group1-sha1"

and the client, seeing this, can decide whether it wants a slow 2Kbit key or a
faster (but perhaps not as secure) 1K bit built-in key.

If the server has just used its 2K ephemeral key and needs time to generate a
new one:

  "diffie-hellman-group-exchange-1024-sha1,diffie-hellman-group1-sha1"

and the client can decide whether it wants to use a 1K key or wait for a new
2K one to be generated.

So that was the first problem.  The second one is the way the key is
communicated, which is by sending the raw key components rather than by using
the standard SSH key format:

   Certificates and public keys are encoded as follows:

     string   certificate or public key format identifier
     byte[n]  key/certificate data

This is problematic because it assumes that the only key type that will ever
be used is a DH key, and that a DH key is only made up of p and g components.
The spec warns about the use of safe primes, but by the use of a nonstandard
key format rules out any means of communicating the safe-prime information to
the server.  For example if you generate DLP keys using the DSA kosheriser (or
any format that provides more than the PKCS #3 p and g) you can communicate
the verification parameters to the client, and they can check things without
having to blindly trust the server.  So if the server wants to send raw PKCS
#3 keys it would use:

     string    "ssh-dh"
     mpint     p
     mpint     g

If it was using verifiable DLP keys it would send:

     string    "ssh-dss"
     mpint     p
     mpint     q
     mpint     g
     mpint     y

and if you really wanted to go to extremes you could send:

     string    "ssh-dss-verifiable"
     mpint     p
     mpint     q
     mpint     g
     mpint     j               -- Subgroup factor satisfying p = jq + 1
     [...]     validationParms -- For kosheriser seed generation
     mpint     y

Implementations know that the built-in DH value is safe because of its
origins, with the inclusion of verification parameters it's possible for
clients to check this for any new keys handed out by the server, but with only
raw key components they have to blindly trust the server to use appropriate
keys.

At a minimum, it should at least use the standard SSH format for public keys,
rather than just sending raw key components across.

Peter.