Slashdot Mirror
Biggest Public-key Crypto Crack Ever
galore writes "Certicom's ECC2k-108 Elliptic Curve Discrete Logarithm challenge has been broken! This was the largest public calculation ever to use a complex parallel algorithm. $5,000 dollars in winnings will be donated to the Free Software Foundation. Congratulations to everyone who participated, including team Slashdot! " There seems to be conflicting versions of info about the prize money - some says 8,000 to the Apache Foundation, others say 5,000 to the FSF.
Given the key-length and the time taken, what (if any) are the implications for EC encryption?
It's a small world and it smells funny; I'd buy another if it wasn't for the money; Take back what I paid (SoM)
i originally posted the story and said that $8,000 would go to the apache software foundation - this is still correct... i'm not sure why it was changed on the front page. just read homepage for the project.
--
The plan:
Solve part of Certicom's ECC challenge.
Win $10000 and give most of it to the Apache Software Foundation.
Um, that's it.
...
Certicom is offering a prize of $10000 for the first correct solution. If we win it, $1000 will go to each of the two people who find the match and we will donate the remaining $8000 to the Apache Software Foundation. Note that following our previous successes, we have already donated $12000 to the Free Software Foundation.
--
older versions of this effort donated to the FSF, this one is definitely going to apache.
later,
ian
other posters have pointed out that DES is a secure algorithm, but also of note is the ridiculousness of comparing ECC to DES. elliptic curve cryptosystems are for public-key use, while DES is a symmetric cipher. so no, ECC is not "better" than DES, or vice versa. DES is a very strong symmetric cipher that has withstood many many years of attacks. This project helps to show how strong elliptic curve cryptosystems really are, as they have been around a relatively short time (early 80's i believe). While elliptic curves have been studied for a great deal longer than that (as certicom points out), not until recently have they been looked at in regards to cryptography. If ECC is as strong as certicom claims, it proves to be one of the most interesting cryptographic techniques since public-key and RSA itself.
later,
ian
Isn't it about time the Apache project relocated to a country not a member of the WIPO? :)
Quoting Alfred Menzes, a consultant at Certicom and general ECC god-of-knowledge,in his web page says:
This same paper (written in response to Bruce's discussion of ECC in his Nov99 crypto-gram goes on to say on speed:
Returned Peace Corps IT Volunteer
Ok, I got confused mail. RSA can't really be broken in 12 micro seconds. That was a joke - refering to a previous article posted on /.
512 rsa really takes a few days to factor with specialized hardware (AFAIK).
-- Virtual Windows Project
Due to a bug in Slash, the message directly above this in the thread (BAYWATCH.JPG) was attached as a response to the wrong message. A newbie was asking a question about multiple encryptions in weird and unexpected ways, and whether or not it could provide security. So please--hold the flames, I really *did* respond to the right message, honest. :)
A bug report has been filed with Taco.
However, unlike DES, there is no known mathematical loophole
Sorry, this is glaringly inaccurate. There is NO known mathematical loophole in DES - the "least effort attack" is a brute-force attack. If there was a weakness known in the algorithm then the best attack would exploit this instead.
The DES algorithm is excellent, merely suffering from keys that are too short at 56 bits to give adequate protection - note the difference between the *quality* of the algorithm and the level of protection here. Triple-DES (112 bit key equivalent - don't believe anyone trying to sell it to you as a 168 bit key solution since there is an attack against double-DES making it only a single bit stronger than single-DES. Yadda yadda - see "Applied Cryptography" for the details) builds upon this and gives a level of protection considered unbreakable since the best attack is still the brute force attack trying all keys in turn, and 2^112 is somewhat larger than 2^56.
SThere are several certificational weaknesses of the DES algorithm that are not practical. Linear and differential cryptanalysis can reduce the required time needed to break DES to about 2^45, with massive amounts of known and chosen plaintext/ciphertext pairs.
Your statements about the strengths of double and triple DES should be clarified. The key-length equivalents that you mention are only applicative for what is know as a "meet in the middle" attack, whereby the attacker uses a known PT->CT pair and decrypts one DES encryption of the CT with a test key while encrypting the PT with another test key under one DES encryption. The attacker keeps a list of the pairs of the results in the middle (I'm handwaving here, as there are some optimizations that can be made) and when there is a match, the correct keys can be trivially recovered. The attack requires serious memory to even think of carrying out (orders of magnitude greater than all of the RAM installed on every computer that has ever been built).
ECC is not strictly faster than RSA. An exact comparison is rather difficult, as the proponents of each cryptosystem can adjust the parameters to make their system appear faster (ie. low or high encryption exponents, choice of basis, GF(p) or GF(2^m),optimization efforts). In most cases, RSA is faster than ECC, especially with a reasonable (2^16+1) public exponent during encryption. ECC is also NOT patent free. Certicom and others have patents on specific implementations and types of the general eliptic curve algorithm that can be significantly faster and more memory friendly than the classic eliptic curve defined over a large prime.
Have I got a deal for you. For only $19.99 (Plus $42.36 S&H) you could be the owner of a hand-made, titanium-polymer, mechanical pencil. No more broken pencils moments before cracking a code. This pencil has a full, money-back guarantee (Minus shipping and handling both ways). And if you order in the next 349 seconds (324 if you read slow), I'll toss in a free piece of 0.7mm lead.
[/Spam]
Sorry, I know it's slighly OT but I couldn't resist this one.
kwsNI
The jaws that bite, the claws that catch!
Team Apache cracks the code and the Apache Software Foundation gets the cash...
Apache (or some variant thereof) runs on over 50% of Internet-connected web servers...
When was the last time you took a peek in the Apache source code to make sure they weren't sneaking some sort of distributed processing client into the web server? Very suspicious indeed... maybe that's why my server's processor usage has been higher than normal! :=]
________________________
Corporate Jenga: You take a blockhead from the bottom and you put him on top...
The decrypted plaintext message contained copyrighted intellectual property.
All participants are officially under arrest.
Please proceed to your nearest police station to turn yourselves in, and nobody gets hurt.
-- What you do today will cost you a day of your life.
Here's what I'd do in order:
.JPG. Wow, guess what, it's not a .JPG... must be something else.
... another ZIP file! Well, damn. Smack it around with the Perl script once more.
1. Try and display it as a
2. Look at the first few hundred bytes of the file. Almost every distinctive filetype out there today has distinctive header information. Standard compression libraries (PKZip, zlib, etc.) have very well-known headers.
3. Try to unzip the BAYWATCH.JPG file. Hey, it's asking for a password. Damn.
4. Leaf through my notebooks to find PKZip's encryption algorithm (it's trivially weak, but I don't remember its implementation off the top of my head).
5. Ah ha! I've found the cipher that's used in PKZip. Now I've just got to write a Perl script that'll break the cipher--it is a trivially weak cipher, after all.
6. Presto. Now I've got the original file back, or so I think. I take a look at it with a hex editor. Hey, this is
7. Check the file again. I've suddenly got the secret recipe for the $250 Neiman-Marcus cookies. I hand over the fruits of my labor to Boris and Natasha in the hopes that they will use these cookies to lure the moose and squirrel to their doom.
... Looking through the chain, you've got some file (FOO.BAR) which you compressed using PKZip (FOO.ZIP). You ran it through uuencode and uudecode (net result, no change), leaving it as FOO.ZIP. Then you just compressed-it-with-password again and renamed it BAYWATCH.JPG.
Total time for me to break it--six hours. That includes time to write the Perl script to break PKZip's encryption (provided I don't already have one somewhere), time to debug the Perl script, and enough time to order a pizza and have a decent lunch while I work.
If I've already got a Perl script to rip PKZip's encryption, then figure it'd take me about fifteen minutes.
What I want to say is: if you are smart enough to leave no traces (or better yet, lure the crackers to a wrong trail), could even a 'mediocre' encryption algorithm (or combos thereof) be 'secure enough'?
... I hope this post answers your question. The short answer is "no". The long answer is "usually, no".
Not to belittle the sheer amount of computing power that was applied here or the effort that went into creating a client for said effort but I still object to calling this a "breaking" of an algorithm. Sure, they've found the key, but change the key and the same amount of computing power will be needed to find that one so what have we learned here? What was so great?
This is about as cool as a guy who claims he can open every safe and when asked to demonstrate sits down in front of it and starts turning the wheel until he gets the combination by accident. Everybody knows you can do it that way.
Now if the attack had taken just a few sheets of paper, a pencil and a calculator, then I'd be impressed.
I was about to break it, but then my pencil broke.
I'm not a slashdotter, I just play one on Slashdot.
So one particular message, encrypted with one particular pair of keys was cracked after running a brute force cracker on lots and lots of machines. I don't get it, what does this prove? Does it not in fact demostrate how hard it is to crack ECC? In fact, this does not prove anything. Maybe there are specific key-pairs which are particularly easy to brute force?
Can someone please enlighten me?
For those of you unfamaliar with with elliptical encryption I recommend this book. EE is an asymetrical algorithm in the same way RSA is. This "crack" is significant because it shows the relative strength between RSA and EE. 512 bit RSA ca n been cracked in about 12 microseconds. Other nice properties about EE algorithms :
- patent free (RSA expires this year!)
- faster than RSA
- can be implemented easily using 8/16bit microcode (ideal for smartcards)
Bruce likes to claim cracking contents have no value, but I disagree. EEs haven't been studied as much as RSA, so contest like this are important to showing the algorithms strength as implemented in the real world - and more importantly - generating interest in the research community.
-- Virtual Windows Project
Although I am a professional InfoSec consultant in real life, my opinions expressed here are not to be interpreted as my professional opinion. (There. Now that the legal disclaimers are done...)
1. ECC is not patent free. Several companies are engaged in patent war over ECC (Certicom being the number one). The "nice" curves have already been patented (mathematicians in the audience will crucify me for describing some curves as "nice", but it's a reasonably accurate layman description--some curves make crypto easier than others, hence they're "nice").
2. ECC is not faster than RSA. RSA is not faster than ECC. Nor are they equal in speed. While this all sounds terribly contradictory, it's all true; as we all know from having complained about NT-versus-Linux benchmarks, whoever is paying the analysis firm gets the results they want. When Certicom pays for ECC-versus-RSA, it always turns out that ECC is faster. When RSADSI pays for it, it always turns out that RSA is faster.
Even assuming that ECC were unambiguously faster than RSA, it wouldn't make a tinker's dam of difference. The applications which use asymmetric cryptography extensively are few and very far between. Symmetric ciphers have a better foundation in number theory, are more thoroughly cryptanalyzed and are often faster. Most of the time when asymmetric crypto is used, it's only used to negotiate a symmetric key. If it takes RSA a millisecond to encrypt/decrypt a 256-bit Twofish key, what do I care if it takes ECC a microsecond to do the same task?
3. RSA smartcards have existed for years. Check out the iButton for an example of how asymmetric cryptography can be used in smartwear (jewelry, buttons, etc).
Insofar as Schneier's distaste for cracking contests, I've got to say I'm in the same boat. Running a cracking contest doesn't prove anything. It doesn't prove it's secure, brute-force cracking rarely betrays insecurities, and what it's best at is media hype. PHBs the world over look at cracking contests and say "Wow, ECC stood up really well to that distributed attack, I guess it's safe for us to use!", without even once bothering to learn what the theory behind ECC is.
Schneier himself uses contests, so it's disingenuous to suggest he claims contests have no value. Schneier's Blowfish contest offered a cash award to the best cryptanalytic results against Blowfish, regardless of whether or not those results led to a break. That seems to me to be a more healthy way to run contests, although I'm still not entirely sold on the idea.
First, I am a professional information security consultant. Second, no, this is not professional advice; do not rely on it without first verifying.
However, unlike DES, there is no known mathematical loophole
Wrong answer, thank you for playing. DES is one of the most, if not the, most thoroughly-analyzed ciphers of all time. So far, the best way to break DES is by a brute force attack. There are some attacks against it which some people use as proof that the NSA put a backdoor in it, but these attacks are extremely esoteric -- for instance, the key complementation property means you only have to test half the possible keys; this reduces the difficulty of some attacks (chosen-plaintext attacks, specifically, although I think Eli Biham has a known-plaintext version) by a factor of 2--meaning the keyspace is only of size 2**55, not 2**56.
The rules for using DES are simple. Don't use weak keys; don't use complementary keys; use it in DESede (aka TripleDES) mode. The resulting ciphersystem is as close to unbreakable as you're likely to ever get. If your system is eventually broken, you can be reasonably certain that the cipher was not the subsystem which suffered the breach.
I trust DESede more than I trust Blowfish, more than I trust IDEA, more than any other symmetric ciphersystem out there.
Interestingly enough, so does Schneier. A few months back at a crypto conference someone in the gallery asked him what the strongest cipher today was. As I recall, his words were "Triple DES. There is no question."
Don't misunderstand what this means. The ECC algorithm was not cracked; an encrypted message was cracked after a ridiculously large amount of computing power was applied to it. Perhaps this means larger key sizes are needed, or smaller windows of using the same key. However, unlike DES, there is no known mathematical loophole; the algorithm has not been shown to be insecure. If there is a loophole, then increasing key size doesn't help; the algorithm is flawed. But in this case, all that's needed is larger key sizes. Arbitrarily large keys allow for encryption that can't be cracked with all the computing horsepower on the planet within the age of the universe.
I'd be more interested in real cryptographic algorithm analysis of the algorithm, but that is not by any means my forte.
-- "Those who cast the votes decide nothing. Those who count the votes decide everything." -Joseph Stalin