Subject: RE: [Curdle] Group 15 needed in draft-baushke-ssh-dh-group-sha2

From: Peter Gutmann <[email-masked]>
Date: Fri, 2 Sep 2016 04:20:47 +0000

[email-masked] <[email-masked]> writes:

>Please advise if there is any consensus as to what changes to the
>https://tools.ietf.org/html/draft-ietf-curdle-ssh-kex-sha2-03 are needed to
>move the draft forward to a standard.

As long as there's a DH-2048 + SHA-256 in there as a SHOULD or MUST, I can
live with it.  In the embedded world where even DH-2048 is already a pain, a
requirement to use any of the ludicrous-speed keys won't go down well...

Peter.

---

From: "Mark D. Baushke" <[email-masked]>
Date: Thu, 1 Sep 2016 14:57:33 -0700

My goal with

  https://tools.ietf.org/html/draft-ietf-curdle-ssh-kex-sha2-03

is to deprecate the use of diffie-hellman groups that use sha1
and promote new key exchange algorithms.

The latest draft has

Key Exchange Method Name              Reference     Note
diffie-hellman-group-exchange-sha1    RFC4419       SHOULD NOT
diffie-hellman-group-exchange-sha256  RFC4419       MAY
diffie-hellman-group1-sha1            RFC4253       SHOULD NOT
diffie-hellman-group14-sha1           RFC4253       SHOULD
diffie-hellman-group14-sha256         This Draft    MAY
diffie-hellman-group16-sha512         This Draft    SHOULD
diffie-hellman-group18-sha512         This Draft    MAY

It seems reasonable to me to provide a replacement option of a DH MODP
group that is well known (already published in another RFC) with a
SHA2-256 or SHA2-512 associated hash.

(In my view, it is nice to have an upgraded alternative in the Finite
Field Cryptography (FFC) key exchanges for the values being deprecated.
So, it is desirable to come up with a group or groups that are
acceptable alternatives.)

MODP groups have been provided in a number of RFCs. In this case, I have
tried to choose a MODP group that would drop into the existing kex that
SSH uses with only a minor table change for the g,q,p and hash
algorithm. I did not try to play games with a MODP Group with 160-bit,
224-bit or 256-bit Prime Order Subgroups like Group22, Group23, or
Group24 specified in RFC 5114 because most implementation are probably
just calculating q rather than having it in a pre-calculated table.

For simplicity, I suggested the groups listed in RFC 3526 which also
provides a rough table of security strength estimates.

I originally thought that diffie-hellman-group14-sha256 might be
reasonable to provide a 2048-bit MODP Group which is already widely
deployed along with a hash algorithm (SHA2-256) that should be used to
replace SHA1.

However, there are those who seem to think that 128 bits or more of
security would be better (more than is provided by Group14) and many
folks are already trying to get rid of 3DES which has similar security
bits to the Group14 2048-bit MODP group.

So, either the Group15 3072-bit MODP Group (~128 bits of security) or
the Group16 4096-bit MODP group (slightly more than 128 bits of
security) using either SHA2-256 or SHA2-512.

I suggest that ONE of these MODP group should be provided as a 'SHOULD'
implementation as it is hoped that it is a very simple modification to
adjust to using a new MODP kex with a new hash in any SSH
implementation.

I am happy with either SHA2-256 or SHA2-512 as the hash, or even letting
the user choose which is desired by making diffie-hellman-<group>-<hash>
let the Group/hash tuple be provided in the negotiation. Where <hash> is
one of SHA256 or SHA512 in the SHA2 family.

I personally believe the following DH MODP list is too large:

  diffie-hellman-group14-sha256
  diffie-hellman-group14-sha512
  diffie-hellman-group15-sha256
  diffie-hellman-group15-sha512
  diffie-hellman-group16-sha256
  diffie-hellman-group16-sha512
  diffie-hellman-group17-sha256
  diffie-hellman-group17-sha512
  diffie-hellman-group18-sha256
  diffie-hellman-group18-sha512

I suspect just listing one of them as a SHOULD for now and possibly a
larger one as a MAY for use in the future is sufficient.

What is the correct DH MODP Group to promote to a SHOULD for
interoperability and what should be deprecated?

For myself, I am looking forward to curve25519-sha256 as a MUST
implementation and letting the NSA/Suite B folks live with whatever
ecdh-sha2-nisp{256,284,521} they feel they want to use.

Please advise if there is any consensus as to what changes to the
https://tools.ietf.org/html/draft-ietf-curdle-ssh-kex-sha2-03 are
needed to move the draft forward to a standard.

	Thank you,
	-- Mark

---

From: Damien Miller <[email-masked]>
Date: Tue, 6 Sep 2016 10:40:23 +1000 (AEST)

On Mon, 5 Sep 2016, Mark D. Baushke wrote:

> Hi,
> 
> The current draft-ietf-curdle-ssh-kex-sha2-03 draft expires in about a
> week, so I will be publishing a new draft before this Friday. Note: I
> will not be able to attend the IETF (November 13-18) in South Korea.
> 
> Here is my current sugestions for the DH entries in the table:
> 
> diffie-hellman-group14-sha256         This Draft    SHOULD
> diffie-hellman-group15-sha512         This Draft    MAY
> diffie-hellman-group17-sha512         This Draft    MAY
> I do not see any problems with letting these kex method names be defined
> and used by folks that want them.
> 
> The remaining questions are: 
> 
>   1) which DH groups are best noted as SHOULD and which ones as MAY
>      (Peter wants diffie-hellman-group14-*, denis wants
>      diffie-hellman-group15-*, and the OpenSSH 7.3 release will
>      negotiate diffie-hellman-group16-sha512 and
>      diffie-hellman-group18-sha512),
> 
>   and
> 
>   2) is the use of sha512 vs sha256 vs allowing either of the sha2
>      functions to be negotiated best to use for the new DH groups?
> 
> As you can see, I am currently tending toward not having any of the new
> DH groups be labled as MUST.
> 
> The -04 draft would therefore list curve25519-sha256 as the only MUST
> kex method.
> 
> Are there any strong objections to this direction?

Sounds good to me

-d

---

From: "denis bider \(Bitvise\)" <[email-masked]>
Date: Mon, 5 Sep 2016 17:12:18 -0600

I support the described change intentions.

With regard to question (1) about MAY/SHOULD – I don’t have a strong position. In my implementation experience, end users don’t care about these types of recommendations, and the recommendations do not stand the test of time. Our security conscious users knew they wanted to disable CBC before there was a spec about it. Our users now want Curve25519 and Ed25519, and they don’t need a “MUST” to tell them this.

The main reason I see to impose a SHOULD / SHOULD NOT is when the spec can inform the implementer about something that’s not obvious. For example, if I’m an implementer of desktop and server software, it may not be obvious that I should offer a key exchange method that’s feasible for resource-constrained devices. So, for interoperability reasons, it’s good to make group14-sha256 a SHOULD, and also to state the reason for this recommendation: interoperability with resource-constrained devices.

With regard to question (2) about SHA-2 versions – I would prefer only SHA-512 for group 15 and higher. Group 14 should use SHA-256 because it’s for interoperability with resource-constrained devices. Group 15 and higher need a way to be used with a 384-bit hash or larger to meet those irrelevant government recommendations no one likes to hear about. An implementation that can do 3072-bit DH can also do SHA-512, so I don’t see why not.

In summary, I think the proposal is fine.

denis

From: Mark D. Baushke 
Sent: Monday, September 5, 2016 15:56
To: Peter Gutmann ; denis bider (Bitvise) ; Damien Miller 
Cc: Daniel Migault ; Watson Ladd ; Paul Hoffman ; Rich Salz ; Phillip Hallam-Baker ; IETF Curdle ; IETF SSH 
Subject: Re: [Curdle] Group 15 needed in draft-baushke-ssh-dh-group-sha2 

Hi,

  and

Thanks,
-- Mark

---

From: "Mark D. Baushke" <[email-masked]>
Date: Mon, 5 Sep 2016 14:56:44 -0700

Hi,

  and

	Thanks,
	-- Mark

---

From: Mouse <[email-masked]>
Date: Tue, 6 Sep 2016 10:59:06 -0400 (EDT)

> The -04 draft would therefore list curve25519-sha256 as the only MUST

Speaking as an implementor, albeit of a relatively fringe
implementation, I do/will ignore anything that mandates elliptic curve
algorithms.

Whether this is worth paying attention to, of course, I cannot say.

/~\ The ASCII				  Mouse
\ / Ribbon Campaign
 X  Against HTML		[email-masked]
/ \ Email!	     7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B

---

From: Tero Kivinen <[email-masked]>
Date: Tue, 6 Sep 2016 16:11:48 +0300

> and used by folks that want them.

I think it is bad idea to define too many KEX methods. I think there
should only be two, one with sha256 one with sha512, i.e.,
diffie-hellman-group14-sha256 and diffie-hellman-group16-sha512.

The reason is that these key exchange methods are negotiated in text.
We already have key exchange list in openssh saying something like:

[email-masked],ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,diffie-hellman-group-exchange-sha256,diffie-hellman-group14-sha1

(150 octets), and now when we add to this list new methods:

,diffie-hellman-group14-sha256,diffie-hellman-group15-sha512,diffie-hellman-group16-sha512,diffie-hellman-group17-sha512,diffie-hellman-group18-sha512

(another 150 octets), it gets to 300 octets, just to negotiate the key
exchange methods. And this string is sent in both directions during
the negotiation.

Also I do not really expect most of them to be used ever...

At least if we define all of them, how about making strings bit
shorter, something like dh-g14-sha256 instead of
diffie-hellman-group14-sha256?

When you have multiple algorithms tied together (here key exchange
method, group, and hash) it is better to avoid full combinatory
expansion, and only define those which are known to be used.

Especially if we are saying curve25519-sha256 is going to be MUST, I
see no reason to define that many MAYs. 
-- 
[email-masked]

---

From: "denis bider \(Bitvise\)" <[email-masked]>
Date: Tue, 6 Sep 2016 13:15:31 -0600

Tero -

I agree I would much rather see dh-g14-sha256 than diffie-hellman-group14-sha256. However, the ship for this has sailed a long time ago. As far as I know, some of these methods are already implemented. The benefit of shortening the names is negligible compared to the likely coordination issues, and it could be argued that the longer names are more understandable, as well.

As far as I know, the cost of making the KEXINIT messages longer is trivial and probably not even worth mentioning. If SSH wanted to optimize this to begin with, it would have gone with single-character names for most algorithms, omit the commas in algorithm lists when not necessary, etc. The original designers have, in my opinion correctly, decided that readability trumps conciseness, and that the savings of a few bytes in a message that’s exchanged once per connection, and then once per hour or per 1 GB of data, are not worth chasing.

>From a performance perspective, the algorithms that involve DH group exchange are much costlier than negotiating the DH group in the KEXINIT packet, even if you were to enumerate many more groups than we are currently proposing. The group exchange methods involve not only sending two extra messages, which are hundreds of bytes themselves, but require an entire additional round-trip between the client and the server, adding noticeable latency to the establishment of the connection, or completion of key re-exchange.

Compared to the group exchange methods, negotiating the DH group in KEXINIT is downright efficient. And if you don’t want to use all of the groups, it is fairly straightforward to simply not include them.

Our SSH Server is going to include by default only diffie-hellman-group14-sha256 and diffie-hellman-group15-sha512. It is also going to be possible to enable diffie-hellman-group16-sha512, but it’s likely going to be disabled by default because it’s twice as costly as group 15 and exacerbates a denial of service vector for busy servers.

Our SSH Client is going to include all three of the above methods by default because it does not have to worry about denial of service.

We are not going to support groups higher than 16 at this time, both because of their cost, and because Windows CNG does not support them. I nevertheless welcome the definition of those groups, so that it is straightforward to implement them in case circumstances change so that this becomes desirable.

With respect to Curve25519, I think it’s nice and all, but it’s probably going to be the first thing broken by a quantum computer. Anyone concerned with forward secrecy should start using a hybrid key exchange method that incorporates a quantum-safe algorithm approximately now. It is that we should be focusing on, I think, instead of trying to put X25519 everywhere, cast in concrete. It’s going to bite us.

denis

From: Tero Kivinen 
Sent: Tuesday, September 6, 2016 07:11
To: Mark D. Baushke 
Cc: Daniel Migault ; Peter Gutmann ; Watson Ladd ; Damien Miller ; IETF Curdle ; Paul Hoffman ; Rich Salz ; denis bider (Bitvise) ; IETF SSH ; Phillip Hallam-Baker 
Subject: Re: [Curdle] Group 15 needed in draft-baushke-ssh-dh-group-sha2

_______________________________________________
Curdle mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/curdle

---

From: "Mark D. Baushke" <[email-masked]>
Date: Tue, 6 Sep 2016 12:19:38 -0700

> Mark D. Baushke writes:
...elided...
> I think it is bad idea to define too many KEX methods. 
>
> I think there should only be two, one with sha256 one with sha512,
> i.e., diffie-hellman-group14-sha256 and diffie-hellman-group16-sha512.

You would be implementing the SHOULD MODP groups in this case. This
seems like a reasonable configuration choice. If possible, I would hope
you could also support curve25519-sha256, given it seems desirable for
it to be a MUST kex.

> (150 octets), and now when we add to this list new methods:

Yes, but this draft RFC is moving most of those to MAY and some to
SHOULD NOT.

I would expect that after this RFC is published, a number of
implementation of the default kex proposals would only contain this
list:

curve25519-sha256,ecdh-sha2-nistp521,ecdh-sha2-nistp384,diffie-hellman-group16-sha512,diffie-hellman-group14-sha256,diffie-hellman-group14-sha1

which is the MUST and SHOULD entries which is only 143 octets.

> exchange methods. And this string is sent in both directions during

Yes.

Even if everyone were to implement all of the current kex methods and
have a proposal for each of them, is this a sufficient problem for an
implementation to need to save a sixteen bytes per algorithm?

If there support from the implementors for this change, I will ammend my
draft.

> Also I do not really expect most of them to be used ever...

The hope is that there is flexibility in the implementations to allow us
to more quicly discard 'weak' entries and adopt 'strong' entries as we
move forward.

> diffie-hellman-group14-sha256?

I think that the implementors need to provide their inputs on what
strings should represent the algorithms to be used.

> expansion, and only define those which are known to be used.

Isn't that a chicken and egg problem? None of these new kex names are
currently being used.

I would like to have at least one kex that uses sha512 given that some
cryptographic experts in the US government seem to think that sha256 is
not good enough for top secret. I don't know if they are ultra paranoid
or not, but it seems prudent to err on the side of being a bit paranoid
if it is not too expensive for the uses involved.

> see no reason to define that many MAYs. 

There are a lot of different stake-holders in this standard. I do not
pretend to be able to make the business trade-offs for everyone.

The primary goal of this RFC is to demote a number of weak key exchanges
and to promote the curve25519-sha256 kex. If there are enough
implementations that are able to move away from MODP groups, then
perhaps all of them could be deprecated. However, the diversity of the
math seems to be a compelling reason to have DH, ECDH, and EdDH methods
in place.

	-- Mark

---

From: Tero Kivinen <[email-masked]>
Date: Wed, 7 Sep 2016 13:42:46 +0300

denis bider \(Bitvise\) writes:
> I agree I would much rather see dh-g14-sha256 than
> diffie-hellman-group14-sha256. However, the ship for this has sailed a long
> time ago. As far as I know, some of these methods are already implemented. The
> benefit of shortening the names is negligible compared to the likely
> coordination issues, and it could be argued that the longer names are more
> understandable, as well.

If they follow the rules set for the identifiers for the secure shell,
they should not use names without domain name before "IETF CONSENSUS".
If they do that is their problem. We cannot make old names to use
shorter names, but we can make the new allocations to use shorter
names. If someone implements things before it is out as RFC, they
should be able to update their implementations too when the RFCs come
out. 

> As far as I know, the cost of making the KEXINIT messages longer is trivial
> and probably not even worth mentioning. If SSH wanted to optimize this to
> begin with, it would have gone with single-character names for most
> algorithms, omit the commas in algorithm lists when not necessary, etc. The
> original designers have, in my opinion correctly, decided that readability
> trumps conciseness, and that the savings of a few bytes in a message that’s
> exchanged once per connection, and then once per hour or per 1 GB of data, are
> not worth chasing.

The idea was that there is only one or two key exchange methods at
times, there was never supposed to be dozens of them. The encryption
algorithms, mac algorithms etc used much shorter names. And I do
remember people complaing that they do not want ot use @ssh.com etc
prefix, as it makes the names longer...

> From a performance perspective, the algorithms that involve DH group exchange
> are much costlier than negotiating the DH group in the KEXINIT packet, even if
> you were to enumerate many more groups than we are currently proposing. The
> group exchange methods involve not only sending two extra messages, which are
> hundreds of bytes themselves, but require an entire additional round-trip
> between the client and the server, adding noticeable latency to the
> establishment of the connection, or completion of key re-exchange.

There is no need to really negotiate DH group in the KEXINIT packet,
you need to agree on common one. For example IKEv2 uses a method,
where the initiator proposes all groups it will allow, and picks one
of them and sends KE payload for it. The responder will then either
accept the selected group if it acceptable for him. If it is not
acceptable for responder, it will send notification back, saying that
your group was not acceptable, but this group is, so then the
initiator retries with the same list of allowed groups, but different
group in KE payload.

This allows agreement of common group in case there is one, and also
most of the times both ends have same group allowed, thus the initial
selection is suitable for both ends too. This is how the DH group
agreement should have been done in secure shell too, but unfortunately
it was not done in this way, and now is too late to change that.

> Compared to the group exchange methods, negotiating the DH group in
> KEXINIT is downright efficient. And if you don’t want to use all of
> the groups, it is fairly straightforward to simply not include them.

If i remember right the secure shell DH group negotation sends the
full group information, and I think that is bad idea. Verifying the
group takes long time (full primatlity checks etc), thus you should
not accept random groups sent by other end. On the other hand if you
always require both ends to configure same set of groups to both ends
before they can be used, then you might as well give names for them.

Yes, I agree that using predefined groups is much better than using
groups sent inline the exchange. 

> Our SSH Server is going to include by default only
> diffie-hellman-group14-sha256 and diffie-hellman-group15-sha512. It is also
> going to be possible to enable diffie-hellman-group16-sha512, but it’s likely
> going to be disabled by default because it’s twice as costly as group 15 and
> exacerbates a denial of service vector for busy servers.

Ok, so you would like to define three. That would still be ok, and it
is better than the five there is now, but I still think two should be
enough.

> With respect to Curve25519, I think it’s nice and all, but it’s
> probably going to be the first thing broken by a quantum computer.
> Anyone concerned with forward secrecy should start using a hybrid
> key exchange method that incorporates a quantum-safe algorithm
> approximately now. It is that we should be focusing on, I think,
> instead of trying to put X25519 everywhere, cast in concrete. It’s
> going to bite us.

We are working on that in the IPsecME for the ESP. I.e., a way to make
ESP quantum computer resistant. I.e., the main goal is to make so that
even if you store all ESP traffic now, you cannot decrypt them when
you get the quantum computers, unless you also know the shared secret
between hosts.

Something like that might also work with secure shell, but situation
is bit different there, as in IKE/ESP both the client and server will
have connection related configuration, thus having one more
pairwise configurable thing there is not that hard, while in secure
shell it might be.
-- 
[email-masked]