Subject: Re: Proposal and intent to implement "dsa-sha2-256" SSH key algorithm

From: "Mark D. Baushke" <[email-masked]>
Date: Thu, 29 Oct 2015 23:53:22 -0700

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.

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?

	Curious,
	-- Mark

---

From: denis bider <[email-masked]>
Date: Fri, 30 Oct 2015 03:03:55 +0000

Hey Jeffrey,

thank you for your comments. :-)

I have updated the draft based on this feedback. Same URL - new version:

http://www.denisbider.com/draft-dsa-sha2-256.txt

> Even though it's fairly obvious from the algorithm name,
> I think that should be mentioned in the abstract and
> introduction.  It might be appropriate to work it into
> the title, too

Done so.

> The reference to FIPS-186-3 in the introduction seems
> superfluous.

Removed.

> NIST SP 800-131A doesn't "suggest" or "consider" that
> 1024-bit DSA and SHA-1 are disallowed after 2013.
> It disallows them for government use(*).

Updated.

> If you don't include it, then either implementors will
> support it anyway, or users will be confused when their
> keys don't work.

I've done some testing, and found that Windows CNG cannot import an L=2048, N=224 private key generated with Crypto++.

In the interest of interoperability, I think it's better to prohibit this option. I have added language to this effect.

> I assume that with N=224, you'd want to actually use SHA-224.

It may be interesting to note that Windows built-in crypto - a major, FIPS-certified platform - does not support SHA-224 at all. With DSA, or standalone.

> For that matter, what about _larger_ key sizes?
> What's to say that NIST won't publish FIPS-186-5
> with an (L=4096, N=512) option.  

Allowing for such keys to be used with the same algorithm name would break interoperability with applications unaware of such a new standard.

I have added a section further emphasizing that any departure from the specified options and key sizes requires a different algorithm name.

denis

----- Original Message -----
From: Jeffrey Hutzelman 
Sent: Thursday, October 29, 2015 07:34
To: denis bider 
Cc: [email-masked] ; [email-masked] ; [email-masked] ; [email-masked] ; [email-masked] ; [email-masked] 
Subject: Re: Proposal and intent to implement "dsa-sha2-256" SSH key algorithm

On Thu, 2015-10-29 at 00:25 +0000, denis bider wrote:
> I have whipped up a draft here:
> 
> http://www.denisbider.com/draft-dsa-sha2-256.txt

Not too bad.  A few comments, all minor:

- The use of SHA-256 is a departure from the original ssh-dss algorithm,
which
  specifies SHA-1.  Even though it's fairly obvious from the algorithm
name, I
  think that should be mentioned in the abstract and introduction.  It
might be
  appropriate to work it into the title, too, since that's all that
appears in
  the RFC index, but IMHO that's less important.

- The reference to FIPS-186-3 in the introduction seems superfluous.

- NIST SP 800-131A doesn't "suggest" or "consider" that 1024-bit DSA and
SHA-1
  are disallowed after 2013.  It disallows them for government use(*).
  I suggest an edit something like this...

OLD:
   The National Institute of Standards and Technology (NIST) Special
   Publication 800-131A [800-131A] suggests that DSA keys shorter than
   2048 bits, and with subgroup sizes under 224 bits, are considered
   to have an encryption strength of less than 112 bits, and are
   disallowed after 2013. DSA key sizes of 2048 bits or more, and with
   subgroup sizes of 224 bits or more, are considered acceptable.

NEW:
   National Institute of Standards and Technology (NIST) Special
   Publication 800-131A [800-131A] suggests that DSA keys shorter than
   2048 bits, and with subgroup sizes under 224 bits, are considered
   to have an encryption strength of less than 112 bits.  It disallows
   use of such keys for U.S. Government use after 2013. DSA key sizes
   of 2048 bits or more, and with subgroup sizes of 224 bits or more,
   are considered acceptable.

Similarly for the next paragraph.

> At this point, I'm most uncertain about whether we should allow the following option also:
> 
>    L = 2048, N = 224
> 
> Arguments for:
> 
> - No apparent interoperability reason to exclude it.
> - Perhaps there are DSA implementations that don't easily support
> setting subgroup size, and can only easily generate the N=224 option?
> Does anyone know of one?
> 
> Arguments against:
> 
> - Slightly weaker than N = 256
> 
> Any comments? Thoughts?

If you don't include it, then either implementors will support it
anyway, or users will be confused when their keys don't work.  I assume
that with N=224,
you'd want to actually use SHA-224.

For that matter, what about _larger_ key sizes?  What's to say that NIST
won't publish FIPS-186-5 with an (L=4096, N=512) option.  You'd want to
use SHA-512 with that, but wouldn't it be better not to constrain this
to the key sizes that are available today?

I'd suggest allowing arbitrary key sizes with L >= 2048 and N >= 224,
with the hash to be the largest of SHA-{224,256,384,512} that produces a
digest not larger than N bits.

-- Jeff

(*)  Or rather, it disallows use of all digital signature algorithms
with strength less than 112 bits.  While specific parameters are
mentioned for RSA and DSA, formally the strengths are defined in SP
800-57.  Hpwever, I think we can ignore the latter detail for our
purpose.

---

From: Stephen Farrell <[email-masked]>
Date: Fri, 30 Oct 2015 21:36:21 +0000

On 30/10/15 18:12, Jeffrey Hutzelman wrote:
> Agreed.  In fact, we probably should undertake a general updating of
> recommended and required crypto algorithms across the protocol. 

If there's general support for this, then I'd be happy to
try shift any annoying IETF bureaucracy out of the way. That
could mean forming a short-lived wg or me AD sponsoring a
single document if that's all that's needed. I'm happy to
help with either approach.

Cheers,
S.

---

From: Stephen Farrell <[email-masked]>
Date: Fri, 30 Oct 2015 21:49:20 +0000

On 30/10/15 21:43, Jeffrey Hutzelman wrote:
> On Fri, 2015-10-30 at 21:36 +0000, Stephen Farrell wrote:
>>
> I imagine that we could do it with an AD-sponsored document and an
> extended IETF last call.  No need to spin up a WG, I hope.

Yeah, if it's just algo updates, that seems right. I guess we
should see if folks have another list of things they'd like to
do though - if there were then that might justify a wg, but if
not, then AD sponsored is much quicker/simpler.

> 
> I admit I haven't been paying attention; what's the plan for SHA3?

Not sure there's a general plan. There does seem to be a general
disinterest;-)

> Should we be thinking about a set of documents to define SHA3-based key
> exchange, public key, and MAC algorithms for SSH?

Personally, I'm not that keen on defining stuff that might not
get widespread use, but that kind of opinion seems to vary from
protocol to protocol, and from one set of folks to another. So
I'm not sure what folks here think.

Deprecating old stuff to the extent we can OTOH, I'm quite keen
on that:-)

Cheers,
S.

S.

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Fri, 30 Oct 2015 14:05:53 -0400

> http://www.denisbider.com/draft-dsa-sha2-256.txt

Those updates all look good.

> I've done some testing, and found that Windows CNG cannot import an
> L=2048, N=224 private key generated with Crypto++.
> 
> In the interest of interoperability, I think it's better to prohibit
> this option. I have added language to this effect.

> It may be interesting to note that Windows built-in crypto - a major,
> FIPS-certified platform - does not support SHA-224 at all. With DSA, or
> standalone.

> Allowing for such keys to be used with the same algorithm name would
> break interoperability with applications unaware of such a new
> standard.

I don't understand.  The issue with ssh-dss was that we _didn't_ allow
for larger key sizes.  Well, that and the fact that we specified SHA1,
which doesn't provide sufficient security to keep up with larger key
sizes(*).

So why would it be bad to support larger key sizes with an existing hash
that is already big enough?

(*) In fact, now that I think about it, we probably should have defined
an rsa-sha256 public key algorithm.

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Fri, 30 Oct 2015 14:12:27 -0400

> into a MUST algorithm while deprecating "ssh-dss" for SSH?

A good question.  I feel like we should be discussing such changes,
since the current situation is rather silly.  However, it probably
belongs in a separate document, if only because reaching consensus on
the choice of algorithms may take some time.

More on this in another post.

-- Jeff

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Fri, 30 Oct 2015 14:12:33 -0400

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.

> 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

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Fri, 30 Oct 2015 17:43:40 -0400

---

From: Phil Lello <[email-masked]>
Date: Sat, 31 Oct 2015 10:33:02 +0000

At the risk of thread-jacking a little, I was working a few months ago on
adding SASL support to the SSH protocol; this work is currently parked, but
if I can find time to work on this again, would this be a good juncture to
get that on the standards track? I'm assuming the audience for adding a new
auth mechanism is the same one involved in deprecation.

Best wishes,

Phil Lello

---

From: "Mark D. Baushke" <[email-masked]>
Date: Sat, 31 Oct 2015 09:52:36 -0700

Hi Jeff,

> upgrading when the algorithm has proven itself and is reasonably widely

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.

Regading your table:

> enc   MAY         ???         4345  arcfour128
> enc   MAY         ???         4345  arcfour256

To the best of my understanding, these use CBC and I suggest

enc   MAY         SHOULD NOT  4345  arcfour128
enc   MAY         SHOULD NOT  4345  arcfour256

Regarding additional ciphers while the door is open.

How about RFC7539 ChaCha and Poly1305?

OpenSSH has implemented [email-masked]

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?

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.

fwiw: I would have no problem with an ssh-rsa-sha2 pk.

	-- Mark

---

From: Peter Gutmann <[email-masked]>
Date: Sun, 1 Nov 2015 01:02:16 +0000

>- Add dsa-sha2-256 as RECOMMENDED

I'm strongly opposed to keeping DSA, for the reasons given earlier.  It's dead
everywhere except SSH, it'd be nice to get rid of this one holdout as well.

>Perhaps Denis wants to add pgp-sign-dsa-sha2-256 and/or x509v3-dsa-sha2-256
>to his document.

Since neither the PGP nor the X.509 formats as used in SSH were ever defined,
I'd just remove them.  Short of reverse-engineering someone else's
implementation to see what they do, I can't see how you'd create an
interoperable implementation of either of these.

Peter.