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

From: Simon Josefsson <[email-masked]>
Date: Fri, 06 May 2016 09:03:47 +0200

Daniel Kahn Gillmor <[email-masked]> writes:

> 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.

Hi Daniel, all,

I agree that is a good goal -- if you can think of text to explain this
difference I would support that it is added.

> 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.

Instead of introducing complexity (i.e., contexts), I suggest that you
recommend to not re-use the same key for different purposes!

Key re-use for different purposes is the fundamental problem as I see
it.  The idea behind context may have good intentions, but I believe
contexts is only a band-aid for the problem of cross-domain key-reuse,
and I believe that overall contexts introduce more harm than they
address.  I believe it is better to address the problem at its source.

>> 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.
>
> This will only further delay systems that want to use Ed25519

How so?

> or it will discourage people from even trying to distinguish between
> domains that do use Ed25519 ("don't bother, unless you use Ed25519ctx
> instead").

My point is that it is a bad idea to attempt to distinguish between
domains.

> 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.

Thanks -- and I agree text like that would be good.  Sorry I didn't
catch this in your first email, I read it as a request to add contexts
to Ed25519.

Thanks,
/Simon

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 6 May 2016 13:17:33 +0300

> address.  I believe it is better to address the problem at its source.

Actually, the problem is that context have serious fundamential usabilty
problems.

If you have self-inconsistent protocol, nothing will save you. However,
contexts suffer from serious usability problems (API and signature
layering), making them effectively unusable, even with protocols that
are self-consistent.

So yeah, just use separate keys. Don't cause problems for everybody
by using contexts.

-Ilari

---

From: Martin Thomson <[email-masked]>
Date: Mon, 9 May 2016 10:23:31 +1000

> So yeah, just use separate keys. Don't cause problems for everybody

As an author of a document that defines the use of contexts, how do
you reconcile this view with what the document says?

I agree with the idea that there is a moral superiority in using
different keys.  That's an inarguable statement from a position of
great integrity.

djb's one-bit protocol examples highlight that there is an inherent
futility in attempting domain isolation at any layer of a protocol
stack that might conceivably be used in support of some high-layer
protocol.

But I see those examples as illustrative of an insufficient degree of
redundancy.  For, if ever there were fans of redundancy, it would be
the military.  While conceivably you could build a protocol that
defers all self-identification and context to the crypto that supports
it, in the cases illustrated, it shows itself as unwise in the extreme
in light of the propensity of people to do bad things.

We find that reuse of signature keys for different purposes is rife in
the real world.  A firm requirement of TLS 1.3 is that existing keys
can be used with the new protocol.  It would not deploy otherwise, and
yet we endorse that which we all agree to be a sin and do what we can
to avoid problems.

When signature keys are used to identify, I predict that they will
definitely be misused in this fashion.  I've seen it many times
already, and don't imagine that any edict from the CFRG will change
that.

I disagree with the notion of there being "serious" or "fundamental"
usability problems.  You are correct in that these are not perfect
bijective mappings from one domain to another, particularly when there
are existing users of the signature scheme.  However, you are
perfectly reasonable in noting that people are using Ed25519 and so
suggesting that they instead use some newly defined Ed25519ctx for
some marginal benefit (domain separation) is not in their interests.

Take the suggestion for what it is: a backstop for when good sense fails.

---

From: Ilari Liusvaara <[email-masked]>
Date: Mon, 9 May 2016 10:09:48 +0300

> you reconcile this view with what the document says?

To actually use contexts, you need a way to do contexts all the way
up to lowermost common layer, which might very well be the signature
primitive itself. This impiles that all the needed contexts exist
and can be specified via an API (existing ones don't support it!).
 
At the level of raw signatures, this would imply defining abstract
API model and then having all context-capable signatures, either
obtained by transforming non-context-capable scheme (the transform
is too trivial to contain here) or having natively context-capable
schemes.

And then the protocol itself needs to be self-consistent. But that
is needed anyway (and is harder requirement than one might think).

Here's one abstract API model of signature scheme with contexts:

keygen: () -> (privkey, pubkey)
sign: (privkey, context<0..255>, message<0..>) -> signature
verify: (pubkey, context<0..255>, message<0..>, signature) -> boolean

With correctness (it verifies its own signatures) and unforgeability
(can't compute signatures for (context,message) one hasn't seen
without private key).

The algorithms can be random.

> stack that might conceivably be used in support of some high-layer

Well, nothing prevents having multiple contexts at different levels,
but all contexts involved need to be able to be specified to be
correct.

E.g. openpgp -> git-push-signature. That's not interchangeable with
git-push-signature nor openpgp.
 
> yet we endorse that which we all agree to be a sin and do what we can

Also, TLS keys get reused in CSR signing, and CSRs are based upon ASN.1,
which is let's say pretty different from TLS syntax...

> usability problems. 

The reason for those usability problems: APIs and what is offered.

-Ilari

---

From: Benjamin Kaduk <[email-masked]>
Date: Mon, 9 May 2016 23:04:20 -0400 (EDT)

> and can be specified via an API (existing ones don't support it!).

I'm still not conviced that we're all talking about the same thing when we
say "context".

The two different "context"s I've seen talked about are:

(1) Ed448ctx-style, as an "extra signature input" that is mixed into the
signature in a way that prevents shifting content from the context input
to the data input of the signature algorithm (or vice versa).

(2) "flat"-style, as in "a string that is prepended or appended to the
data to be signed" that provides only partial domain-separation but can be
bolted on to existing signature algorithms post-facto.  (E.g., as in
https://github.com/unicorn-wg/context-labels)

Clearly your statement is true for (1)-style contexts, but it seems that
for (2)-style contexts, any participant in the call chain could choose to
conver the context into part of the signature input and thereby translate
from a context-ful API to a context-free one.

> is too trivial to contain here) or having natively context-capable

And here we get into all the complications that makes djb dislike extra
inputs to signature algorithms (and rightly so).

> is needed anyway (and is harder requirement than one might think).

For fully provable security properties, sure.

> git-push-signature nor openpgp.

prepending "git-push-signature" || 0 || "openpgp" || 0 to the data to be
signed (as in my (2) above) seems naturally composable.

> The reason for those usability problems: APIs and what is offered.

I agree that for (1), the API situation is a mess and there are not any
currently usable library APIs.

My question is, what are the downsides of (2)?  It can perhaps offer a
false sense of security to protocol designers and/or implementors that
ought to be using separate keys, but if we spin it as something to be used
in addition to key separation, maybe it's not so bad.  Are there other
disadvantages of (2)?

-Ben

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 10 May 2016 09:29:19 +0300

> to the data input of the signature algorithm (or vice versa).

And there is a transform that obtains signature scheme with contexts from
scheme without one. Obviously not needed if scheme already has contexts.

> https://github.com/unicorn-wg/context-labels)

That is just broken. You can not add signature-level contexts into
existing signature scheme without obtaining a new scheme. At least not
reliably, which in cryptography means the same as not at all.

> from a context-ful API to a context-free one.

And looks like I got the layers wrong way around, it should have been
"uppermost common layer".

But basically, if you need contexts, you require them. Anything else is
just too error-prone.

EdDSA spec says not to use signature-level key-binding, even if it works
just fine with EdDSA. The reason why is that there are many _other_
signature schemes where signature-level key-binding utterly fails.

> inputs to signature algorithms (and rightly so).

Well, the alternatives besides just giving different keys to things that
aren't known to play well together are even worse.
 
> signed (as in my (2) above) seems naturally composable.

Well, this is about contexts at different layers (if multiple layers have
contexts). Then all have to match.

And if so, then it is unlikely to be implemented via such prepend.

> currently usable library APIs.

And thus contexts are currently unusable, as such APIs are prerequisite
for usage of contexts.

> in addition to key separation, maybe it's not so bad.  Are there other

That kind of construction is just a minefield.

-Ilari

---

From: Simon Josefsson <[email-masked]>
Date: Tue, 10 May 2016 11:16:03 +0200

> you reconcile this view with what the document says?

Hi Martin.

The difference between personal opinion and group consensus decisions?
I'm just speculating what Ilari's reasons are though.

> in light of the propensity of people to do bad things.

I suspect there is fundamental disagreement between fans of redundancy
and fans of lesser complexity.

In my experience, redundancy (=complexity) in security systems have too
many time been used as a way to get through the system.  Redundancy can
act as a slowdown factor and mitigator, but if your primitives are weak
then you are vulnerable no matter what.  The academic optimistic view
appears to be that it should be possible to find strong primitives, and
to trust that they are strong.  History shows that everything is broken
eventually, but history hasn't killed the optimism.

My thoughts are that it is possible to achieve what the proponents of
redundancy (contexts) want and please the people who want the least
complexity, at the same time.  Just define a low-level primitive like
Ed25519 as it is, and deal with higher-level aspects like
cross-protocol/domain mitigators at the protocol level, or at another
crypto primitive (ed25519ctx) which can be opt-in by the people who have
drunk that particular Kool-Aid.

Thanks,
/Simon

---

From: Watson Ladd <[email-masked]>
Date: Tue, 10 May 2016 08:42:49 -0700

> eventually, but history hasn't killed the optimism.

Let's consider an actual protocol, TLS 1.3. TLS 1.3 cannot rely on the
context mechanism of Ed25519ctx because it must work with RSA
signatures as well. Introducing contexts won't actually make it more
secure so long as it has to work with RSA. But introducing contexts
will force everyone to complicate their implementation, which we know
leads to bugs.

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

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

---

From: Martin Thomson <[email-masked]>
Date: Wed, 11 May 2016 10:46:01 +1000

On 10 May 2016 at 19:16, Simon Josefsson <[email-masked]> wrote:
> Just define a low-level primitive like

That's fine with me.  And my original intent.  I realize that this
thread appears to be an attack on the eddsa draft; I don't think that
was the intent, it certainly wasn't mine.  The confusing inconsistency
was a problem.

---

From: Martin Thomson <[email-masked]>
Date: Wed, 11 May 2016 10:47:30 +1000

On 11 May 2016 at 01:42, Watson Ladd <[email-masked]> wrote:
> TLS 1.3 cannot rely on the
> signatures as well.

That's not strictly true.  It can use contexts opportunistically: if
present, use it, otherwise use this alternative, crappier arrangement
for the signature input.

---

From: Bryan Ford <[email-masked]>
Date: Sat, 21 May 2016 11:43:33 +0200

I see after a long absence that I missed a new flare-up of the Great Context Debate (tm). :)

When I originally proposed the hashing scheme that included contexts for Ed448, I brought up this Ed25519 backward-compatibility issue, and suggested a few alternatives, at least one of which as I recall was similar to DKG’s suggestion.

At any rate, I agree with DKG and others that it would be nice for the RFC to specify a way to deal with an *optional* context parameter for Ed25519 - for consistency with Ed448 if nothing else - while preserving Ed25519 backward compatibility when the context parameter is missing/empty.  No one is forced to use it, but having it in the RFC - and in the APIs of implementations that choose to support it - both makes the RFC more self-consistent and offer a small robustness benefit to new protocols that decide to use contexts.

While the same domain-separation benefit can always be achieved by just prefixing the message, having an explicit context parameter in an API forces the software developer who’s calling that API to see it, and think “do I need to pass something there? what? should I ask a colleague?”  Whereas it’s much easier (essentially trivial) to “forget” to decide to prefix a signed message with something, especially if you’re not a crypto-geek and never heard that you were supposed to.  TLS won’t use contexts, and that’s fine, bit TLS isn’t the relevant “customer” here.  The “customer” is all the possible users of Ed25519 that are *not* nearly so widely-analyzed as TLS.

Yes, key-separation practices are good too, but do not substitute for the domain-separation that contexts can provide, because relying on key-separation exposes message-confusion risks at much higher levels of the “protocol stack” where key management occurs.  If an IETF protocol or proprietary application protocol is designed to use of a context, then any properly-functioning software implementing that protocol will enforce that domain-separation independently of how well or badly users or administrators might manage their keys.  Contexts provide a way for the protocol and software developer to enforce domain separation, whereas key-separation in many environments is something users and administrators have to do.  As others have stated, it’s about redundancy: no one is saying key-separation is bad, but encouraging the use of both reduces the chance of something going critically wrong at *both* levels (protocol design/implementation and key management).

In terms of how exactly to specify a backward-compatible context mechanism for Ed25519, I would certainly support DKG’s specific proposal where context may be empty) as offering a reasonable balance between simplicity and domain-separation goals.  But just to explore a couple slightly different variants with slightly different tradeoffs:

1. DKG’s proposal (baseline): mainly just change H(x) in Table 1 to H(context || x), where context may be empty for backward-compatibility.

2. Change the H(x) line in Table 1 to:

   |    H(x)   | SHA-512(x) [RFC4634] if ctx is empty               |
   |    H(x    | SHA-512(len(ctx) || ctx || x) if ctx is nonempty   |

Advantage: stronger domain separation, ensuring any use that specifies a context is domain-separated from any use that does not.
Downside: slightly more complex specification and code (one ‘if’ statement), though this bit of complexity is hidden from callers of the Ed25519 API.

3. Change the H(x) line in Table 1 to:

   |    H(x)   | SHA-512(len(context)^len(context) || context || x) [RFC4634]    |
…that is, the prefix is L consecutive bytes having value L, where L is the length of the context string, followed by the context and x.  So:

- empty context: H(x) is SHA-512(x)
- context = “foo”: H(x) is SHA-512(“\3\3\3foo” || x)
- context = “blah”: H(x) is SHA-512(“\4\4\4\4blah” || x)

Advantage: eliminates the need for a special-case (the ‘if’ statement) for backward compatibility, while providing the same stronger domain-separation of alternative #2 above.
Downside: doubles the effective size of the context-prefix to process.  But I can’t imagine this mattering in any practical scenario, especially since contexts are expected to be short strings.

Cheers
Bryan

---

From: Watson Ladd <[email-masked]>
Date: Sat, 21 May 2016 11:46:05 +0200

> present, use it, otherwise use this alternative, crappier arrangement

But all the messages need to fit that "alternative, crappier" arrangement
anyway. Contexts don't give extra protection to protocols that must work
without them.

---

From: "Dang, Quynh (Fed)" <[email-masked]>
Date: Sat, 21 May 2016 10:18:52 +0000

#3 is a clever idea.

Regards,
Quynh. 

________________________________________
From: Cfrg <[email-masked]> on behalf of Bryan Ford <[email-masked]>
Sent: Saturday, May 21, 2016 5:43 AM
To: Daniel Kahn Gillmor
Cc: Robert Edmonds; [email-masked]; [email-masked]; Ondřej Surý; Benjamin Kaduk
Subject: Re: [Cfrg] draft-irtf-cfrg-eddsa -- one final proposal for domain separation (context labels) for ed25519

Cheers
Bryan

---

From: "D. J. Bernstein" <[email-masked]>
Date: 21 May 2016 13:57:44 -0000

Bryan Ford writes:
> While the same domain-separation benefit can always be achieved by
> just prefixing the message, having an explicit context parameter in an
> API forces the software developer who’s calling that API to see it,
> and think “do I need to pass something there? what? should I ask a
> colleague?”

And so they copy and paste code from somewhere else, or (if they're in
control of both ends) try the empty string, which works, the same way
that most protocols built on top of DNS are identified in DNS as "TXT".
How do you imagine most programmers being successfully pressured to
create a new "context" whenever the message semantics change: library
revisions, for example, or state modified by previous messages?

If you think you're solving the fundamental cross-protocol security
problems that I described in "Side inputs to signature systems, take 2",
then let me suggest that you follow up in detail to that message. I see
your proposed bottom-to-top API revision as a distraction from the core
task of developing secure message semantics.

We already have too many file-type systems. Most of them were designed
out of complete disregard for previous work; we definitely don't need
more of these. Efforts to define semantics via oversimplified metadata
tags (DOS file types, for example, and MIME types) have always ended up
being supplemented by more flexible mechanisms to define semantics
inline (MP4, for example, and XML). People build software-dispatch
mechanisms around metadata tags and then end up having to build more
flexible software-dispatch mechanisms to handle subtypes declared
inline. Programmers are constantly fighting multiple API layers for
something that could and should have been handled with just one layer.

>From a security perspective there's even more importance to specifying
semantics clearly; it's even more clear that these semantics depend on
application-specific dynamic context; and we _definitely_ don't want
unnecessarily complicated APIs. Separate tags have historically proven
to be inferior to inline mechanisms in all of these dimensions.

---Dan

---

From: Bryan Ford <[email-masked]>
Date: Sat, 21 May 2016 16:36:07 +0200

Hi Dan, 

On May 21, 2016, at 3:57 PM, D. J. Bernstein <[email-masked]> wrote:
> that most protocols built on top of DNS are identified in DNS as "TXT”.

Even if they just to that, then that’s better than if there was no context parameter.  The subset of developers who just copy-and-paste a “TXT” context parameter for one set of applications (likely related, since they’re more likely to copy-and-paste from a similar application than a completely unrelated application) will be domain-separated from the subset of developers who copy-and-paste a “FOO” context parameter in another set of applications, and from the developers who copy-and-paste a “BAR” context parameter in a third class of applications.  Whereas without the context parameters, there will be no domain separation and the risk of signature confusion is strictly worse than if there were no context parameters.

Further, in any IETF-defined protocol in the future that specifies that the context parameter must be “FOO”, any demonstrably interoperable implementation of that protocol will have to use that context parameter, because an implementation that doesn’t will fail to interoperate in a completely obvious way.  Thus, if the IETF defines the Foo protocol to use “FOO” as the contexts in its signatures, and the Bar protocol is defined to require “BAR” to be used as the context in its signatures, then the FOO and BAR domains will effectively be enforced via the IETF process, leaving it not even up to the application developers.  Of course developers of different Foo implementations will probably still copy-and-paste code that creates “FOO”-context signatures from other implementations of the Foo protocol, but that’s fine.

> revisions, for example, or state modified by previous messages?

I never suggested that, and I don’t remember seeing anyone else here suggesting that.  In fact I don’t remember hearing anyone suggesting that programmers be “pressured” to do anything in particular with contexts.

> task of developing secure message semantics.

Looking up the message you’re referring to, it looks to me like you’re way overthinking this.  

Yes, you could turn the context into a hierarchical filesystem-like namespace if you want, e.g., with “FOO/V1” versus “FOO/V2” being V1-type versus V2-type signatures for protocol or application FOO.  One of the nice things about variable-length strings is that they’re automatically composable, up to the 255-byte limit.  Protocol developers - or other IETF WGs that need to use signatures and need to specify what the “context” should be for those signatures - are free to consider fancy hierarchical schemes like that if they want.  Or not.  The EdDSA RFC need not and should not mandate that or any particular scheme for choosing context strings.  Leave that to those who build applications or protocols that use signatures.  If you don’t want context strings at all in your next application or protocol, then fine, don’t use them (i.e., use the empty string).  No Context Police SWAT team is going to bash down your door and haul you in to the face the Inquisition.

Nobody that I see is proposing that contexts “solve” any “fundamental cross-protocol security problems”.  All they are intended to do is add a bit of (weak, but preferably redundant) protection against certain classes of message-confusion blunders at a software engineering level.

Bryan

---

From: Richard Outerbridge <[email-masked]>
Date: Sat, 21 May 2016 12:27:40 -0400

> On 2016-05-21 (142), at 09:57:44, D. J. Bernstein <[email-masked]> wrote:
> 
> Bryan Ford writes:

So, in general, I gather, you’re saying that added complexity is not
simply strictly unnecessary but actually dangerous?  Go figure!
__outer

---

From: "D. J. Bernstein" <[email-masked]>
Date: 23 May 2016 08:22:30 -0000

Bryan Ford writes:
> better than if there was no context parameter.

Applications that share keys are very likely to copy this parameter, for
the same reasons that they pretty much always end up copying MIME types.
The benefits you're referring to are limited to cases where applications
share keys but manage to stick _more_ information into this parameter
than they would have stuck into the message itself.

Meanwhile everyone ends up suffering through bottom-to-top complications
in the signature API. This is, in particular, a drag on auditing, and
it's going to end up taking resources away from auditing and fixing the
hard cases of cross-protocol attacks, very much the same way that a pile
of well-intentioned complications to the X.509 certificate format ended
up taking resources away from what we _need_ to do with certificates.

> in any IETF-defined protocol in the future that specifies that the
> context parameter must be “FOO”

The IETF-defined protocols can just as easily use prefixes---in fact,
more easily, because then they simply work with _all_ signature systems
rather than just systems supporting the committee API.

Nobody is objecting to having signature users coordinate message
semantics (especially if they're sharing keys!). Nobody is objecting to
having a central registry of prefixes. But this doesn't need a new API,
and there are many other reasons to object to a new API.

---Dan