Re: SSH_MSG_KEXGSS_HOSTKEY (was: Re: I-D ACTION:draft-weber-secsh-pkalg-none-00.txt)

[Jeffrey Hutzelman <jhutz%cmu.edu@localhost>]

On Fri, 18 Jul 2003, Nicolas Williams wrote:
> On Sat, Jul 19, 2003 at 01:55:07AM -0400, Joel N. Weber II wrote:

> > As I think I've said, it seems that you and jhutz think that someone
> > someday is going to have a burning desire to use group-exchange with
> > pgp and group1 with ssh-*, and I really don't see why that is going to
> > be especially useful.

Joel, I think you're failing to see the big picture.  You seem to be
seeing the multi-level negotiation problem only in terms of the mechanisms
that exist today.  You talk about wanting to prefer a traditional exchange
with PGP-signed keys over GSS-krb5, and GSS-krb5 over an exchange with
non-PGP-signed keys.  That's all well and good, but you are proposing a
"solution" which assumes that the _only_ alternative algorithm you'll ever
want to put in the second slot is a GSS-based one, and fails to have any
benefit in any other case.

When I point this out, you seem to think I am thinking of some situation
in which the second slot is occupied by diffie-hellman-group1-sha1 or
group exchange, combined with pgp-* or ssh-* host keys.  I am not.  I am
envisioning a situation in which the second slot is occupied by a
yet-to-be-defined keyex algorithm, or perhaps an existing one which uses a
yet-to-be-defined host key algorithm.  Since both of these spaces are
highly open to future extension, it is unacceptable to dismiss potential
extensions as irrelevant.  The problem is a general one, and requires a
general solution.


> No, I'm thinking that the distinction between kex and host key is
> artificial and what we need is a distinction between kex method and kex
> authentication method.

I agree that this should have been done from the beginning, but even that
is not sufficient.  There are really three separate problems here, which
existing keyex algorithms try to solve:

(1) key exchange; that is, agreeing on a key for encrpyting the session.
(2) authentication of the host, and binding this to the key exchange
(3) secure transport of a host key from the host to the client.

We've discussed a general solution to problem (3), involving a new message
type that could be sent after key exchange is complete.  I think we should
explore that avenue further in another thread, and concentrate for now on
problems (1) and (2).

Currently, solutions to (1) and (2) are defined by every "key exchange"
algorithm, which results in a lot of duplication.  For example, it means
that group exchange needs to be defined separately for every algorithm, as
does the exchange hash.  I agree that this is an unfortunate situation,
and that it would be better had these operations been separate.  However,
I also feel that, for those host authentication algorithms which require
the use of public-key encryption, it would be as inappropriate to bind the
key type to the host authentication algorithm as it is to bind key
exchange to that algorithm, or the symmetric cipher used for the session
to the particular key exchange method used.

Thus, if we wanted to do this right, we should negotiate key exchange,
host authentication, and host key algorithms as separate entities.  And of
course, parameterization should be involved so as to avoid the multi-level
negotiation problem.

However, I also feel that it is _far_ too late to rearchitect the protocol
to address this issue.  Making this change would affect the core drafts as
well as every keyex algorithm defined.  It would require defining new
auth-independent keyex algorithms, and new keyex-independent auth
algorithms, which is a lot of text to write.  And it would require
changing existing implementations, which I'll bet no one wants to do.  I'm
having enough trouble getting vendors to adopt gsskeyex; imagine the
difficulty of getting them to adopt a completely new keyex process with
completely new algorithms.  No, it is far too late.


What I think we _can_ do is agree on a mechanism, either through the
extension of KEXINIT or the addition of KEXINIT2, to negotiate tuples
of { keyex algorithm, keyex restrictions }, where the format of keyex
restrictions would be mostly keyex-specific but could include a
restriction (preferably defined in a general way) on what host key
algorithms could be used.  Note that it is important IMHO that the
restrictions field be used only to restrict the ways in which the keyex
algorithm can be used, and not to arbitrarily parameterize it.  Perhaps
I'm being too picky on this point...

> > >    We could also negotiate KEXINIT extensions through
> > >    the use of a bogus alg name.
> > >    If we then define the semantics of the reserved field of KEXINIT we
> > >    could add a field to KEXINIT (w/o revving the protocol version) for
> > >    chaining hashes of failed kex messages through to the next KEXINIT so
> > >    that the resulting session ID is bound to all kex messages and bingo,
> > >    we've got secure re-triable kex w/ downgrade attack detection and w/o
> > >    having to go back and modify the way each kex method defines the
> > >    session ID hash.
> >
> > Right now, each kex method just includes the packet that negotiated
> > the algorithm usage in the hash.  The amount of code required to use
> > KEXINIT2 when KEXINIT2 is used is almost certainly less than this
> > chaining proposal.  And this bogus algorithm name also strikes me as
> > likely to add complexity.
>
> Why?  If both the client and the server propose that bogus alg they know
> that if the first kex selected fails then they can retry and that the
> second try will have an extension field to the KEXINIT where the hash of
> the failed kex's messages will be included, or something to that effect.
> The point here is to avoid changing the definition of the channel ID
> hash, of which there are three currently, in three separate I-Ds.

Hm.  On some reflection, I don't believe the bogus algorithm name is
necessary to prevent a downgrade attack, nor do I believe that a KEXINIT2
message is required.  It should be sufficient to define a non-zero value
of the reserved field to indicate that additional fields follow.  These
fields should include advanced algorithm negotiation information (such as
I described above, or whatever we end up agreeing on) and also a boolean
to indicate whether keyex retries are supported.

There is some question as to what to do with a keyex retry, and how to
authenticate it.  I don't see how KEXINIT2 helps us here, but I don't see
how Nico's chaining proposal helps either.  The KEXINIT message is
constructed as part of the exchange hash, which is computed by each keyex
algorithm when the exchange is complete.  If key exchange fails, there is
and can be no hash, and thus nothing to chain.

I also don't believe it's necessary to repeat algorithm negotiation in the
case of a retry -- just go on to the next algorithm in the selection
process, as if the one that just failed had not been available.  However,
I do think we need a mechanism to signal keyex failure and the start of a
retry, as well as to carry information about the failure.  To this end, I
will propose that when a keyex fails and retry is supported, a
SSH_MSG_KEXFAIL message is sent, possibly containing information about
what combination of algorithms failed.  We can then assert that for the
purposes of computing the exchange hash, "the SSH_MSG_KEXINIT message"
actually consists of the concatenation of the KEXINIT message and all
KEXFAIL messages sent as part of the same exchange.


> > > > Basically, the general idea is to create a new series of "magic" keyex
> > > > algorithm names (hm.. I see a theme here).  These would look something
> > > > like XX:diffie-hellman-group1-sha1:ssh-dss, with the 'XX:' a constant
> > > > defined in the spec.  There are some problems with this approach, which I
> > > > haven't yet had time to fully research; that's why I hadn't yet brought up
> > > > the idea.  But I'd much rather see a mechanism that allows negotiation of
> > > > { keyex, host-key } tuples rather than simply switching the order, which
> > > > doesn't eliminate the existence of a multi-level negotiation.
> >
> > How does this interact with key exchange mechanisms and host key
> > mechanisms that contain at signs?
>
> I don't know what Jeff had in mind, but in my proposal these would be
> aliases of existing kex methods - taken to be limited to subsets of the
> host key algorithms - so any implementors of non-standard kex methods
> would not be affected (and to take advantage of this they'd have to
> define their own aliases).

Actually, my proposal was intended to model the semantics of Nico's (I'll
freely admit that's where I got the idea), in which these new things are
aliases of existing kex algorithms, with limitations on what host key
algorithms could be used.  However, I was going for a general solution, in
which aliases would not have to be explicitly defined "by hand" for each
possible combination -- IMHO this is always a good thing when the things
being combined are defined independently, as keyex and host key algorithms
are.

In this context, Joel's question about the handling of '@' indeed makes
sense.  I don't yet have a good answer; probably the '@' would be mapped
to some other character, such as '%', with a quoting mechanism for literal
occurances of '%', ':', and whatever the quoting character is.
Unfortunately, there is a fixed limit on algorithm name lengths, so I
don't yet see how my proposal can work.  I suppose we could have a model
in which we use a hash if the concatenation is too long, but I'd prefer
not to make implementations compute hashes of all the possible
combinations just to see what the peer supports.  Hm...

How about something like 'XX:keyex-alg:hostkey-alg', where XX is again a
constant, and keyex-alg and hostkey-alg are fixed-length hashes of the
corresponding algorithm names.  Then implementations could simply know the
hashed names of all their supported algorithms in advance, and the search
would become simple again.

Of course, this is only needed if we choose to solve the multi-level
problem in the context of the existing KEXINIT message, rather than
adopting a new negotiation mechanism by extending the message or adding a
new one.  I do think the alias approach is far less complex...


> > I think we need to figure out whether the problem of having extra
> > optional fields available is actually worth solving.  At one point I
> > thought it would be useful for SSH_MSG_KEXGSS_HOSTKEY public key
> > algorithm negotiation, but I no longer believe it is needed for that.

Joel...  Why is this?  Is the solution of adding a transport message to be
used for host key exchange after keyex is complete acceptable to you?

> > This leaves me feeling like I understand how to solve some problem
> > that might exist, without knowing what problem it solves.

Indeed, while I thought the named-field idea was a good general extension
mechanism when you proposed it, I'm not convinced it's necessary right
now.  Perhaps we should drop it, and focus exclusively on multi-level
algorithm negotiation and the possibility of keyex retries...

-- Jeff