Subject: Re: [Curdle] Looking for comments on draft-ietf-curdle-ssh-kex-sha2

From: "Mark D. Baushke" <[email-masked]>
Date: Mon, 23 Nov 2020 13:54:17 -0800

Hi Folks,

I have uploaded draft-ietf-curdle-ssh-kex-sha2-12 which is a large
rewrite of the text to adress the structural comments made by Eric
Rescorla.

It is probably best to review the document from scratch to see if the
flow and issues with older crypto primitives (sha-1) lead to the
conclusions being drawn.

There may not yet be full agreement about the summary guidance for Key
Exchange Method Names.

The diffie-hellman-group1-sha1 exchange was a mandatory to implement and
is now a SHOULD NOT. I could move it to MUST NOT if everyone else thinks
it best.

The diffie-hellman-group14-sha1 exchange was a mandatory to implement
MUST and is now a SHOULD. Similarly for gss-group1-sha1-*

The rsa1024-sha1 exchange is now a MUST NOT.

I have suggested that diffie-hellman-group14-sha256 be a MUST (mandatory
to implement).

A plurality of the list seemed to be in favor of this, but if 2048-bit
(112 bits of security) is falling out of favor (along with 3DES), then
perhaps a different KeX is desirable to be MUST.

	Be safe, stay healthy,
	-- Mark

---

From: Hubert Kario <[email-masked]>
Date: Wed, 25 Nov 2020 13:53:11 +0100

> is now a SHOULD NOT. I could move it to MUST NOT if everyone else thinks

+1 for a MUST NOT, though I'm ok with keeping it at SHOULD NOT

people that need it for interoperability, will use it irrespective of what
RFC says, but new deployments should require the user to jump through
at least one hoop to make it work

> MUST and is now a SHOULD. Similarly for gss-group1-sha1-*

no, I think it should be SHOULD NOT, the sha-1 disqualifies it

> perhaps a different KeX is desirable to be MUST.

while small security margin of 3DES is a factor for its deprecation, the 
most
problematic part of 3DES is the 64 bit block size

and AFAIK, we're not even considering deprecation of 2048 bit RSA in the 
web
PKIX, so, I don't see any arguments against making group14 mandatory

-- 
Regards,
Hubert Kario
Senior Quality Engineer, QE BaseOS Security team
Web: www.cz.redhat.com
Red Hat Czech s.r.o., Purkyňova 115, 612 00  Brno, Czech Republic

---

From: "Mark D. Baushke" <[email-masked]>
Date: Wed, 25 Nov 2020 09:16:37 -0800

> +1 for a MUST NOT, though I'm ok with keeping it at SHOULD NOT

Good. Personally, I favor MUST NOT, but I was being conservative in how
fast something goes from a MUST to a MUST NOT.

> > MUST and is now a SHOULD. Similarly for gss-group1-sha1-*

Minor typo here. I intended 'gss-group14-sha1-*' which shadows the
non-gss name.

> no, I think it should be SHOULD NOT, the sha-1 disqualifies it

Okay. I hope others provide their inputs on this one. I have no issues
with making it a SHOULD NOT if that is desirable by others on the list.

> while small security margin of 3DES is a factor for its deprecation,
> the most problematic part of 3DES is the 64 bit block size

Yes.

> and AFAIK, we're not even considering deprecation of 2048 bit RSA in
> the web PKIX, so, I don't see any arguments against making group14
> mandatory

Good points. Thank you.

	Be safe, stay healthy,
	-- Mark

---

From: Tero Kivinen <[email-masked]>
Date: Thu, 26 Nov 2020 19:09:41 +0200

> no, I think it should be SHOULD NOT, the sha-1 disqualifies it

If I remember right about ssh key exchange, it does not rely on the
collision resistance at all, it relies on the 2nd preimage resistance,
i.e., for attacker to be able to attack ssh key exchange it needs to
get the signature generated by the server using random data created by
the server, and find out inputs to hash function that generates
exactly same hash than what server used to sign the exchange.

As on of the inputs is the server's diffie-hellman public key and the
final resultant secret, the attacker do not know these before server
replies, and thus it needs to do this attack in real time during the
connection establishment phase.

For such use cases sha-1 should be completely acceptable. The
group1-sha1 uses only 1024 bit diffie-hellman, and thats why it is
marked as SHOULD NOT. The group14-sha1 uses 2048 bit diffie-hellman
which is still considered acceptable for some uses. I.e., if you are
just protecting real time shell access to machine 2048 bits should be
enough, but it is not acceptable when transmitting data which needs to
keep secure for tens of years.

Actually the draft already explains this:
----------------------------------------------------------------------
   The SHA-1 hash is in the process of being deprecated for many
   reasons.  There have been attacks against SHA-1 that have shown there
   are weaknesses in the algorithm.  Therefore, it is desirable to move
   away from using it before attacks become more serious.

   At present, the attacks against SHA-1 are collision attacks that rely
   on human help rather than a pre-image attack.  So, it is still
   possible to allow time backward compatibility use of SHA-1 during a
   SSH key-exchange for a transition to stronger hashing.  However, any
   such key exchanges should be listed last in the preference list.
-- 
[email-masked]

---

From: Hubert Kario <[email-masked]>
Date: Thu, 26 Nov 2020 18:26:10 +0100

> collision resistance at all, it relies on the 2nd preimage resistance,

I don't think this is the case:
https://hal.inria.fr/hal-01244855/document

---

From: "Mark D. Baushke" <[email-masked]>
Date: Thu, 26 Nov 2020 11:07:29 -0800

Hi Tero & Hubert,

Hubert does raise an interesting point regarding Transcript Collision
attacks using SHA-1 to perform a downgrade attack on the selection of
weak symmetric ciphers being negotiated during the key exchange.

The pre-conditions of the Transcript Collision Attack depend on public
key reuse as is found on page 13 "C. Downgrading SSH-2 to Weak
Ciphersuites with a Chosen-Prefix Transcript Collision" of the paper.

I could add this informative reference:

    Karthikeyan Bhargavan, Gaeutan Leurent. Transcript Collision Attacks:
    Breaking Authentication in TLS, IKE, and SSH. Network and Distributed
    System Security Symposium -- NDSS 2016, Feb 2016, San Diego, United
    States. 10.14722/ndss.2016.23418 . hal-01244855
    URL: https://hal.inria.fr/hal-01244855/document

to the informative section of the RFC and try to add additional
theoretical justification against SHA-1, is this really necessary?

The paper does show that the group exchange (RFC4419) use of *-sha1 may
be somewhat easier to attack than the fixed group, but I have already
listed that as 'SHOULD NOT' in my -12 draft.

The real question here is if "SHOULD NOT" is the correct implementation
guidance for all use of diffie-hellman-group14-sha1 in key exchanges
which is a big jump from "MUST" right now. All of the other *-sha1
exchanges in the draft are listed as "SHOULD NOT" already.

Even so, I am already suggesting that any *-sha1 kex be listed last in
the negotation list if it appears at all.

I do not actually have a table which compares the current state of the
RFC enumerated key exchanges with the suggestions in this draft.

The '-' in the table below indicates that the RFC did not actually say
if the new key exchanges were a MUST, SHOULD, or MAY. I am considering
them to all be "MAY" ...

I am happy to reconsider if any of the implementation guidance should be
modified as this list is somewhat subjective to my own views based on
the criteria I address in the draft and also looking at algorithms
deployed by a number of the common SSH implementations.

Obviously, if an implementation does not support ECC, I would not expect
ECDH or Curve* to be present. Similarly, an implementation without
GSS-API support will be missing the gss* exchanges.

 Key Exchange Method Name             | Reference | Was       | Implement

 curve25519-sha256                    | RFC8731   | -         | SHOULD
 curve448-sha512                      | RFC8731   | -         | MAY
 diffie-hellman-group-exchange-sha1   | RFC4419   | -         | SHOULD NOT
 diffie-hellman-group-exchange-sha256 | RFC4419   | -         | MAY
 diffie-hellman-group1-sha1           | RFC4253   | MUST      | SHOULD NOT
 diffie-hellman-group14-sha1          | RFC4253   | MUST      | SHOULD
 diffie-hellman-group14-sha256        | RFC8268   | -         | MUST
 diffie-hellman-group15-sha512        | RFC8268   | -         | MAY
 diffie-hellman-group16-sha512        | RFC8268   | -         | SHOULD
 diffie-hellman-group17-sha512        | RFC8268   | -         | MAY
 diffie-hellman-group18-sha512        | RFC8268   | -         | MAY
 ecdh-sha2-*                          | RFC5656   | MAY       | MAY
 ecdh-sha2-nistp256                   | RFC5656   | MUST      | SHOULD
 ecdh-sha2-nistp384                   | RFC5656   | MUST      | SHOULD
 ecdh-sha2-nistp521                   | RFC5656   | MUST      | SHOULD
 ecmqv-sha2                           | RFC5656   | MAY       | MAY
 ext-info-c                           | RFC8308   | SHOULD    | SHOULD
 ext-info-s                           | RFC8308   | SHOULD    | SHOULD
 gss-*                                | RFC4462   | -         | MAY
 gss-curve25519-sha256-*              | RFC8732   | SHOULD    | SHOULD
 gss-curve448-sha512-*                | RFC8732   | MAY       | MAY
 gss-gex-sha1-*                       | RFC4462   | -         | SHOULD NOT
 gss-group1-sha1-*                    | RFC4462   | -         | SHOULD NOT
 gss-group14-sha256-*                 | RFC8732   | SHOULD    | SHOULD
 gss-group15-sha512-*                 | RFC8732   | MAY       | MAY
 gss-group16-sha512-*                 | RFC8732   | SHOULD    | SHOULD
 gss-group17-sha512-*                 | RFC8732   | MAY       | MAY
 gss-group18-sha512-*                 | RFC8732   | MAY       | MAY
 gss-nistp256-sha256-*                | RFC8732   | SHOULD    | SHOULD
 gss-nistp384-sha384-*                | RFC8732   | MAY       | SHOULD
 gss-nistp521-sha512-*                | RFC8732   | MAY       | MAY
 rsa1024-sha1                         | RFC4432   | -         | MUST NOT
 rsa2048-sha256                       | RFC4432   | -         | MAY

Thank you for your continued comments to improve this draft.

	Be safe, stay healthy,
	-- Mark

PS: It has already been noted that the draft actually updates more than
just RFC 4250. So, the next revision will mention that it updates="4250
4253 4432 4462"

---

From: Tero Kivinen <[email-masked]>
Date: Thu, 26 Nov 2020 22:21:28 +0200

>From that paper:
----------------------------------------------------------------------
	In this attack, the MitM does not tamper
	with the Diffie-Hellman values and hence it does not
	know the connection keys. However, it manages to
	tamper with both Ic and Is , and can therefore down-
	grade the negotiate ciphersuite to a weak cryptographic
	algorithm that the attacker knows how to break.
----------------------------------------------------------------------

So simple answer, do not allow weak ciphers in your policy, as
attacker might do really hard attack to force you to use them:

----------------------------------------------------------------------
	Implementing the target collision for SSH-2 requires
	a chosen-prefix attack on SHA-1 which is still consid-
	ered impractical (at least 2^77 work). Moreover, since the
	two tampered fields Ic and Is are meant to be strings
	(not bitstrings), we cannot use arbitrary collisions. Still,
	we find this attack to be an interesting illustration of
	the use of transcipt collisions for downgrade attacks.
-- 
[email-masked]

---

From: Tero Kivinen <[email-masked]>
Date: Thu, 26 Nov 2020 22:46:12 +0200

> theoretical justification against SHA-1, is this really necessary?

I think it would be good idea to add that reference, even when it do
consider that attack against ssh impractical with 2^77 work, but it do
warn about not including weak ciphers in the list, and warn about the
group exchange. 

> listed that as 'SHOULD NOT' in my -12 draft.

This could refer to this same paper.

> exchanges in the draft are listed as "SHOULD NOT" already.

I think it can still be SHOULD, just to keep backward compatibility
with old devices. It does not need to be enabled by policy in default
configuration, but sometimes you need to connect those devices, and it
is painful if you need to find old version of some ssh client just to
be able to connect to them.
-- 
[email-masked]

---

From: Hubert Kario <[email-masked]>
Date: Fri, 27 Nov 2020 13:34:49 +0100

On Thursday, 26 November 2020 21:46:12 CET, Tero Kivinen wrote:
>>     States. 10.14722/ndss.2016.23418 . hal-01244855 ...
>

SHA-1 resistance against 2nd preimage is still at 160 bits, but as SSH 
doesn't
depend on that, but rather on chosen prefix resistance, that's a 
significant
mind-shift

also, 2^77 work is similar to attacking 1024 bit DH or 1024 RSA, and I 
don't
think we have any arguments against deprecating those; besides,
"impractical" != "safe", for "safe" we generally require a work factor of 
2^128