Quote from: gmaxwell on September 08, 2013, 02:34:32 AM

Quote from: maaku on September 07, 2013, 10:09:33 PM

EDIT: gmaxwell, was the algorithm for parameter selection published? If so, I must have missed this.

Not for the "Koblitz" (in quotes because normally Koblitz refers to curves over a field of characteristic 2 and not a prime field) curves but for the random ones which almost everyone else uses.

Thats why I think the claim is kind of odd, virtually all EC usage on the internet uses the prime random ones (like P-256r) which have their selection scheme published as part of the SEC document.

So I went and looked at the actual seeds because I wanted to see if I could perhaps reproduce the secp256k1 curve through low entropy methods...

And I realize that while the P-NNNr curves do use a deterministic value their provided seeds are completely fucking implausible.

E.g. the seed for P-256r is c49d360886e704936a6678e1139d26b7819f7e90. They procedure generates random data by feeding the seed into SHA1. There is no reason I could tell that the seed wouldn't have been something like "15" (and all lower values would have failed the test).

Secg says about these curves:

Quote

Verifiably random parameters offer some additional conservative features. These parameters are chosen
from a seed using SHA-1 as specified in ANSI X9.62 [1]. This process 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.

But that a great big fucking lie, since a special purpose attack only has to applicable to randomly selected curves more often than you can iterate sha1 for you to be able to slip one into one of these "verifiable random" curves. Maybe they used this freedom to apply additional tests and make them stronger... Maybe?

SECG adds another tidbit:

Quote

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.

I would note that if you read "verifiable random" as "backdoored as all fuck" the fact that only verifiable random are provided for export strength (<=128 bit), and perhaps thats some suggestion that the Koblitz curves are not "backdoored as all fuck". Though thats really handwavy speculation... and it could just be that they didn't care about the performance of the export grade ones. (Or... made the export grade ones weak and the others stronger?!)