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
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.
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.
The most widely used assymetric system is RSA, which is indeed based on factoring (or calculating the Euler Phi function - it amounts to the same thing).
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.
Craft Beer Programming T-shirts
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.
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
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
That was ECCp-109.
c _s olution
This is ECC2-109.
Read the entire challenge list at
http://www.certicom.com/index.php?action=res,ec