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

Simon Josefsson <simon@josefsson.org> Sat, 23 April 2016 07:23 UTC

Return-Path: <simon@josefsson.org>
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 1F0E712D519; Sat, 23 Apr 2016 00:23:45 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -4.201
X-Spam-Level:
X-Spam-Status: No, score=-4.201 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_MED=-2.3, 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 5JiOWy6hdnS4; Sat, 23 Apr 2016 00:23:42 -0700 (PDT)
Received: from duva.sjd.se (duva.sjd.se [IPv6:2001:9b0:1:1702::100]) (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 4AA1F12D15E; Sat, 23 Apr 2016 00:23:41 -0700 (PDT)
Received: from latte.josefsson.org ([155.4.17.2]) (authenticated bits=0) by duva.sjd.se (8.14.4/8.14.4/Debian-4+deb7u1) with ESMTP id u3N7NGTv011331 (version=TLSv1/SSLv3 cipher=AES128-GCM-SHA256 bits=128 verify=NOT); Sat, 23 Apr 2016 09:23:17 +0200
From: Simon Josefsson <simon@josefsson.org>
To: Daniel Kahn Gillmor <dkg@fifthhorseman.net>
References: <87bn543id1.fsf@alice.fifthhorseman.net>
OpenPGP: id=54265E8C; url=http://josefsson.org/54265e8c.txt
X-Hashcash: 1:22:160423:bkaduk@akamai.com::WbdHCiionel3L2RY:Pql
X-Hashcash: 1:22:160423:draft-irtf-cfrg-eddsa.all@ietf.org::sSPiO+I08jibsjbN:FBo
X-Hashcash: 1:22:160423:edmonds@debian.org::/g9IXxrU8oJx/ATP:6WPV
X-Hashcash: 1:22:160423:cfrg@ietf.org::ZmRsAiIXl7Fsu850:OEHe
X-Hashcash: 1:22:160423:ondrej@sury.org::fp7tQIvaTVet8DEX:+EX1
X-Hashcash: 1:22:160423:martin.thomson@gmail.com::lBVQ8JMdmhD4CMjt:q6Bu
X-Hashcash: 1:22:160423:dkg@fifthhorseman.net::TMK7gtacqslfuWqu:eJGk
Date: Sat, 23 Apr 2016 09:23:15 +0200
In-Reply-To: <87bn543id1.fsf@alice.fifthhorseman.net> (Daniel Kahn Gillmor's message of "Wed, 20 Apr 2016 02:27:22 -0400")
Message-ID: <87zisk94bg.fsf@latte.josefsson.org>
User-Agent: Gnus/5.130014 (Ma Gnus v0.14) Emacs/24.4 (gnu/linux)
MIME-Version: 1.0
Content-Type: multipart/signed; boundary="=-=-="; micalg="pgp-sha256"; protocol="application/pgp-signature"
X-Virus-Scanned: clamav-milter 0.99 at duva.sjd.se
X-Virus-Status: Clean
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/zs8mHBwrO-dgqhPd-NgaO7XHZGg>
Cc: Robert Edmonds <edmonds@debian.org>, draft-irtf-cfrg-eddsa.all@ietf.org, cfrg@ietf.org, On dřej Surý <ondrej@sury.org>, Benjamin Kaduk <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: Sat, 23 Apr 2016 07:23:45 -0000

I see a serious concern with adding contexts to Ed25519.  So I don't
like this idea.  Below I suggest a way to achieve what I interpret what
you are after, that would still resolv my concern.  I'll try to explain
it all.  First some background.

First, remember that neither Curve25519 or Ed25519 are an CFRG
invention.  People are interested in using both of them in IETF
protocols.  The TLS WG asked and the CFRG accepted to work on
recommending new ECC curves for use with key agreement and signing.
That resulted in accepting Curve25519 and EdDSA/Ed25519, together with
Curve448 and consequently Ed448.

To deal with the API backwards compatibility issue for Ed25519, the less
secure pre-hashed variant was proposed and adopted.  That algorithm is
called Ed25519ph.  The Ed448 algorithm defined in the document is an
CFRG invention, through its addition of contexts and other details, and
while there is a name collision with the externally/academically
proposed Ed448 schema, that is less of a concern because there has been
little implementation interest in either of the Ed448 algorithms.

If the CFRG aims to re-define what Ed25519 means, which is what I read
that you are proposing to do, I believe we have to pick a different name
for it.  I suggest Ed25519ctx.  However, that said, introducing new
algorithms with different properties should not be done lightly and I
believe the motivation for contexts is at best not sufficiently
motivated by academic research.  DJB posted objections to this concept
when it was discussed earlier.

Further, introducing this tweak late in the process appears unfortunate.
We are having serious trouble shipping documents people have been
waiting for as it is.  Redefining what they will get this late in the
process is harmful.

So here is a suggestion.  Write a document describing a Ed25519-variant
called Ed25519ctx.  I would help work on it.  For those implementations
that are interested in using Ed25519ctx (which are they?), try to get
them aligned behind the document.  If there are, say, two different
protocols that have a desire to use contexts, I would believe that there
shouldn't be a problem getting the document published as an RFC.

What do you think?

Thanks,
/Simon

Daniel Kahn Gillmor <dkg@fifthhorseman.net> writes:

> Hi all--
>
> in draft-irtf-cfrg-eddsa-05, there is a context label defined for ed448,
> but no such label is defined for ed25519.  (the "context label" is a way
> to provide domain separation between signatures made in different
> contexts, avoiding cross-protocol attacks)
>
> people seem OK with domain separation for ed448, but we've rejected it
> for ed25519 to achieve backward compatibility with existing signatures,
> and to avoid API changes to existing ed25519 libraries, as discussed in
> threads like [0].
>
> I wanted to float one final middle-ground proposal that would allow us
> to align the APIs between the two by adding an optional context
> parameter to ed25519/ed25519ph.  If this isn't acceptable, please
> consider instead the proposed additional Security Considerations toward
> the end of this message.
>
> The proposal for including optional context labels in 25519 is simple:
>
>  * in Table 1: Parameters of Ed25519, change H(x) from "SHA-512(x)" to
>    "SHA-512(context || x)", and change PH(x) to "context || x".
>
>  * change the sentence describing the ph variant that follows the table
>    to:
>
>     Ed25519ph is the same but with PH being SHA-512(context || x)
>     instead, i.e., the input is hashed using SHA-512 before signing with
>     Ed25519.
>
> If "context" is unspecified by the user it is treated as the empty
> string and, the result is exactly the same as the current description.
> This is also easy for someone to implement with existing ed25519
> libraries with no API change: just concatenate before signing or
> verifying.
>
> This would mean that a signature with a context label for 25519 is not
> separated from a signature *without* a context label (a weaker domain
> separation than we're offering in ed448), but it at least provides a
> standard way for protocols that want to make domain-separated signatures
> to do so, which might help us to encourage domain separation in
> standards which contemplate the use of either Ed448 or Ed25519 (their
> abstract APIs are alignable).
>
>
> I also think we need some text explaining the difference between the two
> approaches.  If we adopt the above proposal, we could add something like
> this to the Security Considerations or section 10.3 ("Use of contexts"):
>
> ----------
>   Note that the domain separation for Ed25519 and Ed25519ph is weaker
>   than the domain separation for Ed448 and Ed448ph in two ways:
>
>     (a) Signatures that do not use context labels can potentially
>   collide with signatures that use context labels.  This can only be
>   mitigated by never using the same key in multiple domains without
>   having a domain-specific context label for each use.
>
>     (b) Signature domains that use context labels where one context
>   label is a prefix of the other may also have collisions.  This can be
>   mitigated by always choosing a context labels that consist of
>   printable ASCII characters followed by a single zero-valued octet.
>
>   This weaker domain separation is accepted in Ed25519 due to widespread
>   existing context-free deployment and the desire to avoid breaking
>   backward compatibility. For Ed448, which is not yet as widely
>   deployed, the dom() function's stronger domain separation guarantees
>   are preferred.
> ----------
>
> If we do not adopt the above changes, and leave ed25519 and ed25519ph
> without any attempt at domain separation, we also probably need a bit of
> text explaining why one primitive has domain separation and the other
> does not, probably in either Security Considerations or section 10.3.
> Otherwise, future people reading the draft would need to track down
> messages like those in [0] to understand the asymmetry.
>
> A proposal for text in this scenario:
>
> -----------
>   Note that only Ed448 offers strong domain separation via context
>   labels, while Ed25519 lacks this capability.  This is due to a desire
>   to retain backward compatibility with existing Ed25519 deployments,
>   and to leave the Ed25519 API as simple as possible.
>
>   If an application or protocol needs domain separation in situations
>   where Ed25519 may be used, a weaker form of domain separation may be
>   had by prepending a context label (fixed octet string) to the message
>   before signing or verifying, using a different context label for each
>   signature domain.  For the prehash variant, prepend the context to the
>   message before pre-hashing.
>
>   To avoid collisions between domains when using this weaker form of
>   domain separation, context labels should consist of only printable
>   ASCII characters followed by a single-valued octet.
> -----------
>
> What do folks think?
>
>      --dkg
>
>
> [0] see for example Ilari's response here to Bryan Ford at Message-Id:
>     20151211202214.GA5522@LK-Perkele-V2.elisa-laajakaista.fi
>     https://www.ietf.org/mail-archive/web/cfrg/current/msg07713.html
>
>     and the "On the differences of Ed25519/448 and how it affects a vote
>     on twoshakes-d" thread starting at Message-Id:
>     CAA4PzX18bcS_awPg-YDAoo90537Ot=s_nf7k_Vt75OVSdvtDrQ@mail.gmail.com
>     https://www.ietf.org/mail-archive/web/cfrg/current/msg07665.html
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>