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.
It's not just a few thousand dollars, it's a few hundred thousand dollars.
RSA-1024 -- $100,000
RSA-1536 -- $150,000
RSA-2048 -- $200,000
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
This is not entirely correct. Elliptic curve cryptography (spelled this way) is based on elliptic groups where per definition is always an inverse so you can always "go back". Getting this inverse is considered to be hard - but this is not proven yet.
In fact for the related parabolic and hyperbolic groups, there are fast algorithms for calculating and inverse. So I personally doubt that elliptic groups are save. Furthermore it's relatively unclear why the researchers cling to the elliptic setting - using the Picard groups of quartics or sextics might prove much more fruitful.
Owner of a Mensa membership card.
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.
Go ahead, use 3DES for your encryption, PLEASE. I'd love to be a spy next time you do a key exchange, so many ways to find out what your key is, and then read your data without you knowing. Please trust your data to 3DES.
For those who know nothing of encryption, 3DES and ECC solve different problems in practice. ECC is public key, meaning you can publicly give the key to everyone, and have no worrys that someone who copys your transmission will be able to understand what is said because there are actually two keys, one encrypts, one decrypts, knowing one doesn't help you do the other operation. 3DES has one key that you need to keep secure at all times. Typically you would use the two togather to achive security that is difficult to achive alone. The poster by suggesting using 3DES (which is very good) in place of ECC is forcing himself into a situation where a lot of security cannot be done.
Quantum computing kills both equally, the same algorithms that get RSA and discrete log can get the elliptic curve discrete log.
Test your net with Netalyzr
Firstly, as mentioned, the DMCA does not apply to Canada.
But may apply to Americans taking part in the challenge.
Secondly, the DMCA does not apply to mechanisms not used to protect copyrighted data.
I understood from the article that they are already using this method to encrypt data like faxes, and that anything fixed in a medium automatically gets an implied copyright by the Berne Convention.
Thirdly, the DMCA does not apply if you've been invited to try to break an encryption mechanism.
Did we forget about the SDMI Challenge (April 21st, 2001)? I felt the chill.
Anyway, a failure to meet this challenge only says that you need to spend more than "one meellion dollars" to break the encryption. That doesn't make me feel too secure.
Oh, say does that Star-Spangled Banner entwine / The myrtle of Venus with Bacchus's vine?
It was the predecessor of NSA, the pockets of intelligence (TICOM, ASA, AFSA) which were to be transformed into the NSA at a later time.
But very little has actually changed. For instance, in 1945 the U.S. Army intelligence spied on the United Nations conference in San Francisco (the reason why it was held in the USA was to better spy on the other countries). You need not search that far in history (few years) to find out similar things from New York.
http://www.mersenne.org/prime.htm
Being called a dork on Slashdot must be like being called the retard in special ed.
The actual government agency was the Signal Intelligence Service (SIS). I don't whether it eventually became the NSA. Here is a brief summary.
Well, there's spam egg sausage and spam, that's not got much spam in it.