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

"Riad S. Wahby" <rsw@jfet.org> Thu, 25 July 2019 01:09 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 0BAA8120614 for <cfrg@ietfa.amsl.com>; Wed, 24 Jul 2019 18:09:49 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.556
X-Spam-Level:
X-Spam-Status: No, score=-1.556 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FREEMAIL_FORGED_FROMDOMAIN=0.091, FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.249, 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 ibb8sXhtI_Ne for <cfrg@ietfa.amsl.com>; Wed, 24 Jul 2019 18:09:48 -0700 (PDT)
Received: from mail-pf1-f195.google.com (mail-pf1-f195.google.com [209.85.210.195]) (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 173A212060B for <cfrg@irtf.org>; Wed, 24 Jul 2019 18:09:48 -0700 (PDT)
Received: by mail-pf1-f195.google.com with SMTP id f17so17808071pfn.6 for <cfrg@irtf.org>; Wed, 24 Jul 2019 18:09:48 -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:cc:subject:message-id:references :mime-version:content-disposition:in-reply-to; bh=sXg9nclVkIFqVdRxUbhVYJama0jtzhjvXTyciqnEeX0=; b=c2Jqkx8d/wkiu6lfps3E7IE3N+ZM2b20iWysbljB8534qnVBX9cCFQzd+CTqbjyDnz yxK0z6R4KX6/v6SwyCeQa9oSb12Ce5NOVTJE7W0wN5zla4adwTQHv3YK2Fi7RxJQwDsu ov5qS2xPfkw4fKD+PFjuYq3a3w1pusvjz3iIlWa9kbXzUMyDV1gfGtcv6WZki1HpagJR ER5S9sssuJt8cUtRTYcfDHXwh50HtJB79HpiLybUFhDWXFKCZJTZlb9biYjhmdnlInRh J0ahYO3Gqe2g2GS7OJ6/zHXWt6Kzr22NXC+Wrb3tzIYTznf1V1esDBN3uagjMj73yV37 FW5Q==
X-Gm-Message-State: APjAAAXLOy1UktKX1bOPUj+87qKUZJvaBWO69NcdEwo1Gzoxf8lz4d0N i3DTQ/nLAKsQEVyzgNkB0ShQyBu9
X-Google-Smtp-Source: APXvYqyaQGm64A7oSJhCyiYIuei2tT+MzlzjwuUTT7nl3nBK7BnFGz65InBI9R/Db8nM6tZ8gN1fWQ==
X-Received: by 2002:a17:90a:2190:: with SMTP id q16mr87367682pjc.23.1564016987542; Wed, 24 Jul 2019 18:09:47 -0700 (PDT)
Received: from localhost (positron.stanford.edu. [171.67.76.114]) by smtp.gmail.com with ESMTPSA id s24sm48481816pfh.133.2019.07.24.18.09.45 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Wed, 24 Jul 2019 18:09:46 -0700 (PDT)
Date: Wed, 24 Jul 2019 18:09:45 -0700
From: "Riad S. Wahby" <rsw@jfet.org>
To: Jeff Burdges <jeff@web3.foundation>
Cc: ietf@jackgrigg.com, cfrg@irtf.org, draft-hdevalence-cfrg-ristretto@ietf.org
Message-ID: <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>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <16485892-168c-a7ca-ba8c-94f7ce5c0e8e@web3.foundation>
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/Z6ZhQKpZE_GeTkJDwYbhCd8M7ng>
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:09:49 -0000

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

-=rsw