4 ms·

Okay, I need to eat my words here. I went to review the deterministic procedure because I wanted to see if I could reproduce the SECP256k1 curve we use in Bitc

by nullc 13y ago

Okay, I need to eat my words here. I went to review the deterministic procedure because I wanted to see if I could reproduce the SECP256k1 curve we use in Bitcoin. They don't give a procedure for the Koblitz curves, but they have far less design freedom than the non-koblitz so I thought perhaps I'd stumble into it with the "most obvious" procedure. The deterministic procedure basically computes SHA1 on some seed and uses it to assign the parameters then checks the curve order, etc.. wash rinse repeat. Then I looked at the random seed values for the P-xxxr curves. For example, P-256r's seed is c49d360886e704936a6678e1139d26b7819f7e90. _No_ justification is given for that value. The stated purpose of the "veritably random" procedure "ensures that the parameters cannot be predetermined. The parameters are therefore extremely unlikely to be susceptible to future special-purpose attacks, and no trapdoors can have been placed in the parameters during their generation". Considering the stated purpose I would have expected the seed to be some small value like ... "6F" and for all smaller values to fail the test. Anything else would have suggested that they tested a large number of values, and thus the parameters could embody any undisclosed mathematical characteristic whos rareness is only bounded by how many times they could run sha1 and test. I now personally consider this to be smoking evidence that the parameters are cooked. Maybe they were only cooked in ways that make them stronger? Maybe???? SECG also makes a somewhat curious remark: "The elliptic curve domain parameters over (primes) supplied at each security level typically consist of examples of two different types of parameters — one type being parameters associated with a Koblitz curve and the other type being parameters chosen verifiably at random — although only verifiably random parameters are supplied at export strength and at extremely high strength." The fact that only "verifiably random" are given for export strength would seem to make more sense if you cynically read "verifiably random" as "backdoored to all heck". (though it could be more innocently explained that the performance improvements of Koblitz wasn't so important there, and/or they considered those curves weak enough to not bother with the extra effort required to produce the Koblitz curves).

reirob 13y ago
Thank you very much for going into such detail. But what does it mean for the ECC or RSA methods? Which can be considered as secure? I guess we need more expertise, right?
- nullc 13y ago
  There is no specific reason to believe ECC methods on these standard curves (or other well selected parameters) to be insecure. But at the same time if someone argues that the NSA could have influenced the parameters to create hidden weaknesses predicated on math unknown to the public, that argument can't be denied. It might even be supported on the basis that they could have easily closed off that argument but did not. (OTOH, equally I could argue that the same selection may have been used to make it stronger). As far as RSA goes, their usage involves fewer free parameters... but to get RSA up to the security levels people are demanding today require increasingly large and slow keys. If the crypto is too burdensome it'll get avoided, and thats worse than whatever speculation you might have about NSA weakening of EC systems.
tptacek 13y ago
You consider it smoking evidence of "cooked" parameters that he hashed a random string? This is the technique suggested by all of IEEE-1363 2000, and in every place its suggested, the standard is at pains to suggest that it provides only a degree of assurance; the standard authors go as far as to repeat the exact same text in each location (RSA, DSA, ECC, &c) while customizing the "what could go wrong" part of the paragraph. 1363 predates the NIST curves, for whatever that's worth.
- pfortuny 13y ago
  I am now rather confused in my ignorance... So the parameters (for ECC) were chosen "at random" theoretically (and so here lies the trust inherent to these?). Thanks for the info.
  - nullc 13y ago
    The parameters are derived from the SHA1 of high entropy values of unspecified origin. It means they very very likely couldn't have algebraically produced a single set of specific magic evil values that enabled them to crack the cryptosystem, a true backdoor, since it would have been computationally infeasible to get SHA1 to output the right values. However, they could have tried billions and billions of sha1 seeds looking for parameters which met some unknown to us characteristics which made the parameters stronger or weaker. Their "veritably random" procedure could have easily foreclosed this possibility, as was later done for some different parameter sets, but they did not.
    - pfortuny 13y ago
      I see, thanks for the explanation.
    - tptacek 13y ago
      So that's true, but remember that they're simply employing the process that IEEE 1363 described years earlier. The circumstances are different: IEEE was trying to explain how to generate parameters, and NIST was specifying which parameters to use, but the methodology is the same. It is thus not particularly "telling" that there's an opaque SHA-1 seed. That is to say, it's not a "tell" that they didn't use a simple string (like the digits of pi or something), because that's not the IEEE method. I preemptively agree that we'd have been better off had the seed been transparently generated, too.

by nullc 13y ago

reirob 13y ago

Thank you very much for going into such detail. But what does it mean for the ECC or RSA methods? Which can be considered as secure? I guess we need more expertise, right?

nullc 13y ago
There is no specific reason to believe ECC methods on these standard curves (or other well selected parameters) to be insecure. But at the same time if someone argues that the NSA could have influenced the parameters to create hidden weaknesses predicated on math unknown to the public, that argument can't be denied. It might even be supported on the basis that they could have easily closed off that argument but did not. (OTOH, equally I could argue that the same selection may have been used to make it stronger). As far as RSA goes, their usage involves fewer free parameters... but to get RSA up to the security levels people are demanding today require increasingly large and slow keys. If the crypto is too burdensome it'll get avoided, and thats worse than whatever speculation you might have about NSA weakening of EC systems.

tptacek 13y ago

You consider it smoking evidence of "cooked" parameters that he hashed a random string? This is the technique suggested by all of IEEE-1363 2000, and in every place its suggested, the standard is at pains to suggest that it provides only a degree of assurance; the standard authors go as far as to repeat the exact same text in each location (RSA, DSA, ECC, &c) while customizing the "what could go wrong" part of the paragraph. 1363 predates the NIST curves, for whatever that's worth.

pfortuny 13y ago
I am now rather confused in my ignorance... So the parameters (for ECC) were chosen "at random" theoretically (and so here lies the trust inherent to these?). Thanks for the info.
- nullc 13y ago
  The parameters are derived from the SHA1 of high entropy values of unspecified origin. It means they very very likely couldn't have algebraically produced a single set of specific magic evil values that enabled them to crack the cryptosystem, a true backdoor, since it would have been computationally infeasible to get SHA1 to output the right values. However, they could have tried billions and billions of sha1 seeds looking for parameters which met some unknown to us characteristics which made the parameters stronger or weaker. Their "veritably random" procedure could have easily foreclosed this possibility, as was later done for some different parameter sets, but they did not.
  - pfortuny 13y ago
    I see, thanks for the explanation.
  - tptacek 13y ago
    So that's true, but remember that they're simply employing the process that IEEE 1363 described years earlier. The circumstances are different: IEEE was trying to explain how to generate parameters, and NIST was specifying which parameters to use, but the methodology is the same. It is thus not particularly "telling" that there's an opaque SHA-1 seed. That is to say, it's not a "tell" that they didn't use a simple string (like the digits of pi or something), because that's not the IEEE method. I preemptively agree that we'd have been better off had the seed been transparently generated, too.