Slashdot Mirror
Weak Elliptic Curve Cryptography Brute-Forced
thegrommit writes "It seems one implementation of elliptic curve cryptography has been broken. It took four years to break a 109 bit key, but the contest sponsors (who provide encryption products for Cisco, Nortel and Palm among others) believe it's still impossible to break their 163 bit keys. The real question is, for how long?" Update: 11/07 01:59 GMT by T : Dan Kaminsky wrote to point out that the key here was really brute forced, and not broken -- that is, no fundamental flaw was discovered in the algorithm.
4 years for the 109 bit version (and that's with a massive, dedicated attack).... I'm willing to believe (barring some unknown theoretical advance, which is always something you have to worry about with all real-world usable cryptography) that the 163 bit keys are good enough for my data considering the exponential difficulty in attacking the longer keys.
Impossible seems like a pretty weird word to ever use in this sort of situation. "Very, very difficult" or "requiring technology or techniques in advance of what is presently available" might be more accurate.
Every year during my review, I just pray the words "slashdot.org" aren't mentioned.
There is no such thing as a crypto key that is impossibile to crack. What it comes down to is how improbably it is to crack it. In this example, it took 10,000 computers 549 days to crack it and it's only 109 bits. At 163 bits, that's a doubling in difficulty for ever additional bit.
Just add a bit, and suddenly you've pushed off the efficiencies gained by moore's law for another 18 months. By going to 163 bits, you've got a good 80 years before the that key can be broken in the same time as this 109 bit key. Frankly I wouldn't be too worried about that problem.
As long as your crypto is good enough to make it too expensive to crack for those who might want to crack it, you've got no worries. And I don't see a lot of people out there able to throw together the 10K computers to crack a key who also don't mind wasting almost two years on the effort.
This sig has been temporarily disconnected or is no longer in service
The time is the most significant factor here. If this was military use, the 500+ days it took to break wouldn't worry anyone since any message more than a few days/hours old is pretty much worthless. If someone where more concerned about long term security, they could setup a system to refresh the keys on any encrypted data, say every year or every quarter.
Cryptography is (and I assume will likely always be) an arms race of sorts... You create a new cryptographic cypher and instantly there are people out there whom are willing (some for the potential prize money, most simply for the pleasure) to spend a great deal of time and effort to crack the encryption. The advent of quantium computers however is an interesting problem for cryptographers, as a cypher that now takes years to break will only take seconds/minutes with a quantium computer, once again the arms race is on, and I don't beleve that one side will ever prevail as the absolute end-all solution. As computers get more powerful and people become more savvy there will always be a new way to encrypt data, and a new way to break the encryption. As for me? I enjoy it, and I hope you do too!
'Breaking' is a term of art in cryptography. It means finding a solution that requires less time than a brute-force search. Even a 1% improvement qualifies as a 'break', although it might not have any practical value.
It's a valid distinction to make, since a flawed algorithm may be unsafe at any key length.
A customer service representative will be with me shortly.
(or unfeasible to be exact) The study of elliptic curves - as a branch of mathematics is not very old one. And as Elliptic Curve Cryptography originates from this theory .... I think this is one of the main reasons why it has not yet been commonly approved for mission critical tasks. Currently, yes, we do know that it is pretty(very) strong against brute-force attacks - but there is still a significant chance that a fundamenta flaws or new discoveries are achieved in ECC theory - leading to easy compromise of previous implementations based on it.
More precisely, they broke a single key, not "weak elliptic curve cryptography". Breaking another 109-bit key (one that had been used to encrypt something, for example) would take another 4 years.
Elliptic encryption is not broken. FEE is still secure, as are all the other well-implemented versions of the encryption out there (unless the NSA has some big news they're not telling us...). Geez.
/. claims the algorithm is broken.
What happened is they brute-forced a 109-bit key. That's a small key. The minimum used in this company's product is 163 bits. While I wouldn't call this "impossible," it certainly is computationally secure for several years, and that's the minimum size.
When distributed.net cracked the 64-bit RC4 key, you didn't hear anyone saying "Oh no! OFB stream ciphers are broken!" That's about what this article amounts to: they brute-forced a small key, and
I hereby place the above post in the public domain.
Encrypt your data using a key large enough in proportion to the length of time it will take to brute force if someone started today with a supercomputer. Essentially it takes X amount of time to check if a key is valid multiply that by number of combinations and you have a rough guess. So if you want something to be safe for a longer period of time (assuming no fundamental weakness is found in the algorithm), then encrypt it with a larger key - every bit doubles the probable time to break it at current cpu speeds. Of course you have to factor in the approximate doubling of cpu speeds every 18 months... but all that really means is that if we add a bit to the key length every 18 months going forward it will continue to take just as long to break into newly encrypted data.
The fact remains that most people don't have anything that needs to be kept 'secret' for a long time anyway. Credit card numbers for online purchases? Those expire after a couple years and the amount of financial gain is not worth the time/cost to break the code. Given that you still need supercomputer equivalents to brute force this encryption it's unlikely that your neighbor is going to be reading your email anytime soon. Even at 109-bit.