Re: [TLS] Testing consensus for adding curve25519 to the EC named curve registry

[Nick Mathewson <[e-mail]>]

On Mon, Sep 9, 2013 at 9:22 PM, Dan Brown <[e-mail]> wrote:
> I'm the current editor of ANSI X9.62 and X9.63, but joined X9F1 a little later than the time in question, so am not the best historical source.
>
> Anyway, I had thought the 15 NIST curves were included in ANSI X9.63 in 2001, but most were not in X9.62 in its first 1998 version, and only added in the 2005 version.
>
> The curve seed sources were not documented in ANSI or NIST docs. I've wondered about it a few times, but could never see a concrete problem. At least intuitively, it would only be a problem if:
>
> 1) a large fraction of elliptic curves were weak, or
>
> 2) sha1 preimages are easy to find and some unknown but rare class of elliptic curves are weak.
>
> Both of these would undermine more than just the curve choice, and seem extremely unlikely.

That's true, so long as "large fraction" and "rare" are defined
appropriately.  But I think what most of the people who worry about
this are worried about is something like:

3) A small-ish fraction of elliptic curves (say, one in every
quadrillion or quintillion or so) has some as-yet-unknown weakness,
and building a sha1 brute-forcing engine to find seeds that would
produce such curves was economically viable the late 1990s.

After a little time investigating SHA1 speeds on late-1990s FPGAs,
special-purpose chips, and general purpose CPUs, a
back-of-the-envelope calculation suggests that, given about ten
million dollars of hardware and about half a year's worth of
processing time, searching quintillions of seeds to find curves with
desired properties wouldn't have been unrealistic.

Now, none of this means that the seeds in question actually _were_
chosen in any hostile way, of course. But it would make it more
comforting if anybody could point out where the seeds actually came
from.

best wishes,
-- 
Nick Mathewson