15.2 Key Distribution – Introduction to Cryptography with Coding Theory, 3rd Edition

15.2 Key Distribution

So far in this book we have discussed various cryptographic concepts and focused on developing algorithms for secure communication. But a cryptographic algorithm is only as strong as the security of its keys. If Alice were to announce to the whole world her key before starting an AES session with Bob, then anyone could eavesdrop. Such a scenario is absurd, of course. But it represents an extreme version of a very important issue: If Alice and Bob are unable to meet in order to exchange their keys, can they still decide on a key without compromising future communication?

In particular, there is the fundamental problem of sharing secret information for the establishment of keys for symmetric cryptography. By symmetric cryptography, we mean a system such as AES where both the sender and the recipient use the same key. This is in contrast to public key methods such as RSA, where the sender has one key (the encryption exponent) and the receiver has another (the decryption exponent).

In key establishment protocols, there is a sequence of steps that take place between Alice and Bob so that they can share some secret information needed in the establishment of a key. Since public key cryptography methods employ public encryption keys that are stored in public databases, one might think that public key cryptography provides an easy solution to this problem. This is partially true. The main downside to public key cryptography is that even the best public key cryptosystems are computationally slow when compared with the best symmetric key methods. RSA, for example, requires exponentiation, which is not as fast as the mixing of bits that takes place in AES. Therefore, sometimes RSA is used to transmit an AES key that will then be used for transmitting vast amounts of data. However, a central server that needs to communicate with many clients in short time intervals sometimes needs key establishment methods that are faster than current versions of public key algorithms. Therefore, in this and in various other situations, we need to consider other means for the exchange and establishment of keys for symmetric encryption algorithms.

There are two basic types of key establishment. In key agreement protocols, neither party knows the key in advance; it is determined as a result of their interaction. In key distribution protocols, one party has decided on a key and transmits it to the other party.

Diffie-Hellman key exchange (see Sections 10.4 and 15.1) is an example of key agreement. Using RSA to transmit an AES key is an example of key distribution.

In any key establishment protocol, authentication and intruder-in-the-middle attacks are security concerns. Pre-distribution, which will be discussed shortly, is one solution. Another solution involves employing a server that will handle the task of securely giving keys to two entities wishing to communicate. We will also look at some other basic protocols for key distribution using a third party. Solutions that are more practical for Internet communications are treated in later sections of this chapter.

15.2.1 Key Pre-distribution

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, B), Trent produces a random key KAB that will be used as a key for a symmetric encryption method (hence KBA=KAB). 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 n1 keys to store, and Trent must send n(n1)/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 pn. 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 rU (mod p).

  2. Trent chooses three secret random numbers a, b,  and c mod p.

  3. For each user U, Trent calculates the numbers

    aUa+brU(mod p)bUb+crU(mod p)

    and sends them via his secure channel to U.

  4. Each user U forms the linear polynomial

  5. If Alice (A) wants to communicate with Bob (B), then Alice computes KAB=gArB, while Bob computes KBA=gBrA.

  6. It can be shown that KAB=KBA (Exercise 2). Alice and Bob communicate via a symmetric encryption system, for example, AES, using the key (or a key derived from) KAB.


Consider a network consisting of three users Alice, Bob, and Charlie. Let p=23, and let

rA=11, rB=3, rC=2.

Suppose Trent chooses the numbers a=8, b=3, c=1. The corresponding linear polynomials are given by

gA(x)=18+14x, gB(x)=17+6x, gC(x)=14+5x.

It is now possible to calculate the keys that this scheme would generate:

KAB=gA(rB)=14, KAC=gA(rC)=0, KBC=gB(rC)=6.

It is easy to check that KAB=KBA, etc., in this example.

If the two users Eve and Oscar conspire, they can determine a, b, and c and therefore find all numbers aA, bA for all users. They proceed as follows. They know the numbers aE, bE, aO, bO. The defining equations for the last three of these numbers can be written in matrix form as

01rE1rO001rOabcbEaObO(mod p).

The determinant of the matrix is rErO. Since the numbers rA were chosen to be distinct mod p, the determinant is nonzero mod p and therefore the system has a unique solution a, b, c.

Without Eve’s help, Oscar has only a 2×3 matrix to work with and therefore cannot find a, b, c. In fact, suppose he wants to calculate the key KAB being used by Alice and Bob. Since KABa+b(rA+rB)+c(rArB) (see Exercise 2), there is the matrix equation

1rA+rBrArB1rO001rOabcKABaObO(mod p).

The matrix has determinant (rOrA)(rOrB)  0 (mod p). Therefore, there is a solution a, b, c for every possible value of KAB. This means that Oscar obtains no information about KAB.

For each k1, 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].

15.2.2 Authenticated Key Distribution

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 KAB to communicate with Bob and has Trent transfer it to Bob securely:

  1. AliceTrent: EKATtAIDBKAB.

  2. TrentBob: EKBTtTIDAKAB.

Here, KAT is a key shared between Alice and Trent, while KBT is a key shared between Bob and Trent. Alice’s and Bob’s identifying information are given by IDA and IDB, respectively. The parameter tA is a timestamp supplied by Alice, while tT is a timestamp given by Trent. It is assumed that Alice, Trent, and Bob have synchronized clocks. Bob will accept KAB as fresh if it arrives within a window of time. The key KAB will be valid for a certain period of time after tT.

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 tA. If Trent gets the message and the time is not too far off from tA, 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 tT. 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 EKBTtTIDAKAB.

  2. Trent sends EKATtT IDBKAB to Alice, with a new timestamp tT . Alice thinks this is a valid message since it came from Trent and was encrypted using Trent’s key. The key KAB will now be valid for a period of time after tT .

  3. Mallory then pretends to be Alice and gets EKBTtT ′′IDAKAB. The key KAB will now be valid for a period of time after tT>tT.

  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 KAB indefinitely. Of course, Alice and Bob should keep track of the fact that they have seen KAB before and begin to suspect that something suspicious is going on when they repeatedly see KAB. 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 tA with tT. If Trent had not changed tT and instead had left tA 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 KS from Trent so that they can talk with each other. The protocol involves the following steps:

  1. AliceTrent: IDAIDBr1


  3. AliceBob: EKBTKSIDA

  4. BobAlice: EKS[r2]

  5. AliceBob: EKS[r21]

Just as in the earlier protocol, KAT is a key shared between Alice and Trent, while KBT 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 r1 and r2 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 r1. Trent gives Alice the session key KS and gives Alice a package EKBT[KSIDA] 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 r2. In the final step, Alice proves her identity to Bob by answering his challenge. Using r21 instead of r2 prevents Mallory from replaying message 4.

The purpose of r1 is to prevent the reuse of old messages. Suppose r1 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 r1 is omitted, Alice has no way of knowing that this happened unless she has kept a list of previous session keys KS.

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 EKBT[KSIDA] to Bob. If we didn’t have step 4 and step 5, Bob would automatically assume that KS is the correct key to use. Mallory could use this strategy to force Bob to send out more messages to Alice involving KS. 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 KS. Only Alice should be able to use KS to calculate EKS[r21].

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 KS. Let us step through this possible attack.

  1. MalloryBob: EKBT[ KSIDA ]

  2. BobAlice:EKS[r3]

  3. MalloryBob:EKS[r31]

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 r3. Mallory can intercept this challenge and, since she knows the session key KS, 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 KS 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.