Re: [Cfrg] Call for adoption: draft-hdevalence-cfrg-ristretto-01

"Filippo Valsorda" <filippo@ml.filippo.io> Fri, 25 October 2019 19:15 UTC

Return-Path: <filippo@ml.filippo.io>
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 DFC0512091E for <cfrg@ietfa.amsl.com>; Fri, 25 Oct 2019 12:15:07 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.6
X-Spam-Level:
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=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=filippo.io header.b=RWAGnv/z; dkim=pass (2048-bit key) header.d=messagingengine.com header.b=oq232T1l
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 4zlY5lZ2I4Gc for <cfrg@ietfa.amsl.com>; Fri, 25 Oct 2019 12:15:06 -0700 (PDT)
Received: from wout2-smtp.messagingengine.com (wout2-smtp.messagingengine.com [64.147.123.25]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 34BB61208E8 for <cfrg@irtf.org>; Fri, 25 Oct 2019 12:15:06 -0700 (PDT)
Received: from compute3.internal (compute3.nyi.internal [10.202.2.43]) by mailout.west.internal (Postfix) with ESMTP id 3582362C; Fri, 25 Oct 2019 15:15:05 -0400 (EDT)
Received: from imap1 ([10.202.2.51]) by compute3.internal (MEProxy); Fri, 25 Oct 2019 15:15:05 -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 :subject:content-type:content-transfer-encoding; s=fm1; bh=vxgBR ajlGPKAb8b3TVpWyp3fO408ls8PbpCgffPQ55U=; b=RWAGnv/zVPC8uH/6mD1sq 5l9mJLarxXmt8sh1s4bz16r2hWWgLeh7z2vz4X/25IA0C4ajPqA5LQD4c5ejWF0C jGON1n89VYJK/Ox8Vk/nfVBOxho3ajTuiDG0MRhO5sOck54XmpVPOT6gg235qBsa OHn6JvQ5qLk4uGcqHNSlJRj0MIl4PZASgkpj32MXm6WuqHEfLJ8AZM0JiQbOnYma +BZTE3Q0z5KfCNEJSQofK2p2xp5kulCqlVF1sqROFZcNjrttoQBaY0LzRRaMVhnI jqNTU0MpXDcTFa5b1lT7Hs1bY4RjsC7YUeJUe9uhoE/eXFvVmfTv43TFntG37jhW w==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=content-transfer-encoding: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=fm1; bh=vxgBRajlGPKAb8b3TVpWyp3fO408ls8PbpCgffPQ5 5U=; b=oq232T1ltaZRa6NRHudXYWfn1sDB4ieexsZsz3VSzNWrYdiHf3dmKLZxV iLCkBgY4hkO+I+yMAMwtR/I+RuiJFujZW78XLVMA6r7rqb62PU9vttefD8v+VyxX qfyunAgGqDFOhTlAjxiENI4SrsB6qZOY8JGxAdQRt1W4PdR2iFEUHKcL7wVk3MxD v3X3SF7hrNmVg+J3+TyixOz1eUyHPtKfFHWVL/Gob5Th77Ou+cwDZS0G0Pa/h4xx qAZ/7lPeOcSqOyuaG8bAUOY/bBXFVuddE67xT5HLgGr3yapK8LwW8uXZETnnBc8/ p7nMDoXJhZ/A9oqofO3ZvB7j5kN/g==
X-ME-Sender: <xms:uEmzXWdASmECi8ghUFWJnB4u80AI38kynXwWObmHtSOLSBVwD8qtMw>
X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedufedrleefgddufeeiucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen uceurghilhhouhhtmecufedttdenucenucfjughrpefofgggkfgjfhffhffvufgtgfesth hqredtreerjeenucfhrhhomhepfdfhihhlihhpphhoucggrghlshhorhgurgdfuceofhhi lhhiphhpohesmhhlrdhfihhlihhpphhordhioheqnecurfgrrhgrmhepmhgrihhlfhhroh hmpehfihhlihhpphhosehmlhdrfhhilhhiphhpohdrihhonecuvehluhhsthgvrhfuihii vgeptd
X-ME-Proxy: <xmx:uEmzXYFsUG4nXh07x95FsdpGDQGtkebSCfi8AScLMkatA1jPnESyyw> <xmx:uEmzXdcxFYKPZSnvfut6XsUwOoDKMZhkl-Ak57S4L9Ts9oL7ybKS9g> <xmx:uEmzXXlBFaPPjdbxgtErYoz8yhNg-aczf-Zs30wpuuSu7QwtkK7g0Q> <xmx:uEmzXXn_9IkH8UK2fofaN9HEJ2AYtMbsapv38WhCnUQ8ousUD04gVA>
Received: by mailuser.nyi.internal (Postfix, from userid 501) id 4B8ABC200A4; Fri, 25 Oct 2019 15:15:04 -0400 (EDT)
X-Mailer: MessagingEngine.com Webmail Interface
User-Agent: Cyrus-JMAP/3.1.7-470-gedfae93-fmstable-20191021v4
Mime-Version: 1.0
Message-Id: <b0714b74-03d7-434c-b67e-862b1c8f64e5@www.fastmail.com>
In-Reply-To: <20191025182546.cptq3qqcv25zhlvs@positron.jfet.org>
References: <e43c34da-1e2c-d1b5-9fc1-5bcc8373ebc8@isode.com> <ecebbdb2-31d5-3a7d-d45a-055b88606b76@isode.com> <acd979f5-61a8-43e2-922c-2fb5016e0c96@www.fastmail.com> <20191025182546.cptq3qqcv25zhlvs@positron.jfet.org>
Date: Fri, 25 Oct 2019 20:14:44 +0100
From: "Filippo Valsorda" <filippo@ml.filippo.io>
To: "Riad S. Wahby" <rsw@jfet.org>, cfrg@irtf.org
Content-Type: text/plain;charset=utf-8
Content-Transfer-Encoding: quoted-printable
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/LXhyG4j3RSFvwk1T8kyekX_uCi0>
Subject: Re: [Cfrg] Call for adoption: draft-hdevalence-cfrg-ristretto-01
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, 25 Oct 2019 19:15:08 -0000

2019-10-25 19:25 GMT+01:00 Riad S. Wahby <rsw@jfet.org>rg>:
> Filippo Valsorda <filippo@ml.filippo.io> wrote:
> > I definitely agree that there should be a standard path from non-uniform
> > inputs to ristretto255 points, and after some experimentation I
> > am fairly convinced the best solution is for hash-to-curve to
> > define the input processing (as well as the domain separation)
> > homogeneously with the other target curves, and then use the
> > ristretto255 FROM_UNIFORM_BYTES API as the abstraction point. This way
> > hash-to-curve users will be presented a uniform API, and ristretto255
> > internal types won't leak into neither the hash-to-curve spec nor its
> > implementations.
> 
> Hi Filippo,
> 
> I'm glad that Ristretto is moving forward, and I eagerly await its
> widespread use :)
> 
> As we're prepping hash-to-curve-05, one of the changes was to ensure
> that the hash function from arbitrary strings to the base field has
> an indifferentiability proof and that the domain separation design
> is conservative. In doing so, I've become (more) convinced that this
> is something that is easy to get subtly wrong, and that we should do
> as much as possible to encourage carefully vetted solutions.
> 
> With that as backdrop, I'm a bit nervous about the FROM_UNIFORM_BYTES
> API. Specifically, I worry that this API will encourage implementors
> to cook up ad-hoc methods of turning strings into "uniform" bytes.
> As one (possibly simple-minded) example, I worry that even the name
> of the API is misleading, because in almost all cases uniformity is
> not really enough. Meanwhile, FROM_INDEPENDENT_UNIFORM_BYTES starts
> sounding a little ridiculous, and isn't yet exhaustive... :)

Hi Riad,

Thanks for getting in touch about the hash-to-curve integration.

As far as I understand, you have concerns about two parts that feel
independent to me:

(a) the conversion from uniform bytes to the field element—this is
defined in the draft, so if you think there is an issue with it, please
let us know so we can address it;

(b) the generation of uniform bytes by the application—of course we
want to make sure this is not hard to get right, so can you share what
kind of issues we should be thinking about, based on your work on
hash-to-curve? Would SHA-512($STRING) be sufficient? We were already
planning to recommend (RECOMMEND, if you feel it would be appropriate)
to use hash-to-curve for domain separation purposes, so there is a
standard and vetted way to do it.

Again, we care about maintaining the abstraction of ristretto255
as nothing else than an abstract prime-order group, and abstract
prime-order groups don't have a base field, that's an implementation
detail that should not leak through the API. Integrating hash-to-curve
on top of FROM_UNIFORM_BYTES also maintains some compatibility between
the existing deployments which already use FROM_UNIFORM_BYTES and the
RFC.

> Here's one possible course of action:
> 
> 1. Remove the function that takes uniform bytes and replace it with
>    one that takes an element of the base field. Let's call this the
>    MAP function.
> 
> 2. As you said in your email, recommend (or even require) the use of
>    hash_to_base (Section 5 of hash-to-curve) to produce the input to
>    the MAP function.
> 
> 3. Define a new hash-to-curve suite based on MAP. I don't know whether
>    this should live in hash-to-curve or Ristretto, but I tend to think
>    the latter.
> 
> 4. Define MAP in terms of the Elligator 2 map in hash-to-curve, with
>    the goal of allowing code reuse and minimizing redundancy between
>    the two documents. (I realize that this is a contentious request.
>    I make it again because I'm still convinced this is both possible
>    and a good idea. If you think it's not, can you please explain in
>    detail why not? All the past explanations I've seen have been too
>    vague to be convincing.)

Multiple people made different arguments about this, but mine is
simple: there should be hash-to-curve libraries, and there should be
ristretto255 libraries. The ristretto255 libraries MUST NOT expose the
underlying curve points because it's an abstraction breach, because
it's encouraging implementors to do unsafe operations, and because
it makes interoperability with ristretto255 implementations based on
an alternative curve impossible. If the ristretto255 libraries don't
expose those internals, though, there is no way for hash-to-curve
libraries to do (4) without being one and the same, and I don't see why
a hash-to-curve library should be forced to implement ristretto255 and
vice-versa.