Subject: [Cfrg] On the differences of Ed25519/448 and how it affects a vote on twoshakes-d

From: Björn Edström <[email-masked]>
Date: Wed, 9 Dec 2015 02:48:17 +0100

Hi cfrg,

For the vote [1] I'm thinking about the twoshakes-d proposal [2] and I
can't decide what to vote on it. I'd like to talk this over because it
touches some larger questions.

1) Ed25519 and Ed448 are described in the same draft. We see them as
being part of a "family" of constructs that share certain properties
or behavior with each other. They are quite similar after all. For
some definition of "related", the authors consider the constructs
related enough to be grouped together in one I.D.

Here's the subtle part. Do we see the relation as being in "shape and
form" or do we see the relation as "solving a common signing problem
at different strength levels"?

If we take the former view, then in my opinion we can't practically go
for twoshakes-d, since that will change the shape and form of Ed448 to
differ significantly from Ed25519 (which we really shouldn't touch too
much in this regard since it's already deployed widely).

If we take the latter view, then we can do whatever we want with
Ed448, as long as it's not very unreasonable, and if it is done in the
spirit of improving the strength level (which is already quite spinal
tap-grade). In this view of the world twoshakes-d is pretty fine,
since domain separation has security benefits.

--

2) Do we see HashEdDSA (such as Ed448ph) as a "signing construct with
IUF" in it's own right i.e. a different beast, or do we see HashEdDSA
as a recommendation for what hash the user will plug in into PureEdDSA
to get IUF?

The draft as is *could* have been written as "To get IUF behavior with
Ed448 an implementation SHOULD use <hash>" (i,e. skipping the entire
definition of HashEdDSA and the *ph versions) but since the *ph
versions are defined and named that implies a black box signing
construct view, from the point of view of the user (in my crypto
library I have 4 primitives instead of 2).

If we take the view that Ed448ph is a "signing construct" black box on
it's own, then the twoshakes-d proposal is fine. The black box will
take care of initializing the pre-hash for the user and the internals
are hidden.

If we take the view that Ed448ph is just a recommendation that for IUF
you should do Ed448(SHAKE(prefix||...)), which is likely what is gonna
happen in practice in actual source code, then we are in murkier
waters and have a slight preference against twoshakes-d for two minor
reasons: a) implementation errors, i.e. missing to take the prefix
into account and 2) coupling. With "coupling" I mean that the
signature context (which is seen as a different thing than the hashing
context) must now live slightly longer and is more spread out,
depending on protocol design.

Thoughts?

Cheers
Björn

[1] Poll: hash functions for Ed448 (ends on December 22nd)
[2] http://www.ietf.org/mail-archive/web/cfrg/current/msg07629.html

---

From: Simon Josefsson <[email-masked]>
Date: Wed, 09 Dec 2015 10:08:26 +0100

> related enough to be grouped together in one I.D.

If we select twoshakes-d, I believe we should consider separating
Ed25519(ph) and Ed448 into two documents.  While sharing some elements,
they have become different beasts.  Ed25519(ph) is domain separated by
naming, Ed448 will be domain separated by parameters.  The separate
algorithm Ed448ph no longer makes any sense; whether to prehash or not
becomes a parameter to the process instead.

If the twoshakes-d domain separation is a good domain separation
algorithm or not is something I don't feel qualified to judge, but I
don't feel comfortable with it as it is novel.  The algorithms will
behave different and have different security considerations.

> much in this regard since it's already deployed widely).

I agree with this, and share this line of thinking.

> since domain separation has security benefits.

Sure.

> as a recommendation for what hash the user will plug in into PureEdDSA

I believe the former.  The latter thinking leads to domain separation
issues when the IUF-plugin becomes optional.

> library I have 4 primitives instead of 2).

Right.  If we don't consider twoshakes-d, there would be 4 primitives.
With twoshakes-d, there could be three with the Ed448 variant taking
parameters to achieve domain separation.  Ed448(ph) with twoshakess-d
questions to point of the naming separation, and it might as well be
called just Ed448.

> depending on protocol design.

I share this concern with twoshakes-d.

/Simon

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

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 9 Dec 2015 14:59:44 +0200

> becomes a parameter to the process instead.

Yeah, algorithm that prehashes internally is quite different from one
that takes the prehash as parameter.

> behave different and have different security considerations.

I also don't feel comfortable with it. I think there are two main issues
with it, one is easy to fix and the other is hard to fix:

- The easy-to-fix one: I think instead of simple prehashed/not flag,
  one should have indication of prehash algorithm. Different protocols
  have different preferences there, and also the likelyhood of the
  prehash breaking seems immensely greater than the main hash.

  There is precendent for this kind of operation: PKCS#1 v1.5 RSA
  signatures try to perform hash separation (but fail at it, for
  reasons unrelated to the interface).

  This also comes up in practice: E.g. Adding PureEdDSA to TLS is
  very simple conceptually: Have curve for each scheme (there are
  64,000+ curve IDs free, so not running out) and use the reserved-
  for-future none hash. Then HashEdDSA is completely different matter,
  with interactions being much murkier (due to fixed prehash, which
  might not even have existing choice).

- The hard-to-fix one: Contexts. While cute idea and very useful for
  blocking cross-protocol attacks that are so darn hard to block any
  other way, the interface parts are concerning.

  It is not just plumbing the context into the API of the library
  handling signatures. It is also plumbing the context into interface
  of all sorts of frameworks different protocols use (that don't
  support contexts of their own), and there are quite many of these.

  Also, for any protocol to take the option of using contexts, the
  contexts must be reliably available (especially with hacks like
  how contexts were added to Ed25519-like scheme).

-Ilari

---

From: Gilles Van Assche <[email-masked]>
Date: Fri, 11 Dec 2015 16:26:00 +0100

Dear all,

> becomes a parameter to the process instead. 

Another point of view could be that Ed448 and Ed448ph are still
distinctly-named algorithms (i.e., symmetrically with Ed25519 and
Ed25519ph), but thanks to the domain separation brought by twoshakes-d
in the internal hash they enjoy the property that a public key can be
certified for one, for the other or for both. As far as I have seen,
twoshakes-d is the only proposal so far that offers that property.

> behave different and have different security considerations.

With the point of view above, there is no problem if a public key is
used in either Ed448 or Ed448ph. This follows from that if f(x) is a
sound hash function, then so is f(dom|x) for a fixed prefix "dom".

With a public key used for both Ed448 and Ed448ph, the internal hash can
be viewed as a tree-hash mode on top of SHAKE256, such as:
    without pre-hashing:
        H(x|M)=SHAKE256(dom00|x|M), or
    with pre-hashing:
        H(x|M)=SHAKE256(dom10|x|SHAKE256(dom11|M)),
where "domXY" follows Bryan's coding with X separating between PureEdDSA
and HashEdDSA and Y separating between the internal hash and the
prehash. The security of this domain separation scheme follows from
checking the sufficient conditions defined in [1].

Kind regards,
Gilles

[1] Bertoni et al., Sufficient conditions for sound tree and sequential
hashing modes, IJS 2013

---

From: Tony Arcieri <[email-masked]>
Date: Fri, 11 Dec 2015 14:03:25 -0800

> twoshakes-d is the only proposal so far that offers that property.

I voted for twoshakes-d for this reason, however there's something odd
about this I think really deserves discussion...

I do not think Ed448(ph) will receive widespread use, because Ed25519(ph)
is "good enough".

If twoshakes-d wins, Ed448 will be in the curious position of supporting
domain separation (but hardly anyone will use it), but Ed25519 will not
(and most people will probably use it).

This seems oddly inconsistent to me.

-- 
Tony Arcieri

---

From: Bryan A Ford <[email-masked]>
Date: Sat, 12 Dec 2015 09:33:45 +0100

> checking the sufficient conditions defined in [1].

+1

Also, similar reason applies at the API level to the addition of the
optional context parameter.  Even if many applications/protocols simply
choose not to specify a context and just leave it as the default of
"empty", that can't make security worse than it would be with Ed25519 or
any other signing scheme with no domain separation.

B

---

From: Bryan A Ford <[email-masked]>
Date: Sat, 12 Dec 2015 09:47:14 +0100

On 12/11/15 11:03 PM, Tony Arcieri wrote:
> On Fri, Dec 11, 2015 at 7:26 AM, Gilles Van Assche
> <[email-masked] <mailto:[email-masked]>> wrote:
> 
> I do not think Ed448(ph) will receive widespread use, because
> Ed25519(ph) is "good enough".
> 

Interesting - I agree with most of your reasoning but it leads me to the
opposite conclusion.  Namely, this makes me feel less concerned about
Ed448 being a bit inconsistent with Ed25519 by virtue of having extra
"conservative security features" like domain separation.  While indeed
most everyone agrees that Ed25519 is probably good enough for most
purposes, Ed448's main "raison d'etre" is to have an additional/backup
alternative with even more conservative security parameters - i.e., from
"good enough" (255-bit curve) to "insane" security (448-bit curve).
From that viewpoint, it doesn't seem at all inconsistent with Ed448's
basic purpose for it to have additional conservative security features
that Ed25519 doesn't, such as explicit domain separation.

I still think it would be straightforward to back-port domain separation
to Ed25519 but don't have strong feelings either way; especially the
line of reasoning above makes me also completely comfortable with not
doing so.

Cheers
Bryan

---

From: Ilari Liusvaara <[email-masked]>
Date: Sat, 12 Dec 2015 13:14:48 +0200

> any other signing scheme with no domain separation.

This brings to mind the following (bit crazy):

- Leave Ed25519 as is.
- Drop Ed25519ph
- Add Ed25519dom, with context and hash-signing capabilities.
- Drop Ed448ph
- Rename Ed448 to Ed448dom, with context and hash-signing capabilties.

Now there is key separation for two subkinds of Ed25519, and one
has hash-signing capabiltiies, which are more useful than prehashes
computed with seemingly random algorithms.

Of course, it remains to be seen if constructs similar to
Ed25519dom are actually usable. TODO: Take some world-class Ed25519
implementation and try to modify it to support domain separation.

-Ilari

---

From: Bryan Ford <[email-masked]>
Date: Sat, 12 Dec 2015 13:14:00 +0100

> - Rename Ed448 to Ed448dom, with context and hash-signing capabilties.

This seems like a potentially pretty reasonable "sweet spot" compromise between the semi-conflicting goals of (a) domain separation, (b) alignment between Ed448 and Ed25519, and  (c) backward compatibility with current Ed25529 uses without prehashing or domain separation. 

The one downside I see is that "pure" Ed25519 wouldn't be domain-separated from ed25519dom, i.e., signatures generated with the former could in principle get misinterpreted as the latter and vice versa. But this is probably a small risk we can live with for backward-compatibility reasons.  And if we still have a non-prehashing version of Ed448, that could still be domain-separated from the prehashing version without creating compatibility concerns as in Ed25519. 

B

---

From: Ilari Liusvaara <[email-masked]>
Date: Sat, 12 Dec 2015 17:17:21 +0200

On Sat, Dec 12, 2015 at 01:14:00PM +0100, Bryan Ford wrote:
> The one downside I see is that "pure" Ed25519 wouldn't be domain-
> separated from ed25519dom, i.e., signatures generated with the former
> could in principle get misinterpreted as the latter and vice versa.
> But this is probably a small risk we can live with for backward-
> compatibility reasons. 

Those two would be separated at key level (like Ed25519 and Ed25519ph
are currently).

And hash-signing capabilities imply that separation is one-sided only
(prehash does not have domain prefix). Omitting the separation on
the other side won't cause problems because all info to generate the
prefixes is either public or requires knowledge of the private key.

And lack of IUF on domain is not a problem either, since domains are
supposed to be short.

-Ilari

---

From: Tony Arcieri <[email-masked]>
Date: Sun, 13 Dec 2015 00:13:33 -0800

> that Ed25519 doesn't, such as explicit domain separation.

This is something I'm a bit confused about and could perhaps use some
clarification from the chairs about...

I had also originally assumed that the Ed448 hash choice(s) were a sort of
"spinal tap grade" option to switch over to in the event of a disastrous
Ed25519 failure, but...

Is it that, or is this to be a future framework for additional elliptic
curve signatures? When it comes time to standardize CFRG signatures for
e.g. FourQ, will Ed25519 be treated as legacy and the decisions around
Ed448 be treated as standard operating procedure. Or will the debate start
over from the beginning?

I think it would be nice if there were a standard signature framework that
could be used for future curves without restarting the bikeshedding debate
again from the beginning.

-- 
Tony Arcieri

---

From: Simon Josefsson <[email-masked]>
Date: Sun, 13 Dec 2015 23:04:11 +0100

> that Ed25519 doesn't, such as explicit domain separation.

This is incorrect -- Ed25519 and Ed25519ph are domain separated since
they are different algorithms.  You should never use the same key with
both algorithms, just as you shouldn't use the wrong
domain-separation-bits in Ed448 twoshakes-d with the same key.

/Simon

---

From: Brian Smith <[email-masked]>
Date: Sun, 13 Dec 2015 12:08:50 -1000

> domain-separation-bits in Ed448 twoshakes-d with the same key.

You could say something similar about RSA w.r.t. RSA encryption vs RSA
PKCS#1 vs RSA PSS. However, in practice, people are and will use the same
RSA key for multiple algorithms unless there's something that makes it
difficult to do so. I suspect the same will happen with Ed25519 and
Ed25519ph. Consequently, I don't think we should consider Ed25519 and
Ed25519ph to be domain-separated in practice.

Cheers,
Brian
-- 
https://briansmith.org/

---

From: Simon Josefsson <[email-masked]>
Date: Sun, 13 Dec 2015 23:12:22 +0100

Ilari Liusvaara <[email-masked]> writes:

>> This seems like a potentially pretty reasonable "sweet spot"
>> compromise between the semi-conflicting goals of (a) domain
>> separation, (b) alignment between Ed448 and Ed25519, and (c)
>> backward compatibility with current Ed25529 uses without prehashing
>> or domain separation.
>> 

Right.

One concern is that approaches like Ed25519ph are already deployed,
compared how Ed25519 is used in OpenPGP.

So a proposal for moving forward could be:

* Leave Ed25519 and Ed25519ph as is and publish now

* Specify Ed448 with twoshakes-d ("Ed448dom") and have it in draft form
  until some implementation experience with it develops

I think we are seeing effects of different level of interest between
Ed25519 and Ed448 coming to a closure here: the Ed25519(ph) effort is
about documenting something that is already out there, while Ed448(dom)
is about describing something new that is not deployed.  While it is
nice to have these in the same document, I feel more and more that this
is problematic.  But we'll have to see what the outcome of the current
poll is first.

/Simon

---

From: Simon Josefsson <[email-masked]>
Date: Sun, 13 Dec 2015 23:19:52 +0100

> Ed25519ph to be domain-separated in practice.

For RSA I believe this happened because the specifications 1) didn't
talk about this problem, and 2) was written to allow this to happen
(i.e., a PKCS#1 key and a PSS key are encoded the same way).  I don't
see this happening for Ed25519, or do you have counter-examples?

/Simon

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 18 Dec 2015 22:23:07 +0200

> checking the sufficient conditions defined in [1].

Seperating between internal hash and prehash is not needed. One can
show that even without prehash prefix any forgery either yields forgery
on the base scheme or is prehash collision. And absolutely no security
is promised in either of those cases.

Furthermore, unless one wants to do random prefixes (which greatly
strengthen signatures), one presumably does not want to deal with
any sorts of prefixes on hashes (and postfixes are pointless),
which tend to force having to calculate hashes multiple times, but
take raw hash value to sign.

OpenPGP works that way. TLS is impiled to work that way. SSH does not
need IUF. Etc...

-Ilari

---

From: Alexey Melnikov <[email-masked]>
Date: Mon, 28 Dec 2015 16:15:37 +0000

Hi Tony,

On 13/12/2015 08:13, Tony Arcieri wrote:
> On Sat, Dec 12, 2015 at 12:47 AM, Bryan A Ford <[email-masked]
> <mailto:[email-masked]>> wrote:
> 
> I had also originally assumed that the Ed448 hash choice(s) were a sort
> of "spinal tap grade" option to switch over to in the event of a
> disastrous Ed25519 failure, but...
> 
> Ed448 be treated as standard operating procedure. Or will the debate
> start over from the beginning?

My personal preference would be to use the decision for 448 as the
future template, however I realize that that might be a rathole I would
rather not descend into right now.

So realistically, if CFRG ever to recommend another EC curve, we would
have to [quicly] revisit hash choices. As a co-chair, I would like to
see a justification why future hash choices would be different from what
we pick for Ed448.

> I think it would be nice if there were a standard signature framework
> that could be used for future curves without restarting the bikeshedding
> debate again from the beginning.

---

From: Tony Arcieri <[email-masked]>
Date: Mon, 28 Dec 2015 14:02:39 -0800

> see a justification why future hash choices would be different from what

As someone who +1'd twoshakes-d for the Ed448 decision, I guess it's
probably a bit late to change my mind, and once the SHA2/3 families are
agreed upon as standards, there's little need to change.

The only reason I have any reluctance is because there haven't been, to my
knowledge, any sort of attack on the SHA2 family, and it continues to
provide the best performance.

Ryan Sleevi recently detailed a history of the role of (broken) hash
functions in digital signatures on TLS certificates:

https://medium.com/@sleevi_/a-history-of-hard-choices-c1e1cc9bb089#.ykzwmnjyp

My main takeaway from this was if there were any reason to doubt the SHA2
family now, we should immediately move away from it, but thus far there is
not.

I don't doubt that SHAKE256 is the more conservative choice, but I do speak
as someone who cares about the capacity of TLS-terminating frontend
servers. I'm guessing people who are interested in FourQ would probably
want the most performant option in a hash function (given the performance
impact of scalar multiplication will greatly outweigh that of calculating a
hash)

I guess my point is: if this is to be a framework for future curves, is
there any possibility of specifying both a SHA2 and SHA3 option?
(effectively parameterizing the signature algorithm around a hash function
in addition to a curve)

--
Tony Arcieri