On Mon, Sep 30, 2013 at 06:35:24PM -0400, John Kelsey wrote:
Having read the mail you linked to, it doesn't say the curves weren't
generated according to the claimed procedure. Instead, it repeats Dan
Bernstein's comment that the seed looks random, and that this would have
allowed NSA to generate lots of curves till they found a bad one.
That is itself a problem, the curves are in fact, not fully veriably fairly
chosen. Our current inability to design a plausible mechanism by which this
could have been done is not proof that it was not done. Also bear in mind
unlike the NSA the crypto community has focused more on good faith (how to
make thing secure) and less on bad faith (how to make things trapdoor
insecure while providing somewhat plausible evidence that no sabotage took
place). Ie we didnt spend as much effort examining that problem. Now that
we have a reason to examine it, maybe such methods can be found.
Kleptography is a for the open community a less explored field of study.
Conversely it would have been easy to prove that the curve parameters WERE
fairly chosen as Greg Maxwell described his surprise that the seed was big
and random looking:
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.
So the question is rather why on earth if they claim good faith, did they
not do that? Another plausible explanation that Greg mentions also, is that
perhaps it was more about protecting the then secrecy of knowledge. eg weak
curves and avoiding them without admitting the rules for which curves the
knew were weak.
Clearly its easier to weaken a system in symmetric way that depends only on
analysis (ie when someone else figures out the class of weak curves they
gain the advantage also, if its public then everyone suffers), vs a true
trapdoor weakening, as in the EC DRBG fiasco.
So if that is their excuse, that the utility of NSA input one can get due to
institutional mentality of secrecy, is hardening but with undisclosed
rationale, I think we'd sooner forgoe their input and have fully open
verifiable reasoning. Eg maybe they could still prove good faith if they
chose to disclose their logic (which may now be public information anyway)
and the actual seed and the algorithm that rejected all iterations below the
used value. However that depends on the real algorithm - maybe there is no
way to prove it, if the real seed was itself random.
But I do think it is a very interesting and pressing research question as to
whether there are ways to plausibly deniably symmetrically weaken or even
trapdoor weaken DL curve parameters, when the seeds are allowed to look
random as the DSA FIPS 186-3 ones do.
Adam
_______________________________________________
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography
