Subject: Re: draft-baushke-ssh-dh-group-sha2-01 (was Re: DH group exchange)

From: "Mark D. Baushke" <[email-masked]>
Date: Sat, 13 Feb 2016 14:26:44 -0800

Hi denis & Niels,

You have both made good points. I have adopted the updated text from
denis and tried provide a meaning for the Note column. I have also added
a pointer to the Simon's ssh-curves draft and included both of the
currently published curve names in the table in this draft.

https://datatracker.ietf.org/doc/draft-baushke-ssh-dh-group-sha2/

Please let me know of additional comments.

	-- Mark

---

From: denis bider <[email-masked]>
Date: Sat, 13 Feb 2016 17:49:04 +0000

Comments:

- If we're being comprehensive, we should include a position with regard to Curve25519 and Curve448:

https://tools.ietf.org/html/draft-josefsson-ssh-curves-03

I suggest we take the following positions:

curve25519-sha256    SHOULD
curve448-sha256      SHOULD, or MAY?

That being said:

- Given the recent NSA recommendations, it seems to me it would be prudent to update the Curve25519/Curve448 draft, and to replace the SHA-256 algorithm with SHA-512 for Curve448. This would create the method "curve448-sha512" instead of "curve448-sha256".

Simon, what do you think? Could your draft be updated to do that?

It seems to me that this would meet the NSA's long-term guidelines, whereas curve448-sha256 doesn't.

- As Niels points out - now that the modifiers are SHOULD / MAY / ..., we ought to specify the verb this refers to. I would be more comfortable assuming that our target audience are developers, and that these modifiers refer to "implement". I'm less comfortable reaching out to end users, dispensing advice about deployed configurations - but I'm not firmly against it.

- If we're going to have text saying SHA-1 is begrudgingly acceptable for backwards compatibility, we can't simultaneously say that it is "NOT SECURE" in all caps. Conversely - if we do say it is "NOT SECURE", we can't have a graceful transition away from SHA-1. We must in that case pursue an aggressive transition, including condemnation of existing products that use it.

It seems to me we don't have reason enough to be that aggressive. If someone asks why SHA-1 is not currently secure for key exchange, we can't point to a document saying "here's how to break diffie-hellman-group14-sha1". What we have is concerns that such attacks might exist in the future, given weaknesses known today.

Bottom line - I think the following is fine:

"The SHA-1 [algorithm] SHOULD NOT be used. If it is used, it should only be provided for backwards compatibility[,] should not be used in new designs[,] and should be phased out of existing key exchanges as quickly as possible"

But it's not currently accurate to say:

"... because it is NOT SECURE."

It may instead be accurate to say:

"... because of its known weaknesses."

- Niels has suggested that it's onerous to have so many "MUST" curves. We've already reduced the number of MUST curves from three (in RFC 5656) to two (in this draft). I'm not sure that either nistp384 or nistp521 are suitable candidates for demotion. However, if we make changes here, it seems we should keep nistp384 as MUST, and demote nistp521 to SHOULD. This is due to that nistp384 meets current longest-term guidelines; whereas nistp521 seems to be overkill, and slower.

----- Original Message -----
From: Mark D. Baushke
Sent: Friday, February 12, 2016 11:48
To: denis bider
Cc: Peter Gutmann ; [email-masked]
Subject: Re: draft-baushke-ssh-dh-group-sha2-01 (was Re: DH group exchange)

Hi denis,

You have made some good points. I have updated my draft to -02 and it is
in the process of being uploaded to the ietf servers.

For now, you can see the latest edition here:

I think I have the normative vs informative references in their proper
locations, please let me know of any nits that still need to be
addressed.

-- Mark

---

From: denis bider <[email-masked]>
Date: Sat, 13 Feb 2016 17:59:24 +0000

On further consideration, it seems to me that:

- to be consistent, "curve25519-sha256" should actually be in status MAY

- "curve448-sha512" is the strongest key exchange method we can offer right now, and is probably preferable to nistp384. I would make this one a "MUST" if it wasn't for (1) the long-term problem of FIPS certification, and (2) the short-term problem of no one implementing it right now.

Therefore, I suggest the following:

curve25519-sha256    MAY
curve448-sha512      SHOULD

Assuming Simon agrees to alter his spec, and specify curve448-sha512.

denis bider <[email-masked]> , 2/13/2016 4:44 PM:
Comments:

curve25519-sha256    SHOULD

That being said:

----- Original Message -----
From: Mark D. Baushke
Sent: Friday, February 12, 2016 11:48
To: denis bider
Cc: Peter Gutmann ; [email-masked]
Subject: Re: draft-baushke-ssh-dh-group-sha2-01 (was Re: DH group exchange)

Hi denis,

-- Mark

---

From: Peter Gutmann <[email-masked]>
Date: Sun, 14 Feb 2016 08:36:00 +0000

denis bider <[email-masked]> writes:

>It seems to me we don't have reason enough to be that aggressive. If someone
>asks why SHA-1 is not currently secure for key exchange, we can't point to a
>document saying "here's how to break diffie-hellman-group14-sha1". 

We can however point to mass-market, mainstream products, and mainstream
industry groups (e.g. the CAB Forum), that have banned SHA-1 outright:

  Effective 1 January 2016, CAs MUST NOT issue any new Subscriber certificates
  or Subordinate CA certificates using the SHA-1 hash algorithm.

Go to a site using SHA-1 right now with Chrome or Firefox and you'll get an
indicator that the connection is untrusted, i.e. it'll be treated worse than
if it wasn't encrypted at all (which is pretty stoopid, but that's a different
issue).  MSIE will also start doing this in a couple of months, if they don't
move the date up yet again.

For crypto as most people experience it, use of SHA-1 will be flagged as
insecure, or (for CA use) banned outright.  So we have a pretty good precedent
for warning about SHA-1:

  In line with widespread industry practice that deprecates SHA-1 as insecure
  from January 2016, the SHA-1 [algorithm] SHOULD NOT be used. If it is used,
  it should only be provided for backwards compatibility[,] should not be used
  in new designs[,] and should be phased out of existing key exchanges as
  quickly as possible. Since SHA-1 is being actively phased out, anyone
  continuing to use it should expect increasing problems in its use, for
  example public CAs will no longer issue certificates using SHA-1.

I think that's a fair warning to people of what's in store for SHA-1, so no-
one can say they weren't warned.

Peter.

---

From: Damien Miller <[email-masked]>
Date: Mon, 15 Feb 2016 19:00:54 +1100 (AEDT)

> Please let me know of additional comments.

IMO curve25519-sha256 should be a MUST, if not immediately then soon.
It's already supported under the [email-masked] alias by
a few implementations.

This paragraph:

>  The group15, group16, group17, and group18 names are the same as
>  those specified in [RFC3526] as 3072-bit MODP Group 14, 4096-bit MODP
>  Group 15, 6144-bit MODP Group 17, and 8192-bit MODP Group 18.

is incorrect: group 14 is 2048 bits, not 3072. Group 15 is 3072 bits,
not 4096. Group 16's length is not described (4096 bits). 17 and 18 are
correct.

I think the table of "Group modulus security strength estimates" should
have a reference - are these from NIST SP800-57?

-d

---

From: "Mark D. Baushke" <[email-masked]>
Date: Mon, 15 Feb 2016 01:36:15 -0800

> It's already supported under the [email-masked] alias by

Good point. I have moved curve25519-sha256 to MUST.

> not 4096. Group 16's length is not described (4096 bits). 17 and 18 are

Thank you for reporting this. I have updated the text in my copy and
removed group15 and group17 from the list.

I have submitted the new edition to 
https://datatracker.ietf.org/doc/draft-baushke-ssh-dh-group-sha2/
it should propagate shortly.

> have a reference - are these from NIST SP800-57?

Actually, I do mention that I got the information from RFC3526,
but I will make that more explicit and also point to RFC3766
for making the security strength calculation in person.

	Thank you,
	-- Mark

---

From: [email-masked] (Niels Möller)
Date: Mon, 15 Feb 2016 16:40:48 +0100

> currently published curve names in the table in this draft.

Thanks.

> https://datatracker.ietf.org/doc/draft-baushke-ssh-dh-group-sha2/

I'm looking at the -04 version where curve25519 is upgraded to MUST. I
think it looks quite good.

If at all possible, I think it would be desirable to

1. Limit the number of REQUIRED/MUST key exchange algorithms to one (1).
   I think curve25519 (if people agree it's mature enough) or group16
   are reasonable choices. I.e., demote ecdh-sha2-nistp384 to SHOULD or
   MAY.

2. Make it possible for a conforming implementation to support only one
   of sha256 and sha512. If we make anything using sha512 REQUIRED, I
   think we should avoid to make sha256 REQUIRED too. And vice versa.

   I don't think I follow the argument in favor of sha512, but using
   sha512 for all REQUIRED methods is nevertheless better than a mix.

   According to the table, group 16 has an estimated security strength
   of 240 bits. As argued before, I don't think birthday-paradox is
   relevant as the hash function is used. Hence, if sha256 is used
   together with group16, sha256 seems good enough for the foreseeable
   future, and in addition, unlikely to be the weakest link.

Finally, about the motivation in Sec 1, "[MFQ-U-OO-815099-15] suggesting
that the use of ECDH using the nistp256 curve and SHA-2 based hashes
less than SHA2-384 are no longer sufficient for transport of Top Secret
information."

On one hand, I don't think government requirements are that relevant for
selecting the REQUIRED algorithm(s). It's motivated to have at least one
SHOULD algorithm approved for US government use. But any organization
handling "Top Secret information" is free to configure its ssh software
any way it pleases, including disabling use of some REQUIRED algorithms.

And "if you don't implement this algorithm, you may not interoperate
with certain US government computer systems" is the kind of warning that
I think is perfectly appropriate if an implementation decides to omit
support for some algorithm with status SHOULD.

But on the other hand, if you interpret the NSA statement as saying "we
know a *lot* more about breaking sha256 than you do", than that could be
a very good reason to avoid sha256. I can't say how credible that
interpretation is.

> Please let me know of additional comments.

In short, no strong objections, but I'd prefer if the selection of
REQUIRED algorithm(s) were even more restrictive.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.

---

From: "Mark D. Baushke" <[email-masked]>
Date: Mon, 15 Feb 2016 09:13:52 -0800

Ni Niels,

>    are reasonable choices. I.e., demote ecdh-sha2-nistp384 to SHOULD or

I am willing to consider a move of ecdh-sha2-nistp384 to SHOULD.
This would mean only one Elliptic Curve (curve25519-sha256) is a MUST.

For ecdh-sha2-nistp384, the downside of this is that OpenSSL library has
no tuning or constant-time multiplication optimizations for the
NIST-P384 curve. It is not clear to me if anyone is going to try to
improve this situation. So, this means that ecdh-sha2-nistp384 may be
open to side-channel attacks right now for those using the OpenSSL
implementation.

If it were defined, I might be interested in moving to curve448-sha512
as the single MUST algorithm, with the understanding that a lot of the
other algorithms that are listed will continue to live for a time
anyway.

That said, is it desirable to also make one of the MODP Diffie-Hellman
groups also be a MUST? 

Perhaps the selection of diffie-hellman-group18-sha512 which has a
security strength estimate of ~190 bits as compared to curve448 which has a
security strength estimate of ~224 bits of security (per RFC7748).

>    sha512 for all REQUIRED methods is nevertheless better than a mix.

I am not sure I follow this line of reasoning. I have seen most
libraries that implement one of the SHA2 family of functions tends to
have an implementation for all members of the family.

>    future, and in addition, unlikely to be the weakest link.

Sure, I tend to think that the weakest element will be the source of
entropy in the system. 

This does not mean that I understand all of the attacks against hashing.
(For example, I still do not understand why BLAKE2 did not win the SHA3
competition. Although, I do admit that I find the SHA3 XOF functions to
be fascinating.)

The key here is the phrase 'foreseeable future' and for that I want to
be a bit more forward-looking and would very much like to see SHA2-512
if there is a negative bias in other publications for SHA2-256 still
being used as a cryptographic primitive.

Many processor families even have some chips with hardware acceleration
for SHA2-256 (e.g., Arm, Intel, Octeon).

> REQUIRED algorithm(s) were even more restrictive.

Okay, I can understand this.

	-- Mark

---

From: [email-masked] (Niels Möller)
Date: Mon, 15 Feb 2016 19:51:55 +0100

> That said, is it desirable to also make one of the MODP Diffie-Hellman

Not sure. But *if* we decide on two REQUIRED curves, I think it makes
sense to let one of them be a modp curve.

>>    of sha256 and sha512.

> have an implementation for all members of the family.

The concern is more about binary size than source code. If you want a
compliant ssh implementation inside your toaster or sensor node, with
only a poor microcontroller inside. Then everything you can cut away
helps. If we don't care about formal compliance for such devices, this
argument becomes weaker.

> being used as a cryptographic primitive.

My understanding is that a secure hash algorithm with 256 bits output
is a very strong primitive. If there's a problem with sha256, it isn't the
too short digest size (might be in other applications, where the
attacker can win by finding arbitrary collisions, with "only" 128 bit
difficulty), but structural problems which allows the attacker to take
short cuts. And the likelyhood of that is hard to put a number on.

I'm not strongly opposed to sha512. If we go for it, I think it's
preferable to not have any sha256 with status MUST. And as someone else
mentioned, if we believe eddsa25519 is going to be widely used, then
it's an advantage to use sha512 in the key exchange too, to be able to
cut away sha256 in the constrained implementation.

Regards,
/Niels

---

From: denis bider <[email-masked]>
Date: Mon, 15 Feb 2016 08:51:51 +0000

It looks like we were writing at about the same time. :-)

Yes, I agree with the below.

With regard to speed - in implementations available to me (Windows CNG and Crypto++), nistp384 appears to be faster than nistp521. I can't testify to how optimized they are.

Damien Miller <[email-masked]> , 2/15/2016 8:33 AM:
On Sat, 13 Feb 2016, denis bider wrote: 
 
> - Given the recent NSA recommendations, it seems to me it would be prudent 
> to update the Curve25519/Curve448 draft, and to replace the SHA-256 
> algorithm with SHA-512 for Curve448. This would create the method 
> "curve448-sha512" instead of "curve448-sha256". 
>  
 
I agree that curve448-sha512 is preferable to curve448-sha256, but 
not for this reason. The NSA's guidance is IMO confused, betting that 
quantum computers hit some goldilocks zone of "big/fast enough to break 
DLP for ~256 bit EC groups" but "too small/slow for 384 bit groups" 
because they've been caught flatfooted by QC developments and don't have 
real QC-resistant replacements ready yet (not that anyone would trust them 
if they came from the NSA anwyay). 
 
IMO a better justification is: curve448 is a backup against as-yet-unknown 
attacks on curve25519. Since we're not likely to need it, we might as well 
pair it with SHA512 as a backup against as-yet-unknown attacks on SHA256. 
 
Implementors who support ssh-ed25519 will need to carry SHA512 code around 
anyway, so the incremental code cost is trivial. The speed cost of a SHA512 
hash instead of a SHA256 hash is minuscule. 
 
> - If we're going to have text saying SHA-1 is begrudgingly acceptable for 
> backwards compatibility, we can't simultaneously say that it is "NOT SECURE" 
> in all caps. Conversely - if we do say it is "NOT SECURE", we can't have a 
> graceful transition away from SHA-1. We must in that case pursue an 
> aggressive transition, including condemnation of existing products that use 
> it. 
 
I agree: saying SHA1 is "NOT SECURE" here is overdoing it a little. The 
justification for abandoning SHA-1 on signatures is that these have a 
relatively long lifetime during which they can be attacked - O(year). 
Key exchange hashes have a much smaller temporal window for attack - 
only as long as an implementation is willing to accept a client that 
doesn't reply before NEWKEYS - O(minutes). 
 
> - Niels has suggested that it's onerous to have so many "MUST" curves. We've 
> already reduced the number of MUST curves from three (in RFC 5656) to two 
> (in this draft). I'm not sure that either nistp384 or nistp521 are suitable 
> candidates for demotion. However, if we make changes here, it seems we 
> should keep nistp384 as MUST, and demote nistp521 to SHOULD. This is due to 
> that nistp384 meets current longest-term guidelines; whereas nistp521 seems 
> to be overkill, and slower. 
 
AFAIK nistp521 is quite a bit faster than nistp384 in practice (OpenSSL) 
because it's been optimised. ~nobody uses nistp384, so it hasn't. 
 
$ openssl speed ecdh 
[...] 
Doing 256 bit  ecdh's for 10s: 45769 256-bit ECDH ops in 9.98s 
Doing 384 bit  ecdh's for 10s: 10505 384-bit ECDH ops in 9.98s 
Doing 521 bit  ecdh's for 10s: 13095 521-bit ECDH ops in 9.98 
 
-d

---

From: Damien Miller <[email-masked]>
Date: Mon, 15 Feb 2016 19:33:40 +1100 (AEDT)

$ openssl speed ecdh
[...]

-d

---

From: Simon Josefsson <[email-masked]>
Date: Thu, 25 Feb 2016 13:30:25 +0100

denis bider <[email-masked]> writes:

> - Given the recent NSA recommendations, it seems to me it would be
> prudent to update the Curve25519/Curve448 draft, and to replace the
> SHA-256 algorithm with SHA-512 for Curve448. This would create the
> method "curve448-sha512" instead of "curve448-sha256".
>

Yes, that will be part of -04.  For what's it worth: I support
curve25519-sha256 as MUST and curve448-sha512 as MAY in
draft-baushke-ssh-dh-group-sha2.

/Simon