Subject: [Spasm] Change of Algorithms: Take 3

From: Jim Schaad <[email-masked]>
Date: Tue, 16 Aug 2016 14:17:40 -0700

This message looks at Signature Algorithms.  Please restrict your discussions to this set of algorithms, I will be sending out messages on other algorithms over time.

I have started doing the editing work on this.  The pull request can be found at https://github.com/lamps-wg/smime/pull/21

Current Document for S/MIME 3.1

MUST:   RSA w/ SHA-256

SHOULD+:  DSA w/ SHA-256, RSASSA-PSS w/ SHA-256

SHOULD-:  RSA w/ SHA-1, DSA w/SHA-1, RSA w/ MD5

Historic:

Key Sizes:

RSA and DSA - sign

SHOULD NOT            Key size <= 1023

SHOULD      1024 <= key size <= 2048

MAY            2048 < key size   

RSA and DSA - Verify

MAY                key size <= 1023

MUST      1024 <= key size <= 2048

MAY        2048 < key size

RSA - Certificate Verify

MAY             key size <= 1023

MUST  1024 <= key size <= 4096

MAY      4096  < key size

DSA - Certificate Verify

MAY             key size <= 1023

MUST    1024 <= key size <= 3072

Proposed for S/MIME 3.5

MUST: RSA-PSS w/ SHA-256, ECDSA P-256 w/ SHA-256, EdDSA25519

MUST-: RSA w/ SHA-256

SHOULD+:

SHOULD:  RSA-PSS w/ SHA-512, ECDSA P-521 w/ SHA-512, EdDSA448

SHOULD-: 

Historic: RSA w/ SHA-1, DSA w/ SHA-1, RSA w/ MD5, DSA w/ SHA-256

Key Sizes:

RSA - sign

SHOULD NOT            Key size <= 2047

SHOULD      2048 <= key size <= 4096

MAY             4096 < key size   

RSA - Verify

Historic MAY                key size <= 2047

MUST      2048 <= key size <= 4096

MAY        4096 < key size

RSA - Certificate Verify

Historic MAY             key size <= 2047

MUST  2048 <= key size <= 4096

MAY      4096  < key size

DSA - Certificate Verify

Historic MAY             key size <= 1023

Historic MUST   1024 <= key size <= 3072

Questions:

1.                Should DSA be dropped to historic for messages and just left as SHOULD- for certificates, I don't know how many DSA certificates actually exist.

Take 2 state: I have removed all DSA from the current set of algorithms for both messages and certificates.  This is now historic only

2.                I have changed to lower limits on RSA but not DSA for certificate verification - should it be changed as well?  Again I don't know how many DSA certificates exist.

Take 2 state: I have removed DSA certificates to historic so the question is moot.

3.                I don't think that any statements for ECDSA on key size need to be made separately from the algorithm support list.  Does anybody disagree?

Take 2 state:  Nobody said anything to the contrary.  So no plans to make a key size section for ECDSA algorithms.

4.                SPT suggested that we should not be making any statements on doing anything with 512 hash values.  (Although with tons of standard snark ).   My reasoning for including this was less to do with the fact that I thought the 512-bit hash functions were more efficient on 64-bit hardware (a statement that I cannot find support for with a quick web search for SHA-2) and therefore it made sense from a throughput point of view.   I don’t think we need the for security and if they are not more efficient I would be in favor not making them SHOULDs

Take 3 state: Since nobody said anything to the contrary, I have removed all of the SHA-512 hash algorithms.  Russ stated that he would like to add ECDSA P-384 w/SHA-384 but I have seen no support for this position on the list.

5.                Blake has complained about the number of MUST algorithms that comes out from this list.  There are effectively 4 in the list above, as opposed to the 1 that is in the current set of documents.  We cannot kill the current MUST so it has to stay.  However, all of the new MUSTs could be downgraded from MUST to SHOULD without out any problems.  The only issue is that one of them needs to be a MUST so that we have a true MUST not just a MUST- algorithm.  Looking at the list my breakdown would be:

•                 RSA-PSS – Given that it has been slow on update the only reason to have it be a MUST is that most people are probably going to have RSA keys today.  There are some arguments that say RSA-PSS is no better than RSA-v1.5 when doing real-world analysis.  I don’t know that I agree with this as I have problems with arguments by analogy.   This could easily be a SHOULD instead of a MUST

•                 ECDSA – This is the world of NIST requirements today.  I think this justifies it being a MUST

•                 EdDSA – This is the world of NOT MIST requirements today.  I think this justifies it being a MUST

Take 3 state: I have modified this to be all on receive and one on send, but I have not changed any of these to be SHOULD rather than MUST.

Jim

---

From: Russ Housley <[email-masked]>
Date: Tue, 16 Aug 2016 17:46:50 -0400

> Take 2 state: I have removed all DSA from the current set of algorithms for both messages and certificates.  This is now historic only

The only DSA certificates that I know about used 1024-bit keys.  Those should be historic.  Can’t we just say historic for all key sizes?
 
> Take 2 state: I have removed DSA certificates to historic so the question is moot.

Okay.

> Take 2 state:  Nobody said anything to the contrary.  So no plans to make a key size section for ECDSA algorithms.

I think that we should only support named curves, and each one of those comes with an implied key size.
 
> Take 3 state: Since nobody said anything to the contrary, I have removed all of the SHA-512 hash algorithms.  Russ stated that he would like to add ECDSA P-384 w/SHA-384 but I have seen no support…

I would still like to see ECDSA P-384 w/SHA-384 as a SHOULD algorithm.

> Take 3 state: I have modified this to be all on receive and one on send, but I have not changed any of these to be SHOULD rather than MUST.

I agree with Blake.  I suggest:

MUST: ECDSA P-256 w/ SHA-256
MUST-: RSA w/ SHA-256
SHOULD+: RSA-PSS w/ SHA-256, EdDSA25519
SHOULD: ECDSA P-384 w/SHA-384

Russ

---

From: Jim Schaad <[email-masked]>
Date: Tue, 16 Aug 2016 17:38:56 -0700

From: Spasm [mailto:[email-masked]] On Behalf Of Russ Housley
Sent: Tuesday, August 16, 2016 2:47 PM
To: Jim Schaad <[email-masked]>
Cc: SPASM <[email-masked]>
Subject: Re: [Spasm] Change of Algorithms: Take 3

Jim:

Questions:

[JLS] This is what I did.  I saw no reason to keep DSA around as it does not seem to be a) used or b) any more quantum resistant than ECDSA is.

Okay.

4.                SPT suggested that we should not be making any statements on doing anything with 512 hash values.  (Although with tons of standard snark J).   My reasoning for including this was less to do with the fact that I thought the 512-bit hash functions were more efficient on 64-bit hardware (a statement that I cannot find support for with a quick web search for SHA-2) and therefore it made sense from a throughput point of view.   I don’t think we need the for security and if they are not more efficient I would be in favor not making them SHOULDs

MUST-: RSA w/ SHA-256

[JLS] Privileging ECDSA over EdDSA is almost surely going to lead to some pushback among some communities as they see the NIST curves as being anathema since they do not have the desired property of transparency.  What would be the argument that you would put forward to calm the waters over this?

[JLS] Do we really see RSA-PSS as being pushed to a MUST at that point?  The world seems to be rushing headlong into the world of EC and leaving RSA behind.  I don’t see a good reason to keep it at SHOULD+ unless we think this would become the standard going forward.  It makes more sense to me for it to be either MUST, because we think that it will be used a lot, or SHOULD, because RSA is now somewhat in the slow lane.   The only reason that I know to support RSA is quantum support.  Today it is believed that RSA is more resistant to quantum cryptography breakages.

Jim

Russ

---

From: Russ Housley <[email-masked]>
Date: Wed, 17 Aug 2016 16:10:45 -0400

> [JLS] Privileging ECDSA over EdDSA is almost surely going to lead to some pushback among some communities as they see the NIST curves as being anathema since they do not have the desired property o…

I would like to see RSA-PSS w/ SHA-256 and EdDSA25519 at the MUST level, but I do not see enough implementation to support either of them at that level.  Frankly, RSA w/ SHA-256 enjoys much greater deployment than all of the rest.  However, it is time to signal that we need to move to the others.  Right now, ECDSA P-256 w/ SHA-256 enjoys greater deployment than either RSA-PSS w/ SHA-256 or EdDSA25519.  I expect TL 1.3 deployment to improve the deployment situation for all of these, but we are not seeing those impacts yet.

> [JLS] Do we really see RSA-PSS as being pushed to a MUST at that point?  The world seems to be rushing headlong into the world of EC and leaving RSA behind.  I don’t see a good reason to keep it at…

TLS 1.3 is going to require RSA-PSS for the signature on the Finished message.  So, as I said above, I expect TL 1.3 deployment to improve the deployment situation for RSA-PSS.  Further, as you know, most existing RSA certificates can be used with RSA-PSS.

Russ

---

From: Sean Turner <[email-masked]>
Date: Tue, 23 Aug 2016 20:47:18 -0400

> On Aug 17, 2016, at 16:10, Russ Housley <[email-masked]> wrote:
> 

I can live with this.

spt

---

From: Jim Schaad <[email-masked]>
Date: Thu, 25 Aug 2016 15:23:14 -0700

Russ,

I agree with you that the most common of the signing algorithms that we are
looking at is RSA w/SHA-256.  Sometimes I wished that I could just have a
full domain hash of RSA and go forward from there.  The amount of pushback
that I get from efforts to remove RSA v1.5 is tiring.

There are times when I feel MUST statements need to be aspirational as well
as practical.  For this reason, I am willing to look at what I would feel is
the paths going forward as well as what is currently done.  I believe that
there is a great deal of support that is either currently in existence or
will shortly be in existence for EdDSA25519.  Today EdDSA25519 is in
BouncyCastle and X25519 is in the next release of OpenSSL and I expect that
EdDSA25519 will in included as well (they are in need of the curdle draft).
I am sure that it is going into the crypto libraries for Mozilla and Google
due to its inclusion in the TLS 1.3 specifications.  I would be surprised if
they are not setup to use it today in testing.  I have also found it in one
embedded cryptographic package that I am working with.  I am not sure how
fast Microsoft and Apple are going to pick these up, but I would not be
surprised if Google tries to get and pushes EdDSA in all of its websites
pushing this for quicker adoption. 

The slow point is going to be getting CAs to accept it as an algorithm, but
I believe that having pressure from Firefox and Chrome is going to make this
something relatively quickly accepted.  On the other half of this is the
question of how fast people are going to update and roll out any updates to
S/MIME.  I would expect this to be on the order of a couple of years before
a reasonable amount of roll out is done.  By then the world will not look
the same as it is today.

One of the ways that I can think of to make sure that one segment of people
decide that they do not want to move from PGP to S/MIME is to stay with the
NIST algorithms as the core EC curves.  I do not believe that there are any
problems with them, but there is a not insignificant group of people who are
more than willing to make the claim that there might be.  Putting both
curves on a par means both that people are going to use the EC algorithms
and that they will be able to use the one of their choice.   I think this
would be good news for Microsoft.  There is also the question of how long do
you think it is going to take for NIST to bless EdDSA25519 and X25519.
Since these are generally thought of as being both faster and less likely to
have timing leaks (maybe true, maybe not) there will be people who perceive
them as being better even if they do not believe that the current NIST
curves are tainted.

Given politics, I believe that 25519 is going to win long term over P-256.
I don't want to go through this process again in 3-5 years to deal with
that.  Making both EC curves musts means that we don't need to.

The only reason that I see RSA-PSS winning is if we have a quantum computing
problem.  If it was not for that I would make this a SHOULD algorithm and
promptly forget about it.  People who use RSA are most likely to stay with
1.5 because it is what they currently have and until we do another update at
some future point not going to go away.  Again, I am not sure that an update
is a likely event given the question of market support.

Based on the above, I am strongly in favor of keeping EdDSA25519 as a must
along with P256.

Jim

Sent: Wednesday, August 17, 2016 1:11 PM

Jim:

MUST-: RSA w/ SHA-256

[JLS] Privileging ECDSA over EdDSA is almost surely going to lead to some
pushback among some communities as they see the NIST curves as being
anathema since they do not have the desired property of transparency.  What
would be the argument that you would put forward to calm the waters over
this?

I would like to see RSA-PSS w/ SHA-256 and EdDSA25519 at the MUST level, but
I do not see enough implementation to support either of them at that level.
Frankly, RSA w/ SHA-256 enjoys much greater deployment than all of the rest.
However, it is time to signal that we need to move to the others.  Right
now, ECDSA P-256 w/ SHA-256 enjoys greater deployment than either RSA-PSS w/
SHA-256 or EdDSA25519.  I expect TL 1.3 deployment to improve the deployment
situation for all of these, but we are not seeing those impacts yet.

[JLS] Do we really see RSA-PSS as being pushed to a MUST at that point?  The
world seems to be rushing headlong into the world of EC and leaving RSA
behind.  I don't see a good reason to keep it at SHOULD+ unless we think
this would become the standard going forward.  It makes more sense to me for
it to be either MUST, because we think that it will be used a lot, or
SHOULD, because RSA is now somewhat in the slow lane.   The only reason that
I know to support RSA is quantum support.  Today it is believed that RSA is
more resistant to quantum cryptography breakages.

TLS 1.3 is going to require RSA-PSS for the signature on the Finished
message.  So, as I said above, I expect TL 1.3 deployment to improve the
deployment situation for RSA-PSS.  Further, as you know, most existing RSA
certificates can be used with RSA-PSS.

Russ

---

From: Russ Housley <[email-masked]>
Date: Thu, 25 Aug 2016 20:16:55 -0400

Jim:

I think your last message is saying:

MUST: ECDSA P-256 w/ SHA-256, EdDSA25519
MUST-: RSA w/ SHA-256
SHOULD: RSA-PSS w/ SHA-256, ECDSA P-384 w/SHA-384

Did I follow you logic correctly?

Russ

---

From: Jim Schaad <[email-masked]>
Date: Thu, 25 Aug 2016 17:35:02 -0700

With the proviso that I am not sure on P-384, yes.

Jim

Sent: Thursday, August 25, 2016 5:17 PM

Jim:

MUST-: RSA w/ SHA-256

Russ