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

Daniel Kahn Gillmor <> Wed, 20 April 2016 21:41 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 26D7A12E983; Wed, 20 Apr 2016 14:41:33 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.9
X-Spam-Status: No, score=-1.9 tagged_above=-999 required=5 tests=[BAYES_00=-1.9] autolearn=ham autolearn_force=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id gJKYlafcohUe; Wed, 20 Apr 2016 14:41:31 -0700 (PDT)
Received: from ( []) by (Postfix) with ESMTP id 716FE12E7C4; Wed, 20 Apr 2016 14:41:31 -0700 (PDT)
Received: from (unknown []) by (Postfix) with ESMTPSA id 6E4BFF991; Wed, 20 Apr 2016 17:41:28 -0400 (EDT)
Received: by (Postfix, from userid 1000) id 54A381FFE0; Wed, 20 Apr 2016 17:41:28 -0400 (EDT)
From: Daniel Kahn Gillmor <>
To: Ilari Liusvaara <>
In-Reply-To: <>
References: <> <> <> <> <> <> <>
User-Agent: Notmuch/0.21+128~g620f892 ( Emacs/24.5.1 (x86_64-pc-linux-gnu)
Date: Wed, 20 Apr 2016 17:41:28 -0400
Message-ID: <>
MIME-Version: 1.0
Content-Type: text/plain
Archived-At: <>
Cc: Robert Edmonds <>, "" <>, "" <>, Ondřej Surý <>, "Kaduk, Ben" <>, Martin Thomson <>
Subject: Re: [Cfrg] draft-irtf-cfrg-eddsa -- one final proposal for domain separation (context labels) for ed25519
X-Mailman-Version: 2.1.17
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Wed, 20 Apr 2016 21:41:33 -0000

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?