Subject: Re: I-D ACTION:draft-weber-secsh-pkalg-none-00.txt

From: "Joel N. Weber II" <[email-masked]>
Date: Tue, 01 Jul 2003 18:41:21 -0400

So, I think I've been a bit confused about the subtlies of this.
Having read the documents more carefully, my current understanding is
this:

SSH_MSG_KEXGSS_HOSTKEY has this format:

           byte      SSH_MSG_KEXGSS_HOSTKEY
           string    server public host key and certificates (K_S)

K_S has this format:

   Certificates and public keys are encoded as follows:
     
     string   certificate or public key format identifier
     byte[n]  key/certificate data

The format identifier is something like ``ssh-rsa'', which means that
a host can send a public host key in a SSH_MSG_KEXGSS_HOSTKEY and the
client will be able to figure out which host key format it got.

I do think that if SSH_MSG_KEXGSS_HOSTKEY is to be prefered over a
public key algorithm of none, it should probably be defined to also be
usable when using non-GSS key exchange with certificates that can
expire.

---

From: "Joel N. Weber II" <[email-masked]>
Date: Tue, 01 Jul 2003 22:30:13 -0400

Looking at the January 2002 mailing list archive, it becomes clear
that while the public key types defined in the transport draft have
this encoding:

there is no requirement that public key types defined elsewhere will
have that encoding.  Perhaps the gsskeyex draft should explicitly say
that SSH_MSG_KEXGSS_HOSTKEY only works with ssh-dss and ssh-rsa keys,
or that it only works with types that start out with the type
identifier as a string.

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Wed, 16 Jul 2003 10:18:37 +0200 (CEST)

> or that it only works with types that start out with the type

Hm..
My interpretation of the description of public key algorithms in section
4.6 of the transport draft is that the encoding described above applies to
_all_ public key types, not just the ones defined in that document.  In
particular, the section you quoted contains general information describing
the nature of public key algorithms and key and certificate formats.  The
descriptions of specific algorithms defined in that document occur further
down, and while they do describe key formats including the specific value
of the format identifier to be used, this duplication is consistent with
usage in these documents.

-- Jeff

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Thu, 17 Jul 2003 16:10:56 +0200 (CEST)

> usage in these documents.

Actually, on further reflection, it doesn't matter.
The key transported in an SSH_MSG_KEXGSS_HOSTKEY message belongs to the
host key algorithm selected during algorithm negotiation.  So we already
know its type, and it doesn't matter whether the type is included in the
blob we transport or not.

Of course, this only helps when you are transporting a single host key of
the type selected during algorithm negotiation.  Fortunately, that is all
that gsskeyex currently does.  However, it doesn't help if what you want
to do is transport multiple host keys, or use keyex with one algorithm to
transport a key belonging to a second algorithm.

To address those issues, I would like to propose a protocol extension in
the form of a new host key algorithm, which could be called something like
'multi'.  The key format for this algorithm would consist of a list of one
or more { algorithm, key-data } tuples, and the format and semantics of
signatures would be identical to those for the first tuple in the list.
I haven't yet worked out all the details of how the algorithm negotiation
would work, but I think it's doable.

If there's interest in this, I'd be willing to work up a draft, either
as a working group item or for individual submission.

-- Jeff

---

From: "Joel N. Weber II" <[email-masked]>
Date: Thu, 17 Jul 2003 11:09:11 -0400

I'm likely to submit an individual draft soon describing an
SSH_MSG_KEXINIT2 message real soon now.  (Existing implementations
will see it as a reserved message and send a message back saying that
they don't recognize SSH_MSG_KEXINIT2, at least if they follow the
IETF spec.)  Specific things I want to change vs SSH_MSG_KEXINIT:

1) You iterate primarily over the host key list, rather than the
   algorithm list.  Once you find a host key type that's in common
   between the client and the server, you then iterate over the key
   exchange algorithm list looking for the first algorithm on the
   client's list that's also in the server's list that works with the
   host key type you picked.

2) Each gss mechanism becomes a host key type, so that if your order
   of preference is kerberos, pgp, gsi, x.509, bare ssh key, in that
   order, you can actually express that preference (which you just
   can't do in that order with the way SSH_MSG_KEXINIT and the gssapi
   draft are currently specified).

3) The language optional field as it exists goes away.

4) Any optional fields after the standard set of required fields each
   start out with a name indicating what they are negotiating.  So,
   you could have, for example

secondary-host-key,ssh-dss,ssh-rsa

if you wanted to negotiate public key algorithms for a secondary host
key.  The functionality of the optional language field in
SSH_MSG_KEXINIT would also have a name added to the front of it.

Perhaps the multi type you're proposing should be defined for
secondary-host-key but not for use with a key exchange algorithm to
actually verify the host's identity?

5) In order to prevent downgrade attacks, an implementation that would
   prefer to use SSH_MSG_KEXINIT2 lists SSH_MSG_KEXINIT2 as a keyex
   algorithm if it ends up sending an SSH_MSG_KEXINIT message, and if
   the SSH_MSG_KEXINIT from the peer includes SSH_MSG_KEXINIT2 as a
   key exchange algorithm when you also included SSH_MSG_KEXINIT2 as a
   key exchange algorithm, you abort.

Does this seem like it would help with solving the problems you're
interested in solving?

---

From: "Joel N. Weber II" <[email-masked]>
Date: Thu, 17 Jul 2003 12:44:26 -0400

> How about a global request that a client send (after kex) to the server
> to list the server's public host keys?

Regardless of what GSSAPI ends up doing, something like that is
probably a good idea for OpenPGP: it would be nice to have a way to
get revocation certificates from the server after you have connected
to the correct server, in case there are old host keys that have been
stolen, and I don't think putting multiple toplevel keys in the key
sent during keyex is the right solution.  I'm willing to write a draft
about messages to do this, though if jhutz wants to, I'd be happy to
defer to him.

(Indeed, the draft on using pgp-sign-* with secsh that I've written
and intend to submit as soon as drafts are being accepted again talks
about the usefulness of such a mechanism, without proposing one.)

A similar revocation mechanism for X.509 may also be a good idea.

---

From: Nicolas Williams <[email-masked]>
Date: Thu, 17 Jul 2003 10:00:09 -0700

> A similar revocation mechanism for X.509 may also be a good idea.

I think I'd call this "implicit revocation."  The server tells the
clients what all its publick keys (and certs) are after authenticating
itself to the clients and the clients update their database of known
server host keys, adding new ones and removing old ones.

I think doing this as a global request rather than as a new host key
pseudo-alg is the way to go.  The only problem being that global
requests are a feature of the "ssh-connection" service, so new services
would have to duplicate this functionality.

Cheers,

Nico
--

---

From: Nicolas Williams <[email-masked]>
Date: Thu, 17 Jul 2003 09:22:44 -0700

Nico
--

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Thu, 17 Jul 2003 20:30:30 +0200 (CEST)

> would have to duplicate this functionality.

I agree.  Let's drop the 'multi' pseudo-algorithm proposal, and consider a
new global request instead.  Ideally, we'd find a way to do this not as
part of a particular connection service, since it really relates directly
to the transport protocol.

-- Jeff

---

From: Nicolas Williams <[email-masked]>
Date: Thu, 17 Jul 2003 11:55:07 -0700

> to the transport protocol.

Agreed.  Unfortunately, there is no method for negotiating the use of
features not present in the transport I-D.  This problem has come up in
the "gssapi host key algorithm usage" and "retrying keyex" threads.

To solve the multi host public key advertisement issue elegantly we'd
have to add a post-keyex, pre-userauth message and response.  And we'd
have to negotiate support for this during keyex.

To negotiate new features in keyex elegantly we must either make use of
the reserved uint32 field in the SSH_MSG_KEXINIT packet or rev the
protocol minor version.  Making use of that reserved field without
revving the protocol minor version is problematic because the transport
I-D does not discuss its semantics (do we have time to fix that?  I
guess I'd better comment on that before the last call ends).  And
revving the protocol minor version is a non-starter at the moment and
probably won't come to pass for quite some time.

(I'm ignoring, too, the issue of how v1 vs. v2 negotiation would happen
 if the v2 minor version is revved - let's not go there).

To negotiate new features in keyex without revving the protocol minor
version or without extending the SSH_MSG_KEXINIT may not be elegant but
it is doable.  I have suggested the use of bogus alg names for this
purpose in earlier threads.

We should explore the semantics of SSH_MSG_KEXINIT extensibility.

Cheers,

Nico
--

---

From: "Joel N. Weber II" <[email-masked]>
Date: Thu, 17 Jul 2003 15:21:39 -0400

>  if the v2 minor version is revved - let's not go there).

While I have previously spewed to the list about many of these things
as possible ways to extend the protocol and why they will work badly,
I did so before I'd realized that we had this in the transport draft:

| 9.4 Reserved Messages
| 
|    An implementation MUST respond to all unrecognized messages with an
|    SSH_MSG_UNIMPLEMENTED message in the order in which the messages were
|    received.  Such messages MUST be otherwise ignored.  Later protocol
|    versions may define other meanings for these message types.
| 
|      byte      SSH_MSG_UNIMPLEMENTED
|      uint32    packet sequence number of rejected message

So I see no reason why the working group can't declare that there will
be an SSH_MSG_KEXINIT2 which has a numeric value of 22, and
SSH_MSG_HOST_KEYS_REQ can be 23, and SSH_MSG_HOST_KEYS_REP can be 24.
(Or we could pick other numbers.  It isn't important what the numbers
are as long as we agree on them and nobody is using them for something
else.)  And unless someone knows that there are buggy implementations
out there, we can assume that ``negotiation'' will happen when
SSH_MSG_UNIMPLEMENTED gets sent.

---

From: "Joel N. Weber II" <[email-masked]>
Date: Thu, 17 Jul 2003 15:28:40 -0400

> server host keys, adding new ones and removing old ones.

You don't want to remove the old ones.  You want to mark them as
permanently unusable.

Consider a host foo.example.com which has a GPG host key.  Assume it
gets compromised, and the attacker copies the private key, and gets a
copy of the public key which has a signature made by the sysadmin's
public key.  Assume that my client doesn't store the compromised key.
There is nothing to require the attacker to send the revocation
certficate along with the key, and so if I don't have the revocation
certificate cached locally and pay attention to only what the attacker
sends me, it's entirely possible that I'll get something that looks
like a valid key.

Another way to try to solve this problem is by contacting a keyserver.
If you connect to a keyserver using TLS, and you trust the keyserver
to keep the revocation certificate for forever once it gets it, this
can be secure.  But I don't know any keyservers that support this
level of security, and it's desireable to not depend on being able to
contact a key server when authenticating an ssh server, for various
reasons related to performance, reliability, and denial of service
tradeoffs.  Contacting a keyserver in this fashion may be a feature
worth implementing someday, but being able to send revocation
certificates in the ssh protocol is still useful.

---

From: Nicolas Williams <[email-masked]>
Date: Thu, 17 Jul 2003 12:26:33 -0700

> SSH_MSG_UNIMPLEMENTED gets sent.

But, again, we have the problem that any such messages would not be
factored into the session ID, thus making downgrade attacks possible.

I'd rather either have KEXINIT extensibility semantics clarified or use
bogus alg names.

Cheers,

Nico
--

---

From: "Joel N. Weber II" <[email-masked]>
Date: Thu, 17 Jul 2003 15:46:11 -0400

> factored into the session ID, thus making downgrade attacks possible.

Are we discussing the mechanism for sending host keys after key
exchange?  If so, the answer is that you wait until after the
SSH_MSG_NEWKEYS, since the whole point of that is to provide keys that
will be useful for rekeying and or for host key veriftication in key
exchange in future connections.

As for SSH_MSG_KEXINIT2, I believe I explained how I propose to
prevent downgrade attacks.

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Thu, 17 Jul 2003 21:54:05 +0200 (CEST)

>    host key type you picked.

Eh.  I don't see a particular problem with this, but I don't see that it
really solves anything either.  This negotiation directly affects the
fundamental security of the protocol, and getting it wrong would really
suck badly.

>    draft are currently specified).

I don't think it's a good idea to try to treat GSS mechanisms as "host
keys".

The gsskeyex draft effectively defines a way to generate an independent
key exchange algorithm for any GSS mechanism.  Such algorithms use a
number of common components, but they are not one key exchange algorithm
with multiple "host key algorithms"; they are different key exchange
algorithms and should be treated as such.  Note that this approach was
adopted in large part to specifically avoid the sort of multi-level
negotiation problem that you appear to be trying to fix in item 1.

I also think that such a change is completely orthogonal to the question
of whether to select first the keyex algorithm or the host key algorithm.
GSS key exchange algorithms work with _any_ host key, so the selection of
host key type is not relevant to whether you want to use GSS, nor does it
affect what GSS mechanism will be used.  Similarly, neither the decision
to use GSS nor the selection of mechanism should affect what host key
algorithm is used.

> SSH_MSG_KEXINIT would also have a name added to the front of it.

Hm.  I'm sort of neutral on this.  An extension mechanism is probably
useful, but we should be careful that it does not get overused.

> actually verify the host's identity?

Actually, I think we can punt this part entirely; I think I prefer Nico's
approach of doing host key transfer in a separate message after key
exchange is complete.

>    key exchange algorithm, you abort.

Yes, something like this is definitely necessary, and I think what you
describe will work.

> Does this seem like it would help with solving the problems you're

So, I was going to start this message by suggesting that I think the goal
of solving the multi-level negotiation mechanism would be better solved by
the mechanism I proposed.  Unfortunately, I realized first that I hadn't
actually yet proposed the mechanism in question.  So I will do so now....

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.

Perhaps we could come up with a solution that incorporates both ideas, by
adding a new message type that results in selection of algorithm and host
key type at the same time.  I'm not sure what the right answer is here,
exactly, but I would not mind seeing a solution to the multi-level
problem.

-- Jeff

---

From: Nicolas Williams <[email-masked]>
Date: Thu, 17 Jul 2003 13:07:35 -0700

> exchange in future connections.

I was discussing the mechanism by which we extend the kex part of the
protocol.  While I agree with your comment about the mechanism for
sending host keys after kex, you suggested a negotiation method that
would apply also to extending the kex phase:

> prevent downgrade attacks.

Remind me?

Nico
--

---

From: "Joel N. Weber II" <[email-masked]>
Date: Thu, 17 Jul 2003 16:14:16 -0400

> I don't think it's a good idea to try to treat GSS mechanisms as "host

I don't understand why not.  A ``host key algorithm'' is a
subcomponent that is called by a key exchange algorithm in order to
verify the identity of a host.  The interface between the key exchange
algorithm and the host key algorithm is well defined, creating a
certain sort of interchangability.  The key exchange mechanisms
described by draft-ietf-secsh-gsskeyex all make the same GSSAPI calls;
the only difference is which GSSAPI mechanism is being used.

Also, the reason that I use the krb5 GSSAPI mechanism is because I
have a keytab, and I want to verify that that keytab matches up
properly.  The purpose of using the GSSAPI mechanism is to verify the
host's identity using a cryptographic key.

> negotiation problem that you appear to be trying to fix in item 1.

Yes, but it's the wrong way to avoid that problem, precisely because
if I want to use pgp-sign-rsa if that's available, and then use
Kerberos, and then use ssh-rsa, there is no way to specify that.

> to use GSS nor the selection of mechanism should affect what host key

I think you're confused on the definition of a host key.  You seem to
be assuming that a host key is always a public signing key.  But
draft-secsh-transport already allows for the possibility that you can
have a public encryption key, which would require a different sort of
key exchange algorithm.

> doesn't eliminate the existence of a multi-level negotiation.

What problem are you trying to solve that switching the order and
treating GSSAPI mechanisms as host keys can't solve?

I can't think of any reason why I'd want to use one key exchange
mechanism with pgp-sign-rsa and a different one with ssh-rsa, which
seems to be the problem you're trying to solve, so I'm wondering why
you're trying to solve that problem.

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Thu, 17 Jul 2003 22:39:23 +0200 (CEST)

On Thu, 17 Jul 2003, Joel N. Weber II wrote:

> The interface between the key exchange
> algorithm and the host key algorithm is well defined

And does not match the interface between a GSSAPI application protocol and
a GSSAPI mechanism.

> Kerberos, and then use ssh-rsa, there is no way to specify that.

No, it's not.  Please note that the problem you describe exists _whether
or not_ the intervening mechanism is GSS-KRB5.  krb5 is not a "host key"
that you want to use in preference to ssh-rsa; it's a key exchange that
you want to use in preference to using a DH exchange signed by a non-PGP
RSA key.  The problem would exist for some other key exchange, too.

The method in which GSS mechanisms are named doesn't make this problem go
away, since the scope of the problem goes beyond GSS.  However, it doesn't
make it worse, either.

> have a public encryption key, which would require a different sort of

No, I'm not confused.  I know what the sshv2 protocol defines as a host
key.  GSS mechanisms are not host keys.

I don't think we're going to make any progress on this issue, and I
haven't heard any comments on this from the rest of the working group.  At
the moment, I'm disinclined to make a sweeping change of the sort you
describe, because

(1) I don't believe that it is either necessary or sufficient to solve
    the multi-level negoitation problem.
(2) I don't believe it's the appropriate abstraction.
(3) I don't see a working group concensus for a change.  Actually, I don't
    see much of any response, but you need a concensus to make a change.
(4) We have a fair bit of implementation experience with the current
    approach, including multiple implementations some of which support
    several GSSAPI mechanisms.  It does work.
(5) It's late in the process, which IMHO raises the bar for changes.
(6) Again, lack of concensus to make the change.

> treating GSSAPI mechanisms as host keys can't solve?

What problem are you trying to solve that treating GSSAPI mechanisms as
host keys will solve?  The multi-layer negotiation problem (keyex must be
selected before host keys) is not unique to GSSAPI, and treating GSSAPI
mechanisms as host keys makes the problem _WORSE_, not better.

> you're trying to solve that problem.

I think you're limiting your vision to the mechanisms you happen to see
today, and what you can think of yourself using.  All of the algorithms
are replaceable, which can lead to arbitrary combinations, including
algorithms not presently in use.  For example, you'd have exactly the same
problem if you substituted the SRP algorithm that was discussed in another
thread instead of one of the GSS algorithms.

The problem is a general problem; let's use a general solution.

-- Jeff

---

From: Joseph Galbraith <[email-masked]>
Date: Thu, 17 Jul 2003 14:48:18 -0600

>Kerberos, and then use ssh-rsa, there is no way to specify that.
Now, I'm not claiming we can arrange it at this late data, but it seems like
maybe the correct way to address your concern would be to seperate key
exchange and server authentication.

Putting aside how to do this without a significant rewrite of the core 
drafts,
doing this might have several advantages.

1. I believe the problem you have would be resolved.  Rather than
'publickey' algorithms in our key exchange, you would instead
have 'server-authentication' methods.  Gssapi would not be a
key exchange method, it would be a server-authentication method.

2. Gssapi would have been a simpler draft because it would have had
to define diffie-hellman key exchange as well, and we would be
wondering whether we should do gssapi-group-exchange as well.

Now, on the half-serious, we could, but I'm not sure we want to, side of 
things, we
could introduce a new service, called authentication, instead of 
userauth, and make
it responsible for handling both host and user authentication.

We could do this in conjuction with the new KEX2 message you are proposing.

On the brighter side, it wouldn't hold up the core drafts, we could 
address other userauth
problems that have come up, and we would be world famous :-)

On the darker side, it is a lot of work, will take time, and we might be 
world infamous for
even suggesting it :-)

At any rate, I was hoping perhaps some clarity would be brought by the 
realization that
it is the tying of host authentication and key exchange that is the root 
of the problem.

Joseph

---

From: "Joel N. Weber II" <[email-masked]>
Date: Thu, 17 Jul 2003 17:09:27 -0400

> mechanisms as host keys makes the problem _WORSE_, not better.

Note that I proposed making two changes together (each GSS mechanism
is a host key algorithm, and you negotiate first on host keys rather
than first on key exchange algorithms).  It's obvious that if you make
either change without the other, the situation gets worse than it is
now.

However, I believe that if you make the two changes together, you
solve the problem I want to solve.

> thread instead of one of the GSS algorithms.

How would this fail?

If my host key algorithms are

pgp-sign-rsa,pgp-sign-dss,Se3H81ismmOC3OE+FwYCiQ==,srp,[GSI],x509v3-sign-rsa,x509v3-sign-dss,ssh-rsa,ssh-dss

and my key exchange algorithms are

diffie-hellman-group-exchange,diffie-hellman-group1,gss-group-exchange-sha1,gss-group1-sha1,srp

(assuming for the moment that srp ends up being its own keyex
mechanism and not a GSS mech, not that it matters for this discussion)

I don't see why going through the list of host key algorithms, finding
the first one that will work, and then picking the first suitable key
exchange algorithms will fail.

> The problem is a general problem; let's use a general solution.

Yes, but we shouldn't design in generality that doesn't provide value,
which I think your tuples proposal does.

---

From: "Joel N. Weber II" <[email-masked]>
Date: Thu, 17 Jul 2003 17:20:05 -0400

>     the multi-level negoitation problem.

Could you please explain why you believe the changes I have proposed
are not sufficient?  I don't think you've done so.

---

From: Nicolas Williams <[email-masked]>
Date: Fri, 18 Jul 2003 19:17:45 -0700

> fundamental security of the protocol, and getting it wrong would really

I do have a problem with it.  The reason the current KEXINIT sucks is
that it negotiates two important aspects of the ultimate kex method
independently.  While reversing the order of algorithm matching and
treating the GSS-API mechanisms as "host key algorithms" would solve one
problem we're dealing with I don't believe it to be a general solution.

The kex negotiation should negotiate kex method tuples where there's a
method name and some method-specific data, e.g.,

 - "diffie-hellman-group1-sha1 w/ ssh-dss host keys"
 - "diffie-hellman-group-exchange-sha1 w/ pgp-sign-dss host keys"
 - "gss-group1-sha1 w/ Kerberos mech [OID]"

And then too, the selection of cipher algorithm maybe ought to have an
impact on the selection of kex method - or else we should deprecate
fixed-group dh kex methods (at the cost of an extra 1/2 round-trip or
having the client always pick the group that satisfies the needs of the
cipher with largest key size).

I'm with Jeff - we gotta get this right; let's not have to repeat this
later.  But, see below - I want to fix KEXINIT rather than add KEXINIT2.

> I don't think it's a good idea to try to treat GSS mechanisms as "host

Me either.

> negotiation problem that you appear to be trying to fix in item 1.

I don't mind separating the one part from the other - I just mind
treating that second aspect of kex methods (the host key or gss mech) as
the same thing when they aren't obviously the same kind of thing.

I'd much rather treat the host key alg / gss mech as kex-specific
"arguments" and then negotiate {kex, kex-specific-args} tuples.

Alternatively, we could break the key exchange and the key exchange
authentication parts of kex apart and have a generic DH key exchange and
a generic message exchange for signing the DH key resulting from the DH
key exchange.  That way we'd need but a single key exchange method (or
two, if the fixed-group (1 round-trip) vs. negotiated group (1.5
round-trips) distinction is worth keeping) and a bunch of kex signature
exchange methods (ssh-*, pgp-*, ... gss-*).  This may sound suspiciously
like Joel's proposal, but the innovation here lies in changing the
actual kex messages for the dh methods and getting rid of the gss kex
name.

All of this is way too complicated anyways.  So let's see first if we
can't just cut through and simplify:

   Earlier I proposed the use of "alias" alg names to cure some of the
   ills with KEXINIT that would solve the preference expression problem
   that Joel had.  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.

> > 3) The language optional field as it exists goes away.

Why?  I agree that we don't need two sets of lang fields
(server-to-client and client-to-server).  But we need a language
negotiation for G11N.  And it has to happen _before_ userauth, and if it
can be piggy-backed onto the kex then you save a round-trip - funny,
that's how it is now, and it works too.

> Yes, something like this is definitely necessary, and I think what you

See above.  I'd rather not do a KEXINIT2 - I think we can fix most of
the problems, albeit not very elegantly, w/o such a drastic step.

> actually yet proposed the mechanism in question.  So I will do so now....

:)

> doesn't eliminate the existence of a multi-level negotiation.

Hey, you're stealing my idea!  Except that what I'd poposed was to use
aliases like "diffie-hellman-group1-sha1:ssh" and
"diffie-hellman-group1-sha1:pgp" (i.e., leave the actual signature alg
out, but leave the "cert" type in).  Plus a "re-triable-kex" bogus alg
name to indicate, well, that and the use extended kexinit for kex hash
chaining in subsequent kexinit messages.

This way we've got a backwards compatible set of kex extensions.

> exactly, but I would not mind seeing a solution to the multi-level

KISS.

Cheers,

Nico
--

---

From: Nicolas Williams <[email-masked]>
Date: Fri, 18 Jul 2003 19:23:51 -0700

> exchange and server authentication.

Correct.  And that's how it should have been from the get go.  But I do
think it's too late and I do think we have a not-elegant-but-bacwards-
compatible way of solving the problems with kex/key preference
expression and kex re-triability - I just posted on that.

> key exchange method, it would be a server-authentication method.

But each of these would have its own kex method too - to separate the
two now would be too much work and not backwards compatible -> a big PITA.

> wondering whether we should do gssapi-group-exchange as well.

Yup - kex and kex auth should have been separate all along.

> problems that have come up, and we would be world famous :-)

Yes it would hold up the core drafts.  We'd have to define a KEX1 vs.
KEX2 negotiation mechanism and all that.

> On the darker side, it is a lot of work, will take time, and we might be 

We've been discussing it already, and I can imagine that the chair might
be getting gloomy :)

> it is the tying of host authentication and key exchange that is the root 

I think so.

Cheers,

Nico
--

---

From: "Joel N. Weber II" <[email-masked]>
Date: Sat, 19 Jul 2003 01:55:07 -0400

> problem we're dealing with I don't believe it to be a general solution.

What problem do you believe would actually be solved by the solution
you're proposing that isn't solved by the solution I'm proposing?  I
can see where you're proposing to introduce more generality, but I
don't see why anyone will ever benefit from that generality.

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.

> cipher with largest key size).

We can always introduce a fixed-group dh kex method with a larger
modulus later.  Chances are that the implementations supporting the
new fixed group are going to be the ones that support the support the
stronger encryption algorithms.

> the same thing when they aren't obviously the same kind of thing.

So, stating that something is ``obviously [not] the same kind of
thing'' is not a useful way to communicate after we've had as many
round trips as we have establishing that we see things differently.
Can you explain why you believe this?

> actual kex messages for the dh methods and getting rid of the gss kex

One of my goals was to avoid changing the actual key exchange
protocols, and change only the KEXINIT message itself.

I also suspect you'd end up adding a round trip or two in the GSSAPI
case if you did this.

>    that Joel had.

Ugh, but I suppose that could solve the problem.  (If I end up with a
client that does all of krb5, X.509, pgp, and bare host keys, I'll end
up listing 8 distinct algorithms, probably, assuming each of those
four types does both group1 and group-exchange.  Plus at the end I'll
end up listing diffie-hellman-group1 and
diffie-hellman-group-exchange, for a total of ten.  While this is
ugly, it is difficult to argue that it is a problem; I don't know of
any reason why listing ten algorithms will fail.)

>    We could also negotiate KEXINIT extensions through

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.

> that's how it is now, and it works too.

Because I want to treat it as just another optional field that has a
field name label, rather than having its mere presence there imply
that it is what it is.

I certainly want the language field content to remain just as
expressible as it is now.  (And shifting to only one field rather than
two was a mistake that came from not reading the draft carefully
enough to realize there were two, not from intending a change.)

> > 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 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.
This leaves me feeling like I understand how to solve some problem
that might exist, without knowing what problem it solves.

---

From: Nicolas Williams <[email-masked]>
Date: Fri, 18 Jul 2003 23:17:23 -0700

> don't see why anyone will ever benefit from that generality.

Whoever designed KEXINIT did not foresee the problems we're running into
now.  Thus the desire to get the model right the second time.  Though
that may be moot since I am actually arguing that we ought to work with
what we got anyways.

> pgp and group1 with ssh-*, and I really don't see why that is going to

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.

> Can you explain why you believe this?

I will have to sleep on it.  Right now my thought is that we have a
separate kex alg for gss and so separating the kex name from the gss
mechanism name doesn't really change much (though taken with the change
in alg selection that you propose it would).

I think my argument boils down to this: if we're to introduce KEXINIT2
then we might as well fix it right, and that includes separating kex
from kex auth, because even adding KEXINIT2 would be a lot of work and
wouldn't be sufficiently general as proposed; the alternative is to
hack, if you wish, around the limitations of KEXINIT in a backwards
compatible way.

> > Alternatively, we could break the key exchange and the key exchange
[...]
> I also suspect you'd end up adding a round trip or two in the GSSAPI

No - the two exchanges could be done in parallel, with the MIC coming
last.  For 1-round-trip GSS mechanisms this means you can do the DH
exchange and the GSS-API exchange and the exchange of the signature of
the session ID all in one round-trip.  Cool, eh?

> any reason why listing ten algorithms will fail.)

Exactly.  It ain't elegant, but it's not wasteful either, either of
network resources or of WG reasources :)

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

> field name label, rather than having its mere presence there imply

Ok, I can live with that.

> enough to realize there were two, not from intending a change.)

Yes, but I'm afraid that having two was a mistake anyways, and the
semantics of language negotiation are much too underspecified.

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

> that might exist, without knowing what problem it solves.

You mean by adding "named" fields?

Nico
--

---

From: Bill Sommerfeld <[email-masked]>
Date: Sat, 19 Jul 2003 13:29:16 -0400

This is your working group chair speaking.

The sudden jump to discussion of problems with gss negotiation to the
overall ssh protocol architecture has gone way faster than I could
follow it in detail.  We've skipped from a statement of the problem
directly to discussing fundamental structural changes to ssh...

So, I'd like to call for a general moratorium on such proposals until
such time as we have a clear statement of why anything NEEDS to be
changed, and a clear understaning of the requirements of any such
change so we can figure out the path of least resistance.

						- Bill

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Mon, 21 Jul 2003 10:41:10 -0400 (EDT)

> > pgp and group1 with ssh-*, and I really don't see why that is going to

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.

> artificial and what we need is a distinction between kex method and kex

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

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

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

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

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

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Mon, 21 Jul 2003 11:23:34 -0400 (EDT)

> change so we can figure out the path of least resistance.

OK; that's fair enough.  I think we have been discussing four basic
problems, and have even come to agreement on solutions for two of them.
Allow me to recap somewhat, and then we can decide where to go from here.

(1) It is desirable for GSS-API key exchange to be able to proceed
    even when the server has no host key and the user's credentials have
    expired.  This is particularly important in the case of a rekey,
    where a failure means the session will be disconnected.  Ken Hornstein
    reports that this problem is causing difficulties for him in deploying
    ssh in his environment.

    Joel Weber proposed a solution to this, in the form of an individual
    internet-draft submission, draft-weber-secsh-pkalg-none-00.txt.  This
    proposal defines a new hostkey algorithm, to be used only during
    rekey, whose semantics amount to not actually performing any signature
    checking or encryption operations.  While there was some initial
    concern, people eventually realized that the rekey operation would be
    protected by the existng encryption.  It was then agreed, at least
    among those who spoke up, that this should be rolled into the gsskeyex
    draft.

(2) Currently, when key exchange fails for any reason, the session is
    disconnected and a client which wishes to try another key exchange
    method must reconnect and try again.  This has the disadvantage that
    any negotiation performed as part of the first connection is lost,
    and particularly that the sequence of negotiations and failures that
    lead to the ultimate selection of a key exchange algorithm and host
    key are not properly authenticated.

    To solve this problem, it has been proposed that key exchange be
    allowed to fail and be retried without disconnection, using a method
    that would allow the complete process to be properly authenticated.
    Exactly how to do this is under discussion, but it would likely
    involve a new message to be used when keyex fails, combined with one
    of (a) a rev in the protocol version, (b) a backward-compatible change
    to the format of the SSH_MSG_KEXINIT message, or (c) a new message to
    be used in place of SSH_MSG_KEXINIT.  I believe it is generally
    agreed that (a) is not acceptable.

(3) There is a multi-level negotiation issue involving the negotiation of
    keyex and host key algorithms.  These are currently listed and
    selected almost as if they were independent, when in fact that are
    not; in particular, a client must choose and express its order of
    preference for key exchange algorithms without regard to what host key
    algorithm will be used.  This makes it impossible to express cases
    like that described by Joel Weber, in which one would prefer to use a
    traditional DH algorithm (either group1 or group exchange) with a
    pgp-* host key, but failing that, to try a mechanism like GSS-krb5
    before falling back on DH using an ssh-* host key.

    IMHO, this is clearly the issue with the most contention with regard
    to finding a solution.  There are three separate proposals under
    discussion:
    (a) Joel Weber's proposal of turning GSSAPI key exchange into a single
        keyex algorithm with multiple host key types, and simultaneously
        reversing the order of selection such that the host key type is
        selected before keyex algorithm.  This involves a change in
        semantics which would be signalled by one of the methods described
        in (2)(a), (b), or (c) above; again, I believe it is generally
        agreed that (2)(a) is not acceptable.
    (b) Nico Williams' proposal of inventing "alias" names for keyex
        algorithms, which would be negotiated in the usual way but would
        carry with them the semantics of being restricted to particular
        host key types.  I expanded on this to propose a general way of
        constructing alias names, rather than requiring them to be
        registered individually for each { keyex, host key } tuple for
        which they are to be used.
    (c) The third proposal (whose origin I can't recall, but it might have
        been myself or Nico Williams) is to exchange a list of { keyex,
        restrictions } tuples, where restrictions might include host key
        algorithms or other parameters.  This would involve a change in
        the way in which this information is exchanged, using one of the
        methods described in (2)(b) or (2)(c) above.

(4) It is desirable under certain circumstances to securely transmit to
    the client a host key which was not used to authenticate the key
    exchange; particularly, a key not known to the client in advance.
    This is useful for bootstrapping a client's host key database using
    a preexisting authentication infrastructure (PGP, PKI, Kerberos,
    DNSSEC, etc), and also for allowing "rollover" when a host decides
    to change its long-term key (Ken Hornstein points out that some sites
    have policies which require long-term keys to be changed on a regular
    basis).

    The GSSAPI-based key exchange algorithms provide an optional mechanism
    for this, by allowing the transport of a host key belonging to the
    algorithm selected in the first steps of key exchange, and including
    that key in the exchange hash.  However, a more general solution is
    desired, which would allow multiple keys to be transported, as well
    as allowing the transport of additional host keys when using keyex
    algorithms other than the GSSAPI-based ones.

    My original proposal was to create a host key pseudo-algorithm which
    would actually carry a list of keys, and perform encryption and
    signature operations as with the first key.  I have since withdrawn
    that proposal, in favor of one proposed by Nico Williams, in which
    a new message type is defined which can be used to transport arbitrary
    host keys once the key exchange has been completed and new keys have
    been taken into use.

I believe the problem described in (1) is well-understood, and the
solution is fairly clean.  Barring any further discussion or objections
from the working group (which has been mostly silent on this), I will be
incorporating Joel's solution into the description of the 'null' host key
algorithm in the next version of the gsskeyex document.

I also believe the problem described in (4) is well-understood, and the
solution is again appropriate and fairly clean.  However, I think some
further work is required to nail down the details.  I will probably
contact Nico offline about preparing an internet-draft to document this
proposal.

(2) and (3) both involve significant changes to the protocol.  I believe
these can both be done as backward-compatible extensions without holding
up the core drafts.  However, I also agree that we should carefully
consider whether these problems are worth solving, particularly given the
amount of work required to specify them properly, evaluate the security
implications, and implement and test the changes.

-- Jeff

---

From: "Joel N. Weber II" <[email-masked]>
Date: Mon, 21 Jul 2003 12:08:43 -0400

[since my understanding is that Bill has asked us to not discuss how
to solve the problems we are trying to solve until we figure out what
problems we are trying to solve, there are some parts of your message
that I am not replying to here.]

> benefit in any other case.

I don't think that's true.  I even mentioned a hypothetical example
involving an srp kex algorithm when I said ``here's a list of possible
kex algorithms and ``host key'' algoithms; if we invert the order of
negotiation, why won't my proposal work?''

> extensions as irrelevant.  The problem is a general one, and requires a

What sort of new requirements do you think we'd get using a new host
key algorithm with an existing key exchange algorithm that provide
different problems than negotiating PGP vs X.509 vs a bare ssh host
key?  As far as I can guess, while the future is very much open to new
host key algorithms in this space, the problems in negotiating them
shouldn't be any different than what we have with the current
algorithms.

And what sort of new requirements do you expect would exist with new
host key algorithms?

If you could give a concrete example of a hypothetical new algorithm,
even if it had a few properties which were rather contrived, and
explain why it would have substantially different negotiation
requirements, I'd probably have an easier time understanding.

I think at some point in the past I may have also pointed out that
the current multilevel approach doesn't do the right thing if you
introduce key exchange algorithms that support encryption rather than
signing keys, and pgp-encrypt-dss, ssh-encrypt-dss, etc, and that
switching the host key vs key exchange algorithm order ought to fix
the problems with that, too.  Of course, I'm assuming that the thing
you care about primarily is being able to pick the most trusted
trusted-third-party scheme, since in practice host key verification
seems to be the weak link.

I just got thinking that another question we might consider is what
happens when you have an ssh server that wants to provide multiple
X.509 keys, each signed by a different CA.  (Last time I dealt with a
well-known CA, I distintively remember them not handling the private
key, but let's hypothetically assume a world where the CA hands you
the private key and the public key; it's probably a good thought
experiment for understanding what problem we're trying to solve if
we're going for generalization.  And I'm also not sure if the X.509
standard allows you to get your cert signed by more than one CA.)  I
could imagine solutions involving an extra field to negotiate which CA
to use; or creating x509v3-sign-rsa-verisign, x509v3-sign-rsa-thawte,
[email-masked], etc, though I don't think either of
these schemes is necessarily ideal.  The latter at least could be done
in a way that doesn't require any changes to the negotiating
infrastructure.

I'm starting to think that the last paragraph may be an argument in
favor of doing a KEXFAIL message with a reason code, where the reason
code indicates what kind of retry to do.  Because for some failure
modes, retrying the same thing with a different key is an option.  In
the extreme case, consider a GSSAPI mechanism where both the client
and the server have alternate credentials.  I don't think that KEXINIT
has much hope of being the right way to efficiently negotiate what to
retry when in that case.

> to the particular key exchange method used.

Why is it inappropriate to bind the public key algorithm to the key
exchange algorithm, yet appropriate to bind a GSSAPI mechanism to a
key exchange algorithm?

> used for host key exchange after keyex is complete acceptable to you?

Yes, a transport message to deal with that is acceptable to me, but it
was fairly recently that I realized that it was a valid option.
Indeed, I believe that I will end up wanting to define such a message
for PGP regardless of what GSSAPI ends up doing, though if it's
possible to use the same message for both (and I believe it is) I'd
like to do so.

(In practice, I believe that openssh has bugs such that we probably
want to recommend that you wait until after you've established a
connection with the userauth service before sending that transport
message, but I believe the IETF spec ought to allow its use anytime
after SSH_MSG_NEWKEYS.)

> algorithm negotiation and the possibility of keyex retries...

Probably.

---

From: Nicolas Williams <[email-masked]>
Date: Mon, 21 Jul 2003 09:12:07 -0700

> change so we can figure out the path of least resistance.

There are two, well, three problems that we've been discussing.  These
are all related only in that they have something to do with key
exchanges.

The problem statement:

A.  Key Exchange and Host Authentication Preference Expressibility

   This is a very unlikely problem that occurs under the following
   circumstances:

      - the client can support the use of three or more host
	authentication infrastructures

      and

      - at least two of those host authentication infrastructures are
	based on public key based using the dh-group1-sha1 or
	dh-group-exchange-sha1 key exchange methods

      and

      - at least one of those host authentication infrastructures is not
	based on host public keys usable with the dh-group1-sha1 or
	dh-group-exchange-sha1 key exchange methods

   The problem then is that some preferences cannot be expressed with
   the current KEXINIT message and algorithm negotiation algorithm.

   One example given to the list was one where the client wishes to
   offer the following preference:

      - diffie-hellman-group1-sha1 w/ pgp-* host keys
      - gss-group1-sha1-*
      - diffie-hellman-group1-sha1 w/ ssh-* host keys

   IMO, the proximate causes of this problem is the conflation of raw
   key exchange methods (DH) with host authentication methods (e.g.,
   ssh-rsa, pgp-dss, x509v3-sign-rsa, ...) and the expectation that all
   host authentication methods would be based on public key
   cryptosystems.

   Thus draft-ietf-secsh-gsskeyex defines its own key exchange method
   which is based on DH because the ones defined in the transport I-D
   are not appropriate since there is no way to fit in the GSS-API to
   authenticate the server.  A separate gss-group-exchange-sha1-* key
   exchange method will eventually be needed also, adding more
   duplication This too is a result of the conflation of key exchange
   and host authentication methods in draft-ietf-secsh-transport.

   A generic key exchange method based on DH plus a generic message
   exchange for server authentication would have allowed both, the use
   of public keys and the use of the GSS-API to authenticate the server
   to the client and prove that there's no man-in-the-middle.  It is
   years too late to consider this in any way other than academically.

   I do not propose that we solve this problem by starting from scratch.  In
   fact, I do not propose solving this problem unless we also want to
   solve (B) - see below.

B.  Key Exchange Should be Re-Triable

   SSHv2 clients and servers must commit to undertaking a single initial
   key exchange method per-connection and disconnect if that method
   fails.

   In the case of public key / certificate based host authentication
   algorithms the client might well refuse to accept the server's keys
   once the client knows what they are, but by then the key exchange
   cannot be re-tried.

   This problem too is unlikely (though I myself have experienced it
   plenty, mostly in situations where a server had multiple identities
   but the server's GSS-API implementation did not support the full
   range of GSS_C_NO_CREDENTIAL/GSS_C_NO_NAME semantics and the SSHv2
   server software did not fully support virtualization).

C.  Distribution of Authenticated Servers' Other Keys

   Draft-ietf-secsh-gsskeyex allows servers to send one, and only one
   public host key to clients protected by the gss-group1-sha1-... key
   exchange.  The I-D should have allowed for hosts to tell clients of
   all their host keys - but then, this feature should be not be
   specific to the GSS key exchange method, it should be available in
   all cases after key exchange succeeds.

IMO, problem (B) is the problem most worth solving, but it requires
extending the key exchange phase of the protocol, one way or another.

IMO, problem (C) is the simplest to solve and does not require modifying
the key exchange part of the protocol.

IMO, problem (A) is the problem least worth solving, but if we solve (B)
then we should consider solving (A) as well.

IMO, problems (A) and (B) can be solve backwards compatibly through
extensions to the KEXINIT message (see its 'reserved' field).  For this
we'd need draft-ietf-secsh-transport to have some text describing the
meta-semantics KEXINIT extensions and their negotiation so that problems
(A) and (B) can be solved in a separate I-D.  I will submit a last call
comment on this point.

Cheers,

Nico
--

---

From: Nicolas Williams <[email-masked]>
Date: Mon, 21 Jul 2003 11:16:55 -0500

I missed Jeff's post on the same topic.  My apologies.

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Mon, 21 Jul 2003 12:44:22 -0400 (EDT)

> negotiation, why won't my proposal work?''

Because your proposal depends on the thing in the second slot being
something that uses a "fake" host key algorithm instead of a real one.
Note that GSSAPI-based and SRP keyex mechanisms currently negotiate a
_real_ hostkey algorithm; if you change the process out from under them
then this functionality goes away.

> shouldn't be any different than what we have with the current

That's probably true, which is why I prefer to concentrate on the case of
potential new key exchange algorithms, which may be significantly
different from what we know about now.  However, the point is not that new
host key algorithms might have particular requirements as that people
might be willing to use certain keyex algorithms only with a suitably
"strong" host key algorithm.

> the problems with that, too.

I'm not sure I see how it's a problem.  Can you elaborate on why the
current model causes a problem here?

> Of course, I'm assuming that the thing

Ah, but I think you're making an invalid assumption.  While host key
verification is important, so is selection of a key exchange algorithm
that is suitably secure (and here by "key exchange", I mean it in the ssh
sense, where it includes the method used to bind a host's authentication
to the exchanged key).  Back when people assumed all keyex algorithms
would do basically the same thing (do an exchange and sign it with a
host's public key), the two seemed independent.  But in reality they are
not, as algorithms like the GSS and SRP ones have taught us.  I don't
think reversing the order makes anything better; it means we still have a
multi-layer negotiation problem; we have just inverted the order of the
layers.

> in a way that doesn't require any changes to the negotiating

Hm; this is an interesting problem.  I think the current theory is that
the host sends you its key along with all the signatures.  But if it has
to select which key to send you on the basis of what CA's you'll accept,
then it won't work.  There's also an identity problem here, in that a
host may need to decide which key and certs to send you based on what
identity you think it has.  TLS has this problem today...

> has much hope of being the right way to efficiently negotiate what to

I think I agree that if we handle the retry problem at all, there is some
complexity in deciding at what level to retry.  Probably we should put
that off until the WG has decided whether the problem is worth solving.

> exchange algorithm, yet appropriate to bind a GSSAPI mechanism to a

I think you misunderstood my intent.  In Nico's ideal world where "key
exchange" and "host authentication" are separate steps, there's no reason
that any particular key exchange and host authentication algorithms should
be bound together.  What I was suggesting above was that while it would be
good for "key exchange" and "host auth" to be separate, that doesn't mean
that for "host auth" types that use a public key, the public key algorithm
should be a function of the "host auth" type, any more than the symmetric
key algorithms we negotiate today are a function of the algorithm we use
to exchange them, or vice versa.

Please note that GSSAPI is not magically interchangeable with other host
key types.  Even in your hypothetical world where GSS mechanisms are
represented as host key types, you couldn't use one with
dffie-hellman-group1-sha1 -- GSS requires context establishment, which
could potentially take multiple round trips, before you can sign or
encrypt anything.

I guess what I'm saying is that it's not appropriate to bind GSSAPI to a
"key exchange" in the sense of the independent anonymous-DH-or-whatever
that would exist in Nico's ideal world.  But in the world we have today,
where key exchange and host authentication happen in the same place, it is
impossible not to bind key exchange and host authentication together.  And
GSS-API must be bound to a particular host authentication method, because
that is what defines the wire protocol bits that allow for GSS context
establishment.

So, I think we've argued on this issue more than enough.  Let's take a
step back and answer the question of whether the multi-level negotiation
problem is worth solving at all.  I don't think I know the answer to that
yet.  If the concensus is that it should be solved, then we can discuss
how.

So...  Do we believe this problem is worth solving?
If so, how simple does the solution need to be to be worthwhile?
Does an alias-based solution meet our needs?
If not, are new messages the only alternative?
If so, is that solution acceptable, or too complex to be worthwhile?

> possible to use the same message for both (and I believe it is) I'd

GSSAPI has a mechanism for dealing with this within the key exchange, for
a single key.  I think we're talking about a general solution now.

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Mon, 21 Jul 2003 17:20:56 -0400

On Monday, July 21, 2003 09:12:07 -0700 Nicolas Williams 
<[email-masked]> wrote:

I'm glad that we pretty much agree on what the problems are.  You seem to 
have omitted the rekey-without-host-key problem, which I called problem 
(1), probably because it's only peripherally relevant to this discussion. 
I would like to hear more comments from people as to whether problem (1) is 
worth solving and whether the solution I described (rolling the semantics 
of Joel Weber's 'none' hostkey algorithm into the 'null' already described 
in the gsskeyex document) is the correct solution.  I believe the answers 
to both questions are "yes", but confirmation would be nice.

I think I need to disagree with you slightly on priorities for the other 
problems...

> extending the key exchange phase of the protocol, one way or another.

IIRC this is what I called problem (2), the keyex retry problem.  I'm not 
sure whether it occurs often enough to be worth solving; I'd love to hear 
comments from people other than you, me, and Joel on this point.  I do 
agree that solving it requires extending the keyex protocol, probably along 
one of the three general paths I described in my message, none of which are 
terribly appealing to me.  I believe the bar to be passed before solving 
this problem should be rather high.

> the key exchange part of the protocol.

Well, no disagreement here.  Of the three problems you listed, this is 
clearly the simplest to solve, and I think we have already achieved 
concensus both that this is worth solving, and that the general approach 
we've discussed is correct.  Hopefully we'll have an I-D in short order, 
and people can comment on whether the specifics are right.  I would like 
some opinion from the WG members and the chair as to whether this should be 
a working group item or not.

> then we should consider solving (A) as well.

This is the multi-level algorithm negotiation problem, which I called 
problem (3).  I can only partially agree here...  If we solve (B), we 
should certainly consider solving (A), since it's clearly possible to do so 
if we're extending the key exchange anyway.  However, I think it may also 
be possible to solve (A) without modifying the key exchange mechanism, by 
using an alias-based approach.  If such a solution is sufficiently simple 
and actually meets the need, then I think the bar should be significantly 
lower than for a solution which requires modifying or extending the key 
exchange.

> (A) and (B) can be solved in a separate I-D.  I will submit a last call

Agree.

-- Jeff

---

From: Nicolas Williams <[email-masked]>
Date: Mon, 21 Jul 2003 15:39:46 -0700

[...]
> to indicate whether keyex retries are supported.

Right, I've been toying with this.  We need to have the transport I-D
fixed to describe the semantics of the last field of KEXINIT.  I just
posted separately about that with proposed I-D changes.

> and can be no hash, and thus nothing to chain.

I think we should proceed by:

 - describing the semantics of KEXINIT extensions (just posted on this)

 - extending KEXINIT in a separate I-D to include:

    - a field containing the checksum of the concatenation of previous
      packets relating to FAILED kex attempts (if any); this is where
      "chaining" comes in (and note that this checksum need not be
      specified on a per-kex method basis);

    - text stating that peers must not disconnect when kex fails if
      there remain any untried kex methods (including host key types);

    - a field for expressing kex/host key preferences as a list of
      tuples to override any values of the 'kex_algorithms' and
      'server_host_key_algorithms' legacy fields of the KEXINIT.

> process, as if the one that just failed had not been available.  However,

Correct.

> SSH_MSG_KEXFAIL message is sent, possibly containing information about

I don't think this is necessary when keyex fails on the client side - it
just should send a new [extended] KEXINIT.

> KEXFAIL messages sent as part of the same exchange.

I don't like the idea of modifying the existing session ID
specifications because those are spread over three I-Ds and never
envisioned that the session ID hash specs would change.

Whereas including a hash of the failed key exchange method's packets in
subsequent kex attempts results in binding the failed attempts to the
subsequent attempts without having to change the actual kex methods.

I much prefer the latter as it will result in a cleaner document.

[...]

:)

Details.  We want to negotiate tuples - how we encode them is not very
important right now (and "dh-group1-sha1-pgp-sign-dss" is really an
encoding for {"dh-group1-sha1", "pgp-sign-dss"}).

> occurances of '%', ':', and whatever the quoting character is.

I think we can come up with a tuple encoding that preserves @ signs.
Again, details.

> combinations just to see what the peer supports.  Hm...

With a new field for negotiating kex/host key type tuples the length
issue can go away.

> algorithm negotiation and the possibility of keyex retries...

The reason named fields are a good ide here is that we may only have ONE
shot at using the reserved uint32 last field of KEXINIT  (once there are
several values defined for it, not just two, the semantics of KEXINIT
extensions negotiation become more complex...).  Of course, we could
just keep appending an extensions field to every KEXINIT extension, to
avoid this problem.  :) :)

Nico
--

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Mon, 21 Jul 2003 19:40:00 -0400

>       specified on a per-kex method basis);

I'm not totally convinced.  It can't be a fixed algorithm; there has to be 
an upgrade path so we don't get screwed if the algorithm we choose turns 
out to be broken.  IMHO the simplest way to handle this is by just allowing 
the keyex to checksum the concatenation of the whole mess at the end, but 
maybe you have a better idea.

Is it necessary to record the complete set of messages exchanged?  I guess 
it probably is, since otherwise the attacker could DoS a better keyex out 
of the way to get at a worse one.

>       there remain any untried kex methods (including host key types);

MUST NOT is too strong, I think.  I'd be happy with a SHOULD NOT, with the 
idea being that you either disconnect or send a retry message, with a 
strong preference for the latter.

>       'server_host_key_algorithms' legacy fields of the KEXINIT.

Yes.

> just should send a new [extended] KEXINIT.

I'm not sure.  I'd have to consider the semantics of this carefully, to 
make sure we don't have a deadlock.  I think you're probably right, but 
I'll have to reread the transport document.

> envisioned that the session ID hash specs would change.

I'm fine with chaining, as long as you can show me a reasonable way to 
determine what hash algorithm to use.

> encoding for {"dh-group1-sha1", "pgp-sign-dss"}).

Agreed.  A better question is, can we solve the problem adequately using an 
encoding that fits everything into the existing key exchange process, or do 
we have to extend it.  I believe this has a significant impact on whether 
the work is too complex to be worthwhile, and on whether we will be able to 
get implementors to adopt it.

> avoid this problem.  :) :)

I guess I was thinking in terms of defining the extensions field as a sort 
of sub-version, which grows as more extension fields are added.  Yes, this 
means the extension mechanism can only be used by IETF consensus.  That 
does not strike me as a problem in this case. :-)

-- Jeff

---

From: Nicolas Williams <[email-masked]>
Date: Mon, 21 Jul 2003 21:22:03 -0700

> <[email-masked]> wrote:

I too am glad to see that we're mostly in agreement.

> sure whether it occurs often enough to be worth solving; I'd love to hear 

You need only have two kex methods (in any permutation with host key
algs) to trigger this problem from time to time.

Whereas you need at least three for problem (A), at least two of which
must be the traditional kex methods, and at least one of which must not.

I think (B) is much more likely than (A) - and I have experienced it
myself; I have never experienced (A).

> this problem should be rather high.

I agree, but I think we MUST fix the transport I-D wrt KEXINIT
extensibility.  If we do that now then we can wait till later to solve
(A) and/or (B).

Yes, you can solve (A) with aliases.  You can also solve (B) with the
"bogus" alg name approach (and modifying the session ID specs to include
the failed kex attempt's messages in the session ID hash).

Before we do either we really ought to fix the transport I-D wrt KEXINIT
extensibility, and in the process find out what implementations do today
about extended KEXINITs.  Though I've proposed the alg aliases/bogus alg
approach I think extending KEXINIT is the right approach and the clean
approach.

Cheers,

Nico
--

---

From: Nicolas Williams <[email-masked]>
Date: Tue, 22 Jul 2003 06:59:18 -0700

> determine what hash algorithm to use.

First extended KEXINIT pair of messages has no chained checksum - it
would have to have a field for negotiation of hash functions.

> get implementors to adopt it.

Agreed.  This is the crucial decision we'll have to make.

> does not strike me as a problem in this case. :-)

Ok.

Nico
--

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Tue, 22 Jul 2003 11:37:37 -0400

> myself; I have never experienced (A).

Fair enough.

>> agree that solving it requires extending the keyex protocol, probably
>> along  one of the three general paths I described in my message, none of
>> which are  terribly appealing to me.  I believe the bar to be passed
>> before solving  this problem should be rather high.
>

Yes, definitely.

> approach I think extending KEXINIT is the right approach and the clean

Yes, extending KEXINIT is definitely cleaner.

---

From: Tomi Salo <[email-masked]>
Date: Tue, 22 Jul 2003 20:48:12 +0300

> identity you think it has.  TLS has this problem today...

   It's an interesting problem, and a real one. There may not be many
   reasons for a host to have multiple plain DSA or RSA keys, but with
   certificates (X.509), there is a real need for one server to have 
   multiple certificates. For example, the server might be used by
   several groups of clients, each group trusting its' own CA. Right
   now, the server can't advertise multiple host keys of the same type
   and the client can't select among multiple host keys (of the same 
   type), even if it retried the connection after having the key
   exchange fail because of receiving a 'wrong' hostkey.

   Of Joel's ideas for fixing this...:

   Putting the hostkeys into the hostkey algorithm list as
   algorithm@name pairs might be a partial solution. The client would
   at least be able to iterate through the list of keys, even if it
   did have to start a new connection for each try. 

   Negotiating the CA by having the client send a list of trusted
   CAs and the server the list of available CAs could also work,
   but different host key algorithms might have completely different
   lists, so each party would have to send a separate list for each
   host key algorithm. 

-- 
Tomi T. Salo <[email-masked]>, SSH Communications Security Corp