ECC2-109 Winners Certified

An anonymous reader writes "The ECC2-109 encryption challenge has now been broken and certified! Certicom announced on Tuesday that the winners, a team from Ars Technica and a member of TeamIMO, will both receive $2500 each for the matching distinguished pairs that has solved the elliptical curve encryption scheme."

bah

[wviperw]

Only $2500? Some of the contests I've seen (namely having to do with the RSA encryption scheme) have been offering prizes upwards of 100 grand IIRC.

I bet the computing time just to break the code probably costed a wee bit more than $2500.

The A HREF="http://www.certicom.com/index.php?act

[Anonymous Coward]

The contest website [certicom.com] doesn't mention a $1M prize, but from the "details" pdf [certicom.com], it looks like you can earn the $1M prize by solving 19 smaller problems, each with their own bounty. $30k for an "infeasable" problem seems a little low to me... I imagine the mob may pay more ;-)

From the pdf: The 109-bit Level I challenges are feasible using a very large network of computers. The 131-bit Level I challenges are expected to be infeasible against realistic software and hardware attacks, unless of course, a new algorithm for the ECDLP is discovered.

The Level II challenges are infeasible given today's computer technology and knowledge. The elliptic curves for these challenges meet the stringent security requirements imposed by existing and forthcoming ANSI banking standard

Challenge Field-size(in-bits) Estimated-number-of-machine-days Prize(US$)
Elliptic curves over f2^m - Exercises:
ECC2-79 79 352 Handbook of Applied Cryptography & Maple V software
ECC2-89 89 11278 Handbook of Applied Cryptography & Maple V software
ECC2K-95 97 8637 $ 5,000
ECC2-97 97 180448 $ 5,000

Level I challenges:
ECC2K-108 109 1.3 x 10 6 $ 10,000
ECC2-109 109 2.1 x 10 7 $ 10,000
ECC2K-130 131 2.7 x 10 9 $ 20,000
ECC2-131 131 6.6 x 10 10 $ 20,000

Level II challenges:
ECC2-163 163 6.2 x 10 15 $ 30,000
ECC2K-163 163 3.2 x 10 14 $ 30,000
ECC2-191 191 1.0 x 10 20 $ 40,000
ECC2-238 239 2.1 x 10 27 $ 50,000
ECC2K-238 239 9.2 x 10 25 $ 50,000
ECC2-353 359 1.3 x 10 45 $ 100,000
ECC2K-358 359 2.8 x 10 44 $ 100,000

Elliptic curves over Fp - Exercises:
ECCp-79 79 146 Handbook of Applied Cryptography & Maple V software
ECCp-89 89 4360 Handbook of Applied Cryptography & Maple V software
ECCp-97 97 71982 $ 5,000

Level I challenges:
ECCp-109 109 9.0 x 10 6 $ 10,000
ECCp-131 131 2.3 x 10 10 $ 20,000

Level II challenges:
ECCp-163 163 2.3 x 10 15 $ 30,000
ECCp-191 191 4.8 x 10 19 $ 40,000
ECCp-239 239 1.4 x 10 27 $ 50,000
ECCp-359 359 3.7 x 10 45 $ 100,000

Re:bah

[stienman]

This contest was $10,000. Half went to the project maintainers, and then half of the remainder (1/4) is given to each of the people who found the collision.

So the individuals got $2,500, and whoever put the project together and hosted it got $5,000.

-Adam

Re:bah

[Bobdoer]

One of the other crypto distributed computing projects that's testing a higher level on encryption is only giving away $1,000 to the winner out of the $10,000 coming from RSA. Here's Distributed.net [distributed.net]'s cash distribution:
$1000 to the winner
$1000 to the winner's team (or to the winner if not on a team)
$6000 to a non-profit organization chosen by all participants
$2000 to distributed.net for building the network and supplying the code
And as ECC2-109 in being run by the company that owns the process, the costs of running the severs that support the project are not factored into the prize distrobution.

Re:Wow.

[NotAnotherReboot]

Well, obviously you adjust your encryption to what you think people will be throwing at it. That goes without saying.

Like it said, the next one is not expected to be cracked for some time because it is far more complicated to brute force.

If it's valuable- determine how valuable it is to others, and encrypt based on that plus some.

For instance, this would work fine for credit cards, seeing as the cost of cracking the number would be far greater than the cost of processing power. Most of the time, however, it is far easier to avoid encryption altogether and hit those who do not bother.

Re:bah

[AArmadillo]

Many of the problems worth lots of money from RSA are significantly harder than this one is. For example, it took distributed.net almost 5 years to solve RC5-64, worth $10000. The RSA factoring challenges worth lots of money are also extremeley difficult problems; the top one (2048 bits for $200,000) would probably take several thousand years even if every machine on the planet constantly worked on it and nothing else.

Re:Wow.

[rasafras]

This is a small key size for the scheme. On the website they have other challenges posted where the key size is four or eight times as long, which are deemed 'infeasible'. This was not a completely realistic security test of the ECC algorithm, they expected it to be solved.
If this was used for real data, the key would be much longer and it would take probably a few billion years to solve.

Re:You can do better stuff with CPU time!

[Cecil]

Hooray for not checking links. Corrected link to Folding@home [stanford.edu]

Sorry.

Brief explanation of elliptic curves

[NonSequor]

An elliptic curve is the set of solutions to a cubic equation in two variables on some field (a field is a set on which two operations which behave like multiplication and division are defined). The solutions form a cyclic group. A group is a set on which an operation is defined such that there is an identity element, every element has an inverse, and the associative property holds. In a cyclic group, if you "multiply" any element by itself enough times, you'll get the original element.

What makes all of this junk more interesting to computer people is that if you use a field with finitely many elements, you end up with some tools that can be used for things like factoring and other problems in number theory.

Elliptic curve cryptography is based around the discrete log problem. That is, you are given two elements of the group, a and b, you want to find what value of k makes a^k=b. This problem can be solved in polynomial time in some cyclic groups, but elliptic curve groups lack certain niceties that make solving the problem for them tough.

It is believed that elliptic curve cryptography will allow one to use significantly smaller keys than those needed by RSA without a loss of security.

PARENT IS COMPLETE AND UTTER NONSENSE

[Paul Crowley]

ECC ("this Certicom encryption system") has turned out to be exactly as hard to break as Certicom and everyone else expected - if anything, the results of this challenge increase our confidence in it.

109 bits was deliberately chosen to be short enough to break. The next challenge is 131 bits, which is also considered breakable (though it will be about 2048 times harder).

After that, you get on to the "Level II" challenges, which are not considered breakable. They start at 163 bits, the least recommended for real use, and would be about 140 billion times harder to break.

I worry about the /. moderators sometimes...

Re:A question about keys

[AiY]

> Does that mean that I have the private key that will decrypt all files encrypted with that public key?

Yes.

> How large a file or how many files do I have to decrypt to be assured that I have uniquely identified the private key?

If it decrypts the encrypted file (that is, you run the decrypting algorithm with the "key" you found and you get the un-encrypted text back exactly), then one. If the encryption system is good, the file doesn't have to be too big, but it should probably be a few kilobytes of input. More input may make it easier to discover the private key (choosen plaintext attack), but if the encryption is good it doesn't help.

Public key encryption systems are devised so that key collisions are unlikely. If there are none, that is good. If there are several, that is bad. If there are several that collide but it is hard to calculate what the other collisions might be, that is good. If the mathematical operations in the keyspace are difficult enough to make encryption possible, then calculating the collisions is just as difficult as calculating the private key given the public key.

> Is it true that if I don't give out a public key that I can produce documents that are in principle un-decryptable.

If you mean "I'll generate a public/private key pair and throw away the private key" then yes. Not terribly useful, but yes. But if you found a sufficiently random input source, you could just generate globs of random data that would be equivalent to that.