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.
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.
Actually, this just validates ECC, as it was fully expected that the 108-bit challenge was feasible (ie. could be broken in reasonable time with massive computing power). The linked site seems to indicate it took about 5 months (searching about 76% of the problem space), which is roughly what the challenge issuers anticipated.
The 97-bit challenge was broken (by the same project) in a couple of months, also in line w/ prediction.
The next challenge is 131 bits, which should take a LOT more time and power to break. The challengers can use these results to justify their claim that the 161+ bit challenges are infeasible.
FWIW, people in the field believe a 160 bit ECC problem to be roughly equivalent to 1024 bits of RSA, which is currently WAY beyond what can be feasibly attacked (barring no advances in factoring technology)
ECC has a bright future and these challenges only serve to emphasize that point.
See the link on the Certicom ECC challenge for more info.
"It's overkill, of course. But you can never have too much overkill." - Anonymous Slashdot Coward
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