CDR: Re: why should it be trusted?

[Tim May]

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.