5.3. Key Exchange

Consider the scenario wherein two parties Alice and Bob want to share a secret information (say, a DES key for future correspondence), but it is not possible to communicate this secret by personal contact or by conversing over a secure channel. In other words, Alice and Bob want to arrive at a common secret value by communicating over a public (and hence insecure) channel. A key-exchange or a key-agreement protocol allows Alice and Bob to do so. The protocol should be such that an eavesdropper listening to the conversation between Alice and Bob cannot compute the secret value in feasible time.

Public-key technology is used to design a key-exchange protocol in the following way. Alice generates a key pair (e_A, d_A) and sends the public key e_A to Bob. Similarly, Bob generates a random key pair (e_B, d_B) and sends the public key e_B to Alice. Now, Alice and Bob respectively compute the values s_A = f(e_B, d_A) and s_B = f(e_A, d_B) using their respective knowledges, where f is a suitably chosen function. If s_A = s_B, then this value can be used as the shared secret between Alice and Bob. The intruder Carol can intercept e_A and e_B, but f should be such that a knowledge of e_A and e_B alone does not allow Carol to compute s_A = s_B. She needs d_A or d_B for this computation. Since (e_A, d_A) and (e_B, d_B) are key pairs, we assume that it is infeasible to compute d_A from e_A or d_B from e_B.

In what follows, we describe some key-exchange protocols. The security of these protocols is dependent on the intractability of the DHP (or the DLP). We provide a generic description, where we work in a finite Abelian multiplicative group G of order n. We write the identity of G as 1. G need not be cyclic, but we assume that an element having suitably large (and preferably prime) multiplicative order m is provided. G, g, n and m may be made publicly available, but G should be a group in which one cannot compute discrete logarithms in feasible time. Typical examples of G are given in Section 5.2.5.

5.3.1. Basic Key-Exchange Protocols

Basic key-exchange protocols provide provable security against passive attacks under the intractability of the DHP. However, several models of active attacks are known for the basic protocols. One requires authentication (validation of the public keys) to eliminate these attacks.

The Diffie–Hellman key-exchange protocol

The Diffie–Hellman (DH) key-exchange algorithm [78] is one of the pioneering discoveries leading to the birth of public-key cryptography.

Algorithm 5.27. Diffie–Hellman key exchange

The DH scheme fails, if the shared secret turns out to be a trivial element (like the identity) of G. In that case, Alice and Bob should re-execute the protocol with different key pairs. The probability of such an incident is, however, extremely low.

The intruder Carol learns the group elements g^d_A and g^d_B by listening to the conversation between Alice and Bob and intends to compute s = g^d_Ad_B. Thus, she has to solve an instance of the DHP in the group G. By assumption, this is computationally infeasible. This is how the DH scheme derives its security.

Small-subgroup attacks

A small-subgroup attack on the DH protocol can be mounted by an active adversary. Assume that the order m of g in G is composite and has known factorization m = uv with u small. Carol intercepts the messages between Alice and Bob, replaces them by their respective v-th powers and retransmits the modified messages.

Algorithm 5.28. A small-subgroup attack by an active eavesdropper

But ord g = uv and so (s′)^u = 1, that is, s′ has only u – 1 non-trivial values. Since u is small, the possibilities for s′ can be exhaustively searched by Carol. The best countermeasure against this attack is to take m to be a prime (of bit length ≥ 160).

Even when m is prime, it may be the case that the cofactor k := n/m has a small divisor u and it is possible that an active attacker intervenes in such a way that Alice and Bob agree upon a secret value of order (equal to or dividing) u. For example, Carol may replace both the transmitted public keys by an element h of order u. If d_A and d_B are congruent modulo u, the shared secret has only a few possible values and Carol can obtain the correct value by exhaustive search. On the other hand, if d_A ≢ d_B (mod u), Alice and Bob do not come up with the same secret. However, if Alice uses her secret to encrypt a message for Bob, it remains easy for Carol to decrypt the intercepted ciphertext by trying only a few choices for Alice’s key. Alice and Bob can prevent this attack by refusing to accept as the shared secret not only the trivial value s = 1 but also elements of small orders.

A small-subgroup attack can also be mounted by one of the communicating parties (say, Bob) in an attempt to gain information about the other’s (Alice’s) secret d_A. Let us continue to assume that the cofactor k := n/m has a small divisor u. Bob finds an element h in G of order u. Instead of e_B = g^d_B Bob now sends h to Alice. Alice computes the shared secret as . Bob, on the other hand, can normally compute s_B := g^d_Ad_B. Now, suppose that Alice uses a symmetric cipher with the key (or some part of it) and sends the ciphertext to Bob. In order to decrypt, Bob tries all of the u possible keys s_Bh^j for j = 0, 1, . . . , u – 1. The value of j for which decryption succeeds equals d_A modulo u. A similar attack can be mounted by Bob, when is chosen to be an element (like h itself) of order u.

If G is cyclic and H is the subgroup generated by g, then an element is in H if and only if a^m = 1 (Proposition 2.5, p 27). Moreover, if gcd(k, m) = 1, each communicating party can check the validity of the other party’s public key by using an m-th power exponentiation. An element like h or h of the last paragraph does not pass this test. If so, Alice should abandon the protocol. However, the validation of the public key requires a modular exponentiation and thereby slows down the protocol.

Cofactor exponentiation

We now present an efficient modification of the basic Diffie–Hellman scheme that prevents small-subgroup attacks (by a communicating party or an eavesdropper) without calculating an extra exponentiation. We continue with the notation k := n/m and assume that k is coprime to m. Now, the shared secret is computed as g^d_Ad_B or g^kd_Ad_B depending on whether compatibility with the original DH scheme is desired or not. Algorithm 5.29 describes the modified DH algorithm. Solve Exercise 5.12 in order to establish the effectiveness of this algorithm against small-subgroup attacks.

5.3.2. Authenticated Key-Exchange Protocols

Other active attack models on the (basic or modified) DH protocol can be conceived of. One important class of attacks is now described.

Unknown key-share attacks

An unknown key-share attack on a key-exchange protocol makes a party believe that (s)he shares a secret with another party, whereas the secret is actually shared by a third party. Assume that Carol can monitor and modify every message between Alice and Bob. When Alice and Bob execute Algorithm 5.27 or 5.29, Carol can intervene and pretend to Alice that she is Bob and to Bob that she is Alice. At the end of the protocol, Alice and Carol come up with a shared secret s_AC, and Bob and Carol with another shared secret s_BC. Alice believes that she shares s_AC with Bob, and Bob believes that he shares s_BC with Alice.

Algorithm 5.29. Diffie–Hellman key exchange with cofactor exponentiation

Now, when Alice wants to send a secret message m to Bob, she encrypts m by s_AC and transmits the ciphertext c. Carol intercepts c, decrypts it by s_AC to retrieve m, encrypts m by s_BC and sends the new ciphertext c′ to Bob. Bob retrieves m by decrypting c′ with his key s_BC. The process raises hardly any suspicion in Alice or Bob about the existence of the mediating third party.

In order to avoid this attack, Alice and Bob should each validate the authenticity of the public key of the other party. Public-key certificates can be used to this effect. Unfortunately, using certificates alone may fail to eliminate unknown key-share attacks, as Algorithm 5.30 shows. At the end of this protocol Alice and Bob share a secret s, but Bob believes that he shares it with (the intruder) Carol. Here Carol herself cannot compute the shared secret s (provided that computing discrete logs in G is infeasible). Still there may be situations where this attack can be exploited (see Law et al. [161] for a hypothetical example).

This attack has two potential problems. Under the assumption of intractability of the DLP in G, Carol cannot compute the private key corresponding to the public key e_C and so her getting the certificate Cert_C knowing e_C alone may be questioned. Furthermore, replacing (e_B, Cert_B) to ((e_B)^d, Cert_B) may make the certificate invalid. If we assume that a certificate authenticates only the entity and not the public key, then these objections can be overruled. In practice, however, a public key certificate should bind the public key to an entity (who can prove the knowledge of the corresponding private key) and so the above attack cannot be easily mounted. Nonetheless, the need for stronger authenticated key-exchange protocols is highlighted by the attack.

Algorithm 5.30. An unknown key-share attack

The Menezes–Qu–Vanstone key-exchange protocol

The Menezes–Qu–Vanstone (MQV) key-exchange protocol is an improved extension of the basic DH scheme, that incorporates public-key authentication. Though the achievement of the desired security goals by the MQV protocol does not seem to be provable, heuristic arguments suggest the effectiveness of the protocol against active adversaries.

Once again, let Alice and Bob be the two parties who plan to agree on a secret element , where the domain parameters G, g, n and m are chosen as in the basic DH scheme. In the MQV scheme, each entity uses two key pairs, one of which ((E_A, D_A) for Alice and (E_B, D_B) for Bob) is called the static or the long-term key pair, whereas the other ((e_A, d_A) for Alice and (e_B, d_B) for Bob) is called the ephemeral or the short-term key pair. The static key is bound to an entity for a certain period of time and is used in every invocation of the MQV protocol during that period. On the other hand, each entity generates and uses a new ephemeral key pair during each invocation of the protocol. The static key of an entity is assumed to be authentic, say, certified by a trusted authority. The ephemeral key, on the other hand, is validated using the static private key.

Assume that there is a (publicly known) function . Let l := ⌊lg m⌋ + 1 denote the bit length of m = ord g. For , let denote the integer . The bit size of is about half of that of m. In particular, (mod m) for all .

In the MQV protocol, Alice and Bob each computes the shared secret s = g^σ_Aσ_B, where and . Here the exponents σ_A and σ_B bear the implicit signatures of Alice and Bob, impressed by their respective static private keys. Alice can compute , since she knows the static public key E_B and the ephemeral public key e_B of Bob. Similarly, Bob can compute from a knowledge of the public keys E_A and e_A of Alice. We summarize the steps in Algorithm 5.31.

Algorithm 5.31. MQV key exchange

Each participating entity using the MQV protocol performs three exponentiations in G. Alice computes g^d_A, and , of which the first and the last ones have exponents O(m). On the other hand, is , so that the middle exponentiation is about twice as fast as a full exponentiation. This performance benefit justifies the use of and instead of e_A and e_B themselves. It appears that using these half-sized exponents does not affect security. Also note that (mod m), which implies a non-zero contribution of the static key D_A in the expression σ_A. Similarly for σ_B.

In order to guard against small-subgroup attacks, the MQV algorithm can incorporate the cofactor k := n/m, that is, assuming gcd(k, m) = 1, the shared secret would now be g^σ_Aσ_B or g^kσ_Aσ_B, depending on whether compatibility with the original MQV method is desired or not.

The MQV algorithm can be used in a situation when only one party, say, Alice, is capable of initiating a transmission to the other party (Bob). In that case, Bob’s static key pair is used also as his ephemeral key pair, that is, the secret element shared between Alice and Bob is .

See Raymond and Stiglic [250] to know more about the security issues for the DH key agreement protocol and its variants.

Exercise Set 5.3

5.12	Let G be a multiplicative Abelian group of order n and with identity 1, H the subgroup of G generated by an element of order n, k := n/m and gcd(k, m) = 1. Further let a be a non-identity element of G. Prove that if ak = 1, then a ∉ H. (The converse of this statement is not true in general, even when G is cyclic. However, if a is an element of small order dividing k, we obviously have ak = 1.) Explain how the modified Diffie–Hellman protocol (Algorithm 5.29) prevents an active attack by Bob described in connection with small-subgroup attacks.
5.13	Write the MQV key-exchange protocol with cofactor exponentiation.
5.14	Provide the details of the Diffie–Hellman key-exchange algorithm based on the XTR representation (Section 5.2.7).