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

2013-10-02 Thread John Kelsey

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


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

2013-10-01 Thread Adam Back

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
___
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)

2013-10-01 Thread Tony Arcieri
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)

2013-10-01 Thread 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]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)

2013-10-01 Thread Tony Arcieri
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)

2013-10-01 Thread Bill Frantz

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


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

2013-10-01 Thread Tony Arcieri
On Tue, Oct 1, 2013 at 12:00 PM, Jeffrey Goldberg jeff...@goldmark.orgwrote:

 If the NSA had the capability to pick weak curves while covering their
 tracks in such a way, why wouldn’t they have pulled the same trick with
 Dual_EC_DRBG?


tinfoilhatThey wanted us to think they were incompetent, so we would
expect that Dual_EC_DRBG was their failed attempt to tamper with a
cryptographic standard, and so we would overlook the more sinister and
subtle attempts to tamper with the NIST curves/tinfoilhat

-- 
Tony Arcieri
___
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography