Slashdot Mirror
Probable Solution Found for ECC2-109 Challenge
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."
Yea
Yeah, this article is definitely a bit confusing, but it is still interesting. I'd like to hear what someone who participated has to say about it.
Wireless News www.DailyWireless
...most widely-used asymmetric cryptosystems these days are based on the hardness of factorising large numbers as opposed to finding the factors of elliptic curves. So...what purpose does this serve? Or does it just act as a useful benchmark?
I understand finding a collision (two things that when crypted yield the same result) is considered a goldmine in breaking an encryption algorithm.
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.
I can count to 1023 on my hands. Ask me about #132.
Finding a collision breaks the HASH function associated with the elliptic curve.
--
AC
Basically it's a cryptographic method that allows the same or nearly the same level of security as a regular public-key encryption scheme(based on factoring large numbers) but makes it computationally cheaper to encrypt the data. 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. This is of course extremely important for, let's say mobile devices with limited processing power.
I was hoping for an explanation. Simply stating that it breaks the HASHing doesn't explain anything. You're just saying the same thing again.
Anyone else know?
I can count to 1023 on my hands. Ask me about #132.
are they something like md5 hashes, or a kind of asymetric encryption?
Only morons moderate based on a sig.
If you put enough computers on the problem, you will eventually find a solution by random chance. (correct me if I'm wrong.)
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...'"
How does it feel to be an unpaid servant of Certicom's marketting department?
I'm not an expert, but this is my basic understanding. ECC is a public key encryption algorithm. The challenge was to find the private keys using a list of public keys and a set of system rules. If two computers find keys (DP points) that are the same, then theoretically, the encryption has been cracked, i.e. the private key has been found. It's a brute force method. This shows, however, that it is very hard to crack the encryption and would be generally useless, since by the time you cracked the encryption, whatever you were trying to read is probably not relevant anymore. However, with a fast enough computer or group of computers, it could be useful.
Don't get off the boat. Absolutely, goddamn right.
Now get on the ball and crack this already.
-JD
... I can probably answer this myself but I'd rather get some credible experts opinions... failing that, slashdot is right handy....
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) to ID now and discard,leaving the one true path, or is this whack?
It gives something to stand on basically. Context can then be taken into account. Most good crypto systems were broken socially, with a person of importance being mentioned and then their name being run through the encrpted messages, or with a i/o machine being captured (ie: enigma in WW2).
The `collision' mentioned here is related to the particular algorithm being used to break ECC, which is called Pollard rho for discrete logarithms.
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. It has to do with the theory of random functions.
Join the NFSNET. Our prime goal is making little numbers out of big ones. http://www.nfsnet.org/
This write-up from the website linked in the article is fairly 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.
The only reason all cover-ups appear to fail is that you never hear about the ones that succeed.
Say you take a hash or sum of the latest Fedora ISOs, and it comes out to some value x. If I make an equal-length file that has the same sum x, but is not Fedora, I can crack the Fedora servers, wreak havoc everywhere, and replace the ISOs. If the Fedora people have trouble fixing my other damage, they may be too busy to notice that the ISOs are different, even though they're the same size and sum.
Now, suppose I make/find a file that not only collides with the ISOs, but also does largely what the ISOs did (to bypass the obvious "wait, this isn't a disk image" test) and contains a nice Trojan horse....
If only I knew what the f*** they were talking about...
MY SECRET DIARIES
Basically it's a cryptographic method that allows the same or nearly the same level of security as a regular public-key encryption scheme(based on factoring large numbers) but makes it computationally cheaper to encrypt the data.
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 of points of an elliptic curve over a finite field. 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
Craft Beer Programming T-shirts
Mod parent up, great techical explanation. I should've been more clear in mentioning that the factoring is used in the brute force _breaking_ of the encryption (in RSA for ex.) by factoring the mod portion of the pub key. It looks like I meant that it's used in the actual encryption. My mistake :)
According to the link, ECC=109 was solved a long time ago!
bring out the 110 foot pole!
"She's a scientist and a lesbian. She's not going to let it slide." Orphan Black
Not fast enough. Considering the current distributed.net challange, RC5-72 has several hundred YEARS to complete (yes, years, to reach 100%,) it wouldn't be much different.
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)
I guess we have a bunch of potential recruits for the MD5CRK project (mentioned here), no?
...K-mart had a run on underwear as geeks everywhere had to replace their semen-stained sweatliners.
It seems that a better use of spare CPU cycles would be distributed.net's Optimal Golomb Ruler search, or Stanford University's Folding @ Home project.
Make an actual contribution to science - much more satisfying than looking for a very improbable E.T. or senselessly cracking encryption schemes.
The purpose of all these challenges is to understand how much computing power is necessary to break encryption or signature schemes. EC109 strength is pretty low, but offer a way-point on the curve. Distinguished points are not really distinguished. They just have an easy search pattern such as a number of trailing zeroes or other constant values. These are searched ad-infinitum and when two matches are found, a little math can get you a private key. The death nell for the DES algorithm was heard when distributed.net, in cooperation with the Electronic Freedom Foundation built a machine that could crack it in 27 days (or so). And the cost made you wonder who might want to build such machines. As a result, we have AES and expanding public key lengths. No-one would really use ECC 109 for current cryptographic systems. The results from this test confirms that. The real question is what is the appropriate key length for a The amount of money (n computers over t time) tells us what sort of advisaries these techniques are useful against. It also
I am too dumb to say anything further on the subject.
Even those who arrange and design shrubberies are under considerable economic stress at this period in history.
i am a little fuzzy on this--does this yeild the session key (and decrypt only this session) or will it yeild the private keys? (and allow decryption of all further communications?)
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 almost guarentee you that the govt has very specialized decryping hardware which would OWN the fastest of 'general use' cpu's on the market today.
Troll, Troll, go away and flame again some other day
Actually that said a lot to me...
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.
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 subexponential-time. This makes a big difference in key lengths when you get down to implementations.
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 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 solving the DLP over a finite group, elliptic curve groups offer the most robust class of groups. Given new techniques to attack the problem, yes, that could esily be reversed.
Perhaps I should have been more specific and said that it maximises the difficulty of current techniques.
Apologies for confusion.
Jedidiah.
Craft Beer Programming T-shirts
DLP over elliptic curves is easy, but still hard over the integers mod primes.
To my knowledge, if (algorithm solving) DLP is "easy" over elliptic curves then the same algorithm can be (modified to be) used for integers "easily".
From one of the links above I got to:
y ,p ress_archive&view=121
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?
Okay, so why does the linked webpage indicate that the 109 challenge was Completed in November of 2002?
To my knowledge, if (algorithm solving) DLP is "easy" over elliptic curves then the same algorithm can be (modified to be) used for integers "easily".
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.
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
two things that when crypted yield the same result
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.
Do you care about the security of your wireless mouse?
Nice story, but not true. According to Coppersmith, the DES design team discovered differential cryptanalysis during the design process of DES, and defended against it in the design of the S-boxes. They called it the T-attack, for "tickle". The NSA said they'd discovered some of their darker secrets, and asked them to keep quiet about it. The result was that everyone could see there was structure in the S-boxes, but no-one knew why, until Biham and Shamir re-invented DC in the late eighties and broke just about everything in use.
Coppersmith has always maintained that the NSA did not dictate a single wire of DES.
Xenu loves you!
Read Paul van Oorschot and Michael Wiener, "Parallel Collision Search with Cryptanalytic Applications". I suspect most Slashdotters would be able to get the gist of it...
Xenu loves you!
the monkeys give you Slashdot.
Can I get a bananna now?
--Rob
(Sorry to reply to my own post...)
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.
can someone explain this without all the numbers with funny symbols, and possibly small words. I mean, sure, I read 'Cryptonomicon', but I admit I skimmed the theory sections....
Don't take it personally, I 'm like this all the time.
...do not take cryptology advice on Slashdot. That goes for the rest of this post, too.
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 no assumptions about the number of factors. If you find one factor, simply do the primality test on the reminder.
Kjella
Live today, because you never know what tomorrow brings
But it's
D(E(m,key),key)
Two messages can collide provided they use different keys.
"Who is the Journal of Quantum Physics going to believe?" --Stephen Hawking
Two messages can collide provided they use different keys.
Yes, that is correct. It shouldn't happen too often though, as that would be a sign of a weakness.
Do you care about the security of your wireless mouse?