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

"Riad S. Wahby" <> Thu, 25 July 2019 01:09 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 0BAA8120614 for <>; Wed, 24 Jul 2019 18:09:49 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.556
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 ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id ibb8sXhtI_Ne for <>; Wed, 24 Jul 2019 18:09:48 -0700 (PDT)
Received: from ( []) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 173A212060B for <>; Wed, 24 Jul 2019 18:09:48 -0700 (PDT)
Received: by with SMTP id f17so17808071pfn.6 for <>; Wed, 24 Jul 2019 18:09:48 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; 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 ( []) by with ESMTPSA id s24sm48481816pfh.133.2019. (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" <>
To: Jeff Burdges <>
Message-ID: <>
References: <> <> <> <> <> <> <>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <>
Archived-At: <>
Subject: Re: [Cfrg] Adoption request: draft-hdevalence-cfrg-ristretto
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Thu, 25 Jul 2019 01:09:49 -0000

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