Xref: cantaloupe.srv.cs.cmu.edu sci.crypt:15600 alt.security.pgp:2589 alt.privacy.clipper:23
Newsgroups: sci.crypt,alt.security.pgp,alt.privacy.clipper
Path: cantaloupe.srv.cs.cmu.edu!rochester!cornell!batcomputer!caen!zaphod.mps.ohio-state.edu!howland.reston.ans.net!agate!linus!linus.mitre.org!linus!mbunix!eachus
From: eachus@spectre.mitre.org (Robert I. Eachus)
Subject: Re: Off the shelf cheap DES keyseach machine (Was: Re: Corporate acceptance of the wiretap chip)
In-Reply-To: scs@lokkur.dexter.mi.us's message of Wed, 21 Apr 93 00:12:30 GMT
Message-ID: <EACHUS.93Apr21140358@spectre.mitre.org>
Sender: news@linus.mitre.org (News Service)
Nntp-Posting-Host: spectre.mitre.org
Organization: The Mitre Corp., Bedford, MA.
References: <pgf.735187239@srl03.cacs.usl.edu> <16BB51156.C445585@mizzou1.missouri.edu>
	<1993Apr19.093227.1093@jarvis.csri.toronto.edu>
	<1993Apr20.150531.2059@magnus.acs.ohio-state.edu>
	<1993Apr20.192105.11751@ulysses.att.com>
Date: Wed, 21 Apr 1993 19:03:58 GMT
Lines: 32


   smb@research.att.com (Steven Bellovin) writes:

   >Thousands?  Tens of thousands?  Do some arithmetic, please...  Skipjack
   >has 2^80 possible keys.  Let's assume a brute-force engine like that
   >hypothesized for DES:  1 microsecond per trial, 1 million chips.  That's
   >10^12 trials per second, or about 38,000 years for 2^80 trials.  Well,
   >maybe they can get chips running at one trial per nanosecond, and build
   >a machine with 10 million chips.  Sure -- only 3.8 years for each solution.

   But there is a MUCH more pernicious problem with the scheme as
proposed.  Building a brute force machine to test 2^40 possible keys
if you have the other half from one escrow agent is EASY.  (One chip,
one test per microsecond gives you one break every two weeks, and that
break gives you all messages involving that phone.)

   The XOR scheme so that the files from one escrow agent gives you
nothing is an improvement, but notice that XORing with (truely random)
bit strings allows for an arbitrary number of escrow agents.  Using +
for XOR, SK for the escrowed key, and A and B for two random bit
strings, hand SK+A+B, SK+A, and SK+B to three escrow agents.  It is
possible to come with an encoding scheme to match any escrow pattern,
for example 3 of 4, such that fewer cooperating escrow agents gives
the cracking agency no benefit.

--

					Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...
