Here’s how it works. As usual, Alice and Bob want to authenticate each other and generate a common key. They agree on some digital signature scheme where any number can serve as the private key, and where the public key is derived from the private key, rather than being generated along with it. The ElGamal and DSA algorithms work well for this. Alice’s password P (or perhaps some simple hash of it) will serve as the private key and as P´.

(1)  Alice picks her random exponent R_a and transmits

E_P´(g^RA mod n)

(2)  Bob, who knows only P´ and cannot derive P from it, chooses R_b and sends

E_P´(g^RA mod n)

(3)  Both Alice and Bob calculate the shared session key K = g^rA*^rB mod n. Finally, Alice proves that she knows P itself, and not just P´, by sending

EK(SP(K))

Bob, who knows both K and P´, can decrypt and validate the signature. Only Alice could have sent this message, since only she knows P; an intruder who obtains a copy of Bob’s password file can try guessing at P, but cannot otherwise sign the session key.

The A-EKE scheme does not work with the public-key variant of EKE, since in it one party chooses the session key and imposes it on the other. This permits a man-in-the-middle attack by an attacker who has captured P´.

Applications of EKE

Bellovin and Merritt suggest using this protocol for secure public telephones [109]:

Let us assume that encrypting public telephones are deployed. If someone wishes to use one of these phones, some sort of keying information must be provided. Conventional solutions...require that the caller possess a physical key. This is undesirable in many situations. EKE permits use of a short, keypad-entered password, but uses a much longer session key for the call.

EKE would also be useful with cellular phones. Fraud has been a problem in the cellular industry; EKE can defend against it (and ensure the privacy of the call) by rendering a phone useless if a PIN has not been entered. Since the PIN is not stored within the phone, it is not possible to retrieve one from a stolen unit.

EKE’s primary strength is that both symmetric and public-key cryptography work together in a manner that strengthens them both:

From a general perspective, EKE functions as a privacy amplifier. That is, it can be used to strengthen comparatively weak symmetric and asymmetric systems when used together. Consider, for example, the key size needed to maintain security when using exponential key exchange. As LaMacchia and Odlyzko have shown [934], even modulus sizes once believed to be safe (to wit, 192 bits) are vulnerable to an attack requiring only a few minutes of computer time. But their attack is not feasible if one must first guess a password before applying it.

Conversely, the difficulty of cracking exponential key exchange can be used to frustrate attempts at password-guessing. Password-guessing attacks are feasible because of how rapidly each guess may be verified. If performing such verification requires solving an exponential key exchange, the total time, if not the conceptual difficulty, increases dramatically.

EKE is patented [111].

22.6 Fortified Key Negotiation

This scheme also protects key-negotiation schemes from poorly chosen passwords and man-in-the-middle attacks [47,983]. It uses a hash function of two variables that has a very special property: It has many collisions on the first variable while having effectively no collisions on the second variable.

H´(x, y) = H(H(k, x) mod 2^m, x),

where H(k, x) is an ordinary hash function on k and x

Here’s the protocol. Alice and Bob share a secret password, P, and have just exchanged a secret key, K, using Diffie-Hellman key exchange. They use P to check that their two session keys are the same (and that Eve is not attempting a man-in-the-middle attack), without giving P away to Eve.

(1)  Alice sends Bob

H´ (P, K)

(2)  Bob computes H´ (P, K) and compares his result with what he received from Alice. If they match he sends Alice

H´(H(P, K))

(3)  Alice computes H´ (H(P, K)) and compares her result with what she received from Bob.

If Eve is trying a man-in-the-middle attack, she shares one key, K₁, with Alice, and another key, K₂, with Bob. To fool Bob in step (2), she has to figure out the shared password and then send Bob H´ * (P, K₂). With a normal hash function she can try common passwords until she guesses the correct one, and then successfully infiltrate the protocol. But with this hash function, many passwords are likely to produce the same value when hashed with K₁. So when she finds a match, she will probably have the wrong password, and hence Bob will not be fooled.

22.7 Conference Key Distribution and Secret Broadcasting

Alice wants to broadcast a message, M, from a single transmitter. However, she doesn’t want it to be intelligible by every listener. In fact, she only wants a select subset of listeners to be able to recover M. Everyone else should get nonsense.

Alice can share a different key (secret or public) with each listener. She encrypts the message in some random key, K. Then she encrypts a copy of K with each of the keys of her intended recipients. Finally, she broadcasts the encrypted message and then all of the encrypted Ks. Bob, who is listening, either tries to decrypt all the Ks with his secret key, looking for one that is correct, or, if Alice doesn’t mind everyone knowing who her message is for, he looks for his name followed by an encrypted key. Multiple-key cryptography, previously discussed, also works.