Path: utzoo!utgpu!water!watmath!clyde!att!osu-cis!tut.cis.ohio-state.edu!mailrus!ames!pasteur!agate!saturn!fouts@lemming.
From: fouts@lemming. (Marty Fouts)
Newsgroups: comp.os.research
Subject: A comment on assigning probabilitis (was Re: Non-secure workstations)
Message-ID: <5257@saturn.ucsc.edu>
Date: 25 Oct 88 16:29:19 GMT
Sender: usenet@saturn.ucsc.edu
Organization: NASA Ames Research Center, Moffet Field, CA
Lines: 44
Approved: comp-os-research@jupiter.ucsc.edu


In article <5241@saturn.ucsc.edu> Michael.Browne@k.gp.cs.cmu.edu writes:

   [ Early exposition deleted. . .]

   What does the quorum buy us?  Well, if the probability of an intruder
   breaking into any one ``secure'' host is p, and our desired level of
   security is s (i.e., the probability of an intruder being able to break our
   system is s, s < p), we can run N > ceil{log(s)/log(p)} hosts (M : s >= p^M)
   to achieve the desired level of security.  We run N > M hosts so the system
   can run with one or more servers disabled so denial-of-service by crashing a
   few servers is not a problem.  (Of course, this does not address
   denial-of-service by somebody cutting your ethernet cable....)

   By using zero-knowledge authentication where the authentication puzzles can
   be widely published (similarly, public key signature schemes may be used),
   we ensure that we contact the hosts that we intended to -- nobody can
   pretend to be the authentication server.  By using quorum consensus, we can
   lower the probability of an intruder breaking our system arbitrarily.

This appears to be an example of a subtle reasoning flaw I've seen
several times in breakin probability analysis.  There are two
problems.  First, there is the apparent tacit assumption that
arbitrary reduction of probability equates to 0 probability.

More importantly, this is an example of a difficulty in using probability
theory to assign degree of security.  The author tacitly assumes that
the probability of breaking into any secure host is independent of the
probability of breaking into any other secure host.  If the breakin is
due to a commonly shared feature of the hosts, such as an
implementation weakness, then the probability of defeating a quorum
system may be independent of the number of hosts used as "secure"
servers.  Worse case analysis requires that this probability be
assigned to the security of the system.

In this event, increasing the number of authenticators has no effect
on the degree of security of the system.

--
+-+-+-+     I don't know who I am, why should you?     +-+-+-+
   |        fouts@lemming.nas.nasa.gov                    |
   |        ...!ames!orville!fouts                        |
   |        Never attribute to malice what can be         |
+-+-+-+     explained by incompetence.                 +-+-+-+