Slashdot Log In
Factoring Breakthrough?
Posted by
michael
on Tue Feb 26, 2002 12:10 PM
from the for-as-long-as-men-are-capable-of-evil dept.
from the for-as-long-as-men-are-capable-of-evil dept.
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?"
This discussion has been archived.
No new comments can be posted.
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
For the PostScript-impaired (Score:5, Informative)
Re:For the PostScript-impaired (Score:4, Informative)
Now let's see how well RR's server can handle the
Parent
Re:For the PostScript-impaired (Score:5, Informative)
Parent
not surprising... (Score:4, Insightful)
Does anybody have good sources about this? Ones based on historical encryption and decryption that lead into modern times would be ideal.
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.
Parent
This does /not/ break RSA. (Score:4, Informative)
If it
himi
Parent
Re:not surprising... (Score:4, Informative)
Parent
Were they even secure yesterday? (Score:5, Insightful)
So when you ask "Are our keys secure" the logical follow-up question is, "From who?"
From me? Yes. I probably couldn't factor a 1000 digit number.
From your boss? Yes. You could use rot-13 and your boss would probably be baffeled.
From your boss' lawyers? From the police? Here is where we get into the gray area; where the article becomes relevant
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.
Known about for years (Score:4, Interesting)
Parent
Re:Known about for years (Score:4, Informative)
Parent
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.
Parent
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.
Parent
Re:Were they even secure yesterday? (Score:4, Insightful)
What public scrutiny? Do you know what the NSA is doing? Do you thing your drunk, philandering senator knows? Or even cares?
This is a dangerous attitude--whereas a corporation could learn all about you, the worst they'll do with the information is use it to sell you more bric-a-brac, and if you discover that they're invading your privacy, you can at least sue them.
If the government is gathering this data, it can use it to take, with force, everything you own because you smoked a joint in 1963. Plus, if you find out the government is invading your privacy, you can only... well... you can only grease up your sphincter to help with the penetration. And, depending on how you find out what the government is doing, they can shoot you.
Corporations do bad things, but the worst things are done by governments, not corporations. Even the worst things done by corporations are done by the government at the corporations' behest (vis. DMCA).
Parent
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...
Parent
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.
Parent
Re:Were they even secure yesterday? (Score:4, Informative)
The mysterious tweak was not restricting a portion of the keyspace; it was the choice of "S-boxes". In DES, the S-boxes are a set of 8 functions that take 6-bit inputs and return 4-bit outputs. They're not specified algorithmically; the standard just says "S-box 1: 0 -> 14, 1 -> 4..." and so on: eight tables, each of which contains 64 4-bit numbers. The S-boxes are central to DES's security; the only other operations in the cipher are bit shuffles and XOR.
When DES was launched, people noticed pretty quickly that these tables had not been filled randomly; they did not pass randomness tests. But IBM (who designed DES) and the NSA (who approved it) were tight-lipped; not only about their design, but about the whole design of DES. Naturally, people suspected a back door.
When differential cryptanalysis was discovered, it was shown that the S-boxes had been specifically hardened against it, and that this was the souce of the pattern seen. Don Coppersmith of IBM had independently discovered DC, calling it the T-attack (T for "tickle"), and had worked out how to defend DES against it.
However, when Mitsuru Matsui discovered linear cryptanalysis, it was found that DES was not specifically hardened against it, and indeed the best academic attack against DES is a linear attack. Since the NSA approved DES, perhaps they did not know about linear cryptanalysis either.
Of course the real NSA back door was always the 56-bit key, and the best practical attack is still brute-force key search.
Parent
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
Parent
Re:Were they even secure yesterday? (Score:5, Informative)
Biham, Shamir - Differential Analysis of DES-Like Cryptosystems [nec.com].
It contains one of my favourite passages in a crypto paper: "Cryptanalysis of GDES... The special case of q=8 and n=16, which is suggested in [16,18] as a faster and more secure alternative to DES is breakable with just six ciphertexts in a fraction of a second on a personal computer." [and that was a personal computer from 1991 :)].
Parent
Re:Were they even secure yesterday? (Score:4, Insightful)
It supposedly improved DES. But it also implies that the NSA might have knowen about differential cryptoanalysis 20 years before public research discoverd it. The implication is that they might know a lot of other things that are not yet knowen in the public crypto research community. On the other hand, they might only have had a hunch, or there might have been other weaknesses in the old design (they changed the s-boxes, as far as I remember), that they could find and the effect on differential cryptoanalysis is accidental.
But there is also another limiting factor: If they can break, e.g. AES or RSA far easier than the public suspects, they don't want the public to know! After all when it is knowen a cipher is insecure, people will stop using it or improce its security. This is analog to not exposing a highly placed intelligence source.
If you plan a major terrorist attack and use email for the related communication, you might have to worry. Otherwise, as long as you use cipthers that are belived to be secure for the near future by current published research, you should not need to worry.
Parent
Re:Were they even secure yesterday? (Score:4, Informative)
I found a brief mention of it here [execpc.com] in the Differential Cryptanalysis section. Also, in "Applied Cryptography, 2nd ed." (Schneier) [amazon.com] on page 290, it quote IBM's Don Coppersmith as saying:
I've heard about it in other places, but I can't remember where at the moment.
Parent
Re:Were they even secure yesterday? (Score:3, Insightful)
The realistic target is making it cost too much to target you. (Note that cost != money -- the usual government policy in that regard is "spend all you want; we'll tax more". Real costs to governments are man-hours of specially trained personnel, risk of exposure and embarassment, or risk of exposure and loss of ability to use the same trick again.)
Re:OT: Your sig (Score:3, Funny)
Whew - I'm safe (Score:3, Funny)
HTML Version of Paper (Score:4, Informative)
Just wait... (Score:5, Insightful)
I wouldn't start sending those revocation certificates just yet.
Re:Just wait... (Score:5, Funny)
Parent
Don't Panic (Score:5, Informative)
Protecting against the http://cr.yp.to/papers.html#nfscircuit speedup means switching from n-bit keys to f(n)-bit keys. I'd like to emphasize that, at this point, very little is known about the function f. It's clear that f(n) is approximately (3.009...)n for _very large_ sizes n, but I don't know whether f(n) is larger than n for _useful_ sizes n.
Bernstein's paper is excerpted from a grant proposal where he is requesting funds to answer the question of whether the design is applicable to useful key sizes. At this point it is far too early to assume that 1024 to 2048 bit keys can be attacked by his proposed machine more efficiently than with known methods.
Reward (Score:5, Funny)
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:Speaking as a computing DPhil... (Score:5, Informative)
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.
Hold on. A parallel implementation would normally just give an N times speedup. But the Berstein method (reportedly) does much better than that: it reduces the base of the exponential complexity by about a third (in the asymptotic case). This is far more significant than "merely" parallelizing the algorithm.
Parent
I don't care about n-bit encryption (Score:5, Funny)
cr.yp.to mirror (Score:4, Informative)
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!
Who cares (Score:3, 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:4, Insightful)
Parent
Re:AES? (Score:5, Informative)
Many public-key algorithms, and many public-key-based authentication protocols, however, *are* reducible to factoring, even if they don't appear to involve such darkness the first time you read them.AFAIK, for public key algs the deep magic is either factoring or the knapsack problem; however, almost all of the latter kind have been proven insecure. One notable exception of the latter variety is the Diffie-Hellman (sp?) algorithm, which is incidentally also the first public-key alg ever invented, and the underlying muscle behind the NSA's DSA signature scheme (although ElGamal did some strengthening work and got to rename the bugger
Parent
Re:AES? (Score:5, Informative)
Where it could be susceptible, however, is during a key negotiation session (say via Diffie-Hellman Key Exchange) or a naive approach of simply encoding the session key using the recepients RSA key.
Where I would be truly frightened is in the realm of digital signatures where somebody could forge a digital signature simply by knowing the sender's public key and factoring it. With digital signatures almost as legally binding as handwritten signatures, identity theft may increase using these methods.
The resulting impact may be less acceptance of digital signatures and more reliance on antiquated methods.
RD
Parent
Re:No wonder NSA was okay with 128 bit encryption. (Score:5, Insightful)
Parent
Re:Hmm.... (Score:5, Informative)
And the symetric keys netscape uses don't depend on factoring primes to be secure
Although the key exchange that netscape uses to send the session key probably does.
Parent
The trick is to find the shortcut (Score:5, Informative)
So the trick is to find a shortcut or a flaw in the algorithm that allows you to get the data without searching all the keys.
In the case of RSA, the shortcut is factoring the product of two primes. It's way way easier to factor a 128-bit product than it is to search through a 128-bit keyspace. So RSA bumped the size of the product up and up and up until it was as impossibly hard to factor it as it was to search a 128-bit keyspace.
Other algorithms have other shortcuts, too. Remember when a weakness was found in the session key choosing algorithm for Netscape? The keyspace was reduced from 128 bits to 24 bits or something like that, and then a search could be made on it.
Anything you can do to avoid trying all the keys is the name of the game. Unless you're some kind of quantum computer freak. ;-)
Parent
Yes, key exchange is asymmetric. (Score:3, Informative)
The real reason a symmetric algorithm is used for the bulk of an SSL session is that it is much less computationally intensive than an asymmetric algorithm with a similar degree of security.
Note that these algorithms are independently pluggable, so a more secure or larger key size asymmetric algorithm could be used alongside the same old 128 bit RC4.
The big problem here is for systems using browser managed certificates for authentication would have to be upgraded and new certs issued. This is not the most common usage of SSL, but where it is in place the systems tend to be large and expensive.
Re:Hmm.... (Score:4, Funny)
to be secure
Good, because here's a script I wrote that factors any prime number in constant time:
#/usr/local/bin/perl5 -w
print "Please enter a prime number";
chomp($prime = <STDIN>)
print "The factors of $prime are $prime and 1";
exit(0);
Of course, you really DO need to input a prime for it to work.
Parent
Re:it's a cool method (Score:5, Insightful)
My understanding is that keys of three times the length can be cracked in about the same time - which is an _exponential_ increase in speed.
Parent
Re:it's a cool method (Score:4, Insightful)
Exactly. That means we have to make N three times as large as we thought we had to. This is not a catastrophe, except in high-security applications. But these should use something like "make absolute sure its enough bits and then quadruple the number" anyway...
Parent
Re:OMFG (Score:5, Informative)
Suppose I have a 1024-bit key. The new algorithm makes it essentially take the same time to break as a 341-bit key using the old algorithm.
Since each bit makes it take twice as long, this means that the new algorithm is 2^683 times faster at cracking the code. This is a bit different than 3 times...
Parent
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.
Parent
Re:NSA, et. al. (Score:5, Insightful)
For the past 50 years, that's been the case.
> I suppose this very well could be the case, but it sure lends itself to great conspiracy theories.
For the past 50 years, that's also been the case ;-)
Most of us older /.ers grew up believing that the mods to the S-boxes in DES were probably backdoors. Turns out they were to secure the algorithm against differential cryptanalysis, which didn't get discovered outside of NSA until recently.
NSA is still reputed to be the largest employer of mathematicians on the planet. They're reputed to have more supercomputing power than any organization on the planet. Both allegations are reasonably well-substantiated.
> I suppose the TLA agencies don't really need strong crypto to invade on my privacy. They just need a court order.
Correct. NSA's got two missions - secure American computing and communications, and 0wn every one else's ;-)
Not only is it easier to get a court order to make you give up your keys (or to eavesdrop/keylog you while you enter them), it's a hell of a lot safer.
The funniest part of Cryptonomicon is where the Brits are busy sending bombers to "see" German shipping but not bomb it. (If they just bombed the Germans, the Germans would realize that their crypto had been broken.) One of the protagonist's jobs, as an information theorist, was to figure out just how often they could get away with "just bombing them" and how often they had to make it look like they "got lucky" with a chance overflight or other observation.
The hardest part of crypto isn't breaking your opponent's codes, nor is it securing your own secrets. It's securing the big secret, namely not acting in a way that proves you've broken your opponent's codes.
Knowing your enemy's "A" team plans to attack tomorrow at dawn is good, but if you take out the "A" team 5 minutes before dawn, you run the risk of losing your ability to monitor the "B" team.
Parent
Re:NSA, et. al. (Score:4, Informative)
They no longer need it if you are suspected of any "terrorist activities". whatever that means.
"The US can't force you to give up your encryption keys "
See above and see Patriot Act and Homeland Security Act. They can force you if its for the good of the state, oops, I mean if its for the "security" of the state.
Parent
Re:1.5 bits lost? - not quite (Score:3, Informative)
"This reduction of total cost from L^(2.852...+o(1)) to L^(1.976...+o(1) means that a ((3.009...+o(1))d)-digit factorization with the new machine has the same cost as a d-digit factorization with previous machines."
In plain terms: A factorization of a number that has 3 times as many digits will have the same cost as a the number did before.
Hope this clarifies why this is a breakthrough (that may be important).