Slashdot Mirror
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 ;)
http://www.cs.uct.ac.za/courses/CS400W/NIS/papers0 0/mlesaoan/paper.html
'Internet! Is that thing still around?' - Homer Simpson
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
HIV Crosses Species Barrier... into Muppets
It's a Canadian company, there is no DMCA in Canada...
From the guru Bruce Schneier, Fallacy of cracking contests
Free XBox, PS2
The problem with ECC is that the "hard problem" on which its security relies is based on some non-trivial mathematics which, until recently, no-one's really been interested in. Contrast this with RSA, which is based on a comparatively easy-to-understand problem (factoring a product of two primes) which has been known about for centuries.
What this means is, it's possible (very unlikely, but possible) that the conjecture that the elliptic curve logarithm problem is very hard to solve might be proved wrong tomorrow. That is much less of a risk with RSA (although see under quantum computing, if you go in for that sort of thing).
Last time I checked, the best "brute force" algorithm to attack ECC was the Pollard rho method. Is that still true?
These sigs are more interesting tha
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.
If any of you is seriously considering going at this, I recommend the well known Applied Cryptography
Slashdot has reviewed this before.
Free XBox, PS2
In the grand tradition of "It came over the wire service", Slashdot posts an article about a contest that has been going on since 1997. IIRC, I bookmarked http://www.certicom.com/research/ch2.html last january (I'm not sure because I have changed computers since then). Its been long enough that Certicom has changed their website too.
ECC is interesting, although I am not 100% sure that it is as relatively strong as Certicom claims. Elliptic curves are similar to the discrete log method, which can be shown to be approximately as strong as RSA (factoring). I am not an expert in Elliptic curves, so I can't speak as to whether there are any 'shortcuts' which would reduce the problem to a discrete log one, but if so, then the ECC would be no stronger than RSA. Elliptic curves, by the way, are the same branch of mathematics which brought us the proof of Fermat's last theorem.
http://www.mersenne.org/prime.htm
Being called a dork on Slashdot must be like being called the retard in special ed.