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."
Price money. About $10,000 I believe.
vampirical
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...
It seems that you're referring to the RSA crypto system. If so, you should realise that using RSA for extended lengths of communication is almost prohibitively (computationally) expensive. Elliptic curve crypto systems, on the other hard, have much lower computational costs. Moreover, experts believe that they provide at least as much security, if not more, as the RSA scheme. This is one of the primary reasons ECC is the hot thing these days (just check eprint.iacr.org)
-
Orca
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 think it's enough to say the theory is proven... no number of bits of security is ever going to be "enough" to be uncrackable. However, a LARGE number of processor-time units on even the fastest processors available is needed to crack strong encryption.
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 prediction formulas that should be able to give pretty reliable statements for how many processor-time units a security key will require to discover by now... the challenges just give us real-world datapoints to verify theories.
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.
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.
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
ECC-109 was not brute forced. They used a cycle finding algorithm to find a collision [blah blah read site].
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.
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.
Someday, I'll have a real sig.
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.
"If you put enough computers on the problem, you will eventually find a solution by random chance. (correct me if I'm wrong.)" Yeah, but the number of primes 2^109(109 bit number) is about 2^109 / ln(2^109), and after some ballparking this is 2^109 / 109 (pretend e = 2) which is still a 100+ bit number of primes. Now if you have 1,000,000 computers doing 1,000,000,000 checks per second, this would be a total of 1 quadrillion checks per second. or about 2^40 checks per second, so then this would take 2^60 seconds to check all primes this way. This is equivalent to 2^25 years, a little longer than most of us will live. And the above was only for RSA, and ECC is more secure than that, so enough computers doing this randomly is not a viable option.
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