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

[Daniel Kahn Gillmor <[e-mail]>]

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.

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.

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

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

   --dkg