6 ms·

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-slee

by yarg 7y ago

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 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.

segfaultbuserr 7y ago
> 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 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.
- tptacek 7y ago
  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.
  - segfaultbuserr 7y ago
    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?
    - yarg 7y ago
      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.
loup-vaillant 7y ago
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.

by yarg 7y ago

segfaultbuserr 7y ago

> 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 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.

tptacek 7y ago
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.
- segfaultbuserr 7y ago
  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?
  - yarg 7y ago
    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.

loup-vaillant 7y ago

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.