[Cryptography] are ECDSA curves provably not cooked? (Re: RSA equivalent key length/strength)

[Adam Back]

On Tue, Oct 01, 2013 at 08:47:49AM -0700, Tony Arcieri wrote:
>   On Tue, Oct 1, 2013 at 3:08 AM, Adam Back <[1]adam at cypherspace.org>
>   wrote:
>
>     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.

>   See slide #28 in this djb deck:
>   If e.g. the NSA knew of an entire class of weak curves, they could
>   perform a brute force search with random looking seeds, continuing
>   until the curve parameters, after the seed is run through SHA1, fall
>   into the class that's known to be weak to them.

Right but weak parameter arguments are very dangerous - the US national
infrastructure they're supposed to be protecting could be weakened when
someone else finds the weakness.  Algorithmic weaknesses cant be hidden with
confidence, how do they know the other countries defense research agencies
arent also sitting on the same weakness even before they found it.  Thats a
strong disincentive.  Though if its a well defined partial weakening they
might go with it - eg historically they explicitly had a go at in public
requiring use of eg "differential cryptography" where some of the key bits
of lotus notes were encrypted to the NSA public key (which I have as a
reverse-engineering trophy here[1]).  Like for examle they dont really want
foreign infrastructure to have more than 80 bits or something close to the
edge of strength and they're willing to tolerate that on US infratructure
also.  Somewhat plausible.

But the more interesting question I was referring to is a trapdoor weakness
with a weak proof of fairness (ie a fairness that looks like the one in FIPS
186-3/ECDSA where we dont know how much grinding if any went into the magic
seed values).  For illustration though not applicable to ECDSA and probably
outright defective eg can they start with some large number of candidate G
values where G=xH (ie knowing the EC discrete log of some value H they pass
off as a random fairly chosen point) and then do a birthday collision
between the selection of G values and diffrent seed values to a PRNG to find
a G value that they have both a discrete log of wrt H and a PRNG seed. 
Bearing in mind they may be willing to throw custom ASIC or FPGA
supercomputer hardware and $1bil budgt at the problem as a one off cost.

Adam

[1] http://www.cypherspace.org/adam/hacks/lotus-nsa-key.html