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
- [Cfrg] Consensus and a way forward Benjamin Black
- Re: [Cfrg] Consensus and a way forward Watson Ladd
- Re: [Cfrg] Consensus and a way forward Joppe Bos
- Re: [Cfrg] Consensus and a way forward Hannes Tschofenig
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Alyssa Rowan
- Re: [Cfrg] Consensus and a way forward Ilari Liusvaara
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Adam Langley
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Alyssa Rowan
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Mike Hamburg
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Alyssa Rowan
- Re: [Cfrg] Consensus and a way forward Paterson, Kenny
- Re: [Cfrg] Consensus and a way forward Paterson, Kenny
- Re: [Cfrg] Consensus and a way forward Paterson, Kenny
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Benjamin Black
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Alexey Melnikov
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Michael Hamburg
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Benjamin Black
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Alyssa Rowan
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Robert Ransom
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Adam Langley
- Re: [Cfrg] Consensus and a way forward Lochter, Manfred
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Ilari Liusvaara
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Robert Ransom
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Benjamin Black
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Watson Ladd
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Tony Arcieri
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Benjamin Black
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Alyssa Rowan
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… D. J. Bernstein
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Robert Ransom
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Benjamin Black
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Watson Ladd
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Paterson, Kenny
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Alyssa Rowan
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Watson Ladd
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Benjamin Black
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Robert Ransom
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Paul Hoffman
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Alexey Melnikov
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Paterson, Kenny
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Alexey Melnikov
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Watson Ladd
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Paterson, Kenny
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Harry Halpin
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Paul Hoffman
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Watson Ladd
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Tanja Lange
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Salz, Rich
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Tony Arcieri
- Re: [Cfrg] Mishandling twist attacks D. J. Bernstein
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Paterson, Kenny
- Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Conse… Tanja Lange
- Re: [Cfrg] Mishandling twist attacks Paterson, Kenny
- Re: [Cfrg] Mishandling twist attacks D. J. Bernstein
- Re: [Cfrg] Mishandling twist attacks Salz, Rich
- Re: [Cfrg] Mishandling twist attacks Stephen Farrell
- Re: [Cfrg] Mishandling twist attacks Adam Back