4 ms·

Particularly noteworthy is the part near the end regarding the selection process for curves when standards are written, and the caginess of the presenters in an

Particularly noteworthy is the part near the end regarding the selection process for curves when standards are written, and the caginess of the presenters in answering the audience question on the topic. This is a good argument for software authors to really understand for themselves at all levels what is going on with the cryptography/ packages they are using.

tptacek 12y ago
There's a backstory here; the TLS working group asked the IETF crypto review board to recommend a standard for DJB's Curve25519. The effort seems to be running aground on bikeshedding concerns. The jab about NSA continuing to influence CFRG is weird, though. Bernstein doesn't really believe that NSA influences Kenny Paterson.
orbifold 12y ago
This has also bugged me in the case of other cryptographic algorithms, for example SHA-1 has several magic input constants, whose choice is not obvious. When casually reading through the original papers I could not find a clear explanation of how those values were chosen. Pretty much everything in the design seems fairly arbitrary and amendable to variation. In physics there are multiple case where you can do seemingly very hard calculations, if you do it in the wrong coordinate system and neglect symmetries that are present, that collapse to almost nothing (In the case of elliptic curves that was the fact that the curve points chosen by NSA were related by Q = P + e, where e was some point on the curve only known to the NSA)
- tptacek 12y ago
  Regarding the SHA-1 constants: http://crypto.stackexchange.com/questions/10829/why-initialize-sha1-with-specific-buffer http://crypto.stackexchange.com/questions/10829/why-initiali... Your latter example seems to be about the Dual-EC RNG, which is not an ECC encryption algorithm.
  - orbifold 12y ago
    Ah that is good to know. Yes the latter example was not exactly on point, just meant as a general illustration of possible vulnerabilties.
fryguy 12y ago
Based on her response (at 53:40), I feel like she misunderstood the question. The first response "The nice thing about standards is there's so many to choose from" is probably because even if she proposes a curve with a flaw, people could just choose to use Curve25519 or whatever. I feel like they've already addressed the question with their "bada55 curves" page: http://safecurves.cr.yp.to/bada55.html http://safecurves.cr.yp.to/bada55.html
- tptacek 12y ago
  The subtext of BADA55 is that even curves that are seeded from mathematical constants or from other first-principals rationales still provide a malicious curve generator with leeway to pick from many potential curves, and to steer victims to the weakest of them.
  - jeff_marshall 12y ago
    That's true, but if the curve uses a well-studied underlying field where the curves that are vulnerable to cryptanalytic attacks can be avoided (prime fields lead the way here, last time I worked on an ECC implementation ~ 5 years ago), the risk from this threat isn't so great -I'd worry about other aspects of the resulting system first. A quick google search shows DJB and Tanja Lange have some nice analysis of existing curves here: http://safecurves.cr.yp.to/index.html http://safecurves.cr.yp.to/index.html Of course, if the cryptographers generating the curve aren't sharing their knowledge of some new class of weak curves, all bets are off.
  - deleted 12y ago
    [deleted]
  - nullc 12y ago
    BADA55 curves are not "from mathematical constants or from other first-principals rationales", they're a demonstration that the spec "provably random" construction used for some other curves can be ground to produce very rare characteristics. They all have unjustified high entropy random "seeds", like P-256, which were the product of a computationally expensive search to find curves meeting the BADA55 characteristic. An example of a curve "from mathematical constants or from other first-principals rationales" would be to set parameters to 'trivial values' like 0 or 2^255 and increment until you get the first curve that matches a security test. Some curves, like the curve25519 curve or secp256k1 were constructed this way and this method could not be "BADA55" in the way that P-256 could be.

tptacek 12y ago

There's a backstory here; the TLS working group asked the IETF crypto review board to recommend a standard for DJB's Curve25519. The effort seems to be running aground on bikeshedding concerns. The jab about NSA continuing to influence CFRG is weird, though. Bernstein doesn't really believe that NSA influences Kenny Paterson.

orbifold 12y ago

This has also bugged me in the case of other cryptographic algorithms, for example SHA-1 has several magic input constants, whose choice is not obvious. When casually reading through the original papers I could not find a clear explanation of how those values were chosen. Pretty much everything in the design seems fairly arbitrary and amendable to variation. In physics there are multiple case where you can do seemingly very hard calculations, if you do it in the wrong coordinate system and neglect symmetries that are present, that collapse to almost nothing (In the case of elliptic curves that was the fact that the curve points chosen by NSA were related by Q = P + e, where e was some point on the curve only known to the NSA)

tptacek 12y ago
Regarding the SHA-1 constants: http://crypto.stackexchange.com/questions/10829/why-initialize-sha1-with-specific-buffer http://crypto.stackexchange.com/questions/10829/why-initiali... Your latter example seems to be about the Dual-EC RNG, which is not an ECC encryption algorithm.
- orbifold 12y ago
  Ah that is good to know. Yes the latter example was not exactly on point, just meant as a general illustration of possible vulnerabilties.

fryguy 12y ago

Based on her response (at 53:40), I feel like she misunderstood the question. The first response "The nice thing about standards is there's so many to choose from" is probably because even if she proposes a curve with a flaw, people could just choose to use Curve25519 or whatever. I feel like they've already addressed the question with their "bada55 curves" page: http://safecurves.cr.yp.to/bada55.html http://safecurves.cr.yp.to/bada55.html

tptacek 12y ago
The subtext of BADA55 is that even curves that are seeded from mathematical constants or from other first-principals rationales still provide a malicious curve generator with leeway to pick from many potential curves, and to steer victims to the weakest of them.
- jeff_marshall 12y ago
  That's true, but if the curve uses a well-studied underlying field where the curves that are vulnerable to cryptanalytic attacks can be avoided (prime fields lead the way here, last time I worked on an ECC implementation ~ 5 years ago), the risk from this threat isn't so great -I'd worry about other aspects of the resulting system first. A quick google search shows DJB and Tanja Lange have some nice analysis of existing curves here: http://safecurves.cr.yp.to/index.html http://safecurves.cr.yp.to/index.html Of course, if the cryptographers generating the curve aren't sharing their knowledge of some new class of weak curves, all bets are off.
- deleted 12y ago
  [deleted]
- nullc 12y ago
  BADA55 curves are not "from mathematical constants or from other first-principals rationales", they're a demonstration that the spec "provably random" construction used for some other curves can be ground to produce very rare characteristics. They all have unjustified high entropy random "seeds", like P-256, which were the product of a computationally expensive search to find curves meeting the BADA55 characteristic. An example of a curve "from mathematical constants or from other first-principals rationales" would be to set parameters to 'trivial values' like 0 or 2^255 and increment until you get the first curve that matches a security test. Some curves, like the curve25519 curve or secp256k1 were constructed this way and this method could not be "BADA55" in the way that P-256 could be.