Key agreement based on asymmetric techniques
Diffie-Heilman key agreement (also called exponential key exchange) is a fundamental technique providing unauthenticated key agreement. This section discusses key establishment protocols based on exponential key agreement, as well as the concept of implicitly- certified public keys and their use in Diffie-Helhnan protocols.
Diffie-Hellman and related key agreement protocols
This section considers the basic Diffie-Helhnan protocol and related protocols providing various authentication assurances (see Table 12.4).
(i) Diffie-Hellman key agreement
Diffie-Helhnan 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-Helhnan problem and the related problem of computing discrete logarithms (§3.6). The basic version (Protocol 12.47) provides protection in the form of secrecy of the resulting key from passive adversaries (eavesdroppers), but not from
-¥ Properties i Protocol |
key authentication |
entity authentication |
number of messages |
Diffie-Hellman |
none |
none |
2 |
ElGamal key agreement |
unilateral |
none |
1 |
MTI/AO |
mutual - implicit |
none |
2 |
Gunther (see Remark 12.63) |
mutual - implicit |
none |
2 |
STS |
mutual - explicit |
mutual |
3 |
Table 12.4: Selected key agreement protocols.
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.
12.47 Protocol Diffie-Hellman key agreement (basic version)
SUMMARY: A and В each send the other one message over an open channel.
RESULT: shared secret К known to both parties A and B.
- 1. One-time setup. An appropriate prime p and generator a of Z* (2 < a < p - 2) are selected and published.
- 2. Protocol messages.
- 3. Protocol actions. Perform the following steps each tune a shared key is required.
- (a) A chooses a random secret x, 1 < x < p — 2, and sends В message (1).
- (b) В chooses a random secret у, 1 < у < p - 2, and sends A message (2).
- (c) В receives a^{x} and computes the shared key as К = (a^{x})^{y} mod p.
- (d) A receives a^{v} and computes the shared key as К = (o^)* mod p.
- 12.48 Note (Diffie-Hellman with fixed exponentials) A variation of Protocol 12.47 provides mutual key authentication. Fix a^{x} and a^{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 К = a^{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; Protocol 12.53 provides one resolution. A second solution involves use of key update techniques as in §12.3. l(ii).
- 12.49 Remark (Diffie-Hellman in other groups) The Diffie-Hellman protocol, and those based on it, can be earned out in any group in which both the discrete logarithm problem is hard and exponentiation is efficient. The most common examples of such groups used in practice are the multiplicative group Z* of Z_{p}, the analogous multiplicative group of F2», and the group of points defined by an elliptic curve over a finite field.
- 12.50 Note (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 Z_{p} 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 a generates Z* where p = Rq + 1 (consider R = 2 and q prime). Then 3 = a^{q} = has order R
ф = -1 for R = 2). If A and В exchange unauthenticated short-term exponentials a^{x }and a^{y}, an adversary may replace these by (а^{ж})^{9} and (a^{y})^{q}, forcing the shared key to be К = a^{xyq} = (3^{xy}, which takes one of only R values (+1 or -1 for R = 2). К 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.
(ii) EIGamal key agreement in one-pass
ElGamal key agreement is a Diffie-Hellman variant providing a one-pass protocol with unilateral key authentication (of the intended recipient to the originator), provided the public key of the recipient is known to the originator a priori. While related to ElGamal encryption (§8.4), the protocol is more simply Diffie-Hellman key agreement wherein the public exponential of the recipient is fixed and has verifiable authenticity (e.g., is embedded in a certificate).
12.51 Protocol EIGamal key agreement (half-certified Diffie-Hellman)
SUMMARY: A sends to В a single message allowing one-pass key agreement. RESULT: shared secret К known to both parties A and B.
1. One-time setup (key generation and publication). Each user В does the following: Pick an appropriate prime p and generator a of Z*.
Select a random integer b, 1 < b < p - 2, and compute a^{b} mod p.
В publishes its public key (p, a, a^{b}), keeping private key b secret.
2. Protocol messages.
- 3. Protocol actions. Perform the following steps each time a shared key is required.
- (a) A obtains an authentic copy of B’s public key (p, a, a^{b}).
A chooses a random integer x, 1 < x < p - 2, and sends В message (1).
A computes the key as К = (a^{b})^{x} mod p.
- (b) В computes the same key on receipt of message (1) as К = (a^{x})^{b} mod p.
- 12.52 Remark (assurances in one-pass ElGamal) The recipient in Protocol 12.51 has no corroboration of whom it shares the secret key with, nor any key freshness assurances. Neither party obtains entity authentication or key confirmation.
- (iii) MTI two-pass key agreement protocols
The MTI/AO variant (Protocol 12.53) of Diffie-Hellman key agreement yields, in two messages (neither requiring signatures), time-variant session keys with mutual (implicit) key authentication against passive attacks. As in ElGamal key agreement (Protocol 12.51), A sends to В a single message, resulting in the shared key К. В independently initiates an analogous protocol with A, resulting in the shared key K'. Each of A and В then computes к = К К' mod p (p and a are global parameters now). Neither entity authentication nor key confirmation is provided. Although appropriate for applications where only passive attacks are possible, this protocol is vulnerable to certain active attacks (see Note 12.54).
12.53 Protocol MTI/AO key agreement
SUMMARY: two-pass Diffie-Heilman key agreement secure against passive attacks.
RESULT: shared secret К known to both parties A and B.
- 1. One-time setup. Select and publish (in a maimer guaranteeing authenticity) an appropriate system prime p and generator a of Z*. 2 < a < p — 2. A selects as a long-term private key a random integer a, 1 < a < p - 2, and computes a long-term public key z_{A} = «" mod p. (B has analogous keys b, zb-) A and В have access to authenticated copies of each other’s long-term public key.
- 2. Protocol messages.
- 3. Protocol actions. Perform the following steps each tune a shared key is required.
- (a) A chooses a random secret x, 1 < x < p — 2, and sends В message (1).
- (b) В chooses a random secret у, 1 < у < p - 2, and sends A message (2).
- (c) A computes the key к = (а^{у})^{а}гв^{х} mod p.
- (d) В computes the key к = (а^{х})^{ь}гл^{у} mod p. (Both parties now share the key
к = a^{bx+ay} mod p.)
Table 12.5 summarizes Protocol 12.53 and three related two-pass protocols. All four of these MTI protocols provide mutual key authentication without key confirmation or entity authentication, and are role-symmetric: each party executes directly analogous operations. The protocols are also message-independent per Definition 12.12 (neither party requires receipt of the other’s message before sending its own), although three of the four require a priori access to the other party’s authentic public key. The remaining protocol - MTI/AO - does not, and requires no additional passes (or communications delays) if this is not true; public keys may be exchanged e.g., via certificates included with the existing protocol messages. Thus in MTI/AO, the content of both messages sent is also independent (e.g., of the identity and public key) of the intended recipient.
IProtocol |
т_{А}в |
тел |
K_{A} |
Kb |
key К |
MTI/AO |
|||||
MTI/BO |
|||||
MTI/CO |
|||||
MTI/C1 |
Table 12.5: Selected MTI key agreement protocols. A and В have long-term secrets a and b, respectively, verifiably authentic corresponding long-tem public keys za = a“, zв - a^{6} mod p, and random per-session secrets x and y, respectively, тлв denotes the message A sends to В; твл is analogous. К a and Kb are the final key К as computed by A and B.
12.54 Note (source-substitution attack on MTI/AO) As a general rule in all public-key protocols (including Table 12.5), prior to accepting the authenticated public key of a party A, a party В should have assurance (either direct or through a trusted third party) that A actually knows the corresponding private key. Otherwise, an adversary C may claim ,1’s public key as its own, allowing possible attacks, such as that on MTI/AO as follows. Assume that in a particular implementation, A sends to В its certified public key in a certificate appended to message (1). C registers A’s public key as its own (legitimately proving its own identity to the certificate-creating party). When A sends В message (1), C replaces A’s certificate with its own, effectively changing the source indication (but leaving the exponential a^{x} sent by Л to В unchanged). C forwards B’s response a^{y} to A. В concludes that subsequently received messages encrypted by the key к = a^{bx+ay} originated from C, whereas, in fact, it is only A who knows к and can originate such messages.
A more complicated attack achieves the same, with C’s public key differing from A's public key za- C selects an integer e, computes (z_{y})^{e} = a^{ae}, and registers the public key a^{ae}. C then modifies a^{y} sent by В in message (2) to (a^{y})^{e}. A and В each compute the key к = a^{aey}a^{xb}, which A believes is shared with В (and is), while В believes it is shared with C.
In both variations, C is not actually able to compute к itself, but rather causes В to have false beliefs. Such attacks may be prevented by modifying the protocol such that the exponentials are authenticated (cf. Note 12.50), and binding key confirmation evidence to an authenticated source indication, e.g., through a digital signature (cf. Remark 12.58). The MTI protocols are, however, also subject to certain theoretical known-key attacks (see p.538).
- 12.55 Remark (implications of message independence) Protocols such as MTI/AO “leak” no information about long-term secrets, since the exchanged messages are independent thereof. However, such protocols in which each party’s message is independent of the other’s, and yet the session key depends on fresh input from each, cannot provide mutual explicit key authentication.
- 12.56 Remark (computational complexity’ of MTI protocols) The AO and Б0 protocols require 3 exponentiations by each party, whereas the CO and Cl protocols require only 2. Cl has the additional advantage over BO and CO that no inverses are needed; however, these fixed long-term values may be precomputed.
- (iv) Station-to-Station protocol (STS)
The following three-pass variation of the basic Diffie-Hellman protocol allows the establishment of a shared secret key between two parties with mutual entity authentication and mutual explicit key authentication. The protocol also facilitates anonymity - the identities of A and В may be protected from eavesdroppers. The method employs digital signatures; the description below is for the specific case of RSA signatures.
- 12.57 Protocol Station-to-Station protocol (STS) ^{[1]} {{ Notation. E is a symmetric encryption algorithm. Sa(m) denotes A’s signature on m, defined as: Sa(m) = (H(m))dA mod пд (i.e.,RSA preceded by an appropriate one-way hash function Я, H(m) < па)• 2. One-time setup (definition and publication of system parameters). (a) Select and publish an appropriate system prime p and generator a of Z*, 2 copies of the other’s public key (if not, certificates can be included in existing messages (2) and (3)).
- 3. Protocol messages.
4. Protocol actions. Perform the following steps each time a shared key is required.
The protocol is aborted (with failure) immediately upon any signature failure.
- (a) A generates a secret random x, 1 < x < p - 2, and sends В message (1).
- (b) В generates a secret random у, 1 < у < p — 2, and computes the shared key к = (a^{x})^{y} mod p. В signs the concatenation of both exponentials ordered as in (2), encrypts this using the computed key, and sends A message (2).
- (c) A computes the shared key к = (a^{!l})^{x} mod p, decrypts the encrypted data, and uses B’s public key to verify the received value as the signature on the hash of the cleartext exponential received and the exponential sent in message (1). Upon successful verification, A accepts that к is actually shared with B, and sends В an analogous message (3).
- (d) В similarly decrypts the received message (3) and verifies A’s signature therein. If successful, В accepts that к is actually shared with A.
The attack of Note 12.50 is precluded in the STS protocol due to the signatures over the exchanged exponentials.
- 12.58 Remark (key confirmation in STS protocol) Encryption under key к provides mutual key confirmation plus allows the conclusion that the party knowing the key is that which signed the exponentials. The optimal use of this protocol occurs when all subsequent messages are also to be encrypted under key к; if this is not the case, alternate means of key confirmation avoiding encryption may be preferable. One alternative is to use a MAC in messages (2) and
- (3), e.g., for .s = S_{A}(a^{x},a^{y}), A -» В : (s, MACjt(s)). A second alternative is inclusion of a one-way hash of к within the signed messages, e.g., A —> B : S_{A}(a^{x}, a^{y}, h(k)) where here h(k) may be replaced by к alone if the signature process itself employs an appropriate one-way hash.
- [1] SUMMARY: parties A and В exchange 3 messages. RESULT: key agreement, mutual entity authentication, explicit key authentication.