Symmetric Key Distribution using Asymmetric Encryption

Because of the inefficiency of public-key cryptosystems, they are almost never used for the direct encryption of sizable blocks of data, but are limited to relatively small blocks. One of the most important uses of a public-key cryptosystem is to encrypt secret keys for distribution. Here, we discuss general principles and typical approaches.

Simple Secret Key Distribution

An extremely simple scheme was put forward by Merkle, as illustrated in Figure 14.7. If $A$ wishes to communicate with $B$, the following procedure is employed:

1. $A$ generates a public/private key pair ${PU_a, PR_a}$ and transmits a message to $B$ consisting of $PU_a$ and an identifier of $A, ID_A$.

2. $B$ generates a secret key, $K_s$, and transmits it to $A$, which is encrypted with $A$’s public key.

3. $A$ computes $D(PR_a, E(PU_a, K_s))$ to recover the secret key. Because only $A$ can decrypt the message, only $A$ and $B$ will know the identity of $K_s$.

4. $A$ discards $PU_a$ and $PR_a$ and $B$ discards $PU_a.$

$A$ and $B$ can now securely communicate using conventional encryption and the session key $K_s$. At the completion of the exchange, both $A$ and $B$ discard $K_s.$ Despite its simplicity, this is an attractive protocol. No keys exist before the start of the communication and none exist after the completion of communication. Thus, the risk of compromise of the keys is minimal. At the same time, the communication is secure from eavesdropping.

The protocol depicted in Figure 14.7 is insecure against an adversary who can intercept messages and then either relay the intercepted message or substitute another message. Such an attack is known as a man-in-the-middle attack. In present case, if an adversary, $D$, has control of the intervening communication channel, then $D$ can compromise the communication in the following fashion without being detected (Figure 14.8).

1. $A$ generates a public/private key pair $\{PU_a, PR_a\}$ and transmits a message intended for $B$ consisting of $PU_a$ and an identifier of $A, ID_A.$

2. $D$ intercepts the message, creates its own public/private key pair $\{PU_d, PR_d\}$ and transmits $PU_d ||ID_A$ to $B.$

3. $B$ generates a secret key, $K_s$, and transmits $E(PU_d, K_s).$

4. $D$ intercepts the message and learns $K_s$ by computing $D(PR_d, E(PU_d, K_s)).$

5. $D$ transmits $E(PU_a, K_s)$ to $A.$

The result is that both $A$ and $B$ know $K_s$ and are unaware that $K_s$ has also been revealed to $D$. $A$ and $B$ can now exchange messages using $K_s$. $D$ no longer actively interferes with the communications channel but simply eavesdrops. Knowing $K_s$, $D$ can decrypt all messages, and both $A$ and $B$ are unaware of the problem. Thus, this simple protocol is only useful in an environment where the only threat is eavesdropping.

Secret Key Distribution with Confidentiality and Authentication

Figure 14.9, based on an approach suggested by Needham et al, provides protection against both active and passive attacks. We begin at a point when it is assumed that $A$ and $B$ have exchanged public keys.

1. $A$ uses $B$’s public key to encrypt a message to $B$ containing an identifier of $A(ID_A)$ and a nonce $(N_1$), which is used to identify this transaction uniquely.

2. $B$ sends a message to $A$ encrypted with $PU_a$ and containing $A$’s nonce ($N_1$) as well as a new nonce generated by $B (N_2)$. Because only $B$ could have decrypted message (1), the presence of $N_1$ in message (2) assures $A$ that the correspondent is $B.$

3. $A$ returns $N_2$, encrypted using $B$’s public key, to assure $B$ that its correspondent is $A.$

4. $A$ selects a secret key $K_s$ and sends $M = E(PU_b, E(PR_a, K_s))$ to $B$. Encryption of this message with $B$’s public key ensures that only $B$ can read it; encryption with $A’$ s private key ensures that only $A$ could have sent it.

5. $B$ computes $D(PU_a, D(PR_b, M)) $to recover the secret key.

The result is that this scheme ensures both confidentiality and authentication in the exchange of a secret key.

A Hybrid Scheme

Yet another way to use public-key encryption to distribute secret keys is a hybrid approach in use on IBM mainframes . This scheme retains the use of a key distribution center (KDC) that shares a secret master key with each user and distributes secret session keys encrypted with the master key. A public-key scheme is used to distribute the master keys. The following rationale is provided for using this three-level approach:

■ Performance: There are many applications, especially transaction-oriented applications, in which the session keys change frequently. Distribution of session keys by public-key encryption could degrade overall system performance because of the relatively high computational load of public-key encryption and decryption. With a three-level hierarchy, public-key encryption is used only occasionally to update the master key between a user and the KDC.

■ Backward compatibility: The hybrid scheme is easily overlaid on an existing KDC scheme with minimal disruption or software changes.

The addition of a public-key layer provides a secure, efficient means of distributing master keys. This is an advantage in a configuration in which a single KDC serves a widely distributed set of users.