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?"
Try viewing the postscript file using the online viewer here instead.
/cj
The NSA factors numbers, and their work is top-secret. When I read stories like this, I wonder if people are just discovering things that the NSA has known about for years. If the NSA could factor 2 Kbit keys, would they tell people? Probably not.
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.
God is real unless declared integer
Shouldn't we all hang on until crypto experts validate this? Is it theoretical? How much does the attack cost? etc. etc.
I wouldn't start sending those revocation certificates just yet.
e4 e5
Using 128 bits is fine for symmetric key algorithms like IDEAS and Blowfish. It's not ok for public/private key algorithms like RSA. You're comparing Apples to Oranges.
The 128 bits Netscape uses are for a symetric key. It takes considerably less bits for a symetric key to be secure, than an asymetric key. (I forget the equivalency, but ISTR that 128 bits symetric is roughly equivalent of 2048 bits asymetric.) ...
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.
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.
None at all when considered by itself. AES (ala Rijndael) does not depend upon prime numbers. Hence, it is not subject to factoring. It is a symmetric cipher with key lengths up to 256 bits.
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
Only a threefold increase in speed? That would make hardly any difference, you'd get a threefold speed increase just by waiting a few years for Moore's law to deliver.
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.
-- Ed Avis ed@membled.com
Is he going to pay someone $5000 if they can prove him wrong? (qmail joke)
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
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. ;-)
AES is secure, as is DES, as is almost any other symmetric cryptographic protocol. AES, for instance, is based on Galois Fields (and associated chicanery), whereas DES is based on drop-dead simple permutations that are so elegant and inexpensive that I find it difficult to resist *not* implementing them on an 8-bit PIC (although someone else has of course beaten me to the punch!). Neither one is reducible to anything like factoring.
;). However, don't make the switch to DH just yet -- IIRC, the ciphertext is effectively doubled in length (over RSA). So you can either make a bigger RSA, or you can make a bigger message every time you encrypt -- either way, you email just got longer :)
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
- undoware.ca
.deen uoy noitpyrcne eht all is sihT
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...
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.
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