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

Watson Ladd <watsonbladd@gmail.com> Tue, 09 December 2014 02:58 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 DB25F1A1A1C for <cfrg@ietfa.amsl.com>; Mon, 8 Dec 2014 18:58:59 -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 x0n3RdpUm8tb for <cfrg@ietfa.amsl.com>; Mon, 8 Dec 2014 18:58:57 -0800 (PST)
Received: from mail-yh0-x233.google.com (mail-yh0-x233.google.com [IPv6:2607:f8b0:4002:c01::233]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id BC43C1A1A80 for <cfrg@irtf.org>; Mon, 8 Dec 2014 18:58:56 -0800 (PST)
Received: by mail-yh0-f51.google.com with SMTP id a41so2926651yho.10 for <cfrg@irtf.org>; Mon, 08 Dec 2014 18:58:56 -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=Ouhl99q45I2rZtYvG0luvhfRWfalxxnB4ztf7p+QP74=; b=dqxfngys7ko6xRW+sUlFFQUXcPUqJnKO40suQ0DGHDiH1E6d3FTJ7ONyyzjyp108ov C0hFUcnfo7+yoEcVMbwksX25Qy+FiYxn/uzm+cGcBqTiBnfk/pCTCCtEA1GYvGLczkzu HBpTDbdLkSQyTlgdPxHoThonlQNqs5tTYQrCopItmEdbSMyoDyfGOdGypF6tjN7dtiXB VaGFZGSvFxgIlcslcLrY5Sp+KQLGtpxCTeC/ldevCkX3tXG761lOxEc1Pj4HrPkcwEiy bN+0aIfVk9m0MKNqgDb4gdEomCODbFaTv5XgNGlOfb4onG7v1alfYQG5aUJF9SvPKHWa IRfQ==
MIME-Version: 1.0
X-Received: by 10.236.61.8 with SMTP id v8mr670550yhc.44.1418093935989; Mon, 08 Dec 2014 18:58:55 -0800 (PST)
Received: by 10.170.195.21 with HTTP; Mon, 8 Dec 2014 18:58:55 -0800 (PST)
In-Reply-To: <CA+Vbu7yQoYf3ei3MADhJ1iV6BcuqVUmkg8SkQ4ud=8m7pz7AvQ@mail.gmail.com>
References: <CA+Vbu7ye3bytMZ-j8pfZixrjF8irTOoWmRo_GwjB0LphwjXq+Q@mail.gmail.com> <20141202092847.29027.qmail@cr.yp.to> <CA+Vbu7yQoYf3ei3MADhJ1iV6BcuqVUmkg8SkQ4ud=8m7pz7AvQ@mail.gmail.com>
Date: Mon, 8 Dec 2014 18:58:55 -0800
Message-ID: <CACsn0cm9QFq3u1Q492YSvEcd6hMq+ACGyPkfi3bHAfWH_4=oBA@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: Benjamin Black <b@b3k.us>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/CKB0hf9OvbkWGI-BR5o-ObpQf1o
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: Tue, 09 Dec 2014 02:59:00 -0000

On Mon, Dec 8, 2014 at 1:56 PM, Benjamin Black <b@b3k.us>; wrote:
>>Benjamin Black writes:
>>> The concerns do not apply to the twisted Edwards curve we generated,
>>> only to the isogenous Montgomery curve.
>>
>>False.
>>
>>Invalid-curve attacks completely break the simplest DH implementations
>>in Montgomery coordinates _and_ in Edwards coordinates. Rather than
>>blaming the implementor, we eliminate these security failures by
>>
>>   * adding twist security, for both Montgomery and Edwards, and
>>   * switching to single-coordinate ladders.
>>
>>This is the primary motivation for twist security (and a closer look,
>>as I've explained in detail, shows a twist-security criterion that's met
>>by Curve25519 and not by PinkBikeShed). This has nothing to do with the
>>superficial differences between the Montgomery x and the Edwards y, both
>>of which support ladders.
>>
>
> The additional criterion you are describing is difficult to see as "twist
> security". The curves in the draft are twist secure by any reasonable
> definition, including your own SafeCurves twist security requirements.
> Looking at your Curve25519 paper there is a single mention of requirements
> on cofactors: "Multiply the secret key by a small power of 2 to account for
> cofactors in the curve group and the twist group". There is no reading of
> this that indicates selection of (8,4) is needed or was even a consideration
> at the time. In the recent Curve41417 paper I similarly find a single
> mention of cofactor requirements: "For security we ... insist on the same
> level of twist-security as Curve25519 — the cofactors of the curve and its
> twist are in {4, 8}." No mention of either requiring the cofactors be equal
> or that they be minimal (which they aren't).

All DJB is saying is that a PinkBikeShed implementation using the
Montgomery ladder, which doesn't validate points, and clears the low 2
bits, not 3, leaks one additional bit, whereas a Curve25519
implementation will not.

>
> Suggesting that (4,8) vs (8,4) introduces security risk is not a technical
> argument about the strength of the curve. A sloppy implementor could just as
> easily misread guidance and clear cofactor 4 on Curve25519. A sloppy
> implementor could even more easily skip checks for weak keys when using
> Montgomery Curve25519 outside of DH. All Curve25519 documentation makes
> clear all 32-byte strings are valid keys. That this is so only for DH is
> easily forgotten and I've not found a Curve25519 implementation that
> performs the required check.

Have you seen implementations that don't deal only with DH? A protocol
that requires points to be torsion points would need implementations
that do check, and PinkBikeShed doesn't change this property.

>
> Further, using p = 1 mod 4 primes introduces the concern you are raising.
> Rather than blaming the implementor for clearing the "wrong" cofactor, we
> can eliminate this "security failure" by using p = 3 mod 4 to ensure the
> cofactors are equal, which is the choice you made for both Curve1174 and
> Curve41417. Looking to SafeCurves rigidity criteria we see Curve1174
> described with "Curve and twist orders chosen as {4*prime,4*prime} for
> security", but for Curve25519 we see "Curve and twist orders required to be
> {4*prime,8*prime} for security". Once again, no indication that (8,4) is
> required.
>
> Looking through all the curves you list, we see a wide variety of
> justifications for any given choice, with qualitative comments about
> "security", "performance", or "efficiency", but little consistency in the
> results:
>
> Curve1174: "Curve and twist orders chosen as {4*prime,4*prime} for security"
> Curve25519: "Curve and twist orders required to be {4*prime,8*prime} for
> security"
> Curve41417: "Curve and twist cofactors limited to {4,8} for security"
>
> Curve1174: "Edwards curve shape x^2+y^2=1+dx^2y^2 chosen for efficiency."
> Curve25519: "Montgomery curve shape y^2=x^3+Ax^2+x chosen for efficiency"
> Curve41417: "Edwards curve shape x^2+y^2=1+dx^2y^2 chosen for efficiency"
>
> Curve1174: "Complete Edwards curve chosen for security."
> Curve25519: No such statement.
> Curve41417: "Complete Edwards curve chosen for security."
>
> It is difficult to see this as rigidity.

Put "BADA55ECC" into the hexadecimal constants of a curve selected by
the methodology DJB used to pick Curve25519. It's easy to see that
Microsoft had equally substantial freedom to manipulate it's curve
choice, as shown by the fact that the new generation method produces
the same curve modulo 2^521-1.

Most of the reduction in DOF comes from requiring minimal parameters
for some reasonable model subject to some reasonable criteria,
together with forcing primes of the form 2^s-c. Arguing that one
choice is "more rigid" than another is aesthetics.

>
> I do not agree with your assertion that "adding twist security" _and_
> "switching to single-coordinate ladders" is the solution against security
> failures when it comes to invalid-curve attacks. Windowing implementations
> on complete Edwards curves can be implemented securely and eliminate any
> risks against those attacks. So it is correct to say that in practice "the
> concerns do not apply to the twisted Edwards curve we generated, only to the
> isogenous Montgomery curve". In fact, looking at the Curve41417 paper, you
> eschew the Montgomery (or Edwards) ladder in favor of windowing. In this
> case, the performance advantages of Edwards trump the irrefutable and
> essential requirement for eliminating "security failures" above via use of
> single-coordinate ladders. Obviously, single-coordinate ladders are not a
> hard requirement.

The same is true for short Weierstrass curves. But I don't see why the
choices a particular implementation, written very carefully by experts
in the field, reduces the impact of traps for the nonexperts who write
the majority of implementations.

By requiring twist security, we've already chosen to support
single-coordinate ladders. If a check was enough, twist security would
not be required. Why not design the ladder in such a way to never leak
bits? Given that we are using cofactor multiplication to ensure that
matching test vectors is enough, we will have to multiply by
2*cofactor for PinkBikeShed to have the same security.

>>If you disagree, please explain why you're requiring _any_ type of twist
>>security for Edwards curves. Why aren't you saying something like "The
>>larger d forced by 'twist security' is a violation of rigidity" and
>>objecting to the whole concept of twist security for Edwards curves?
>
> I am not objecting to twist security and the curves in the draft are twist
> secure. I am objecting to the notion that cofactors (8,4) are in any way
> more secure than (4,8). Your own statements on SafeCurves and in the
> Curve25519 and Curve41417 papers support there being no difference. I am
> also objecting to your repeated claims, contradicted by your own work, that
> single-coordinate ladders are required. And since there is no such
> requirement and no security difference, I want the curve generated via the
> process with fewest qualitative, opinion-based constraints.

-Some people think twist security is not required
-Some people think cofactor 1 is required
-Some people think we need to specify short Weierstrass curves
-Some people think we need random primes
-Some people think we should keep c small and vary s in 2^s-c.

While debating the fate of a single bit might be far less
controversial than the above, I don't see how it is more or less a
qualitative constraint then the others, some have which been accepted
by the NUMS group, and some of which have not.
>
>
> b
>
>
>
> On Tue, Dec 2, 2014 at 1:28 AM, D. J. Bernstein <djb@cr.yp.to>; wrote:
>>
>> Benjamin Black writes:
>> > The concerns do not apply to the twisted Edwards curve we generated,
>> > only to the isogenous Montgomery curve.
>>
>> False.
>>
>> Invalid-curve attacks completely break the simplest DH implementations
>> in Montgomery coordinates _and_ in Edwards coordinates. Rather than
>> blaming the implementor, we eliminate these security failures by
>>
>>    * adding twist security, for both Montgomery and Edwards, and
>>    * switching to single-coordinate ladders.
>>
>> This is the primary motivation for twist security (and a closer look,
>> as I've explained in detail, shows a twist-security criterion that's met
>> by Curve25519 and not by PinkBikeShed). This has nothing to do with the
>> superficial differences between the Montgomery x and the Edwards y, both
>> of which support ladders.
>>
>> If you disagree, please explain why you're requiring _any_ type of twist
>> security for Edwards curves. Why aren't you saying something like "The
>> larger d forced by 'twist security' is a violation of rigidity" and
>> objecting to the whole concept of twist security for Edwards curves?
>>
>> ---Dan
>>
>> _______________________________________________
>> Cfrg mailing list
>> Cfrg@irtf.org
>> http://www.irtf.org/mailman/listinfo/cfrg
>
>
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg
>



-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin