Subject: Re: [psg.com #460] IESG - Transport - Oakley

From: Chris Lonvick <[email-masked]>
Date: Tue, 15 Jun 2004 08:53:54 -0700 (PDT)

Hi Folks,

From all of the notes on this subject, it looks like we may have some
consensus on how to address this issue.  Many thanks to everyone who
partifipated in this discussion; it helps to move us forward.  I believe
that this is going to require edits to 4 places in the documents.

[TRANSPORT] - revise section 8.1 (formerly titled
"diffie-hellman-group1-sha1")

8.1 Required Key Exchange Methods

   Two methods for key exchange are defined in this document.

   The "diffie-hellman-group1-sha1" method specifies Diffie-Hellman key
   exchange with SHA-1 as HASH, and Oakley Group 2 [RFC2409] (1024bit
   MODP Group).  This method MUST be supported for interoperability as all
   of the known implementations currently support it.

   The "diffie-hellman-group14-sha1" method specifies Diffie-Hellman key
   exchange with SHA-1 as HASH, and Oakley Group 14 [RFC3526] (2048bit
   MODP Group), and it MUST also be supported.

[NUMBERS] - Add a line in the current Section 4.3

4.3  Key Exchange Method Names

   The Key Exchange Method Name describes a key-exchange method for the
   protocol [SSH-TRANS].  The names MUST be printable US-ASCII strings,
   and MUST NOT contain the characters at-sign ('@'), comma (','), or
   whitespace or control characters (ASCII codes 32 or less).  Names are
   case-sensitive, and MUST NOT be longer than 64 characters.

   Requests for assignment of new key-exchange method names must be
   accompanied by a reference to a standards-track or Informational RFC
   which describes this method.

   Method name                   Reference
   ------------                  ---------
   diffie-hellman-group1-sha1    [SSH-TRANS, Section 8.1]
   diffie-hellman-group14-sha1   [SSH-TRANS, Section 8.1]

[ARCHITECTURE]  (2 changes needed)

(1)
Section 9.2.7 discusses Forward Secrecy and PFS, and it specifically names
diffie-hellman-group1-sha1.  This can be changed to "the key exchange
methods described in Section 8.1 in [TRANS]".

(2)
A new section 9.2.8 will be needed to discuss the ordering of key exchange
method proposals.  Currently, [TRANS] Section 7.1 states:
-------------------
         kex_algorithms
         Key exchange algorithms were defined above.  The first
         algorithm MUST be the preferred (and guessed) algorithm.  If
         both sides make the same guess, that algorithm MUST be used.
         Otherwise, the following algorithm MUST be used to choose a key
         exchange method: iterate over client's kex algorithms, one at a
         time.  Choose the first algorithm that satisfies the following
         conditions:
         +  the server also supports the algorithm,
         +  if the algorithm requires an encryption-capable host key,
            there is an encryption-capable algorithm on the server's
            server_host_key_algorithms that is also supported by the
            client, and
         +  if the algorithm requires a signature-capable host key,
            there is a signature-capable algorithm on the server's
            server_host_key_algorithms that is also supported by the
            client.
         +  If no algorithm satisfying all these conditions can be
            found, the connection fails, and both sides MUST disconnect.
-------------------
The proposed new section in [ARCH] will say:

   As stated in Section 7.1 of [TRANS], each device will send a list of
   methods for key exchange.  The preferred method will be the first in
   the list.  The preferred method SHOULD be the cryptographically
   strongest method, and the method most likely to satisfy the conditions
   stated in that section.  Of the two methods defined in Section 8.1 of
   [TRANS], diffie-hellman-group14-sha1 MUST be listed before
   diffie-hellman-group1-sha1 in the kex list.  Implementors are
   encouraged to review current literature to decide upon the order of any
   other locally defined kex methods listed in the kex proposal.

These edits do _not_ address the following items:

- Parameterizing the kex namespace.

- Using SSH"group1" when we mean IKE"group2".  From what I understand,
making changes to this would have interoperability ramifications to the
deployed products.

- Referencing DH-GEX.

If there is strong consensus from the WG that any of these issues really
needs to be addressed, I will work on them.

Can I get some feedback on these proposed changes and the items I'm not
addressing?

Thanks,
Chris

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Tue, 15 Jun 2004 12:17:33 -0400

>    MODP Group), and it MUST also be supported.

I don't like the section name.
Structurally, this section isn't about defining required methods; it's 
about defining some specific methods that build on the functional 
description in the section before.  IMHO this would work better with 
separate sections 8.1 and 8.2, defining diffie-hellman-group1-sha1 and 
diffie-hellman-group14-sha1, resepectively.

In any case, the new method needs to be listed in section 6.5, "Key 
Exchange Methods".

> [NUMBERS] - Add a line in the current Section 4.3

Fine.

> methods described in Section 8.1 in [TRANS]".

Make it section 8.  Really, the statement applies to anything built on that 
general description, including new methods that may be defined in the 
future with different groups or hashes.

>    stated in that section.

The conditions are all about negotiating a method which both sides support. 
The only way to choose an order such that the preferred method is "likely 
to satisfy" these conditions is to choose one that you think the peer 
supports, and for which there is a suitable host key algorithm that you 
think the peer supports.  That would imply either waiting for the other 
side's KEXINIT message (both sides can't do this, and neither should), or 
making guesses based on the version string.

I propose dropping everything after the last comma.

>  Of the two methods defined in Section 8.1 of
>    diffie-hellman-group1-sha1 in the kex list.

I don't think we have concensus for this requirement.

> - Parameterizing the kex namespace.

I don't feel real strongly about this one way or the other.  I don't think 
we have agreement to do it yet, and I'm not sure how important it is.

> making changes to this would have interoperability ramifications to the

Yeah; it would suck.

> - Referencing DH-GEX.

I don't think this needs to be much more than a line in section 6.5 of the 
transport draft listing diffie-hellman-group-exchange-sha1 as a RECOMMENDED 
method, plus a mention somewhere in section 9.2 of the architecture draft.

-- Jeffrey T. Hutzelman (N3NHS) <[email-masked]>
   Sr. Research Systems Programmer
   School of Computer Science - Research Computing Facility
   Carnegie Mellon University - Pittsburgh, PA

---

From: [email-masked] (Niels Möller)
Date: 15 Jun 2004 19:54:23 +0200

> "diffie-hellman-group1-sha1")

Looks ok.

>    case-sensitive, and MUST NOT be longer than 64 characters.

This is the same for all algorithm names. It would make sense to
describe this name syntax in *one* place, and not repeat it several
times in the document. Besides from that nit, it looks ok to me.

> methods described in Section 8.1 in [TRANS]".

Or just make it clear that diffie-hellman-group1-sha1 is an *example* of
a specified key exchange method that have PFS-properties.

> method proposals.  Currently, [TRANS] Section 7.1 states:

I don't think this is needed at all. To me, the rules are the same as
for all the other algorithm lists: Each client lists the algorithms it
is willing to use, in the client's preferred order.

The client's preferences can be based on perceived relative strength,
or on cpu cost, or on explicit user configuration. It's totally up to
the client to decide.

The key exchange method is no different, in this respect, than the
host key algorithm list, encryption algorithm list and mac algorithm
list.

>    other locally defined kex methods listed in the kex proposal.

"You can get this nice car in any color of your choice, as long as
your choice is black", or "You must put the algorithm you prefer
first, and you MUST prefer the one I say". It makes the word "prefer"
meaningless. 

I *strongly* object to having MUSTs and SHOULDs here. And I'd prefer
not having this section at all.

If we, now or in the future, really want to deprecate
diffie-hellman-group1-sha1, the right way to do that is to *formally*
deprecate it, by changing

     diffie-hellman-group1-sha1       REQUIRED
     diffie-hellman-group14-sha1      REQUIRED

to

     diffie-hellman-group1-sha1       DEPRECATED
     diffie-hellman-group14-sha1      REQUIRED

in the appropriate document.

I don't want any semi-deprecated state that is is buried elsewhere in
the text, and in particular, the architecture document is *not* the
right place.

> - Parameterizing the kex namespace.

I see no need to do anything formal about that.

> making changes to this would have interoperability ramifications to the

Don't change diffie-hellman-group1-sha1, it's too late. Also, a new
alias for the same thing is unnecessary and pointless.

> needs to be addressed, I will work on them.

I don't have any strong opinion on that. I don't think it's necessary;
the dh-gex spec seems to be the right place for recommending dh-gex.

Regards,
/Niels

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Tue, 15 Jun 2004 14:19:12 -0400

>> Section 9.2.7 discusses Forward Secrecy and PFS, and it specifically
>> names diffie-hellman-group1-sha1.  This can be changed to "the key
>> exchange methods described in Section 8.1 in [TRANS]".
>
>> A new section 9.2.8 will be needed to discuss the ordering of key
>> exchange method proposals.  Currently, [TRANS] Section 7.1 states:
>

I'm not sure if you're commenting here on the proposed ARCH/9.2.8 text, or 
on the TRANS/7.1 text which Chris actually quoted at this point.  The 
quoted text was existing text from the transport draft, and is the 
normative description of the algorithm selection rules for key exchange 
(which are a bit more complicated than for others).  It needn't be 
duplicated in the architecture document, but I don't think that was being 
proposed.

>>    encouraged to review current literature to decide upon the order of
>>    any other locally defined kex methods listed in the kex proposal.
>

I'm inclined to agree; MUST is too strong.

> deprecate it, by changing

Careful.  REQUIRED means must-implement.  DEPRECATED doesn't mean anything, 
requirements-wise.  We want people to implement group1 but not prefer it. 
We do not want people not to implement it, at least now.

> the text, and in particular, the architecture document is *not* the

The security considerations section is a perfectly reasonable place for 
advice on algorithm selection, to the extent that we want to give such 
advice.  I'm still inclined to think we should provide some advice like 
"prefer diffie-hellman-group14-sha1".

On further reflection, I think it gets even more fun...
For some symmetric ciphers, group1 will be good enough.
For others, it will not.

What this means is that we should avoid selecting a cipher for which the 
kex does not provide enough keying material.  Or, more likely, we should 
avoid selecting a kex that does not provide enough keying material for the 
cipher we're going to use.  Unfortunately, that would mean changing the 
algorithm selection rules, and I think it's too late to do that without a 
really good reason.

As it stands now, we could end up negotiating diffie-hellman-group1-sha1 
and, say, aes256-cbc, which woule not be very good.  So, IMHO there's a
good security reason for giving advice about selecting a larger group.

-- Jeff

---

From: Bill Sommerfeld <[email-masked]>
Date: Tue, 15 Jun 2004 16:04:05 -0400

[wg chair hat off].

We have to cope with a grab bag of algorithms at seemingly random
bit-strengths that don't necessarily fit together well if you try to
tune one to match the other.  I think that's the wrong attitude..

> kex does not provide enough keying material.  

Reality check:

so, if the kex provides N bits, and you have a choice between a cipher
with keysize N/2 and keysize 2N, you would prefer the N/2-bit cipher
to running a 2N bit cipher with what is effectively a stretched N-bit
key?

The latter is obviously stronger against brute force attacks.  

> Or, more likely, we should avoid selecting a kex that does not
> provide enough keying material for the cipher we're going to use.
> Unfortunately, that would mean changing the algorithm selection
> rules, and I think it's too late to do that without a really good
> reason.

Going outside the scope of the IETF spec and deep into
quality-of-implementation space:

I'd rather see an application-level requirement for a specific
strength-in-bits.  If the kex generates enough bits, add it to the
acceptable list.  Likewise, if the symmetric algorithm is
N-bits-strong against all known attacks, add it to the list.

Then sort the lists by the performance metric of your choice
(throughput, latency, etc.,).  

						- Bill

---

From: [email-masked] (Niels Möller)
Date: 15 Jun 2004 23:35:16 +0200

Jeffrey Hutzelman <[email-masked]> writes:

> I'm not sure if you're commenting here on the proposed ARCH/9.2.8
> text, or on the TRANS/7.1 text which Chris actually quoted at this
> point.

Sorry if I was unclear. I didn't want to comment the old text in
section 7.1 of the transport draft, which is about how to select the
algorithm to use from the given lists. That's a little too hairy for
my taste, but if it works (I don't know, I haven't really tested the
"algorithm guessing" part), then we should *not* touch it now.

I wanted to comment the new text, which says in which order a client
should or must list its algorithms. I.e. the text which restricts the
set of allowed input to the algorithm selection procedure.

> The security considerations section is a perfectly reasonable place
> for advice on algorithm selection, to the extent that we want to give
> such advice.

This is partly a question of taste. The way I see the architectures
document, it should describe the overall structure of the protocol and
the components, which roles the various parts play, what security
properties the parts are expected to have, data types and background
needed in many places, etc.

I'd find it easier to accept a general recommendation that if there
are no other particular reason to prefer a certain algorithm over the
other, clients should list algorithms ordered by strength, strongest
first. Such a recommendation applies equally to all of the key exchange,
host key, encryption and mac algorithm lists.

Comments on particular algorithms seem out of place. If we really need
that, the security considerations section of the transport draft seems
like more natural place to me.

> What this means is that we should avoid selecting a cipher for which
> the kex does not provide enough keying material.

I don't buy this reasoning at all. The security requirements are
determined by the context in which the connection is made, not by the
key size of negotiated ciphers.

Say you have estimated that you need "100-bit security" (I'm not going
to try to define this rigorously, I hope you understand what I mean).
Then you can use a 110-bit key exchange method, and a 256-bit cipher
and a 256-bit mac. That's fine. The important thing is that *both* are
strong enough.

Or you can also use a 200-bit key exchange, a 128-bit cipher and a
160-bit mac. That's fine too.

It *doesn't matter* if the weakest link happens to be the key exchange
or the cipher, as long as it's strong enough. And it makes no sense to
strive towards a system where all links are of equal strength; if some
link happens to be much stronger than necessary, what's the problem
with that?

And I agree with Bill that if we want to replace preferences of the
form "I want group14 and aes256" (like in the implementations I'm
aware of) with preferences of the form "I want at least 100-bit
security", then that's excellent. It can be implemented in servers and
clients, and in all cases it affects *which* algorithms are listed,
not their order. As long as only algorithms that have adequate
security are listed, order doesn't matter.

> As it stands now, we could end up negotiating
> diffie-hellman-group1-sha1 and, say, aes256-cbc, which woule not be
> very good.

In this case, depending on the circumstances, either group1 is harder
to crack than your enemies can afford, or it isn't. If group1 is
strong enough, then (diffie-hellman-group1-sha1 + aes256-cbc) is
adequate, and so is (diffie-hellman-group1-sha1 + 3des-cbc). And I'd
choose aes256-cbc, since the overall security will be the same, and
aes256 likely is significantly faster.

And if your enemies do have a discrete log table for group1, or you
suspect that they might have, *don't* list that group, in any order,
ever.

Regards,
/Niels

---

From: Jon Bright <[email-masked]>
Date: Wed, 16 Jun 2004 11:24:00 +0200

Hi,

I'd argue for text more like this:

-----
As stated in Section 7.1 of [TRANS], each device will send a list of
methods for key exchange.  The most-preferred method is the first
in the list.  Implementations are free to determine their default
preferences based upon relative cryptographic security, performance
or other criteria.  If only the two methods defined in Section 8.1 of 
[TRANS] are are implemented, it is RECOMMENDED that 
diffie-hellman-group14-sha1 be listed before
diffie-hellman-group1-sha1 in the kex list.
----

Where this text belongs is a different question - [ARCH] is probably 
wrong, in my opinion.  This seems more like an issue for the Security 
Considerations section of [TRANS].  The text above would obviously need 
reformatting if it were moved there.

-- 
Jon Bright
Silicon Circus Ltd.
http://www.siliconcircus.com

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Tue, 15 Jun 2004 21:57:49 -0400 (EDT)

> The latter is obviously stronger against brute force attacks.

I'd prefer not to be running in either situation without knowing it.
Unfortunately, there are a lot of factors, and it's hard to say what
combinations are acceptable, so we don't try.  We also don't (can't)
prevent implementations from rejecting combinations they decide are
unacceptable.  It seems clear to me that listing the group14 method before
the group1 will result in better security and possibly better
interoperability.  That doesn't mean we need a REQUIREMENT here, but some
advice doesn't seem out of line.

> (throughput, latency, etc.,).

Yes, that sounds like a good approach for an implementation to take.
Of course, DH-GEX makes this real fun -- you can't know what key size it
will produce.  In other words, yet another multi-level negotiation issue.

-- Jeff

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Tue, 15 Jun 2004 22:05:01 -0400 (EDT)

> host key, encryption and mac algorithm lists.

Sure, that seems like a resonable recommendation to make.

> like more natural place to me.

The transport draft doesn't really have a security considerations section.
All the security considerations are collected in the architecture draft,
just as we collected all the IANA considerations in one place.

> key size of negotiated ciphers.

Yeah, OK.  The approach Bill describes makes a lot more sense.  And in any
case, it can't be anything other than a means of deciding what methods to
offer and in what order, which is entirely a matter of implementation and
local policy.

> security are listed, order doesn't matter.

Yes.  Now that it's been suggested, I'd love to see an implementation or
three actually do this.