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

From: "Mark D. Baushke" <[email-masked]>
Date: Wed, 5 Aug 2020 09:57:06 -0700

Hi,

Before IETF-108, I uploaded a new edition of

  Key Exchange (KEX) Method Updates and Recommendations for Secure Shell (SSH)
  https://datatracker.ietf.org/doc/draft-ietf-curdle-ssh-kex-sha2/

with the hope of

  a) Providing a survey of existing IANA Secure Shell (SSH) Protocol
     Parameters for Key Exchange Method Names
     https://www.iana.org/assignments/ssh-parameters/ssh-parameters.xhtml#ssh-parameters-16

  b) identifying a KEX to replace the current MUST implement exchanges:

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

  c) the desire to be deprecate any KEX which use sha1 as the secure hash:

       diffie-hellman-group-exchange-sha1
       diffie-hellman-group1-sha1
       diffie-hellman-group14-sha1
       gss-group1-sha1-*
       gss-group14-sha1-*
       gss-gex-sha1-*
       rsa1024-sha1

  d) A desire that the IANA KEX parameters contain another column in the
     table to indicate MUST, SHOULD, SHOULD NOT, MUST NOT, and MAY.

I have tried to indicate general guidance for the rest of the Method
Names, but many of the guidelines may be my personal opinion even though
I have tried to be objective throughout.

In my private copy, I have converted from v2 of the xmlrfc directives to
v3 and that will be part of the next revision.

I would very much like to hear any comments about the current draft.

	Be safe, stay healthy,
	-- Mark

---

From: Ron Frederick <[email-masked]>
Date: Sun, 16 Aug 2020 14:00:27 -0700

Hi Mark,

> I have tried to be objective throughout.

This generally looks good to me. Here are a few more detailed comments:

- Sections 3.14 and 3.15 list the ext-info values as SHOULD (which I agree with). However, your table in section 5 has them marked as MAY.

- I noticed you dropped diffie-hellman-group14-sha256 back from MUST to SHOULD, leaving no algorithms listed as MUST. I’d still like to see at least one algorithm be listed as MUST, and think this is probably the safest candidate for that.

- I’m also thinking diffie-hellman-group15-sha512 might be a good candidate for a SHOULD rather than a MAY, but I’m not sure we have consensus on that.

- I agree with the downgrade of diffie-hellman-group16-sha512 from SHOULD to MAY.

- Regarding possible ECDSA algorithms, I implemented the secp256k1 curve as ecdh-sha21.3.132.0.10 in AsyncSSH after seeing it was implemented by Bitvise. I don’t know if it is worth mentioning here explicitly, but it’s one real-world example of an ecdh-sha2-* algorithm not explicitly given a name in RFC 5656. The ‘endsa-sha2’ algorithm with this curve is also supported.
-- 
Ron Frederick
[email-masked]

---

From: "Mark D. Baushke" <[email-masked]>
Date: Mon, 17 Aug 2020 15:34:35 -0700

Ron Frederick <[email-masked]> writes:

> This generally looks good to me.

I am still going back over some of the comments that ekr provided...

> Here are a few more detailed comments:
> 
> - Sections 3.14 and 3.15 list the ext-info values as SHOULD (which I
>   agree with). However, your table in section 5 has them marked as
>   MAY.

Updated in my copy.

> - I noticed you dropped diffie-hellman-group14-sha256 back from MUST
>   to SHOULD, leaving no algorithms listed as MUST. I’d still like to
>   see at least one algorithm be listed as MUST, and think this is
>   probably the safest candidate for that.

How long is a 2048-bit prime, even with such a large q-ordered subgroup
likely to remain viable?

1024-bits for:

  a) IFC RSA, 
  b) FFC DSA, and 
  c) FFC DH,
  d) as well as FFC DH group5 (1536-bits)

are all considered too weak now.

3DES with 112-bits of security is being phased out as of January 1, 2024.

When should we expect to see 2048-bit RSA, which also nominally has only
112-bits of security as does 2048-bit DSA become retired?

To me, it looks like the better bet would be the 3072-bit MODP prime of
group15, but I do not see it being adopted by most implementations.

I might suggest Curve25519, as it is pretty fast and has many
implementations.

That said, there are many who have been doing research which seems to
show that ECC is easier to break with Quantum Crypto systems than FFC
and are NOT interested in implementating ANY ECC algorithms.

I believe I have seen some text from implementers who have said they
would NOT adopt ECC for their SSH implementations.

> - I’m also thinking diffie-hellman-group15-sha512 might be a good
>   candidate for a SHOULD rather than a MAY, but I’m not sure we have
>   consensus on that.

Yup, I have not seen any consensus on this issue as yet.

Perhaps we should opt to make diffie-hellman-group-exchange-sha256 a
MUST? This allows implementors to put in whatever MODP groups they wish
as long as q = (p-1)/2 ... so, a maximized q-ordered subgroup... though
I o worry a bit about the way that the generator g is created perhaps
not providing that g^q mod p == 1 is a will formed subgroup. When it is
not a well-formed subgroup, then it will be leaking the first bit of the
key value.

> - I agree with the downgrade of diffie-hellman-group16-sha512 from

Okay.

> - Regarding possible ECDSA algorithms, I implemented the secp256k1
>   curve as ecdh-sha21.3.132.0.10 in AsyncSSH after seeing it was

I think you mean ecdh-sha2-1.3.132.0.10 here?

>   implemented by Bitvise. I don’t know if it is worth mentioning here
>   explicitly, but it’s one real-world example of an ecdh-sha2-*
>   algorithm not explicitly given a name in RFC 5656. The ‘endsa-sha2’
>   algorithm with this curve is also supported.

The reserved name is for ecdh-sha2-* ... so ecdh-sha2-secp256k1 or
ecdh-sha2-1.3.132.0.10 or ecdh-sha2-oid-1.3.132.0.10 would be better...
depending on what Bitvise uses.

I think you might as well use the name, the Koblitz curve names are
present in RFC 4492.

    b'1.3.132.0.10': (ec.SECP256K1, SHA256),
    b'1.3.132.0.34': (ec.secp384r1, SHA384),
    b'1.3.132.0.35': (ec.secp521r1, SHA512),

For that matter, as long as you are going to use vanity curve for Bitcoin;

Why not use the RFC 7027 ECC Brainpool curves too?

    b'1.3.36.3.3.2.8.1.1.7':  (ec.brainpoolP256r1, SHA256),
    b'1.3.36.3.3.2.8.1.1.11': (ec.brainpoolP384r1, SHA384),
    b'1.3.36.3.3.2.8.1.1.13': (ec.brainpoolP512r1, SHA512),
  
That said, given that they are named in RFC 7027, using their names may
be better too.

Does anyone else want me to add either the Koblitz or Brainpool names or
OIDs to this IETF draft?

	Be safe, stay healthy,
	-- Mark

---

From: Ron Frederick <[email-masked]>
Date: Mon, 17 Aug 2020 22:42:40 -0700

> 112-bits of security as does 2048-bit DSA become retired?

I’m no expert when it comes to key strength, but I would expect a 2048-bit RSA key to last at least as long as 3DES, since both are considered to have 112 bits of security. The applies to DH keys as well. According to Wikipedia, RSA claimed back in 2003 that 2048-bit keys should be good until 2030, and even now the largest RSA key known to be cracked was a key with 829 bits. So, it seems like we’ve got another 5-10 years probably before we’d have to worry about phasing these keys out.

> group15, but I do not see it being adopted by most implementations.

As I noted below, I can definitely get behind this as a SHOULD, and perhaps that could position it to become a MUST later when it comes time to retire 2048-bit keys.

> I might suggest Curve25519, as it is pretty fast and has many

I’m definitely a big fan of curve25519/Ed25519, and indeed curve25519-sha256 is the most preferred key exchange algorithm in AsyncSSH right now. However, when it comes to choosing which algorithm to make a MUST, I figured that going with one of the plain DH algorithms might be less of a burden on implementers, as it’s much easier to change the key size than it would be to add ECC support to an implementation that doesn’t yet have it.

> would NOT adopt ECC for their SSH implementations.

That’s interesting - I hadn’t read that. I was aware of concerns about potential compromises in the nistp curves, but not specifically about Quantum attacks against ECC.

> not a well-formed subgroup, then it will be leaking the first bit of the

That’s an interesting thought. Are there “best practices” which could be followed in generating/validating  these values that could avoid such a weakness?

For now, my implementation of the “group-exchange” algorithms has been to only let them select from a table of previously generated groups (basically the same group14-18 values that can be named directly). I haven’t looked into what it would take to construct new MODP groups.

> I think you mean ecdh-sha2-1.3.132.0.10 here?

Whoops, yes. Looks like my cost/paste swallowed the preceding dash.

> depending on what Bitvise uses.

They use ecdh-sha2-1.3.132.0.10 and so do I, following the guidance in RFC 5656 section 6.3 which states:

   This section specifies identifiers encoding named elliptic curve
   domain parameters.  These identifiers are used in this document to
   identify the curve used in the SSH ECC public key format, the ECDSA
   signature blob, and the ECDH method name.

   For the REQUIRED elliptic curves nistp256, nistp384, and nistp521,
   the elliptic curve domain parameter identifiers are the strings
   "nistp256", "nistp384", and "nistp521".

   For all other elliptic curves, including all other NIST curves and
   all other RECOMMENDED curves, the elliptic curve domain parameter
   identifier is the ASCII period-separated decimal representation of
   the Abstract Syntax Notation One (ASN.1) [ASN1] Object Identifier
   (OID) of the named curve domain parameters that are associated with
   the server's ECC host keys.  This identifier is defined provided that
   the concatenation of the public key format identifier and the
   elliptic curve domain parameter identifier (or the method name and
   the elliptic curve domain parameter identifier) does not exceed the
   maximum specified by the SSH protocol architecture [RFC4251], namely
   64 characters; otherwise, the identifier for that curve is undefined,
   and the curve is not supported by this specification.

   A list of the REQUIRED and RECOMMENDED curves and their OIDs can be
   found in Section 10.

   Note that implementations MUST use the string identifiers for the
   three REQUIRED NIST curves, even when an OID exists for that curve.

So, with the exception of the REQUIRED curves, it looks like it would violate the RFC to use names even when they exist (e.g. ecdh-sha2-secp256k1). So, until there is a new SSH-specific RFC which updates RFC 5656, I think only OIDs should be used.

> Does anyone else want me to add either the Koblitz or Brainpool names or

My rule on adding new curves (and algorithms in general) is that I want at least one other independent implementation of that support that I can do interoperability testing against before I’ll consider adding something. For now, I’m not aware of any SSH implementations that support any other curves, but if anyone knows of any, I’d love a pointer to them.

As for adding new named curves to this draft, I would recommend you focus only on implementations currently out there and not introduce anything new. I like the fact that this draft focuses on being a catalog of existing algorithms in actual use, and recommendations for which ones should be prioritized. If someone wanted to recommend new curves, I think that should probably be its own separate draft, and it can then decide whether to recommend using the OID format required by RFC 5656 or updating it to introduce additional non-OID algorithm names.
-- 
Ron Frederick
[email-masked]

---

From: "Mark D. Baushke" <[email-masked]>
Date: Mon, 17 Aug 2020 23:37:33 -0700

Ron Frederick <[email-masked]> writes:

> On Aug 17, 2020, at 3:34 PM, Mark D. Baushke <[email-masked]<mailto:[email-masked]>> wrote:
> Ron Frederick <[email-masked]<mailto:[email-masked]>> writes:

MDB wrote:
> How long is a 2048-bit prime, even with such a large q-ordered
> subgroup likely to remain viable?
> 
> 1024-bits for:
> 
>  a) IFC RSA,
>  b) FFC DSA, and
>  c) FFC DH,

Ron wrote:
> I’m no expert when it comes to key strength, but I would expect a
> 2048-bit RSA key to last at least as long as 3DES, since both are
> considered to have 112 bits of security.

MDB: Note this is in NIST SP 800-131Ar2

URL: https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-131Ar2.pdf

Table 1.

    Three-key TDEA Encryption Deprecated through 2023
                              Disallowed after 2023

Ron wrote:
> The applies to DH keys as well. According to Wikipedia, RSA claimed
> back in 2003 that 2048-bit keys should be good until 2030, and even
> now the largest RSA key known to be cracked was a key with 829 bits.
> So, it seems like we’ve got another 5-10 years probably before we’d
> have to worry about phasing these keys out.
> 
> 
...elided...

Ron wrote:
> I’m definitely a big fan of curve25519/Ed25519, and indeed
> curve25519-sha256 is the most preferred key exchange algorithm in
> AsyncSSH right now. However, when it comes to choosing which algorithm
> to make a MUST, I figured that going with one of the plain DH
> algorithms might be less of a burden on implementers, as it’s much
> easier to change the key size than it would be to add ECC support to
> an implementation that doesn’t yet have it.

Ron wrote:
> That’s interesting - I hadn’t read that. I was aware of concerns about
> potential compromises in the nistp curves, but not specifically about
> Quantum attacks against ECC.

MDB:

I found the article. It was in Advances in Cryptology - ASIACRYPT 2017.

 Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms
 by Martin Roetteler, Michael Naehrig, Krysta M. Svore, and Kristin Lauter
 November 2017, 24 Pages

URL: 

https://www.microsoft.com/en-us/research/wp-content/uploads/2017/09/1706.06752.pdf

It compares ECC with RSA (IFC) rather than really comparing against FFC DSA.

...elided...

Ron wrote:
> That’s an interesting thought. Are there “best practices” which could
> be followed in generating/validating these values that could avoid
> such a weakness?
> 
> For now, my implementation of the “group-exchange” algorithms has been
> to only let them select from a table of previously generated groups
> (basically the same group14-18 values that can be named directly). I
> haven’t looked into what it would take to construct new MODP groups.

It is not a difficult program to write, I just find that RFC 4419 is not
very good at given instructions. Basically, after you have a candidate
generator g, you need to ensure that g^q mod P == 1, then you have a
generator able to generate a proper q-orded subgroup. This is different
than RFC 4419 which just suggests forcing a congruence to 2 or 5 in
section 6.1. This method works about one quarter of the time. The rest
of the time the g value does NOT generate a proper q-ordered subgroup.

There are faster ways to generate p,q,g set of non-safe prime DH
parameters than the method outlined in RFC 4419, but then you won't
maximize the q = (p-1)/2 for the largest possible q-ordered subgroup...
and as SSH does only sends g,p, the client needs to assume it can
generate q if it needs to make any FIPS tests to make governments
happy... which includes doing a g^q mod p == 1 to ensure that any x
generated is a q-ordered subgroup.

...elided...
> RFC 5656 section 6.3 which states:

MDB: Ah.. Yes, I forgot about that detail. Thank you or the pointer.

Ron wrote:
> My rule on adding new curves (and algorithms in general) is that I
> want at least one other independent implementation of that support
> that I can do interoperability testing against before I’ll consider
> adding something. For now, I’m not aware of any SSH implementations
> that support any other curves, but if anyone knows of any, I’d love a
> pointer to them.

MDB: Me too.

> As for adding new named curves to this draft, I would recommend you
> focus only on implementations currently out there and not introduce
> anything new. I like the fact that this draft focuses on being a
> catalog of existing algorithms in actual use, and recommendations for
> which ones should be prioritized. If someone wanted to recommend new
> curves, I think that should probably be its own separate draft, and it
> can then decide whether to recommend using the OID format required by
> RFC 5656 or updating it to introduce additional non-OID algorithm
> names.

MDB: Fair enough.

	Be safe, stay healthy,
	-- Mark

---

From: denis bider <[email-masked]>
Date: Tue, 18 Aug 2020 19:21:30 -0500

> Perhaps we should opt to make diffie-hellman-group-exchange-sha256
> a MUST? This allows implementors to put in whatever MODP groups
> they wish

I think this is unwise for reasons mentioned earlier: implementations
generate their own DH groups which fail FIPS tests and are incompatible
with FIPS implementations. In the interest of compatibility, FIPS
implementations then have to avoid this algorithm.

> To me, it looks like the better bet would be the 3072-bit MODP prime
> of group15, but I do not see it being adopted by most implementations.

The main problem here is that OpenSSH does not implement it. Last time I
checked, their stated reasoning was that 3072 bits was "too much
granularity". They like either 2048 or 4096. But on constrained devices,
4096 is super expensive.

I agree here that 3072-bit DH and RSA are a sweet spot for a fair amount of
future security with acceptable performance. If it was up to me with no
other considerations involved, I would declare this the conservative
"MUST". If everyone else decides this and declares it so, then perhaps
OpenSSH might reluctantly support it. However, it's also quite possible
they might not.

And even if they do, it's not CURRENTLY offered by any existing OpenSSH
version.

For now, I think we're left with either group14 as the only widely
acceptable MUST, or no MUST key exchange algorithm at all.

The NIST post-quantum crypto fest is also slowly unfolding, and we may have
a post-quantum standard in a few years. I think that will be the next major
event that changes the algorithm preference landscape, more so than great
classic progress in breaking larger RSA or DH. If there is surprising
progress in breaking RSA or DH, chances are it will be quantum rather than
classic, in which case the new standard will need to be the winner of the
post-quantum contest, which we currently don't have.

denis

On Mon, Aug 17, 2020 at 5:34 PM Mark D. Baushke <mdb=
[email-masked]> wrote:

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

---

From: denis bider <[email-masked]>
Date: Tue, 18 Aug 2020 21:01:20 -0500

About ECDH/secp256k1:

> The reserved name is for ecdh-sha2-* ... so ecdh-sha2-secp256k1
> or ecdh-sha2-1.3.132.0.10 or ecdh-sha2-oid-1.3.132.0.10 would be
> better... depending on what Bitvise uses.

RFC 5656 is clear about this and provides an example:

https://tools.ietf.org/html/rfc5656#section-6.3

"For example, the method name for ECDH key exchange with ephemeral
generated on the sect409k1 curve is "ecdh-sha2-1.3.132.0.36"."

secp256k1 is not among the curves explicitly named in RFC 5656, therefore
it uses the OID form (unfortunately).

Bitvise SSH Server, SSH Client and FlowSsh (the library) use the following
for ECDSA and ECDH over secp256k1:

ecdsa-sha2-1.3.132.0.10
ecdh-sha2-1.3.132.0.10

I'm not sure if ECDH over secp256k1 needs to be mentioned in the draft. If
so, the reason would be to acknowledge its practical usage. In this case,
the disposition should be "MAY" and there ought to be some remark to
indicate this is secp256k1.

> Does anyone else want me to add either the Koblitz or Brainpool
> names or OIDs to this IETF draft?

In theory, we could add all the possible curves that have OID assignments.
I would not add them unless there exist practical implementations that are
in use.

denis

---

From: Ron Frederick <[email-masked]>
Date: Wed, 19 Aug 2020 19:42:03 -0700

On Aug 17, 2020, at 11:37 PM, Mark D. Baushke <[email-masked]> wrote:
> URL: https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-131Ar2.pdf <https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-131Ar2.pdf>
> Table 1.
> 

[Ron] Thanks for the pointer. I was familiar with an earlier version of that doc, but didn’t know there was a 2019 update. The deprecation of TDEA seems to be a special case, though, and not something which it is applying to all algorithms with 112 bits of security. For the others, it still seems to be sticking by the previous recommendation that 112 bits will be ok until 2030. For DH in particular, we don’t need to worry about the lifetime of the “protected data”, as the session keys negotiated by the SSH key exchange typically don’t last very long. The main issue for DH seems to be whether it complies with SP 800-56A or not (https://doi.org/10.6028/NIST.SP.800-56Ar3 <https://doi.org/10.6028/NIST.SP.800-56Ar3>), and I think we’re ok on that here, at least for the predefined safe primes.

> https://www.microsoft.com/en-us/research/wp-content/uploads/2017/09/1706.06752.pdf <https://www.microsoft.com/en-us/research/wp-content/uploads/2017/09/1706.06752.pdf>

[Ron] Thanks - I’ll check it out!
-- 
Ron Frederick
[email-masked]

---

From: Hubert Kario <[email-masked]>
Date: Wed, 26 Aug 2020 13:36:00 +0200

On Tuesday, 18 August 2020 07:42:40 CEST, Ron Frederick wrote:
>> Ron Frederick <[email-masked]> writes: ...
> That’s interesting - I hadn’t read that. I was aware of 
> concerns about potential compromises in the nistp curves, but 
> not specifically about Quantum attacks against ECC.

basically it boils down to the size of the field, with 256 bit field you
need 384 qbit QC, with 2048 bit field you need 3072 qbit QC to break it

so ECC will be broken before RSA/DH/DSA of similar classical level of 
security

the open question is how much time RSA/DH will have over ECC

> That’s an interesting thought. Are there “best practices” which 
> could be followed in generating/validating  these values that 
> could avoid such a weakness?

if the p is a safe prime, then "a bad" generator can leak one bit of the 
private
key, but it can leak at most one bit of private key; you can guess that bit
with a 50% chance of being right anyway, that does not translate to an 
attack

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