Author(s): Bruce Schneier

ISBN: 0471128457

Publication Date: 01/01/96

Previous | Table of Contents | Next |

Diffie-Hellman key exchange is vulnerable to a man-in-the-middle attack. One way to prevent this problem is to have Alice and Bob sign their messages to each other [500].

This protocol assumes that Alice has a certificate with Bob’s public key and that Bob has a certificate with Alice’s public key. These certificates have been signed by some trusted authority outside this protocol. Here’s how Alice and Bob generate a secret key, *k.*

**(1)**Alice generates a random number,*x,*and sends it to Bob.**(2)**Bob generates a random number,*y.*Using the Diffie-Hellman protocol he computes their shared key based on*x*and*y: k.*He signs*x*and*y,*and encrypts the signature using*k.*He then sends that, along with*y,*to Alice.*y,E*_{k}(*S*_{B}(*x,y*))

**(3)**Alice also computes*k.*She decrypts the rest of Bob’s message and verifies his signature. Then she sends Bob a signed message consisting of*x*and*y,*encrypted in their shared key.*E*_{k}(*S*_{A}(*x,y*))

**(4)**Bob decrypts the message and verifies Alice’s signature.

This protocol, invented by Adi Shamir but never published, enables Alice and Bob to communicate securely without any advance exchange of either secret keys or public keys [1008].

This assumes the existence of a symmetric cipher that is commutative, that is:

*E*_{A}(*E*_{B}(*P*)) =*E*_{B}(*E*_{A}(*P*))

Alice’s secret key is *A;* Bob’s secret key is *B.* Alice wants to send a message, *M,* to Bob. Here’s the protocol.

**(1)**Alice encrypts*M*with her key and sends Bob*C*_{1}=*E*_{A}(*M*)

**(2)**Bob encrypts*C*_{1}with his key and sends Alice*C*_{2}=*E*_{B}(*E*_{A}(*M*))

**(3)**Alice decrypts*C*_{2}with her key and sends Bob*C*_{3}=*D*_{A}(*E*_{B}(*E*_{A}(*M*))) =*D*_{A}(*E*_{A}(*E*_{B}(*M*))) =*E*_{B}(*M*)

**(4)**Bob decrypts*C*_{3}with his key to recover*M.*

One-time pads are commutative and have perfect secrecy, but they will not work with this protocol. With a one-time pad, the three ciphertext messages would be:

*C*_{1}=*P*⊕*A**C*_{2}=*P*⊕*A*⊕*B**C*_{3}=*P*⊕*B*

Eve, who can record the three messages as they pass between Alice and Bob, simply XORs them together to retrieve the message:

*C*_{1}⊕*C*_{2}⊕*C*_{3}= (*P*⊕*A*) ⊕ (*P*⊕*A*⊕*B*) ⊕ (*P*⊕*B*) =*P*

This clearly won’t work.

Shamir (and independently, Jim Omura) described an encryption algorithm that will work with this protocol, one similar to RSA. Let *p* be a large prime for which *p* - 1 has a large prime factor. Choose an encryption key, *e,* such that *e* is relatively prime to *p* - 1. Calculate *d* such that *de* ≡ 1 (mod *p* - 1).

To encrypt a message, calculate

*C*=*M*^{e}mod*p*

To decrypt a message, calculate

*M*=*C*^{d}mod*p*

There seems to be no way for Eve to recover *M* without solving the discrete logarithm problem, but this has never been proved.

Like Diffie-Hellman, this protocol allows Alice to initiate secure communication with Bob without knowing any of his keys. For Alice to use a public-key algorithm, she has to know his public key. With Shamir’s three-pass protocol, she just sends him a ciphertext message. The same thing with a public-key algorithm looks like:

**(1)**Alice asks Bob (or a KDC) for his public key.**(2)**Bob (or the KDC) sends Alice his public key.**(3)**Alice encrypts*M*with Bob’s public key and sends it to Bob.

Shamir’s three-pass protocol will fall to a man-in-the-middle attack.

COMSET (COMmunications SETup) is a mutual identification and key exchange protocol developed for the RIPE project [1305] (see Section 25.7). Using public-key cryptography, it allows Alice and Bob to identify themselves to each other and also to exchange a secret key.

The mathematical principle behind COMSET is Rabin’s scheme [1283] (see Section 19.5). The scheme itself was originally proposed in [224]. See [1305] for details.

The Encrypted Key Exchange (EKE) protocol was designed by Steve Bellovin and Michael Merritt [109]. It provides security and authentication on computer networks, using both symmetric and public-key cryptography in a novel way: A shared secret key is used to encrypt a randomly generated public key.

*The Basic EKE Protocol*

Alice and Bob (two users, a user and the host, or whoever) share a common password, *P.* Using this protocol, they can authenticate each other and generate a common session key, *K.*

**(1)**Alice generates a random public-key/private-key key pair. She encrypts the public key,*K´,*using a symmetric algorithm and*P*as the key:*Ep*(*K´*). She sends Bob*A, E*_{P}(*K´*)

**(2)**Bob knows*P.*He decrypts the message to obtain*K´*. Then, he generates a random session key,*K,*and encrypts it with the public key he received from Alice and*P*as the key. He sends Alice*E*_{P}(*E*_{K´}(*K*))

**(3)**Alice decrypts the message to obtain*K.*She generates a random string,*R*_{A}, encrypts it with*K,*and sends Bob*E*_{K}(*R*_{A})

**(4)**Bob decrypts the message to obtain*R*_{A}. He generates another random string,*R*_{B}, encrypts both strings with*K,*and sends Alice the result.*E*_{K}(*R*_{A},*R*_{B})

**(5)**Alice decrypts the message to obtain*R*_{A}and*R*_{B}. Assuming the*R*_{A}she received from Bob is the same as the one she sent to Bob in step (3), she encrypts*R*_{B}with*K*and sends it to Bob.*E*_{K}(*R*_{B})

**(6)**Bob decrypts the message to obtain*R*_{B}. Assuming the*R*_{B}he received from Alice is the same one he sent to Alice in step (4), the protocol is complete. Both parties now communicate using*K*as the session key.

Previous | Table of Contents | Next |