From: collins@newton.apple.com (Scott Collins)
Date: Wed, 15 Dec 93 14:10:43 PST
To: loki@cass156.ucsd.edu (Lance Cottrell)
Subject: Re: Improved DH system.
Message-ID: <9312152207.AA19290@newton.apple.com>
MIME-Version: 1.0
Content-Type: text/plain


Howdy,

  >I have been told that there is a new improved version of
  >DH key exchange, which is authenticated. Could
  >someone give me the reference, and/or tell me what it is
  >all about?........ Diffie??

I'm back at the office and can (finally) provide the information, sorry for
the delay.

The paper is "Authentication and Authenticated Key Exchanges" by Whitfield
Diffie, Paul C. van Oorschot, and Michael J. Wiener, published in _Designs,
Codes and Cryptography, 2, 107-125 (1992), by Kluwer Academic Publishers.

Here is some notation, and a brief description of the basic protocol. 
Almost everything from this point forward is quoted directly from the
paper.

{.}     Braces indicate a hash function.  {x, y} is the result when a hash
function is applied to x concatenated with y.

S_A     Alice's secret key for a signature scheme.  S_A(x) is Alice's
signature on x.  S_A{x} is Alice's signature on the hashed version of x.

P_A     Alice's public key for a signature scheme.  If the signature scheme
is a public-key cryptosystem, then we define P_A{x} and P_A(x) to be
Alice's public key encryption function with and without hashing.

E_K(x)  Encryption using a symmetric cryptosystem with key K.

[...]

5.1. Basic [Station-to-Station] Protocol

The STS protocol consists of DH key establishment, followed by an exhcange
of authentication signatures.  In the basic version of the protocol, we
assume that the parameters used for the key establishement, (i.e., the
specification of a particular cyclic group and the corresponding primitive
element a) are fixed and known to all users.  While we refer to the DH
operation as exponentiation, implying that the underlying group is
multiplicative, the description applies equally well to additive groups
(e.g., the group of points of an elliptic curve over a finite field).  We
also assume in this section that Alice knows Bob's authentic public key,
and vice versa; this assumption is dropped in the following section [which
I did not type in].

[...]

Alice                                           Bob
-----                                           ---
a is known,
x is random

        ------------- a^x --------------->>
                                                a is known,
                                                y is random
                                                K = (a^x)^y = a^(xy)
        <<---- a^y, E_K(S_B{a^y, a^x}) ----

K = (a^y)^x = a^(xy)

        ------- E_K(S_A{a^x, a^y}) ------>>



The paper is a very good read.  It describes the motivations behind the
protocol; how to assure (or dis-abuse) yourself of the security of other
protocols; modifications; other uses; etc.  I highly recommend it.

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