From: "A. Padgett Peterson P.E. Information Security" <PADGETT@hobbes.orl.mmc.com>
Date: Mon, 19 Feb 1996 00:39:13 +0800
To: cypherpunks@toad.com
Subject: Numbers don't lie...
Message-ID: <960218111857.202256bd@hobbes.orl.mmc.com>
MIME-Version: 1.0
Content-Type: text/plain


Have finally gotten around to reading the Jersey Seven paper on keylengths.
Is rather amazing since if anything they are being conservative with some
of their numbers - are using 30 Mhz for the FPGA where I have been using 40 
& using 200 Mhz for ASICs where I would use 300 (year and a half ago I used
150mhz based on what I knew *had* been built, not what I knew X-ray 
lithography is capable of.

In their figures, they do seem to gloss over a couple of minor points:

The most compelling to me is "how do you know when you broke it ?". Bruce
has always used the "known plaintext" approach, however using modern 
techniques for messaging, *every* message has a different session key,
negotiated using assymetric keying so the only message that will be broken
is one that you already have - not terribly helpful.

The second point is that their scalability seems to be based on costs per
chip alone, cost for which the engineering cost has been recovered and for
which the yeild is significant, hardly givens when you are talking pushing
the state of the art, given this 200 Mhz Pentiums would be U$10.00 also
(well, maybe U$25.00).

Finally, no cost is allocated to the sustem required to program/evaluate
the ponderings of these 100's of ASICs. As anyone who has ever programmed
a massively parallel computer (which is what they are talking about in their
brute force machine, it is the boundary communications that kill you.

True, each machine could operate on a specific portion of the keyspace with
bits fixed as a function of its address, but each will need to be loaded
with the plaintext to match and have some means to communicate success.

You also have to consider that dividing the keyspace may result in some
processors running slower than others due to the values used. Another minor
problem in parallel processors.

The cost is given of U$300,000 to build a SOA machine that could break DES
in 3 hours. Using the 200 Mhz (2*10^8) figure and assuming 1 trial per 
clock (being nice), a single chip will test 2.2*10^12 keys in that period.
2^55 is otoa 3.6*10^16 so will require 16,680 thingies running
in parallel. If they can get the chips for U$10, they will be able to 
allocate another whole U$10.00 per chip to the support structure and basic
programming to stay inside the budget. Since this will hardly be a 
production process, I suspect that the cost might be a tad higher.

Now often banking and EDI (as opposed to EC) does make the mistake of using 
the same key for more than one message. Similarly a firewall<>firewall
connection might beep a single keyed channel open for multiple sessions.
This would be at risk. But for individual messages.

The paper does make an appropriate observation: the cost is essentially
fixed per key (scaling is not perfect but can ignore that for the moment
- has to do with why Crays are circular and Grace's "nanosecond"). This means
that the strength of cryptography should be appropriate to the value of
the information protected. If less than U$10,000, the message is individually
encrypted, and has value only today, then DES is probably "good enough".

Strategic information of higher value arguably needs "more" but how much ?
64 bits is 256 times stronger than DES. This would indicate effective
security up to say U$2.5 million. More is better but I would not be quite
so alarmist nor would I dismiss the cost of engineering. Non-trivial.

Do agree that 40 bits is the same as no crypto at all (reminds me of Bob
Clampett's "No Bikini Atoll" but is another hobby entirely).

Still, at what point is it simply easier/cheaper to buy someone who knows 
the secret ?

						Warmly,
							Padgett

ps calculation made with a Sharp EL-5806 "scientific" calculator that is 
   probably older than some readers. If I dropped a digit, please let me know.