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

Daniel Kahn Gillmor <dkg@fifthhorseman.net> Wed, 20 April 2016 06:27 UTC

Return-Path: <dkg@fifthhorseman.net>
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 2E39B12D5FD; Tue, 19 Apr 2016 23:27:34 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.9
X-Spam-Level:
X-Spam-Status: No, score=-1.9 tagged_above=-999 required=5 tests=[BAYES_00=-1.9] 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 KVFRTG5kkcv6; Tue, 19 Apr 2016 23:27:32 -0700 (PDT)
Received: from che.mayfirst.org (che.mayfirst.org [162.247.75.118]) by ietfa.amsl.com (Postfix) with ESMTP id D7F4812D908; Tue, 19 Apr 2016 23:27:28 -0700 (PDT)
Received: from fifthhorseman.net (ool-6c3a0662.static.optonline.net [108.58.6.98]) by che.mayfirst.org (Postfix) with ESMTPSA id 7CFF6F991; Wed, 20 Apr 2016 02:27:26 -0400 (EDT)
Received: by fifthhorseman.net (Postfix, from userid 1000) id 2B43B20051; Wed, 20 Apr 2016 02:27:26 -0400 (EDT)
From: Daniel Kahn Gillmor <dkg@fifthhorseman.net>
To: cfrg@ietf.org, draft-irtf-cfrg-eddsa.all@ietf.org
User-Agent: Notmuch/0.21+128~g620f892 (http://notmuchmail.org) Emacs/24.5.1 (x86_64-pc-linux-gnu)
Date: Wed, 20 Apr 2016 02:27:22 -0400
Message-ID: <87bn543id1.fsf@alice.fifthhorseman.net>
MIME-Version: 1.0
Content-Type: multipart/signed; boundary="=-=-="; micalg=pgp-sha512; protocol="application/pgp-signature"
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/H1uELJOW-0tTBAn1jJv2p1IVTrs>
Cc: =?utf-8?B?T25kxZllaiBTdXLDvQ==?= <ondrej@sury.org>, Robert Edmonds <edmonds@debian.org>, Benjamin Kaduk <bkaduk@akamai.com>, Martin Thomson <martin.thomson@gmail.com>
Subject: [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: Wed, 20 Apr 2016 06:27:34 -0000

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