SSH key algorithm updates

[Jeffrey Hutzelman <jhutz%cmu.edu@localhost>]

On Thu, 2015-10-29 at 23:53 -0700, Mark D. Baushke wrote:
> Hi denis,
> 
> Should this Draft RFC also be the one that moves the "ssh-dss" public
> key algorithm from a "REQUIRED" and "MUST" implement algorithm to
> an "OPTIONAL" and "SHOULD NOT" implement algorithm?
> 
> As things stand right now with RFC4253, the only REQUIRED algorithm is
> "ssh-dss" and I do not believe that it is a good idea to leave it in
> that state.

Agreed.  In fact, we probably should undertake a general updating of
recommended and required crypto algorithms across the protocol.  A
number of new algorithms have been defined over time, but none of them
is REQUIRED and none of the old ones have been downgraded.

My suggestion would be to publish a document which updates RFC4253 with
a new set of requirements and recommendations for algorithms.  It should
include tables listing key exchange, encryption, MAC, and public key
algorithms, showing the current state (REQUIRED, RECOMMENDED, OPTIONAL,
NOT RECOMMENDED) of each algorithm.  I've included below a table showing
the current state of all registered algorithms, as far as I've been able
to determine, along with some proposals for changes.

To summarize the changes, I propose:

For public key algorithms:
- Downgrade ssh-dss, pgp-sign-dss, and x509v3-ssh-dss to NOT
RECOMMENDED.
- Upgrade ssh-rsa to REQUIRED
- Upgrade ecdsa-sha2-* to RECOMMENDED
- Add dsa-sha2-256 as RECOMMENDED

Since ssh-rsa has always been RECOMMENDED and is very widely deployed,
it not only is a good candidate for upgrade to REQUIRED, but also
justifies downgrading ssh-dss directly from REQUIRED to NOT RECOMMENDED.

If we're going to downgrade DSS, we should do it across the board.
Perhaps Denis wants to add pgp-sign-dsa-sha2-256 and/or
x509v3-dsa-sha2-256 to his document.

Both larger-key DSA and ECDSA are viable algorithms, and there is some
benefit to having multiple algorithms which are widely implemented,
since public keys tend to have long lifetimes and be difficult to
upgrade if there is a crisis.  Thus, I think it's reasonable to list
both of these as RECOMMENDED and would probably not object to listing
one of them as REQUIRED (in addition to ssh-rsa).


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.


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?

Downgrading the CBC modes should be obvious.  Similarly, it should be
clear that we should upgrade one of the AES counter variants to take its
place.  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.  Today, we may want to
reconsider this position and REQUIRE aes256-ctr instead of aes128-ctr.
Unfortunately, I don't have a good idea how widely implemented these
are.

We may wish to consider leaving 3des-cbc at SHOULD, with a
recommendation that it be disabled by default, especially in servers.
If implementors all remove this, then users may be stuck unable to
access embedded and other old devices which cannot be upgraded.  This
has been a serious problem for people trying to access web-based
management interfaces of older devices, as browsers and TLS stacks have
done things like removing support for smaller DH groups and objecting to
certificates with smaller key sizes.


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, but there is the question of interoperability with
existing deployments.  Thus, we may want to consider leaving group1 or
group14 at SHOULD, with a recommendation that it be disabled by default
in servers.

If we're going to de-recommend SHA1 (outside of HMAC), we should do so
across the board.  Unfortunately, sha256-based versions of the GSSAPI
key exchanges have not yet been defined or implemented.  Since no
replacement is available, deprecating them is premature.  It would
probably be good to update RFC4462, but even after an update is
published, it will probably be a while before the new version is widely
implemented enough to downgrade the old.

Analogous to the public key algorithms, ECDH is a viable algorithm, so
IMHO it makes sense to upgrade to RECOMMENDED.



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


-- Jeff

Type  Current     Proposed    RFC   Name
====  ==========  ==========  ====  ========================================
kex   MUST        SHOULD NOT  4253  diffie-hellman-group1-sha1
kex   MUST        SHOULD?     4253  diffie-hellman-group14-sha1
kex   MAY         SHOULD NOT  4419  diffie-hellman-group-exchange-sha1
kex   MAY         MUST        4419  diffie-hellman-group-exchange-sha256
kex   MAY         SHOULD NOT  4432  rsa1024-sha1
kex   MAY                     4432  rsa2048-sha256
kex   MAY                     4462  gss-group1-sha1-*
kex   MAY                     4462  gss-group14-sha1-*
kex   MAY                     4462  gss-gex-sha1-*
kex   MAY(+)      SHOULD      5656  ecdh-sha2-*
kex   MAY                     5656  ecmqv-sha2-*

Type  Current     Proposed    RFC   Name
====  ==========  ==========  ====  ========================================
enc   MUST        SHOULD?     4253  3des-cbc
enc   MAY         SHOULD NOT  4253  blowfish-cbc
enc   MAY         SHOULD NOT  4253  twofish256-cbc
enc   MAY         SHOULD NOT  4253  twofish-cbc
enc   MAY         SHOULD NOT  4253  twofish192-cbc
enc   MAY         SHOULD NOT  4253  twofish128-cbc
enc   MAY         SHOULD NOT  4253  aes256-cbc
enc   MAY         SHOULD NOT  4253  aes192-cbc
enc   SHOULD      SHOULD NOT  4253  aes128-cbc
enc   MAY         SHOULD NOT  4253  serpent256-cbc
enc   MAY         SHOULD NOT  4253  serpent192-cbc
enc   MAY         SHOULD NOT  4253  serpent128-cbc
enc   MAY         SHOULD NOT  4253  arcfour
enc   MAY         SHOULD NOT  4253  idea-cbc
enc   MAY         SHOULD NOT  4253  cast128-cbc
enc   SHOULD NOT              4253  none
enc   ???                     ----  des-cbc
enc   SHOULD      MUST?       4344  aes128-ctr
enc   SHOULD                  4344  aes192-ctr
enc   SHOULD                  4344  aes256-ctr
enc   SHOULD                  4344  3des-ctr
enc   MAY                     4344  blowfish-ctr
enc   MAY                     4344  twofish128-ctr
enc   MAY                     4344  twofish192-ctr
enc   MAY                     4344  twofish256-ctr
enc   MAY                     4344  serpent128-ctr
enc   MAY                     4344  serpent192-ctr
enc   MAY                     4344  serpent256-ctr
enc   MAY         ???         4344  idea-ctr
enc   MAY         ???         4344  cast128-ctr
enc   MAY         ???         4345  arcfour128
enc   MAY         ???         4345  arcfour256
enc   MAY                     5647  AEAD_AES_128_GCM
enc   MAY                     5647  AEAD_AES_256_GCM

Type  Current     Proposed    RFC   Name
====  ==========  ==========  ====  ========================================
mac   MUST        SHOULD?     4253  hmac-sha1
mac   SHOULD      SHOULD NOT  4253  hmac-sha1-96
mac   MAY         SHOULD NOT  4253  hmac-md5
mac   MAY         SHOULD NOT  4253  hmac-md5-96
mac   SHOULD NOT              4253  none
mac   MAY                     5647  AEAD_AES_128_GCM
mac   MAY                     5647  AEAD_AES_256_GCM
mac   SHOULD      MUST        6668  hmac-sha2-256
mac   MAY         SHOULD?     6668  hmac-sha2-512

Type  Current     Proposed    RFC   Name
====  ==========  ==========  ====  ========================================
pk    MUST        SHOULD NOT  4253  ssh-dss
pk    SHOULD      MUST        4253  ssh-rsa
pk    MAY                     4253  pgp-sign-rsa
pk    MAY         SHOULD NOT  4253  pgp-sign-dss
pk    ???                     ????  spki-sign-rsa
pk    ???                     ????  spki-sign-dss
pk    MAY                     4462  null
pk    MAY(+)      SHOULD      5656  ecdsa-sha2-*
pk    MAY         SHOULD NOT  6187  x509v3-ssh-dss
pk    MAY                     6187  x509v3-ssh-rsa
pk    MAY                     6187  x509v3-rsa2048-sha256
pk    MAY                     6187  x509v3-ecdsa-sha2-*

(+) "SSH ECC implementations" (i.e., those that implement RFC5656)
    are required to implement the ecdsa-sha2-* public key algorithms
    and the ecdh-sha2-* kex algorithms, but not the ecmqv-sha2-* kex
    algorithm.  Furthermore, only certain curves are required.