Key transport based on symmetric encryption
This section presents a selection of key establishment protocols based on key transport (i.e., transfer of a specific key chosen о priori by one party) using symmetric encryption. Related techniques involving non-reversible functions are also presented. Discussion is subdivided into protocols with and without the use of a trusted server, as summarized in Table 12.2. Some of these use time-variant parameters (timestamps, sequence numbers, or random numbers) or nonces as discussed in §10.3.1.
-¥ Properties i Protocol |
server type |
use of timestamps |
number of messages |
point-to-point key update |
none |
optional |
1-3 |
Shamir’s no-key protocol |
none |
no |
3 |
Kerberos |
KDC |
yes |
4 |
Needham-Schroeder shared-key |
KDC |
no |
5 |
Otway-Rees |
KDC |
no |
4 |
Protocol 13.12 |
KTC |
no |
3 |
Table 12.2: Key transport protocols based on symmetric encryption.
Symmetric key transport and derivation without a server
Server-less key transport based on symmetric techniques may either require that the two parties in the protocol initially share a long-term pairwise secret or not, respectively illustrated below by point-to-point key update techniques and Shamir’s no-key algorithm. Other illustrative techniques are also given.
(i) Point-to-point key update using symmetric encryption
Point-to-point key update techniques based on symmetric encryption make use of a longterm symmetric key К shared a priori by two parties A and B. This key, initially distributed over a secure channel or resulting from a key pre-distribution scheme (e.g., see Note 12.48), is used repeatedly to establish new session keys W. Representative examples of point-to- point key transport techniques follow.
Notation: гд, t-л, and пд, respectively, denote a random number, timestamp, and sequence number generated by A (see § 10.3.1). E denotes a symmetric encryption algorithm (see Remark 12.19). Optional message fields are denoted by an asterisk (*).
1. key transport with one pass:
The session key used is W = г д , and both A and В obtain implicit key authentication. Additional optional fields which might be transferred in the encrypted portion include: a timestamp or sequence number to provide a freshness guarantee to В (see Remark 12.18); a field containing redundancy, to provide explicit key authentication to В or facilitate message modification detection (see Remark 12.19); and a target identifier to prevent undetectable message replay back on A immediately. Thus:
If it is desired that both parties contribute to the session key, В may send A an analogous message, with the session key computed as f(r_{A}, гд). Choosing / to be a oneway function precludes control of the final key value by either party, or an adversary' who acquires one of r_{A}, гв-
2. key transport with challenge-response:
If a freshness guarantee is desired but reliance on timestamps is not, a random number or sequence number, denoted пв here, may be used to replace the timestamp in the one-pass technique; the cost is an additional message. The session key is again W =
Г A-
If it is required that the session key W be a function of inputs from both parties, A may insert a nonce n_{A} preceding n/j in (2), and a thud message may be added as below. (Here г_{А},гв are random numbers serving as keying material, while n_{A}, пв are nonces for freshness.)
- 12.18 Remark (key update vulnerabilities) The key update techniques above do not offerperfect forward secrecy, and fail completely if the long-term key К is compromised. For this reason they may be inappropriate for many applications. The one-pass protocol is also subject to replay unless a timestamp is used.
- 12.19 Remark (integrity guarantees within encryption) Many authentication protocols which employ encryption, including the above key update protocols and Protocols 12.24, 12.26, and 12.29, require for security reasons that the encryption function has a built-in data integrity mechanism (see Figirre 9.8(b) for an example, and Definition 9.75) to detect message modification.
- (ii) Point-to-point key update by key derivation and non-reversible functions
Key irpdate may be achieved by key transport as above, or by key derivation wherein the derived session key is based on per-session random input provided by one party. In this case, there is also a single message:
The session key is computed as W = Ек{г_{А}). The technique provides to both A and В implicit key authentication. It is, however, susceptible to known-key attacks; Remark 12.18 similarly applies. The random number r_{A} here may be replaced by other time-variant parameters; for example, a timestamp t_{A} validated by the recipient by comparison to its local clock provides an implicit key freshness property, provided the long-term key is not compromised.
Here A could control the value of W, forcing it to be x by choosing r_{A} = Dk(x). Since the technique itself does not require decryption, E may be replaced by an appropriate keyed pseudorandom function 1гк, hi which case the session key may be computed as W = Ьк(та), with r_{A} a time-variant parameter as noted above.
hi the other techniques of §12.3.1(i) employing an encryption function E, the confidentiality itself of the encrypted fields other than the session key W is not critical. A key derivation protocol which entirely avoids the use of an encryption function may offer potential advantages with respect to export restrictions. Protocol 12.20 is such a technique, which also provides authentication guarantees as stated. It uses two distinct functions h and h' (generating outputs of different bitlengths), respectively, for message authentication and key derivation.
12.20 Protocol Authenticated Key Exchange Protocol 2 (AKEP2)
SUMMARY: A and В exchange 3 messages to derive a session key W.
RESULT: mutual entity authentication, and implicit key authentication of W.
- 1. Setup: A and В share long-term symmetric keys К, K' (these should differ but need not be independent), h к is a MAC (keyed hash function) used for entity authentication. h'_{K}, is a pseudorandom permutation or keyed one-way function used for key derivation.
- 2. Protocol messages. Define Г = (В. A, г a,г в)-
- 3. Protocol actions. Perform the following steps for each shared key required.
- (a) A selects and sends to В a random number r a-
- (b) В selects a random number tb and sends to A the values (В. А, га ■ гв), along with a MAC over these quantities generated using h with key K.
- (c) Upon receiving message (2), A checks the identities are proper, that the r_{A} received matches that in (1), and verifies the MAC.
- (d) A then sends to В the values {А, гв), along with a MAC thereon.
- (e) Upon receiving (3), В verifies that the MAC is correct, and that the received value гв matches that sent earlier.
- (f) Both A and В compute the session key as W = 1г'_{к},(гв).
- 12.21 Note (AKEP1 variant of Protocol 12.20) The following modification of AKEP2 results in AKEP1 (Authenticated Key Exchange Protocol 1). В explicitly generates a random session key W and probabilistically encrypts it using h' under K' and random number r. The quantity (r, W®h'_{K},{r)) is now included as a final extra field within T and hx(T) in (2), and from which A may recover W. As an optimization, r = r_{B}-
- (iii) Key transport without a priori shared keys
Shamir’s no-key algorithm (Protocol 12.22) is a key transport protocol which, using only symmetric techniques (although involving modular exponentiation), allows key establishment over an open channel without requiring either shared or public keys. Each party has only its own local symmetric key. The protocol provides protection from passive adversaries only; it does not provide authentication. It thus solves the same problem as basic
Diffie-Hellman (Protocol 12.47) - two parties sharing no a priori keying material end up with a shared secret key, secure against passive adversaries - although differences include that it uses three messages rather than two, and provides key transport.
12.22 Protocol Shamir’s no-key protocol
SUMMARY: users A and В exchange 3 messages over a public channel.
RESULT: secret К is transferred with privacy (but no authentication) from A to В.
- 1. One-time setup (definition and publication of system parameters).
- (a) Select and publish for common use a prime p chosen such that computation of discrete logarithms modulo p is infeasible (see Chapter 3).
- (b) A and В choose respective secret random numbers a, b, with 1 < a, b < p - 2, each coprime to p - 1. They respectively compute a^{-1} and l> ^{1} mod p - 1.
- 2. Protocol messages.
- 3. Protocol actions. Perform the following steps for each shared key required.
- (a) A chooses a random key К for transport to В, 1 < К < p — 1. A computes K^{a} mod p and sends В message (1).
- (b) В exponentiates (mod p) the received value by b, and sends A message (2).
- (c) A exponentiates (mod p) the received value by a ~ ^{1} mod p — 1, effectively “undoing” its previous exponentiation and yielding K^{b} mod p. A sends the result to В as message (3).
- (d) В exponentiates (mod p) the received value by 6^{_1} mod p — 1, yielding the newly shared key К mod p.
Use of ElGamal encryption for key transport (as per §12.5.1) with an uncertified public key sent in a first message (which would by definition be safe from passive attack) achieves in two passes the same goals as the above three-pass algorithm. In this case, the key is transported from the recipient of the first message to the originator.
12.23 Remark (choice of cipher in Protocol 12.22) While it might appear that any commutative cipher (i.e., cipher wherein the order of encryption and decryption is interchangeable) would suffice in place of modular exponentiation in Protocol 12.22, caution is advised. For example, use of the Vemam cipher (§1.5.4) would be totally insecure here, as the XOR of the three exchanged messages would equal the key itself.