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
The *answer* is 42. We don't know the code. Or the question.
Surely anything can be cracked if enough brute force is chucked at it.
Not really. Trying to brute-force a message encrypted with a one-time pad will generate every possible message of the same length. You can't determine which of those messages is the true one.
Agree or disagree, I usually at least understand Slashdot editorial comments. But I don't get "we wasted all those RC5 keys". You mean we cracked them when they could have been used? I hope not. You mean we cracked them without the promise of 1 meelion dollar bills? Ok, greedy, but I'm with you.
Seriously, how do you waste a key?
-madgeorge
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.
and we'd most certainly be happy to consider them for a lifetime position
;-)
What position are the lawyers thinking about after the break the encryption?
This SIG pulled due to lack of funding. (This damn war is costing too much!)
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!]
There's a general uneasiness in much of the cryptographic community regarding ECC that comes from the thought that with a new and elegant cryptographic algorithm or methodology there is often a new and elegant attack that renders it worthless in practical applications. As I'm sure you realize (but others may not) the ability of a methodology to withstand conventional attacks is no indicator of long-term viability; algorithms may only be proven unsafe, not safe (except perhaps for one-time pads under certain circumstances).
I happen to hold out hope for this technique, but it takes time in the field for confidence to be built. This contest may help, but by no means is it absolute proof of the security of the technique (although one would be hard pressed to make a million dollars hoarding a working attack on ECC to themselves).
Try not. Do or do not, there is no try.
-- Dr. Spock, stardate 2822-3.
Anyone (outside patent encumbered countries) working on a Free implementation? It should be okay in the EU, for "allowing interoperability with existing products".
"'I pass the test,' she said. 'I will diminish, and go into the West, and remain Galadriel.'"
- JRR Tolkien.
...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.
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.
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.
There are exceptions, but they are few and far between. The RSA challenges, both their factoring challenges and their symmetric brute-force challenges, are fair and good contests. These contests are successful not because the prize money is an incentive to factor numbers or build brute-force cracking machines, but because researchers are already interested in factoring and brute-force cracking. The contests simply provide a spotlight for what was already an interesting endeavor.
In this case, finding clever ways to factor ECCs is actually a number-theoretically interesting thing to do.
I'd rather win a million legally.
I don't think cellmate Bubba would be interested in that particular crack.
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.
As has been pointed out, demonstrably crackable encryption is OK for data with an expiry date. Credit card numbers, for instance, are usually only good for 3 years or so -- you get a new number with the new card.
Still, I worry about any closed-source encryption technology. Imagine somebody coming up to you and saying in a cheesy mexican accent: "Hey, extranjero! You want to send top-secret message? No problemo, Amigo! I know secret code, so secret only me and my brother know it. You give me message, si, you dictate, one words at a time. I write it down in secrets codes and send it to my brothers. He only one in whole wides worlds who understand it. But my brother, he take it to your amigo, si, and he tell the message one word a times. Is very good. Top-secret. Only me and my brothers knows the code."
Je fume. Tu fumes. Nous fûmes!
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
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
It seems that these two two acronyms, which are very different in meaning, are likely to show up in the context of computer-related discussions :
The Russians have won. They have made the world a cesspool of distrust, greed, fear and hate.
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?
This is comparing an apple and an orange and concluding something about a strawberry.
When it comes to encryption keys, it's not the size, it's how you use it.
I am sorry to be against this topic but I do seriously urge any person competent not to participate in such a bullshit test. Asking people to "crack" something while offering cash doesn't mean it's secure (which is what is implied, which is insanely stupid for people that work in security and professionnals involved in cryptography). It just proves that no one that cared to break it came over it to break it. Serious cryptographers ask people to present their work in a formalized scientific form. We have a HUGE history of crypto having get breaked and like in science, we want people to present their work and show us they did study all previous breakings and that none apply to their work. This is annoying, yes, but it's like that in science. If it's done seriously and how people expect it to be ,it will be considered seriously. No cryptographer will ever consider loosing time in such a contest unless there is a serious implication for people or the public (like voting machines for example).
We should bash this stupid annoucement that implies that "if no one breaks it it means it's secure" because that's an insult to cryptography and those that work hard in shadow to have it work properly.
This is really the kind of stuff that pisses me of :(
http://www.mersenne.org/prime.htm
Being called a dork on Slashdot must be like being called the retard in special ed.
No. It's just that you know you're in trouble when people use "age of the universe" as a unit of measurement. It'll break, it's just that it'll take so long that when you (or rather your far distant descendants) crack it, there probably won't be a great deal of point in knowing it.
At that point, it's simpler to use the Caveman attack:
Walk over, beat subject about the cranium with a stout cudgel, and take the subject's computer containing the keys.
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.