Key length security (calculations!)
Tim Mays writes:
I refer readers to the sci.crypt FAQ, the RSA FAQ, or books such as "Applied Cryptography." (Hint for those who don't want to: one time pads (Vernam ciphers) and things like RSA with 1000-digit moduli.)
("Enough effort" can be interpreted in a circular way to ensure the answer is 'Yes," as a truism. This is meaningless, if "enough effort" is impossible to achieve, as with OTPs, or is beyond the energy in the universe. If "enough effort" is interpreted to mean theft or rubber hose crytanalysis, all bets are off. But most people who ask the question I cited don't mean these loopholes.)
I have seen Tim posting statements to this effect many times, and because he is one of the more well respected and listened to voices on the list, I feel it important to examine this in some detail. While I agree that 1000 bit moduli in RSA is adequate protection *in all probability*, for even national security secrets, I think it is far from clear that this will definitely be true 10, or even 5 years from now. Instead of just waving vague generalities around, though, let's do some nitty gritty calculations: The people who cracked RSA-129 themselves have stated that they believe a 1024 bit modulus is at most 20,000 to 2,000,000 times more difficult to crack than RSA-129. For example, I recall Derek Atkins posting that he estimated a 1024 bit key to be 40,000 times harder than a 512 bit key, although I didn't save the posting. And Paul Leyland of Oxford posted:
RSA-129 is 425 bits; rather harder than 384-bit numbers. We estimate that 512-bit keys are about 20 times harder than RSA-129, if a more efficient but available algorithm is used. No-one knows how much harder 1024-bit numbers are, but they will be no where near a trillion times harder than 384-bit keys. Best estimates suggest that 1024-bit numbers are about 10^4 to 10^5 times harder than 512-bit numbers.
OK, so the people in the civilian world working on this today say it is possible that a 1024 bit key is only 20,000 times harder than RSA-129 *using known algorithms*. Now let's really get our hands dirty: cracking RSA-129 was estimated to take 5000 mips years. The NAL NWT 2/140 computer installed at the National Aerospace lab in Tokyo is estimated at 357 Cray YMP equivalents. I estimate this to be equivalent to 200 Gips for the purposes of this computation (this is possibly where I am most off). 5000 mips years = 1.58 X 10^17 instructions. This comes out to 9.13 days on the NAL NWT 2/140. If my estimates above are correct, scaling up to the 7400 Cray equivalent computer due to be installed 4Q95, from the 357 Cray equivalent above, we go down to 10.5 hours. This is all for the RSA-129, of course. Still sounds pretty safe so far... if it really takes at least 20,000 times as long to crack a 1024 bit modulus, then it would still take the 7400 C.E. (Cray Equivalent) computer 24 years to crack a 1024 bit number. BUT, the biggest worry is that no one knows how good the NSA's factoring algorithms are. I read recently that the NSA is the world's largest employer of mathematicians. The relative improvement in factoring algorithms since the introduction of the RSA-129 problem, to its factoring almost 20 years later, far exceed even the exponential increase in computer speed over that same period of time. (5 orders of magnitude? more?) We have no way of knowing how many orders of magnitude leeway we have, because as the moduli get larger, the factoring algorithm gets more and more important. Suppose the NSA has four orders of magnitude on us in the efficiency of their factoring algorithms. In that case, they might be able to crack a 1024 bit key as early as the end of 1995. (20,000 X 10.5)/10^4 hours = 21 hours required). Granted, this may not be likely, but I think we have to take the possibility seriously. At this point, 1024 bit keys cease to be secure for matters of critical national security (but still good for everything else). Now let's continue with our worst case scenario... suppose that computer speed doubles every 3.3 years over the next decade, and that further algorithmic breakthroughs continue to at least match this rate of doubling (not likely, perhaps, but *possible*). Then just one decade later, in 2005, the computer power of the NSA is 8 times greater, and the algorithms are 8 times faster, for a total speed increase of 64. At this point, they could crack a 1024 bit key in just 20 minutes (using all their resources), or 72 keys per day. At this point, I start to be uncomfortable trusting my security to a 1024 bit key length. So, it seems *possible*, even if by no means probable, that a 1024 bit key length is only good for the next decade or so. My intent is not to foster paranoia, but cypherpunks, of all people, should take as critical a view of key length security as possible. I suggest that people who state that the want 1200 bit or even 2000 bit key sizes in PGP be no longer ridiculed... the issue is subjective, as we have no way of knowing what the NSA's factoring algorithms are like. Doug ___________________________________________________________________ Doug Cutrell General Partner doug@OpenMind.com Open Mind, Santa Cruz ===================================================================
Doug Cutrells writes:
Tim Mays writes:
Singular, but no matter.
I refer readers to the sci.crypt FAQ, the RSA FAQ, or books such as "Applied Cryptography." (Hint for those who don't want to: one time pads (Vernam ciphers) and things like RSA with 1000-digit moduli.)
("Enough effort" can be interpreted in a circular way to ensure the answer is 'Yes," as a truism. This is meaningless, if "enough effort" is impossible to achieve, as with OTPs, or is beyond the energy in the universe. If "enough effort" is interpreted to mean theft or rubber hose crytanalysis, all bets are off. But most people who ask the question I cited don't mean these loopholes.)
I have seen Tim posting statements to this effect many times, and because he is one of the more well respected and listened to voices on the list, I feel it important to examine this in some detail. While I agree that 1000
Before going further, let me emphasize my mention in my section above of one-time pads, or Vernam ciphers. These are *information-theoretically secure*, which means that no amount of computer power can *ever* break them. Period. (In my characteristic way, I included a sidebar mention of stealing the key and or using rubber hose cryptanalysis, which some may think finessed my point about not being able to break OTPs. It does not, as far as "breaking" the cipher has cryptographic meaning.) As for RSA, that is only computationally secure, and depends on advances on factoring, as we all know. Many of us think there will not be "dramatic" advances in factoring, for various reason, but this of course cannot be proved (can't prove the nonexistence of some clever approach, logically). Factoring is suspected to be in the class NP (or even harder, some suspect), but it has not yet been proved to be so. If factoring is NP-complete, and if P = NP, then fast factoring methods may be found (fast = polynomial in length). Crypto books deal with this issue better than I can here.
Still sounds pretty safe so far... if it really takes at least 20,000 times as long to crack a 1024 bit modulus, then it would still take the 7400 C.E. (Cray Equivalent) computer 24 years to crack a 1024 bit number. BUT, the biggest worry is that no one knows how good the NSA's factoring algorithms are. I read recently that the NSA is the world's largest employer of mathematicians. The relative improvement in factoring algorithms since the
Not to attack Doug's point, which has validity here (that we don't know what factoring advances NSA may have made), but I personally think the combined capabilities of "public domain mathematicians" are now far greater than what NSA has. Shamir, Odzylko, Blum, Micali, Rackoff, Goldwasser, Solovay, Berlenkamp, etc., are top-flight researchers, publishing many papers a year on these topics. It is unlikely that some GS-14 mathematicians at the Fort, not able to publish openly, have made much more progress. I think the resurgence of crypto in the 70s, triggered by public key methods and fueled by complexity theory breakthrough, caused a "sea change" in inside NSA-outside NSA algorithm expertise.
So, it seems *possible*, even if by no means probable, that a 1024 bit key length is only good for the next decade or so. My intent is not to foster paranoia, but cypherpunks, of all people, should take as critical a view of key length security as possible.
I suggest that people who state that the want 1200 bit or even 2000 bit key sizes in PGP be no longer ridiculed... the issue is subjective, as we have no way of knowing what the NSA's factoring algorithms are like.
I have never ridiculed them (in fact, I use 1280 bits or somesuch), and I think the whole recent matter of Phil Zimmermann charging that "amateur cryptologists" are tainting his reputation and that of PGP to have some supreme ironies. Seems to me I heard a guy named Bidzos making the same points..... (I'm not attacking Phil, just noting the ironies of Phil now attempting to control the evolution of "his" intellectual property. The "naming" issue is minor--and that's what digital signatures are for, anyway.) A 3000-bit key may very well require more total energy to break than is available in the universe. Barring P = NP sorts of breakthroughs, of course. (I did a post on this last week.) The bottom line is sometimes lost in the debate: * It is just not true that "any cipher can be broken if the NSA really wants to." (This was the original point I was responding to.) * Some ciphers are absolutely unbreakable, and others are effectively unbreakable, or soon will be. Increased key length is computationally "cheap" to use, but "expensive" to break. (The current imbroglio about key lengths of PGP 2.6 is a passing implementation detail, having to do with how PGP does math. By Version 3.0, speculatively, it will likely be increased dramatically. No big deal. People should generate new keys and flush the old ones, anyway.) --Tim May -- .......................................................................... Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay@netcom.com | anonymous networks, digital pseudonyms, zero 408-688-5409 | knowledge, reputations, information markets, W.A.S.T.E.: Aptos, CA | black markets, collapse of governments. Higher Power: 2^859433 | Public Key: PGP and MailSafe available. "National borders are just speed bumps on the information superhighway."
To quote you: <<Not to attack Doug's point, which has validity here (that we don't know what factoring advances NSA may have made), but I personally think the combined capabilities of "public domain mathematicians" are now far greater than what NSA has. Shamir, Odzylko, Blum, Micali, Rackoff, Goldwasser, Solovay, Berlenkamp, etc., are top-flight researchers, publishing many papers a year on these topics. It is unlikely that some GS-14 mathematicians at the Fort, not able to publish openly, have made much more progress. I think the resurgence of crypto in the 70s, triggered by public key methods and fueled by complexity theory breakthrough, caused a "sea change" in inside NSA-outside NSA algorithm expertise.
You mention Shamir, etc. However I would point out that even if any of the original RSA mathematicians found a better factoring algorithm, they'd be more than likely to keep it under lock and key. The obvious reason is that their money supply depends on such an algorithm being suppressed. Now, someone outside of their circle with a little less to worry about the impact of such a factoring algirthm would be likely to publish it, but I doubt that PKP's founders would.
Arsen Ray A. writes:
To quote you: <<Not to attack Doug's point, which has validity here (that we don't know what factoring advances NSA may have made), but I personally think the combined capabilities of "public domain mathematicians" are now far greater than what NSA has. Shamir, Odzylko, Blum, Micali, Rackoff, Goldwasser, Solovay, Berlenkamp, etc., are top-flight researchers, publishing many papers a year on these topics. It is unlikely that some GS-14 mathematicians at the Fort, not able to publish openly, have made much more progress. I think the resurgence of crypto in the 70s, triggered by public key methods and fueled by complexity theory breakthrough, caused a "sea change" in inside NSA-outside NSA algorithm expertise.
You mention Shamir, etc. However I would point out that even if any of the original RSA mathematicians found a better factoring algorithm, they'd be more than likely to keep it under lock and key. The obvious reason is that their money supply depends on such an algorithm being suppressed.
Now, someone outside of their circle with a little less to worry about the impact of such a factoring algirthm would be likely to publish it, but I doubt that PKP's founders would.
Several points: 1. Adi Shamir sold out what little share he had some years back. He has no financial links to PKP or RSADSI. 2. Shamir is Israeli. (This has led to more than one humorous situation in which Shamir has received notification from the U.S. government that he cannot "export" something he's working on--as an Israeli, living in Israel.) 3. Shamir was the coinventor (with Biham), or at least the recent rediscoverer, of differential cryptanalysis. He apparently felt no constraint to not publish. 4. Some of the others I listed, such as Odzylko, are in fact the known leaders of making improvements in factoring. (Not that various linear factors matter much, in the long run, of course.) It's only speculation as to the relative competence of mathematicians inside vs. outside the NSA; my main point remains that the outside community is very dynamic and robust and shows no signs that I can see of holding back on reporting breakthroughs. Nor could a major breakthrough be contained, I think. --Tim May -- .......................................................................... Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay@netcom.com | anonymous networks, digital pseudonyms, zero 408-688-5409 | knowledge, reputations, information markets, W.A.S.T.E.: Aptos, CA | black markets, collapse of governments. Higher Power: 2^859433 | Public Key: PGP and MailSafe available. "National borders are just speed bumps on the information superhighway."
To quote you: <<Not to attack Doug's point, which has validity here (that we don't know what factoring advances NSA may have made), but I personally think the combined capabilities of "public domain mathematicians" are now far greater than what NSA has. Shamir, Odzylko, Blum, Micali, Rackoff, Goldwasser, Solovay, Berlenkamp, etc., are top-flight researchers, publishing many papers a year on these topics. It is unlikely that some GS-14 mathematicians at the Fort, not able to publish openly, have made much more progress. I think the resurgence of crypto in the 70s, triggered by public key methods and fueled by complexity theory breakthrough, caused a "sea change" in inside NSA-outside NSA algorithm expertise.
You mention Shamir, etc. However I would point out that even if any of the original RSA mathematicians found a better factoring algorithm, they'd be more than likely to keep it under lock and key. The obvious reason is that their money supply depends on such an algorithm being suppressed.
What about Shamir's triple pass key exchange protocol (explained briefly below). Its the perfect key exchange algorithm. It obsoletes Public key systems entirely as long as you only need to exchange keys and not authenticate. I'd say that is pretty decent evidence that he does still do things to help the field when it might hurt RSADSI. (although I wouldn't say the same thing about all of them) Triple pass key exchange: Choose a commutative symetric encryption algorithm. Step 1: A encrypts the session key in his personal symetric key (he doesn't share it with anybody) and sends the message to B: Ea(K) Step 2: B encrypts this in her personal symetric key and sends it back to A: Eb(Ea(K)) Step 3: A decrypts the message and sends it back to B: Da(Eb(Ea(K))) Since we chose a commutative algorithm, this is Eb(K). Step 4: B decrypts with her key and Eve (ala Scheier) has no clue. Mallet can't intercept your communication, but he can talk to you and unless you have some sort of authentication impersonate Eve. Example commutative algorithm out of Schneier by Shamir based on the hardness of factoring: Choose a large prime, p. Choose an encryption key e that is a large prime less than p. Choose a d so that d*e mod (p-1) = 1 (i.e. the muliplicative inverse of e in mod (p-1)). C = P^e mod p P = C^d mod p Cheers, Jason W. Solinsky
Timothy C. May writes
Factoring is suspected to be in the class NP (or even harder, some suspect), but it has not yet been proved to be so.
Those who have studied the matter generally believe that factoring is NP, but is not NP complete. Factoring cannot be "even harder than NP" since a simple minded brute force attack is 2^(n/2), which is only NP As Timothy May points out, if factoring is NP, then modest increases in key length can easily defeat enormous improvements in factoring.
... if P = NP, then fast factoring methods may be found (fast = polynomial in length).
In the highly unlikely event that P = NP then we have also solved, as an almost trivial special case, the problems of true artificial intelligence, artificial consciousness, and artificial perception, and the failure of one particular form of crypto will not be noticed in the midst of such radical changes. -- --------------------------------------------------------------------- We have the right to defend ourselves and our property, because of the kind of animals that we James A. Donald are. True law derives from this right, not from the arbitrary power of the omnipotent state. jamesd@netcom.com
First Tim wrote:
Factoring is suspected to be in the class NP (or even harder, some suspect), but it has not yet been proved to be so.
NP is nondeterministic polynomial time, meaning that you can verify the answer in polynomial time. You need not be able to derive the answer in P time. The 'nondeterministic' part means that the machine guesses the reason for the correct answer and then verifies that it has the right answer. The reasoning is encoded in a piece of data called a witness. Since one can multiply two numbers together quickly, factoring is NP-hard. (X-hard means that the answer comes from a 'short' sequence of decision questions in complexity class X.) The verification, multiplication, is in P, so factoring, the inverse of multiplication, is NP-hard. Since every P problem can be verified in P time (by running the P time algorithm without the need for a witness), P is a subset of NP. The unknown question is whether it is a proper subset. Then James wrote: Those who have studied the matter generally believe that factoring is NP, but is not NP complete. Factoring isn't in NP. Factoring is NP-hard. Problems in P and NP are decision problems, i.e. problems which have true or false answers. NP-hard means that the problem can be reduced to answering a short list of NP problems. In this case, those questions might be "Is the second-lowest bit of the smallest factor a 1?" and so on, questions about specific properties of the factorization. Note that a factorization makes a suitable witness for every such NP question. Factoring cannot be "even harder than NP" since a simple minded brute force attack is 2^(n/2), which is only NP 2^n problems give you E, exponential time. There's also NE, nondetermistic exponential time, problems which have witnesses verifiable in E time. Merely having an exponential time algorithm does not mean that the problem is in NP. NP is a subset of E, however. The easy algorithm is exhaustive search of the space of possible witnesses, which in exponential in the length of the P time verification method, and therefore exponential in the length of the input. As Timothy May points out, if factoring is NP, then modest increases in key length can easily defeat enormous improvements in factoring. Also not quite true. Consider a putative problem whose provably best algorithm is O(n^(log log n)). This algorithm dominates every polynomial (and hence is _not_ in P), but grows extremely slowly. How extremely? Take the log base at 10 and n = 1 googol. The calculation yields O(n^2). No such algorithms or problems are known, I might add; neither is their existence firmly denied. Eric
Still sounds pretty safe so far... if it really takes at least 20,000 times as long to crack a 1024 bit modulus, then it would still take the 7400 C.E. (Cray Equivalent) computer 24 years to crack a 1024 bit number. BUT, the biggest worry is that no one knows how good the NSA's factoring algorithms are. I read recently that the NSA is the world's largest employer of mathematicians. The relative improvement in factoring algorithms since the
Not to attack Doug's point, which has validity here (that we don't know what factoring advances NSA may have made), but I personally think the combined capabilities of "public domain mathematicians" are now far greater than what NSA has. Shamir, Odzylko, Blum, Micali, Rackoff, Goldwasser, Solovay, Berlenkamp, etc., are top-flight researchers, publishing many papers a year on these topics. It is unlikely that some GS-14 mathematicians at the Fort, not able to publish openly, have made much more progress. I think the resurgence of crypto in the 70s, triggered by public key methods and fueled by complexity theory breakthrough, caused a "sea change" in inside NSA-outside NSA algorithm expertise.
I disagree with this, and I would site as a case and point the fact that differential cryptanalytic attacks were not "discovered" until 1990 while a relatively small team of IBM cryptologists had it back in 1974 when they made DES. NSA apparently had it before then. This is why I would rather find a fast secure mulitple DES method based on spliting and not have to use IDEA which us so new. Before I was born, NSA knew all of these things which were not figured out by the academic community until this decade. (of course they could also know of some sort of back door, but I think that the fact that NSA knew of differential cryptography and let an algorithm immune to it pass while they lowered the key size says something about DES's security against attacks the academic community hasn't figured out yet. The bottom line is that NSA has demonstrated that they can outperform academia without public reviews of their method (LEAFs aside for the moment [government agencies are after all required to do several stupid things each year]) Cheers, JWS
participants (6)
-
doug＠OpenMind.com -
hughes＠ah.com -
jamesd＠netcom.com -
rarachel＠prism.poly.edu -
solman＠MIT.EDU -
tcmay＠netcom.com