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.

Comments

Elliptical Encryption

[jonathanclark]

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.

Corrections

[rjh]

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.

DES has no such loophole

[rjh]

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."

Not cryptographically weak....

[Noer]

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.