Re: What Constitutes an Exhaustive Attack? (Murray, RISKS-15.02)

[David Farber <farber () central cis upenn edu>]

Date: Tue, 7 Sep 93 13:19:21 -0400
From: padgett () tccslr dnet mmc com (A. Padgett Peterson)
Subject: Re: What Constitutes an Exhaustive Attack? (Murray, RISKS-15.02)


> The cost of an exhaustive attack is an interesting number.  It gives us an
> upper bound for the cost of efficient attacks.  However, it is never, itself,
> an efficient attack. 


What has bothered me for some time about Clipper/Capstone/SkipJack is
exactly this question and the concern that what might be an exhaustive 
to some might not be what the user would think.


Consider the possibility that every person in the United States were issued
a SkipJack key - better, suppose that every possible ZIP code in the United 
States were issued a key (10^9 as opposed to approx. 2.5*10^8 women, men, and
children). Next suppose that every key issued were known (not WHO they were
issued to, just WHICH had been issued). An exhaustive attack is now 10^9
trials with average success in 5*10^8 trials. At a 40 MHZ rate (common for
DSPs) this would take well under a minute for an exhaustive search.
No trapdoors, backdoors, or weak keys. Just a database of all issued keys.
In the sixties, a thief who wanted your GM car often did not have YOUR key, 
they had ALL the keys (on a ring about six inches in diameter - typically 
took about five minutes to find the right one).


The disclaimer here is usually one of random seeds etc but does anyone really
think that every key is going to have a unique random seed ? Or is it
more likely that the two agents will each contribute their 80 bit piece and
then a few thousand keys run off. And that the first (or last) from each batch
along with the count might be for some nameless agency ?


My belief is that the SkipJack algorithm is every bit as strong as everyone
has said it will be. The question will it really take an exhaustive attack or
will there be a "black bag" attack possible that will stem from the key
generation process. Creative accounting at work.


Padgett


ps I believe in Clipper/Capstone/SkipJack & if the price is within reason
   will be one of the first to use it. Most people do not care if our
   government can listen in. Just no surprises, Teapot Domes, or fingers-
   crossed promises please.