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

Benjamin Kaduk <kaduk@MIT.EDU> Thu, 21 April 2016 18:31 UTC

Return-Path: <kaduk@mit.edu>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id EF64612E851; Thu, 21 Apr 2016 11:31:15 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -5.197
X-Spam-Level:
X-Spam-Status: No, score=-5.197 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_MED=-2.3, RP_MATCHES_RCVD=-0.996, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 3THLgNd9VG0h; Thu, 21 Apr 2016 11:30:59 -0700 (PDT)
Received: from dmz-mailsec-scanner-8.mit.edu (dmz-mailsec-scanner-8.mit.edu [18.7.68.37]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 4191712EB10; Thu, 21 Apr 2016 11:30:59 -0700 (PDT)
X-AuditID: 12074425-c6bff70000005f72-41-57191c6228eb
Received: from mailhub-auth-1.mit.edu ( [18.9.21.35]) (using TLS with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client did not present a certificate) by (Symantec Messaging Gateway) with SMTP id B9.25.24434.26C19175; Thu, 21 Apr 2016 14:30:58 -0400 (EDT)
Received: from outgoing.mit.edu (outgoing-auth-1.mit.edu [18.9.28.11]) by mailhub-auth-1.mit.edu (8.13.8/8.9.2) with ESMTP id u3LIUuur032358; Thu, 21 Apr 2016 14:30:57 -0400
Received: from multics.mit.edu (system-low-sipb.mit.edu [18.187.2.37]) (authenticated bits=56) (User authenticated as kaduk@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.8/8.12.4) with ESMTP id u3LIUp0v009671 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT); Thu, 21 Apr 2016 14:30:54 -0400
Received: (from kaduk@localhost) by multics.mit.edu (8.12.9.20060308) id u3LIUoND026561; Thu, 21 Apr 2016 14:30:50 -0400 (EDT)
Date: Thu, 21 Apr 2016 14:30:50 -0400
From: Benjamin Kaduk <kaduk@MIT.EDU>
To: Ilari Liusvaara <ilariliusvaara@welho.com>
In-Reply-To: <20160421043947.GA24394@LK-Perkele-V2.elisa-laajakaista.fi>
Message-ID: <alpine.GSO.1.10.1604211349530.26829@multics.mit.edu>
References: <87bn543id1.fsf@alice.fifthhorseman.net> <D33CFF00.6A70D%kenny.paterson@rhul.ac.uk> <11c960b5f1fa42aaaf4cd0a6961332ec@usma1ex-dag1mb1.msg.corp.akamai.com> <87ziso1m0l.fsf@alice.fifthhorseman.net> <20160420142953.GA23528@LK-Perkele-V2.elisa-laajakaista.fi> <87potk1de7.fsf@alice.fifthhorseman.net> <20160420182617.GA23652@LK-Perkele-V2.elisa-laajakaista.fi> <87bn540xh3.fsf@alice.fifthhorseman.net> <20160421043947.GA24394@LK-Perkele-V2.elisa-laajakaista.fi>
User-Agent: Alpine 1.10 (GSO 962 2008-03-14)
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset="US-ASCII"
X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFprNKsWRmVeSWpSXmKPExsUixCmqrJskIxlu8PsZp0Xj5kZWi6O72lgs Wrs/M1lcX/eU3eLftseMFu93T2exuHbmH6PF9d1PmRw4PCYfWcDs8attLrPH2e52Vo+ds+6y eyxZ8pPJ48LhHmaP291z2ALYo7hsUlJzMstSi/TtErgyjnS9YS5YIVWxp/kKUwPjM5EuRk4O CQETiaX/tjB1MXJxCAm0MUncOfGFDcLZyCixa88vKOcQk8Sjm8+YIZwGRonzXYsZQfpZBLQl +h5tYgGx2QRUJGa+2cgGYosI6EkcX3eRFaSBWeA7k8TE42eYQRLCAiUSJ+aeBCviFPCQeH7v PVgzr4CjxII3exkhNlxnlrjxaxlYkaiAjsTq/VOgigQlTs58AmYzC2hJLJ++jWUCo8AsJKlZ SFILGJlWMcqm5Fbp5iZm5hSnJusWJyfm5aUW6Vro5WaW6KWmlG5iBMUBu4vqDsY5f70OMQpw MCrx8HLIS4QLsSaWFVfmHmKU5GBSEuVlY5EMF+JLyk+pzEgszogvKs1JLT7EKMHBrCTCGyMB lONNSaysSi3Kh0lJc7AoifMyMjAwCAmkJ5akZqemFqQWwWRlODiUJHgZpYEaBYtS01Mr0jJz ShDSTBycIMN5gIY7SoEMLy5IzC3OTIfIn2JUlBLntQNJCIAkMkrz4HrBaWo3k+orRnGgV4R5 zUBW8ABTHFz3K6DBTECD+e+KggwuSURISTUw+ujvmz1B2pqp8djUoMlvvy4uvsk01d0i92bj 1MdN5hF+DXabVfY7sD2Z86uAm2ciw5Hs2wdq99x5xZ4j/ez+pOSd91fMCFnAxHox28anQrHu QJXZJ0YDzdXRyZxbllfHxs5+OXNTxYG57Jbzz/zYKhiYzKP7+e3mF7X8byf+PszVfZ9zh0eo lhJLcUaioRZzUXEiAGDZEbcuAwAA
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/eaua91C7zgvtevYX8cS3MoOXhck>
Cc: "draft-irtf-cfrg-eddsa.all@ietf.org" <draft-irtf-cfrg-eddsa.all@ietf.org>, Robert Edmonds <edmonds@debian.org>, "cfrg@ietf.org" <cfrg@ietf.org>, Ondřej Surý <ondrej@sury.org>, "Kaduk, Ben" <bkaduk@akamai.com>
Subject: Re: [Cfrg] draft-irtf-cfrg-eddsa -- one final proposal for domain separation (context labels) for ed25519
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.17
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Thu, 21 Apr 2016 18:31:17 -0000

On Thu, 21 Apr 2016, Ilari Liusvaara wrote:

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

I think I'm confused.  Surely if I set chunk = { 'a', 'b', 'c', 'd', 'e',
'f'} containing six octets, then SHA-512(chunk) is the same, whether I
construct chunk from 'abc','def' or 'abcd','ef'.  So you must be talking
about something else, but I'm not sure what.

> It is also not possible to compute the result using stock Ed25519 code
> with any non-empty context.

Can you be more specific?  Is the complaint just that one would need to
use a temporary buffer and copy the data to be signed in order to put in
the prefix?

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

>From where I am sitting, it seems like there are two options: does the
signing API include a context input?  If yes, use that input; if no,
prepend the context to the message to be signed in my own code.  What am I
missing?

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

I am mostly inclined to agree, which gives some useful flexibility here.

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

Sure.

-Ben