4 ms·

I'm going to display lots of ignorance in the hope you'll correct me. I thought these "possibly backdoored" curves needed a seed, and the creators provided a "p

I'm going to display lots of ignorance in the hope you'll correct me. I thought these "possibly backdoored" curves needed a seed, and the creators provided a "provably random" one by hashing... a random number they provided. That alone is so silly and I'm not sure how anyone could take it seriously. But then, after that, it was discovered all those "provably random" seeds had a 1-in-a-million weakness. While this weakness alone doesn't comprise everything, it's an indicator that someone intentionally found those seeds so it might indicate something more. Is my poor understanding terribly wrong?

tptacek 12y ago
Yes. The P- curves start from a single random number, and then go through a number of reasonable steps to expand the number into a set of curve parameters. It's not easy, given the steps involved, to see how that random seed could easily be used to select a weak curve, but it's possible. At this point, nobody OK with "possible". The NIST curves suck. But if your choice is between the NIST P- curves and PKCS1v15 RSA, it's not hard to see what the better of the two options is.
- MichaelGG 12y ago
  So the fact that NIST used a "verifiably random" seed that was definitely not random, and later shown to not be rigid isn't a practical cause for concern? Wouldn't it be prudent to assume that these unexplained seeds might have some more advanced attack, assuming the NSA is a decade or two beyond public research?
  - Perseids 12y ago
    The seed itself was never claimed to be verifiably random. Instead, because it uses a (cryptographically secure) pseudo random generator to produce the curve parameters out of a public seed, the curve parameters are said to be "verifiably random". Today, we have more strict requirements on curve rigidity in mind than at the time they released the curves. It's not really fair to claim that NIST acted in malice by not following best practices which only developed after its publication.
    - TheLoneWolfling 12y ago
      Which hash function was used?
      - Perseids 12y ago
        Apparently Sha1: http://csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf http://csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReC... - Appendix 4-7 Which is fine, given that even today Sha1's preimage resistance is not practically broken.
    - MichaelGG 12y ago
      How does hashing prevent anything? It just makes it a bit harder, as you've got to try a bunch of inputs and look for a desired output. Big deal, especially if they have plenty of time before publishing. It's not like it is hard at all to come up with a really truly random seed to use, one that would not allow such speculation.
      - Perseids 12y ago
        If you are looking for one specific output, this bunch of inputs is as large as 2^159 on average before you find the preimage (which is far too large to bruteforce with the meager earthly energy resources). The current fear regarding this curves is that the NSA might know how to break a large fraction of all curves, like every millionth curve. In that case, trying out seeds until you get one of those rare curves is feasible, but a truly random curve would be safe with 99.9999% probability. As we have don't trust anybody to generate these truly random curves, we a stuck with rigidity requirements as our best shot.
- sarciszewski 12y ago
  Would you support an effort to get Ed25519/Curve25519 incorporated into NSS and OpenSSL? :)
  - tptacek 12y ago
    What does that even mean? Are Ed25519 and Curve25519 superior to ECDSA and NIST P-256? Of course. What would it mean to "support" or "not support" it?
    - tedunangst 12y ago
      You have to say "I think OpenSSL should support Ed25519" and then you support it. Until you say the magic words, you don't support it.
      - sarciszewski 12y ago
        That's not at all what I meant by "support".
    - sarciszewski 12y ago
      Support an effort -- Volunteer time/resources to make it happen.
      - tptacek 12y ago
        It's not about the code. You need to get Mozilla and Google to agree to deploy. They aren't dragging their feet; they put an enormous amount of effort into these problems, and employ some of the best in the industry.
        sarciszewski 12y ago
        Okay. I wish there was more visibility on these matters. I'm still, by and large, an outsider to all the going ons of the industry. :)

tptacek 12y ago

Yes. The P- curves start from a single random number, and then go through a number of reasonable steps to expand the number into a set of curve parameters. It's not easy, given the steps involved, to see how that random seed could easily be used to select a weak curve, but it's possible. At this point, nobody OK with "possible". The NIST curves suck. But if your choice is between the NIST P- curves and PKCS1v15 RSA, it's not hard to see what the better of the two options is.

MichaelGG 12y ago
So the fact that NIST used a "verifiably random" seed that was definitely not random, and later shown to not be rigid isn't a practical cause for concern? Wouldn't it be prudent to assume that these unexplained seeds might have some more advanced attack, assuming the NSA is a decade or two beyond public research?
- Perseids 12y ago
  The seed itself was never claimed to be verifiably random. Instead, because it uses a (cryptographically secure) pseudo random generator to produce the curve parameters out of a public seed, the curve parameters are said to be "verifiably random". Today, we have more strict requirements on curve rigidity in mind than at the time they released the curves. It's not really fair to claim that NIST acted in malice by not following best practices which only developed after its publication.
  - TheLoneWolfling 12y ago
    Which hash function was used?
    - Perseids 12y ago
      Apparently Sha1: http://csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf http://csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReC... - Appendix 4-7 Which is fine, given that even today Sha1's preimage resistance is not practically broken.
  - MichaelGG 12y ago
    How does hashing prevent anything? It just makes it a bit harder, as you've got to try a bunch of inputs and look for a desired output. Big deal, especially if they have plenty of time before publishing. It's not like it is hard at all to come up with a really truly random seed to use, one that would not allow such speculation.
    - Perseids 12y ago
      If you are looking for one specific output, this bunch of inputs is as large as 2^159 on average before you find the preimage (which is far too large to bruteforce with the meager earthly energy resources). The current fear regarding this curves is that the NSA might know how to break a large fraction of all curves, like every millionth curve. In that case, trying out seeds until you get one of those rare curves is feasible, but a truly random curve would be safe with 99.9999% probability. As we have don't trust anybody to generate these truly random curves, we a stuck with rigidity requirements as our best shot.
sarciszewski 12y ago
Would you support an effort to get Ed25519/Curve25519 incorporated into NSS and OpenSSL? :)
- tptacek 12y ago
  What does that even mean? Are Ed25519 and Curve25519 superior to ECDSA and NIST P-256? Of course. What would it mean to "support" or "not support" it?
  - tedunangst 12y ago
    You have to say "I think OpenSSL should support Ed25519" and then you support it. Until you say the magic words, you don't support it.
    - sarciszewski 12y ago
      That's not at all what I meant by "support".
  - sarciszewski 12y ago
    Support an effort -- Volunteer time/resources to make it happen.
    - tptacek 12y ago
      It's not about the code. You need to get Mozilla and Google to agree to deploy. They aren't dragging their feet; they put an enormous amount of effort into these problems, and employ some of the best in the industry.
      - sarciszewski 12y ago
        Okay. I wish there was more visibility on these matters. I'm still, by and large, an outsider to all the going ons of the industry. :)