Path: utzoo!utgpu!water!watmath!clyde!att!rutgers!apple!bionet!agate!saturn!Michael.Browne@k.gp.cs.cmu.edu
From: Michael.Browne@k.gp.cs.cmu.edu
Newsgroups: comp.os.research
Subject: Re: Non-secure workstations (long) (Was: The NeXT Problem)
Message-ID: <5241@saturn.ucsc.edu>
Date: 24 Oct 88 18:33:35 GMT
Sender: usenet@saturn.ucsc.edu
Organization: Cranberry Melon
Lines: 110
Approved: comp-os-research@jupiter.ucsc.edu


In article <5198@saturn.ucsc.edu>, fouts@lemming. (Marty Fouts) writes:
> 
> In article <5187@saturn.ucsc.edu> wyatt%cfa@husc6.harvard.edu (Bill Wyatt) writes:
> 
>    > 
>    > [...]
>    > Anyway, authentication in a hostile network is at best a currently
>    > unsolved problem, and at worse an unsolvable problem.
> 
>    Not true, at least if you allow *some* machines to be trusted.
>    Check out MIT/Athena's `Kerberos' network authentication system,
>    [...]
> 
> I vaugely remember reading about work aimed at beating such a system,
> but I don't have a reference handy.  However, in a truely hostile
> environment the underlying assumption of hostility makes the idea of
> trusting *some* machines seem rather silly.  What systems like
> Kerberos do (besides giving their users a false sense of security) is
> change the problem from faking one user to faking both the user and
> the authentication system.
> 
> One of the reasons why public-key based signature systems haven't been
> widely received is because of their need to depend on a repository
> that everybody trusts.  [...]
>
> The problem with using even a trusted authentication server is
> that before I believe that you are the authentication server, you have
> to prove you are the authentication server in the presence of the
> possibility that someone else will pretend to be the authentication
> server, or attempt to cause me to believe you are not.  In a
> nonhostile environment the problem is trivial, but without hostility
> not worth solving.
> 
> In a hostile environment it appears doable, if you are willing to make
> assumptions along the lines of "OK, Kings-X, nobody cheat while I set
> up an authentication server, and nobody pretend to be the
> authentication server.  Done.  Go ahead cheat now, if you can."
> 
> Kerberos increases my confidence that you are the authentication
> server but it doesn't guarentee that you are.  If I'm willing to
> accept the level of confidence that it provides, than I can claim to
> be 'reasonably secure' or 'adequately secure' for my needs.  It still
> doesn't make me 'secure.'

You should read Needham and Shroeder's paper.  It gives ways of performing
authentication given reliable communication.  Neuman et. al.'s Kerberos
system relies on the secret-key authentication algorithm presented there.

Another reason why public-key schemes are not very popular is that they tend
to require lots of CPU time.  Further, some have theoretical problems:  RSA,
for example, was shown by Chor that if you can figure out the last bit of
plaintext given the cryptext with probability greater than 1/2 plus epsilon,
then you can invert RSA.  Also, RSA leaks information:  the value of the
Jacobi function on the cryptext is always identical to the value of the
Jacobi function on the plaintext.  The scheme proposed by Rabin which relies
on the ability of the recipient to extract square roots mod pq, though
provably equivalent to factoring, is susceptible to chosen-cryptext attacks
where the adversary uses the recipient as an oracle to extract square roots.

Let us consider the problem of authentication in a hostile network.  How do
we contact our authentication server?  The solution is relatively simple.
We set up N hosts which serves as authentication servers; each
authentication server uses a different puzzle (chosen independently) used in
zero-knowledge authentication.  The puzzles can be widely published; only
the solutions are kept secret (local to the appropriate server).  By using
0-knowledge authentication, we guarantee that no information about the
solution is leaked out.  When a client needs to obtain authentication
information, it must contact (at least) M of the N hosts and retrieve >=M
copies of authentication information; we must have a quorum of M identical
copies before we'd trust the information.

Note that before we run the authentication protocol, we perform key-exchange
in order to establish a secure channel.  There are (relatively) cheap
key-exchange methods that allow the sender to send a few bits securely; a
public key scheme could also be used.  Having a secure channel ensures that
if our adversary interposes himself in our communication channel he would
not be able to insert erroneous data.  For sending widely-published data, we
don't really need to encrypt the data -- we can simply exchange an
irreducible polynomial which is used to calculate a fingerprint to be
appended to each message.  A fingerprint is a cryptographic checksum which
is unforgeable with high probability when the key (the irreducible
polynomial) is unknown (kept secret).  The algorithm is by Rabin and Karp
and was presented by Karp during is Turing award acceptance lecture.  By
sending a fingerprint with each packet, we ensure that the recipient will
know if any data are corrupted.  This is much more efficient that encryption:
we have an implementation of this that can fingerprint at an excess of 900
Kbytes/second on an IBM APC/RT.

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.

- -bsy
- -- 
Internet:	bsy@cs.cmu.edu		Bitnet:	bsy%cs.cmu.edu%smtp@interbit
CSnet:	bsy%cs.cmu.edu@relay.cs.net	Uucp:	...!seismo!cs.cmu.edu!bsy
USPS:	Bennet Yee, CS Dept, CMU, Pittsburgh, PA 15213-3890
Voice:	(412) 268-7571