At 12:27 AM -0700 10/17/00, Kerry L. Bonin wrote:
And yet ciphers are a significant target of the NSA. Sure, they devote significant resources to exploiting weaknesses in key management, but ciphers are a primary target.
Many people who discuss the capabilities of the NSA do not use proper methodology in extrapolating their technical capabilities. General purpose computers and supercomputers are not well suited to attacking ciphers - custom silicon is the best means.
For a message encrypted (or signed, a related problem) with a PKS cipher, recovering the plaintext involves factoring the modulus...so far as we know. This factoring may be done with conventional computers, special-purpose computers, or even exotic computers (tanks of DNA computers, billions of Net-connected computers, superconducting geodes orbiting around Neptune, quantum computers, whatever.) (Note that I am assuming here a pure PKS/RSA cipher, with no use of IDEA or 3DES or AES, etc. This is feasible for short messages. ) A look at the work factors (cf. Rivest's paper of circa 1993-4, or Schneier's book, or any of several other books, or one's own calculations) will show the pointlessness of throwing more computer power at sufficiently large moduli. Absent a breakthrough in factoring (and I mean a _major_ breakthrough, not a polynomial factor speedup), a modulus of thousands of decimal digits will never be factored. The "RSA-129" challenge becomes the "RSA-1000" challenge. Moore's Law won't do any good, nor will using ASICs or gate arrays or even nanotechnology. A quantum computer _might_ make a difference (though this is unproven).
Extrapolate capabilities from the EFF DES crack project and you are somewhat closer (1536 ASIC w/ 24 cores/ASIC yielded 4.52 days/crack of 56 bit keyspace), then take into consideration the advantages of using more sophisticated semiconductor processes (ECL 15 years ago, GaAs on Sapphire today) and the higher clock rates that go with that (40MHz to well > 1GHz), and rerun your numbers. Instead of a small cabinet, fill floors of buildings with these machines, and you have realtime cracking farms.
Please spend a bit of time calculating what these "cracking farms" do for factoring very large numbers. (Or even for cracking 3DES.) Look, no one has any doubt that NSA and probably other intelligence agencies have built gate-array-based DES-cracking machines. This was implicit in Diffie and Hellman's paper on cracking DES, a paper published twenty-some years ago. And of course people we know have built DES-cracking machines of their own. But a DES-cracker is not a 3DES-cracker. I hope the math of this is known to all readers. And it is especially not a machine for factoring 3000-digit numbers. Talking about SOS and ECL and 1 GHz and all is nonsensical. All of those technologies are as nothing when in comes to problems with work factors exponential in key length! The exact point at which brute force becomes economically infeasible depends on technologies, improvements in algorithms, etc., but the broad outlines remain as described.
It should be noted that increasing the keyspace isn't a magic protection implying the heat entropy of the universe prevents a crack - the NSA has been playing with Feistel networks since before most cryptographers even knew about DA, not to mention the possibilities of many other unknown weaknesses in Feistel networks being known to the NSA.
As for my own comments, I wrote layout and design tools used on these NSA custom chips in the mid 80's, certified for use with the "NSA Standard Cell Library" by their chip designers (they were just one of the customers of the CAD/CAM/CAE software I worked on back then...)
Then I'd have to say your analytical abilities are shallow. If you think one of these ciphers with work factors exponential in modulus size (or "key length," approximately) will fall to custom chips, you don't understand exponential time/space.
I don't think its unreasonable to extrapolate that a sufficiently high priority message can be cracked by the NSA in near realtime, regardless of the cipher strength used, without significant knowledge of the nature of the plaintext.
And you believe this?
I'd imagine most attacks focus on key management, but anyone serious about the game will have obscene numbers of gates chewing on ciphertext.
Please read up on work factors. Here's something from one of the PGP FAQs, http://www.uk.pgp.net/pgpnet/pgp-faq/faq-appendix2.html#2.5.1 --begin excerpt-- Here's a table from Applied Cryptography, referenced with an unpublished paper (as of Feb. 1995) by Andrew Odlyzko "Progress in Integer Factorization and Discrete Logarithms" Mips years required to factor a number with the GNFS: Bits Mips-years 512 30,000 768 2*10^8 1024 3*10^11 1280 1*10^14 1536 3*10^16 2048 3*10^20 --end excerpt-- Good luck with your PALs and gate arrays. Have fun. Near realtime cracking. Sure. Whatever. --Tim May -- ---------:---------:---------:---------:---------:---------:---------:---- Timothy C. May | Crypto Anarchy: encryption, digital money, ComSec 3DES: 831-728-0152 | anonymous networks, digital pseudonyms, zero W.A.S.T.E.: Corralitos, CA | knowledge, reputations, information markets, "Cyphernomicon" | black markets, collapse of governments.