2010/575 says that it speeds up ECDLP for a "large class of elliptic curves." In fact, the elliptic curves targeted in this paper are quite special and rare, and are already excluded by every ECC standard.

2010/575 says that its example of a "vulnerable" curve has "no special features that would rule it out as undesirable from a cryptographic point of view." In fact, ECC standards for ten years have had perfectly clear prohibitions on all of the extension fields that could possibly be vulnerable to Weil-descent attacks, including this paper's attack.

There have already been many papers exploring the limits of Weil-descent attacks. These papers are useful for people who want to live life on the edge and skirt the boundaries of the attacks. However, these papers are of no relevance to mainstream elliptic-curve cryptography.

---D. J. Bernstein
Research Professor, Computer Science, University of Illinois at Chicago

To hit those who work on this problem with the "standards" complaint is disingenuous. First, it's wrong, and second, it's unhelpful.

Although some standards (like NIST) certainly forbid the base fields I consider, a great deal of the literature and many other standards actively use them. In fact, the IEE-P1363a-d4 standard proposal even had algorithms in it for elliptic curves over such extension fields. Moreover, any restriction on odd q (for GF(q)) is often missing in the literature and in talks (see for instance page 41 of [cr.yp.to]).


I think our energy is better spent implementing these attacks.

-Otto Johnston

No. All ECC standards in the past ten years are immune to Weil-descent attacks. The only fields allowed by the standards are F_p and F_{2^p} for various sensible choices of p. The safety of F_p against Weil descent is obvious, and the safety of each of the standard fields F_{2^p} was established by Menezes and Qu soon after the introduction of Weil descent (http://www.cacr.math.uwaterloo.ca/techreports/2000/corr2000-48.ps).

Weil descent certainly poses problems for fields such as F_{2^{155}} (see [eprint.iacr.org]) and F_{(2^61-1)^3} (see Example 3 in [homepage.mac.com]). But those fields are prohibited by the ECC standards.

I see no justification for the claim that this prohibition is "often missing in the literature and in talks." The cited example is a talk titled "Introduction to elliptic curves" defining Edwards curves over arbitrary non-binary finite fields. A subsequent slide says that in crypto one has to "check 'twist security', 'embedding degree', et al." Anyone reading "et al." sees that there are other criteria to check, consults a reference such as the Handbook of Elliptic and Hyperelliptic Curve Cryptography, and finds a comprehensive list of security criteria, including a prohibition on fields that could be vulnerable to Weil descent.

There are certainly some papers considering the possibility of improving speed by violating this prohibition; [eprint.iacr.org] is a recent example. Even over fields where Weil descent applies, it often seems to apply to only a small fraction of curves, and even for those curves it often doesn't seem to make a big difference in security. Maybe continued analysis will show that Weil descent has reached its limits, or maybe it will find improved descent algorithms; either way, describing such an attack on such rare curves as "a discrete logarithm attack on elliptic curves" is a wild exaggeration.

---D. J. Bernstein
Research Professor, Computer Science, University of Illinois at Chicago

As to the reference to your own work where these curves show up, I disagree with you that someone would be inspired to fix the problem with a magic internet search inspired by the words "et al." This is just not serious. A simple google search finds all kinds of "standards" without any restriction on the base field, much like the one I cited last time. I hope they are not in wide use, but they certainly indicate some confusion on this topic.

But now you have decided to attack my title. You are certainly aware of "Reducing elliptic curve logarithms to logarithms in a finite field" by Menezes, Okamoto, and Vanstone (STOC 91). This was about an extremely small class of elliptic curves, which does not at all diminish the importance of the result. Would you call this a "wild exaggeration" as well? The authors certainly did not mean this title applied to every elliptic curve. If it did, there would be no need for most of ECC. And this is just one example! We could go on all day writing about titles that might be "wild exaggerations" if we apply your logic.

My work is not even about Weil descent. It bypasses Weil descent and constructs another group. This is made very clear in the paper. Unfortunately, my paper is not really the issue here. You simply attack the entire area of research.

No, these curves don't show up in my ECC work. The talk that Johnston cited recommends precisely one elliptic curve for cryptography, namely Curve25519, and of course Curve25519 (like all of the NIST curves) is invulnerable to any attack of this type.

The idea that somebody is going to take a general definition of elliptic curves, misunderstand it as a definition of elliptic curves suitable for ECC, generate his own bad curve, implement his bad curve, manage to convince users to adopt that curve without anybody ever checking any discussions of ECC security from any standards or surveys in the last ten years, be so lucky as to avoid the typical curves vulnerable to other attacks, and be so astonishingly unlucky as to end up with one of the special curves vulnerable to Weil descent, is too absurd to warrant further discussion.

Johnston's repeated pointers to an IEEE P1363 draft are also missing any mention of how ancient that draft is. There were a few proposals in the 1990s of curves over fields such as F_{2^155} and F_{(2^61-1)^3}, but Frey's famous talk on Weil descent in 1998 (http://www.cacr.math.uwaterloo.ca/conferences/1998/ecc98/frey.ps), followed by a series of papers showing that Weil descent works for at least occasional curves, quickly killed interest in those proposals.

As for "the entire area of research": Continued exploration of the exact boundaries of Weil descent is respectable work in computational number theory (if it's new; I'm privately told that Johnston should compare his paper to the 2003 paper [homes.esat.kuleuven.be]), and I've already outlined a way that it might help produce better cryptosystems someday, but it is not even marginally threatening to modern elliptic-curve cryptography.

---D. J. Bernstein
Research Professor, Computer Science, University of Illinois at Chicago

So, you drop the "title" debate. We are making progress! Let's try for some more. Let's also work on formatting so that as you abandon certain issues and try to bring up new ones, I can keep a clear track of what still needs to be refuted.

1. If you understood the research in this area, then you would know that (http://homes.esat.kuleuven.be/~jscholte/weilres.pdf) is dealt with by Satoh's Eurocrypt 2009 paper, which I discuss in my work. To be specific, the author of the work you cite does not bring up discrete logarithms beyond the introduction. It isn't relevant here. Going from elliptic curves to genus 2 curves is not enough. One must do much more. The author hints in the introduction that DLP work might be possible in extensions of his work, but he never returns to this topic at all throughout the rest of his paper. He never followed it up with other papers either. It's a difficult topic, so we shouldn't blame him for this. We also shouldn't see things that are not there. He isn't doing what I'm doing at all. And seriously, you should read what you cite before you wave it around.

2. The weak curves I attack most definitely show up in your ECC work. You define Edward's curves over any finite field in odd characteristic. This contains the class of weak elliptic curves discussed in my paper. The deep theory here goes like this: when one non-empty set is a subset of a second set, then the second set contains objects from the first set. Difficult? If you want to talk about distributions, you might want to actually look at my text first. My curves are not "rare," they grow at least in size q/2. And this is a crude lower bound -- it's likely to be much more when the isogenies are factored in.

3. The IEEE P1363 proposals have even been updated recently. Up until the 2006 drafts, there were still unrestricted extension fields for elliptic curves in the documents. Since you know all of the standards about absolutely every aspect of ECC in the last ten years (minus the things I find), perhaps you can do the research and tell me what the current state of IEEE P1363 is. I don't have the password for the latest documents. I guess I could get it, but it's more fun if you do it. Then I can look for other standards for our next round. But seriously, "every" standard? Are you kidding? Half of the theory community doesn't understand this topic, much less the engineers. The irony here is that over at (http://www.ellipticsemi.com/pdf/presentations/EC_overGF_in_cryptography.pdf) your name comes up with a proposal for ECC over arbitrary finite fields in odd characteristic (page 8, and then on to page 15). It's very clear the industry is confused on this point. Keep at this one, though. Soon we'll find a nice list of companies to help.

I've checked a 1999 draft of IEEE P1363. The "algorithm for generating EC parameters" (A.16.7) requires the field size q to be "an odd prime p or 2^m." The "algorithm for validating EC parameters" has the same requirement.

I've also checked Certicom's SEC 1. It starts by imposing the same requirement, allowing only q=p or q=2^m. It then says that "composite m was avoided to align this specification with other standards efforts and to address concerns expressed by some experts about the security of elliptic curves defined over F_{2^m} with m composite - see, for example, [32]." The citation is to Galbraith-Smart, one of the first Weil-descent papers.

I've also checked FIPS PUB 186-3. Appendix D, "Recommended elliptic curves for federal government use," specifies the NIST curves and states that they were "generated using SHA-1 and the method given in the ANS X9.62 and IEEE Standard 1363-2000 standards." The only allowed field sizes are certain primes p and certain powers 2^p.

I've also checked Certicom's SEC 2, which specifies the NIST curves and various additional curves. The only allowed field sizes are certain primes p and certain powers 2^p.

I've also checked RFC 5480, "Elliptic Curve Cryptography Subject Public Key Information." This specification requires the SEC curves, and prohibits use of a historical syntax that allowed arbitrary primes p and arbitrary powers 2^m. Even the historical syntax didn't allow powers of odd primes.

There are also specifications and deployments of Curve25519. The original Curve25519 paper selects a prime field for performance reasons, but also mentions (citing two Weil-descent papers) that prime fields have "the virtue of minimizing the number of security concerns for elliptic curve cryptography," and in its Curve25519 security analysis briefly discusses the non-impact of Weil descent.

Over the years one can see evolution in the security requirements for ECC: for example, Curve25519 explicitly adds a twist-security requirement that most of the NIST/SEC curves don't meet. But adding a requirement of security against 2010/575 would be completely and utterly redundant. Out of of the curves allowed by the previous standards, there are _zero_ curves that can, even theoretically, be subject to the attack in 2010/575.

The paper is simply wrong when it claims that its example curve has "no special features that would rule it out as undesirable from a cryptographic point of view." I've now cited five ECC standards that severely restrict the field size, ruling out this curve (and many more); in at least one of these standards the restriction is very clearly labelled as addressing potential security concerns.

Johnston continues (1) pointing to slides that discuss broad classes of elliptic curves and (2) misrepresenting those slides as absurd claims that all elliptic curves, including the rare curves targeted by 2010/575, are suitable for ECC. I really don't think that real-world ECC users have to worry that their curves are being selected by such confused people.

---D. J. Bernstein
Research Professor, Computer Science, University of Illinois at Chicago

So, let's recap. We've dropped the "wild exaggerations" complaint about the title. We've accepted the fact that these curves occur in your work. And we've dropped the complaint that my work might not be new (by the way, good work; I'm glad you read the paper you blindly cited).

Now we are back once again to the standards complaint. I can make your life much easier. If you want to prevent the elliptic curves in my attack from occurring, just make sure they are of odd order. All of my curves have extra 2-torsion in them. I need this in my double descent. This would be simple enough. In later work, we might get rid of this. But you haven't really focused on my curves. You have this need to diminish my work, and I don't really understand why. And if we start cutting out curves from standards to "prevent attacks," shouldn't we understand why? All of ECC is based on assumptions about security, not proofs.

Why do you think Curve[insert number] is secure? It's easy: you have assumed things. It's a DLP assumption (and CDH, and DDH, and so on). The one who makes the assumptions always has the burden of proof. Papers like mine look at the mathematics behind these assumptions. We find cases where these assumptions might not be ideal. Why is this not "main stream?" Does someone need to break every elliptic curve before an attack is "main stream?" Let's hope it doesn't happen like that. Remember, I am only offering a few new techniques. I'm sure more will come. Isn't it better this way? This is all made perfectly clear in my introduction.

(And finally, about IEEE P1363, you cite the one in 1999, but a year later, there is a 4th draft that has ECC over extensions of prime fields in it. You are not telling the truth when you act as if there is no confusion on this topic in the standards in the last ten years. Let's not unleash the beast here.)

No, there was never any regression in IEEE P1363 on this issue. In particular, the prime-or-power-of-2 requirement was never dropped from the IEEE P1363 curve-generation and curve-verification algorithms.

The alleged confusion in standards is nothing more than Johnston misrepresenting general elliptic-curve discussions as elliptic-curve-suitable-for-ECC discussions. Johnston persists in saying, e.g., that P1363 "has ECC over extensions of prime fields" in it, and trying to mislead the reader into believing that P1363 blindly allows all elliptic curves over extensions of prime fields; in fact, P1363 does _not_ allow most such extensions, and does _not_ allow most curves over such extensions.

Imagine someone misled by Johnston into believing that the ECC standards tolerate generating a uniform random (q,E) with q an arbitrary prime power between, say, 2^255 and 2^256, and E an arbitrary elliptic curve over F_q (up to isomorphism). This E will be quite likely to be broken by Pohlig-Hellman, and would have to be astonishingly unlucky to be broken by 2010/575 or any other Weil-descent attack. There are, asymptotically, about x^2/log x choices of E with q<=x, and only about x^2/(log x)^2 of those have prime or near-prime order. For comparison, Johnston has constructed only about x^(1/2)/log x "bad" choices of E (far fewer than previous Weil-descent papers), and even in his wildest dreams can't go beyond about x/log x, never mind the question of whether the "bad" features actually lead to smaller attack costs for cryptographically interesting values of q (something asserted by Johnston without justification and without mention of the much more thorough analyses in the literature).

A better title for this paper would be "A discrete logarithm attack on some rare elliptic curves that were already prohibited by all ECC standards." Of course, the title isn't the only wildly exaggerated part of the paper. Fixing the paper really requires the author to (1) spend time really reading the prior work, rather than just Google-surfing it, and (2) be honest about the relationship of this paper to the prior work.

---D. J. Bernstein
Research Professor, Computer Science, University of Illinois at Chicago

Dan, do you really think the issue here is about "isomorphisms" of elliptic curves? A first year student knows this isn't the case. Isomorphism needs to be isogeny. Do you understand elliptic curve theory at all? I don't want to hurt you with this, I just want the debate to be fair. We could discuss this over email if you want. I want to help you. However, you can't take the wrong distribution and attack me with it on a public forum. This just isn't the right thing to do.

This misconception has cost us hours. It's time to stop. I have already emailed you, so you know how to contact me. I can even stop by in Eindhoven and we can talk. We can then come back and post what we find.

As I said: Choosing a prime power q<=x and an elliptic curve E over F_q up to isomorphism produces about x^2/log x choices of curves. Only about x^2/(log x)^2 of those curves have prime or near-prime group order. Johnston is fundamentally limited to a vastly smaller set of about x/log x curves (all of which were already prohibited by the ECC standards), and within those has actually written down only about x^(1/2)/log x "bad" curves, far fewer than previous Weil-descent papers.

I have no idea which statement Johnston thinks he's disputing, and I have no idea why he claims that this perfectly clear (q,E) distribution is "wrong." Of course, it's not the distribution used in elliptic-curve cryptography, but that's exactly my point: ECC does _not_ allow general curves E over general finite fields F_q. In particular, the ECC standards prohibit curves with far-from-prime group order, curves vulnerable to Weil descent (contrary to Johnston's claims), et al.

As for isogenies versus isomorphisms: One can, of course, ignore cryptographic reality and count isogeny classes instead of isomorphism classes. There are about x^(3/2)/(log x)^2 isogeny classes that have prime or near-prime group order, and Johnston is fundamentally limited to a vastly smaller set of about x^(1/2)/(log x) isogeny classes.

There are two reasons that counting isogeny classes is ignoring cryptographic reality. First, applications that generate "random" elliptic curves normally do it by generating uniform random Weierstrass coefficients a4,a6, or something very similar. (See, e.g., FIPS 186-3.) This is almost identical to generating a uniform random isomorphism class, and quite far from generating a uniform random isogeny class. Probabilities that are concentrated near the ends of the Hasse interval are then quite horribly misrepresented by isogeny-class statistics. I'm not saying that there's a big change for Weil descent; I'm just saying that the isogeny-class question is asking about a quite different distribution from the distribution actually used in the applications.

The second reason is more important, and does have an effect on Weil descent: counting isogeny classes obviously can't see the difference between a "bad" curve and other curves in the same isogeny class. The standards prohibit entire isogeny classes (and fields), but this doesn't mean that security is an isogeny invariant. There are some well-known examples of curves E where we know fast ECDL algorithms for E (by Weil descent) but we _don't_ know fast ECDL algorithms for most isogenous curves.

One might naively think that the _existence_ of fast isogenies (in most cases; see [arxiv.org] for proofs in the typical case, and [eprint.iacr.org] to understand the exceptional cases) implies that ECDL difficulty is an isogeny invariant. This logic is erroneous, because it ignores effectivity; it's just like leaping from the trivial _existence_ of collisions in SHA-512 to the completely unjustified claim that collisions in SHA-512 are easy to find.

---D. J. Bernstein
Research Professor, Computer Science, University of Illinois at Chicago

We could have done this over email.

"Only about x^2/(log(x))^2 of those curves have prime or near prime order." --djb

This is wrong, and everything concluded from it is also wrong. The mistake here is the assumption that isomorphism classes of elliptic curves somehow carry over nicely to the distribution of their orders. This is not true. It is not uniform. Many non-isomorphic elliptic curves have the same order, and the number of isomorphism classes of elliptic curves with the same order varies widely (see the references in my paper about this). This problem isn't solved by a basic appeal to the prime number theorem. This is such a basic mistake I don't know what else I can write. This has been studied for over 100 years.

"I'm just saying that the isogeny-class question is asking about a quite different distribution from the distribution actually used in applications." --djb

The order of an elliptic curve is its isogeny class. To find "prime" or "near-prime order" groups, one is necessarily talking about an isogeny problem. This is embarrassing.

"One might naively think that the _existence_ of fast isogenies (...) implies that ECDL difficulty is an isogeny invariant." --djb

I'm going to explain this problem for every one. Two RSA groups do not have to worry about (interesting) homomorphisms between them. This also isn't a big issue for finite field multiplicative groups. But for elliptic curves, this is a huge issue. Two elliptic curves can have "fast" (i.e., efficient) morphisms between them that carry over much of the group structure for DLPs. The literature on this only defeats the quoted argument. These maps are extremely important, and it's the first thing one learns about when studying elliptic curves.

This discussion needs to go to email, Dan.



Edited 1 time(s). Last edit at 29-Nov-2010 16:42 by johnston.

Here's an illustrative example. An application generates a uniform random integer a_6 modulo a large prime p. What's the chance that the curve y^2=x^3-3x+a_6 is a "maximal" elliptic curve over F_p, i.e., is an elliptic curve with p+1+floor(2 sqrt p) points?

One might naively think that, since the order of an elliptic curve is determined by its isogeny class, one should answer this question by counting isogeny classes. There are about 4 sqrt p isogeny classes of elliptic curves over F_p; exactly one of those classes consists of the "maximal" elliptic curves; so one might guess that the answer is about 1/(4 sqrt p), on the scale of p^(-1/2).

But this guess turns out to be horribly inaccurate. The correct answer is vastly smaller: typically on the scale of p^(-3/4), and sometimes on the scale of p^(-1), depending on p. The underlying source of this error is that y^2=x^3-3x+a_6 is very, very, very far from being uniformly distributed across isogeny classes.

The easiest way to see the correct scale is to apply Deuring's formula (using Kronecker class numbers) for the number of isomorphism classes of elliptic curves having a particular order. The curve y^2=x^3-3x+a_6 isn't uniformly distributed across isomorphism classes, but it's within a small constant factor of being uniformly distributed.

Students interested in learning more about these phenomena should see, e.g., the famous 1987 Annals paper "Factoring integers with elliptic curves" by Hendrik W. Lenstra, Jr. One might think that the success of a curve in ECM at finding a prime p is determined by the number of points on the curve over F_p (this is certainly much closer to being true for ECM than for Weil descent), and that one can therefore simply count isogeny classes. However, the curve in ECM is not even close to being uniformly distributed across isogeny classes, so counting isogeny classes is not answering the right question. That's why Lenstra is careful to count isomorphism classes. (Presumably Johnston will now claim that Lenstra is embarrassing himself.)

Pure mathematicians without algorithmic experience might think that counting isogeny classes is just as natural as counting isomorphism classes. Why do applied mathematicians always seem to pose isomorphism-class questions? Why don't applications such as ECM and ECC generate uniform random isogeny classes? The answer is that generating a uniform or near-uniform isomorphism class is algorithmically much more efficient than generating a uniform random isogeny class.

Anyway, I think this is getting a bit far from the original topic, namely the fact that all ECC standards for the past ten years have excluded the kinds of curves that 2010/575 is targeting. I'm not going to bother following up to whatever additional nonsense Johnston posts at this point. Anyone else who has questions about the inapplicability of 2010/575 is welcome to post those questions here.

---D. J. Bernstein
Research Professor, Computer Science, University of Illinois at Chicago

Here we go again.

The problem here is not science. It's rhetoric. Here we have someone who is entirely confined to a premise that certain problems are difficult (e.g. DLP, CDH, DDH). This person doesn't like my paper.

So, this guy comes to this forum and starts the slime machine. When he feels the need to "prove" himself, he writes things like

"Only about x^2/(log(x))^2 of those curves have prime or near prime order." --djb

This shows that he doesn't know what he is doing. He then waits a few days, realizes he's dead wrong, and comes back with a new distribution problem about elliptic curves defined in a factoring algorithm. A little off topic, don't you think?

This is not a "pure-mathematics" versus "computer science" debate. A security expert needs to get the facts straight. Making them up and then using them in a security analysis is a bit scary. It begs for early retirement.

If anything good comes from this thread, it might be to attract attention to these distribution problems. Some of the most interesting problems in all of mathematics begin here.