Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Consensus and a way forward]

Robert Ransom <rransom.8774@gmail.com> Wed, 03 December 2014 07:13 UTC

Return-Path: <rransom.8774@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 37F7E1A00DF for <cfrg@ietfa.amsl.com>; Tue, 2 Dec 2014 23:13:33 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.75
X-Spam-Level:
X-Spam-Status: No, score=-1.75 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_ENVFROM_END_DIGIT=0.25, FREEMAIL_FROM=0.001, SPF_PASS=-0.001] autolearn=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 H28qwwE4h7w8 for <cfrg@ietfa.amsl.com>; Tue, 2 Dec 2014 23:13:31 -0800 (PST)
Received: from mail-qc0-x22d.google.com (mail-qc0-x22d.google.com [IPv6:2607:f8b0:400d:c01::22d]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 840B91A0092 for <cfrg@irtf.org>; Tue, 2 Dec 2014 23:13:23 -0800 (PST)
Received: by mail-qc0-f173.google.com with SMTP id i17so10709377qcy.18 for <cfrg@irtf.org>; Tue, 02 Dec 2014 23:13:22 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; bh=3qL6FWR6BAMHJMzRaPjV4NXdGXlEMl/mI8hwFHh3wsI=; b=D8J0USoebM8NYChXA3uRVsXh9LfZazySSA0iXhHtB1TKCHi4HPYup5uHPCL1N/s/EK HIiZV50vHW2j0aqkbD5Zyr8VGhpkLiRC+1VQ2PQPbvrqmi9XAtWgmA0+5Q+qg4r51t1l e6TurBKWZwlgCT2qHUObGSKDs1kZeFCPFkkvXgRf7P/cg60MvHCwZoHpWL8X38W1KS8L u2pG3/1XDEee5Nf+XL5gMRAOcuO1x8LrJdB6ER/YQyXsx2E9N6KigAcu92wddysaIyCT QtIncfsW6HqAsGnxxArEzK1FHrJ1ILgwTI7ME98I9+uGTCmXKSe+pv7h20WnXePQmmXi 6GIg==
MIME-Version: 1.0
X-Received: by 10.140.104.236 with SMTP id a99mr5519482qgf.56.1417590802730; Tue, 02 Dec 2014 23:13:22 -0800 (PST)
Received: by 10.140.30.100 with HTTP; Tue, 2 Dec 2014 23:13:22 -0800 (PST)
In-Reply-To: <CAMfhd9VF784rJ5gXiLkB6DdwS+zAi=GDgT=792jQ=+oqcK_F3Q@mail.gmail.com>
References: <CA+Vbu7xvvfRWyqyE9sqU7VbjzNQZp+DwRWjaV3Lw0hjLr8ye1A@mail.gmail.com> <5476CB73.7090206@akr.io> <CAMfhd9XxkZsVPMcevWOgvvqbBK0JqLVCGBYfwWu0QFO5rsfbJQ@mail.gmail.com> <CABqy+sodVBbwNrA28AFxYMiw5rJxtUX3cbYCjtrYxK-48Ocd6A@mail.gmail.com> <CAMfhd9VF784rJ5gXiLkB6DdwS+zAi=GDgT=792jQ=+oqcK_F3Q@mail.gmail.com>
Date: Tue, 2 Dec 2014 23:13:22 -0800
Message-ID: <CABqy+so9ChaGBUtt0WmmeO5LJ2X-UEOSawdcuqka_PV7x5Uz2Q@mail.gmail.com>
From: Robert Ransom <rransom.8774@gmail.com>
To: Adam Langley <agl@imperialviolet.org>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/rF0uo1SlAqqDx4zIgqxtj5kD4I4
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Consensus and a way forward]
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Wed, 03 Dec 2014 07:13:33 -0000

On 12/1/14, Adam Langley <agl@imperialviolet.org>; wrote:
> On Sun, Nov 30, 2014 at 7:33 PM, Robert Ransom <rransom.8774@gmail.com>;
> wrote:
>> Third, you appear to be arguing that ECDH operations would not use the
>> Montgomery curve *isomorphic* to the Edwards curve in your Internet
>> draft, but use a *different* Montgomery curve (PinkBikeShed) which is
>> merely *isogenous* to the curve that you are proposing, in order to
>> reduce the modifications required to make the many existing
>> independent, interoperable implementations of Curve25519 operate on
>> your curve.  This would *slightly* reduce the technical disadvantage
>> of your proposal compared to Curve25519, but would clearly not
>> eliminate it.  If you do intend to propose PinkBikeShed for ECDH,
>> rather than the Montgomery curve isomorphic to the one specified in
>> your Internet draft, then that needs to be stated explicitly in your
>> draft.
>
> Yes, I agree. The draft should specify the Montgomery curve and the
> isogeny maps.

You are listed as a co-author of the draft.  If you believed that
those pieces of information should be included in it, why did you not
include them into the draft?

> I also very much hope that the CFRG doesn't just specify
> curves, but also will provide detailed guidance about their use --
> that's also missing from the draft at the moment.

The previous proposal draft-turner-thecurve25519function-01 includes a
complete statement of the Montgomery ladder.  It was submitted ‘in
full conformance with the provisions of BCP 78 and BCP 79’, and does
not include any notice forbidding modifications to it.  Thus, other
IETF participants -- including you -- are permitted to copy text from
that draft into other Internet drafts.  Why did you not include that
description of the Montgomery ladder into the draft that you
co-authored?

Your co-authors wrote a paper (listed as one of the draft's
references) which specifies algorithms to perform several
scalar-multiplication tasks.  Did you ask them to provide plain-text
descriptions of those algorithms for inclusion in the draft itself?


>> Interesting suggestion.
>>
>> Both 89747 and 121665 are 17 bits long (they are between 2^17 and 2^18
>> - 1), and 89747 has a slightly greater Hamming weight than 121665 (10
>> rather than 9); I would expect any performance improvement on due to
>> that change in curve parameter to be quite small and only applicable
>> to a very few implementation strategies.  Have you done any
>> benchmarking to quantify the performance improvement that you are
>> claiming as a technical benefit of PinkBikeShed?
>
> I've not done any benchmarking, it's just a guess. But the Edward's d
> parameter for the curve isomorphic to Curve25519 isn't 121665, it's
> +/- 121665/121666 [http://eprint.iacr.org/2007/286.pdf, section 2].
> That value doesn't have a small representation so I think that the
> PinkBikeShed curve does get to use a multiplication by a small
> constant in place of a multiplication by a large constant. That might
> be a small help.

In order to claim that your proposal only requires changing the
curve-parameter constant (A - 2)/4 from one small integer to another
in an existing Curve25519 implementation, you proposed to use the
Montgomery curve with A=358990 (i.e. PinkBikeShed) for ECDH.
PinkBikeShed is isomorphic to an Edwards curve with d equal to a ratio
of small integers, exactly like Curve25519.

Both Curve25519 and PinkBikeShed are *isogenous* to Edwards curves
with small-integer d; neither of them is *isomorphic* to one.


>> Do you believe that that possible performance improvement is a
>> sufficiently large technical benefit over Curve25519 to outweigh the
>> technical disadvantages of your proposal that you were aware of at the
>> time that you submitted it?
>
> No. I think the prevalence of Curve25519 alone is enough that the CFRG
> should adopt it. PinkBikeShed isn't what I want, but it's close and
> it's something that I can live with in order to move forward.

Do you believe that there is *any* benefit (technical, procedural, or
otherwise) in further consideration of the draft that you co-authored,
draft-black-rpgecc-00, over the previously submitted
draft-turner-thecurve25519function-01?


Robert Ransom