From: catalyst@netcom.com (Scott Collins)
Date: Thu, 30 Sep 93 00:26:36 PDT
To: Mike Ingle <MIKEINGLE@delphi.com>
Subject: Re: Active Eavesdropping of Clipper Phones
Message-ID: <9309300715.AA02851@newton.apple.com>
MIME-Version: 1.0
Content-Type: text/plain


What you are describing is the classic 'man-in-the-middle' attack.  It is
not avoidable short of out of band signalling i.e., you know some
fact/secret about the person you really want to talk to (like their public
key) that does not go through the man-in-the-middle (to possibly be
replace), and can't be faked.

Even with such knowledge, you still have to design your protocol with care.
 The essence of one protocol that is proof against this attack is this:

        Diffie-Hellman key exchange, during which the two parties seeking
        privacy also exchange challenge data which is returned after being
        concatenated with the other parties a^x, and signed with their
        private key.

These are only the central parts.  Additionally, certificates might be
exchanged etc.  But even slight changes to this would make it less secure:
e.g. if each party only sent the cryptographically signed a^x, then an
attacker willing to build the log table to (much later) derive x (this
person could even be the intended recipient) could use saved portions of a
real exchange to mount a 'replay' attack.  Also, choosing a system wide 'a'
and 'p' increase the incentive to build the tables, much better to let
people put their personal choice for 'a' and 'p' in their signed & sealed
key certificate.

This protocol is described in detail in a paper (that is not in front of me
right now, so I'm a little fuzzy) that was published in 'Designs, Codes and
Cryptograpy', a periodical originating in the Netherlands.  I believe the
authors were Diffie and van Oorschot(?), but I'm just can't remember off
the top of my head.  If Whit Diffie is reading this message, then surely he
will know, I think, even if he wasn't the author.

Without 'out of band' signalling, the clipper chip would certainly be
subject to this kind of attack.  My understanding is that Skipjack is
symmetric, so that's no help.  We already noted that straight DH key
exchange is vulnerable.  The only remaining hope, then, is that your phone
knows some serial number or such about the phone you _intend_ to be
communicating with, and that this fact is an unavoidable part of the IV
such that once you know who the message is supposed to be coming from, you
couldn't decrypt it unless it really did, and no one else could fake it. 
This is possible, but obviously teetering on the brink of asymmetry, and
therefore, I think, unlikely.

The man-in-the-middle attack is so well known, however, that clipper must
have _some_ provision for it, and I just haven't read the right paragraph
yet.

Hope this helps,


Scott Collins         | "Few people realize what tremendous power there
                      |  is in one of these things."     -- Willy Wonka
......................|................................................
BUSINESS.   voice:408.862.0540  fax:974.6094   collins@newton.apple.com
Apple Computer, Inc.   5 Infinite Loop, MS 305-2B   Cupertino, CA 95014
.......................................................................
PERSONAL.   voice/fax:408.257.1746    1024:669687   catalyst@netcom.com