Subject: [Cfrg] draft-irtf-cfrg-eddsa-00

From: Simon Josefsson <[email-masked]>
Date: Thu, 08 Oct 2015 14:14:15 +0200

Dear WG,

We have posted the following draft to describe EdDSA, based on the
EdDSA/Ed25519 description in draft-josefsson-eddsa-ed25519 and the
EdDSA2 paper.

   https://tools.ietf.org/html/draft-irtf-cfrg-eddsa-00

Feedback is welcome.

There are at least two main areas I believe the WG will need to discuss:

1) The 912-bit wide internal hash function to use for Ed448.  In the
   EDDSA2 paper we proposed SHA-512/912 because we thought use of SHA512
   would be more convenient in existing deployments than SHAKE256.

   However, given that 1) some implementers thought the IV-modification
   we proposed would be difficult to implement in some APIs, and 2) some
   implementers (including at least one smartcard implementer, which
   typically are more constrained than software-only developers)
   appeared to be fine with SHAKE256 even though it is newer, I believe
   we should treat this as an open issue.  Options include:

     1) SHA-512/912 as described in
        http://ed25519.cr.yp.to/eddsa-20150704.pdf

     2) Straightforward use of SHAKE256, also discussed in the previous
        paper.

     3) Home-cooked SHA2-based variant such as:

          Truncate-912-bits(SHA512("0" | M) | SHA512("1" | M))

     4) Less home-cooked SHA2-based variant such as the RFC 5869 HDKF.

   Thoughts?  Other options?  Strengths and weaknesses of the above?

   Personally I am currently in favor of chosing SHAKE256 for Ed448.

2) Naming of the pre-hashed variants of Ed25519 and Ed448 and the
   relationship between PureEdDSA and HashEdDSA.

   For this draft I chose the short but still (barely) readable names
   Ed25519ph and Ed448ph.  In the EDDSA2 paper we used
   'SHA-512-Ed25519-SHA-512' which might be shorted to 'SHA-512-Ed25519'
   since the internal hash function is already settled on.  Still, I
   believe 'SHA-512-Ed25519' is a quite unreadable name and the
   important part, Ed25519, is lost.  Using 'Ed25519-SHA-512' to refer
   to the pre-hash variant seems confusing given that it is already in
   use to describe Ed25519 with SHA-512 as the internal hash.

   The 'Ed25519ph' name variant came up during discussions related to
   the PKIX EdDSA draft.

   I believe we definitely should not use the name 'Ed25519' to describe
   what we are doing in the pre-hash variant since that is already well
   established in deployment to refer to, eh well, Ed25519.  So another
   name is needed.

   Does someone have a better suggestion, or can we settle on
   'Ed25519ph' and 'Ed448ph'?

The document is not ready, and our primary main open work items are as
below.  If anyone has suggested improvements here, they are welcome.

1) Test vectors and sample code for Ed448 and the pre-hash variants.

2) Align terminology and notation with cfrg-curves.  Perhaps this is
already in good shape, but it might be that a lot of work is required to
harmonise terminology.  Someone has to review both documents for
consistency.

3) We need to abstract the Ed25519 description somewhat so that it can
describe Ed448 too, but not abstract it all the way to the generic EdDSA
which is already described.  Otherwise the document will repeat large
chunk of text to describe Ed25519 and Ed448 which is mostly identical.

4) Security Considerations, especially related to cross-protocol attacks
(i.e., when you use the same key in pure mode or different pre-hashes).

Of course, any other feedback is welcome.

Thanks,
/Simon

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Thu, 8 Oct 2015 14:35:37 +0000

>   would be more convenient in existing deployments than SHAKE256.

I disagree.

>        http://ed25519.cr.yp.to/eddsa-20150704.pdf

Only if worst comes to worst.

>     2) Straightforward use of SHAKE256, also discussed in the previous

Yes, this is the ideal option, which I state my support for.

>          Truncate-912-bits(SHA512("0" | M) | SHA512("1" | M))

Oh Lord, no! Violently opposing.

>     4) Less home-cooked SHA2-based variant such as the RFC 5869 HDKF.

2nd worst - better than (1), worse than (2).

>   Ed25519ph and Ed448ph.

Good names! Remind me of the days of “Phreaking” and such. :-)

>   ...  The 'Ed25519ph' name variant came up during discussions related to
>   the PKIX EdDSA draft... ... Does someone have a better suggestion, or
>can we settle on

I’m for settling on the above names.

---

From: Ilari Liusvaara <[email-masked]>
Date: Thu, 8 Oct 2015 18:29:32 +0300

>    Thoughts?  Other options?  Strengths and weaknesses of the above?

As a note, only the signing function internals need 912-bit hash
function. For the hash that appears in both signing and verification,
512 bits is fine.

Specifically, the steps that need large hashes are:
- Derivation of secret scalar and seed from master key
- Derivation of pseudorandom parameter r from seed and message.

OTOH, the internal hash function needs to be specified for completeness
and testability.

-Ilari

---

From: Taylor R Campbell <[email-masked]>
Date: Thu, 8 Oct 2015 16:27:51 +0000

Date: Thu, 08 Oct 2015 14:14:15 +0200
   From: Simon Josefsson <[email-masked]>

      [...]

Yes please!

If you use SHAKE256 for the hash in Ed448ph, why not use SHA3-512 for
the prehash?  That would reduce the number of distinct crypto
primitives needed for a single Ed448ph implementation.

      [...]

Yes please!

No objection here.

---

From: Tony Arcieri <[email-masked]>
Date: Thu, 8 Oct 2015 09:39:32 -0700

> primitives needed for a single Ed448ph implementation.

...but using SHAKE256 would increase the total number of primitives needed
to implement both Ed25519ph and Ed448ph in a single implementation.

The latest EdDSA paper:

...considers both SHAKE256 and SHA-512/912, and selects the latter because
existing widespread deployment of SHA-512 (e.g. in Ed25519, which isn't
called out specifically in the paper but is certainly worth noting)

My vote would be for #1 (SHA-512/912 as described in the EdDSA paper) or #4
(HKDF)

I am fine with the names Ed25519ph and Ed448ph

-- 
Tony Arcieri

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Thu, 8 Oct 2015 16:42:20 +0000

> ...but using SHAKE256 would increase the total number of primitives needed to
> implement both Ed25519ph and Ed448ph in a single implementation.

It may. So be it.

> existing widespread deployment of SHA-512 (e.g. in Ed25519, which isn't called
> out specifically in the paper but is certainly worth noting)

I haven’t seen SHA-512 “widely deployed”. Perhaps we operate in different
worlds.

---

From: "Salz, Rich" <[email-masked]>
Date: Thu, 8 Oct 2015 16:48:09 +0000

> My vote would be for #1 (SHA-512/912 as described in the EdDSA paper) or #4 (HKDF)

Ditto, for the same reasons as Tony.

--  
Senior Architect, Akamai Technologies
IM: [email-masked] Twitter: RichSalz

---

From: Tony Arcieri <[email-masked]>
Date: Thu, 8 Oct 2015 09:48:13 -0700

On Thu, Oct 8, 2015 at 9:42 AM, Blumenthal, Uri - 0553 - MITLL <
[email-masked]> wrote:

> Both SSH and GPG support Ed25519-with-SHA-512, along with Tor and I2P.

Ed25519-with-SHA-512 is also used by Apple's HomeKit in iOS:
https://ssl.apple.com/business/docs/iOS_Security_Guide.pdf

-- 
Tony Arcieri

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Thu, 8 Oct 2015 16:54:09 +0000

> On Thu, Oct 8, 2015 at 9:42 AM, Blumenthal, Uri - 0553 - MITLL
> <[email-masked]> wrote:

OK. My preference is still SHAKE256.

---

From: Viktor Dukhovni <[email-masked]>
Date: Thu, 8 Oct 2015 17:55:01 +0000

> OK. My preference is still SHAKE256.

Presumably because this is a more natural primitive for producing
arbitrary width output.  So you're looking for a "cleaner" design?

While SHA2-512 expanded to 912 bits is an "ad-hoc" construction?
And you want to avoid legacy baggage?

If so, the choice is between a cleaner forward-looking design, and
a pragmatic what can we use with off-the-shelf code today design.

The downside of the forward-looking design is that code for both
SHAKE256 and SHA2-256 would likely be needed in a complete protocol
implementation.

I think a relevant question then is how soon would SHAKE256 be
needed anyway (because it ends up in TLS ciphersuites or other
protocol components in a complete system).

If SHAKE256 support is a likely near term requirement in many
applications anyway, then we're not saving anyone code-space with
a SHA2-512 ad-hoc construction.  In the long-run, we may be imposing
a code-space cost, if SHA2-512 is mostly deprecated by SHAKE256
some day in the all the other algorithm slots of complete systems.

Is it the group's best guess that SHAKE256 will become "essential"
soon enough, and ultimately preferred to SHA512?  If so, that seems
the wiser long-term choice.

Or is it the case that SHA2-512 is likely with us for the long-haul
(long enough for EC to be obsoleted by scalable Quantum Computers)?
In which case allowing immediate implementation with off-the-shelf
code without introducing a new SHAKE256 requirement may be the more
pragmatic option.

-- 
	Viktor.

---

From: Damien Miller <[email-masked]>
Date: Fri, 9 Oct 2015 05:10:14 +1100 (AEDT)

>    we should treat this as an open issue.  Options include:

[snip]

My preference, with OpenSSH hat on:

Ed25519: SHA512 (quite a bit of deployed software uses this already)

Ed448: In preference order:

1. SHA-512/912 or HKDF (slight preference to SHA-512/912, but don't mind much)
2. SHAKE256
3. Homebrew extension of SHA512 (distant last)

>    relationship between PureEdDSA and HashEdDSA.

don't care beyond retaining Ed25519 as the name of what is already deployed.

-d

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Thu, 8 Oct 2015 18:13:09 +0000

>arbitrary width output.  So you're looking for a "cleaner" design?

Yes, I most certainly do.

>And you want to avoid legacy baggage?

That too. Also, in my experience SHA-256 caught up somewhat - not nearly
to the degree I’d expect given the SHA-* situation, SHA-512 is nowhere to
be seen (sort of examples Tony provided, which I haven’t dealt with
myself).

>a pragmatic what can we use with off-the-shelf code today design.

We’re already re-doing and adding (and removing :) ton of things.

If the concern is *existence* of the code - then there’s code available
for all of the algorithms mentioned, both ECC and hash. I believe I saw
both reference and optimized implementations of SHA-3 and SHAKE.

So I don’t see how avoiding SHAKE (and SHA-3) *now* is “pragmatic”.

>SHAKE256 and SHA2-256 would likely be needed in a complete protocol

True - unless you replace SHA-256 with SHA-3 (which is already
approved/allowed by NIST for use in “federal"-related products, so it
doesn’t look like jumping the gun any more).

On the other hand, while SHA-256 is likely to stay in the code for quite a
while, SHA-3 would have to be added anyway, and probably sooner rather
than later. So why not now…

>protocol components in a complete system).

Off-hand, I cannot answer this question. :-(

>some day in the all the other algorithm slots of complete systems.

I’m pretty sure we’d all be better off with employing SHAKE256 now.

I don’t think there are reasons to prefer SHA-512 over SHAKE256 or
SHA-3-512, given that there seems to be a need for a 256-bit security, but
few seem to actually deploy a SHA-512-based solution.

>code without introducing a new SHAKE256 requirement may be the more

Good points! Though I suspect the group’s crystal ball is no better than
mine. :-)

---

From: Simon Josefsson <[email-masked]>
Date: Thu, 08 Oct 2015 20:36:02 +0200

Thanks for feedback.

> primitives needed for a single Ed448ph implementation.

Interesting idea.  So Ed25519 is all SHA2 and Ed448 would be all SHA3.
That gives some agility against hash concerns as well.

/Simon

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Thu, 8 Oct 2015 18:41:11 +0000

>That gives some agility against hash concerns as well.

+1

---

From: Simon Josefsson <[email-masked]>
Date: Thu, 08 Oct 2015 21:12:20 +0200

> Ed25519: SHA512 (quite a bit of deployed software uses this already)

Agreed.  For Ed25519 I don't believe there are any options on the table
for the internal hash -- the internal hash in Ed25519 has been SHA-512
since 2011 and there is no reason to change this now.  It would not be
'Ed25519' anymore if we change the internal hash.

> don't care beyond retaining Ed25519 as the name of what is already deployed.

I strongly agree.

/Simon

---

From: Dan Brown <[email-masked]>
Date: Thu, 8 Oct 2015 19:32:50 +0000

> -----Original Message-----
> From: Cfrg [mailto:[email-masked]] On Behalf Of Blumenthal, 
> Uri -
> 0553 - MITLL
>

[DB] I agree, and earlier proposed essentially the approach above for 
ECDSA_CFRG:

https://www.ietf.org/proceedings/93/slides/slides-93-cfrg-8.pdf

For larger curves, e.g. Curve448, slide 23 says verifier to use SHA3-512, and 
slide 26 says signer to also use SHAKE256 for key generation (and SHA3-512 for 
hashing).

My rationale was that a larger curve is mainly a precaution, and using SHA3 
instead of SHA2, is a roughly comparable precaution (due to the SHA3 
competition).  But _if_ hash experts now strongly prefer SHA2 to SHA3, for 
some security reason , despite the competition, then SHA2'd be ok.  In other 
words, if SHA2 secure-enough, and more convenient than SHA3, then cannot be 
the same rationale be used to prefer a 256-bit curve instead of 448-bit? 
Obviously, these matched-security arguments are never exact.

---

From: James Cloos <[email-masked]>
Date: Thu, 08 Oct 2015 16:30:45 -0400

>>>>> "SJ" == Simon Josefsson <[email-masked]> writes:

SJ> Thanks for feedback.

>> primitives needed for a single Ed448ph implementation.

SJ> Interesting idea.  So Ed25519 is all SHA2 and Ed448 would be all SHA3.
SJ> That gives some agility against hash concerns as well.

I think I like that idea.

But I'd suggest ignoring sha3 and using shake256 for every type of
digest needed by an ed448 ecosystem.

-JimC
-- 
James Cloos <[email-masked]>         OpenPGP: 0x997A9F17ED7DAEA6

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Thu, 8 Oct 2015 20:41:07 +0000

>I think I like that idea.

+N  :-)

>digest needed by an ed448 ecosystem.

I'd probably prefer sha3 except where non-standard output length is
needed, but I would be happy with your suggestion too.

---

From: Tony Arcieri <[email-masked]>
Date: Thu, 8 Oct 2015 18:27:04 -0700

> That gives some agility against hash concerns as well.

I'll revise what I said previously and be +1 for this. It's a compelling
argument that an Ed448-based construction use a different hash function so
in the event there's an Ed25519 meltdown of some sort, the "spinal-tap
security" equivalent be stronger all around.

So I guess my vote for "Ed448DSA" is:

+1: SHA-912
+1: HKDF
+1: SHAKE-256

Any of these are acceptable to me

-- 
Tony Arcieri

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 9 Oct 2015 18:37:46 +0300

> needed, but I would be happy with your suggestion too.

FYI: SHA3-512 has the problem of being very slow[1].

SHA3-256 or SHAKE256 (you need 512 bit output for 256-bit collision
resistance) is like 85% faster. And even then those are slower than
SHA-512 (apparently quite a bit on Skylake).

[1] The reason for this is that 64-bit Keccak needs to have relative
rate go way down in order to get 512-bit preimage resistance expected
from 512-bit hash.

-Ilari

---

From: Paul Lambert <[email-masked]>
Date: Fri, 9 Oct 2015 18:17:56 +0000

On 10/9/15, 8:37 AM, "Cfrg on behalf of Ilari Liusvaara"
<[email-masked] on behalf of [email-masked]>

>FYI: SHA3-512 has the problem of being very slow[1].

Are we constrained to NIST approved hash algorithms?
If not, BLAKE2 has some impressive performance benefits:
	https://blake2.net/   and
	https://datatracker.ietf.org/doc/draft-saarinen-blake2/

Paul

>_______________________________________________
>Cfrg mailing list
>[email-masked]
>https://mail.ietf.org/mailman/listinfo/cfrg

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 9 Oct 2015 21:22:56 +0300

> 	https://datatracker.ietf.org/doc/draft-saarinen-blake2/

Yes, Blake2 has impressive performance. Unfortunately, the widest
defined variant is 512 bits, which isn't enough here (need 912).

-Ilari

---

From: "Dang, Quynh" <[email-masked]>
Date: Fri, 9 Oct 2015 18:30:58 +0000

Hi IIari and all, 

256-bit preimage-resistance strength is enough. I don't see any reasons to pay a huge performance penalty to get 512 bits of preimage-resistance.

I think SHAKE256 performs competitively to SHA-512 over all. 

In cases where 128-bit of security is required, SHAKE128 outperforms SHAKE256, SHA-256 and SHA-512 generally. I would just recommend to add output-length coding to input strings. 

I would also recommend to implement any of the SHAKE functions, a SHA3 or any other  Keccak-derived function (may be specified in the future) as a mode of operation on top of the Keccak's permutation. By doing this, the permutation can be called by other functions (modes of operation) in the future.

I would also recommend to talk to the Keccak team about Keccak beside NIST. 

Potentially, someone could build a complete symmetric crypto system by calling a Keccak permutation in the future. I have not seen any elegant symmetric crypto design like this one. 

Quynh. 

________________________________________
From: Cfrg <[email-masked]> on behalf of Ilari Liusvaara <[email-masked]>
Sent: Friday, October 9, 2015 11:37 AM
To: Blumenthal, Uri - 0553 - MITLL
Cc: Simon Josefsson; [email-masked]; James Cloos
Subject: Re: [Cfrg] draft-irtf-cfrg-eddsa-00

-Ilari

---

From: Stephen Farrell <[email-masked]>
Date: Sat, 10 Oct 2015 01:21:44 +0100

> Are we constrained to NIST approved hash algorithms?

No, not at all. (IMO)

I think any well-studied algorithm that has the confidence
of both the crypto and implementer communities could well
be adopted.

That sha2 and sha3 have received a lot of scrutiny with
sha2 (sha256 especially) being very widely deployed is also
significant. Though existing code/deployment is less of
a deal in this specific case when we're dealing in any
case with a new signature algorithm.

The fact that NIST seem to have done a fine job with
these hash functions does make them more likely to be
chosen though I think. That's not because NIST say to do
that though but rather because of the level of public
scrutiny.

S.

---

From: Peter Gutmann <[email-masked]>
Date: Sat, 10 Oct 2015 02:13:43 +0000

Paul Lambert <[email-masked]> writes:

>Are we constrained to NIST approved hash algorithms? If not, BLAKE2 has some
>impressive performance benefits:

I would prefer Blake2 (and other standards groups are moving in that direction
too), it's a much better solution than SHA-3.  If you're not going to go with
SHA3-because-NIST-says-so then you may as well do it right and use Blake2.

Peter.

---

From: Yoav Nir <[email-masked]>
Date: Sat, 10 Oct 2015 18:02:39 +0300

> On Oct 10, 2015, at 5:13 AM, Peter Gutmann <[email-masked]> wrote:
> 

I’ve seen that preference for Blake2 as well in some places, although I’m not sure it’s well enough documented for what the IETF likes.  I also notice that none of the IETF working groups are rushing to standardize the use of SHA-3. There’s no “SHA-3 and its use in X” draft for IPsec, TLS, SSH, or whatever. Also it seems like nobody’s bothered to allocate OIDs for SHA-3 with either RSA ([1]) or ECDSA ([2]). It might be the fact that it’s brand new and everybody’s been waiting for NIST to finalize it, but I’m feeling a distinct lack of interest in SHA-3.

It should also be noted that this EDDSA is not a NIST-approved algorithm anyway, so using SHA-3 doesn’t get you much, unless people believe that NIST will be persuaded to add EdDSA to the list of approved algorithms, and in that case having a non-approved hash be part of it could be trouble.

Yoav

[1] http://oid-info.com/get/1.2.840.113549.1.1
[2] http://oid-info.com/get/1.2.840.10045.4

---

From: Taylor R Campbell <[email-masked]>
Date: Sat, 10 Oct 2015 15:40:36 +0000

Date: Sat, 10 Oct 2015 18:02:39 +0300
   From: Yoav Nir <[email-masked]>

   It might be the fact that it's brand new and everybody's been
   waiting for NIST to finalize it, but I'm feeling a distinct lack of
   interest in SHA-3.

SHA-3 was finalized on 2015-08-05: 

http://csrc.nist.gov/groups/ST/hash/sha-3/fips202_standard_2015.html
http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.202.pdf

Its software performance leaves a lot to be desired, and there doesn't
seem to be anyone actively pushing for its adoption at least in free
software and public internet engineering.  The security margin of
SHA-3 is pretty high, so maybe that argues in favour of using it for
Ed448ph.

In contrast, BLAKE2 has decent performance in software, comparable to
SHA-2 in portable C code and -- with the help of hand-tuned vectorized
x86 assembly -- better than MD5 on certain platforms, and its
designers have been actively pushing to encourage its adoption.

---

From: Taylor R Campbell <[email-masked]>
Date: Sat, 10 Oct 2015 15:46:05 +0000

Date: Fri, 9 Oct 2015 21:22:56 +0300
   From: Ilari Liusvaara <[email-masked]>

It's not hard to imagine using BLAKE2 in `CTR mode' to get a 912-bit
hash function -- and that wouldn't be much different securitywise from
using SHAKE256.  Certainly neither one will claim 912-bit preimage
resistance.

---

From: Eric Rescorla <[email-masked]>
Date: Sat, 10 Oct 2015 17:50:10 +0200

My vote would be for something SHA-based for two reasons:

1. We already have SHA in our systems (this becomes a vote for SHA-512
but failing that for SHA-3)
2. It will make it easier to get it NIST-certificated, which seems good.

-Ekr

On Sat, Oct 10, 2015 at 5:02 PM, Yoav Nir <[email-masked]> wrote:

> I’ve seen that preference for Blake2 as well in some places, although I’m
> not sure it’s well enough documented for what the IETF likes.  I also
> notice that none of the IETF working groups are rushing to standardize the
> use of SHA-3. There’s no “SHA-3 and its use in X” draft for IPsec, TLS,
> SSH, or whatever. Also it seems like nobody’s bothered to allocate OIDs for
> SHA-3 with either RSA ([1]) or ECDSA ([2]). It might be the fact that it’s
> brand new and everybody’s been waiting for NIST to finalize it, but I’m
> feeling a distinct lack of interest in SHA-3.
>
> It should also be noted that this EDDSA is not a NIST-approved algorithm
> anyway, so using SHA-3 doesn’t get you much, unless people believe that
> NIST will be persuaded to add EdDSA to the list of approved algorithms, and
> in that case having a non-approved hash be part of it could be trouble.
>
> Yoav
>
>

---

From: David Jacobson <[email-masked]>
Date: Sat, 10 Oct 2015 10:32:23 -0700

> using SHAKE256.  Certainly neither one will claim 912-bit preimage
Assuming you put the counter at the beginning, this is essentially the 
"homebrew" proposal that got all the boos and hisses at the beginning of 
this thread.  But I'm not sure why all the boos and hisses.  It is the 
same technique that NIST uses for counter mode key derivation function 
in Special Publication 800-108.  And it is also the same technique that 
NIST uses to get 440 bits of initial state using SHA-256 in the 
HASH-DRBG of NIST Special Publication 800-90A.

    --David

---

From: "Jim Schaad" <[email-masked]>
Date: Sat, 10 Oct 2015 11:05:59 -0700

> From: Cfrg [mailto:[email-masked]] On Behalf Of Yoav Nir
> Sent: Saturday, October 10, 2015 8:03 AM
> To: Peter Gutmann <[email-masked]>
> Cc: Simon Josefsson <[email-masked]>; [email-masked]; Ilari Liusvaara
> <[email-masked]>; James Cloos <[email-masked]>
> >> Are we constrained to NIST approved hash algorithms? If not, BLAKE2
> >> has some impressive performance benefits:
> >
> > I would prefer Blake2 (and other standards groups are moving in that
> > direction too), it's a much better solution than SHA-3.  If you're not
> > going to go with SHA3-because-NIST-says-so then you may as well do it right
> and use Blake2.
> 
> I’ve seen that preference for Blake2 as well in some places, although I’m not
> sure it’s well enough documented for what the IETF likes.  I also notice that
> none of the IETF working groups are rushing to standardize the use of SHA-3.
> There’s no “SHA-3 and its use in X” draft for IPsec, TLS, SSH, or whatever. Also it
> seems like nobody’s bothered to allocate OIDs for SHA-3 with either RSA ([1]) or
> ECDSA ([2]). It might be the fact that it’s brand new and everybody’s been
> waiting for NIST to finalize it, but I’m feeling a distinct lack of interest in SHA-3.

Blake2 is being processed through the Independent stream at the moment.  It is currently in IESG conflict review.

jim

> anyway, so using SHA-3 doesn’t get you much, unless people believe that NIST
> will be persuaded to add EdDSA to the list of approved algorithms, and in that
> case having a non-approved hash be part of it could be trouble.
> 
> Yoav
> 
>

---

From: Ilari Liusvaara <[email-masked]>
Date: Sat, 10 Oct 2015 22:33:28 +0300

On Sat, Oct 10, 2015 at 11:05:59AM -0700, Jim Schaad wrote:
> 
> Blake2 is being processed through the Independent stream at the
> moment.  It is currently in IESG conflict review.
> 

>From my reading of that, the draft is currently being edited by the
RFC-editor (and it already cleared conflict review)

Next steps would be RFC editor review and then AUTH48.

But, using Blake2 wouldn't really help: The issue is the 512 bit limit,
and Blake2 has that like SHA-2 does.

Proper hash functions >512 bits are very rare (AFAIK, there is just
one with any serious analysis, and it is not that suitable). To reach
that amount of bits, one pretty much has to use something else than
hashes.

One idea I got:
NIST SP800-108 CTR mode KDF with HMAC-SHA512 with Ki=SHA512(x).
The idea of applying SHA512 first is to make it always behave
like x is a long key (HMAC-SHA512 would apply it anyway if
|x|>128).

(Also, for H in s=r+H(R,A,M)*a, even raw SHA512 should do the
trick: Got 512 bits, need 448 bits).

-Ilari.

---

From: Watson Ladd <[email-masked]>
Date: Sat, 10 Oct 2015 15:36:07 -0400

> and Blake2 has that like SHA-2 does.

Why isn't an extra 64 bits enough to get sufficient uniformity? Or am
I misremembering my formulas?

-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.

---

From: Ilari Liusvaara <[email-masked]>
Date: Sat, 10 Oct 2015 23:06:05 +0300

> I misremembering my formulas?

AFAIK, it is enough. The way I calculate uniformity, even 448 bits
(2 extra bits!) would be enough.

The reason is that difference of l from power of two is on order of
sqrt(l). Thus one obtains random collision (breaking the private
key anyway) before detecting any useful statistical anomaly.

-Ilari

---

From: Jean-Philippe Aumasson <[email-masked]>
Date: Tue, 13 Oct 2015 07:01:15 +0000

Hi CFRG,

> and Blake2 has that like SHA-2 does.
BLAKE2 can be used to create longer hashes by leveraging its
personalization string. This is similar to the trick proposed for SHA-2 on
p4 of https://eprint.iacr.org/2015/677.pdf, except that the personalization
string is tweaked instead of the IV.

A different personalization string in BLAKE2 achieves the same
differentiation as a different IV in SHA-512. Namely, it creates totally
different, unrelated functions (but for their specs).

We would thus have:

* For 832-bit hashes: "eddsa-832-1" and "eddsa-832-2" padded with null bytes

* For 912-bit hashes: "eddsa-912-1" and "eddsa-912-2" padded with null bytes

* For 1056-bit hashes: "eddsa-1056-1", "eddsa-1056-2", "eddsa-1056-3"
padded with null bytes

We can call the newly created functions "BLAKE2b-eddsa-832", etc. Or,
shorter codenames like B2ed832.

If CFRG wants to consider this option, we (the BLAKE2 team) can provide a
more formal specs along with test vectors, etc.

---

From: Gilles Van Assche <[email-masked]>
Date: Wed, 14 Oct 2015 11:33:32 +0200

Hi all,

Indeed, as noted by several people, using an extendable-output function
(XOF) like SHAKE128 or SHAKE256 is rather natural and results into
simpler (and cleaner IMHO) definitions.

If I understood correctly, computing a longer hash with SHA-512 as
specified in [Bernstein et al., EdDSA for more curves] requires
processing the input twice (for SHA-512/832 and /912) or four times (for
SHA-512/1056) with different IVs, against only *once* for a SHAKE. Aside
from the complexity aspect, this should also be taken into account if
the performance of the hashing part matters.

Keep also in mind energy consumption, which can become a significant
cost metric in the long run. These signature protocols may be some day
deployed beyond general purpose processors, as in the internet of
things, with some dedicated hardware to reduce the energy consumption.
It was shown during the SHA-3 competition that Keccak is a "greener"
function than the other SHA-3 finalists or SHA-2 (and largely
outperforms them in performance as well).

Kind regards,
Gilles, for the Keccak team

---

From: Peter Schwabe <[email-masked]>
Date: Wed, 14 Oct 2015 15:17:12 +0200

> Hi all,

Dear all,

> simpler (and cleaner IMHO) definitions.

I fully agree with Gilles here. It's true that Keccak is slower in
software than, e.g., Blake 2, but when compared to SHA-512, there's not
much of a difference, except if SHA-512 has hardware acceleration [1]. 
As much as I like fast crypto, I think that simplicity is more
important.

Some people have argued that SHA-3 is complex to implement in software,
but actually, an implementation of all 6 algorithms of the FIPS-202
standard fits into just 9 tweets:
http://keccak.noekeon.org/tweetfips202.html

Best regards,

Peter

[1] http://bench.cr.yp.to/results-sha3.html

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 14 Oct 2015 16:49:05 +0300

> As much as I like fast crypto, I think that simplicity is more

SHA-512 hardware acceleration? I'm not aware of that on any widespread
platform (for some reason, Skylake is much faster in SHA-512 than
Haswell (at least in eBASH), but AFAIK Skylake does not have SHA-512
hardware accel (only SHA-1 (boo) and SHA-256)).

Maybe some ARM SoC?

> http://keccak.noekeon.org/tweetfips202.html

How compact implementations can be code golf'd has little bearing on
realistic complexities of implementation.

- I implemented Blake2b on basis of the I-D (now in RFC-Ed queue). That
  was very straightforward.
- I implemented SHA-3 on bais of FIPS202 (also looked at the original
  Keccak spec, but that didn't help much). I made a spec reading error
  (critical part that is very heavily impiled) that I only discovered
  when going through detailed computation traces. I think SHA-3 could
  really use a spec that doesn't give engineer a headache (not
  specifying variable round count nor lane width and working in terms
  of words instead of bytes would likely help a lot).

Regards to performance, I can't optimize my way out of wet paper bag,
but SHA-3 did seem easier to make run with semi-decent performance
(apparently Blake2 relies on vectorization, which GCC can't do well).

Of course, making Blake2 SSE reference implementation work was very
straightforward (except for adapting existing extended Blake2b code,
due to the way that code integrated to existing Blake2b code).

Then there are proposals to use HKDF-SHA512. It only hashes message
once per pass. Many protocols already use HKDF or are moving towards
it. And it isn't difficult to implement from HMAC-SHA512 or even raw
SHA512 (I had test vectors go through first try).

Certainly much simpler to go from SHA512 to HKDF-SHA512 than to
implement SHA-3. With additional fun of SHAKE256 not fitting into
usual general-purpose hashing frameworks.

Off-list, someone (I think he is on this list) stated that use of
HKDF should abide by following two limits:
- Nothing secret in salt.
- Info almost constant (no message in info).

Due to operation of HKDF, that means IKM needs to include seed
and message, making operation look pretty much like ordinary hash
function operation a'la Ed25519 (messages should be short anyway).

-Ilari

---

From: Peter Schwabe <[email-masked]>
Date: Wed, 14 Oct 2015 17:11:54 +0200

Ilari Liusvaara <[email-masked]> wrote:

Dear Ilari, dear all,

> hardware accel (only SHA-1 (boo) and SHA-256)).

Right. Sorry for that. I'll have to go and figure out why Skylake is so
much faster.

> realistic complexities of implementation.

Well, it shows how short and concise you can make code.

>   of words instead of bytes would likely help a lot).

I agree; it's much easier to read Keccak code than the description if
you want to implement it. That is actually the idea of TweetFIPS202: to
provide a short and concise description. Admittedly, for readability you
should run it through indent first, which gives you something like this:
https://github.com/jedisct1/TweetFIPS202/blob/master/sha3.c

Cheers,

Peter

---

From: Taylor R Campbell <[email-masked]>
Date: Wed, 14 Oct 2015 15:29:08 +0000

Date: Wed, 14 Oct 2015 11:33:32 +0200
   From: Gilles Van Assche <[email-masked]>

Since this hash function is used only on one or two hundred bytes in
the first place, to hash two x coordinates and a message hash
together, it is unlikely to be a bottleneck, given that we already
have to perform elliptic curve scalar multiplications.

That said, even if it were, or for the sake of a non-prehashed scheme,
it is not hard to imagine appending a counter instead of changing the
IV/personalization string, e.g.

blake2b(r || a || m || "0") || blake2b(r || a || m || "1") || ...,

which allows one to copy the state of blake2b(r || a || m || .)
instead of recomputing the hash from the beginning, in any reasonable
implementation[1].

Blake2b's security properties include that

c |---> blake2b(r || a || m || c)

is a PRF indexed by r || a || m, so I don't expect security concerns
with this construction.  (If the message is not prehashed and hence
not uniform random, then still (m, c) |---> blake2b(r || a || m || c)
is a PRF indexed by r || a.)

[1] Example, using http://mumble.net/~campbell/hg/blake2/:

struct blake2b ctx0, ctx;
uint8_t h[128];
uint8_t c[8] = {0};

blake2b_init(&ctx0, 64, NULL, 0);
blake2b_update(&ctx0, r, rlen);
blake2b_update(&ctx0, a, alen);
blake2b_update(&ctx0, m, mlen);
ctx = ctx0;
blake2b_update(&ctx, c, sizeof c);
blake2b_final(&ctx, h + 0);
c[0]++;
ctx = ctx0;
blake2b_update(&ctx, c, sizeof c);
blake2b_final(&ctx, h + 64);

---

From: Damien Miller <[email-masked]>
Date: Thu, 15 Oct 2015 03:10:41 +1100 (AEDT)

On Fri, 9 Oct 2015, Damien Miller wrote:

The arguments wrt SHA-3/SHAKE have convinced me, so updating my

> Ed25519: SHA512 (quite a bit of deployed software uses this already)

unchanged

> 3. Homebrew extension of SHA512 (distant last)

1. SHA-3/SHAKE
2. SHA-512/912 or HKDF (could live with this)
3. Homebrew extension of SHA512 (avoid if possible)

-d

---

From: Alyssa Rowan <[email-masked]>
Date: Wed, 14 Oct 2015 18:30:03 +0100

On 2015-10-14 17:10, Damien Miller wrote:

I'm on the same page here. My preferences mirror Damien's updated ones:
 • Ed25519: keep SHA-512
 • Ed448: use the SHAKE256 XOF; failing that, SHA-512/912 or HKDF

It (still) just seems like the most naturally-fitting solution to this
issue for me - I think I suggested it before? - even more natural in
this particular ('paranoid'-level) instance than BLAKE2, which I
otherwise really like for other purposes like file hashing.

- -- 
/akr

---

From: Taylor R Campbell <[email-masked]>
Date: Wed, 14 Oct 2015 22:47:25 +0000

On reflection, for Ed448, my preferences are, from most to least
preferred:

1. SHA3-512 for prehash, SHAKE256 for H
2. Blake2b for prehash, Blake2b-CTR for H
   (i.e., Blake2b(r || 0) || Blake2b(r || 1) || ...)
3. SHA-512 for prehash, either HKDF-SHA512 or SHA-512/912 for H

Rationale:

- Prefer one primitive over several for a single signature scheme.
- Prefer SHA-3 or Blake2 over SHA-2 for better security properties.
- Prefer standard primitives over nonstandard (e.g., SHA-512/912).
- Prefer simpler constructions over more complex (e.g., HKDF, HMAC).
- Performance of prehash is not critical: if you rely on signing very
  long messages, you're inviting DoS for verifiers -- don't.

Both Blake2 and SHA-3 are easy to implement with decent performance in
portable C code:

http://mumble.net/~campbell/hg/blake2/blake2b.c
http://mumble.net/~campbell/hg/blake2/blake2s.c
http://mumble.net/~campbell/hg/sha3/keccak.c
http://mumble.net/~campbell/hg/sha3/sha3.c

(Blake2 is much easier to make fast than either SHA-2 or SHA-3, even
in portable C code (for 256-bit, blake2s 11-12 cpb, SHA-256 21-22 cpb,
SHA3-256 23-24 cpb; for 512-bit, blake2b 7-8 cpb, SHA-512 10-11 cpb,
SHA3-512 ~43 cpb -- on my Intel Ivy Bridge i7).  But the cost of a
signature in sensible protocols is dominated by the cost of the
elliptic curve operations, not by the cost of the prehash.)

---

From: Tony Arcieri <[email-masked]>
Date: Wed, 14 Oct 2015 15:50:26 -0700

On Wed, Oct 14, 2015 at 3:47 PM, Taylor R Campbell <[email-masked]

>    (i.e., Blake2b(r || 0) || Blake2b(r || 1) || ...)

Why would you do this with Blake2b as opposed to using the personalization
strings feature?

-- 
Tony Arcieri

---

From: Taylor R Campbell <[email-masked]>
Date: Wed, 14 Oct 2015 23:10:50 +0000

Date: Wed, 14 Oct 2015 15:50:26 -0700
   From: Tony Arcieri <[email-masked]>

It's simpler and likely faster to do this than to use personalization
strings (which, e.g., the Blake2 internet-draft doesn't include).  See
my note (message-id [email-masked]) at

https://www.ietf.org/mail-archive/web/cfrg/current/msg07420.html

for details.

---

From: Ilari Liusvaara <[email-masked]>
Date: Thu, 15 Oct 2015 08:54:29 +0300

> 3. SHA-512 for prehash, either HKDF-SHA512 or SHA-512/912 for H

I think using anything else than identity / SHA-512 as prehash
in Ed448 is a bad idea.

The reason isn't so much that SHA3-512 is hilariously slow (Blake2b
is well known to be a speed demon), but due to practical
considerations the prehash is going to leak out of the "box", so
now applications need to deal with more casess.

E.g. TLS 1.2 has apparently been designed to leak the prehash
that way (TLS 1.3 retains the basic structure, but the amounts
of data to sign are much smaller).

> elliptic curve operations, not by the cost of the prehash.)

Aside, comparing speeds with my implementations, my Blake2 is quite
a bit slower, but SHA-3 is quite a bit faster (I ended up unrolling
every loop except the round loop).

BTW: Estimates for amount of data it takes for good prehash to
dominate signing time against signing the hash with good PureEd448
implementation:
- SHA-3: ~13kB
- SHA-2: ~30-31kB
- Blake2b: ~69kB.

(I estimated PureEd448 signing time for 64 bytes at 240-260 kcyc
(depending on the hash, with Blake2 being at low end[1], and
HKDF-SHA512 at top end[2]).

[1] "Blake2b-CTR" is pretty much the fastest on almost all sizes
(except some very small ones due to blocking effects).

[2] The HKDF-SHA512 slowness is mostly from overhead (18 blocks
@~1kcyc each(!)): It is faster than SHAKE256 on 8kB messages.

-Ilari

---

From: Taylor R Campbell <[email-masked]>
Date: Thu, 15 Oct 2015 13:27:05 +0000

Date: Thu, 15 Oct 2015 08:54:29 +0300
   From: Ilari Liusvaara <[email-masked]>

Well, I think *any* fixed prehash is a bad idea, but identity and
randomized prehash were both rejected in favour of appeasing legacy
I/U/F APIs and encouraging DoS against verifiers, so given that...

Can you elaborate on this leak?  I'm not familiar enough with the
details of TLS 1.2 to know what you're referring to.

If it's just the SignatureAndHashAlgorithm list, in which one could
conceivably mix Ed448 with a prehash of, e.g., SHA-1 (which is still
there in the TLS 1.3 draft, apparently), that doesn't preclude the
CFRG from recommending that Ed448 be mixed only with SHA3-512.

---

From: Ilari Liusvaara <[email-masked]>
Date: Thu, 15 Oct 2015 17:01:19 +0300

> I/U/F APIs and encouraging DoS against verifiers, so given that...

Well, agreed. I consider signature-level online operation a bad
idea.

And with regards to those legacy APIs, I suspect PKCS#11 is major
one, and it tends to cause problems everywhere it touches (e.g. Firefox
THS fix got delayed some time in order to deal wit PCKS#11 issues).

> details of TLS 1.2 to know what you're referring to.

TLS 1.2 spec impiles (altough it doesn't state this explicitly) that
TLS protocol code itself does the HashAlgorithm hashing of the
signature and then passes the hash to be signed.
 
> CFRG from recommending that Ed448 be mixed only with SHA3-512.

Or one could perhaps specify that al EdDSA signatures always have
HashAlgorithm of 0 (None). No current signature primitive uses
HA0, but it is explicitly specified for future signature primitives.
Ed25519 and Ed448 definitely always use HA0. But does e.g.
Ed25519ph use HA0 or HA6 (SHA-512)? There is no SHA3-512 currently.

-Ilari

---

From: Simon Josefsson <[email-masked]>
Date: Fri, 16 Oct 2015 10:13:19 +0200

> I think using anything else than identity / SHA-512 as prehash

If we use SHAKE256 (which appears to have support from a number of
people now) for the internal hash, I think there is some merit to the
idea that you shouldn't have to have both SHAKE256 and SHA-512 in an
implementation of Ed448ph.  So you would have SHAKE256 as the internal
hash, and SHA3-512 as the pre-hash.  I could live with SHA-512 as the
prehash too, but it feels a bit awkward to depend on two hash
algorithms.

/Simon

---

From: Gilles Van Assche <[email-masked]>
Date: Fri, 16 Oct 2015 10:24:47 +0200

> 1. SHA3-512 for prehash, SHAKE256 for H

If the targeted security strength is 256 bits, I would suggest to use
SHAKE256 for prehash as well, since SHAKE256 is much faster than SHA3-512.

Kind regards,
Gilles

---

From: Peter Schwabe <[email-masked]>
Date: Fri, 16 Oct 2015 12:02:55 +0200

Dear all,

+1 

Cheers,

Peter

---

From: Simon Josefsson <[email-masked]>
Date: Fri, 16 Oct 2015 13:15:16 +0200

> SHAKE256 for prehash as well, since SHAKE256 is much faster than SHA3-512.

How would you use SHAKE256 for the prehash?

/Simon

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 16 Oct 2015 16:42:04 +0300

> SHAKE256 for prehash as well, since SHAKE256 is much faster than SHA3-512.

Well, SHAKE256 isn't a hash (according to FIPS202).

And if you want to use SHAKE256 for "prehash", you could as well
extract it at 912 bits, so one can use the same "hash" function for
internal and pre hashing (this costs about 4kcyc from blowing of
block boundaries).

(Some hash APIs need to fix hash length for each algorithm, so
you can't have "SHAKE256", but could have "SHAKE256@912b").

-Ilari

---

From: Taylor R Campbell <[email-masked]>
Date: Fri, 16 Oct 2015 14:49:59 +0000

Date: Fri, 16 Oct 2015 16:42:04 +0300
   From: Ilari Liusvaara <[email-masked]>

   > SHAKE256 for prehash as well, since SHAKE256 is much faster than SHA3-512.

No objection here, provided it is truncated at (at least) 512 bits.

The relevant property is that SHAKE256 truncated at d bits is
advertised to have collision resistance of min(d/2, 256) bits.  So
SHAKE256@512b is supposed to satisfy the main property we expect of a
prehash.

If there are concerns about sharing common outputs, we could always
prepend `Ed448ph-SHAKE256@512b-prehash' or something to the message
before feeding it SHAKE256@512b as the prehash.

---

From: Gilles Van Assche <[email-masked]>
Date: Fri, 16 Oct 2015 18:08:49 +0200

> How would you use SHAKE256 for the prehash?

I would simply take SHAKE256 and truncate the output to 512 bits. This
gives a hash function of 512 bits with a 256-bit security strength.

> Well, SHAKE256 isn't a hash (according to FIPS202).

After truncation, it becomes a hash function, but indeed this is not a
hash function approved by NIST. As far as I understood, the reason for
this is summarized in [FIPS 202, Section A.2], i.e., calling SHAKE with
the same input and different output lengths yield common output
prefixes. However, I expect the output length of the pre-hash to be
clearly defined in the signature scheme.

> (Some hash APIs need to fix hash length for each algorithm, so you
> can't have "SHAKE256", but could have "SHAKE256@912b").

Right, if you need to stick to traditional hash APIs, you would have
"SHAKE256@512b" for pre-hash and "SHAKE256@912b" for the internal hash,
both calling SHAKE256 internally.

When possible, a better solution would be to foresee a XOF API, where
the output bits can be taken at will ("extendable output", literally).

> SHAKE256@512b is supposed to satisfy the main property we expect of a

I agree.

Kind regards,
Gilles

---

From: Paul Lambert <[email-masked]>
Date: Fri, 16 Oct 2015 16:02:06 +0000

+1 on using just one hash function Š I still have a slight preference for
BLAKE2 for it¹s speed in software.

PAul

On 10/16/15, 7:49 AM, "Cfrg on behalf of Taylor R Campbell"
<[email-masked] on behalf of [email-masked]> wrote:

>[email-masked]
>https://www.ietf.org/mailman/listinfo/cfrg

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 16 Oct 2015 20:08:36 +0300

> the output bits can be taken at will ("extendable output", literally).

I wrote a hash library (for all sorts of experiments, it could treat
all kinds of hashes in way uniform to the caller). With API being new
design, but mostly following tried and true IUF (albeit with some
extensions). Had to modify API in ways I'm not happy about in order
to accomodiate variable-width stuff[1].

Well yeah, one could take 912-bit SHAKE256 and truncate it to 512 bits
to get 512-bit SHAKE256. But that property is specific to XOFs, which
aren't the only variable-width things around. With SHAKE256, one could
even use 1088-bit variant (one full block) and truncate the answer.
That would be big enough even for E-521 (needs 1056-bit KDF).

This looks to be part of problem with "exotic-and-simple" vs. "ordinary-
and-complicated" one sees a lot in diffrent contexts.

[1] XOFs and variant where different widths are not truncations of each
other.

-Ilari