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

Benjamin Black <b@b3k.us> Tue, 02 December 2014 00:18 UTC

Return-Path: <b@b3k.us>
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 4C83D1AC3A5 for <cfrg@ietfa.amsl.com>; Mon, 1 Dec 2014 16:18:58 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.977
X-Spam-Level:
X-Spam-Status: No, score=-1.977 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FM_FORGED_GMAIL=0.622, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7] autolearn=ham
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 tflY79b1A4M7 for <cfrg@ietfa.amsl.com>; Mon, 1 Dec 2014 16:18:55 -0800 (PST)
Received: from mail-wg0-f49.google.com (mail-wg0-f49.google.com [74.125.82.49]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 07C711A8A54 for <cfrg@irtf.org>; Mon, 1 Dec 2014 16:18:54 -0800 (PST)
Received: by mail-wg0-f49.google.com with SMTP id n12so7372776wgh.22 for <cfrg@irtf.org>; Mon, 01 Dec 2014 16:18:53 -0800 (PST)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc:content-type; bh=HONiX0ja2QnqzESdJ0+0PGjU0aChSUUS3ir2nqffYLg=; b=Z5fz6vCFBV+R+uaYvhUBSXyn4tG7kH4YQxRIdgENrqFGDPxN5zKw+m4SKbYDeSVb2s MUeZD6t7QjhbnPUcI+kR+pzWb5StoVTW8M+cZ/3JU8/VY9WBRDf1EgzXQ3a7Vc48kwNg Y1kHN1/4JU2vhp/s05NXmiRfL/x1BjeZ6sOjo5ko1tCftTBto/kUjvO7tulMC7KeAQ4c B7myipAPtXIDf1IqlPWRYeyjHKw4XXa4orK+GNsxcqraIDdpkZ85yYDqpJojlC7K7umR Ix4Fl+Kvp4eK6octelysqPgnzvkwYFQIQWVVJOrI1rTipFBBQtDXD8FeJ32rlJPL/FG7 6wGQ==
X-Gm-Message-State: ALoCoQklSt4MFMTm1ICIBH8swaC06Mn6OaB2dWWEK0rVc+Ne6so+V4lqdE+Wln4OjgbfHJLBxKsp
X-Received: by 10.180.100.230 with SMTP id fb6mr68392619wib.73.1417479533470; Mon, 01 Dec 2014 16:18:53 -0800 (PST)
MIME-Version: 1.0
Received: by 10.217.191.195 with HTTP; Mon, 1 Dec 2014 16:18:33 -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>
From: Benjamin Black <b@b3k.us>
Date: Mon, 1 Dec 2014 16:18:33 -0800
Message-ID: <CA+Vbu7yuDncMwiAhQiDUR=LW-Rd4WU=BgaD_G+akS4JROoy1ng@mail.gmail.com>
To: "cfrg@irtf.org" <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary=f46d041824ee11bcb5050930ac40
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/38WuY6Z0S9Zq-UzZk_rjzhM-YAw
Cc: Adam Langley <agl@imperialviolet.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: Tue, 02 Dec 2014 00:18:58 -0000

Several of the responses to this proposal leave me a bit confused as it
appears they were written without having read the draft. If your
perspective is that Curve25519 must be adopted, and under no circumstances
will alternatives be considered, then it will be difficult to reach an
accommodation. If instead you are interested in achieving consensus, the
first step should be understanding alternative viewpoints and considering
how we might find a middle ground. The draft documents such a middle ground.

The draft we (Microsoft, Google and NXP) posted describes rigid generation
of parameters for (twisted) Edwards curves. The generation process is about
as minimalist as can be for generation of secure curves. Additional rules
intended to produce a specific outcome are the definition of flexibility.
Constructing a curve explicitly for a specific implementation technique is
a short-sighted and contrary to good engineering process.

In addition, having a clear, rigid generation process for the parameters
allows those in need of curves for specific applications to easily and
deterministically produce them. Several people involved in hardware
implementation have expressed their concern with only producing curves
based on special primes. For such scenarios, a random prime selection
section could be added to the draft and the resulting curves need not find
their way into TLS at all. Again, being creative in accommodating the needs
of the participants is the key to consensus.

Recall that our preference was for similarly rigid generation of 3 mod 4
special primes. We still hold that preference, but we believe so strongly
in finding a middle ground acceptable on performance and security that we
have agreed to a process that does not produce most of the "NUMS" curves
and does not include our preferred prime at the 256-bit level. p = 2^255 -
19 with rigidly generated parameters is that performant and secure middle
ground.

The generated curve for p = 2^255 - 19 is not Curve25519 and is not
isogenous to the Montgomery curve in X25519. It is, however, not vulnerable
to the extremely minor concern that a private key is a multiple of the
group order. The isogenous minimum A Montgomery curve does have that
concern, and as has already been mentioned it is a trivial problem with a
trivial solution. Those working with signatures or ECDH with x,y points,
which are the majority of scenarios outside TLS ECDH via X-only point
format (and associated Montgomery isogeny), don't need to worry about it at
all.

As some have noted, this new curve can actually be faster than Curve25519.
Preliminary benchmarking of our implementation of it bears that out. It is
unfortunate that, having argued at great length for the primacy of
performance in selection, people are rejecting similar performance gains
because some code has already been deployed or multiplying by 8 instead of
4 represents a security threat.

We were expecting implementation considerations, such as requiring use of
compressed points for x,y and x-only for ECDH at the 128-bit security
level, to be addressed in another draft. That would decouple the generation
draft from the needs of a specific working group or scenario.

There is no perfect answer, there are only acceptable arrangements of trade
offs. To echo Adam, this is something we can live with to move forward.


b