Hacker News new | past | comments | ask | show | jobs | submit login

It's not simply that they were designed to be secure - they utilised mathematically justifiable constants.

See https://en.wikipedia.org/wiki/Nothing-up-my-sleeve_number.

There's actually a counter example on that Wiki page - the highly complex numbers used in the NIST curves, for which no path to derivation was publicly provided.




DJB himself gave a talk about "nothing up my sleeve" curves, which can still have a backdoor. The limitation section on the page you linked to says it best:

Bernstein, et al., demonstrate that use of nothing-up-my-sleeve numbers as the starting point in a complex procedure for generating cryptographic objects, such as elliptic curves, may not be sufficient to prevent insertion of back doors. If there are enough adjustable elements in the object selection procedure, the universe of possible design choices and of apparently simple constants can be large enough so that a search of the possibilities allows construction of an object with desired backdoor properties.


> There's actually a counter example on that Wiki page - the highly complex numbers used in the NIST curves, for which no path to derivation was publicly provided.

It's both. The security of curves are evaluated according a set of criteria:

1. Whether the cost for attackers by the Rho Method is above 2^100? (security margin against known attack)

   - NIST P-Curves: Yes.

   - Curve25519/448: Yes.
2. Whether the curve has resistance against additive and multiplicative transfer to avoid potential attacks via index calculus? (security margin against known attack)

   - NIST P-Curves: Yes.

   - Curve25519/448: Yes.
3. Whether the absolute value of this complex-multiplication field discriminant D of the curve is larger than 2^100 to avoid attackers from benefiting from possible speedups to the Rho Method? (security margin against known attack)

   - NIST P-Curves: Yes.

   - Curve25519/448: Yes.
Notably,

   - Bitcoin Curve (secp256k1): No.
But it doesn't mean Bitcoin is broken, it just decreases our confidence that it would be still secure if HUGE speedups to the Rho Method are found for a practical attack. But finding it seems unlikely.

4. Whether the coefficients of the curve are justified mathematically? (security criteria against backdoor)

   - NIST P-Curves: No (!)

   - Curve25519/448: Yes.

   - Bitcoin Curve (secp256k1): Okay.
For example, coefficients for NIST P-256 (secp256r1, prime256v1) is generated by hashing random seed:

    c49d3608 86e70493 6a6678e1 139d26b7 819f7e90
Nobody knows what is it. NIST has its own defense: this random seed is only used as the input of SHA-256, since all cryptographers know that SHA-256 is secure, nobody, not even the NSA, can invert SHA-256, the output must be secure. They called it "verifiable randomness". But it's still room of doubts for sophisticated cryptographers, e.g. See this highly-amusing, satirical paper with lots of insight on this issue: How to manipulate curve standards: a white paper for the black hat https://bada55.cr.yp.to/bada55-20150927.pdf

Coefficients for secp256k1 are not fully explained, but nothing fishy and generally looks good.

And keep in mind that when Satoshi Nakamoto was developing Bitcoin, secp256k1 was the best choice among available, well-accepted standard curves from this perspective, obviously, Satoshi must be an experienced hacker and have made a careful decision.

5. Whether the construction of the curve allows "simple" multiplication and addition. (security criteria against implementation pitfalls).

   - NIST P-Curves: No.

   - Curve25519/448: Yes.

   - Bitcoin Curve (secp256k1): No.
Curve25519 utilizes a mathematical technique called Montgomery Ladder, which also allowed the practical implementation of constant-time, side-channel resistance crypto. On the other hand, NIST curves make it difficult.

6. Whether the curve still offers strong security guarantee even if an attacker has "twisted" the curve, e.g. fooling a program to choose a point which is not on the actual curve. (security margin against known attack and implementation pitfalls)

   - NIST P-Curves: Yes.

   - Curve25519/448: Yes.

   - Bitcoin Curve (secp256k1): Yes.
7. Whether the representation of curve points are indistinguishable from uniform random strings. (security usefulness in various protocols)

   - NIST P-Curves: No.

   - Curve25519/448: Yes.

   - Bitcoin Curve (secp256k1): No.
Therefore, we conclude Curve25519/448 is more robust than NIST curves.


I don't know any serious researcher who thinks the P-curves are backdoored (I sort of doubt even Bernstein thinks they are). They date back before fetishized justifications for curve parameters was a norm, and it's not all that surprising to see "drawn from a random seed" as a design rationale. The problem with the P-curves is that (1) it's harder than necessary to implement constant-time arithmetic on them and (2) they require point validation to use safely.

What you've written here is basically a sort of semi-accurate editorialized summary of safecurves. Safecurves is a cool site, but you should let it stand on its own, I guess.


Here's what happened:

I initially posted the parent comment, it's just the introduction of SafeCurves with its original URL, and I cited that Curve25519 has advantages of better treatment of timing side-channels and invalid curves in its design. I never mentioned "backdoor" at all because I thought it was unimportant.

Then user "yarg" replied my comment, said the point of Curve25519 here is that it uses mathematically-justifiable constants. And to me, what the author seems to be implying, is (1) that those security advantages I cited before are not too important, and (2) that the main concern is that NIST curves have "backdoors".

So as a response, I gave a somewhat editorialized summary of SafeCurve's findings for those who didn't want to read the whole thing. "yarg" seems to be interested on the issue of backdoor, so I gave some personal commentary on the concern of backdoors in the coefficients of NIST curves, and the Internet folklore of why Bitcoin used that unusual Koblitz curve.

But what I wanted to communicate was that it wasn't all about the backdoors, so I summarized all the criteria in SafeCurve to make the point. For example I said Curve25519 allowed "simple" multiplication and addition, and it makes constant-time implementation easier than NIST curves.

I think it's fair enough, do you?


I wasn't attempting to negate the worth of any of the known security and efficiency properties, I was simply adding that there's significant value in understanding how the curve came to be.

Something can be provably secure against all known attacks and still be back-doored.

I said "not simply" implying that there are other considerations and not "not" which wold have implied that what you'd stated was unimportant.

As to the justification for my opinion, that was based on Bruce Schneier's comments regarding the numbers - which he made long before the Snowden revelations.

I'm not saying that the numbers are back-doored, but the situation gives a reasonable justification for pause.


I wouldn't look to Bruce Schneier for insight about curves.


As a serious question, why not? Isn't Schneier basically a crypto deity?


No. More of a crypto hack and policy wonk.


Come on, the man's a legend!

Schneier designed Blowfish and was involved in the design of Twofish and Skein. When I was starting out, his book "Applied Cryptography" was both inspirational and informative, and I wouldn't be surprised if it was one of the most successful cryptography books ever written.

Schneier has also beeing blogging about security in general for decades; yes, sometimes he necessarily discusses government policy as a result, but I don't see what is wrong with that, or why that would make him a "hack" or "wonk".


Blowfish isn't good, and it's important never to use it (as a cipher; bcrypt is fine). But that aside: Schneier has had a weird aversion to elliptic curves, has never (that I know of) written anything technical about them, claims to "not trust the math" behind them (whatever that means), and my suspicion is that he simply hasn't studied them in any depth. All I said was: I wouldn't look to Schneier for information about curves.


Both of those are basically famous for being his work. They didn’t fare super well in the competitions they were submitted to. And they were collaborations, regardless.

His books are inspirational and somewhat informative. That means he is a successful author of cryptography books, not a successful cryptographer per se.


Blowfish predates the AES (and I believe he designed this one solo), Twofish was an AES finalist, and more recently Skein was a SHA3 finalist. I'd say his crpyptography credentials check out.

> Come on, the man's a legend!

He’s a self-promoter. A valuable life skill to learn at some point is how to differentiate those who are legendary due to the awesomeness of their own feats, and those who manufacture legend from mediocrity.


That's pretty harsh, given his contribution to the field.

FWIW, I met him briefly at a developer conference in Norway a few years ago, and he actually seemed quite humble.


Note that #7 is not actually true anymore, and actually hasn't been for quite a while.

A paper from Mehdi Tibouchi [1] shows how to represent points on essentially any curve as uniform random bitstrings.

Another paper by Aranha, Fouque, Qian, Tibouchi, and Zapalowicz [2] gives an even more efficient construction for curves over binary fields.

(As an aside, there are really good reasons not to use curves over binary fields. Discrete log has recently been getting easier much faster over GF(2^k) than over GF(p).)

[1] https://ia.cr/2014/043

[2] https://ia.cr/2014/486


The hardness of discrete logs over fields doesn't have much to do with the hardness of elliptic curve discrete logs. At this stage, I don't think we have any evidence that curves over binary fields are less secure than over prime fields, especially for cryptographically relevant curve sizes.

(The situation is different for pairing-friendly elliptic curves, of course, but that's a different kettle of fish).


Thanks for the update!




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: