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

Watson Ladd <watsonbladd@gmail.com> Sat, 13 December 2014 01:15 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 8AE811A1B15 for <cfrg@ietfa.amsl.com>; Fri, 12 Dec 2014 17:15:18 -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 6wsehd4akPUx for <cfrg@ietfa.amsl.com>; Fri, 12 Dec 2014 17:15:15 -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 40A391A1B70 for <cfrg@irtf.org>; Fri, 12 Dec 2014 17:15:14 -0800 (PST)
Received: by mail-yk0-f169.google.com with SMTP id 79so3637466ykr.0 for <cfrg@irtf.org>; Fri, 12 Dec 2014 17:15:13 -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=nLyKgbntI7rU+A5QJn8tFGVdufD83LWnP0u8dFaBsVc=; b=yaNFQOraQdDAIPgSF2pVSL//XRD5yRKPxxB8OrpUqu6FaXMo60ILj+m9o/maVECGnZ BdcRKMzNjVskwLOreNK1jkzyYbpGwPrIdsSPBpM+oyk0Yt9f0Q/g5zfYxOY8tn4xssFt gnHoQcH99cTMJSXaJbFrIOezW7k1XseThd3RtoiMGSp4x++mA1bxqlNoffgHXwgGUIax o/qyejB0ZYXD+1Y7oBegGBqtdcLSB2Ci3zD/t6flSW6Vk95QyX3hLFHBJgT6Lze9CtJ3 039yZ/0F02zJPt5De4TRvPYkXfEM4u7mpSWfdVCTMZbsYU2BIkp7+Ptq3GRpe4Q0uy35 99UQ==
MIME-Version: 1.0
X-Received: by 10.236.61.8 with SMTP id v8mr14043815yhc.44.1418433313417; Fri, 12 Dec 2014 17:15:13 -0800 (PST)
Received: by 10.170.195.21 with HTTP; Fri, 12 Dec 2014 17:15:13 -0800 (PST)
In-Reply-To: <D0B0DC9F.39BD0%kenny.paterson@rhul.ac.uk>
References: <CA+Vbu7ye3bytMZ-j8pfZixrjF8irTOoWmRo_GwjB0LphwjXq+Q@mail.gmail.com> <20141202092847.29027.qmail@cr.yp.to> <CA+Vbu7yQoYf3ei3MADhJ1iV6BcuqVUmkg8SkQ4ud=8m7pz7AvQ@mail.gmail.com> <D0B0DC9F.39BD0%kenny.paterson@rhul.ac.uk>
Date: Fri, 12 Dec 2014 17:15:13 -0800
Message-ID: <CACsn0c=uyPT6xa4CsXPeAV31QeeO+HfsCXAxt7Ba6NOt_Y2hiA@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: "Paterson, Kenny" <Kenny.Paterson@rhul.ac.uk>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/pCgIQuv_LR7XCvGulpZk9zTz-g0
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: Sat, 13 Dec 2014 01:15:18 -0000

On Fri, Dec 12, 2014 at 2:13 AM, Paterson, Kenny
<Kenny.Paterson@rhul.ac.uk>; wrote:
> Dear Ben,
>
> Thanks for your continued contributions to this discussion. I think you
> make quite powerful arguments for keeping  draft-black-rpgecc-00 the way
> it is and not adding an extra criterion concerning divisibility of
> co-factors.
>
> Nevertheless, based on previous discussions on list (and discussions off
> list that Alexei and I have been having in our role as co-chairs), we have
> reason to believe that we will have a strong chance of making progress as
> a group, and unblocking our current logjam, if your team were to add this
> criterion to the draft.
>
> If you were also to add explicit isogenies enabling mapping to Montgomery
> form curves for the specific primes/curves at the 128-bit and 192-bit
> security levels, then this would also help move things along too.
>
> As co-chairs, then, we would like to strongly recommend that your team
> take these two significant steps to modify your draft. Modulo my
> understanding of IRTF processes, we would then be in a position to call
> for consensus on formal adoption of the draft by CFRG.

Why can't the turner-curve25519 draft be adopted? We could add the
curves for the 2^389-21 prime that Ilari has computed. As one of the
coauthors I'm surprised that no discussion of the shortcomings of this
draft, has taken place, instead we've been modifying a draft that was
further from being useful until it can be adopted.

I'm also surprised that we aren't using 2^389-21 for the same reasons
cited for using 2^255-19. We do not need complete agreement to go
forward. If we want a consensus result we'll still have gratuitous
incompatibilities and an unforced loss of additional performance, in
order to get one particular group on board. A process justified as
being driven by technical criteria has devolved into an openly
political horse trade, where we're supposed to be happy that the
2^255-19 prime is used, and ignore the issues with 2^384-317.

I'm happy to assist in writing whatever material is required to
specify the algorithms that we need to produce, such as a signature
algorithm and standalone description of the key exchange method.
Existing drafts and RFCs have fallen short here in the past. I can
only hope this does not take another 9 months.

>
> As a side note to *everyone* who has been contributing to our discussions
> to date: we are rapidly getting to the point where the process might well
> be taken away from us and solutions imposed from outside. CFRG's inability
> to reach a decision will not stand us in good stead as the preferred
> supplier of "crypto clue" to IETF.

Honestly, if the past 9 months is the best we can do, we deserve it.
(Not that the IETF works much better: the codec debate in RTCweb,
etc.) It would be a shame if the result was no clue in the IETF at
all, and I hope that we can figure out a way to make the CFRG more
effective.

While this conversation was going on I caught yet another draft with a
crypto problem, which got fixed. The authors had probably not realized
that there was a possible issue.

Sincerely,
Watson Ladd

>
> Regards,
>
> Kenny
>
>
> On 09/12/2014 05:56, "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).
>>
>>
>>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
>>
>>
>>
>>
>>
>>
>>
>
> _______________________________________________
> 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