[Cfrg] draft-hdevalence-cfrg-ristretto and draft-irtf-cfrg-hash-to-curve

"Filippo Valsorda" <filippo@ml.filippo.io> Fri, 26 July 2019 21:03 UTC

Return-Path: <filippo@ml.filippo.io>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id A7EA112011B for <cfrg@ietfa.amsl.com>; Fri, 26 Jul 2019 14:03:31 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.6
X-Spam-Status: No, score=-2.6 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=unavailable autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=filippo.io header.b=gR8JowRc; dkim=pass (2048-bit key) header.d=messagingengine.com header.b=MNUDkN2c
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id 6nl4nXfmLlGY for <cfrg@ietfa.amsl.com>; Fri, 26 Jul 2019 14:03:28 -0700 (PDT)
Received: from wout3-smtp.messagingengine.com (wout3-smtp.messagingengine.com []) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id CB22B12006E for <cfrg@irtf.org>; Fri, 26 Jul 2019 14:03:28 -0700 (PDT)
Received: from compute3.internal (compute3.nyi.internal []) by mailout.west.internal (Postfix) with ESMTP id F3D00629; Fri, 26 Jul 2019 17:03:27 -0400 (EDT)
Received: from imap1 ([]) by compute3.internal (MEProxy); Fri, 26 Jul 2019 17:03:28 -0400
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=filippo.io; h= mime-version:message-id:in-reply-to:references:date:from:to:cc :subject:content-type; s=fm1; bh=QgjprX2zad5L322q50igpjjaB7tRyOV UxOfJ4ZvXDsI=; b=gR8JowRcatZlPtVMgRATrYTtnzV7OEPVKmLnpaybw1yl05J iTuo2faAebC2YySTMvlELXH9xUqdBRQmI0KTdItqffVTIT5hSQh+0iejZKMi7Qa3 TFxS3HyCM27Ql1a0iOsCt80MoIOojsCwCGDgpLj6mh5AEqgQIt4/p2EQoT2D1RH9 NIktAFsRpfduYlEmVCxw4D9MYEzoFILrRmXBrurOUE/bfzG61r7dOrj+ZB7jZTZ5 nRTeqLj9P9UT7rOcTPTe6gvOGBs7QddTi3z1xtHU6I/Q5e/5B7GpOPo7jQHslk7C xYhnhlZfyPcHjjf49AUbWIMvDJn7z1A4qrhewFQ==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:content-type:date:from:in-reply-to :message-id:mime-version:references:subject:to:x-me-proxy :x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s=fm3; bh=QgjprX 2zad5L322q50igpjjaB7tRyOVUxOfJ4ZvXDsI=; b=MNUDkN2cYkXhunJAZ3En7g RkTW6ygljZ0noDJYsKzC51xzKDPLopn60SFnjenHnoKkV29gSlAwa30r3HsQVjPf loZ0ozfrNMi8JiOY2uVjIaJ6SoBX6o22j8CxVQw5pnbZyfdq8n7dyTL9DQk+hs2/ Ws9K6uP4h7b3K4hb8oQlpVIf5VmgCSYvZZICu9CFLfi0jb2gcM4Jx8Y6sAib8HYi tJf17kTPaProm+afaGdeY789/+R8pOt6RHOoyD42kAvvKu64qOgyTTvP9FPYghyp qKquZg6m76lI95S2BjXEl67WjAqeOL4ZRnIARDnhNF/bogU+OOa+VHAoC0fjgMnQ ==
X-ME-Sender: <xms:nmo7XUBNqnZ26mghaCQn7x2n-NxIsqm0VdPtEFev2LPlw7FLLgApgQ>
X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeduvddrkeeggdduheeiucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen uceurghilhhouhhtmecufedttdenucenucfjughrpefofgggkfgjfhffhffvufgtsehttd ertderredtnecuhfhrohhmpedfhfhilhhiphhpohcugggrlhhsohhruggrfdcuoehfihhl ihhpphhosehmlhdrfhhilhhiphhpohdrihhoqeenucffohhmrghinhepghhithhhuhgsrd gtohhmpdhmvghrlhhinhdrtghoohhlnecurfgrrhgrmhepmhgrihhlfhhrohhmpehfihhl ihhpphhosehmlhdrfhhilhhiphhpohdrihhonecuvehluhhsthgvrhfuihiivgeptd
X-ME-Proxy: <xmx:nmo7XRui6Q5VkIeIH46TwMCc_ah3nhPokVouvwH2HswI11bWZSWIDw> <xmx:nmo7XbbFOlgxQSGZhL4CMqTIw4gi_NRb-JM-RFvGXriI4phmx0KnQw> <xmx:nmo7XVG4HFWF2c7pvabocHsYKXOTdrdPIX6Zl2vMkHYOtjn0QiYZFQ> <xmx:n2o7XQ6LU-7Pcvx5kGXO8BOuo92RereUS6G0nUrx4oanDGGwxLJDBw>
Received: by mailuser.nyi.internal (Postfix, from userid 501) id 9D0B7C200A3; Fri, 26 Jul 2019 17:03:19 -0400 (EDT)
X-Mailer: MessagingEngine.com Webmail Interface
User-Agent: Cyrus-JMAP/3.1.6-736-gdfb8e44-fmstable-20190718v2
Mime-Version: 1.0
Message-Id: <d93e63ff-32ab-4ad5-ab79-d0dc02ae49f7@www.fastmail.com>
In-Reply-To: <CA+jiKjOPT_JpWULgQ6kJ2q1yqP-iymAms80NCcDf_mHE7mi3qg@mail.gmail.com>
References: <0370cd6b-adf3-4be2-9ab4-79693b9dc096@www.fastmail.com> <B7F73174-29F0-4B83-8AC0-A7D42D372D4A@inf.ethz.ch> <075d43b1-e123-42a9-ccd9-64fe45306f8b@web3.foundation> <20190724212030.ddcswlg5uxm3muzo@positron.jfet.org> <CAPC=aNVCV2cn62rhQsu+RsJsdjt2Dqqw_rqooLsuc8J5v9s3kQ@mail.gmail.com> <20190725004633.l5k7toldcgy7uthb@positron.jfet.org> <a391f8d5-c4c4-4650-9392-860864543198@www.fastmail.com> <20190725015259.betglszxmwpgg7q7@positron.jfet.org> <3dde344b-40d2-4ea8-84c9-7ddec039afe3@www.fastmail.com> <20190725034958.bp6nnhqedjwmyzng@positron.jfet.org> <20190725143626.aetja4eeyzyimcne@positron.jfet.org> <CA+jiKjNsH6ROj9j-R_+AuRDEMSDq=Ee7hg_z63P_8CTjyE0r2g@mail.gmail.com> <CA+jiKjOPT_JpWULgQ6kJ2q1yqP-iymAms80NCcDf_mHE7mi3qg@mail.gmail.com>
Date: Fri, 26 Jul 2019 23:02:54 +0200
From: "Filippo Valsorda" <filippo@ml.filippo.io>
To: cfrg@irtf.org
Cc: draft-hdevalence-cfrg-ristretto@ietf.org, "Henry, de Valence" <ietf@hdevalence.ca>, "Riad S. Wahby" <rsw@jfet.org>
Content-Type: text/plain
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/p_r53FtGcaNSB_HwIV0J9FSgYbg>
Subject: [Cfrg] draft-hdevalence-cfrg-ristretto and draft-irtf-cfrg-hash-to-curve
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.29
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: Fri, 26 Jul 2019 21:03:32 -0000

The discussion about draft-hdevalence-cfrg-ristretto so far brought up a
number of areas worth clarifying which we plan to address in -02. Aside
from that, if I'm not mistaken, the only other topic of discussion was
the interaction with draft-irtf-cfrg-hash-to-curve.

I am bringing it into its own thread and adding my remarks at the bottom.

2019-07-26 22:09 GMT+02:00 Henry de Valence <ietf@hdevalence.ca>;:
> Riad S. Wahby <rsw@jfet.org>; wrote:
> > 7. Make FROM_UNIFORM_BYTES incorporate edwards25519-SHA256-EDELL2-RO
> >    by reference, and specify a DST (domain separation tag, see Section
> >    5.1 and 5.3 of hash-to-curve), e.g., "Ristretto255-Hash".
> >
> > 7.1. Also, rename FROM_UNIFORM_BYTES to either FROM_BYTES or FROM_STRING,
> > and remove the length and distribution requirements on the input.
> > The hash-to-curve document handles the uniformity internally while
> > ensuring that conforming usage meets relevant security requirements.
> > There's no reason to make higher-level protocols reinvent the wheel.
> I don't think this suggestion is a good idea, for a number of reasons:
> 1. edwards25519-SHA256-EDELL2-RO is not compatible with ristretto255, as
> it does not produce valid internal representatives;
> 2. even if it did, ristretto255 implementations are not required to
> use Curve25519 internally, so the hash-to-group method cannot be
> defined in terms of Curve25519;
> 3. ristretto255 already provides a hash-to-group method, which is defined
> so that implementations remain wire-compatible even when changing the
> curve used internally, as noted in the Ristretto website and the Decaf
> paper;
> 4. requiring use of a specific hash function is a layering violation,
> as the definition of an elliptic curve should not depend on use of a
> particular symmetric primitive.
> The FROM_UNIFORM_BYTES function provides a generic hook which handles
> all of the details specific to the ristretto255 group, whose input
> uniformity requirement retains composability with various symmetric
> constructions.  This isn't requiring higher-level protocols to
> reinvent the wheel, but retaining compatibility with them.
> For instance, why should a higher-level protocol that everywhere else
> uses domain-separated SHA3 be forced to use SHA2 for hash-to-group?
> Or, consider a protocol that uses a duplex construction to ensure that
> hash output is not just bound to a single domain separator, but to an
> entire message transcript with arbitrary application domain separation
> messages (e.g., https://merlin.cool).  Why should it be forced to
> launder its domain-separated hash output through a second HKDF
> construction?
> Of course, it would be most preferable to achieve compatibility
> between the ristretto255 draft and the hash-to-curve draft.  But since
> the hash-to-curve draft describes hash-to-curve methods for various
> elliptic curve groups (P-256, secp256k1, Curve25519, etc), while this
> draft is tightly focused on describing a specific group, it seems like
> the cleaner layering would be for the hash-to-curve draft to
> incorporate this draft by reference, and use this draft's
> FROM_UNIFORM_BYTES function to define a
> ristretto255-SHA256-RISTRETTO-RO
> or similar (I'm not 100% confident in my understanding of your naming
> scheme).
> In this way, the hash-to-curve draft defines hash-to-curve methods for
> various elliptic-curve-based groups (P-256, secp256k1, Curve25519, and
> ristretto255), while the ristretto255 draft remains focused on
> definining a single group and retains compatibility with other
> symmetric constructions (e.g., sponge constructions).

I agree with Henry, and I think it helps to think about it in terms of
implementations. As I see it, there are three options.

Option 1: use an existing hash-to-curve method

This is definitely unworkable. A method that hashes to Curve25519 points
is not fit for hashing to ristretto255 because ristretto255 internal
representatives are a different type from Curve25519 points. Internal
representatives are an opaque type that might or might not be a wrapper
around a Curve25519 point, and there's no map between Curve25519 points
and internal representatives.

Option 2: specify FROM_UNIFORM_BYTES in hash-to-curve

This would require putting a method that returns a ristretto255 internal
representative in hash-to-curve. On top of moving a lot of the Ristretto
math to hash-to-curve, that would leak all the complexity of specifying
behavior without mandating the actual curve to the hash-to-curve
specification, and is a major breach of the ristretto255 abstraction.

Think about a ristretto255 implementation,
https://github.com/gtank/ristretto255 for example. The spec requires
it to keep its element type opaque (to preserve the group abstraction,
to guarantee interoperability with other implementations, to prevent
misuse, to allow switching curve, ...), so there is no way for a
hash-to-curve implementation to construct an element from an internal
representative. It's internal after all!

Consequently forcing ristretto255 implementations to also implement
hash-to-curve and making it impossible for generic hash-to-curve
implementations to offer the ristretto255 method sounds wrong.

Option 3: use FROM_UNIFORM_BYTES from hash-to-curve

This is what Henry is suggesting, and it looks like the natural
separation of concerns to me. hash-to-curve is in charge of
parametrizing hashes, defining domain separation, and all the things it
already does. It then generates uniform bytes, and ristretto255 defines
the interoperable map to an opaque group element.

Of course, we'd be happy to contribute such a method to hash-to-curve,
but unlike Option 2 it should be fairly trivial (which in itself
suggests we hit the right level of abstraction).