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

[Ilari Liusvaara <[e-mail]>]

On Fri, Apr 22, 2016 at 11:29:32AM -0400, Daniel Kahn Gillmor wrote:
> On Fri 2016-04-22 07:28:43 -0400, Ilari Liusvaara wrote:
> > 1) More vulernable to attacks there.
> 
> can you describe the attacks you're concerned about?
> 
> > 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.
> 
> 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.

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

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

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.

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

Yes, trivial existential forgeries. And attempts to look at how prefixing
the context into inner hash would fare turned into mess.
 
> 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.

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