Slashdot Mirror
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."
$2,500 for breaking an encryption scheme. I wonder what SETI@Home will pay me for discovering an extraterrestrial...
If "disco" means "I learn" in Latin, does "discothèque" mean "I learn technology"?
Nasa will be the one awarding your prize... A pair of handcuffs, followed by a rag soaked with ether. After that you will just undergo lots of brainwashing, and you pretty much get the idea from there. :)
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.
Nothing disturbs me more than blind loyalism towards some unrealistic and over-idealistic notion of one's nationality.
1) Put the decryptors in a remote island
2) Make them wear skimpy clothing
3) get them to compete in small subgames, such as
blow the fish up etc..
4) Get an affable good looking host to..err host..
5) Get cameman to zoom in on their mental games an
anguish as they try their best to out-decrypt the
other contestants.
voila..$1Million Cash Prize
The contest website doesn't mention a $1M prize, but from the "details" pdf, 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
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.
Now let's run the same test, but instead of attacking the algorithm, let's see how many hours it takes to social engineer the key :)
I wonder what would happen if China began requiring all computers in the country to run some unspecified distributed application.
Not trolling, just musing. I doubt such a thing would happen in any country.
True story.
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.
webpage
Is it just me, or is there no real point to these encryption challenges? Brute forcing one particular key doesn't help you attack the encryption algorithim in general, and we can already calculate about how long it will take to crack with current processors. Other than the prize money, there is no reason to participate (except maybe for bragging rights, but finding an algorithmic flaw would get you so much more). Perhaps the prize money and CPU time might be better spent searching for a cure for cancer? I know there's a distributed computing project out there that does just that (no link right now, I'm lazy), and this *is* a case where the computers are just as good at calculating numbers for cracking encryption as calculating numbers for saving lives.
Damn. That's my root password. Damn again.
More importantly there are more useful distributed computing projects. Here is a pretty good index. For example there's Folding@Home which furthers our onderstanding of proteins, which are so important in so many life processes and diseases, and fightAIDS@home which has already found a promising new drug. Or how about SETI@home? Trying to crack encryption by brute force seems like such a waste in comparison to these.
Perhaps the encryption contests are so popular just because you can win money. It's like a lottery. Maybe the only thing that could be done would be to have a cash prize for significant findings in other projects, or if who did it can't be defined due to the nature of the algorithm, maybe even just an ordinary lottery?
1) It gives you a real world baseline of what kind of current power it takes to break your keys. You can then make some educated projections about what kind of security these keys will offer in the future. Computing power has and continues to grow at a fairly predictable rate. Thus you can infer how long a specific level of key will take to crack at a given point in the future, assuming no new mathematical or processing systems. Which leads us to
2) It encourages people to try novel types of attacks. Yes, there are those that are just doing a brute attempte and they are there fore reason #1. However there are those that will try to come up with new algorithms, new hardware, or a combination, to defeat your encryption and prove it weak. This is what it's all about. You don't prove encryption strong, you continually prove that it's not weak, lending creedence to the theory that it is strong.
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.
My only political goal is to see to it that no political party achieves its goals.
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.
/. moderators sometimes...
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
Xenu loves you!