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

"Filippo Valsorda" <filippo@ml.filippo.io> Thu, 25 July 2019 01:42 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 C9C101200B9 for <cfrg@ietfa.amsl.com>; Wed, 24 Jul 2019 18:42:23 -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=unavailable autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=filippo.io header.b=Vit6TJMZ; dkim=pass (2048-bit key) header.d=messagingengine.com header.b=BmEbHjDU
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 u3qc_Jkr0idP for <cfrg@ietfa.amsl.com>; Wed, 24 Jul 2019 18:42:21 -0700 (PDT)
Received: from out4-smtp.messagingengine.com (out4-smtp.messagingengine.com [66.111.4.28]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 5290D120297 for <cfrg@irtf.org>; Wed, 24 Jul 2019 18:42:21 -0700 (PDT)
Received: from compute3.internal (compute3.nyi.internal [10.202.2.43]) by mailout.nyi.internal (Postfix) with ESMTP id 4195521165; Wed, 24 Jul 2019 21:42:20 -0400 (EDT)
Received: from imap1 ([10.202.2.51]) by compute3.internal (MEProxy); Wed, 24 Jul 2019 21:42:20 -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=QOd9ViA/scOfIIQKh8GgWOhQYevdqcW 6kG6Vf4mHA6w=; b=Vit6TJMZeQebXXsGWpyaMCjeVUlF9SwBC3iQuoR06pSA40V rSDl/x23eCHly7CtVJX9xJQSdPTELcMB0Dcsm+3HHMUZPeP4B1tQmwPGJvOrDF5V NA8WokBHXrorKBYDaHjSWtI3w1+6JtS4QcRga/rXyvY4cc7lmMNjtVtljRJrO/fU yMK6KjEKxU48Ds+sJdSlI/p3lueL44iiz7UpbZlLZ92c+2BaiYbwfoNNOFfQQf6d S/PwUdZHjc49pZTs6WqXGhO8QJrM8KIX48XBsGNtmLLyARWnkaNSNF015bdvpl/u ri+xVZYTX+rOLCV+JcgIyTxPA3Yna4s6XYE8cow==
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=QOd9Vi A/scOfIIQKh8GgWOhQYevdqcW6kG6Vf4mHA6w=; b=BmEbHjDUELdZomUt/IVejK BzAsfjaMxJvSPyoFj8afUl+SYzhLxJMJRrUJ2wo5PmIKTiIVdS3tCKbs5ZU4nbbS wvbVTBEtDK8xdJe4wpEZKkDB7G0SDBYJI5cQlkc0MXn3+7IhDYjaYdGFhMWBQECg BjdXQNr3ZJkO6yG8Iw+59NVTwJal3vHgPJbLZjVMxujbQMq9SkEYoXDfF/v2AuyI WevJYhZT5qLXlvScFe7TMPnlf3e7lnebhmcmetswTu351QltsQPxeRQ6vFsS6fXY 3+LiP/whdHjzUYij2j3A4f1avIBuyd1Vinf16aa/Jw1sPguuXo6EIPoqoX9OgsNA ==
X-ME-Sender: <xms:-gg5XRQ6CO9ZLvxqNETVGVT7wEhr4A0m6C1A4gFtRew7KxV26dD8AQ>
X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeduvddrkedugdeghecutefuodetggdotefrodftvf curfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfghnecu uegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivghnthhsucdlqddutddtmdenuc fjughrpefofgggkfgjfhffhffvufgtsehttdertderredtnecuhfhrohhmpedfhfhilhhi phhpohcugggrlhhsohhruggrfdcuoehfihhlihhpphhosehmlhdrfhhilhhiphhpohdrih hoqeenucfrrghrrghmpehmrghilhhfrhhomhepfhhilhhiphhpohesmhhlrdhfihhlihhp phhordhiohenucevlhhushhtvghrufhiiigvpedt
X-ME-Proxy: <xmx:-wg5XVjDSmUL32nH1x3Z05g38WYC58EPDtMECiT1GSKAE1Nyz6Q2ww> <xmx:-wg5XVsMGb5bq7cpRtuSHeX5sjh3iw8ii5sGBIfl2cyrFXgzjLWWnQ> <xmx:-wg5Xfxd8Fv-BS2LrudcnpAdlOWRiX0mr7A1gHWWrKS1Jygbfo1VCA> <xmx:_Ag5XWZvjx_AgiGVdMyAT-abGDf1M2HZ2wNoedrljT3L5gbvLjky5A>
Received: by mailuser.nyi.internal (Postfix, from userid 501) id E366AC200A5; Wed, 24 Jul 2019 21:42:18 -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: <1d2252da-95b1-44fb-b9d5-9dd7f9c5bc54@www.fastmail.com>
In-Reply-To: <20190725010945.h2c3pa6k6cqlogqg@positron.jfet.org>
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> <CAPC=aNVCV2cn62rhQsu+RsJsdjt2Dqqw_rqooLsuc8J5v9s3kQ@mail.gmail.com> <16485892-168c-a7ca-ba8c-94f7ce5c0e8e@web3.foundation> <20190725010945.h2c3pa6k6cqlogqg@positron.jfet.org>
Date: Thu, 25 Jul 2019 03:41:11 +0200
From: "Filippo Valsorda" <filippo@ml.filippo.io>
To: "Riad S. Wahby" <rsw@jfet.org>, "Jeff Burdges" <jeff@web3.foundation>
Cc: draft-hdevalence-cfrg-ristretto@ietf.org, cfrg@irtf.org
Content-Type: text/plain
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/BRD7A2PiMMSzEs9auNivh86yEtg>
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: Thu, 25 Jul 2019 01:42:24 -0000

2019-07-25 03:10 GMT+02:00 Riad S. Wahby <rsw@jfet.org>rg>:
> Jeff Burdges <jeff@web3.foundation> wrote:
> > The real issue is that there are two such mappings, depending upon the
> > branch of the inverse square root chosen.  These two interoperate
> > seamlessly, provided the mapping is not exposed.  If however the mapping
> > is exposed later then they suddenly differ.  The problematic scenario goes:
> 
> Just to clarify: the mappings you're talking about are the ones in
> RFC7748, Section 4.1, and the value whose sign you're worried about
> is sqrt(-486664) mod p, right?
> 
> A second clarification: we're really talking about mapping *from*
> edwards25519 *to* curve25519, since what's in the Ristretto draft
> Section 3 apparently works on edwards25519 points (I think).
> 
> > Joe later expands his protocol by adding and using the mapping, using
> > the form of the mapping natural given the arithmetic he inherited.
> > Again everything works, so now people depend upon Joe's mapping.  Joe
> > does not however check all newly applicable test vectors from the
> > standard because everything works fine.
> 
> Again, "the mapping" being the one to curve25519?
> 
> > Joe expands his protocol to interoperate with another implementation.
> > Now suddenly everything breaks because the mappings differ.  Yet both
> > incompatible forms are deployed.
> 
> Same question as above re "the mappings".
> 
> Can you give a specific example of the kind of interop that would
> break? In particular, provided that reverse_map(map(X)) == X for all
> rational points X on edwards25519, wouldn't it always be safe to do
> something like
> 
>     DECODE -> map -> (something) -> reverse_map -> ENCODE
> 
> provided that (something) includes only allowed operations (addition,
> inversion, multiplication)?

I think you and Jeff are talking about different things, and myself
and the rest of the authors are mostly concerned about yet a different
thing. Let me try to enumerate them.

    DECODE -> map -> (something) -> reverse_map -> ENCODE

This chain that you describe, if done correctly, would in fact be just
an alternative implementation of ristretto255, as it operates entirely
within the realm of internal representatives.

    ENCODE -> map -> (something) -> reverse_map -> DECODE

This, correct me if I'm wrong, is an example of the kind of map Jeff
is talking about: something that takes abstract ristretto255 elements
(which might be implemented with something else than edwards25519) and
maps them to edwards25519 points (NOT internal representatives).

While not an abstraction breach, this would be problematic for the
reasons Jeff mentions (that it would be a niche feature of the group
prone to errors), but most importantly IMHO because it would cause
confusion and those mapped edwards25519 points would end up being used
as internal representatives, breaching the abstraction.

    edwards25519 point -> (something) -> reverse_map -> ENCODE

    DECODE -> map -> edwards25519 point -> (something)

This is an abstraction breach, which if specified would make it
difficult if not impossible for non-edwards25519 implementations to
interoperate, and would risk compromising the safety of the primitive.

An example of this is draft-irtf-cfrg-voprf-01 defining its own map to
ristretto255 internal representatives.

In my previous email I was mostly addressing this last case, so
apologies if I ended up talking past you while you were talking about
the first one.