Re: [Cryptography] are ECDSA curves provably not cooked? (Re: RSA equivalent key length/strength)
On Oct 1, 2013, at 12:51 PM, Adam Back a...@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
___
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] are ECDSA curves provably not cooked? (Re: RSA equivalent key length/strength)
On Tue, Oct 1, 2013 at 3:08 AM, Adam Back a...@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: http://cr.yp.to/talks/2013.05.31/slides-dan+tanja-20130531-4x3.pdf Specifically: http://i.imgur.com/C7mg3T4.png 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. -- Tony Arcieri ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] are ECDSA curves provably not cooked? (Re: RSA equivalent key length/strength)
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]a...@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 ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] are ECDSA curves provably not cooked? (Re: RSA equivalent key length/strength)
On Tue, Oct 1, 2013 at 9:51 AM, Adam Back a...@cypherspace.org wrote: 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. As the fallout from the Snowden debacle has shown (with estimates of the damage to US businesses in the tens of billions) the NSA seems to be unconcerned with the blowback potential of doing things that are potentially damaging when discovered. I wouldn't put it past them to intentionally weaken the NIST curves. That said, my gut feeling is they probably didn't. -- Tony Arcieri ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
Re: [Cryptography] are ECDSA curves provably not cooked? (Re: RSA equivalent key length/strength)
On 10/1/13 at 8:47 AM, basc...@gmail.com (Tony Arcieri) wrote: 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. Or NSA could have done what it did with DES and chosen a construct that didn't have that weakness. We just don't know. Cheers - Bill --- Bill Frantz| I don't have high-speed | Periwinkle (408)356-8506 | internet. I have DSL.| 16345 Englewood Ave www.pwpconsult.com | | Los Gatos, CA 95032 ___ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography
