Probable Solution Found for ECC2-109 Challenge 130
kpearson writes "The eCompute ECC2-109 distributed computing project discovered a probable solution to Certicom's
ECC2-109 challenge today. The challenge was to defeat a 109-bit Elliptic Curve Cryptosystem (ECC). Since the eCompute ECC2-109 project began on November 8, 2002, 1,981 volunteers have run the project's software and found almost 40.5 million distinguished points. From those points the project found two which matched and caused a collision, enabling the project to find a solution to the ECC. The solution was submitted to Certicom this morning for verification."
Really hard to understand for someone (Score:5, Interesting)
Yea
Re:Really hard to understand for someone (Score:5, Informative)
Re:Really hard to understand for someone (Score:2, Insightful)
Re:Really hard to understand for someone (Score:3, Insightful)
This ofcourse is nothing to what one can imagine that national agencies have at their disposal. If a gang of internetusers can break a cipher (brute forcing it) using spare cpu-cycles, imagine what a dedicated cluster of highend computers using an algorithm more efficient than bruteforcing it would be.
Re:Really hard to understand for someone (Score:4, Interesting)
However, they most certainly have the resources to create a reduced instruction set processor dedicated to breaking an instance of a popular encryption scheme, and the ability to buy lots of such to build a supercomputer.
Re:Really hard to understand for someone (Score:2)
OTOH governmentstyle ciphercrunching doesn't necessarily have all the information about which cipher and so on that most of these cryptochallenges has.
Re:Really hard to understand for someone (Score:5, Informative)
The NSA is the largest hirer of math majors. The NSA is mostly interested in encryption. A custom computer is not nearly as good as an algorithm breakthrough, though the computer is obviously creatable (or not creatable depending on the requirements). We know the NSA is doing algorithm research, but because they are not talking we don't know what or how much.
Back in the '70s IBM developed DES, and it was proposed that it become the national standard for encryption. In the process the NSA got involved and told IBM to make some changes, IBM did, but didn't understand why. About 10 years latter differential cryptanalysis was developed, and it turns out that the changes the NSA requested made DES much more secure than the original design, just because of resistance to differential cryptanalysis.
Many researchers believe that with recent private interest in cryptography the gap has been closed. However we do not know that. In any case, the NSA know everything universities know, but they do not contribute back.
Re:Really hard to understand for someone (Score:2)
very true about code vs hardware. log(n) is so much faster then n - x (x being some hardware improvement).
yeah if I would guess government is atleast a couple years ahead of civilian technology. Makes since given the resources they have.
Re:Really hard to understand for someone (Score:5, Funny)
Gee and I thought the cell phone companies hired the most math majors.
Seriously, you have to have taken Analytical Calculus I-III, Differential Equations, Geophysical Fluid Dynamics, and be Phd standing in order to understand the rate plans. Think of the guy who must have made them up!
Re:Really hard to understand for someone (Score:1)
Re:Really hard to understand for someone (Score:2)
Even if true, they still hire only a small, small fraction of all math and computer science PhDs.
Worldwide non-NSA talent vastly outweighs NSA talent, I would wager dollars to donuts.
Re:Really hard to understand for someone (Score:2)
Though I doubt the gap between the NSA and other crypto teams is huge, I am positive the difference between the crypto teams and pgp is a joke.
In fact I wouldn't be surprised if they can crack pgp in real time.
Re:Really hard to understand for someone (Score:2)
Yes, it is. First, you radically underestimate the quality of researchers doing crypto in academia -- if you look at the people who were doing top-rate crypto work in graduate school and publishing at the best conferences, virtually all of them have taken academic positions after graduation. Second, a sizable fraction of those researchers are not US citizens. The rest of
Re:Really hard to understand for someone (Score:2)
I'm saying the two crypto teams are at the same level.
And we are quite a bit behind them.
Re:Really hard to understand for someone (Score:2)
If so, I repeat: if you look at the people who were doing top-rate crypto work in graduate school and publishing at the best conferences, virtually all of them have taken academic positions after graduation. When you take a reasonable look at these things, the far-and-away most likely conclusion is that there is vastly more talent doing civilian crypto than classified crypto. The only way to think otherwise is to believe that tons of uber-geniuses are somehow found a
Re:Really hard to understand for someone (Score:1)
We seemed to do a pretty good job of it in WWII, I see no reason to expect things are different now.
Re:Really hard to understand for someone (Score:2)
> We seemed to do a pretty good job of it in WWII, I see no reason to expect things are different now.
If you're referring to the Manhattan project, the government just went out and hired everyone who had ever done any research work in nuclear physics, regardless of how good they were or how much they'd published. Sinc
Re:Really hard to understand for someone (Score:2)
Re:Really hard to understand for someone (Score:1)
At public universities, the government does have a say in what papers get published based on research done at a governmentally funded institution. So, maybe the great theorists submitted their paper for publication and got picked up by the powers that be.
Just kidding.
Re:Really hard to understand for someone (Score:2)
Re:Really hard to understand for someone (Score:2)
That's not what the DES designers say. (Score:2)
Re:Really hard to understand for someone (Score:2)
Naaa... its not as if the government hires some huge number of mathematicians [wikipedia.org] or anyting.
Re:Really hard to understand for someone (Score:3, Insightful)
Re:Really hard to understand for someone (Score:1)
It proves that it is possible with commodity hardware (and a lot of time) to break ciphers that are regarded as pretty strong.
You don't need to have any hardware to prove this. Every cipher in the world can be cracked given enough time
The real queustion is how long would it take if it wouldn't been what cipher and length has been used
Re:Really hard to understand for someone (Score:2)
Re:Really hard to understand for someone (Score:1)
Re:Really hard to understand for someone (Score:2, Interesting)
Reading around it seems that the idea is to prove that the encryption method is good rather than just theoretically sound. Probably makes it easier to sell stuff based on ECC if you can show how hard it is to crack.
Re:Really hard to understand for someone (Score:2)
Wouldn't it just mean that the test program they were using to crack it just didn't happen to exploit any weaknesses that might exist? The uniqueness of the point is one thing but choosing it is another.
Re:Really hard to understand for someone (Score:3, Insightful)
So when someone says "64-bits of security ought to be enough" you can say "no, no it isn't."
Though yeah, if they do more challenges it's just getting futile.
Tom
Re:Really hard to understand for someone (Score:4, Informative)
The real "contribution" of this attack is that these cycle finding attacks are not just theoretical.
Against RC5/DES brute force was used and shown to be effective for small key lengths. Against ECC a new attack was used [and a newer attack will be required to really continue]. Similarly for RSA they wanted to show factoring was possible [e.g. QS, GNFS, etc...]
There is a point where continuing to work is pointless. E.g. RC5-72 is useless. people have learned and use 128-bit symmetric keys now as a "lower boundary". So even if they do break RC5-72 [which is likely to take a shitload of time] we'd already be ahead of the curve.
In the case of ECC-109 [over GF(p)], 163-bit [over GF(2)]] ECC curves are still "recommended" by NIST document [nist.gov].
A 163-bit key provides roughly 80-bits of security which is enough to not be insecure against most modest attacks but I doubt many cryptographers would recommend it with a straight face [personally I draw the line at 256-bit curves].
Point is showing all these theoretical attacks working is important cuz not one attack fits all.
Re:Really hard to understand for someone (Score:3, Informative)
I think the only remaining point of the challenges are just to prove that the ability to legally aquire $10,000 and the point of saying it's been done is enough to motivate people to contribute their processor time to such a project. We should have stats p
Re:Really hard to understand for someone (Score:3, Interesting)
Pet peeve: You can't prove something is always true by providing anecdotal evidence - but you can disprove it.
Anyway, to the main point: you live in a universe with a finite number of particles and a finite TTL (physics majors are welcome to argue if they want). Or let's put it this way: The total amount of resources available to humanity is limited. Given that, there are problem
Re:Really hard to understand for someone (Score:2)
An ECC key size of 106 bits should take 10^4 MIP years to compute, corresponding to a RSA key size of 512 bits.
An ECC key size of 160 bits should take 10^12 MIP years to compute, corresponding to a RSA key size of 1024 bits.
An ECC key size of 211 bits should take 10^20 MIP yea
Re:Really hard to understand for someone (Score:2)
The problem with that logic is that it assume brute force attack -- that a chess program must compute all branches of the game tree or that a cracker mus
Re:Really hard to understand for someone (Score:1)
Against ECC was the pollard-rho cycle finding algorithm. DES/RC5 was brute force and RSA has been a combo of QS and GNFS.
Tom
Re:Really hard to understand for someone (Score:1)
This was application of something that could have just been left alone as a probability.
It's one thing to have it on 'paper', it's another to know it will actually work (or not) as predicted.
What's additionally fascinating is that the post-doc researcher called it "the most difficult elliptic curve discrete algorithm problem ever computed" and now plans to take the 10000 USD prize and give $8K to the Open Software Foundation and a grand each to two i
Re:Really hard to understand for someone (Score:2)
Re:Really hard to understand for someone (Score:1)
Now give me my $10k
Wasn't this already solved in 2002? (Score:1)
http://www.certicom.com/index.php?action=compan
It appears the 109-bit challenge was already solved in November 2002 and one would expect them to be working on the 131-bit challenge now. Am I missing something here?
Impressive buy confusing (Score:1)
If I recall correctly... (Score:1)
Re:If I recall correctly... (Score:4, Informative)
That's probably why it isn't as well known and well deployed as factor-based encryption. The number of implementations is also much smaller.
Be aware however that NSA NSA Turns to commercial software for crypto [slashdot.org] chose ECC as (one of) the way(s) to go for the future not long ago...
Re:If I recall correctly... (Score:1)
Don't you mean, factoring large PRIME [encyclopedia4u.com] numbers?
Re:If I recall correctly... (Score:2)
Re:If I recall correctly... (Score:4, Informative)
Actually, using a non-prime makes your encryption bullet-proof against any check against the domain of all known prime numbers...
Therefore, the much larger domain of near-primes also needs to be considered. Afterall, you can get a known near-prime just by multiplying two known primes by each other, the only factors will be 1, itself, and the two primes by each other. To check all of those, it'll take quite the load of processor time too.
And that leads to a guessing situation as to which subset of the possible numbers to check first. If the "blue team" checks all the prime known numbers in a situation where the "red team" has has selected a near-prime... the near-prime will take longer to solve than had any known prime been selected. If the "blue team" checks the near-primes with the same priority of as the primes while the "red team" has selected a prime number, then the possiblity of the near-primes has lead to a time-costing distraction from the real solution.
Re:If I recall correctly... (Score:2)
Sigh... (Score:2)
It's extremely easy to dermine if a number is prime or composite (as long as it isn't pseudoprime, but that's something completely different from near-prime) using Fermat.
Normally you have n = p*q, p and q prime
If you have n = p*c, c composite, what you really have is n = p*q1*q2(*q3...), which makes each factor a lot smaller.
The odds of finding a prime dividing n is now a *lot* greater. The algorithms typically make n
Re:If I recall correctly... (Score:2)
RSA is in principle very simple. Take two big prime numbers, multiply them together, and you get a bigger number. Finding out what those factors are is *hard*. A brute force check is not possible (relatively speaking: it's possible, but expensive, or requires writing a vir
Re:If I recall correctly... (Score:1, Informative)
-
Orca
Re:If I recall correctly... (Score:5, Informative)
Next on the list is Diffie-Hellman, which just a key exchange algorithm (you can't encrypt with it, it simply allows both parties to communiccate in public to agree on a private session key. RSA is slow enough that this is all RSA gets used for mostly anyway though (agreeing on a symmetric session key). Diffie-Hellman is based on the difficulty of the discrete logarothm problem. That is, given a large prime p, and a numbers x, y find a such that a^x mod p = y.
If you want to do encryption with a Diffie-Hellman liem system, you can, and that system is known as El-Gamal. It works very similarly, and is based on the same problem (Discrete Log Problem).
Elliptic Curve Cryptography is simply Diffie-Hellman or El-Gamal, except that instead of using Z_p as the group in which you do calculations, you use the group formed by the points of an elliptic curve over a given finite field. Mostly that means that multiplication is much more complicated, and the Discrete Log Problem itself becomes much harder (partly due to multiplication being harder, partly due to other properties of the group that it would be tedious and not very illuminating to explain).
The advantage of Elliptic Curve systems is that because the DLP is much harder on the group used (elliptic curve group), you can use a much smaller key size and still have strong encryption. Note that it was only a 109bit key that was cracked after years of effort - compare that to the RSA factoring challenge where much larger key sizes have been cracked.
You have extra benefits in ECC as well - you get to choose the base field, and the curve itself to determine the group, rather than picking a large prime. As the properties of elliptic curve groups can vary dramatically given a change in field or curve this means if you can choose your curve randomly you get even more security (for very few extra bits - elliptic curves are very complicated objects, but simple to describe).
What all of that means is that, while current systems are based on factoring (RSA), that system require slarger keys, is less secure and - given recent developments by Biham, Bernstein and the like - is looking potentially surprisingly crackable even at some of the larger key sizes. That is to say, Elliptic Curve Cryptography is very much the future of Asymmetric Cryptosystems. Being able to break this key size gives a decent benchmark of the security of current systems (which don't use randomly chosen curves yet - there are still issues with that).
That is to say - this is very important, but given the complexity and the effort involved, looks like a good sign for the security of Elliptic Curve Cryptography.
Jedidiah.
Re:If I recall correctly... (Score:1)
That and they're only finding collisions. Collisions are next to useless unless you want somebody to accidentally download a file with seemingly random bits instead of something they wanted. (That's just one example, but collisions are not very useful a good 99.99999999% o
Re:If I recall correctly... (Score:3, Informative)
That would be hash collisions you are thinking of, this is rather different, given the nature of the system. I would direct you to this [slashdot.org] very well written post, which explains the significance of collisions in ECC. It effect
Re:If I recall correctly... (Score:2)
Question for the more cryptically inclined crowd: (Score:5, Interesting)
How does finding a collision help break the encryption? Does anyone know the technicalities of why this allows you to break an encryption algorithm, to me, who has no clue, this seems just like a coincidence and not very useful, but i'd like to be enlightened.
Re:Question for the more cryptically inclined crow (Score:2, Informative)
--
AC
Re:Question for the more cryptically inclined crow (Score:1)
Anyone else know?
Re:Question for the more cryptically inclined crow (Score:5, Informative)
http://www.ecompute.org/ecc2/ecc2-109.pdf
The question of why a collision makes solving the problem easy is answered at the top of page 8.
can they.... (Score:1)
umm, can they do a coordinated analysis of their logs at the moment of capture, then work backwards and determine the sequence of what I will term "lucky breaks" that lead to the capture, allowing them to throw away all the blind leads, so that in future attempts they can cut to the chase quicker? All the non-lucky breaks should be easy (that's the real question I don't know)
Re:Question for the more cryptically inclined crow (Score:1)
Re:Question for the more cryptically inclined crow (Score:5, Informative)
Let's work with the integers modulo a prime p -- the algorithm works just the same with elliptic curves. Say you were told that a^b == c mod p (where == means `is congruent to'). You were also given a, c and p, and you need to figure out b. This is the so-called discrete logarithm problem.
Pollard's rho algorithm solves this problem the following way. Suppose you somehow figure out that a^x c^y == a^w c^z mod p, and of course x != w, y != z (which is the trivial solution). That's the kind of collision they found. Now this yields a solution because, as c == a^b, then a^x c^y == a^x (a^b)^y == a^x a^(by) == a^(x+by), and similarly a^w c^z == a^(w+bz). Thus a^(x+by) == a^(w+bz), so one is left with the very easy task of solving the equation x+by == w+bz modulo the group order, which is p-1 here since we are working with integers modulo p (this is Fermat's Little Theorem). For elliptic curves, it's not so easy (i.e., it may take a couple of hours, maybe days, on a single CPU for a curve of cryptographic interest) to figure out the group order but it's still possible.
And how is that collision found anyway? That's a bit complicated, but I guess it can be found on the Handbook [uwaterloo.ca]. It has to do with the theory of random functions.
Paper on finding collisions (Score:2)
Re:Question for the more cryptically inclined crow (Score:2)
Now, suppose I make/find a file that not only collides with the ISOs, but also does largely what the ISOs did
Re:Question for the more cryptically inclined crow (Score:2)
That can't happen. Would you by any chance be thinking of something else? Possibly a hash rather than an encryption. The fact that you can decrypt proves that the encryption cannot produce collisions. That is for any m we know that D(E(m))=m so if E(m1)=E(m2) then it must be the case that D(E(m1))=D(E(m2)) which is the same as m1=m2.
Re:Question for the more cryptically inclined crow (Score:2)
D(E(m,key),key)
Two messages can collide provided they use different keys.
Re:Question for the more cryptically inclined crow (Score:1)
Yes, that is correct. It shouldn't happen too often though, as that would be a sign of a weakness.
What is Elliptic curve cryptography.... (Score:5, Informative)
Re:What is Elliptic curve cryptography.... (Score:5, Informative)
Re:What is Elliptic curve cryptography... (Score:5, Informative)
Mostly right. ECC is based on the Discrete Log Problem, not factoring. The Discrete Log Problem is basically: given x, y find g such that g^x = y. That's easy for real numbers - you just take a log. The problem becomes rather more difficult in the case where you are working with integers mod some prime - that is, find an integer g, such that g^x mod p = y. That gives you Diffie-Hellman and El-Gamal. ECC is the same problem, but over the group [wolfram.com] of points of an elliptic curve [wolfram.com] over a finite field [wolfram.com]. You can show that this class of groups effectively maximises the difficulty of the Discrete Log Problem, and that's why the key sizes and computational efficiency is so much better.
Jedidiah
Re:What is Elliptic curve cryptography... (Score:2)
Re:What is Elliptic curve cryptography... (Score:2)
Nobody has shown any such thing -- as far an anyone knows, DLP over elliptic curves is easy, but still hard over the integers mod primes.
However, the best *known* algorithms for solving DLP over elliptic curves are exponential-time (this may change, if more is learned about elliptic curves), while in the integers case they are
Re:What is Elliptic curve cryptography... (Score:2)
However, the best *known* algorithms for solving DLP over elliptic curves are exponential-time (this may change, if more is learned about elliptic curves), while in the integers case they are subexponential-time. This makes a big difference in key lengths when you get down to implementations.
Quite true - that's why I said effectively. Given current techniques for solvi
Re:What is Elliptic curve cryptography... (Score:2)
Maybe; I've never seen such a result, but this isn't my area of expertise. You'd need to be able to efficiently map a random generator and element of Z_p^* into a generator and element on the elliptic curve group, such that the elements have the same discrete log with respect to the bases. If there's a way, it's not at all straightforward.
Re:What is Elliptic curve cryptography... (Score:2)
Actually, in Z_p^* it's not even known how to efficiently map an element (y,g) to (z,h) where g and h are random generators and z and y have the same discrete logs with respect to their bases. So I strongly doubt that such a thing could be done between Z_p^* and elliptic curve groups, which have radically different structure.
Re:What is Elliptic curve cryptography... (Score:1)
Actually, that's taking the x'th root of y, not a logarithm. The discrete logarithm problem is:
given g, y find x such that g^x = y
The Diffie Hellman Problem is given g, g^x, g^y, find g^xy. This is generally done by finding the discrete log of g^x or g^y, but I'm not entirely sure whether it's proven if the DLP and DHP are equivalent.. perhaps google may yield answers to that
Re:What is Elliptic curve cryptography.... (Score:2)
So while the bad guys still, theoretically, need nearly the same amounts of processing power and time as regular asymmetric crypto to decrypt the message, the good guys save significantly in encryption.
Unless of course it's the bad guys doing the encryption. Then it will take the good guys more time to decrypt. That evil, evil knowledge! :)
This reminds me of a Bob Newhart sketch (Score:3, Funny)
The sketch goes something like this:
If you put enough monkeys at enough typewriters, they will eventually, by random chance, type all the works of Shakespeare. Unfortunately, this would require an infinite number of people going around checking the monkey typing.
"Bob, Bob, come here, I think we've got something! Yes this is really it! 'To be, or not to be, that is the gzortmanplatz...'"
Re:This reminds me of a Bob Newhart sketch (Score:2, Interesting)
Re:This reminds me of a Bob Newhart sketch (Score:2, Informative)
And while you're waiting on Shakespear... (Score:2)
Can I get a bananna now?
This is my basic understanding (Score:2, Informative)
Re:This is my basic understanding (Score:1)
-Mr. Lizard
oh (Score:2)
-JD
to protect out castle (Score:1)
MD5CRK (Score:1)
I guess we have a bunch of potential recruits for the MD5CRK project [md5crk.com] (mentioned here [slashdot.org]), no?
Waste of cycles (Score:4, Informative)
Make an actual contribution to science - much more satisfying than looking for a very improbable E.T. or senselessly cracking encryption schemes.
Re:Waste of cycles (Score:4, Insightful)
Re:Waste of cycles (Score:3, Insightful)
And isn't it trivial to calculate the probability of a solution being found when using a known alogrithm and expending a certain amount of CPU time?
What is learned?
Some answers, maybe.... (Score:5, Interesting)
Re:Some answers, maybe.... (Score:2)
Actually, it was about 22 hours [eff.org]. Amusingly, the project [eff.org] was called Deep Crack [eff.org].
curves... (Score:3, Funny)
I am too dumb to say anything further on the subject.
interesting (Score:1)
either way..this was only what, 17 months for only 2k people on a 109 bit key?... just think.. each bit doubles a key's strength. and with 64 bit keys still being fairly commonly used, think how fast the govt (NSA) will be (probably, has been) blowing through lower bit (possibly higher bit) crypto communications--and i can almo
Uh... November 2002? (Score:4, Interesting)
Re:Uh... November 2002? (Score:4, Informative)
This is ECC2-109.
Read the entire challenge list at
http://www.certicom.com/index.php?action=res,ec
my brain hurts (Score:1)
Re:Wow, that's fascinating (Score:1)
I bet both of these projects have a similar total amount of CPU power, not to mention this project is a bit cooler. I shut down dnetc and I'm going to run this one for a while, after 700 million iterations, I've found my first DP, yay! (Supposedly, the average is around 1.7 billion)