Re: [Cfrg] Mishandling twist attacks

"Paterson, Kenny" <Kenny.Paterson@rhul.ac.uk> Wed, 31 December 2014 18:32 UTC

Return-Path: <Kenny.Paterson@rhul.ac.uk>
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 A2B4C1A009E for <cfrg@ietfa.amsl.com>; Wed, 31 Dec 2014 10:32:50 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.902
X-Spam-Level:
X-Spam-Status: No, score=-1.902 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, SPF_HELO_PASS=-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 Waq7Ry9dd8WT for <cfrg@ietfa.amsl.com>; Wed, 31 Dec 2014 10:32:44 -0800 (PST)
Received: from emea01-am1-obe.outbound.protection.outlook.com (mail-am1on0675.outbound.protection.outlook.com [IPv6:2a01:111:f400:fe00::675]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id EAB6D1A0060 for <cfrg@irtf.org>; Wed, 31 Dec 2014 10:32:43 -0800 (PST)
Received: from DBXPR03MB383.eurprd03.prod.outlook.com (10.141.10.15) by DBXPR03MB381.eurprd03.prod.outlook.com (10.141.10.11) with Microsoft SMTP Server (TLS) id 15.1.49.12; Wed, 31 Dec 2014 18:30:37 +0000
Received: from DBXPR03MB383.eurprd03.prod.outlook.com ([10.141.10.15]) by DBXPR03MB383.eurprd03.prod.outlook.com ([10.141.10.15]) with mapi id 15.01.0049.002; Wed, 31 Dec 2014 18:30:37 +0000
From: "Paterson, Kenny" <Kenny.Paterson@rhul.ac.uk>
To: "D. J. Bernstein" <djb@cr.yp.to>, "cfrg@irtf.org" <cfrg@irtf.org>
Thread-Topic: [Cfrg] Mishandling twist attacks
Thread-Index: AQHQJHiu8f86jJSxUEKDoe4rg4OX25yqBsQA
Date: Wed, 31 Dec 2014 18:30:36 +0000
Message-ID: <D0C9ED09.3B226%kenny.paterson@rhul.ac.uk>
References: <CA+Vbu7yQoYf3ei3MADhJ1iV6BcuqVUmkg8SkQ4ud=8m7pz7AvQ@mail.gmail.com> <20141230213458.22858.qmail@cr.yp.to>
In-Reply-To: <20141230213458.22858.qmail@cr.yp.to>
Accept-Language: en-GB, en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
user-agent: Microsoft-MacOutlook/14.4.7.141117
x-originating-ip: [2.96.147.218]
authentication-results: spf=none (sender IP is ) smtp.mailfrom=Kenny.Paterson@rhul.ac.uk;
x-microsoft-antispam: BCL:0;PCL:0;RULEID:;SRVR:DBXPR03MB381;
x-exchange-antispam-report-test: UriScan:;
x-exchange-antispam-report-cfa-test: BCL:0;PCL:0;RULEID:;SRVR:DBXPR03MB381;
x-forefront-prvs: 0442E569BC
x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(6009001)(479174004)(164054003)(243025005)(189002)(199003)(51704005)(24454002)(76104003)(36944003)(4396001)(86362001)(83506001)(106356001)(97736003)(1720100001)(92566001)(19580405001)(107886001)(105586002)(66066001)(36756003)(106116001)(19580395003)(15975445007)(2950100001)(2900100001)(561944003)(120916001)(74482002)(64706001)(76176999)(50986999)(102836002)(77096005)(68736005)(54356999)(87936001)(40100003)(62966003)(31966008)(99396003)(46102003)(122556002)(20776003)(77156002)(2501002)(2656002)(21056001)(559001)(579004)(19627235001); DIR:OUT; SFP:1101; SCL:1; SRVR:DBXPR03MB381; H:DBXPR03MB383.eurprd03.prod.outlook.com; FPR:; SPF:None; MLV:sfv; PTR:InfoNoRecords; MX:1; A:1; LANG:en;
received-spf: None (protection.outlook.com: rhul.ac.uk does not designate permitted sender hosts)
Content-Type: text/plain; charset="iso-8859-1"
Content-ID: <F77BFE0864C1B24194F71293AE8CE495@eurprd03.prod.outlook.com>
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-OriginatorOrg: rhul.ac.uk
X-MS-Exchange-CrossTenant-originalarrivaltime: 31 Dec 2014 18:30:36.9024 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 2efd699a-1922-4e69-b601-108008d28a2e
X-MS-Exchange-Transport-CrossTenantHeadersStamped: DBXPR03MB381
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/qqrtZnjV1oTBHtvZ1MPYVvnkDYE
Subject: Re: [Cfrg] Mishandling twist attacks
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: Wed, 31 Dec 2014 18:32:50 -0000

Dan,

I was going through the recent CFRG messages in order, and then I spotted
the one below, and decided (after consultation with my co-chair Alexey
Melnikov) that it deserved a more immediate response.

Our view is that you have crossed the line of acceptable behaviour in the
way that you are acting on the list, particularly with respect to, but not
exclusively limited to, the message below. Specifically, the tone of the
language and the way you impute motives to other CFRG participants falls
below the levels of professional behaviour that we expect from
participants in the group.

In short: it's time to stop trying to score petty points, making personal
attacks, and using what we can only assume to be deliberately provocative
language. Instead, it's time to start focussing on helping CFRG deliver
the best solution we can, given the externally imposed time constraints
that we are under, and to do so using respectful, constructive language.

I credit you with way too much intelligence not to realise a) what is at
stake here (not only for this particular process, but also for the
reputation of CFRG as a whole) and b) how your recent behaviour will
negatively affect the process. I also know that you are perfectly capable
of restraining yourself. Please start doing so.

Thanks,

Kenny (for the chairs)



On 30/12/2014 21:34, "D. J. Bernstein" <djb@cr.yp.to>; wrote:

>I think it's important for the public record to be clear on the security
>advantages of Curve25519 over PinkBikeShed.
>
>I realize that most people don't see this as important---"Microsoft has
>abandoned the PinkBikeShed proposal now; you're beating a dead horse"---
>but I have serious concerns about the procedures that have brought CFRG
>to this point. This message first discusses the procedures, and then
>discusses the technology issues. Some of these issues are also of
>interest beyond PinkBikeShed.
>
>Timeline review:
>
>   * 19 May 2005: http://cr.yp.to/talks/2005.05.19/slides.pdf was the
>     original presentation of what I now call PinkBikeShed. At the time
>     I didn't give it a name (the talk said "Curve"), and the curve
>     didn't last long---very soon afterwards I had thought through the
>     security issues carefully enough to see that Curve25519 was better.
>
>   * 16 October 2014: One of the CFRG chairs proposed taking two weeks
>     to finalize requirements and agree on "whatever benchmarking system
>     we're going to use for performance measurements", and then a month
>     to measure and settle on the final "recommendations to the TLS WG".
>
>   * 2 November 2014: Benjamin Black wrote "I don't understand the
>     insistence on rushing a decision. We're talking about choices we
>     will have to live with for 20 years. An extra month or two won't
>     kill us."
>
>     Notice the calm long-term perspective here, quite consistent with
>     the idea that CFRG wanted to take time to think carefully through
>     curve-selection issues---a process I respect and have been happy to
>     contribute to.
>
>   * 3 November 2014: The chair wrote "We are in fairly regular contact
>     with the W3C folks, and while it's true that they are waiting with
>     bated breath for our recommendations, we are not about to miss any
>     trains. ... I agree with the sentiment that we have excellent
>     choices already before us. However, if there's a reasonably simple
>     way to ensure the highest possible levels of trustworthiness in our
>     recommendations with[out] unduly compromising efficiency and
>     security, then I am prepared to sacrifice some extra time to
>     achieve it. ... And the longer we take, the better answers we can
>     hope to get on the things that really matter."
>
>   * 26 November 2014: The chair foreshadowed "significant developments
>     ... that will help us move forward with that main work of selecting
>     curves to recommend to the TLS WG." What would these developments
>     be? Finally the requirements list? The details of the publicly
>     verifiable benchmarking process?
>
>   * 26 November 2014, after sundown: Night of the Living PinkBikeShed.
>
>   * Subsequent days: Various followup discussion, both inside and
>     outside CFRG. For example, Felix von Leitner characterized
>     Microsoft's approach as "embrace+extend", and Trevor Perrin
>     characterized Microsoft's approach as a "meaningless tweak" and a
>     "terrible idea" given its impact on the existing and future code
>     base. (Microsoft can afford this sort of fragmentation, but most
>     ECC implementors can't.)
>   
>   * 28 November 2014: I sent my first "Mishandling twist attacks"
>     message, carefully explaining one of the security reasons to reject
>     PinkBikeShed. (In my messages to the CFRG mailing list, I've been
>     careful to focus on intrinsic long-term merits of curve choices,
>     rather than on how well established Curve25519 already is.)
>
>   * 1 December 2014: Black claimed that twist attacks don't apply to
>     PinkBikeShed if the curve-specifying document presents the Edwards
>     view of PinkBikeShed rather than the Montgomery view.
>
>   * 2 December 2014: I asked how Black could justify _any_ form of
>     twist security in his Edwards proposals if he believes his claim;
>     this question is still unanswered weeks later. I also explained why
>     his claim was wrong.
>
>   * 8 December 2014: Black, in the guise of responding to my message,
>     made many erroneous comments about related issues. I was extremely
>     busy and didn't have a chance to respond to this before now.
>
>   * 12 December 2014: The chair characterized Black's comments as
>     "quite powerful arguments" but said that Black should abandon those
>     arguments for the sake of "unblocking our current logjam" and
>     "making progress".
>
>     There was no explanation of why CFRG was suddenly in a rush, or why
>     CFRG was suddenly in a "logjam", or why CFRG should abandon its
>     ongoing process of settling requirements and evaluating curves
>     according to those requirements.
>
>   * 12 December 2014: Black wrote "we will acquiesce to the will of the
>     co-chairs in the interest of seeing this move forward."
>
>Some of Black's errors related to PinkBikeShed were already pointed out
>in the brief period between 8 December and 12 December, but certainly
>not all, and after 12 December people seem to have decided that no
>further comment was required on his message.
>
>It's easy to imagine how someone looking back at this record could
>imagine that Black had raised real technical objections that at this
>point are still unaddressed---and that the result was dictated by
>non-transparent politics rather than by technology. Look at the
>situation from the future reader's perspective:
>
>   * If Black's arguments were plainly bogus, or were considered and
>     rejected, or were considered and judged to be outweighed by more
>     important factors, then why did the chair four days later declare
>     the objections to be "quite powerful arguments"?
>     
>   * Black's recent behavior is quite explicitly the type of
>     "compromise" blasted in RFC 7282---and behind the scenes there's
>     even worse "horse-trading" going on. The people who sent me private
>     email along the lines of "we'll convince them to stop complaining
>     about Curve25519 if you give them their pet 384-bit prime" ought to
>     be ashamed of themselves. If a company can so easily push its pet
>     cryptography into standards, what stops an attacker from doing the
>     same with secretly weak cryptography?
>
>   * Last month Black and the chair were saying how important it was to
>     obtain "the highest possible levels of trustworthiness" in "choices
>     we will have to live with for 20 years"---and suddenly this month
>     they're rushing towards a call for "consensus" on a highly
>     questionable new Black document.
>
>The reader should also be faced with the technical evaluation: no, Black
>never had good arguments for regressing from Curve25519 to PinkBikeShed;
>no, his arguments aren't "powerful"; no, PinkBikeShed isn't some sort of
>superior Microsoft technology being repressed by politics.
>
>Enough about procedures; let me now focus on the technology.
>
>In my first "Mishandling twist attacks" message I wrote "every major ECC
>standard already multiplies scalars by the curve's cofactor" and then
>analyzed the worrisome impact on PinkBikeShed if a "protocol multiplies
>the secret scalar s by the cofactor 4 exactly as the standards say".
>This security issue for PinkBikeShed is eliminated by Curve25519.
>
>Here's the centerpiece of Black's response: "A sloppy implementor could
>just as easily misread guidance and clear cofactor 4 on Curve25519."
>
>Let's think this through, starting from the facts.
>
>The DH factor used in IEEE P1363-2000 Section 7.2.2 is "k", which by
>definition is the "cofactor k = #E/r"; of course, "r" is a big "prime
>integer" and is the order of the specified generator. The MQV cofactor
>in Section 7.2.4 is also k. The DH factor in ANSI X9.63 Section 5.4 is
>"h", the same cofactor under a different name. The MQV factor in ANSI
>X9.63 Section 5.5 is the same cofactor. I could keep going like this for
>a while. There are explanations all over the place, in these standards
>and elsewhere, of why you should multiply by the curve's cofactor.
>
>In the case of Curve25519, the curve's cofactor is amply documented as
>being 8, and the consistent message of these standards is to multiply by
>8. There's no ambiguity here, and Black gives no indication of how a
>"sloppy implementor" (or protocol designer) could "misread" any of this.
>
>It's true that, in the types of protocols I've been talking about,
>taking cofactor 4 on Curve25519 would cause very similar damage to
>taking cofactor 4 on PinkBikeShed. However, to judge the impact of
>conceivable failures, one has to rationally evaluate the probability of
>the failures. For PinkBikeShed, multiplying by 4 is _exactly_ what all
>of these standards recommend, and it's easy to see how the failures
>would happen. For Curve25519, Black's imaginary multiplication by 4 is
>_contrary_ to what all of these standards recommend. Black's claim of
>equal probability ("just as easily") isn't even marginally plausible.
>
>Benjamin Black writes:
>> I am objecting to the notion that cofactors (8,4) are in any way more
>> secure than (4,8).
>
>See my first "Mishandling twist attacks" message, and see above.
>
>> I am not objecting to twist security and the curves in the draft are
>> twist secure.
>
>This doesn't answer the question that I asked on 2 December. Let me try
>phrasing it differently.
>
>You claim that, because of your choice to specify curves in Edwards form
>rather than Montgomery form, the advanced twist attacks that I'm talking
>about "do not apply" to your draft. You therefore claim that "rigidity"
>requires taking a smaller coefficient (PinkBikeShed) rather than a
>coefficient protected against these attacks (Curve25519).
>
>Obvious analogy: You claim that, because of exactly the same choice,
>_no_ twist attacks apply to your draft. You therefore claim that
>"rigidity" requires taking a smaller (in fact, _much_ smaller)
>coefficient, ignoring _all_ twist attacks.
>
>But wait a minute: you _don't_ seem to be making these last two claims;
>these claims aren't consistent with any of the curves you've proposed.
>You must therefore have some reason for believing that Edwards curves
>_are_ subject to twist attacks. What exactly is this reason, and why do
>you think that it _doesn't_ apply to more advanced twist attacks?
>
>> 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.
>
>Yes, the implementor _can_ check whether the incoming point is on the
>curve. However, it's very easy to see how an implementor could end up
>using a scalarmult routine that doesn't include this check---see
>
>   https://duckduckgo.com/?q=elliptic+curve+scalar+multiplication
>
>for many, many, many examples---and then the attacker wins. As I wrote
>before: "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."
>
>You say that you don't agree that this is "the solution". You instead
>advocate ignoring the problem on the protocol level, and relying on the
>implementor to be careful to do this right. The simple fact is that your
>"solution" is fragile (even Hugo Krawczyk was bitten by these attacks!)
>while mine is not.
>
>More examples of the same general phenomenon, and a more detailed
>discussion of this example, appear in the "General context" section of
>my first "Mishandling twist attacks" message.
>
>> In fact, looking at the Curve41417 paper, you eschew the
>> Montgomery (or Edwards) ladder in favor of windowing.
>
>No, the paper does not "eschew" the Montgomery ladder. It says that (for
>this number of bits on this platform, and of course disregarding the
>differences in inputs) Montgomery-ladder scalarmult is "not quite as
>fast" as windowed-Edwards scalarmult, but it also says that the
>Montgomery ladder "has the advantage of fitting the computation into
>less SRAM", says that "each curve in Edwards form is birationally
>equivalent to one in Montgomery form, so there is no need to choose one
>over the other", and mentions the importance of twist-security when
>"only the [Montgomery] x-coordinate is transmitted and used".
>
>Furthermore, you're once again confusing the choice of _computation_
>with the choice of _coordinates_. I feel like a broken record here---
>starting in my first message to CFRG in July, I've pointed out a number
>of errors from your team stemming from this rather basic confusion, and
>your team has consistently dodged rather than responding.
>
>> 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.
>
>No, the paper says nothing of the sort; it simply evaluates the speed of
>scalar multiplication. Furthermore, you're _again_ confusing the choice
>of computation with the choice of coordinates.
>
>> I am also objecting to your repeated claims, contradicted by your own
>> work, that single-coordinate ladders are required.
>
>Precisely what do you think you mean by "single-coordinate ladders are
>required", and precisely which claims do you think you're objecting to?
>Exact quotes in context, please, not careless paraphrases.
>
>Here's a sampling of what I've actually written. The Montgomery ladder
>is a remarkably simple, fast, constant-time algorithm for single-scalar
>multiplication on (e.g.) Curve25519:
>
>   x2,z2,x3,z3 = 1,0,x1,1
>   for i in reversed(range(255)):
>     bit = 1 & (n >> i)
>     x2,x3 = cswap(x2,x3,bit)
>     z2,z3 = cswap(z2,z3,bit)
>     x3,z3 = ((x2*x3-z2*z3)^2,x1*(x2*z3-z2*x3)^2)
>     x2,z2 = ((x2^2-z2^2)^2,4*x2*z2*(x2^2+A*x2*z2+z2^2))
>     x2,x3 = cswap(x2,x3,bit)
>     z2,z3 = cswap(z2,z3,bit)
>   return x2*z2^(p-2)
>
>For DH I've repeatedly said that the Montgomery ladder minimizes
>tensions between speed, simplicity, and security; I've seen no arguments
>to the contrary. My primary reason for objecting to cofactor-1 curves is
>that those curves fail to provide this important option to DH protocol
>designers and DH implementors.
>
>There are many situations---most obviously, signatures---where most
>implementors will want to do something different from the Montgomery
>ladder. If you think that I've told them "No, you have to use the
>Montgomery ladder!" then you're mistaken. If you think that specifying a
>Montgomery curve forces people to use the Montgomery ladder then you're
>again mistaken.
>
>> Suggesting that (4,8) vs (8,4) introduces security risk is not a
>> technical argument about the strength of the curve.
>
>Are you trying to say that twist security isn't a technical issue, or
>that leaks of scalar bits inside existing and future protocols aren't a
>technical issue, or that you have some more limited notion of curve
>"strength" that doesn't cover these security issues?
>
>> The additional criterion you are describing is difficult to see as
>> "twist security".
>
>That depends on how broad your protocol view is. As I said before,
>unless the RNG is backdoored, standard DH is _not_ noticeably damaged by
>this particular type of leak of scalar bits; but there are other
>protocols that _are_ seriously damaged.
>
>> The curves in the draft are twist secure by any reasonable definition,
>> including your own SafeCurves twist security requirements.
>
>There's one attack paper after another showing how to break
>implementations of standard ECC (and of semi-standard ECC making similar
>mistakes, such as Bitcoin). I'm talking about major failures in major
>protocols such as DH and signatures.
>
>The traditional response to these problems is to blame the implementor.
>SafeCurves blames the curve choices, declaring the underlying curves to
>be "unsafe", since we know exactly how the underlying implementation
>pitfalls are eliminated by better choices of curves. SafeCurves is
>completely explicit about what it means by "safe", and about why it is
>drawing that line.
>
>If some particular curve is labeled as "safe" by SafeCurves, can you
>conclude that it has identical security to all of the other curves
>labeled "safe" by SafeCurves? Of course not: this conclusion is silly,
>and certainly isn't justified by anything SafeCurves says.
>
>It should also be obvious, as a procedural matter, that CFRG needs more
>stringent requirements than SafeCurves. The BADA55 paper shows that
>there are more than a million "safe" curves (including Brainpool-level
>rigidity) even without exploiting variations in primes; something is
>seriously wrong if CFRG is actively recommending all of those curves for
>deployment.
>
>> 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.
>
>Let me get this straight. You think that the amazing simplicity and
>robustness of Montgomery coordinates for DH are _bad_ things since
>
>   (1) you think they might encourage implementors to oversimplify some
>       unusual protocol that relies on "contributory" behavior and
>
>   (2) you think this oversimplification would be less likely if
>       implementors were forced to use other coordinates for DH?
>
>Even if the (many) unclear details in this argument were filled in, the
>argument would be completely missing the incredible importance of DH.
>DH obviously outweighs all of the "contributory" protocols that have
>ever been invented.
>
>The analogy to the PinkBikeShed/Curve25519 comparison also doesn't work.
>For PinkBikeShed/Curve25519, the DH situation is the same and the
>lesser-known protocols are the tiebreaker.
>
>> using p = 1 mod 4 primes introduces the concern you are raising
>
>First, this isn't an argument for PinkBikeShed over Curve25519; they
>both use the same prime.
>
>Second, this argument is incorrect. I'm talking about curves where
>multiplying by the curve cofactor doesn't clear the twist cofactor.
>Curve25519 is _not_ one of these curves, but the prime _is_ 1 mod 4.
>
>> 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.
>
>First, this isn't an argument for PinkBikeShed over Curve25519.
>
>Second, this argument gets the technical facts all wrong. Taking primes
>that are 3 mod 4 _allows_ equal cofactors but doesn't "ensure" them.
>More importantly, having the twist cofactor _divide_ the curve cofactor
>fully solves the problem I'm talking about; there is no reason to have
>the cofactors equal.
>
>Third, this argument gets the historical facts all wrong. The prime for
>Curve41417 was the output of a performance-focused search, and it
>happened to be 3 mod 4. Curve1174 _did_ require 3 mod 4---but the reason
>for this requirement had nothing to do with cofactors; the reason was to
>give an example of a curve supporting the Elligator 1 function. The
>introduction of the Elligator paper is completely explicit in saying "we
>introduce a high-security high-speed elliptic curve that supports the
>[Elligator 1] function".
>
>> 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".
>
>Actually, the paper contains a considerably more detailed discussion of
>cofactor requirements, although to see this you have to read the paper
>and understand what some formulas are saying---a naive word search isn't
>adequate.
>
>In particular, in the "Security" section, the "Small-subgroup attacks"
>subsection gives a unified description of small-subgroup attacks and
>twist attacks, describes the information leaked considering the curve
>cofactor 8 and the twist cofactor 4, and observes that the
>multiplication of scalars by 8 eliminates the leak.
>
>For the security analysis in the paper, it's irrelevant whether this
>multiplication is
>
>   * by the curve cofactor (as all the standards say) or
>   * by the lcm of curve and twist cofactors (as the paper introduction
>     says).
>   
>The reason it's irrelevant is that for Curve25519 these two options are
>identical. This is exactly where PinkBikeShed would have created an
>unnecessary conflict, begging implementations to do the wrong thing.
>
>> 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.
>
>All of these curves can be viewed as Montgomery curves _and_ as complete
>Edwards curves. The Edwards view is better for signatures and similar
>speed for DH (depending on exact sizes, compression, etc.), although
>Montgomery is by far the simplest DH option.
>
>The reason that Curve25519 didn't require completeness in Edwards form
>is obvious from the following timeline:
>
>   * ECC 2005: I introduced Curve25519.
>
>   * 2007: Tanja Lange and I went to a surprising talk by Edwards
>     presenting what are now called "original Edwards curves". We then
>     introduced "Edwards curves", in particular introduced "complete
>     Edwards curves" (none of which are original Edwards curves), and
>     introduced fast algorithms for arithmetic on Edwards curves.
>
>Surely you understand that it would have been rather difficult to make
>efficiency choices and security choices on the basis of tools that
>nobody knew about until two years later. You can think of Curve25519 as
>being lucky for also meeting the newer requirements, and then the fact
>that it was introduced so early makes it arguably _more_ rigid---curve
>manipulation would have had to be based on secret attacks known in 2005.
>
>Of course, any manipulation of, e.g., NIST P-224 would have had to be
>based on attacks known in the 1990s. The critical difference is that
>P-224 _doesn't_ meet newer public requirements. For example, P-224
>doesn't meet the SafeCurves twist-security requirements. P-224 turns out
>to be at the attacker's perfect level of twist-insecurity, similar to
>DES, breakable at moderate cost while still being plausibly deniable.
>
>> 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).
>
>Obviously very large cofactors aren't compatible with security, but very
>specific rules such as cofactor _minimality_ and cofactor _equality_
>aren't required. Even NIST managed to get this right in the original
>NIST-curve specification: it advocated minimal cofactors for
>"efficiency", not for security.
>
>What ultimately matters is the tradeoff between the security level and
>performance. This is influenced in a complicated, but measurable, way by
>choices of primes, cofactors, etc. In the case of Curve41417, we
>obtained a surprisingly small d by allowing (8,8), although of course
>this also reduced the rho security from 2^205.8 to 2^205.3.
>
>---Dan
>
>_______________________________________________
>Cfrg mailing list
>Cfrg@irtf.org
>http://www.irtf.org/mailman/listinfo/cfrg