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?"

Comments

For the PostScript-impaired

[Hew]

Try viewing the postscript file using the online viewer here instead.

Re:For the PostScript-impaired

[killmenow]

Or view it as this PDF.

Now let's see how well RR's server can handle the /. effect. :^)

Re:For the PostScript-impaired

[Cy Guy]

Or you can (try to) view in plain text via the Google archive here. Here's the Preface:

Preface
This paper is an excerpt from a grant proposal that I submitted to NSF DMS at the beginning of October 2001.

The same techniques can be applied to other congruence-combination algorithms for factoring, discrete logarithms, class groups, etc. See [3] for a bibliography.

Priority dates. I realized on 13 September 2000 that special-purpose hardware would change the exponent in the cost of integer factorization. I announced the exponent reduction from 3 + o(1) to 2:5 + o(1) for real (two-dimensional) circuits in a seminar at Butler University on 23 March 2001, a rump-session presentation at Eurocrypt 2001 on 7 May 2001, and a talk at the Algorithms and Number Theory conference at Dagstuhl on 14 May 2001. I realized on 9 August 2001 that the sieving exponent could easily be reduced from 2:5 + o(1) to 2 + o(1).

HTML Version of Paper

[BigBadAssMonkey]

http://cr.yp.to/papers.html

Re:Hmm....

[jkujawa]

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.

Don't Panic

[SiliconEntity]

I am a co-author of RFC 2440, the OpenPGP standard. It's important to put this result into perspective. Dan Bernstein is the first to say that it is too early to tell whether his design for a factoring machine would be practical for keys of the size in commmon use today. See for example this recent Usenet posting, where he says,

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.

Re:Known about for years

[gowen]

Correct, it was invented in 1973 by Ellis, Cocks and Williamson at GCHQ.

Re:AES?

[Ronin Developer]

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

The trick is to find the shortcut

[beej]

Any key can be cracked--you just have to search through all of them. Phew! Now, for 128 bits, that's a lots of numbers to search. For 2048 bits, it's more than you can possibly imagine.

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. ;-)

Re:AES?

[Snafoo]

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.

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 ;). 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 :)

Re:not surprising...

[Plutor]

Read the book The Code Book by Simon Singh. It's a fantastic mix of technical cryptography and historical perspectives.

Re:OMFG

[Anonymous Coward]

No, this is NOT a threefold increase in factoring speed. This is a threefold decrease in bit strength.

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...

cr.yp.to mirror

[Xanni]

See also my Australian mirror at: http://www.glasswings.com.au/cr.yp.to/papers.html# nfscircuit Share and enjoy, *** Xanni ***

Re:NSA, et. al.

[Strange Ranger]

"(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.

Re:Speaking as a computing DPhil...

[The Pim]

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.

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.

Re:Were they even secure yesterday?

[broter]

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:

• The design took advantage of certain cryptanalytic techniques, most prominently the technique of "differential cryptanalysis," which were not known in the published literature. After discussions with NSA, it was decided that disclosure of the design consideration would reveal the technique of differential cryptanalysis, a powerful technique that can be used against many ciphers. This in turn would weaken the competitive advantage the United States enjoyed over other countries in the field of cryptography.

I've heard about it in other places, but I can't remember where at the moment.

Re:Were they even secure yesterday?

[jonathan_ingram]

Here is the paper showing that DES is secure from differential cryptanalysis, but many related schemes were insecure:

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 :)].

This does /not/ break RSA.

[himi]

All it does is speed up a brute force attack.

If it /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.

himi

Re:Were they even secure yesterday?

[Paul Crowley]

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.