Factoring Breakthrough? 492
An anonymous reader sent in: "In this post to the Cryptography Mailing List, someone who knows more about math than I do claimed "effectively all PGP RSA keys shorter than 2k bits are insecure, and the 2kbit keys are not nearly as secure as we thought they were." Apparently Dan Bernstein of qmail fame figured out how to factor integers faster on the same cost hardware. Should we be revoking our keys and creating larger ones? Is this "the biggest
news in crypto in the last decade," as the original poster claims, or only ginger-scale big?"
Known about for years (Score:4, Interesting)
Really Unique Crypto (Score:1, Interesting)
Re:Were they even secure yesterday? (Score:4, Interesting)
Note that there have been rumors of an RSA cracker built by a
three-letter agency in custom silicon before this, but until
analyzing Bernstein's paper I had always dismissed them as
ridiculous paranoid fantasies. Now it looks like such a device
is entirely feasible and, in fact, likely.
There has always been speculation that the NSA could break RSA, but it was dissmised as paranoid by most "in the know." Most of the mathematicians didn't believe that they were that much ahead of the rest of us. Now that this technique is known it explains how the spooks may be able to break crypto everyone else believed was "unbreakable" if they had previously made this discovery.
Re:not surprising... (Score:4, Interesting)
Imagine the conversation with the CIO when you tell him he has to throw out his 1 year old meesaging platform because some guy figured out how to factor very large numbers effeciently and your current platform doesn't support eliptical curve cryptography.
Re:Were they even secure yesterday? (Score:5, Interesting)
Exactly! One of the most lucid posts I have ever seen on
I have never thought that I could put one by the government, and I have never encrypted my documents because I was worried that some spook might read it. If they want my password, credit card number or DNA bad enough, they're going to get it no matter what I do. I encrypt my data because I'm more worried about script kiddies and regular old fashioned crooks.
Re:Were they even secure yesterday? (Score:5, Interesting)
20 years later, when differential cryptography was "discovered", it turned out those changes made it more resistant to differential cryptography...
Re:OMFG (Score:1, Interesting)
Speaking as a computing DPhil... (Score:5, Interesting)
Basically, what DJB has done is translated the GNFS from its normal implementation on serial computers (where there is a great deal of available memory, but only one operation is performed at once) into a parallel implementation, where the number of processors more closely matches the available memory.
The "decreased cost" is misleading here, since it is calculated on the assumption that sieving would have been done by a single processor with access to a huge memory... this quite simply was never the case.
There is nothing here to suggest that factoring can be performed using any fewer FLOPS; all that is demonstrated is that by using several processors, each with a smaller memory, you can do better than with a single processor and a giant memory. Which we already knew.
To summarize: DON'T PANIC!
Re:Quamtum Computing (Score:1, Interesting)
Qubits have randomness inherent within themselves which is why Quantum computers are so damn hard to build. But for the cryptographer, this randomness is the literal *Holy Grail* of cryptography -- the one time pad.
By using a stream of qubits passing through filters to detect the spin of the bit two people can establish a TRULY RANDOM one time pad. Better yet, the instability of the qubits also makes it mathematically impossible for a third party to eavsedrop without affecting the transmission stream? The checks in the alhorithm verify this. Simon Singh's book "The Code Breakers" analyizes the algorithm in sufficient detail.
So don't worry about the advent of quantum computers. Relish in the thought they bring truly secure communications along with their ability to make obselete all current forms of cryptography.
In short -- technological progress as usual. Film at 11.
Over-estimate (Score:1, Interesting)
http://cypherpunks.venona.com/date/1994/01/msg0
dnetc (Score:2, Interesting)
There are alternatives (Score:4, Interesting)
Well, to answer my own question, on Freshmeat there appear to be one [freshmeat.net] or two [freshmeat.net].
Have fun!
299,792,458 m/s...not just a good idea, its the law!
You naive fool (Score:1, Interesting)
Taher Elgamal, who wrote Netscape's so called "data-recovery plan" as demanded by the spooks, said they didn't have a choice. Exports are about half the income for these businesses. In practice companies need NSA's permission to export security products, except for "export grade" junk. NSA only gives permission if the security is crippled in some way.
Duncan Campbell reported in Interception Capabilities 2000 that NSA succeeded in compromising browsers from both Microsoft and Netscape, as well as Lotus Notes. The browsers' security was openly gutted by NSA's insistence on reducing key sizes to whatever the NSA can easily crack at the time. In the case of Lotus Notes the keys appeared to be longer, but just enough of each key was secretly given to the NSA.
According to Network World the NSA "forced MasterCard International, Inc. to dumb down the Secure Electronic Transaction (SET) credit-card encryption standard." NSA insisted that most of every transaction not be encrypted at all. When someone steals a lot of money using SET we'll know why.
Sabotaging friends and foes isn't new for the NSA. It's life long behavior. In Crypto AG: The NSA's Trojan Whore you'll find the intriguing but very disturbing story of how 50 years ago NSA rigged the crypto systems sold by Crypto AG so that NSA could read the supposedly secret messages. Customers of Crypto AG include embassies, military, banks, and rogue nations such as the Vatican. "
I pasted that selection from this Cryptome article. [cryptome.org] Secure from who? It is probably hard to crack for private persons, but the NSA apparently can crack it since they force companies to install backdoors. If you search around Cryptome you will learn that the NSA forces companies to use crypto that is weaker than most companies want to use, so that it is easier for them to crack.
Who cares (Score:3, Interesting)
Re:Were they even secure yesterday? (Score:5, Interesting)
Which, of course, means that this is the absolute truth, so please repeat it as such.
DES has a large space of possible keys to use. At some point in time (I don't know that it was 20 years prior to the general knowledge about differential cryptography, but it was numerous years prior at lest) the NSA quietly told everyone that a certain portion of that keyspace should not be used. Ever. They didn't say why. They just said that it shouldn't be used for secure applications.
Eventually someone discovered differential crypto. It revealed that the keyspace that the NSA said not to use for DES was very, very weak and could be cracked rather trivally. The rest of the keyspace was still secure though (within the scope of the original security on DES at least).
What he's saying is that the NSA knew about this a long, long time before anyone else had figured out why. It is not unreasonable to believe that they've figured out other "magic" to make crypto either harder or easier to crack, despite claims otherwise.
The NSA exists to protect US national secrets. Crypto is their business. Knowing how to crack crypto tells you how safe your own crypto is. They have a very large, very undisclosed budget. Contrary to popular belief, not everyone in the government is incompetent. You may put together your own conclusions from there. Please wait in line for your aluminum foil beanie though.
Re:Were they even secure yesterday? (Score:4, Interesting)
The NSA recommended changes to DES that made it a better, less crackable, scheme. Years later, when a new type of code breaking was publicly discovered, people looked back and noticed the changes the NSA had made were directly influenced by this "new" type of code breaking. The bottom line is that the NSA is, and always has been, leaps and bounds ahead of all non-classified "state of the art" cryptography.
Could the original poster give a link? I would love to read the story.
-B
Re:It was used to ... (Score:2, Interesting)
NSA-sponsored Cray 4 development now makes sense. (Score:5, Interesting)
In the early nineties, CCC was working on the Cray 3, a new gallium arsenide computer. It was to have a cycle time of about 1ns (shockingly fast back then.) It was cooled by a high-pressure very high-speed mist of Flourinert suspended in helium. It was built as a series of wedges much like the Cray 1 and 2, although somewhat smaller. They built working prototype wedges, and were debugging them, while looking over their collective shoulders at the ground being gained on them by arrays of microprocessors.
One thing led to another, and it was clear that the Cray 3 would never be a commercial success. They were then given a contract to build what was called the Cray 4. The Cray 4 was a one-off machine using PIM (processor in memory) chips. These were 1-bit computers, but there were 262,144 of them in the box. The idea was that the gallium arsenide chips, wiring, and cooling system that made up the Cray 3 were just the networking system for these PIM chips, which would do the actual work.
Anyway, Cray died, and then CCC quickly died, and I don't believe that the machine was ever finished.
thad
Re:AES? (Score:2, Interesting)
Diffie-Helman is not based on the knapsack problem (which is roughly: given a bunch of sack of various sizes (say, all of size 100) and a bunch of objects, what's the most efficient way of packing the objects into the (least number of) sacks?); DH is based on the discrete logarithm.
Note: people are interested in the knapsack problem because it is NP-complete to solve in general; the problem is that many (many!) specific cases are very easy to crack, and it's hard to tell a priori if you are generating such an example (a similar thing occurs in factor, in that there are some numbers that are much easier to factor than they may appear).
The discrete logarithm is as follow: recall that computing the logarithm (base b=10, say) of a number n is determining a number a such that 10^a=n. If you're working over the real numbers, this is easy to solve, and any calculator can do it quickly. On the other hand, suppose you are working in the integers modulo a prime p (imagine you're on a clock with p hours); then it's still possible to raise an integer b to a power a, getting a number n, and this is very quick. Say, given p=7 and b=5, and a=4, we get that 5^4 = 25*25 = 4*4 = 2 (modulo 7), so the discrete log base 5 mod 7 of 2 is 4. This is what Diffie-Helman relies on. Note that there are variants that work in different groups than this (a group is a mathematical object where you can add and subtract, roughly), particularly with elliptic curves, and these last are much touted as being possibly more secure than RSA or DH.
Re:OMFG (Score:5, Interesting)
No. This is wrong. Read the paper.
For large keys, this method reduces the difficulty of factoring keys by a factor of ~3.009, i.e. the diffuclty of factoring a 90,000 byte key is now comparable to factoring a 30,0000 byte key using traditional methods.
It is unknown if this applies to smaller keys currently in widespread use, i.e. if your 2048 key will now have a factorization cost equivelent to that of a 683 byte key using traditional methods. That is what they guy wants funding for
So yes, this makes cracking keys orders of magnitude easier and faster.
Alternatives such as EC may be vulerable as well (Score:3, Interesting)
The methods described in the paper [cr.yp.to] can be used to improve the cost of cracking EC discrete logs as well. The author, in a recent Usenet posting [google.com], points out that the paper's methods are likely to reduce the cost/effort of EC key cracking as well ... perhaps even more than RSA key
factoring.
The paper, combined with other other EC strength [slashdot.org] concerns suggests that EC is not the technology to turn to at the moment.
In other words, if this paper has you concerned about the security of RSA keys by factoring, then you should be even more concerned about the safety of Elliptic Curves as well.
But as others, including the author, have stated (in large friendly letters): DONT PANIC! It is not known if the ideas expressed in the paper are applicable to key sizes that are in common use.
Questions for Those that Understand (Score:3, Interesting)
I'm a person who has quite an interest in crypto and often a good understanding of the base concepts behind crypto systems, but I don't understand much of the math that goes into proofs like this. Thus, I'd like to put some questions out to those who are more experienced than I am.
First, does this work? Have people independently verified that DJB is correct? (I went looking for some peer review via Google and didn't turn up anything that looked conclusive.)
Secondly, what's vulnerable? As I understand it, what DJB has discovered is a more efficient method of factoring numbers (on custom hardware) such that keys three times longer can be factored in roughly the same time. RSA is based on the product of two relatively prime numbers, so it's vulnerable. Aren't most public key systems based on this principle, though? How vulnerable is, for example, DSA to this new factoring technique?
--Phil (This article went up yesterday; hope someone's still around to read my post...)