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.
Finding a collision breaks the HASH function associated with the elliptic curve.
--
AC
Elliptic Curve Cryptography is a much younger branch of mathematics and cryptography than plain old factor-based ciphers like RSA and friends.
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 chose ECC as (one of) the way(s) to go for the future not long ago...
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.
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...'"
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.
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.
having non-prime factors makes the cipher much weaker
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.
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
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% of the time).
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 very well written post, which explains the significance of collisions in ECC. It effectively breaks the system.
Jedidiah.
Craft Beer Programming T-shirts
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.
Okay, so why does the linked webpage indicate that the 109 challenge was Completed in November of 2002?