|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´), EP(EK´(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 .
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 gr mod p. The message Alice sends to Bob in step (1) becomes
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 .
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
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.
Bellovin and Merritt suggest an enhancement of the challenge-and-response portion of the protocolto 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, SA, and sends Bob
In step (4), Bob generates another random number, SB, and sends Alice
Alice and Bob now can both calculate the true session key, SA ⊕ SB. 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.
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 users password, not the password itself (see Section 3.2). The Augmented EKE (A-EKE) protocol uses a one-way hash of the users 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|