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.

Comments

Apple and FEE

[wizbit]

Apple made use of NeXT's Fast Elliptical Encryption in their "personal security" element of OS 9, allowing basically any document to be encrypted and decrypted by the OS. Apparently they planned this for OS X as well, but I see no mention of it except as a future feature on their scientific papers page. I wonder if this will force them to reconsider such a relatively insecure approach to OS security?

"How long" is the question...

[Da VinMan]

...because no system is uncrackable or unbreakable, given enough time. The question isn't "will anyone ever be able to see my data?". The question a user should ask "how long would it take someone to get into my data and will it matter if they finally do get into it?".

Purists will argue against that idea, but I am being realistic here.

Security for the Masses

[Oculus Habent]

It's interesting to see graphs of cracking power.

RC5 took almost 5 years to crack, but take look at the graph. At the beginning of 1998 there were about 15 GigaKeys/sec. Then look at the increase.

Sure, a fair portion of the increase was also the addition of new computers, but 261 days to double is comfortably below Moore's Law. If the whole project had run continuously at 200 GigaKeys/sec, it would have taken under 2.5 years, and under two years at their reported peak rate of 270 GigaKeys/sec.

So, if we follow the 261 day doubling statistic they had, all these encryption methods seem weaker than reported. The big issue is if it's 4 years now, it's 1 year soon, and 3 months, soon after.

If the cracking power scales nearly linearly, shouldn't we make some projections on how fast we can crack this encryption in a year? In two years?

If your data is very time sensitive, then most "strong" encryptions currently available will do. If your data is, however, of a continuously sensitive nature (some corporate or government info), maybe you should be looking at the 1000+ bit keys now.

Assumptions assumptions!

[bugnuts]

It may be computationally infeasable, but that claim is made using certain assumptions which may be wrong.

An example of such an assumption is that it takes n log(n) time to sort a list of n elements, using the best sort possible. The proof of this is based on the compare statement. However, there are sorts that work in O(n) time, not O(n log(n)) such as a radix sort which does not use the comparison operator (a/k/a "if-then-else").

The assumptions made are that brute-force is the only way to break this code.

I don't know of any attacks on elliptic curve crypto, when implemented correctly. That doesn't mean they don't exist using different assumptions, different number systems, or different computer hardware. (Quantum computing looks very promising to destroy our complacent attitude toward "computationally infeasable" problems.)

Here's an idea:

[Anonymous Coward]

So now we know distributed efforts can solve great big math problems. Don't get me wrong, that's good to know and all, but.. aren't there any math problems that would be of more use than giving people with 210 IQs something else to bicker over during Star Trek conventions? Really, I'm an engineer, and sometimes I actually have to use math to do things like MAKE A FRIGGIN CAR OR SOMETHING.

There are plenty of nontrivial engineering problems out there, especially when you take a trip into thermodynamics and fluid flow. Let's solve those. Or sequence the human genome to grow an extra arm or something. Or better yet, let's put the computing power of mankind to work to randomly generate a script for Episode 3 that won't make us want to beat Lucas senseless with our plastic lightsabers. Why can people scrape together all these prizes for pointless pseudo-intellectual drivel but nobody can get some money behind something worthwhile, or at least interesting?

Here's an idea: Instead of using distributed computing for all this junk science, let's start a central distributed network. This network would have a basic interface element for all the major OS configurations, and would be able to update from the web with whatever mathematic formula and trial space it was supposed to run at a given time. Everyone everywhere could download the client, and set it up to run with whatever processor load they wanted, update on a schedule, maybe vary processor load on a schedule so it works extra hard when you're not using the system. Not much of an interface really. Then some organization, say the NSF or better yet an international science conglomerate, could alot portions of the system load to projects they deemed worthy, depending on complexity and value. The cost is basically nothing, in fact since you could get somebody on the planet to write the code for free one weekend, and the bandwidth would likely be rather low, you would most likely not be talking about the cost of funding a minor research project. Users could still run other distributed clients if they wanted, and the system would be completely voluntary. But it would attract a lot of attention and users, do some good for mankind, and direct our computing power in positive directions.

Think of EMP shielding

[gelfling]

Back in the day when we worked on EMP shielding, no matter the elegance of the solution it all came down to raw force. If you wanted to shield to 100 MEV then all your opponent has to do is create 110 MEV. *Poof*

"Give me a big enough hammer and a place to stand and I can break practically anything"

-Archimediocrates

Re:Weak Elliptic Curve Cryptography Broken

[Dunark]

"...assuming the algorithm is known...". Isn't this a great weakness of all codebreaking efforts? I think another weakness is the need for a quick way to recognize properly-decoded data. It doesn't matter how fast you can do test decryptions with candidate keys if you don't have a near-equally-fast way to test the results and recognize a success. If you have no idea what the decrypted data is supposed to look like, you're pretty much screwed.

What are the trade offs of adding bits

[thistle]

I don't know much about encryption and am curious to know why we don't just choose some arbitrarily high key-length like 500 bits. What is the rational for slowly increasing key size every year? Is there some kind of computational limitation that makes longer lengths undesirable?

Re:secure enough

[FasterThanLight]

Moore's Law looks like its going to hold for the forseable future (still), so it wont be long before the 109 bit version becomes trivial and the 163 bit is doable in a reasonable time frame

Depends what you call a reasonable time frame- Moore's law predicts a doubling every 18 months, and if the same brute-force code-guessing techniques are used to "break" the encryption it will be awhile. 109! is a much smaller number than 163!(!), and IMMIC(If My Math Is Correct), there are ~2 x 10^114 more bit combinations in 163 factorial than in 109 factorial...