Subject: [Cfrg] Message Digest Algorithm Choice for CMS with Ed448

From: Russ Housley <[email-masked]>
Date: Sat, 12 Nov 2016 22:55:21 -0500

The CURDLE WG is working on a document that specifies the
conventions for using EdDSA with CMS [RFC5652].  See
draft-ietf-curdle-cms-eddsa-signatures.

The most common case involves these steps:

   1.  Compute a message digest on the content.

   2.  Create a message-digest attribute that include the 
       result from 1.

   3.  Gather all of the attributes that will be signed, which
       includes the attribute from 2.

   4.  Digitally sign the set of attributes.

For Ed448 (EdDSA with Curve448), step 4 uses SHAKE256.

SHAKE256 uses SHA3-512 internally.

What message digest algorithm should be used in step 1?

It seems that SHA3-512 would be a good choice to avoid
having to implement more that one message digest algorithm
to generate the signature or validate it.

Russ

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Sun, 13 Nov 2016 04:20:28 +0000

> -----Original Message-----
> From: Cfrg [mailto:[email-masked]] On Behalf Of Russ Housley
> Sent: Saturday, November 12, 2016 10:55 PM
> To: IRTF CFRG
> Subject: [Cfrg] Message Digest Algorithm Choice for CMS with Ed448
> 
> The CURDLE WG is working on a document that specifies the conventions for
> using EdDSA with CMS [RFC5652].  See draft-ietf-curdle-cms-eddsa-
> signatures.
> 

Not precisely, a blackbox SHA3-512 implementation would be of little use to create a SHAKE256 implementation.  What is true that both are based on the Keccak permutation, and so parts of a nonblackbox SHA3-512 implementation could be reused in a SHAKE256 implementation.
> It seems that SHA3-512 would be a good choice to avoid having to implement
> more that one message digest algorithm to generate the signature or
> validate it.

How about SHAKE256, with the output limited to 256 bits?  SHAKE256 in that mode ought to have the same security properties as SHA3-256 (as they are the same except for different end-message padding).

> 
> Russ
> 
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

---

From: Ilari Liusvaara <[email-masked]>
Date: Sun, 13 Nov 2016 08:13:03 +0200

> How about SHAKE256, with the output limited to 256 bits?  SHAKE256 in
> that mode ought to have the same security properties as SHA3-256 (as
> they are the same except for different end-message padding).

Eeh... Except SHAKE256 has 256-bit collision resistance, so one needs
512-bit output to reach that bound. And this is signatures right, where
collision resistance is the most important?

The preimage resistances cap at 256 bits, but those aren't that
important with signatures, and 256 bits is above the security level of
the curve anyway.

So 512-bit output?

-Ilari

---

From: Derek Atkins <[email-masked]>
Date: Mon, 14 Nov 2016 11:28:56 -0500

> collision resistance is the most important?

It depends which security service of signatures you're asking about.
For non-repudiation, yes, collision resistance is important.  However
preimage resistance is important for integrity/forging security.

> important with signatures, and 256 bits is above the security level of

Luckily for most hashes the preimage resistance is the full size of the
hash, whereas collision resistance is half.  So even though preimage
resistance is important we should focus on collision resistance when
choosing sizes.

> So 512-bit output?

If you want 256-bit collision resistance then yes, you would need
512-bit output.

> -Ilari

-derek

-- 
       Derek Atkins                 617-623-3745
       [email-masked]             www.ihtfp.com
       Computer and Internet Security Consultant

---

From: "Salz, Rich" <[email-masked]>
Date: Mon, 14 Nov 2016 18:30:38 +0000

> more that one message digest algorithm to generate the signature or

Let's rephrase:  Any argument *against* SHA3-512?

(yes, jetlag stinks:)

---

From: Taylor R Campbell <[email-masked]>
Date: Mon, 14 Nov 2016 18:47:20 +0000

Date: Mon, 14 Nov 2016 11:28:56 -0500
   From: Derek Atkins <[email-masked]>

No!

A signature scheme defined in terms of H(m), such as RSASSA-PSS,
relies on the collision resistance of H to prevent forgery.  Preimage
resistance is *not* sufficient.  Failure of MD5 to be collision-
resistant is what enabled HTTPS certificate forgery in the wild ten
years ago.

(Attack: Find m =/= m' such that H(m) = H(m') and m is a certificate
for for harmlessexample.com while m' is a certificate for google.com.
Submit a CSR to a CA that you predict will issue m signed.  Now you
have a signed certificate for google.com.)

A more sensible signature scheme defined in terms of H(r, m) for some
unpredictable per-message value r, such as EdDSA, relies only on the
*target* collision resistance of H to prevent forgery.  This is a
stronger requirement than preimage resistance, but all the standard
hash functions, even MD5, are still conjectured to be target-
collision-resistant.

However, the question at hand is about a scheme defined in terms of
H(m) -- in particular, what H should we use for computing the message
digest in step 1 of Russ Housley's original message, message-id
<[email-masked]> at
<https://www.ietf.org/mail-archive/web/cfrg/current/msg08786.html>?

   Date: Sat, 12 Nov 2016 22:55:21 -0500
   From: Russ Housley <[email-masked]>

      [...]

Can we persuade the CURDLE WG to use an H(r, m) scheme instead, such
as EdDSA without the prehash, and thereby dispel requirements of
collision resistance?

---

From: Taylor R Campbell <[email-masked]>
Date: Mon, 14 Nov 2016 18:53:47 +0000

Date: Mon, 14 Nov 2016 18:30:38 +0000
   From: "Salz, Rich" <[email-masked]>

   (yes, jetlag stinks:)

SHA3-512 is slow in order to attain the meaninglessly high 512-bit
preimage resistance, whereas SHAKE256-512 provides `only' 256-bit
preimage resistance at much higher speed.  Both provide only 256-bit
collision resistance.

Note that draft-irtf-cfrg-eddsa doesn't use SHA3-512 at all, whereas
it does use SHAKE256 for several purposes.

---

From: Jim Schaad <[email-masked]>
Date: Tue, 15 Nov 2016 08:10:08 +0900

> From: Cfrg [mailto:[email-masked]] On Behalf Of Taylor R Campbell
> Sent: Tuesday, November 15, 2016 3:47 AM
> To: Derek Atkins <[email-masked]>
> Cc: IRTF CFRG <[email-masked]>; Russ Housley <[email-masked]>; Scott
> Fluhrer (sfluhrer) <[email-masked]>
> Subject: Re: [Cfrg] Message Digest Algorithm Choice for CMS with Ed448
> 
> A signature scheme defined in terms of H(m), such as RSASSA-PSS, relies on
the
> collision resistance of H to prevent forgery.  Preimage resistance is
*not*
> sufficient.  Failure of MD5 to be collision- resistant is what enabled
HTTPS
> certificate forgery in the wild ten years ago.
> 
> (Attack: Find m =/= m' such that H(m) = H(m') and m is a certificate for
for
> harmlessexample.com while m' is a certificate for google.com.
> Submit a CSR to a CA that you predict will issue m signed.  Now you have a
> signed certificate for google.com.)
> 
> *target* collision resistance of H to prevent forgery.  This is a stronger
> requirement than preimage resistance, but all the standard hash functions,
even
> MD5, are still conjectured to be target- collision-resistant.
> 
digest in
> step 1 of Russ Housley's original message, message-id <7DDD1353-96FC-4E70-
> [email-masked]> at <https://www.ietf.org/mail-
> archive/web/cfrg/current/msg08786.html>?
> 
> Can we persuade the CURDLE WG to use an H(r, m) scheme instead, such as
> EdDSA without the prehash, and thereby dispel requirements of collision
> resistance?

Please note that the following is how CMS works

Sign( list of attributes )
List of attributes contains a hash of the message along with other items
such as a time, which signature algorithm, which hash algorithm, potentially
which certificate(s) to use for verification.

For this exercise, we are looking what to use for the hash of message, the
sign operation is using EdDSA pure.

Jim

---

From: "Salz, Rich" <[email-masked]>
Date: Mon, 14 Nov 2016 23:15:56 +0000

For this document, we are not defining a new signing technique, we are defining how to use the existing techniques with current crypto.  Make sense?

---

From: Taylor R Campbell <[email-masked]>
Date: Mon, 14 Nov 2016 23:31:54 +0000

Date: Tue, 15 Nov 2016 08:10:08 +0900
   From: Jim Schaad <[email-masked]>

If you are limited to choosing a single fixed public hash function H
so that the message m figures into the rest of the system only via
H(m), then it is essential to choose H so that it has collision
resistance at the desired security level, e.g. SHAKE256-512 for a
256-bit security level.

(SHA3-512 does too but is excessively slow for that security level.
The CFRG's EdDSA draft uses SHAKE256 rather than SHA3-512 for this
reason.)

---

From: Taylor R Campbell <[email-masked]>
Date: Mon, 14 Nov 2016 23:39:17 +0000

Date: Mon, 14 Nov 2016 23:15:56 +0000
   From: "Salz, Rich" <[email-masked]>

   For this document, we are not defining a new signing technique, we
   are defining how to use the existing techniques with current
   crypto.  Make sense?

Not sure what you mean here.  H(r, m) is an exising technique with
current crypto -- the plethora of applications using Ed25519 out of
libsodium or whatever do exactly this, picking r = H(sk, m) where sk
is the long-term secret key.  This doesn't require extra inputs to the
signature on the part of the user -- the user still just feeds in a
long-term secret signing key sk and a message m, and gets out a
signature or signed message.

A prehash is needed only for legacy protocols that foolishly insist on
incorporating the message m only via a single fixed public hash
function H(m) of it, which renders them vulnerable to collisions in H,
or forces them to pay the additional cost of collision resistance.

---

From: Russ Housley <[email-masked]>
Date: Wed, 16 Nov 2016 02:22:24 -0500

I’d like to summarize what I have heard.  Either SHA3-512 or SHAKE256-512 provide the necessary protection.  Both of these use Keccak, and both produce a 512-bit result.  SHAKE256 is more efficient.

I wrote a small test program, and it confirms that SHAKE256 is more efficient than SHA3-512.

Looking at the NIST web pages, the algorithm identifier for SHA3-512 has been defined, but the only algorithm identifier for SHAKE256 has a 256-bit result.  Quynh Dang says he can help with that.

For the SHAKE256 algorithm identifier, I am thinking about something like this:

      hashAlg-SHAKE256  ALGORITHM ::= { OID id-TBD
                                        PARMS SHAKE256OutputSize }

      SHAKE256OutputSize  ::=  INTEGER  -- Output size in bits

Russ

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 16 Nov 2016 10:31:37 +0200

On Wed, Nov 16, 2016 at 02:22:24AM -0500, Russ Housley wrote:
> I’d like to summarize what I have heard.  Either SHA3-512 or
> SHAKE256-512 provide the necessary protection.  Both of these
> use Keccak, and both produce a 512-bit result.  SHAKE256 is
> more efficient.
> 

Note that from theoretical grounds, one gets that SHAKE256 is supposed
to have 89% higher throughput than SHA3-512 (or equivalently hashing
takes 47% less time) over long messages.

This if from the fact that SHAKE256 packs 136 data octets into each
block, whereas SHA3-512 only packs 72. And the algorithm to process
each block is the same. So SHAKE256 processes about 136 octets in the
same time as SHA3-512 processes 72.

The security level difference is in preimage resistance (512->256
bits), but 256 bit security level is more than sufficient here,
given that the curve is weaker than that.

Output length adjustment to "match security levels" is not helpful,
given that the block counts will be the same anyway.

Also, I hope that there is some envelope around the raw SHAKE256
result. Otherwise the result is the same as Ed448ph, except without
the TBS collision protection w.r.t. Ed448.

-Ilari

---

From: Derek Atkins <[email-masked]>
Date: Wed, 16 Nov 2016 11:56:16 -0500

Taylor,

>    preimage resistance is important for integrity/forging security.

Yes!  (two can play at that silly game -- I've got two toddlers who LOVE
to play that game).

> resistant is what enabled HTTPS certificate forgery in the wild ten

Ah, I see the confusion now...  We're using different definitions (and
processes) of forgery.

> have a signed certificate for google.com.)

In my mind this is a different kind of "non-repudiation" attack, not a
"forgery" attack.  In this case you're getting actual data signed, but
you're instead claiming (successfully, due to the collision) that you
got something else signed.  I.e., getting harmlessexample.com signed
isn't forging.  It's a valid signature on a valid certificate.  But
you're using a collision to effect a repudiation attack by claiming that
no, what was signed wasn't harmlessexample.com, but google.com.

It's a subtle but very important distinction (even if the end result is
the same -- a signed certificate for google.com).

[snip]
> as EdDSA without the prehash, and thereby dispel requirements of

Unlikely.

-derek

---

From: Watson Ladd <[email-masked]>
Date: Wed, 16 Nov 2016 09:18:46 -0800

> Ah, I see the confusion now...  We're using different definitions (and

Yours are nonstandard.

> the same -- a signed certificate for google.com).

It is not actually so. This would violate EUF-CMA.

---

From: Russ Housley <[email-masked]>
Date: Sat, 19 Nov 2016 20:04:27 -0500

> the TBS collision protection w.r.t. Ed448.

Ilari:

I believe the ASN,1 encoding of the signed attributes provides the “envelope around” the SHAKE256-512 result.

I just posted an updated Internet-Draft:
https://www.ietf.org/id/draft-ietf-curdle-cms-eddsa-signatures-01.txt

Thanks,
  Russ

---

From: Ilari Liusvaara <[email-masked]>
Date: Sun, 20 Nov 2016 07:56:14 +0200

On Sat, Nov 19, 2016 at 08:04:27PM -0500, Russ Housley wrote:
> I believe the ASN,1 encoding of the signed attributes provides the
> “envelope around” the SHAKE256-512 result.

Oh, indeed it does.

-Ilari