Slashdot Mirror
Factoring Breakthrough?
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?"
I read somewhere that the RSA public key algorithm was invented at GCHQ, and kept secret, years before RSA invented it.
Best Slashdot Co
From the referenced post:
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.
Si vis pacem, para bellum
The only thing more annoying than a Libertarian is an (un|mis)informed Libertarian
You are right, and this is a major stumbling block to widespread acceptance of encryption in the civilian world. The military and other organizations with a strong need to keep secrets are used to playing these games, but corporate America just isn't. Current applications aren't flexible enough to plug-and-play cryptography, changing crypto systems often means a complete redeployment of the application, or worse yet a new application.
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.
Si vis pacem, para bellum
The only thing more annoying than a Libertarian is an (un|mis)informed Libertarian
From the government? I think you were kidding yourself when you thought it was secure in the first place. I find it easy to believe that the NSA is far ahead of the public in the encryption arms-race.
/. The alphabet soup agencies spend millions of dollars and hire the most brilliant minds in the world (not just the US), and their whole existance is based on the premise that they need to be able to find out what every human on earth is doing at any point in time.
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.
Do you have Linux and a DotPal? Click here now!
Remember what happened with DES. The NSA said "make these changes. We can't tell you why." IBM made the changes.
20 years later, when differential cryptography was "discovered", it turned out those changes made it more resistant to differential cryptography...
This isn't really a big deal, nor is it surprising.
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!
Tarsnap: Online backups for the truly paranoid
Well, to answer my own question, on Freshmeat there appear to be one or two.
Have fun!
299,792,458 m/s...not just a good idea, its the law!
Galileo: "The Earth revolves around the Sun!"
Score: -1 100% Flamebait
Ok, I'm paraphrasing stuff I previously read on /.
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.
For the first time I know of, the NSA is actually the good guys in a Slashdot post.
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
A friend of mine worked for Cray Computer Corporation until the untimely death of Seymour Cray. The last machine they were working on was a monster, that might make more sense in terms of today's developments.
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
I love Mondays. On a Monday, anything is possible.
This is about a threefold increase in factoring speed.. not an order of magnitude.
... to find out.
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.
The Future of Human Evolution: Autonomy