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

Benjamin Kaduk <kaduk@MIT.EDU> Tue, 10 May 2016 03:04 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 1B03E12D138; Mon, 9 May 2016 20:04:30 -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 LtvUWzExwYAt; Mon, 9 May 2016 20:04:27 -0700 (PDT)
Received: from dmz-mailsec-scanner-1.mit.edu (dmz-mailsec-scanner-1.mit.edu [18.9.25.12]) (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 2389E12D098; Mon, 9 May 2016 20:04:26 -0700 (PDT)
X-AuditID: 1209190c-12fff7000000490a-57-57314fb908d8
Received: from mailhub-auth-3.mit.edu ( [18.9.21.43]) (using TLS with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client did not present a certificate) by (Symantec Messaging Gateway) with SMTP id CC.B7.18698.9BF41375; Mon, 9 May 2016 23:04:25 -0400 (EDT)
Received: from outgoing.mit.edu (outgoing-auth-1.mit.edu [18.9.28.11]) by mailhub-auth-3.mit.edu (8.13.8/8.9.2) with ESMTP id u4A34O43018292; Mon, 9 May 2016 23:04:25 -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 u4A34KTr004322 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT); Mon, 9 May 2016 23:04:23 -0400
Received: (from kaduk@localhost) by multics.mit.edu (8.12.9.20060308) id u4A34KRo003924; Mon, 9 May 2016 23:04:20 -0400 (EDT)
Date: Mon, 9 May 2016 23:04:20 -0400 (EDT)
From: Benjamin Kaduk <kaduk@MIT.EDU>
To: Ilari Liusvaara <ilariliusvaara@welho.com>
In-Reply-To: <20160509070948.GA5360@LK-Perkele-V2.elisa-laajakaista.fi>
Message-ID: <alpine.GSO.1.10.1605092210490.26829@multics.mit.edu>
References: <87bn543id1.fsf@alice.fifthhorseman.net> <87zisk94bg.fsf@latte.josefsson.org> <871t5wxfs4.fsf@alice.fifthhorseman.net> <87d1ozvfak.fsf@latte.josefsson.org> <20160506101733.GA2552@LK-Perkele-V2.elisa-laajakaista.fi> <CABkgnnVDDoh1t-GA54b31X9GVGTyFHtjNjEhzMaGdCHkFNNO6g@mail.gmail.com> <20160509070948.GA5360@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+NgFvrFIsWRmVeSWpSXmKPExsUixCmqrbvT3zDc4OY8M4uju9pYLK6ve8pu 8X73dBaLa2f+MVrc23KJ3YHVY+esu+weS5b8ZPKYeeYiu8ft7jlsASxRXDYpqTmZZalF+nYJ XBlPzz5mLjilXLFm7kOWBsajMl2MnBwSAiYSDz4fYuxi5OIQEmhjkvi59xgbhLOBUeLDmnvs EM5BJokVb7pZQVqEBOolJt5rYASxWQS0JG5seMgOYrMJqEjMfLORDcQWEdCTOL7uIitIM7PA TEaJXRObwRqEBUokTsw9CVTEwcEp4C5x/68KSJhXwFGi8+4xdoj5T5gkdr0QALFFBXQkVu+f wgJRIyhxcuYTMJsZaO/y6dtYJjAKzEKSmoUktYCRaRWjbEpulW5uYmZOcWqybnFyYl5eapGu oV5uZoleakrpJkZwEEvy7GA888brEKMAB6MSD+8OLsNwIdbEsuLK3EOMkhxMSqK8rox64UJ8 SfkplRmJxRnxRaU5qcWHGCU4mJVEeNPdgMp5UxIrq1KL8mFS0hwsSuK8hftPhwkJpCeWpGan phakFsFkZTg4lCR4Xf2AGgWLUtNTK9Iyc0oQ0kwcnCDDeYCGnwCp4S0uSMwtzkyHyJ9iVJQS 5w0GSQiAJDJK8+B6wUlmN5PqK0ZxoFeEeT+DVPEAExRc9yugwUxAg+XY9EEGlyQipKQaGPd/ MBavVP3XO3fGq9Czf+oZShgbGPcpCb64xGl/xPh4MJfs1SOu/+zdJpYmr024WBk6yy5DSmJD 9qU/9ZVq0aeS2hXsm6ZNXLKcwWqdxPmyI5nnbR1ZFij+urzgPeMrnfUart93bVh76iLz5/5P VSfq/LS4yvZ22czVkxNw5LKcJWE4T8zzuRJLcUaioRZzUXEiALF/IQcNAwAA
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/hhwnLYhXjCYJrjBeWcSUJKwMMmc>
Resent-From: <alias-bounces@ietf.org>
Resent-To: @ietf.org
Cc: Simon Josefsson <simon@josefsson.org>, cfrg@ietf.org, draft-irtf-cfrg-eddsa.all@ietf.org
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: Tue, 10 May 2016 03:04:30 -0000

On Mon, 9 May 2016, Ilari Liusvaara wrote:

> On Mon, May 09, 2016 at 10:23:31AM +1000, Martin Thomson wrote:
> > On 6 May 2016 at 20:17, Ilari Liusvaara <ilariliusvaara@welho.com> wrote:
> > >
> > > So yeah, just use separate keys. Don't cause problems for everybody
> > > by using contexts.
> >
> > As an author of a document that defines the use of contexts, how do
> > you reconcile this view with what the document says?
>
> To actually use contexts, you need a way to do contexts all the way
> up to lowermost common layer, which might very well be the signature
> primitive itself. This impiles that all the needed contexts exist
> and can be specified via an API (existing ones don't support it!).

I'm still not conviced that we're all talking about the same thing when we
say "context".

The two different "context"s I've seen talked about are:

(1) Ed448ctx-style, as an "extra signature input" that is mixed into the
signature in a way that prevents shifting content from the context input
to the data input of the signature algorithm (or vice versa).

(2) "flat"-style, as in "a string that is prepended or appended to the
data to be signed" that provides only partial domain-separation but can be
bolted on to existing signature algorithms post-facto.  (E.g., as in
https://github.com/unicorn-wg/context-labels)

Clearly your statement is true for (1)-style contexts, but it seems that
for (2)-style contexts, any participant in the call chain could choose to
conver the context into part of the signature input and thereby translate
from a context-ful API to a context-free one.

> At the level of raw signatures, this would imply defining abstract
> API model and then having all context-capable signatures, either
> obtained by transforming non-context-capable scheme (the transform
> is too trivial to contain here) or having natively context-capable
> schemes.

And here we get into all the complications that makes djb dislike extra
inputs to signature algorithms (and rightly so).

> And then the protocol itself needs to be self-consistent. But that
> is needed anyway (and is harder requirement than one might think).

For fully provable security properties, sure.

> Here's one abstract API model of signature scheme with contexts:
>
> keygen: () -> (privkey, pubkey)
> sign: (privkey, context<0..255>, message<0..>) -> signature
> verify: (pubkey, context<0..255>, message<0..>, signature) -> boolean
>
> With correctness (it verifies its own signatures) and unforgeability
> (can't compute signatures for (context,message) one hasn't seen
> without private key).
>
> The algorithms can be random.
>
> > I agree with the idea that there is a moral superiority in using
> > different keys.  That's an inarguable statement from a position of
> > great integrity.
> >
> > djb's one-bit protocol examples highlight that there is an inherent
> > futility in attempting domain isolation at any layer of a protocol
> > stack that might conceivably be used in support of some high-layer
> > protocol.
>
> Well, nothing prevents having multiple contexts at different levels,
> but all contexts involved need to be able to be specified to be
> correct.
>
> E.g. openpgp -> git-push-signature. That's not interchangeable with
> git-push-signature nor openpgp.

prepending "git-push-signature" || 0 || "openpgp" || 0 to the data to be
signed (as in my (2) above) seems naturally composable.

> > We find that reuse of signature keys for different purposes is rife in
> > the real world.  A firm requirement of TLS 1.3 is that existing keys
> > can be used with the new protocol.  It would not deploy otherwise, and
> > yet we endorse that which we all agree to be a sin and do what we can
> > to avoid problems.
>
> Also, TLS keys get reused in CSR signing, and CSRs are based upon ASN.1,
> which is let's say pretty different from TLS syntax...
>
> > I disagree with the notion of there being "serious" or "fundamental"
> > usability problems.
>
> The reason for those usability problems: APIs and what is offered.

I agree that for (1), the API situation is a mess and there are not any
currently usable library APIs.

My question is, what are the downsides of (2)?  It can perhaps offer a
false sense of security to protocol designers and/or implementors that
ought to be using separate keys, but if we spin it as something to be used
in addition to key separation, maybe it's not so bad.  Are there other
disadvantages of (2)?

-Ben