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
http://cr.yp.to/papers.html
Raised by monkeys.
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.
Correct, it was invented in 1973 by Ellis, Cocks and Williamson at GCHQ.
Athletic Scholarships to universities make as much sense as academic scholarships to sports teams.
The paper talks about constructing a computer optimized for factoring large numbers. Part of the RSA public key is the product of two large prime numbers. If you can factor that, you can get the private key, and then do whatever.
AES is a symmetric key algorithm -- the same key is used for both encrypting and decrypting. Factoring numbers has nothing to do with any part of the algorithm, so this has no impact at all.
That said, most of the stuff encrypted these days with AES uses a public key algorithm to send along the AES key. If the public key is broken, then out pops the AES key and the message is cracked. So, just because you're using AES doesn't mean you are safe. You have to ask if there is any public key key exchange, and if so, what it is. El-gamal, DSA, Diffie-Hellman are OK, RSA is just weaker than we thought it was.
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
Actually that was a university experiment (MIT maybe?) on actual random number generation. The images from the lava lamp were used as the random number seed, since apparently the lamp is the easiest way to observe "true" randomness.
Silicon Graphics took this farther and made a sellable package of this called lavarand. Check out this article for more.
Comparing apples and oranges. 128 is a symmetric key length, where every bit in the key is (potentially) a bit of entropy in the key space. 2048 bit keys are public keys, where not every number less than 2^2048 can be used as a key.
You could view this post script file online here, or you could use the Windows, OS/2 or Linux viewers available here.
Every rule has an exception, and this is the only rule with no exceptions! Huh? -- Spatch
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. ;-)
Rather, it effectively reduces the bit strength by a factor of a bit more than three for large keys. The author is not sure if the factor of three holds for the size of keys currently in use.
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
Read the book The Code Book by Simon Singh. It's a fantastic mix of technical cryptography and historical perspectives.
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...
But then again, quantum cryptography may be even closer than working quantum computers, which means secure private key cryptography, meaning you can factor all you want, you aren't gonna find anything unless you get that private key.
You are just kidding yourself. There are many ways to get info, *without* the bother of breaking the encryption and RSA never was secure. The fact that the government allows it is sufficient proof of its insecurity...
See also my Australian mirror at: http://www.glasswings.com.au/cr.yp.to/papers.html# nfscircuit
Share and enjoy,
*** Xanni ***
http://www.glasswings.com/
"(NSA, CIA) have no authority to get a court order
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.
Operator, give me the number for 911!
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.
Or more correctly, the new algorithm operates in the cube-root of the time of the original. (I'm pretty sure factoring is still an exponential search problem. Would someone who knows this algo better than I comment?)
At any rate, it's not quite as impressive as if an exponential search had been made polynomial. Rather, the exponent in the exponential search's runtime has been divided by 3. (Still a very big deal.)
In terms of big-Oh, it went from O(x^N) to O(x^(N/3)).
--JoeProgram Intellivision!
Um, a 512-bit key was cracked a few years ago:3 0.shtm l
http://slashdot.org/articles/99/08/29/02132
No, someone has been spreading around an erroneous interpretation of the paper. From the abstract:
"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).
Well i couldn't get to the original site, but i see that NEC's citeseer has it.
please learn the difference between symmetrical and asymmetrical encryption
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.
The evaluation of an action as 'practical' . . . depends on what it is that one wishes to practice.
I found a brief mention of it here in the Differential Cryptanalysis section. Also, in "Applied Cryptography, 2nd ed." (Schneier) 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.
"One man can change the world with a bullet in the right place."
- Mick Travis, "If..."
Wrong... in 1999, a group in Australia factored the RSA-140 challenge (140 decimal digits). This effort took roughly 3 months of calendar time using roughtly 300 computers (300MHz PC's and slower megahertz wise suns/sgi) for the seiving portion (parallizable) and then 1 cray (don't know specs) for the final step (which took less that 1 month). The RSA-155 challenge (512 bits) is estimated to only be 7.2 times harder CPU wise (versus the 1024 bit one, which is estimated at 40 million times harder). If I understand how this enhancement works, the algorithm is still not polynomial, but it should cut down the growth from 140 digits to 155 digits.
The NSA exists to protect US national secrets.
and to perform industrial espionage on behalf of US corporations.
"The new wave is not value-added; it's garbage-subtracted" - Esther Dyson, Dec 1994
If the only way to factor a number was trial division then you would be correct. However the modern algorythms for factoring are much better than that, perhaps you are confusing symetric cryptography such as DES or AES with RSA.
I am unable to find a table online but in 83 a cray factored a 71 digit number in 0.1 Mips-year (1 million instructions per second for 1 year) Since the numbers are talking about are much smaller (50 digits vs 71 digits) and cpu's are much faster (> 1 billion ips) it would not be unresonable that a 50 digit prime could be factored in a few hours on a machine with suffecient memory.
Biham, Shamir - Differential Analysis of DES-Like Cryptosystems.
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 :)].
-- Help Digitise the Public Domain at DP.
This is wrong on several levels.
1. RSA's security comes from the inability to find the e'th root modulo a composite. Its *conjectured* to be as secure as factoring is hard but thats not what the security comes from. The security comes from the inability to find the decryption function from the encryption function.
2. Current factoring algorithms take via the GNFS
e^(1.923 * (ln(n)^1/3 * ln(ln(n))^2/3))
Time not n^3 time as you suggest.
Finally, the new result appears to just be a more efficient implementation of the GNFS, its not a new algorithm.
Given all that the new results certainly are worth taking a look at.
Tom
Someday, I'll have a real sig.
I don't know about the rest of the Three Letter Agencies, but the most important of them for this topic will only hire Americans.
From the NSA's employment FAQ,
The most brilliant minds outside of the US need not apply.Living better through chemicals
He's observed that current factoring algorithms use asymptotically more memory than CPU. For a sufficiently big problem, all of the cost of the machine goes into buying memory, which spends most of its life waiting for the CPU to get around to it.
It's the same idea that motivated the Connection Machine.
He's observing that if you use the right (low-memory) algorithms, you can trade off memory for CPU and get something for which the total cost, memory+CPU, grows more slowly with problem size.
But it's not clear that's we've reached the CPU bottleneck yet. RAM is really cheap these days, so it's quite possibly premature to worry about the growth rate of that term.
Remember, the paper is part of a grant application. "I have this neat idea, and I'd like to study how practical it is."
More concretely, if all his ideas pan out, he can factor a 3*n+k-bit number for the same cost*time that GNFS can factor an n+k-bit number. What's k? Nobody knows! That's what he wants to study. If it's 1024, there are no immediate security issues. If it's 128, we need to deal with it.
(The claim in the abstract, (3.009...+o(1))*n, is more accurate, but the casual reader might not notice that o(1) can be significant and negative for currently interesting problem sizes.)
So while it deserves careful attention, let me add, in large, friendly letters: Don't Panic .
I don't think it'll be an issue.
All it does is speed up a brute force attack.
/did/ break RSA completely - ie, by indicating that factoring is in fact a P problem rather than NP complete - then it would have made infinitely more of a splash than it did. That kind of breakthrough is Nobel Prize type stuff.
If it
himi
My very own DeCSS mirror.
That's not quite right.
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.
Xenu loves you!