Applied Cryptography, Second Edition: Protocols, Algorthms, and Source Code in C (cloth)
(Publisher: John Wiley & Sons, Inc.)
Author(s): Bruce Schneier
ISBN: 0471128457
Publication Date: 01/01/96

Previous Table of Contents Next

22.2 Station-to-Station Protocol

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.
(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.
(4)  Bob decrypts the message and verifies Alice’s signature.

22.3 Shamir’s Three-Pass Protocol

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:

EA(EB(P)) = EB(EA(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
C1 = EA(M)
(2)  Bob encrypts C1 with his key and sends Alice
C2 = EB(EA(M))
(3)  Alice decrypts C2 with her key and sends Bob
C3 = DA(EB(EA(M))) =DA(EA(EB(M))) = EB(M)
(4)  Bob decrypts C3 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:

C1 = PA
C2 = PAB
C3 = PB

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

C1C2C3 = (PA) ⊕ (PAB) ⊕ (PB) = 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 = Me mod p

To decrypt a message, calculate

M = Cd 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.

22.5 Encrypted Key Exchange

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(). She sends Bob
A, EP()
(2)  Bob knows P. He decrypts the message to obtain . 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
(3)  Alice decrypts the message to obtain K. She generates a random string, RA, encrypts it with K, and sends Bob
(4)  Bob decrypts the message to obtain RA. He generates another random string, RB, encrypts both strings with K, and sends Alice the result.
(5)  Alice decrypts the message to obtain RA and RB. Assuming the RA she received from Bob is the same as the one she sent to Bob in step (3), she encrypts RB with K and sends it to Bob.
(6)  Bob decrypts the message to obtain RB. Assuming the RB 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
[an error occurred while processing this directive]