Author(s): Bruce Schneier

ISBN: 0471128457

Publication Date: 01/01/96

Previous | Table of Contents | Next |

At step (3), both Alice and Bob know *K´* and *K. K* is the session key and can be used to encrypt all other messages between Alice and Bob. Eve, sitting between Alice and Bob, only knows *EP*(*K´*), *E*_{P}(*E*_{K´}(*K*)), and some messages encrypted with *K.* In other protocols, Eve could make guesses at *P* (people choose bad passwords all the time, and if Eve is clever she can make some good guesses) and then test her guesses. In this protocol, Eve cannot test her guess without cracking the public-key algorithm as well. And if both *K´* and *K* are chosen randomly, this can be an insurmountable problem.

The challenge-response portion of the protocol, steps (3) through (6), provides validation. Steps (3) through (5) prove to Alice that Bob knows *K;* steps (4) through (6) prove to Bob that Alice knows *K.* The Kerberos protocol timestamp exchange accomplishes the same thing.

EKE can be implemented with a variety of public-key algorithms: RSA, ElGamal, Diffie-Hellman. There are security problems with implementing EKE with a knapsack algorithm (aside from the inherent insecurity of knapsack algorithms): The normal distribution of the ciphertext messages negates the benefits of EKE.

*Implementing EKE with RSA*

The RSA algorithm seems perfect for this application, but there are some subtle problems. The authors recommend encrypting only the encryption exponent in step (1) and sending the modulus in the clear. An explanation of the reasoning behind this recommendation, as well as other subtleties involved in using RSA, is in [109].

*Implementing EKE with ElGamal*

Implementing EKE with the ElGamal algorithm is straightforward, and there is even a simplification of the basic protocol. Using the notation from Section 19.6, *g* and *p* are parts of the public key and are common to all users. The private key is a random number *r.* The public key is *g*^{r} mod *p.* The message Alice sends to Bob in step (1) becomes

- Alice,
*g*^{r}mod*p*

Note that this public key does not have to be encrypted with *P.* This is not true in general, but it is true for the ElGamal algorithm. Details are in [109].

Bob chooses a random number, *R* (for the ElGamal algorithm and independent of any random numbers chosen for EKE), and the message he sends to Alice in step (2) becomes

*E*_{P}(*g*^{R}mod*p, Kg*^{Rr}mod*p*)

Refer back to Section 19.6 for restrictions on choosing the variables for ElGamal.

*Implementing EKE with Diffie-Hellman*

With the Diffie-Hellman protocol, *K* is generated automatically. The final protocol is even simpler. A value for *g* and *n* is set for all users on the network.

**(1)**Alice picks a random number,*r*_{A}, and sends Bob*A,**g*mod^{rA}*n*

With Diffie-Hellman, Alice does not have to encrypt her first message with*P.***(2)**Bob picks a random number,*r*_{B,}and calculates*K*=*g*^{r}A*^{rB}mod*n*

He generates a random string*RB,*then calculates and sends Alice:*E*_{P}(*g*^{rB}mod*n*),*EK*(*RB*)

**(3)**Alice decrypts the first half of Bob’s message to obtain*g*^{r}B mod*n.*Then she calculates*K*and uses*K*to decrypt*R*_{B}. She generates another random string,*R*_{A}, encrypts both strings with*K,*and sends Bob the result.*E*_{K}(*R*_{A},*R*_{B})

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

**(5)**Alice decrypts the message to maintain*R*_{A}. Assuming the*R*_{A}she received from Bob is the same as the one she sent to Bob in step (3), the protocol is complete. Both parties now communicate using*K*as the session key.

*Strengthening EKE*

Bellovin and Merritt suggest an enhancement of the challenge-and-response portion of the protocol—to prevent a possible attack if a cryptanalyst recovers an old *K* value.

Look at the basic EKE protocol. In step (3), Alice generates another random number, *S*_{A}, and sends Bob

*E*_{K}(*R*_{A},*S*_{A})

In step (4), Bob generates another random number, *SB,* and sends Alice

*E*_{K}(*R*_{A},*R*_{B},*S*_{B})

Alice and Bob now can both calculate the true session key, *S*_{A} ⊕ *S*_{B}. This key is used for all future messages between Alice and Bob; *K* is just used as a key-exchange key.

Look at the levels of protection EKE provides. A recovered value of *S* gives Eve no information about *P,* because *P* is never used to encrypt anything that leads directly to *S.* A cryptanalytic attack on *K* is also not feasible; *K* is used only to encrypt random data, and *S* is never encrypted alone.

*Augmented EKE*

The EKE protocol suffers from one serious disadvantage: It requires that both parties possess the *P.* Most password-based authentication systems store a one-way hash of the user’s password, not the password itself (see Section 3.2). The Augmented EKE (A-EKE) protocol uses a one-way hash of the user’s password as the superencryption key in the Diffie-Hellman variant of EKE. The user then sends an extra message based on the original password; this message authenticates the newly chosen session key.

Previous | Table of Contents | Next |