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."

Comments

Really hard to understand for someone

[after]

At least for me, I never heard of this ECC-109 method before. The summery clears it up though.

Project Overview

This is a distributed computing project to solve the Certicom ECC2-109 challenge.In general it can be described as a whole lot of computers from all over the world, all of them working together in an attempt to have a collision. Each of the computers runs a program that computes DP (Distinguished Points) values. Each time a computer finds a DP, it is uploaded to a main server. The main server then checks to see if anyone has uploaded a matching DP (this is known as a collision). If a collision happens (two matching DP values exist), then the Certicom challenge is solved!

Yea ... but what practical use does this have? Was this done _just_ because it could have been done?

Re:Really hard to understand for someone

[bluGill]

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.

Question for the more cryptically inclined crowd:

[jamonterrell]

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.

Re:Question for the more cryptically inclined crow

[acidblood]

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.

Re:Question for the more cryptically inclined crow

[rueba]

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.

Some answers, maybe....

[crypto257]

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