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

[John Kelsey]

On Oct 1, 2013, at 12:51 PM, Adam Back <adam at cypherspace.org> wrote:

[Discussing how NSA might have generated weak curves via trying many choices till they hit a weak-curve class that only they knew how to solve.]
...
> 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.

This general idea is a nice one.  It's basically a way of using Merkle's puzzles to build a private key into a cryptosystem.  But I think in general, you are going to have to do work equal to the security level of the thing you're trying to backdoor.  You have to break it once at its full security level, and then you get to amortize that break forever.  (Isn't there something like this you can do for discrete logs in general, though?)  

Consider Dual EC DRBG.  You need a P, Q such that you know x that solves xP = Q, over (say) P-224.  So, you arbitrarily choose G = a generator for the group, and a scalar z, and then compute for

 j = 1 to 2^{112}:
	T[j] = jz G

Now, you have 2^{112} values in a group of 2^{224} values, right?  So with about another 2^{113} work, you can hit one of those with two arbitrary seeds, and you'll know the relationship between them.  

But this takes a total of about 2^{113} work, so it's above the claimed secuity level of P-224.  I suspect this would be more useful for something at the 80 bit security level--a really resourceful attacker could probably do a 2^{80} search.  

> Adam

--John