Crack the Code and Win a Million Bucks

JS_RIDDLER noted a Toronto Star article about a sort of contest to crack some encryption and win a million bucks. The article is a bit fluffy, but it getst the point across... we wasted all those RC5 keys ;)

Comments

RSA vs ECC

[noelp]

For those of you who are suprised at the number of bits needed to secure data using ECC compared to RSA, a good discussion can be found here

http://www.cs.uct.ac.za/courses/CS400W/NIS/papers0 0/mlesaoan/paper.html

Prize breakdown / contest page

[morcheeba]

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

Fallacy

[savagedome]

From the guru Bruce Schneier, Fallacy of cracking contests

Re:Fallacy

[mistered]

Much more relevant is Schneier's Essay on Certicom and ECC. Note though that this isn't your typical doghouse style "crack our code for $1 MEELEEON dollars" contest with fine print that says you have to do it in three days on a Commodore 64. It's a fair contest for a "real" algorithm. Anyone who completes any of the sub-contests is (a) not in it for the money and (b) unlikely to be a generic Slashdot hacker.

By the way this is Schneier's recommendation on ECC:

My recommendation is that if you're working in a constrained environment where longer keys just won't fit -- smart cards, some cellphones or pagers, etc. -- consider elliptic curves. If the choice is elliptic curves or no public-key algorithm at all, use elliptic curves. If you don't have performance constraints, use RSA. If you are concerned about security over the decades (almost no systems are), use RSA.

Re:Brute force

[Entrope]

I was slightly worried that this would be what Bruce Schneier calls "doghouse crypto" -- if you use it, you belong in the doghouse. The kind of companies that sell doghouse crypto usually don't say what algorithm they use, they usually use a "proprietary" (non-critically-reviewed) algorithm, and they usually don't have nearly enough knowledge to do a good review themselves. Fortunately, it's ECC, which is well known and well reviewed.

Elliptic Curve Cryptography is, like RSA and Unix crypt, believed to be hard because it looks like a one-way door: It is easy to go in one direction, but unless you have exactly the right data (or an obscene amount of time), impossible to go in the other direction.

Classic Unix crypt is limited by its key size to 56 bits, which makes it practical for a dedicated attack to break. RSA is limited by its structure to use keys that are related to large prime numbers; prime numbers are relatively rare. ECC shares neither of those limitations, so you get a lot more bang from your bits.