Better to know some
... than all
Key agreement based on asymmetric techniques
Diffie-Hellman key agreement (also called exponential key exchange) is a fundamental technique providing unauthenticated key agreement. This discusses key establishment protocols based on exponential key agreement, as well as the concept of implicitly certified public keys and their use in Diffie-Hellman protocols.
Diffie-Hellman key agreement protocols
Diffie-Hellman key agreement provided the first practical solution to the key distribution problem, allowing two parties, never having met in advance or shared keying material, to establish a shared secret by exchanging messages over an open channel. The security rests on the intractability of the Diffie-Hellman problem and the related problem of computing discrete logarithms. The basic version provides protection in the form of secrecy of the resulting key from passive adversaries (eavesdroppers), but not from active adversaries capable of intercepting, modifying, or injecting messages. Neither party has assurances of the source identity of the incoming message or the identity of the party which may know the resulting key, i.e., entity authentication or key authentication.
Protocol Diffie-Hellman key agreement (basic version)
SUMMARY: A and B each send the other one message over an open channel.
RESULT: shared secret K known to both parties A and B.
1. One-time setup. An appropriate prime p and generator of Z* p (2 p - 2) are selected and published.
A B : x mod p (1)
2. Protocol messages.
A B : y mod p (2)
3. Protocol actions. Perform the following steps each time a shared key is required.
(a) A chooses a random secret x, 1 x p - 2, and sends B message (1).
(b) B chooses a random secret y, 1 y p - 2, and sends A message (2).
(c) B receives x and computes the shared key as K = (x)y mod p.
(d) A receives y and computes the shared key as K = (y)x mod p.
Diffie-Hellman with fixed exponentials: A variation of Protocol provides mutual key authentication. Fix x and y mod p as long-term public keys of the respective parties, and distribute these using signed certificates, thus fixing the long-term shared key for this user pair to K = xy. If such certificates are available a priori, this becomes a zero pass key agreement (no cryptographic messages need be exchanged). The time-invariant nature of this key K, however, is a drawback.
Diffie-Hellman in other groups: The Diffie-Hellman protocol, and those based on it, can be carried out in any group in which both the discrete logarithm problem is hard and exponentiation is efficient. Themost commonexamples of such groups used in practice are the multiplicative group Z*p of Zp, the analogous multiplicative group of F2m, and the group of points defined by an elliptic curve over a finite field.
Control over Diffie-Hellman key: While it may appear as though Diffie-Hellman key agreement allows each party to guarantee key freshness and preclude key control, use of an exponential with small multiplicative order restricts the order (and thereby value) of the overall key. The most degenerate case for Zp would be selection of 0 as private exponent, yielding an exponential with order 1 and the multiplicative identity itself as the resulting key. Thus, either participant may force the resulting key into a subset of the original (naively assumed) range set. Relatedly, some variants of Diffie-Hellman involving unauthenticated exponentials are vulnerable to the following active attack. Assume generates Z*p where p = Rq + 1 (consider R = 2 and q prime). Then = q = (p-1)/R has order R ( = -1 for R = 2). If A and B exchange unauthenticated short-term exponentials x and y, an adversary may replace these by (x)q and (y)q, forcing the shared key to be K = xyq = xy, which takes one of only R values (+1 or -1 for R = 2). K may thus be found by exhaustive trial of R values. A more direct attack involves simply replacing the exchanged exponentials by +1 or p - 1 = - 1. This general class of attacks may be prevented by authenticating the exchanged exponentials, e.g., by a digital signature.