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

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.

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.

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:

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₁ = E_A(M)

(2)  Bob encrypts C₁ with his key and sends Alice

C₂ = E_B(E_A(M))

(3)  Alice decrypts C₂ with her key and sends Bob

C₃ = D_A(E_B(E_A(M))) =D_A(E_A(E_B(M))) = E_B(M)

(4)  Bob decrypts C₃ 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₁ = P⊕ A

C₂ = P⊕ A⊕ B

C₃ = 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₁ ⊕ C₂ ⊕ C₃ = (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.

22.4 COMSET

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(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.