Subject: [Cfrg] draft-irtf-cfrg-eddsa -- one final proposal for domain separation (context labels) for ed25519

From: Daniel Kahn Gillmor <[email-masked]>
Date: Wed, 20 Apr 2016 02:27:22 -0400

Hi all--

in draft-irtf-cfrg-eddsa-05, there is a context label defined for ed448,
but no such label is defined for ed25519.  (the "context label" is a way
to provide domain separation between signatures made in different
contexts, avoiding cross-protocol attacks)

people seem OK with domain separation for ed448, but we've rejected it
for ed25519 to achieve backward compatibility with existing signatures,
and to avoid API changes to existing ed25519 libraries, as discussed in
threads like [0].

I wanted to float one final middle-ground proposal that would allow us
to align the APIs between the two by adding an optional context
parameter to ed25519/ed25519ph.  If this isn't acceptable, please
consider instead the proposed additional Security Considerations toward
the end of this message.

The proposal for including optional context labels in 25519 is simple:

 * in Table 1: Parameters of Ed25519, change H(x) from "SHA-512(x)" to
   "SHA-512(context || x)", and change PH(x) to "context || x".

 * change the sentence describing the ph variant that follows the table
   to:

    Ed25519ph is the same but with PH being SHA-512(context || x)
    instead, i.e., the input is hashed using SHA-512 before signing with
    Ed25519.

If "context" is unspecified by the user it is treated as the empty
string and, the result is exactly the same as the current description.
This is also easy for someone to implement with existing ed25519
libraries with no API change: just concatenate before signing or
verifying.

This would mean that a signature with a context label for 25519 is not
separated from a signature *without* a context label (a weaker domain
separation than we're offering in ed448), but it at least provides a
standard way for protocols that want to make domain-separated signatures
to do so, which might help us to encourage domain separation in
standards which contemplate the use of either Ed448 or Ed25519 (their
abstract APIs are alignable).

I also think we need some text explaining the difference between the two
approaches.  If we adopt the above proposal, we could add something like
this to the Security Considerations or section 10.3 ("Use of contexts"):

----------
  Note that the domain separation for Ed25519 and Ed25519ph is weaker
  than the domain separation for Ed448 and Ed448ph in two ways:

    (a) Signatures that do not use context labels can potentially
  collide with signatures that use context labels.  This can only be
  mitigated by never using the same key in multiple domains without
  having a domain-specific context label for each use.

    (b) Signature domains that use context labels where one context
  label is a prefix of the other may also have collisions.  This can be
  mitigated by always choosing a context labels that consist of
  printable ASCII characters followed by a single zero-valued octet.

  This weaker domain separation is accepted in Ed25519 due to widespread
  existing context-free deployment and the desire to avoid breaking
  backward compatibility. For Ed448, which is not yet as widely
  deployed, the dom() function's stronger domain separation guarantees
  are preferred.
----------

If we do not adopt the above changes, and leave ed25519 and ed25519ph
without any attempt at domain separation, we also probably need a bit of
text explaining why one primitive has domain separation and the other
does not, probably in either Security Considerations or section 10.3.
Otherwise, future people reading the draft would need to track down
messages like those in [0] to understand the asymmetry.

A proposal for text in this scenario:

-----------
  Note that only Ed448 offers strong domain separation via context
  labels, while Ed25519 lacks this capability.  This is due to a desire
  to retain backward compatibility with existing Ed25519 deployments,
  and to leave the Ed25519 API as simple as possible.

  If an application or protocol needs domain separation in situations
  where Ed25519 may be used, a weaker form of domain separation may be
  had by prepending a context label (fixed octet string) to the message
  before signing or verifying, using a different context label for each
  signature domain.  For the prehash variant, prepend the context to the
  message before pre-hashing.

  To avoid collisions between domains when using this weaker form of
  domain separation, context labels should consist of only printable
  ASCII characters followed by a single-valued octet.
-----------

What do folks think?

     --dkg

[0] see for example Ilari's response here to Bryan Ford at Message-Id:
    [email-masked]
    https://www.ietf.org/mail-archive/web/cfrg/current/msg07713.html

    and the "On the differences of Ed25519/448 and how it affects a vote
    on twoshakes-d" thread starting at Message-Id:
    CAA4PzX18bcS_awPg-YDAoo90537Ot=[email-masked]
    https://www.ietf.org/mail-archive/web/cfrg/current/msg07665.html

---

From: "Paterson, Kenny" <[email-masked]>
Date: Wed, 20 Apr 2016 08:43:50 +0000

Hi Daniel,

Your proposal seems to me to be a very sensible idea.

We are quite keen to get draft-irtf-cfrg-eddsa "shipped", as it's needed
elsewhere in IETF and dependencies are building up.

So, @all, let's try to have a quick discussion on the proposal and see if
any reasons emerge for not adopting it.

Cheers,

Kenny

---

From: "Salz, Rich" <[email-masked]>
Date: Wed, 20 Apr 2016 11:27:00 +0000

This is okay with me, except for one pedantic clarification.  "Empty string" has a specific meaning in C, it's a single NUL byte.  Since our other uses of context including the NUL terminator, to avoid prefix attacks, then I think the wording needs some editing.

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Wed, 20 Apr 2016 08:51:22 -0400

On Wed 2016-04-20 07:27:00 -0400, Salz, Rich wrote:
> This is okay with me, except for one pedantic clarification.  "Empty
> string" has a specific meaning in C, it's a single NUL byte.  Since
> our other uses of context including the NUL terminator, to avoid
> prefix attacks, then I think the wording needs some editing.

the "empty string" message in my message was not part of the proposed
wording change to the draft, but i can see how it might be confusing if
it were to make it into an edit.

If we need additional clarification in the draft to avoid confusion, i
propose:

  If no context label is supplied, it is treated as an octet string of
  zero length; that is, (context || x) is the same as x.

Regards,

  --dkg

---

From: "Salz, Rich" <[email-masked]>
Date: Wed, 20 Apr 2016 12:59:58 +0000

>   zero length; that is, (context || x) is the same as x.

Works for me!

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 20 Apr 2016 17:29:53 +0300

> > prefix attacks, then I think the wording needs some editing.

Eh, I thought the other uses had length prefixing to avoid prefix attacks?
 
>   zero length; that is, (context || x) is the same as x.

Also, anyone up to some quick analysis to show that doesn't interact
harmfully with Ed25519 when using the same keys?

Also, that wouldn't solve the troublesome interaction between Ed25519
and Ed25519ph...

-Ilari

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Wed, 20 Apr 2016 11:57:36 -0400

> Eh, I thought the other uses had length prefixing to avoid prefix attacks?

they do, but we can't have that while still preserving backward
compatibility with the deployed implementations of ed25519, and while
making it relatively easy to use with ed25519 libraries that don't offer
explicit contexts.

If you wanted to do a length-prefixed context, but apply it only in the
case where the context exists (has non-zero length), that's another
option that would preserve backward compatibility with the deployed base.

But i think that's marginally more complicated to reason about and to
implement, and it still doesn't address the potential for collision
between contextualized and context-free domains, so i'm not sure what
we'd gain.

> harmfully with Ed25519 when using the same keys?

eh?  this is specifically and only about how to apply a context label in
Ed25519 and Ed25519ph, since it's already defined for Ed448 -- what do
you mean "interact harmfully with Ed25519" ?

> Also, that wouldn't solve the troublesome interaction between Ed25519

That's true, this proposal doesn't try to solve that problem.  I hope it
can be evaluated independently.

       --dkg

---

From: Russ Housley <[email-masked]>
Date: Wed, 20 Apr 2016 14:07:32 -0400

> This is okay with me, except for one pedantic clarification.  "Empty string" has a specific meaning in C, it's a single NUL byte.  Since our other uses of context including the NUL terminator, to a…

+1

It would be better to say that an “empty context” consists of zero bytes (or octets if you prefer).

Russ

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 20 Apr 2016 21:26:17 +0300

> you mean "interact harmfully with Ed25519" ?

Suppose attacker can get signatures for arbitrary (context,message) pairs
under some key, can he forge a signature for some (context',message') under
that key that he didn't see?

> can be evaluated independently.

I actually once implemented variant of Ed25519 with contexts done like
Ed448. Separate variant, so needed its own keys. It would be very easy
to build Ed25519ph-like scheme by just using SHA-512(msg) as prehash
and marking the message as prehashed (there is no need for context in
inner hash).

-Ilari

---

From: "D. J. Bernstein" <[email-masked]>
Date: 20 Apr 2016 20:51:20 -0000

> elsewhere in IETF and dependencies are building up.

Do any of those dependencies rely on having the signed object be
something other than a message?

I sent CFRG a message "Side inputs to signature systems" back in
September that raises several different objections to the "context"
concept. I believe that all of the objections remain valid. I didn't
notice until now that the concept was still under consideration; sorry!

---Dan

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Wed, 20 Apr 2016 17:41:28 -0400

> that key that he didn't see?

sure, by definition if context' is a prefix of context, and message' is
just the concatenation of (context - context' || message), then it's a
viable forgery.

This is the price we pay for backward compatibility, but it's actually a
*better* situation than we have without a recommended way to use a
context label.

Without a context label, any arbitrary message can be treated as a
"forgery" by simply replaying it in a different context. (e.g. i sign
an ASN.1 sequence of two integers, and you understand it as signed
finite-field DHE params, but i wanted you to understand it as an RSA
public key)

With a context label, for every domain that defines a sane context
(e.g. the guidance i suggested of printable-ascii followed by '\0'), we
can rule out inter-domain replay as a successful forgery because no
context will be a prefix of any other context.

Furthermore, in practice, if we don't specify a standard way to use a
context label for domain separation in Ed25519, different schemes may
apply the context label in different ways, potentially allowing for some
message collision.

> and marking the message as prehashed (there is no need for context in

i'm sure we could propose an entirely new variant that has the same
robustness as Ed448, but it would fail the backward compatibility goals
that i thought the group (including you) had previously identified. In
my proposal here, i am trying to work within those constraints.  Are you
saying that Ed25519ph doesn't need the backward compatibility?

If you're proposing a fix to a separate problem, is it something we can
consider separately?

   --dkg

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Wed, 20 Apr 2016 18:12:05 -0400

> notice until now that the concept was still under consideration; sorry!

The context label is explicitly in place in Ed448 in the current draft,
but not in Ed25519.

Your concerns are reasonable, but i don't think they're insurmountable
or that they warrant the removal of Ed448:

>       * Are cryptographic libraries supposed to change their signature
>         APIs to allow an extra side input?

A library that implements a signature scheme that has a context string
needs to provide an API for it, yes.  For signature schemes where the
context string is optional (which is all of them, afaict), the context
label should be optional.  Libraries that implement such a scheme can
continue to offer the traditional API (without a context label) of
course.

We've already seen some primitives adopt this approach, including the
"info" parameter for HKDF-Expand
(https://tools.ietf.org/html/rfc5869#section-2.3).  This isn't a
traditional asymmetric signature scheme, but it's an addition to the API
compared to earlier KDFs (e.g. PBKDF2 didn't have such a context label).

>       * What exactly are the format and semantics of this input? For
>         example, how exactly would this side input be used to stop the TLS
>         bug mentioned above?

We're actually doing exactly this in TLS 1.3, but doing it in an ad-hoc
way: basically using the prefix approach in some places (e.g. server
CertificateVerify and client CertificateVerify in TLS 1.3 are prefixed
with distinct context strings:
https://tools.ietf.org/html/draft-ietf-tls-tls13-12#section-6.3.4), and
switching our KDF to HKDF in others (key expansion, etc
https://tools.ietf.org/html/draft-ietf-tls-tls13-12#section-7.1).

>       * What happens when someone wants to use more of these inputs?

I'm not sure what you mean here.  You mean more context labels?  the
goal here is one distinct context label per domain.  the only purpose of
the context label is domain separation.  why would you want more than
one?

>       * How should libraries handle all of the signature standards that
>         don't support this input?

Not all signature schemes take the same set of parameters (e.g. public
keys and secret keys have different structures in different messages).

A library that wants to offer a generic signature scheme where the user
doesn't know anything about the mechanism in use could accept a context
label (byte array and length) and a message (bytearray and length).  if
the signature scheme supports an explicit context, it would use it. If
not, it could use the concatenation approach described above.

>       * More to the point, how is this supposed to be better than having
>         the application sign a more informative message, using the
>         traditional concept of a signature system?

"more informative" assumes that you know exactly how any bytestring is
going to be interpreted in every other context.

If we define a standard way that a signature or key derivation domain
can distinguish itself from any other domain, then we can avoid
cross-protocol attacks for every scheme that adopts this standard.

Without it, each protocol will define how it thinks it should structure
a message that is "informative enough" to be distinct from every other
signed message in every other protocol -- but how will this be
determined without cross-protocol coordination?  This mechanism offers a
means for cross-protocol coordination by selection of distinct context
strings.  (for signature schemes like Ed448 that aren't using the
prefix-approach, the only requirement is context string uniqueness,
since they are prefix-resistant)

Does this make it seem more palatable?  This isn't a strictly
cryptographic property, it's a mechanism to facilitate larger
cross-protocol coordination.

Regards,

               --dkg

---

From: Watson Ladd <[email-masked]>
Date: Wed, 20 Apr 2016 15:36:06 -0700

> finite-field DHE params, but i wanted you to understand it as an RSA

Cryptographers have understood since the 1990s the importance of not using
keys across protocols and signing all information affecting interpretation
of signed data.

Protocols which rely on a context cannot work with RSA - PSS or ECDSA. They
can simply specify preappending the context to work with all signature
schemes.

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

---

From: Benjamin Kaduk <[email-masked]>
Date: Wed, 20 Apr 2016 19:38:25 -0400 (EDT)

> going to be interpreted in every other context.

To perhaps step back a bit, a signature scheme taking an optional context
label input with specified semantics (i.e., the label is prepended,
recommended to end with a NUL byte, etc.) is a way to strongly suggest
that application protocols using that signature scheme provide such "more
informative message"s, and gives guidance as to what the structure of the
more informative message could be.

I don't really care if the application protocol makes its message being
signed more informative (i.e., specific to the particular protocol message
at hand) by manually putting that data at the front of its signing input
and ignoring the context input, or by using the context input.  I just
want it to happen, since that improves the overall safety of the internet.

> since they are prefix-resistant)

Having a contetx input to newly specified signature schemes (and a
registry to ensure global prefix-uniqueness, which dkg and Martin and I
are working on a draft for) is a way to help protocol designers that
aren't cryptographers do the right thing, cryptographically speaking.
Perhaps there are better ways to encourage this behavior, but this is the
best proposal I've seen so far, for this issue.

-Ben

---

From: Ilari Liusvaara <[email-masked]>
Date: Thu, 21 Apr 2016 07:39:47 +0300

> just the concatenation of (context - context' || message), then it's a

H(x)=SHA-512(context||x) without any lengths or separators does not behave
that way. It does not have trivially computable collisions (but easily
computed ones might still exist, or worse, a way to extract the private key).

That is, signature for ('abc','def') is not expected to validate for
('abcd','ef').

It is also not possible to compute the result using stock Ed25519 code
with any non-empty context.

> finite-field DHE params, but i wanted you to understand it as an RSA

Contexts were never meant to help with internally-inconsistent protocol
(e.g. TLS ServerKeyExchange signatures), only between different protocols
possibly sharing keys.

> context will be a prefix of any other context.

Also, contexts cause large amount of API problems. And it is very easy
to use in spec without understanding the problems, resulting spec that
is very annoying to implement.

> apply the context label in different ways, potentially allowing for some

There is absolutely no working way to apply contexts using stock Ed25519
implementations that isn't utterly broken.
 
> saying that Ed25519ph doesn't need the backward compatibility?

I don't think Ed25519ph needs backward compatiblity.

> If you're proposing a fix to a separate problem, is it something we can

It is closely related in any space to stick contexts to would also be space
to stick the hash flag to.

-Ilari

---

From: David Jacobson <[email-masked]>
Date: Wed, 20 Apr 2016 22:47:04 -0700

> more informative message could be.

If you want to include a NUL byte to separate the context from the 
following stuff, then to avoid ambiguity you need to require that the 
context not contain any NUL bytes.   And this rules out general binary 
blobs as context values, including general ASN.1 objects.

NIST Special Publication 800-108 (about key derivation functions) made 
this mistake.  Even though Section 7.4 requires a 1-to-1 mapping from 
inputs to the internal blob send to the PRF, the constructs used in 
Section 5 does not achieve that requirement when the label is allowed to 
be an object that contains a NUL byte.

     --David

---

From: Martin Thomson <[email-masked]>
Date: Thu, 21 Apr 2016 15:58:22 +1000

On 21 April 2016 at 15:47, David Jacobson <[email-masked]> wrote:
> If you want to include a NUL byte to separate the context from the following
> stuff, then to avoid ambiguity you need to require that the context not
> contain any NUL bytes.   And this rules out general binary blobs as context
> values, including general ASN.1 objects.

Yes, we can be more concrete if you like:

It's possible to say that only necessary requirement is that no label
be a prefix of any other.  One way of doing that is with a proper
bijective mapping like the length-and-value encoding used in Ed448.
However, that makes zero-length contexts incompatible with existing,
context-free signatures; or to retcon existing uses into being good
citizens.

BTW, the plan is to submit this as a -00 soon, but here's our recommendation:

  https://unicorn-wg.github.io/context-labels/#rfc.section.4

I'm sure that this will stimulate many fruitful discussions, much like this one.

---

From: Ilari Liusvaara <[email-masked]>
Date: Thu, 21 Apr 2016 17:37:53 +0300

> values, including general ASN.1 objects.

You really don't want ASN.1 objects, JSON serializations or anything like
that as context values.

Those values are supposed to be at most name of the protocol and possibly
version thereof (if one decides to use those at all).

-Ilari

---

From: Benjamin Kaduk <[email-masked]>
Date: Thu, 21 Apr 2016 14:30:50 -0400 (EDT)

> That is, signature for ('abc','def') is not expected to validate for

I think I'm confused.  Surely if I set chunk = { 'a', 'b', 'c', 'd', 'e',
'f'} containing six octets, then SHA-512(chunk) is the same, whether I
construct chunk from 'abc','def' or 'abcd','ef'.  So you must be talking
about something else, but I'm not sure what.

> with any non-empty context.

Can you be more specific?  Is the complaint just that one would need to
use a temporary buffer and copy the data to be signed in order to put in
the prefix?

>From where I am sitting, it seems like there are two options: does the
signing API include a context input?  If yes, use that input; if no,
prepend the context to the message to be signed in my own code.  What am I
missing?

> I don't think Ed25519ph needs backward compatiblity.

I am mostly inclined to agree, which gives some useful flexibility here.

> to stick the hash flag to.

Sure.

-Ben

---

From: Ilari Liusvaara <[email-masked]>
Date: Thu, 21 Apr 2016 22:50:14 +0300

> about something else, but I'm not sure what.

I actually implemented the scheme (modifying the python reference
implementation in the draft (modifying H(x) to be SHA512(context|x)).

- Modified and base scheme generate identical signatures and validate
  identical signatures for empty context (as expected).
- Signature of ('abc','def') is different from signature of ('abcd','ef')
  and does not cross-validate. Nor does either cross-validate with
  ('',abcdef).

> use a temporary buffer and copy the data to be signed in order to put in

No. I am saying you can't put in the prefix unless you have Ed25519
implementation modified to support it. Buffering the message won't
help.

> prepend the context to the message to be signed in my own code.  What am I

This does not work.

-Ilari

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Thu, 21 Apr 2016 16:43:15 -0400

>   and does not cross-validate. Nor does either cross-validate with

Is this because you're including the NUL octet between the context and
the signature, or for some other reason?  if so, then i'd phrase it as:

 signature of ('abc\0', 'def') is different from signature of ('abcd\0', 'ef')

which i think everyone would agree is the right outcome.

Or are you talking about some other scheme?

> [ben kaduk wrote:]
>> From where I am sitting, it seems like there are two options: does
>> the signing API include a context input?  If yes, use that input; if
>> no, prepend the context to the message to be signed in my own code.
>> What am I missing?
>
> This does not work.

Why not?  Can you explain more?

    --dkg

---

From: Benjamin Kaduk <[email-masked]>
Date: Thu, 21 Apr 2016 16:54:18 -0400 (EDT)

Hmm, Ilari's messages are not making it into either my MIT or my Akamai
inbox; that's quite unfortunate.

> Or are you talking about some other scheme?

I think Ilari is talking about the Ed448 scheme already describe in the
document, which uses the function:

   dom(x, y)  The octet string "SigEd448" || octet(x) ||
      octet(OLEN(y)) || y, where x is in range 0-255 and y is octet
      string of at most 255 octets.  "SigEd448" is in ASCII (8 octets).

which length-prefixes the context before including it in the signed data,
among other things.  (The dom() output is then concatenated with other
data before being passed to SHAKE256 as H(x).)

> Why not?  Can you explain more?

I think we all need to be more clear about whether we are talking about
the existing Ed448 context scheme, or the bits in
http://unicorn-wg.github.io/context-labels/ .

My comments in this thread have centered on the latter.

-Ben

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 22 Apr 2016 09:21:21 +0300

> Or are you talking about some other scheme?

No, I am not including '\0'.

I literially modified H(x) to prepend context (defaulted to blank byte
string), with no lengths nor separators to x before hashing with SHA-512..

It does not handle empty context as special case, since <empty> is
additive identity for string concatenation.

> Why not?  Can you explain more?

H(x)=SHA512(context|x) does not cause behaviour like Ed25519(key,context|x)
when applied.It causes behaviour that can't be expressed using the base
Ed25519 primitive.

-Ilari

---

From: Martin Thomson <[email-masked]>
Date: Fri, 22 Apr 2016 17:26:37 +1000

> when applied.It causes behaviour that can't be expressed using the base

I don't know why we got hung up on that concept.  PH(x) =
SHA512(context || x) might be closer to what we've been thinking of.

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 22 Apr 2016 12:16:18 +0300

> SHA512(context || x) might be closer to what we've been thinking of.

1) That only 'works' with Ed25519ph. And even with that, you do not
want the context inside data hash.

2) You definitely do not want that kind of context schemes on non-
context keys. Even the prepending the context in hash (without
separation) makes me VERY uneasy.

-Ilari

---

From: Martin Thomson <[email-masked]>
Date: Fri, 22 Apr 2016 20:37:28 +1000

> want the context inside data hash.

I don't know what you want, but maybe you could tell me why I don't want that.

> separation) makes me VERY uneasy.

Well, it's how everyone is forced to do things if the primitive
doesn't have native contexts.  I agree that it could be better, but
I'm not going to lose sleep over it.

I'm having a hard time understanding what you want out of this
conversation.  Maybe you could try to explain whether you think that
context is a good idea and maybe how you would prefer that we solve
the problem.

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 22 Apr 2016 14:28:43 +0300

> I don't know what you want, but maybe you could tell me why I don't want that.

1) More vulernable to attacks there.
2) You need the context outside it anyway for non-prehashed version
   (if you do contexts).
 
> I'm not going to lose sleep over it.

Or just split on key. May be bit painful (and sometimes not possible
at all, e.g. TLS versus CSR) but much better than dealing with the
API mess.

> context is a good idea and maybe how you would prefer that we solve

It is not possible to retrofit contexts into Ed25519 in a way that
I would be even remotely comfortable with. This is because Ed25519
lacks any space to put any extensions to.

Just adding contexts to Ed25519 without splitting variant would
leave it open for trivial attacks (or cryptographic screwedness
I really do not want to see).

If you split variant, you can do whatever is desired, eg. fit
Ed448-style context and hash indicator (which would also solve
problems with Ed25519ph).

-Ilari

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Fri, 22 Apr 2016 11:29:32 -0400

> 1) More vulernable to attacks there.

can you describe the attacks you're concerned about?

> at all, e.g. TLS versus CSR) but much better than dealing with the

I don't think the API mess is as worrisome as you do.  We've had API
changes for primitives in the past (i already mentioned HKDF's evolution
from previous context-free KDF schemes), and they haven't caused the sky
to fall.  We already have a plan for how people can continue using the
primitive without a context label, and we can provide a well-defined
(granted, suboptimal) way for people to use it *with* a context label as
well.

> lacks any space to put any extensions to.

Right, this is the backward-compatibility issue.  So, we're trying to
propose a standard way that people who want contexts can use them with
Ed25519 that doesn't break backward compatibility with context-free
Ed25519.

This is guaranteed to be weaker protection than a scheme that included
contexts from the beginning; but we're not at the beginning -- the
deployed base of "pure" Ed25519 is too large.

However, it seems likely to offer better protection than either:

 a) no one does domain separation at all even in cases where key
    separation is not possible

 b) different protocols make up their own domain separation mechanisms,
    which may or may not collide with each other

No one is arguing that this is a perfect thing to do for Ed25519, we're
arguing that we should do something which is better than nothing at
all.  This is the curse of trying to improve a deployed base.  it should
be familiar to anyone who works at the IETF :/

> I really do not want to see).

Are there other "trivial attacks" beyond confusing signature with a sane
context with a context-free signature?  Is there other cryptographic
screwedness we should be aware of?

I don't understand how to split the variant in a way that is
successfully incompatible with "pure" Ed25519, since as you say Ed25519
has no extension mechanism.

Are you proposing a way to do this that i'm not seeing?

    --dkg

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 22 Apr 2016 20:12:28 +0300

> (granted, suboptimal) way for people to use it *with* a context label as

Well, I don't recall seeing KDF interface.

But then, given crazy stuff I have seen in at least one WG, signature
APIs might not be that standardized (outside things like PKCS#11, that
are bit bad matches anyway).

> be familiar to anyone who works at the IETF :/

There exists pretty close to trivial transform that transforms any signature
scheme into DIFFERENT signature scheme (that uses original scheme as subroutine)
with context input.

Weak signatures are transformed into weak signatures with context, strong
signatures are transformed into strong signatures with context.

> screwedness we should be aware of?

Yes, trivial existential forgeries. And attempts to look at how prefixing
the context into inner hash would fare turned into mess.
 
> has no extension mechanism.

You can add contexts, only you get different scheme (which needs
different keys). If you can compute the result using existing Ed25519
code as-is is independent.

-Ilari

---

From: Simon Josefsson <[email-masked]>
Date: Sat, 23 Apr 2016 09:23:15 +0200

I see a serious concern with adding contexts to Ed25519.  So I don't
like this idea.  Below I suggest a way to achieve what I interpret what
you are after, that would still resolv my concern.  I'll try to explain
it all.  First some background.

First, remember that neither Curve25519 or Ed25519 are an CFRG
invention.  People are interested in using both of them in IETF
protocols.  The TLS WG asked and the CFRG accepted to work on
recommending new ECC curves for use with key agreement and signing.
That resulted in accepting Curve25519 and EdDSA/Ed25519, together with
Curve448 and consequently Ed448.

To deal with the API backwards compatibility issue for Ed25519, the less
secure pre-hashed variant was proposed and adopted.  That algorithm is
called Ed25519ph.  The Ed448 algorithm defined in the document is an
CFRG invention, through its addition of contexts and other details, and
while there is a name collision with the externally/academically
proposed Ed448 schema, that is less of a concern because there has been
little implementation interest in either of the Ed448 algorithms.

If the CFRG aims to re-define what Ed25519 means, which is what I read
that you are proposing to do, I believe we have to pick a different name
for it.  I suggest Ed25519ctx.  However, that said, introducing new
algorithms with different properties should not be done lightly and I
believe the motivation for contexts is at best not sufficiently
motivated by academic research.  DJB posted objections to this concept
when it was discussed earlier.

Further, introducing this tweak late in the process appears unfortunate.
We are having serious trouble shipping documents people have been
waiting for as it is.  Redefining what they will get this late in the
process is harmful.

So here is a suggestion.  Write a document describing a Ed25519-variant
called Ed25519ctx.  I would help work on it.  For those implementations
that are interested in using Ed25519ctx (which are they?), try to get
them aligned behind the document.  If there are, say, two different
protocols that have a desire to use contexts, I would believe that there
shouldn't be a problem getting the document published as an RFC.

What do you think?

Thanks,
/Simon

---

From: "D. J. Bernstein" <[email-masked]>
Date: 23 Apr 2016 12:59:54 -0000

Here's the standard API for signature systems:

   * keygen inputs: nothing; outputs: public key, secret key;
   * sign inputs: message (string), secret key; outputs: signature;
   * verification inputs: message, signature, public key: outputs: yes/no.

This API is overwhelmingly popular in the cryptographic literature, the
security literature, and the software ecosystem. It is shared by the
vast majority of

   * specifications of signature systems,
   * papers analyzing the security of signature systems,
   * theoretical proofs regarding signature systems,
   * cryptographic libraries, and
   * applications of signatures at higher layers of software.

This sharing is tremendously helpful---compare it to all the horror
stories of mismatched APIs slowing everybody down, making the auditor's
job hellishly difficult, and producing real-world security problems. The
simple fact that the signature API is so popular means that any change
to the API comes with a heavy presumption of being a _very bad idea_.

I'm not saying that it's impossible to rebut this presumption. For
example, I recommend merging the message and signature into a signed
message---I'm acutely aware of how many system layers need to be adapted
to make this work, but I don't see any other plausible way to eliminate
the very common "use the message without noticing it's a forgery" error
pattern. Stateful signatures are a deeper example. In both of these
cases I see clear, convincing reasons for a new API, outweighing the
massive costs and dangers---but changing the API is obviously an uphill
battle against a default position of amply justified skepticism.

This brings me to the idea of modifying signature specifications to add
"contexts" (whatever exactly those are!) to signing and verification,
with the hope of stopping cross-protocol attacks. There's a severe lack
of justification for this idea:

   * The security analysis is almost entirely missing. It's easy to come
     up with examples where the idea seems to work, but slightly more
     thought shows many more examples where the idea fails, because it's
     not directly aimed at the core cross-protocol issue.

   * The syntax/layering/API analysis is entirely missing. In every case
     where the idea is effective, the same benefit is also achieved by a
     much more traditional fix that _doesn't_ change the signature API,
     and this traditional fix is much easier from a systems perspective.

As an example, let's imagine that the PGP protocol adopts some sort of
signature-plus-context system, and labels itself with context "PGP".
Sounds like a great way to separate PGP from other protocols, right?

Now let's consider two protocols built on top of PGP (copied verbatim
from my first "Side inputs to signature systems" message):

   * Protocol A: There are two messages, "Put the troops through a
     surprise drill" and "Don't put the troops through a surprise
     drill". For efficiency these messages are compressed to "1" and
     "0" respectively. For security, make sure to check that the
     compressed message is signed with the General's PGP key.

   * Protocol B: There are two messages, "Launch the missiles" and "Don't
     launch the missiles". For efficiency these messages are compressed
     to "1" and "0". For security, make sure to check that the
     compressed message is signed with the General's PGP key.

There's a gigantic cross-protocol vulnerability here, and the "PGP"
context string completely fails to stop this vulnerability.

If you think that the messages in protocol A have to be separated
somehow from the messages signed by the same key in protocol B, then of
course you're right---but how exactly is this supposed to map to the
vague concept of a "context"? Was it wrong for the PGP protocol to
declare "PGP" as the context? Is A supposed to assign a new "A" context,
ignoring the lower-level protocol that's actually doing the signatures?
How is the PGP software supposed to handle this?

What happens when the semantics of the A message _do_ take information
from the lower-level protocol? Should the higher-level protocol A change
the context to some tree structure such as "A within PGP"? Maybe nobody
is actually using the side data available from PGP, but there are many
other examples of semantics being built through chains of protocols.

Even worse, what if the people writing the A software and the B software
don't even realize the need to coordinate "context"? Assigning semantics
to strings is something that programmers are doing all the time---and,
whenever these strings are transmitted through an untrusted network, the
new semantics create a new opportunity for cross-protocol attacks. By
saying "Protocol A" and "Protocol B" I've been painting a picture of
programmers who _realize_ that they're building new protocols, but this
is not actually the normal situation; it is a rare exception.

At this point I expect "Aha, we know the solution!" comments from fans
of dozens of different formats for "self-describing strings." Random
examples that come to mind include the VAX/VMS file format, the original
MacOS file-type system, the Internet mail-message attachment format,
XML, etc., etc., etc. The dream of each of these formats is to provide a
grand unified description of semantics, resolving all possible
misinterpretations. This means that all we have to do is specify that
signed messages are encoded as XML, right?

Unfortunately---even if we ignore the question of how well defined and
understood these formats are---the reality is that programmers are
defining new data semantics so frequently that they usually don't even
define new types _inside their own programs_, never mind going through
the hassle of registering types in any of these grand unified systems.
The universe of semantics defined by software ends up vastly broader
than contemplated in any of these formats. Each format ends up resolving
misinterpretations only within an extremely limited semantic scope.

But wait, there's more! The notion of having a file describe its own
semantics might seem reasonable in contexts where each file is handled
independently---for example, viewed within a stateless file viewer. But
this notion disintegrates as soon as files begin to communicate through
a shared state. By changing this shared state, a signed file can change
how a subsequent signed file is interpreted---but then the signatures
need to include the state or some other strict-sequencing mechanism, to
prevent an attacker from changing the semantics of the second file. The
protocol _after_ modification of the shared state is not the same as the
protocol _before_ modification of the shared state.

It's easy to say that cross-protocol attacks are created by messages
being taken out of context. But what _is_ the context? This is the core
issue, and solving it is vastly more complex than simply sticking "PGP"
somewhere into a signature hash. As I wrote before (without elaborating
on what the word "protocol" means):

   The standard fix for this type of problem is to encode more
   information into the signed messages so that they can't be taken out
   of context. Of course, to figure out how much information is enough,
   you have to work at the protocol layer, understanding all the
   different contexts in all of the high-level protocols that might sign
   messages under the same key---and the protocol designers need to talk
   to each other! Any encoding, no matter how verbose, can be ruined by
   another protocol assigning new meanings to some of the encoded
   messages.

I think that's enough about semantics. Let me now turn to the questions
of syntax, layering, and API.

Show me any definition of semantics in a signature-plus-context system---

   * what the "context" says about the semantics of the message, and
   * how the "message" then encodes data

---and I'll show you an equivalent definition of semantics for the
_standard_ signature API, the simpler API that doesn't have "context":
simply encode the same "context" information and the data together as
the "message" to be signed.

This use of the _standard_ signature system provides all of the same
protection against cross-protocol attacks that can possibly be provided
by the signature-plus-context system. What creates the protection is
_not_ the change of signature concept to include a separate "context";
what creates the protection is defining the semantics of the string
being communicated.

The huge advantage of this syntax choice is that it's compatible with
the signature API already used in specifications and papers and proofs
and libraries and the rest of the system. It preserves the familiar
signature layer that we already have. It minimizes the number of inputs
for signing and the complexity of the task facing the signature-system
auditor.

I hope I've now made sufficiently clear that I'm objecting---and why I'm
objecting---to the use of "contexts" and other side inputs in CFRG's
specifications of signature systems.

> The context label is explicitly in place in Ed448 in the current draft,

My objection applies equally to all signature systems with side inputs.

> needs to provide an API for it, yes.

This is considerable deployment hassle---and it's only the beginning of
the massive software upgrade that you'd need to actually make "context"
work. Remember that, e.g., PGP would need to accept "context" arguments
from any application processing PGP-signed messages, that those
applications would need to similarly allow "context" from higher-level
callers, etc. And then what happens if the applications, for whatever
reasons, think that they need to use traditional signature systems? Is
the "context" thrown away, allowing cross-protocol attacks? Or is it
encoded into the message, which is exactly what I'm saying should always
be done, and which doesn't need or want "context" in the signature spec?

Encoding the same information into traditional messages does just as
well in stopping cross-protocol attacks as a "context" side input can
possibly do. The API divergence is unnecessary and highly undesirable.

> We're actually doing exactly this in TLS 1.3, but doing it in an
> ad-hoc way

Do you have justification for using the loaded word "ad-hoc" here? It
should be obvious that part of the job of TLS is to adequately define
the semantics of its own signatures. It's not at all surprising that
these semantics are specific to TLS.

> goal here is one distinct context label per domain.

What's the "domain" for a PGP-signed message, interpreted by protocol X,
further interpreted by protocol Y, as meaning "Immediately sell all of
the stocks that I listed in my previous message"? Surely one needs to
include not just static protocol information but also something dynamic
such as the hash of the stock list or of the previous message.

> going to be interpreted in every other context.

This is a tough question of semantics, as I've been trying to explain.
Complicating the syntax---splitting "message" into "message" plus a
separate "context"---is of no value in tackling this question of
semantics. Meanwhile the costs of the new syntax are very clear.

> want it to happen, since that improves the overall safety of the internet.

Everyone agrees on trying to eliminate all possible confusion in the
semantics of signed messages, but the right way to do this is to
directly tackle the question of semantics, not to frivolously screw
around with the standard syntax for a signature system. You're saying
that you don't care about the syntax/layering/API issues; I _do_ care
and am very much opposed to changing the API.

---Dan

---

From: Natanael <[email-masked]>
Date: Sat, 23 Apr 2016 17:16:34 +0200

> possibly do. The API divergence is unnecessary and highly undesirable.

I'm just going to add a few more comments in addition to my reply from the
last time.

(And as always, anything of this complexity is unlikely to ever get
implemented, or implemented right for that matter. This is mostly a thought
experiment.)

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

Summary of how to define the context:

Track the path / branch taken through the code in the generation of the
signed message (identifying the software, the configuration / instance of
it, what it was that invoked the generation of the signature, which checks
the software went through to confirm it should be created, or whatever else
is important). Encode that with the message.

Document what each section of each code branch means, which paths are
valid, what exactly is authorized by any given path's signatures.

A code path that only covers acknowledgement of receipt obviously can't be
use to issue orders of action. Anything that parse the signed messages for
some given system must follow the documentation and must be able to
determine what exact actions a message authorizes. Ideally every type of
valid action should also be explicitly defined in the documentation, so
that this is possible to begin with.

The more I think of it, the more it resembles building a capabilities
oriented system. A bit like an adaption of Bitcoin pay-to-script-hash
transactions / Ethereum, where the system declares what conditions must be
fulfilled for every given action, and where the signed messages
(transactions) must prove the conditions were fulfilled. Take a look at
Bitcoin's Merkelized Abstract Syntax Trees (MAST) for a highly relevant
reference.
http://css.csail.mit.edu/6.858/2014/projects/jlrubin-mnaik-nityas.pdf

You shouldn't sign messages with this data structure without first
verifying it does what you want (to not fall for signature oracle attacks).
If everybody follows that advice, you can be sure that the signer intended
to create that particular message.

---

By my reading, it sounds like you'd rather see something like a specific
signature message input format, where you sign some structured data that
encode the message. (Perhaps we could use the new saltpack format, and
define some json / xml data structure for encoding contexts, etc.)

As for the comment on preventing (carelessly) stripping out the raw message
without further verification: encrypt the message with a key derived from
the metadata (the non-message parts of the data structure) and signature.
Yes, this too is likely to be bypassed by careless programmers, but at
least they should have come across an warnings against doing so when
reading the documentation on how to extract the message. It shouldn't end
up like this:
https://xkcd.com/1181/

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Sat, 23 Apr 2016 15:54:03 -0400

> waiting for as it is.  Redefining what they will get this late in the

My goal in raising this is not to delay the process further, but to at
least clarify for future readers why the interfaces for Ed25519 and
Ed448 differ by a "context" argument, and to give some form of
implementation guidance to people who want to use that argument while
being able to use both signature schemes.

A recent example is
https://tools.ietf.org/html/draft-ietf-curdle-dnskey-eddsa-00, which
defines DNSKEY records for both Ed25519 and Ed448.  I spoke to the
authors about using a context label to avoid RRSIGs from being re-usable
in non-RRSIG contexts.

Section 4 there now says:

  [...]
   EdDSA signatures in this scheme use the 17-octet context label
   'DNSSEC SIGNATURE\0' (where \0 represents a zero-valued octet).
   
   (Note: Only Ed448 has the Context specified.  Before publishing the
   final draft we need to specify what to do with Ed25519 Context.)

> shouldn't be a problem getting the document published as an RFC.

This will only further delay systems that want to use Ed25519; or it
will discourage people from even trying to distinguish between domains
that do use Ed25519 ("don't bother, unless you use Ed25519ctx instead").

As i wrote in my mail that started this thread, i'd be fine with just
the addition to the security considerations explaining the distinction
between the primitives, if that would get the draft out the door more
promptly.  I don't want this to drag on any longer than anyone else
does.

           --dkg

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Sat, 23 Apr 2016 16:19:03 -0400

Hi Dan--

>      not directly aimed at the core cross-protocol issue.

This seems to be saying that because domain separation by context labels
doesn't solve all conceivable cross-protocol issues (i agree it does
not) that we should not use it to address those issues that it does
solve.

Your PGP example is definitely correct.  The PGP signature would not
prevent collisions of multiple PGP messages with different
interpretations.  However, it *would* prevent a PGP signature from being
replayed as a signature on a TLS certificate verify message from the
same secret key (or a PKINIT message in krb5, etc)

>      and this traditional fix is much easier from a systems perspective.

i'm assuming that the "traditional fix" is just "incorporate a sane
context-specific bytestring into the message being signed".  And I
agree, it would be great if people did that.  But calling it a
"traditional fix" implies that there is a tradition of doing the right
thing here, and that's been inconsistent at best.

Do you have a better suggestion of how to formalize this practice than
giving protocol designers a place to put a distinct context?  I'd be
happy with other proposals that try to address the same issue.

Thanks for the thoughtful discussion,

     --dkg

---

From: Watson Ladd <[email-masked]>
Date: Sat, 23 Apr 2016 14:25:16 -0700

> promptly.  I don't want this to drag on any longer than anyone else

Systems actually deployed today are actually using signature systems
that don't have the context argument. The whole argument that we need
to reconsider what signatures are is fine: but it shouldn't stop us
from introducing a new signature scheme that meets the standard
definition.

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

---

From: David Jacobson <[email-masked]>
Date: Sat, 23 Apr 2016 15:28:17 -0700

> thing here, and that's been inconsistent at best.

A second traditional fix is "never use the same key for two different 
purposes".  And if the "general" in DBJ's story can't deal with many 
keys, then use a KDF to derive a key for each purpose from the general's 
key.  You can even have multi-level use of KDFs.  Once can be each 
semantic domain the general uses, and a second level can be for 
protocols (e.g. "PGP"), etc., as deep as you need to go.

This keeps the issue of domain separation independent of encryption APIs 
and algorithms.

     --David Jacobson