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 ;)
... they should have left an option open for people finding holes in the ACTUAL implementation... Now only mathematicians stand a chance - go, go, go, you few good number theoretisists not employed by the NSA! =-= insert favorite conspiricy theory here =-=
it's really a one time pad. =)
"And a voice was screaming: 'Holy Jesus! What are these goddamn animals?'" - HST
They are using keys that sound big 168 bits, 256 bits, etc. But those aren't really that big, only 21 bytes and 32 bytes respectively. These sentences are longer than those keys.
Then I note that UNIX limits passwords to 8 bytes. A measly 64 bits.
I don't think I can sleep well knowing that all that stands between my data and some hacker is such a small string.
I have been pwned because my
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
...is that it uses much smaller keys with the same level of encryption. This makes it useful for handhelds and phones, and network devices. If you've never heard of this before, chances are you're already using it, too, as this is prevalent already in many of the aforementioned devices.
libertarianswag.com
It's a Canadian company, there is no DMCA in Canada...
From the guru Bruce Schneier, Fallacy of cracking contests
Free XBox, PS2
I think the company who came up (or rather markets) ECC [eliptic curce cryptography] should be careful about saying that ECC is more secure than RSA. RSA has stood up to A LOT of cryptanalysis, simply because of it's age. ECC might have bad keys or something else we don't know about simply because we have not have time to try all attacks yet. Who knows, tomorrow someone may find a trivial algorithm for taking the discrete logarithm on an EC (rendering ECC useless). Then again, someone may find a way of doing a simple discrete logarithm (rendering RSA useless). Both are highly unlikely, but hey -- stranger things have happened.
Basically, take a company's claim with a grain of salt. Right now I'll keep my data encrypted with something more tested (3DES anyone?).
My other car is first.
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
One million dollars split between 500,000 people is what??? TWO DOLLARS!!! Well, at least we'll be able to pay that annoying paper boy...
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.
In theory and given enough time, yes.
:) Our current universe is about 15 billion years old, so if you had 10^197 parallel universes, and you started at the Big Bang, you may be ready with brute force by now.
0 00 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 universes!
But if you can chuck all electrons of the world on it (about 10^91) and every electron is swinging with 10^15Hz, and every swing allows you to do a Yes-No-decision, you have a number cruncher that can check about 10^106 bits a second. If your key is 1024 bits long, you can check about 10^103 keys every second. There are 2^1024 different 1024 bit keys out there (about 10^320), so you need about 10^217 seconds to exhaust the key space with brute force, if you have the whole universe working as a big computer for you. A year has a little more than 30 Mio seconds, so your world computer needs 10^209 years for the task, give or take about a factor of 100 maybe. 10^211 years, 10^207 years, what's the difference anyway?
Imagine that:
10000000000000000000000000000000000000000000000
This company is saying their encryption can't reasonably be brute forced with current computing, even if you got pretty much everyone on the internet (more than are currently running SETI) to start brute forcing the keys. It's harder than RSA encryption mathematics theory, on a key which is like 163 bits for the $20,000 prize, and to get a million you'd have to break the scheme for any bit length I imagine, not just the 224 bit key they mention earlier in the article.
So, unless there is a quantum leap (how ironic that quantum computing would indeed be a quantum leap) this is not some kind of Distributed project. RC5 was fairly simple bruteforcing at the end of the day.
The summary of the article is like so dumb I cannot believe it passes muster. And the million bucks are as likely to be awarded as a release of Duke Nukem Forever and Ever Amen. Nothing to see here, move along.
Conversion Rate Optimisation French / English consultant
It's a trick.
Mathwiz: "Hello? I think I may have cracked your encryption".
NSA: "Great. Just stay where you are and we'll over with you money in a second".
[40 seconds later]
Police: "Drop your weapon and step out side!"
Mathwiz: "But I'm unarmed!! Dude!"
Police: "I said DROP YOUR WEAPON".
[BLAM!]
...to crack it, but as of how long it will take them. Information that is worth a lot today may be worthless tomorrow, and by next week it'll be history. So the question isn't about making a perfect encoding (we allready have one, namely 'one time pads'), but finding the best encoding for the application. Also bear in mind the rule of thumb that states that the thoughter the code, the more difficult (think CPU-cycles and batterydrain) it is to encode it in the first place. Off course, just how strong thats strong enought will change as the tools for encryption, decryption and codebreeaking gets stronger.
Remember folks, an encrypted message don't have to be unbreakable, it just has to be hard enought to break. One rule of thumb is that it should cost more to break than the one breaking it will earn on doing so.
Besides, one can learn a lot about whats going on even if you can break the code. Where does the signal originates? Where is it heading. Does it occour on a frequent basis? What is the matter of transmitting? The more you learn about the message, the more you learn about the reason it's beeing sendt - even if you don't know what it says. THEN you can often start using social enginering to gain access to the key, or better yet, to the unencrypted message.
Everything in the world is controlled by a small, evil group to which, unfortunately, no one you know belongs.
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
I went over to their website and parused around... Seems they did the security to XM Radio, http://www.certicom.com/download/aid-78/success_XM Radio.pdf) which humors me because XM Radio was hacked about 2 months after it went live.. All you need is a part from an old Dish Network reciever and a soldier iron.
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.
I wouldn't waste a CPU cycle on this contest.
Bruce Schneier nailed the truth about cracking contests in a December 1998 article in his crypto-gram newsletter, "The Fallacy of Cracking Contests".
Here is another article he published in November 1999, "Elliptic Curve Public-Key Cryptography".
Interesting reading.
Fools ignore complexity; pragmatists suffer it; experts avoid it; geniuses remove it. ~A. Perlis
http://www.mersenne.org/prime.htm
Being called a dork on Slashdot must be like being called the retard in special ed.