Subject: Re: SSH key algorithm updates

From: Damien Miller <[email-masked]>
Date: Tue, 3 Nov 2015 10:21:41 +1100 (AEDT)

On Sat, 31 Oct 2015, Mark D. Baushke wrote:

> > That's an unfinished, -00 version internet draft from CFRG.  It's
> > probably too soon to use it as the basis for an SSH public key algorithm
> > at all, let alone make such an algorithm mandatory to implement.  Once
> > the document is ready, we can start with OPTIONAL, and consider
> > upgrading when the algorithm has proven itself and is reasonably widely
> > implemented in SSH.
> 
> Hmmm.... OpenSSH has implemented an ssh-ed25519 and B. Harris has
> written:
> 
>   https://tools.ietf.org/html/draft-bjh21-ssh-ed25519-02
> 
> I am not sure how closely the IRTF Ed25519 an ssh-ed25519
> implementations match, but I suspect it may be relevant to discuss
> both drafts and the SSH protocol sooner rather than later.

AFAIK ssh-ed25519 is compatible with CFRG consensus on new
signature schemes, but it's not yet become an I-D.

> OpenSSH has implemented [email-masked]

Since we did that there has been an RFC on using this combination
https://tools.ietf.org/html/rfc7539 which is incompatible with ours.

The OpenSSH one, among other less-notable differences, maintains a
second chacha20 instance to encrypt packet lengths.

AFAIK a couple of other implementation support the openssh version.

> The way that RFC5647 was written seems to not have been widely adopted
> although OpenSSH did implement [email-masked] and
> [email-masked] which are very similar. It might be nice to
> actually come up with a 'standards' track document dealing with AEAD
> ciphers and SSH and see if there is a better way to negotiate it within
> the existing framework of SSH's separation of MAC and Cipher. For
> example, maybe MAC=AEAD and Cipher=aes-gcm,chacha20-poly1305 would make
> more sense in the negotiation?

The situation wrt aes-gcm is frustrating. A draft was posted by a NSA
employee here a few years ago, and there was quite a bit of feedback
that the negotiation method that it proposed effectively broke
negotiation of non-AEAD ciphers. The NSA/IETF standardised it anyway.

The only difference between the NSA/IETF RFC and the openssh
implementation is that we fixed the negotiation in kex.

> It would be useful to see what other protocols various SSH implementers
> have been adding and see if there is a desire to move any of them into a
> recommended or optional standard.
> 
> There is also the possibility of a encrypt-then-mac kinds of MAC choices
> to try to avoid attacks against block ciphers which are either
> mac-then-encrypt or AEAD.

OpenSSH has had encrypt-then-MAC modes as the default for some time. 

One other thing worth mentioning is the [email-masked]
key exchange method. It's supported by a few implementations and is
AFAIK compatible with the CFRG curves draft.

We'll probably do curve448 KEX and public key schemes in the near future,
with the NSA's recent de-recommendation of 256 bit EC.

With regard to recommended options, my take is something like:

kex: curve25519-sha256, with ecdh-sha2-nistp* as a second choice
pubkey: ed25519, with ecdsa-sha2-nistp* as a second choice
cipher: chacha20-poly1305, with [email-masked] as second choice

(second choices for people who suffer under the yoke of FIPS compliance)

-d

---

From: [email-masked] (Niels Möller)
Date: Fri, 06 Nov 2015 06:16:09 +0100

Jeffrey Hutzelman <[email-masked]> writes:

> To summarize the changes, I propose:

I think this makes sense. I've been a bit out of the loop for this, wit
lsh being a mostly dormant project, but I'd like to offer my comments.
My apologies if I misremember some relevant details.

> For public key algorithms:
> - Downgrade ssh-dss, pgp-sign-dss, and x509v3-ssh-dss to NOT
> RECOMMENDED.
> - Upgrade ssh-rsa to REQUIRED

ssh-rsa is sha1 only, right? It's still stronger than ssh-dss (since it
allows larger keys), so if we want a widely deployed algorithm to
replace ssh-dss as REQUIRED, it makes sense. But defining ssh-sha256-rsa
as RECOMMENDED would make sense too.

And when it comes to sha1 weaknesses, using sha1 with a signature
algorithm seems more dangerous than using it for hmac or for key
expansion.

> - Upgrade ecdsa-sha2-* to RECOMMENDED
> - Add dsa-sha2-256 as RECOMMENDED

I have no strong opinion on whether these should be recommended or
optional. I think there are quite strong reasons to prefer deterministic
algorithms, but that's more a question of a recommendation for the
implementation, since it's not really visible on the wire what method
was used to produce the nonce.

> For MAC algorithms:
> - Upgrade hmac-sha2-256 to REQUIRED
> - Consider upgrading hmac-sha2-512 to RECOMMENDED
> - Downgrade hmac-md5 and hmac-md5-96 to NOT RECOMMENDED
> - Downgrade hmac-sha1-96 to NOT RECOMMENDED
> - Consider downgrading hmac-sha1 to RECOMMENDED
>
> HMAC-SHA1 is not (yet) considered insecure, it has been SSHv2's only
> required algorithm since RFC 425x were published, and it is probably the
> most widely deployed.  So, we should not downgrade it below RECOMMENDED.
> However, I think a case can be made for hmac-sha2-256 replacing it as
> the REQUIRED algorithm, if we think that has gained enough traction.

My understanding is that there are no known attacks on hmac-sha1, and
that the attacks on non-keyed hashfunctions in the family don't apply.
Is there any likely harm in keeping it as required for another decade?

> For encryption algorithms:
> - Upgrade aes128-ctr to REQUIRED
> - Consider downgrading 3des-cbc to RECOMMENDED
> - Downgrade all other *-cbc algorithms to NOT RECOMMENDED
> - Do we want to say anything about IDEA, CAST, or RC4?

The last 3 seem fairly irrelevant now. We could specify salsa20 or
chacha, to replace rc4 for high-performance use-cases.

> I chose aes128-ctr because RFC4253 listed aes128-cbc as
> RECOMMENDED while leaving the other sizes OPTIONAL.  I suspect this was
> done because at the time, some folks did not want to ship AES256 due to
> export restrictions and/or lack of utility.

What about the key-setup problems in aes256? I seem to recall that it's
not as much better than aes128 as was intended.

> We may wish to consider leaving 3des-cbc at SHOULD,

I think that makes sense, if the main problem with 3des is performance
rather than security.

> Finally, for key exchange algorithms:
> - Upgrade diffie-hellman-group-exchange-sha256 to REQUIRED
> - Upgrade ecdh-sha2-* to RECOMMENDED
> - Consider downgrading diffie-hellman-group14-sha1 to RECOMMENDED
> - Downgrade other diffie-hellman-*-sha1 to NOT RECOMMENDED
> - Downgrade rsa1024-sha1 to NOT RECOMMENDED

> Again, eliminating the SHA1-based DH algorithms in favor of GEX SHA256
> should be obvious,

I don't think choosing group-exchange is obvious; using a fixed group is
an obvious gain in terms of simplicity. Personally, I don't quite like
the complexity and validation issues with group-exchange (but maybe I
could be convinced it's no problem). So I hesitate to make it the
reqiured algorithm.

Why don't you like diffie-hellman-group14-sha1 as required? Is that group
considered too small these days, or is sha1 considered too weak for this
use?

To me it would make sense to also define diffie-hellman-group14-sha256 and/or
diffie-hellman-curve25519, but they can't be candidates for required  at
this time.

>> Or, is this better left to another RFC? Perhaps moving the Ed25519
>> algorithm created by
>> 
>>   https://tools.ietf.org/html/draft-irtf-cfrg-eddsa-00 
>> 
>> into a MUST algorithm while deprecating "ssh-dss" for SSH?
>
> That's an unfinished, -00 version internet draft from CFRG. 

Is that related to the (now expireed, I think) draft I and Simon wrote
some time ago? I'm not following the cfrg work.

I think it would also be highly desirable to standardize use of
aead-algorithms. But as far as I remember, from last time this was
discussed, it was tricky to extend the algorithm negotiation in a clean
way. (And I'd like to do chacha-poly1305 sligthly different from the way
openssh does it, but we can get to that in due time).

So specifying AEAD is a different and harder problem than just updating
the list of recommended algorithms.

Regards,
/Niels

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

---

From: [email-masked] (Niels Möller)
Date: Fri, 06 Nov 2015 07:50:10 +0100

Jeffrey Hutzelman <[email-masked]> writes:

> On Fri, 2015-11-06 at 06:16 +0100, Niels Möller wrote:

[about hmac-sha1]

> Your understanding matches mine.  However, it's still only a 160-bit
> hash, and eventually that just stops being strong enough.  I'd like to
> have something stronger implemented and reasonably widely deployed
> before then.

Reasonable. We need to specify a new REQUIRED algorithm. Demoting
HMAC-SHA1 to recommended lets implementations drop support in due time
without formally departing from the standard. It would kind-of make
sense to specify a flag day "algothithm X is REQUIRED until date Y,
after which is is only RECOMMENDED", but not worth the effort to
formalize.

> SSH's 3des-cbc is three-key EDE 3DES.  It has an effective key length of
> 112 bits, and so is weaker than AES128.

But the "effective key bits" attack is a time/memory-tradeoff which
requires a huge table, right? So in practice I'm not sure a brute force
attack on 3DES really can be expected to be 16 times faster than a brute
force attack on aes128.

> It's also a CBC mode and AFAIK has the same problems as all of SSH's
> other CBC-mode ciphers.

Right, reprecating CBC makes sense. What's the status of 3des-ctr mode?
Not at all as widely deployed as 3des-cbc, I imagine.

> Group exchange doesn't have to mean live, dynamic group generation.  It
> can work fine with a set of fixed groups, either manually configured or
> compiled in.  

Hmm. I was thinking of the receiver of the group list, it has to be
prepared to handle any group, and make an intelligent choice. My gut
feeling is that there may be some subtleties there. But maybe there's no
issue to trust the server and just choose the largest group you think
you can afford to compute with.

> I'd have to go back and look, but I think the sense of the
> group at the time was that there was no reason to define more variations
> with the group baked into the algorithm names.

I can see that argument. Perhaps we shouldn't get into that now, but I
could see scenarious where client might have a preference like

  1. Large Z_p group (preferred option)
  2. curve25519      (acceptable)
  3. Small Z_p group (not acceptable)

Then negotiation fails in the case that they agree on group exchange,
but the server offers only small Z_p groups. While with named groups,
they might have agreed to use curve25519.

Feel free to ignore this discussion if you find in untimely or
distracting. There's a spec for it and noone on the list have raised any
serious security concerns.

> I'm not sure.  It's only a month old, and does have Simon's name on it.

Hmm. It looks like like it's based on our earlier version. I think the python
reference implementation of ed25519 is the same. Nice.

Regards,
/Niels

---

From: Max Horn <[email-masked]>
Date: Fri, 6 Nov 2015 10:08:06 +0100

Hi there,

just joined the list, but saw on the list archive that a few days ago,

> recommended or optional standard.

As a matter of fact, I started such a page some time ago:

  http://ssh-comparison.quendi.de/
  http://ssh-comparison.quendi.de/comparison.html

I tried my best to make it accurate, but of course cannot exclude mistakes.
Also, of course there are implementations missing (one notable is Bitvise's;
I started work on that, but had a hard time finding reliable a source for
what they actually support and what not).

Anyway, issue reports and pull request (also with info on additional
implementations) are most welcome:

  https://github.com/fingolfin/ssh-comparison

The comparison page shows for example that hmac-sha2-256 and hmac-sha2-512
support is quite good now; one notable SSH library not implementing it yet
in a released version is libssh2, but they will have it in the next release
(the code is in their repository already), which in turn should allow
various clients based on it to support it. Another exception is lsh.

Cheers,
max

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Fri, 06 Nov 2015 00:56:40 -0500

> algorithm seems more dangerous than using it for hmac or for key

Agreed.

> not as much better than aes128 as was intended.

Oh, hm; that may be the case.  

SSH's 3des-cbc is three-key EDE 3DES.  It has an effective key length of
112 bits, and so is weaker than AES128.  It's also a CBC mode and AFAIK
has the same problems as all of SSH's other CBC-mode ciphers.  So, the
main reason to deprecate it is indeed security.  The main reason _not_
to do so is interop, particularly with old things.

compiled in.  I'd have to go back and look, but I think the sense of the

In any case, there's a spec for SHA256 with group exchange, but not with
fixed groups.  So if we want to go that route, we have to specify new
algorithms and wait for them to be supported.

> considered too small these days, or is sha1 considered too weak for this

The latter, at least.  The SHA1 here is used to compute the exchange
hash, which is signed to authenticate the key exchange process and bind
it to the host's public key.  It's also used to derive the session keys.
I'm not sure what current thinking is about use of SHA1 for key
derivation, but for non-HMAC authentication it's definitely no longer
sufficient.

> the list of recommended algorithms.

Yup.

---

From: [email-masked] (Niels Möller)
Date: Sun, 08 Nov 2015 17:22:35 +0100

> can work fine with a set of fixed groups, either manually configured or

I've been thinking a bit more about this, and I think that way of using
group exchange has to be *highly discoraged*.

First, it totally defeats the original purpose of group exchange, which
was to avoid wide use of any particular group, in order to reduce the
attacker's gain from massive precomputation.

Second, if fixed groups are used, then those groups ought to be subject
to both standardization review and negotiation at runtime.

E.g., suppose one server implementation with signiifcant deployment uses
group exchange with a single fixed group, say p = 2^3072 - 47. (And it also
supports group14, for interop reasons).

Then, it is discovered that there are relevant attacks on this group and
it should be avoided. But how can a client make sure the 2^3072 - 47
group is avoided, and still interoperate with the above server? It has
to give group14 higher preference than group exchange (with the effect
of practically never negotiating use of group exchange), or resort to
hacks using the server version string and an extra roundtrip delay.

Best regards,
/Niels

---

From: Peter Gutmann <[email-masked]>
Date: Mon, 9 Nov 2015 00:53:02 +0000

Niels Möller <[email-masked]> writes:

>First, it totally defeats the original purpose of group exchange, which was
>to avoid wide use of any particular group, in order to reduce the attacker's
>gain from massive precomputation.

Something even scarier, first pointed out in the Logjam paper, is that (at
least for TLS) some server implementations precompute g^x mod p and reuse it
over a period of time, so every client that connects gets the same DH phase 1
value sent to them.  It's a nice efficiency "optimisation", but it turns DH
into something that works more like RSA (or, since it's DLP, maybe Elgamal)
than DH.

I wouldn't even have considered that someone would do that until I saw it in
the Logjam paper.

>Second, if fixed groups are used, then those groups ought to be subject to
>both standardization review and negotiation at runtime.

The benefit of fixed groups is that, as you mention, they can be reviewed, and
also that they're a lot more efficient than on-the-fly keygen, particularly if
you have to use full-size safe primes rather than the Lim-Lee swarm-of-small-
primes trick.

I'm worried about this short, quick draft turning into a tutorial on how not
to do DH...

Peter.