Re: [Cfrg] Adoption request: draft-hdevalence-cfrg-ristretto

Jack Grigg <ietf@jackgrigg.com> Wed, 24 July 2019 23:32 UTC

Return-Path: <me@jackgrigg.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 C22931202C7 for <cfrg@ietfa.amsl.com>; Wed, 24 Jul 2019 16:32:05 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.898
X-Spam-Level:
X-Spam-Status: No, score=-1.898 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=unavailable 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 jPANRVeavbcf for <cfrg@ietfa.amsl.com>; Wed, 24 Jul 2019 16:32:01 -0700 (PDT)
Received: from mail-wr1-f42.google.com (mail-wr1-f42.google.com [209.85.221.42]) (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 332791202CC for <cfrg@irtf.org>; Wed, 24 Jul 2019 16:32:01 -0700 (PDT)
Received: by mail-wr1-f42.google.com with SMTP id y4so48710803wrm.2 for <cfrg@irtf.org>; Wed, 24 Jul 2019 16:32:01 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:reply-to :from:date:message-id:subject:to:cc; bh=wRFmdRRBNh5U/92WVmfgptvy7A2RYs64hQMpUWTzUIc=; b=Xqbpm+O/YfQ2HLvPp+UpqDEEcWIr1QZDuB1EUDjAymlpKL42bsFnnNjjrlsDmnnoQo SQIkRmROlyVb3YS1na66byWX7DjP4zYcqH/S5kcfxAcKTWtp4Mpe0foPkX4npaXfn0u4 U0YdisTOk70e/uCCNA2MN945U2Df4qMiIl5e8OEZ4IGf0dCtgbrLhGF7t6fBgOQhGeG2 FuOl3L3vzhhsFA3jbV95ecqlUNIgwqSLlx6ERfafbd+vnXFdQKRepC+GYGR7LcoraP5W yvWWmN1XwXhu2taMobCtA3rmIdJqnAiHjqqKjvaaWAGVF5ltVKIslxVfA9rWAeya12jC WhIw==
X-Gm-Message-State: APjAAAWfOQsEMmfb9/OAil3iPVZ4SV4+kR3b1QislooaR8TKIuK5uZXh BS/FljUZHv91E16mCiMXURUIFTwAgmsCTqD5i70=
X-Google-Smtp-Source: APXvYqyzE6//A3oE+3agAfODp3XVnnFENkkvQtv/TTu58+oUjWR24tAQhET9GuYblCzVYeNkV30ef83nGRKwikZvTVA=
X-Received: by 2002:adf:b1d0:: with SMTP id r16mr34698648wra.332.1564011119489; Wed, 24 Jul 2019 16:31:59 -0700 (PDT)
MIME-Version: 1.0
References: <a505c99b-32a9-447a-9c69-a8efe3ed1b70@www.fastmail.com> <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>
In-Reply-To: <20190724212030.ddcswlg5uxm3muzo@positron.jfet.org>
Reply-To: ietf@jackgrigg.com
From: Jack Grigg <ietf@jackgrigg.com>
Date: Thu, 25 Jul 2019 00:31:48 +0100
Message-ID: <CAPC=aNVCV2cn62rhQsu+RsJsdjt2Dqqw_rqooLsuc8J5v9s3kQ@mail.gmail.com>
To: "Riad S. Wahby" <rsw@jfet.org>
Cc: Jeff Burdges <jeff@web3.foundation>, cfrg@irtf.org, draft-hdevalence-cfrg-ristretto@ietf.org
Content-Type: multipart/alternative; boundary="00000000000033ce3a058e75b74a"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/srITSfnWFs1S_HAsPl3NsWEaKL8>
Subject: Re: [Cfrg] Adoption request: draft-hdevalence-cfrg-ristretto
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: Wed, 24 Jul 2019 23:33:04 -0000

Hi Riad,

On Wed, Jul 24, 2019 at 10:20 PM Riad S. Wahby <rsw@jfet.org> wrote:

> Hello Jeff,
>
> I think I'm being a little slow here---sorry! But:
>
> Jeff Burdges <jeff@web3.foundation> wrote:
> > I'd expect the only contentious issue around Ristretto might be the
> > decision that a mapping from Ristretto to Ed25519 should not be
> > standardized.
> >
> > It's clear such a map is useful, so often people start off favoring one,
> > but it's also clear such a map leads to non-compliant implementations,
> > so similarly often people eventually come around to the opinion that
> > such a map should not be standardized.
>
> Can you please explain in a little more detail what you mean by
> "such a map leads to non-compliant implementations"? The most naive
> interpretation appears to be: currently a bunch of people do different
> things, so if the document requires one thing, some of those people
> will be non-compliant. Is that right? Or do you mean that somehow
> it would be impossible for (some) implementations to comply with any
> particular spec? (If so, why?)
>
> In any case, it seems to me that what we should care about is
> interoperability, not compliance for its own sake. Is it the case
> that dictating the Edwards mapping just doesn't matter, because
> implementations will be able to interoperate despite using different
> mappings internally? (I assume yes, based on my understanding of
> Decaf.)


The ability for ristretto255 implementations to interoperate, despite using
different internal representations, is contingent on implementors following
the normative requirement that the internal representations are not
exposed, or operated on except via the Ristretto APIs. This precludes any
mapping from ristretto255 elements to edwards25519 points.

Put another way: if a mapping from ristretto255 elements to edwards25519
points existed, any higher-level protocol that leveraged this mapping would
only work with ristretto255 implementations specifically constructed over
edwards25519, breaking interoperability across ristretto255 implementations.

It is an explicit design decision to define the Ristretto API solely in
terms of the four provided operations:

> ristretto255 is an abstraction which exposes a prime-order group, and
> ristretto255 elements are represented by curve points, but they are
> not curve points. The API needs to reflect that: the type
> representing an element of the group SHOULD be opaque and MUST NOT
> expose the underlying curve point.

>From an interoperability perspective, users of ristretto255 rely on the
fact that e.g. DECODE(x) will always return the same ristretto255 element
given a valid encoding x. They do not need to care how it is implemented,
or even that the same internal representation is always used. From section
3.2.3:

> Note that the equality function always returns TRUE when applied to
> an internal representation and to the internal representation
> obtained by encoding and then re-decoding it. However, the internal
> representations themselves might not be identical.


> If that's right, it seems reasonable to give implementors
> latitude to make decisions that have no effect on interoperability.
> (As a very rough analogy, RFC7748 doesn't say "you MUST do modular
> reductions in such-and-such way," because that doesn't matter from
> an interop perspective.)
>

I agree! This is what the current draft aims to do, by allowing
implementors to use whatever internal representation they choose.
Specifically, the document intends to specify the normative behavior of the
group and the API, while providing informationally the details of one
possible implementation, the one based on edwards25519. If there are ways
we can make this more clear, please do send suggestions.


>
> If my interpretation is correct, then I suggest the authors provide
> a mapping that implementations MAY use, as a way of assisting
> implementors in getting things right. This is probably as simple as
> citing the birational map between edwards25519 and curve25519 from
> Section 4.1 of RFC7748, and explaining how to use this map in concert
> with the Ristretto functions.
>

Per above, the way to ensure implementors get things right is to prohibit
such a mapping (which would necessarily be breaking the API provided by the
Ristretto functions, rather than being a mapping operating behind them).


>
> Also, a couple general comments for the authors regarding the document
> as it currently stands:
>
> First, the text of section 1 makes repeated reference to Edwards
> curves, but the document deals with a Montgomery curve (and, per the
> above, explicitly *does not* deal with an Edwards curve)---and the
> word Montgomery *never appears in the document*! Of the curves are
> equivalent, but the document should be intelligible even to readers
> who don't instantly recall this fact. I'm happy to suggest specific
> (likely minor) edits to the intro to help clarify this point.
>

This is a salient point. We in fact mean edwards25519 throughout the text,
but almost every implementation of edwards25519 that isn't built into an
Ed25519 implementation is provided in a Curve25519 library, and I figure
the latter is more familiar to readers (even RFC7748 only contains a single
occurrence of "edwards25519"). I personally would be happy to replace all
occurrences of "Curve25519" with "edwards25519", but I would like to hear
from the other authors on this point.


>
> Second, to make extremely clear what's going on with the Ristretto
> functions, it probably makes sense to reiterate, for each function,
> the types of the input and output. For example, I think the document
> is saying that DECODE takes a 32-octet string as input and returns
> a point (X : Y : Z : T) on curve25519 (i.e., the Montgomery curve)
> equivalent to the affine point (x, y) = (X/Z, Y/Z) (and analogously
> for the rest). Is this right? To my reading, this is not obvious from
> the document. That might be me being slow---sorry!---but perhaps in
> that case the authors will interpret this as feedback from a very
> naive reader who would love some extra handholding :)
>

If all occurrences of "Curve25519" were replaced with "edwards25519", would
this be clearer? For this particular example, the intention is that DECODE
takes a 32-byte string and returns either an error, or a ristretto255
element that is internally represented as a point (X : Y : Z : T) on
edwards25519. Part of the fun here is figuring out how to make these types
clear and the ristretto255 API well-defined, while enabling implementors to
use concrete internal implementations outside of what is provided in the
draft.

Thanks for the feedback,
Jack


>
> Looking forward to Ristretto,
>
> -=rsw
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>