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>: > 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.
- [Cfrg] Adoption request: draft-hdevalence-cfrg-ri… Filippo Valsorda
- Re: [Cfrg] Adoption request: draft-hdevalence-cfr… Jeff Burdges
- Re: [Cfrg] Adoption request: draft-hdevalence-cfr… Filippo Valsorda
- Re: [Cfrg] Adoption request: draft-hdevalence-cfr… Paterson Kenneth
- Re: [Cfrg] Adoption request: draft-hdevalence-cfr… Jeff Burdges
- Re: [Cfrg] Adoption request: draft-hdevalence-cfr… Riad S. Wahby
- Re: [Cfrg] Adoption request: draft-hdevalence-cfr… Jack Grigg
- Re: [Cfrg] Adoption request: draft-hdevalence-cfr… Jeff Burdges
- Re: [Cfrg] Adoption request: draft-hdevalence-cfr… Riad S. Wahby
- Re: [Cfrg] Adoption request: draft-hdevalence-cfr… Riad S. Wahby
- Re: [Cfrg] Adoption request: draft-hdevalence-cfr… Filippo Valsorda
- Re: [Cfrg] Adoption request: draft-hdevalence-cfr… Filippo Valsorda
- Re: [Cfrg] Adoption request: draft-hdevalence-cfr… Riad S. Wahby
- Re: [Cfrg] Adoption request: draft-hdevalence-cfr… Riad S. Wahby
- Re: [Cfrg] Adoption request: draft-hdevalence-cfr… Filippo Valsorda
- Re: [Cfrg] Adoption request: draft-hdevalence-cfr… Filippo Valsorda
- Re: [Cfrg] Adoption request: draft-hdevalence-cfr… Riad S. Wahby
- Re: [Cfrg] Adoption request: draft-hdevalence-cfr… Watson Ladd
- Re: [Cfrg] Adoption request: draft-hdevalence-cfr… Riad S. Wahby
- Re: [Cfrg] Adoption request: draft-hdevalence-cfr… Riad S. Wahby
- Re: [Cfrg] Adoption request: draft-hdevalence-cfr… Henry de Valence
- [Cfrg] draft-hdevalence-cfrg-ristretto and draft-… Filippo Valsorda
- Re: [Cfrg] Adoption request: draft-hdevalence-cfr… Riad S. Wahby