3 ms·

However, I don't find it funny reading all the "gory" details: In the article, under the subtitle "Step back, what is this about?" is: "The NIST elliptic curv

by acqq 3y ago

However, I don't find it funny reading all the "gory" details: In the article, under the subtitle "Step back, what is this about?" is: "The NIST elliptic curves (P-192, P-224, P-256, P-384, and P-521[1]) were published by NIST in FIPS 186-2 in 2000, and generated “verifiably at random” according to ANSI X9.62 by taking an arbitrary seed, hashing it with SHA-1, and using the output to derive some of the parameters." Note the sentence: “verifiably at random” according to ANSI X9.62. Now, the mentioned ANSI X9.62 describes very formal algorithms of what “verifiably at random” should mean: "If it is desired that an elliptic curve be generated verifiably at random, then select parameters (SEED, a, b) using the technique specified in Annex A.3.3.1" and then goes on to specify an exact algorithm both how the parameters are selected in A.3.3 and then in A.3.4 the verification algorithm: "The technique specified in this section verifies that the defining parameters of an elliptic curve were indeed selected using the method specified in Annex A.3.3" So, if I understand correctly, the authors spent enough energy both to construct the algorithms to generate the constants and make the SEED public as well as the algorithms to later verify the parameters given the publicly known SEED as an input. And to publish all that in ANSI X9.62. If that was the idea of “verifiably at random” according to ANSI X9.62, and if then nobody knows the SEED, then it appears that the very procedure, for which a lot of energy was spent to be developed or described, was just not followed. From which it can be concluded that the "if" condition of the sentence was just not true: "If it is desired that an elliptic curve be generated verifiably at random..." (Not to mention that the algorithms published there clearly aren't "simply SHA1 hashes" in the sense result = SHA1( seed ) but, casually looking, a concatenation of only some bits of output from multiple SHA1 runs over the increments of the seed, which could suggest that nobody who tries any human written string as a seed would ever find a result by expecting a match of a whole constant with an output of a single SHA1 pass? Has anybody calculated how big would be a chunk of bits from a single SHA1 run actually for every of the constants?) Now, I probably miss something here, if it is so, I'd like to know what.

meithecatte 3y ago
The standards claim that the existence of such a (SEED, a, b) tuple is enough to show that there is nothing special about the curve in question. But if one in a billion curves have a special property that only you know about, which would make it easier for you to attack the cryptosystem, you can try a variety of different SEED values until you find a desirable curve.
- acqq 3y ago
  I don't think we can complain that there were retries over different human-readable seeds to make an appearance of "verifiably at random" design if the chosen human-readable seeds just haven't been published at all. And if the argument is that the publishing of human-readable seeds was unnecessary because the retries of the procedure could have been performed until some exploit was possible, why even define and publish these definitions? Was it an error? Or something else?
dfox 3y ago
The procedures in Annex A.3.3.1 and A.3.3.2 do not really specify how you are supposed to come up with the SEED value used in the first step ("Choose an arbitrary bit string SEED"). Note that this value is part of the output that is published. The claim here is that the procedure used for choosing the SEED in the first step involved SHA-1 of some ASCII text with a counter. By the way the construction with incrementing counter (steps 3 respective 4) is horribly inefficient PRNG that expands/shrinks the entropy in the SEED to the size of field element one bit at a time. I suspect that the inefficiency is intentional to make it even more obvious that authors did not try enough SEEDs to be able to specifically select weak one.
- acqq 3y ago
  > The claim here is that the procedure used for choosing the SEED in the first step involved SHA-1 of some ASCII text with a counter. That's the story as much as I see it: there's a constant that doesn't appear to be "arbitrary" enough in a sense that there's a suspicion that it could be too "special" if nobody can recognize it, and nobody can show how that one was generated. And as there's an official procedure to turn something to something "more random" that "something" appears to be still missing. BTW I don't think that the "inefficiency" you see in the steps there changes anything.
  - dfox 3y ago
    The whole point of the procedure as designed is to make how the constant was selected irrelevant to the security of the resulting curve. Also you have to consider the historical context. The procedure was originally designed to generate parameters for cryptosystems that were very much built on the assumption that SHA-1 is secure hash. Any method to choose a weak SEED in a reasonably practical way involves either breaking SHA-1 (collision does not really help, you would need preimage) or the underlying ECC structure having some gaping security issue that only NSA knows about (ie. there being ridiculously many weak curves).
    - acqq 3y ago
      And we come once again back to the start: _because_ there's an explicit algorithm right there in the standard which allows to start from something "not special" like the digits of Pi or even the ASCII strings of the beginning of the Declaration of Independence, why the completely opaque constants instead? Even if it's, as Filippo suggests, because "the counter has to be there because only one in every 192 to 521 hashes is actually good to make a curve out of", if the counter is a known part of the process of such a selection, all these details could still have been "open". At least, that's my understanding why there's still talk about it all, and this bounty: those who don't like the opaque constants argue: why aren't they "open", if really "irrelevant"? Now, if the bounty shows that the constants come from something like SHA-1("Jerry and Alice deserve a raise. 1398") then all this looks a little better, especially if it can be shown that that "1398" was the first integer that "worked" for the selected phrase, according to the publicly known criteria.

by acqq 3y ago

meithecatte 3y ago

The standards claim that the existence of such a (SEED, a, b) tuple is enough to show that there is nothing special about the curve in question. But if one in a billion curves have a special property that only you know about, which would make it easier for you to attack the cryptosystem, you can try a variety of different SEED values until you find a desirable curve.

acqq 3y ago
I don't think we can complain that there were retries over different human-readable seeds to make an appearance of "verifiably at random" design if the chosen human-readable seeds just haven't been published at all. And if the argument is that the publishing of human-readable seeds was unnecessary because the retries of the procedure could have been performed until some exploit was possible, why even define and publish these definitions? Was it an error? Or something else?

dfox 3y ago

The procedures in Annex A.3.3.1 and A.3.3.2 do not really specify how you are supposed to come up with the SEED value used in the first step ("Choose an arbitrary bit string SEED"). Note that this value is part of the output that is published. The claim here is that the procedure used for choosing the SEED in the first step involved SHA-1 of some ASCII text with a counter. By the way the construction with incrementing counter (steps 3 respective 4) is horribly inefficient PRNG that expands/shrinks the entropy in the SEED to the size of field element one bit at a time. I suspect that the inefficiency is intentional to make it even more obvious that authors did not try enough SEEDs to be able to specifically select weak one.

acqq 3y ago
> The claim here is that the procedure used for choosing the SEED in the first step involved SHA-1 of some ASCII text with a counter. That's the story as much as I see it: there's a constant that doesn't appear to be "arbitrary" enough in a sense that there's a suspicion that it could be too "special" if nobody can recognize it, and nobody can show how that one was generated. And as there's an official procedure to turn something to something "more random" that "something" appears to be still missing. BTW I don't think that the "inefficiency" you see in the steps there changes anything.
- dfox 3y ago
  The whole point of the procedure as designed is to make how the constant was selected irrelevant to the security of the resulting curve. Also you have to consider the historical context. The procedure was originally designed to generate parameters for cryptosystems that were very much built on the assumption that SHA-1 is secure hash. Any method to choose a weak SEED in a reasonably practical way involves either breaking SHA-1 (collision does not really help, you would need preimage) or the underlying ECC structure having some gaping security issue that only NSA knows about (ie. there being ridiculously many weak curves).
  - acqq 3y ago
    And we come once again back to the start: _because_ there's an explicit algorithm right there in the standard which allows to start from something "not special" like the digits of Pi or even the ASCII strings of the beginning of the Declaration of Independence, why the completely opaque constants instead? Even if it's, as Filippo suggests, because "the counter has to be there because only one in every 192 to 521 hashes is actually good to make a curve out of", if the counter is a known part of the process of such a selection, all these details could still have been "open". At least, that's my understanding why there's still talk about it all, and this bounty: those who don't like the opaque constants argue: why aren't they "open", if really "irrelevant"? Now, if the bounty shows that the constants come from something like SHA-1("Jerry and Alice deserve a raise. 1398") then all this looks a little better, especially if it can be shown that that "1398" was the first integer that "worked" for the selected phrase, according to the publicly known criteria.