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

[Ilari Liusvaara <[e-mail]>]

On Wed, Apr 20, 2016 at 05:41:28PM -0400, Daniel Kahn Gillmor wrote:
> On Wed 2016-04-20 14:26:17 -0400, Ilari Liusvaara wrote:
> > On Wed, Apr 20, 2016 at 11:57:36AM -0400, Daniel Kahn Gillmor wrote:
> >> On Wed 2016-04-20 10:29:53 -0400, Ilari Liusvaara wrote:
> >> > Also, anyone up to some quick analysis to show that doesn't interact
> >> > 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" ?
> >
> > 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?
> 
> 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.

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.

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

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

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

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.

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

There is absolutely no working way to apply contexts using stock Ed25519
implementations that isn't utterly broken.
 
> >> > Also, that wouldn't solve the troublesome interaction between Ed25519
> >> > and Ed25519ph...
> >> 
> >> That's true, this proposal doesn't try to solve that problem.  I hope it
> >> 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).
> 
> 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?

I don't think Ed25519ph needs backward compatiblity.

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

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


-Ilari