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

Watson Ladd <watsonbladd@gmail.com> Tue, 02 December 2014 01:56 UTC

Return-Path: <watsonbladd@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 758B51A1A7A for <cfrg@ietfa.amsl.com>; Mon, 1 Dec 2014 17:56:40 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Level:
X-Spam-Status: No, score=-2 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, SPF_PASS=-0.001] 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 stN9_GAXNpy9 for <cfrg@ietfa.amsl.com>; Mon, 1 Dec 2014 17:56:38 -0800 (PST)
Received: from mail-yk0-x229.google.com (mail-yk0-x229.google.com [IPv6:2607:f8b0:4002:c07::229]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id B74B81A008B for <cfrg@irtf.org>; Mon, 1 Dec 2014 17:56:38 -0800 (PST)
Received: by mail-yk0-f169.google.com with SMTP id 79so5415129ykr.28 for <cfrg@irtf.org>; Mon, 01 Dec 2014 17:56:38 -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; bh=ucJV3TLxdDBkFEFd4tUeY9D87v99vYEDS4CCnMdJchE=; b=TvT5vn41iYA9H7elWMKlY7dyo9no6VSt3MlnRcUclqW1YrIo39LnmOHH2UW7eVOXBa O+PQmLunYmRXzpvpyNqQudoxZtPcn/p9t3c+WStHWjFp/xYLrn4OdbOyzZihlBfF7xBb 1Gz66IssDUCk/1xR53ZtiH7Z8TYC/Wmv4sONu0UJw3DYLEqpnRF5/Q5FJTyVciNPdD7z 32LrXDvn3xRIGI0UotF0eobnOP+LXVDcPE71w7tBHUlOd55ExBfWDwlir0pxzM839rh0 DBWkbU7Ri69FX4Ukv0wtRga9WrYNUXFZGGLUULviGd64vQAjEW1BS+HzXHT7qa2t+WYM cEtQ==
MIME-Version: 1.0
X-Received: by 10.170.214.6 with SMTP id g6mr72955711ykf.34.1417485397937; Mon, 01 Dec 2014 17:56:37 -0800 (PST)
Received: by 10.170.195.21 with HTTP; Mon, 1 Dec 2014 17:56:37 -0800 (PST)
In-Reply-To: <CA+Vbu7yuDncMwiAhQiDUR=LW-Rd4WU=BgaD_G+akS4JROoy1ng@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> <CA+Vbu7yuDncMwiAhQiDUR=LW-Rd4WU=BgaD_G+akS4JROoy1ng@mail.gmail.com>
Date: Mon, 1 Dec 2014 17:56:37 -0800
Message-ID: <CACsn0c=LFB+Q=x7vf=PZtPj1ZrabHD8AGJjSHs0ApBRf=08wpA@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: Benjamin Black <b@b3k.us>
Content-Type: text/plain; charset=UTF-8
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/EdmywyTWUGwqxPNpO3-1X_AvwQE
Cc: Adam Langley <agl@imperialviolet.org>, "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: Tue, 02 Dec 2014 01:56:40 -0000

On Mon, Dec 1, 2014 at 4:18 PM, Benjamin Black <b@b3k.us>; wrote:
> 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.

To reach that middle ground you changed the generation procedure from
the initial draft to match E-521. Professor Bernstein has pointed out
that there is an (admittedly minor) security related reason why he
rejected PinkBikeShed. Why not add this criterion to the generation
method? You already did it to get the right curve modulo 2^521-1 after
all. You also changed the choice of primes. Why not change the choice
of prime near 2^384 as well?

Were the initial parameters not rigid, or are these new parameters less rigid?

>
> 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.

What do random primes have to do with anything related to the request
from the TLS WG, particularly if we don't recommend them for TLS?

>
> 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.

What about the 384 bit level, where the choice made in the draft is
not a middle ground between performance and (mythical) security, but
rather to favor a rather poor choice of prime? This was a clearly
political exercise.

>
> 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.

I'm having trouble seeing how a change between constants of roughly
the same size can lead to a 10-15% performance gain. What I can see is
how an implementor can compare a highly optimized implementation of
one curve to a less-well optimized implementation of another, then
make a claim about the curves.

Unless the benchmarking code is made publicly available, I'm skeptical
of such claims.

Sincerely,
Watson Ladd