From: jim@bilbo.suite.com (Jim Miller)

To: cypherpunks@toad.com

Message Hash: 8f26494789731aff31c3b416352dfc665ffbe20131ea9ec8277c4cffb1bf8d0c

Message ID: <9402130044.AA01412@bilbo.suite.com>

Reply To: *N/A*

UTC Datetime: 1994-02-13 00:51:09 UTC

Raw Date: Sat, 12 Feb 94 16:51:09 PST

```
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
```

Return to February 1994

- Return to “jim@bilbo.suite.com (Jim Miller)”
Return to “Timothy A. Ryan <gymnast@Crissy.Stanford.EDU>”

- 1994-02-13 (Sat, 12 Feb 94 16:51:09 PST) - a protocol -
*jim@bilbo.suite.com (Jim Miller)*- 1994-02-13 (Sat, 12 Feb 94 18:11:10 PST) - Re: a protocol -
*Timothy A. Ryan <gymnast@Crissy.Stanford.EDU>*

- 1994-02-13 (Sat, 12 Feb 94 18:11:10 PST) - Re: a protocol -