Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Consensus and a way forward]
Benjamin Black <b@b3k.us> Sat, 13 December 2014 04:39 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 AA1A71A1B75 for <cfrg@ietfa.amsl.com>; Fri, 12 Dec 2014 20:39:55 -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 fj-nRtlWuh1u for <cfrg@ietfa.amsl.com>; Fri, 12 Dec 2014 20:39:51 -0800 (PST)
Received: from mail-wg0-f46.google.com (mail-wg0-f46.google.com [74.125.82.46]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 5C4331A00BF for <cfrg@irtf.org>; Fri, 12 Dec 2014 20:39:51 -0800 (PST)
Received: by mail-wg0-f46.google.com with SMTP id x13so10729807wgg.33 for <cfrg@irtf.org>; Fri, 12 Dec 2014 20:39:49 -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:cc:content-type; bh=ICdgMlwouuinI2wbR8GpeeunnjmeFGVVebFGiqG3X4o=; b=gyyxD+455PtHk1vE3fEB1ysLk2OoqHlM29ynGCxDy4zkuOEcAy9srZstGVzquDKzEL tC71SPAM11x1XRk1FNq3/+QsLj36drd/MebgS39wAKrlWnDjfWNuyvhwM+M85xmGQzI1 p8nfjwg04eNX4ue6VKDWsUAIYWrT+fu43l17qKl6dx5mLG7MuihEstMbfVKDfcVpy3QK 5mfcZw/84nQQ9ZxmezVp5JODUvlnEwNk7q5MDCFtpxpXX2fMJ44DHvxTuBsSQMN2cpXJ bUc8cCjvomAN+UwyhyQnXce68/VqwjzAuLx42XnrtaovQ7aMQc1+ZC4CO4U8xCG2Waen TWmQ==
X-Gm-Message-State: ALoCoQlGPLC1h53/GoanutwUj1J2U37HUcK1Ki7hzrCB2FTvhBxHpKuitb2Lofs3J8J4rY+zKOVp
X-Received: by 10.194.178.231 with SMTP id db7mr32493928wjc.112.1418445589631; Fri, 12 Dec 2014 20:39:49 -0800 (PST)
MIME-Version: 1.0
Received: by 10.217.191.195 with HTTP; Fri, 12 Dec 2014 20:39:28 -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>
From: Benjamin Black <b@b3k.us>
Date: Fri, 12 Dec 2014 20:39:28 -0800
Message-ID: <CA+Vbu7w=uq9C2_LNUX=2boDqKS0zekniOWPd+mk42eWOS3ZVXQ@mail.gmail.com>
To: "Paterson, Kenny" <Kenny.Paterson@rhul.ac.uk>
Content-Type: multipart/alternative; boundary="089e01419fc080eb1b050a11999e"
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/zLuLm07UpHnNKzKARNHI8P9IMpI
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 04:39:55 -0000
Kenny, While we remain convinced there is no compelling technical reason to make the change, we will acquiesce to the will of the co-chairs in the interest of seeing this move forward. b 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. > > 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. > > 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] 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