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.
Just because brute-force is an inelegant method of breaking encryption doesn't mean it isn't valid.
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.
The site is slashdotted already, but I think you're right. Nothing to see here. Move along, folks.
Patrick Doyle
I mod down every jackass who puts his moderation policy in his sig. Oh, wait a sec....
The information that was "secure" isn't anymore. So regardless of how they broke it, it was broken. Brute-force is one of many ways. As the following threads will surely show. :)
Yes, but it means it will take just as long to break another code. It's not like they found some magical universal scheme for decoding any key.
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.
What about their 163-bit encryption makes it harder to brute force than any lesser bit encryption? Why is is "impossible" to break whereas the 109-bit encryption is only difficult?
Encryption is not a permanent thing; encrypted data is *always* vulnerable after a time. The question is how long the data is protected for, and this is a functino of time. Either an elegant method will be revealed, or a system (software and/or hardware) will be powerful enough to break it using a brute-force method. Note that for the brute-force method to matter, it has to be within a given time frame. (e.g. decoding a VISA number sent over the web within microseconds is useful; within days it is not)
cheers,
Andrew
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.
64-bit computing with very large RAM (and possibly bandwidth) becomes as commom as the current PC configurations, IMHO
C|N>K
(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.
With a brute-force break, it takes the same amount of time to break one key that it takes to break any other.
Not strictly true. It is possible that a brute-force attack will hit upon the right key at its first attempt. Or indeed, not until the last possible key in all of the keyspace. On average, though, the correct key will be found 0.5 way through the keyspace search.
Call me old fashioned, but I like a dump to be as memorable as it is devastating - Bender
Furthermore, the article doesn't say how much of the total keyspace was searched (I'm assuming it was a simple exhaustive search algorithm). The time to search 50% of the keyspace, and 100% of the keyspace (corresponding to average and max time to "break" another 109 key, at the same average key checking rate) would be very useful to know.
But yes, this isn't breaking the algorithm, by any means. In fact, the contest is meant to show how infeasible a brute-force attack is against larger key sizes.
"It's overkill, of course. But you can never have too much overkill." - Anonymous Slashdot Coward
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.
As brute force will open it, even if that means making every possible shaped key or just the mundane big enough hammer.
There are places where the networks are not touching,and there are places where they are-Boeing's Lori Gunter
Time complexity? What the hell is that? Hint: Brute-forcing most encryption schemes is O(2^n), where n is the length of the key. Brute forcing encryption is not sorting.
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.
A little math is a dangerous thing. You've confused yourself completely unnecessarily. He is correct that if Moore's Law were to hold up, then it would take 81 years for computing power to get 2^54 as fast as it is now. Thus in 81 years, we would expect to be able to brute force a key with 54 more bits than one that we can brute force in an equal amount of time now.
I have a question about brute-force attacks on encryption: How do you know when you've found the right key? Suppose I encrypted my data twice. A brute-force attacker could test *every* possible key (to the outer encryption) and get trash every time.
It's a language from Kenya that you have never heard of.
It worked on you just as well as Navahoe worked on the Japanese in WWII.
As long as you cannot get a chance to torture a Kenyan into giving you a language training course this code will continue to be effective against you
At least until bablefish adds Luo as an option.
Just change keys every three years and you'll be fine.
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.
Hence, if it doubles in 261 days, that is indeed below the time specified in Moore's law.
What's your point?