From: jim@bilbo.suite.com (Jim Miller)
Date: Sat, 12 Feb 94 16:51:09 PST
To: cypherpunks@toad.com
Subject: a protocol
Message-ID: <9402130044.AA01412@bilbo.suite.com>
MIME-Version: 1.0
Content-Type: text/plain



An idea came to me today for a protocol for exchanging keys  
point-to-point (inspired by the Robert Cain messages).  The protocol  
is a just combination of the Interlock Protocol described on page 44  
of "Applied Cryptography" and Diffie-Hellman, describe on page 275.

Keeping with the terminology of the book, Alice will attempt to  
exchange a key with Bob, and Mallet will attempt to sit in the middle  
without being detected.

As has been demonstrated in the past, I haven't read a lot of the  
cryptography papers that are out there, so for all I know, this is a  
well known protocol (or simple variation).  However, I haven't seen  
it, and it seems interesting.  Anyways, on with the show...


1) Alice sends Bob her public key.  (ala Interlock Protocol)

2) Bob sends Alice his public key.

3) Alice generates a Diffie-Hellman "n" value, encrypts "n" with  
Bob's public key and sends half of the "n" message to Bob.

4) Bob generates a Diffie-Hellman "g" value, encrypts "g" with  
Alice's public key and sends half of the "g" message to Alice.

5) Alice sends other half of "n" message to Bob.

6) Bob puts the two halves of Alice's "n" message together and  
decrypts it with his private key.  Bob sends the other half of his  
"g" message to Alice.

7) Alice puts the two halves of Bob's "g" message together and  
decrypts it with her private key.

Alice and Bob's each now have an "n" and a "g".  Below, I try to show  
that they can only have the same "n" and "g" if there is no  
man-in-the-middle.

Alice chooses a random large integer x and computes:

		X = (g**x) mod n

Bob chooses a random large integer y and computes:

		Y = (g**y) mod n

Standard Diffie-Hellman stuff.


8) Alice encrypts X with Bob's public key and sends half of X message  
to Bob.

9) Bob encrypts Y with Alice's public key and sends half of Y message  
to Alice.

10) Alice sends other half of X message to Bob.

11) Bob puts the two halves of Alice's X message together and  
decrypts it with his private key.  Bob sends the other half of his Y  
message to Alice.

12) Alice puts the two halves of Bob's Y message together and  
decrypts it with her private key.

Now Alice and Bob's each have an X and a Y.

Alice computes k = (Y**x) mod n.

Bob computes k' = (X**y) mod n.

13) Alice encrypts a message using k and sends it to Bob.

Bob decrypts message using k' and validates success of protocol.

14) Bob encrypts a message using k' and sends it to Alice.

Alice decrypts message using k and validates success of protocol.

----------

What can Mallet do to this protocol?

Mallet can substitute his own public keys for Alice's and Bob's in  
steps 1 and 2.  Mallet can then capture "n" (from Alice) and "g"  
(from Bob), although not immediately.  Mallet forward Bob bogus "n"  
message halves and Alice bogus "g"  message halves.  Thus Alice will  
get a bogus g, call it g', and Bob will get a bogus n, call it n'.

Mallet cannot forward the real "n" to Bob because of the interlock  
protocol.  Similarly, Mallet cannot forward the real "g" to Alice.   
Mallet only learns "n" in step 5 and "g" in step 6.  However, he must  
forward half of a bogus "n" to Bob in step 3), half of a bogus "g" to  
Alice in step 4.

At the end of step 6, Alice will have n and g' and Bob will have n'  
and g.

Alice and Bob continue with the protocol and calculate X and Y.   
Alice and Bob use the interlock protocol to exchange X and Y.  As  
with n and g, Mallet will eventually get X and Y, but not before  
having to forward a bogus X to Bob and a bogus Y to Alice (call them  
X' and Y').

Alice and Bob, still unaware of Mallet, compute k and k'.  However,  
since they are using different values for n, g, X, and Y, they will  
compute different values.  The encrypted messages in steps 13 and 14  
will expose Mallet.

I've only spent about fifteen minutes thinking about this protocol.   
I can't say that it is without holes or even that it does what I say  
it does.  However, I think it might have potential.  What to the  
professionals think?

Jim_Miller@suite.com