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

Benjamin Black <b@b3k.us> Mon, 08 December 2014 21:57 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 474F51ACFEC for <cfrg@ietfa.amsl.com>; Mon, 8 Dec 2014 13:57:30 -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 P_ib0y6IyrrY for <cfrg@ietfa.amsl.com>; Mon, 8 Dec 2014 13:57:22 -0800 (PST)
Received: from mail-wi0-f175.google.com (mail-wi0-f175.google.com [209.85.212.175]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id AB5011ACFE6 for <cfrg@irtf.org>; Mon, 8 Dec 2014 13:57:21 -0800 (PST)
Received: by mail-wi0-f175.google.com with SMTP id l15so6056391wiw.8 for <cfrg@irtf.org>; Mon, 08 Dec 2014 13:57:20 -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:content-type; bh=KZHZqALMX2ABJ9cduhITW+FC8mtgrz3fI/AF1ObMvAg=; b=m6hLAxHLI8yOoH0juY2SDaRfQD7jQz0ZGo4vizuUOpXf0WAOSwxB/PsOMi93FWkKdq dKT8N/o3T/l2AcWlUeRUj9Pm6ldHxGJvlOC8zN0pRR3pxpuDwfBdNVUp8MVh8rPI42xt /zg+ukKdedfrxgXpOSC06Ex19XM0VM9SdDAd28FnHC52HNHDTtf3W74Mgdfuf6B1KF9p MWf9K+1eycniU19cqkM9hNWm1VjFK3B3uIHtWg8cRl7W6yXopMj6Z88P6ljeKh9Khotm 8KZ6avETZGb1K5kfblD+ekCBkAUF/1+Hk0wShxS/2CyuHf2O1nqGDCyULKeLxgMlKerD NlQg==
X-Gm-Message-State: ALoCoQn8NFYMAaKg/tvBDuxgDuHAwUsERisHdCabV6wtD3PBAB892SY3brMEFegoJCqvIsp1zRca
X-Received: by 10.181.12.17 with SMTP id em17mr27336865wid.45.1418075840401; Mon, 08 Dec 2014 13:57:20 -0800 (PST)
MIME-Version: 1.0
Received: by 10.217.191.195 with HTTP; Mon, 8 Dec 2014 13:56:59 -0800 (PST)
In-Reply-To: <20141202092847.29027.qmail@cr.yp.to>
References: <CA+Vbu7ye3bytMZ-j8pfZixrjF8irTOoWmRo_GwjB0LphwjXq+Q@mail.gmail.com> <20141202092847.29027.qmail@cr.yp.to>
From: Benjamin Black <b@b3k.us>
Date: Mon, 8 Dec 2014 13:56:59 -0800
Message-ID: <CA+Vbu7yQoYf3ei3MADhJ1iV6BcuqVUmkg8SkQ4ud=8m7pz7AvQ@mail.gmail.com>
To: "cfrg@irtf.org" <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary=f46d043893c3bb68120509bb8292
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/rc1jBRVmVImc3mLEClrsXFRzxew
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: Mon, 08 Dec 2014 21:57:30 -0000

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

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.

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.

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.

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


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
>