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

"Riad S. Wahby" <rsw@jfet.org> Fri, 25 October 2019 18:25 UTC

Return-Path: <rswatjfet.org@gmail.com>
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 B15711208A3 for <cfrg@ietfa.amsl.com>; Fri, 25 Oct 2019 11:25:50 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.397
X-Spam-Level:
X-Spam-Status: No, score=-1.397 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FREEMAIL_FORGED_FROMDOMAIN=0.249, FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.25, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_MSPIKE_H3=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=no 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 nnOAW8WTtgJn for <cfrg@ietfa.amsl.com>; Fri, 25 Oct 2019 11:25:49 -0700 (PDT)
Received: from mail-pf1-f170.google.com (mail-pf1-f170.google.com [209.85.210.170]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id C30BE1208A5 for <cfrg@irtf.org>; Fri, 25 Oct 2019 11:25:49 -0700 (PDT)
Received: by mail-pf1-f170.google.com with SMTP id v19so2126741pfm.3 for <cfrg@irtf.org>; Fri, 25 Oct 2019 11:25:49 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:subject:message-id:references :mime-version:content-disposition:in-reply-to; bh=vFcxlz8hkr69We9irF3nPb5mMLFe+xNDzPkMSoknsbQ=; b=klCwuYnDqkx1+Is9GSKYAdtEmhCfoSI1mzFXaQ6sRGU12eixv938+C8bRLoDrDLaZb H0a39vLneEcDNYuKWMKSKOM5hrf4HNSOJDV36jj4TyOr0lw4dVUwT4V8yO11nLlHb9ee 1Mzo9XzaIRuzIa2gU3jz0itZc+7SuJb9mhqDMVjHZf0SE78xbK1UocJ8mf+VMDKgatzM hybV0peU8vla3KnpZ4o4EeoeAZAwzVuxdCz9uj7oWoTLDX9XD5T6nOZvBnpk6Oddcm9n KdcxnsqWrd3r0NZzMmkD2e+NYzDz+g9lKLY4kCsiOeJc70XVrvMuVTh7IjtDYU5Z3WuV aKdQ==
X-Gm-Message-State: APjAAAWyWe4REbPww7cIzGHxfbRq1br+nneUpr7gUYEKmTvfS7o/uEm7 Abf0kRpT3bZs83L4aUzAwT4=
X-Google-Smtp-Source: APXvYqymCRbpFPnf/FCr7s1iXQsIb3bODQqCUQuydZ1MrHSapZDtdqJoftiHeYhY0wBrV1bizPEQnQ==
X-Received: by 2002:a63:b25d:: with SMTP id t29mr5783108pgo.395.1572027948972; Fri, 25 Oct 2019 11:25:48 -0700 (PDT)
Received: from localhost (positron.stanford.edu. [171.67.76.114]) by smtp.gmail.com with ESMTPSA id m12sm3982804pff.66.2019.10.25.11.25.47 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Fri, 25 Oct 2019 11:25:48 -0700 (PDT)
Date: Fri, 25 Oct 2019 11:25:46 -0700
From: "Riad S. Wahby" <rsw@jfet.org>
To: Filippo Valsorda <filippo@ml.filippo.io>, cfrg@irtf.org
Message-ID: <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>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <acd979f5-61a8-43e2-922c-2fb5016e0c96@www.fastmail.com>
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/T9nnByF3wAASejheTwOSXqTA5ag>
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 18:25:51 -0000

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... :)

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.)

Even if (4) really is impossible, (1)-(3) still look to me like they
would help avoid confusion and steer implementors towards safe choices.

Looking forward to working with you on this,

-=rsw