Crack the Code and Win a Million Bucks 276
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 ;)
2 bad... (Score:5, Interesting)
Re:2 bad... (Score:5, Interesting)
As for Elliptic Curve Cryptography as mentioned in this article - it's still in its infancy - at least compared to other ciphers. This is just a stupid publicity show. But I bet I can win that $1M with an investment of under $20.
There is an old KGB proverb: "It is easier to break fingers than it is to break codes." So, using my $20 budget on a pipe cutter, fifty feet of rope, and an ice pick, I believe I can recover the key.
Re:2 bad... (Score:5, Funny)
How about I provide the financial backing for your plan and we split the profit.
--
In London? Need a Physics Tutor? [colingregorypalmer.net]
American Weblog in London [colingregorypalmer.net]
Re:2 bad... (Score:2)
However keep in mind that $1M for reversing ECC is waaaaay too cheap.
That's if you'll manage to survive after you break it
Re:2 bad... (Score:2)
Re:2 bad... (Score:2)
Slashdot Personals (Score:2)
Apparently it is [osdn.com]
President Bush to Liberate Alaska [alaska-freegold.com]
Re:2 bad... (Score:2)
I really wish Certicom had not done this in this particular way. Offering million dollar prizes is actually quite common in the crypto world. Nobody ever collects because when the schemes are broken the company offering the prize goes under. Certicom are not that kind of fly-by-n
Re:2 bad... (Score:2)
We'll change that after they win.
Unrealistically high challenge == no challenge (Score:2)
Here's a cipher contest for mere mortals [jdueck.net]. It's been going on since mid-december. The prize is a tin of penguin mints and a boost to your self-respect. And anyone with a decent knowledge of basic cryptography should be able to crack it.
The downside is ... (Score:5, Funny)
Copyright violation (Score:2)
I demand that they pay for the copyright violation.
If you use another key, you'll see that it also includes SCO's source code.
I read this and wonder about UNIX (Score:5, Interesting)
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.
Re:I read this and wonder about UNIX (Score:5, Insightful)
Re:I read this and wonder about UNIX (Score:2)
Actually, neither any commercial Unix that I know of nor Linux limits your password length to 8 bytes. However, some Unix implementation currently only support 8-byte usernames.
Re:I read this and wonder about UNIX (Score:3, Insightful)
So?
2^64 is a big number, about 18,000,000,000,000,000,000.
Assume your computer can hash and test a billion passwords a second. It'll take you 584 years to test all combinations, a little less than three centuries on average.
Even the worst users out there change their passwords more often than THAT.
Re:I read this and wonder about UNIX (Score:3, Interesting)
However, how many use the entire eight-bit character set in their completely random p
Re:I read this and wonder about UNIX (Score:2)
Re:I read this and wonder about UNIX (Score:2)
Re:I read this and wonder about UNIX (Score:4, Insightful)
No, my friend, it's not 92*8 but 92 to the 8th power (92**8, if you like). Thats 5,132,188,731,375,616 which is a good deal more than 736.
RSA vs ECC (Score:5, Informative)
http://www.cs.uct.ac.za/courses/CS400W/NIS/papers0 0/mlesaoan/paper.html [uct.ac.za]
ECC vs ECC = AC (acronym collision!) (Score:3, Interesting)
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 :
Re:RSA vs ECC (Score:2, Insightful)
RSA - and most public key systems - are extremely slow when compared to symmetric systems such as DES, AES etc.
Sure, RSA is readily usable on desktops, but you don't need a very large key before even a simple encryption og a few kilobytes becomes an expensive operation.
Besides, desktop computers is hardly the only environment in which encryption is used. Smart cards, which are often limited in both CPU and RAM, benefit hugely from ECC where the computing and memory overhead is much sm
Re:RSA vs ECC (Score:2)
Karma whoring at its most pathetic.
Re:RSA vs ECC (Score:2)
Re:RSA vs ECC (Score:2)
So saying "I'd use ECC because it's faster" is a tad loaded.
Tom
Re:RSA vs ECC (Score:2)
Here is some supporting documentation. [entrust.com]
Also, the article says:
The link above disproves that as well. Also, the article says .
Re:RSA vs ECC (Score:2)
If anything multiplication is O(n^1.58) [using Karatsuba] and you will have 2.5 multiplications per bit of exponent [squaring, reduction and prob 50% of multiplication]. That's 3*n^1.58 work for n digits. ECC on the other hand requires one modular inverse per bit (n^2) as well as several multiplications and various other things [a
Re:RSA vs ECC (Score:2)
Prize breakdown / contest page (Score:5, Informative)
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
ECC2-109 project (Score:2)
Anyway, there are different clients available if you want to participate. I would suggest this client [dcworld.nl] and this GUI [gilchrist.ca]. The project is moving to the end fa
Linux client (Score:2)
Happy cracking.
Re:Prize breakdown / contest page (Score:2)
I'm guessing that's something I won't be seeing on the next season of the Sopranos.
The real promise of this technology... (Score:5, Interesting)
Fallacy (Score:5, Informative)
Honeypot! (Score:3, Interesting)
Re:Honeypot! (Score:2)
Re:Honeypot! (Score:2)
Re:Honeypot! (Score:2)
Not around here, they don't. If you read the Terms and Conditions for the lottery, they state that if you win over a certain threshold (i.e., the jackpot), then in order to claim the prize, you have to consent to being photographed and having your name released. It is impossible to claim lottery winnings anonymously. It's actually the law. Think about it. If people could claim lottery winnings anonymously, how would
Re:Honeypot! (Score:2)
Re:Fallacy (Score:5, Informative)
By the way this is Schneier's recommendation on ECC:
Not a Fallacy (Score:3, Interesting)
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 crac
Huh? (Score:3, Interesting)
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
Better than RSA? (Score:5, Interesting)
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?).
Re:Better than RSA? (Score:3, Informative)
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 actual
Wouldn't rush to adopt this... (Score:4, Informative)
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?
Re:Wouldn't rush to adopt this... (Score:3, Informative)
By recently I take it you mean within the last century or so. Elliptic curves are pretty much a staple now in number theory and modern algebra.
the conjecture that the elliptic curve logarithm problem is very hard to solve might be proved wrong tomorrow.
And large integer factoring (RSA) and the discrete logarithm problem (DSA) are both believed to be hard, but both could be proved/demostrated to not be as h
ECC and RSA die under quantum... (Score:3, Informative)
Quick,someone start a distributed computer effort! (Score:5, Funny)
What about the DMCA? (Score:3, Interesting)
What position are the lawyers thinking about after the break the encryption?
Yawn (Score:5, Insightful)
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.
Re:Yawn (Score:2)
Of course, a quantum leap is a very small leap.
Re:Yawn (Score:2)
Well... (Score:2)
The reason for the saying is that it is a leap, with no intermediate stage. There is a before, and an after. Compared to say an object going from warm to cold - there's always intermediate stages, no matter how quickly the object is cooled.
That's why quantum computing is a quantum leap - because there's no intermediate stages between that and electronic coputing. There's a before, and an after.
Kjella
Re:Yawn (Score:2)
Ah, you don't bother to bruce force the public key to recovery the private key. You use factoring.
Re:Yawn (Score:2)
rsa requires factoring...this isn't rsa
Are we talking RSA-ECC or DLP-ECC? (See: RSA Labs FAQ [rsa.com])
Don't do it! (Score:5, Funny)
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!]
Mostly the plot line for Mercury Rising (Score:2)
Time for some coding (Score:3, Interesting)
Re:Time for some coding (Score:2)
See OpenSSL [openssl.org] and Sun's announcement [sun.com] for including ECC code in OpenSSL.
Re:Time for some coding (Score:2)
Last I heard, OpenBSD was going to fork OpenSSL off and maintain their own version as these restrictions no longer allowed them to include OpenSSL that fit their charter.
Perhaps someone that knows more about this could comment?
It's not as much a matter of IF someone manages... (Score:5, Interesting)
...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.
Book (Score:3, Informative)
Slashdot has reviewed [slashdot.org] this before.
XM Radio (Score:5, Interesting)
Re:XM Radio (Score:2)
They may make it a pain in the butt to find the key, but it is an inherently "easy" problem,
This isn't news (Score:4, Informative)
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.
hmm (Score:2, Funny)
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
Best Will Hunting... (Score:2)
So get ready to hit the pause button, and have pencil and paper ready.
Other, more worthy projects? (Score:2)
The Fallacy of Cracking Contests (Score:5, Insightful)
Bruce Schneier nailed the truth about cracking contests in a December 1998 article in his crypto-gram newsletter, "The Fallacy of Cracking Contests [schneier.com]".
Here is another article he published in November 1999, "Elliptic Curve Public-Key Cryptography [schneier.com]".
Interesting reading.
I managed to crack it!! (Score:2)
Sorry... (Score:2)
You keep right on developing that uncrackable ECC st
ECC is cool but RSA better (Score:2)
Patent nonsense (Score:2)
And why don't we have digital cash? Well, social problems primarily, but it doesn't help that David Chaum and Stefan Brands, after developing *phenomenally* cool techniques for preserving privacy in electronic cash, carpeted the whole area with patents.
So, thanks for setti
Key-size comparisons suck (Score:3, Insightful)
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.
Who cares about $1M (Score:2)
That's like, what, US$25?
Go to goodwill and pick up a bunch of monopoly sets for that price and save yourself the trouble!
this is nonense, it proves nothing but being crap (Score:2, Insightful)
no DMCA in Canada (Score:4, Informative)
Re:no DMCA in Canada (Score:3, Insightful)
Just because the DMCA is bad doesn't mean it's a ban on all reverse engineering.
"Know your enemy" etc..
Re:Huh? DMCA anyone? (Score:3, Informative)
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 for
Re:Duh! (Score:2, Funny)
The *answer* is 42. We don't know the code. Or the question.
Re:Brute force (Score:2, Insightful)
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.
Re:Brute force (Score:5, Informative)
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.
Re:Brute force (Score:2, Informative)
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 prove
Re:Brute force (Score:5, Insightful)
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
Re:Brute force (Score:2)
Re:Brute force (Score:2)
Argh... (Score:2)
A 1024 bit symmetric key has 2^1024 possibilities. Which is excessive, 128 is common, 256 bit is probably safe for all future.
A 1024 bit asymmetric key depends entirely on the algorithm, but has typically nowhere near 2^1024 possibilities. RSA 5-700 bit challenges have been broken. Based on that, 1024 bit RSA is about as difficult as breaking a 128 bit symmetric key. So a factor of about 8:1.
The ECC algorithm is much
Re:Brute force (Score:2)
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
Re:Brute force (Score:3, Interesting)
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.
Re:Brute force (Score:2)
You raise very good points. (Score:3, Interesting)
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
Re:You raise very good points. (Score:2)
I would tend to agree with you that concerns about the security of ECC are overblown, and tend to come from the common wisdom that old-and-proven is better than new-and-unproven.
Let's see, RSA [mit.edu] was put forth in 1977. ECC was first discussed in the mid-1980s, by Victor Miller (IBM) and Neal Koblitz [washington.edu].
So which is suppose to be "old-and-proven" and "new-and-unproven"?
In fact there is no assurance that RSA or DSA is any more secure than ECC. RSA is not proven (in the math sense) to be secure. We do not know f
Re:ECC is hard to crack (Score:2)
Impressive, your entire paragraphs were, word for word, copied from here [std.com]
Alert, Karma whore. The only thing he changed was "You may have heard arguments" to " I often hear".
You often plagerize?
Re:Mod Parent Up (Score:2)
Perhaps you you refer to my post to the parent? He copied it straight from here [std.com] under the heading "Is Elliptic Curve Cryptography Safe?"
Re:Keys are Safe (Score:2, Informative)
RSA-1024 -- $100,000
RSA-1536 -- $150,000
RSA-2048 -- $200,000
Re:Keys are Safe (Score:2)
The reason these cash prizes are used is to make people assume what you are assuming: "Hell, they wouldn't offer so much money if their protocal was not safe."
Although I surely hope that turns out to be the case, jumping to that conclusion without any data is dangerous.
AC
I rather not go to jail (Score:2, Funny)
I don't think cellmate Bubba would be interested in that particular crack.
Re:searching for primes? (Score:4, Informative)
Re:NSA accomplishments exaggerated (Score:3, Informative)