In the simplest version of this protocol, if Alice wants to communicate with Bob, the keys or key schedules (lists describing which keys to use at which times) are decided upon in advance and somehow this information is sent securely from one to the other. For example, this method was used by the German navy in World War II. However, the British were able to use codebooks from captured ships to find daily keys and thus read messages.

There are some obvious limitations and drawbacks to pre-distribution. First, it requires two parties, Alice and Bob, to have met or to have established a secure channel between them in the first place. Second, once Alice and Bob have met and exchanged information, there is nothing they can do, other than meeting again, to change the key information in case it gets compromised. The keys are predetermined and there is no easy method to change the key after a certain amount of time. When using the same key for long periods of time, one runs a risk that the key will become compromised. The more data that are transmitted, the more data there are with which to build statistical attacks.

Here is a general and slightly modified situation. First, we require a trusted authority whom we call Trent. For every pair of users, call them $(A\text{,}B)$, Trent produces a random key $K_{AB}$ that will be used as a key for a symmetric encryption method (hence $K_{BA}=K_{AB}$). It is assumed that Trent is powerful and has established a secure channel to each of the users. He distributes all the keys that he has determined to his users. Thus, if Trent is responsible for $n$ users, each user will be receiving $n-1$ keys to store, and Trent must send $n(n-1)/2$ keys securely. If $n$ is large, this could be a problem. The storage that each user requires is also a problem.

One method for reducing the amount of information that must be sent from the trusted authority is the Blom key pre-distribution scheme. Start with a network of $n$ users, and let $p$ be a large prime, where $p\ge n$. Everyone has knowledge of the prime $p$. The protocol is now the following:

1. Each user $U$ in the network is assigned a distinct public number $r_U(\text{mod}p)$.

2. Trent chooses three secret random numbers $a\text{,}b\text{,}$ and $c\text{ mod }p$.

3. For each user $U$, Trent calculates the numbers

   $$\begin{array}{cc}{a}_U\equiv a+b{r}_U& (\text{mod}p)\end{array}\begin{array}{cc}{b}_U\equiv b+c{r}_U& (\text{mod}p)\end{array}$$

   and sends them via his secure channel to $U$.

4. Each user $U$ forms the linear polynomial

   $$g_U(x)=a_U+b_{U}x\text{.}$$

5. If Alice (A) wants to communicate with Bob (B), then Alice computes $K_{AB}=g_A\left(r_B\right)$, while Bob computes $K_{BA}=g_B\left(r_A\right)$.

6. It can be shown that $K_{AB}=K_{BA}$ (Exercise 2). Alice and Bob communicate via a symmetric encryption system, for example, AES, using the key (or a key derived from) $K_{AB}$.

If the two users Eve and Oscar conspire, they can determine $a$, $b$, and $c$ and therefore find all numbers $a_A\text{,}{b}_A$ for all users. They proceed as follows. They know the numbers $a_E\text{,}{b}_E\text{,}{a}_O\text{,}{b}_O$. The defining equations for the last three of these numbers can be written in matrix form as

The determinant of the matrix is $r_E-r_O$. Since the numbers $r_A$ were chosen to be distinct mod $p$, the determinant is nonzero mod $p$ and therefore the system has a unique solution $a\text{,}b\text{,}c$.

Without Eve’s help, Oscar has only a $2\times 3$ matrix to work with and therefore cannot find $a\text{,}b\text{,}c$. In fact, suppose he wants to calculate the key $K_{AB}$ being used by Alice and Bob. Since $K_{AB}\equiv a+b(r_A+r_B)+c(r_A{r}_B)$ (see Exercise 2), there is the matrix equation

The matrix has determinant $(r_O-r_A)(r_O-r_B)\cancel{\equiv }0(\text{mod }p)$. Therefore, there is a solution $a\text{,}b\text{,}c$ for every possible value of $K_{AB}$. This means that Oscar obtains no information about $K_{AB}$.

For each $k\ge 1$, there are Blom schemes that are secure against coalitions of at most $k$ users, but which succumb to conspiracies of $k+1$ users. See [Blom].

Key pre-distribution schemes are often impractical because they require significant resources to initialize and do not allow for keys to be changed or replaced easily when keys are deemed no longer safe. One way around these problems is to introduce a trusted authority, whose task is to distribute new keys to communicating parties as they are needed. This trusted third party may be a server on a computer network, or an organization that is trusted by both Alice and Bob to distribute keys securely.

Authentication is critical to key distribution. Alice and Bob will ask the trusted third party, Trent, to give them keys. They want to make certain that there are no malicious entities masquerading as Trent and sending them false key messages. Additionally, when Alice and Bob exchange messages with each other, they will each need to make certain that the person they are talking to is precisely the person they think they are talking to.

One of the main challenges facing key distribution is the issue of replay attacks. In a replay attack, an opponent may record a message and repeat it at a later time in hope of either pretending to be another party or eliciting a particular response from an entity in order to compromise a key. To provide authentication and protect against replay attacks, we need to make certain that vital information, such as keys and identification parameters, are kept confidential. Additionally, we need to guarantee that each message is fresh; that is, it isn’t a repeat of a message from a long time ago.

The task of confidentiality can be easily accomplished using existing keys already shared between entities. These keys are used to encrypt messages used in the distribution of session keys and are therefore often called key encrypting keys. Unfortunately, no matter how we look at it, there is a chicken-and-egg problem: In order to distribute session keys securely, we must assume that entities have already securely shared key encrypting keys with the trusted authority.

To handle message freshness, however, we typically need to attach extra data fields in each message we exchange. There are three main types of data fields that are often introduced in order to prevent replay attacks:

• Sequence numbers: Each message that is sent between two entities has a sequence number associated with it. If an entity ever sees the same sequence number again, then the entity concludes that the message is a replay. The challenge with sequence numbers is that it requires that each party keep track of the sequence numbers it has witnessed.

• Timestamps: Each message that is sent between two entities has a statement of the time period for when that message is valid. This requires that both entities have clocks that are set to the same time.

• Nonces: A nonce is a random message that is allowed to be used only once and is used as part of a challenge-response mechanism. In a challenge-response, Alice sends Bob a message involving a nonce and requires Bob to send back a correct response to her nonce.

We will now look at two examples of key distribution schemes and analyze attacks that may be used against each in order to bypass the intended security. These two examples should highlight how difficult it is to distribute keys securely.

We begin with a protocol known as the wide-mouthed frog protocol, which is one of the simplest symmetric key management protocols involving a trusted authority. In this protocol, Alice chooses a session key $K_{AB}$ to communicate with Bob and has Trent transfer it to Bob securely:

1. $\text{Alice}\to \text{Trent}:E_{K_{AT}}\left[t_A\parallel I{D}_B\parallel K_{AB}\right]$.

2. $\text{Trent}\to \text{Bob}:E_{K_{BT}}\left[t_T\parallel I{D}_A\parallel K_{AB}\right]$.

Here, $K_{AT}$ is a key shared between Alice and Trent, while $K_{BT}$ is a key shared between Bob and Trent. Alice’s and Bob’s identifying information are given by $I{D}_A$ and $I{D}_B$, respectively. The parameter $t_A$ is a timestamp supplied by Alice, while $t_T$ is a timestamp given by Trent. It is assumed that Alice, Trent, and Bob have synchronized clocks. Bob will accept $K_{AB}$ as fresh if it arrives within a window of time. The key $K_{AB}$ will be valid for a certain period of time after $t_T$.

The purpose behind the two timestamps is to allow Bob to check to see that the message is fresh. In the first message, Alice sends a message with a timestamp $t_A$. If Trent gets the message and the time is not too far off from $t_A$, he will then agree to translate the message and deliver it to Bob.

The problem with the protocol comes from the second message. Here, Trent has updated the timestamp to a newer timestamp $t_T$. Unfortunately, this simple change allows for a clever attack in which the nefarious Mallory may cause Trent to extend the lifetime of an old key. Let us step through this attack.

1. After seeing one exchange of the protocol, Mallory pretends to be Bob wanting to share a key with Alice. Mallory sends Trent the replay $E_{K_{BT}}\left[t_T\parallel I{D}_A\parallel K_{AB}\right]$.

2. Trent sends $E_{K_{AT}}\left[t_T^{{}^{\prime }}\parallel I{D}_B\parallel K_{AB}\right]$ to Alice, with a new timestamp $t_T^{{}^{\prime }}$. Alice thinks this is a valid message since it came from Trent and was encrypted using Trent’s key. The key $K_{AB}$ will now be valid for a period of time after $t_T^{{}^{\prime }}$.

3. Mallory then pretends to be Alice and gets $E_{K_{BT}}\left[t_T^{{}^{\prime \prime }}\parallel I{D}_A\parallel K_{AB}\right]$. The key $K_{AB}$ will now be valid for a period of time after $t_T^{{}^{\prime \prime }}>t_T^{{}^{\prime }}$.

4. Mallory continues alternately playing Trent against Bob and then Trent against Alice.

The net result is that the malicious Mallory can use Trent as an agent to force Alice and Bob to continue to use $K_{AB}$ indefinitely. Of course, Alice and Bob should keep track of the fact that they have seen $K_{AB}$ before and begin to suspect that something suspicious is going on when they repeatedly see $K_{AB}$. The protocol did not explicitly state that this was necessary, however, and security protocols should be very explicit on what it is that they assume and don’t assume. The true problem, though, is the fact that Trent replaces $t_A$ with $t_T$. If Trent had not changed $t_T$ and instead had left $t_A$ as the timestamp, then the protocol would have been better off.

Another example of an authenticated key exchange protocol is due to Needham and Schroeder. In the Needham–Schroeder protocol, Alice and Bob wish to obtain a session key $K_S$ from Trent so that they can talk with each other. The protocol involves the following steps:

1. $\text{Alice}\to \text{Trent}:I{D}_A\parallel I{D}_B\parallel r_1$

2. $\text{Trent}\to \text{Alice}:E_{K_{AT}}\left[K_S\parallel I{D}_B\parallel r_1\parallel E_{K_{BT}}[K_S\parallel I{D}_A]\right]$

3. $\text{Alice}\to \text{Bob}:E_{K_{BT}}\left[K_S\parallel I{D}_A\right]$

4. $\text{Bob}\to \text{Alice}:E_{K_S}[r_2]$

5. $\text{Alice}\to \text{Bob}:E_{K_S}[r_2-1]$

Just as in the earlier protocol, $K_{AT}$ is a key shared between Alice and Trent, while $K_{BT}$ is a key shared between Bob and Trent. Unlike the wide-mouthed frog protocol, the Needham–Schroeder protocol does not employ timestamps but instead uses random numbers $r_1$ and $r_2$ as nonces. In the first step, Alice sends Trent her request, which is a statement of who she is and whom she wants to talk to, along with a random number $r_1$. Trent gives Alice the session key $K_S$ and gives Alice a package $E_{K_{BT}}[K_S\parallel I{D}_A]$ that she will deliver to Bob. In the next step, she delivers the package to Bob. Bob can decrypt this to get the session key and the identity of the person he is talking with. Next, Bob sends Alice his own challenge by sending the second nonce $r_2$. In the final step, Alice proves her identity to Bob by answering his challenge. Using $r_2-1$ instead of $r_2$ prevents Mallory from replaying message 4.

The purpose of $r_1$ is to prevent the reuse of old messages. Suppose $r_1$ is omitted from Steps 1 and 2. If Eve sees that Alice wants to communicate with Bob, she could intercept Trent’s message in Step 2 and substitute a transmission from a previous Step 2. Then Alice and Bob would communicate with a previously used session key, something that should generally be avoided. When $r_1$ is omitted, Alice has no way of knowing that this happened unless she has kept a list of previous session keys $K_S$.

Observe that the key exchange portion of the protocol is completed at the end of the third step. The last two exchanges, however, seem a little out of place and deserve some more discussion. The purpose of the nonce in step 4 and step 5 is to prevent replay attacks in which Mallory sends an old $E_{K_{BT}}[K_S\parallel I{D}_A]$ to Bob. If we didn’t have step 4 and step 5, Bob would automatically assume that $K_S$ is the correct key to use. Mallory could use this strategy to force Bob to send out more messages to Alice involving $K_S$. Step 4 and step 5 allow Bob to issue a challenge to Alice where she can prove to Bob that she really knows the session key $K_S$. Only Alice should be able to use $K_S$ to calculate $E_{K_S}[r_2-1]$.

In spite of the the apparent security that the challenge-response in step 4 and step 5 provides, there is a potential security problem that can arise if Mallory ever figures out the session key $K_S$. Let us step through this possible attack.

1. $\text{Mallory}\to \text{Bob: }{E}_{K_{BT}}\left[K_S\parallel I{D}_A\right]$

2. $\text{Bob}\to \text{Alice:}{E}_{K_S}[r_3]$

3. $\text{Mallory}\to \text{Bob:}{E}_{K_S}[r_3-1]$

Here, Mallory replays an old message from step 3 of Needham–Schroeder as if Mallory were Alice. When Bob gets this message, he issues a challenge to Alice in the form of a new nonce $r_3$. Mallory can intercept this challenge and, since she knows the session key $K_S$, she can respond correctly to the challenge. The net result is that Mallory will have passed Bob’s authentication challenge as if she were Alice. From this point on, Bob will communicate using $K_S$ and believe he is communicating with Alice. Mallory can use Alice’s identity to complete her evil plans.

Building a solid key distribution protocol is very tough. There are many examples in the security literature of key distribution schemes that have failed because of a clever attack that was found years later. It might seem a lost cause since we have examined two protocols that both have weaknesses associated with them. However, in the rest of this chapter we shall look at protocols that have so far proven successful. We begin our discussion of successful protocols in the next section, where we will discuss Kerberos, which is an improved variation of the Needham–Schroeder key exchange protocol. Kerberos has withstood careful scrutiny by the community and has been adopted for use in many applications.