Chapter 17
Key Servers
At last we turn to key management. This is, without a doubt, the most difficult issue in cryptographic systems, which is why we left it to near the end. We've discussed how to encrypt and authenticate data, and how to negotiate a shared secret key between two participants. Now we need to find a way for Alice and Bob to recognize each other over the Internet. As you will see, this gets very complex very quickly. Key management is especially difficult because it involves people instead of mathematics, and people are much harder to understand and predict. Key management is in many ways a capstone to all we have discussed so far. Much of the benefit of cryptography is defeated if key management is done poorly.
Before we start, let us make one thing clear. We talk only about the cryptographic aspects of key management, not the organizational aspects. The organizational aspects include things like a policy covering whom to issue keys to, which keys get access to which resources, how to verify the identity of the people who get keys, policies on the security of the stored keys, mechanisms for verifying that these policies are being adhered to, etc. Every organization will implement these differently, depending on their requirements and their existing organizational infrastructure. We focus only on parts that directly affect the cryptographic system.
One way to handle key management is to have a trusted entity to hand out all the keys. We'll call this entity the key server.
The basic idea is simple. We assume that everybody sets up a shared secret key with the key server. For example, Alice sets up a key KA that is known only to her and to the key server. Bob sets up a key KB that is known only to him and to the key server. Other parties set up keys in the same fashion.
Now suppose Alice wants to communicate with Bob. She has no key she can use to communicate with Bob, but she can communicate securely with the key server. The key server, in turn, can communicate securely with Bob. We could simply send all the traffic to the key server and let the key server act as a giant post office. But that is a bit hard on the key server, as it would have to handle enormous amounts of traffic. A better solution is to let the key server set up a key KAB that is shared by Alice and Bob.
This is the basic idea behind Kerberos, a widely used key management system [79]. Kerberos is based on the Needham-Schroeder protocol [102].
At a very basic level, here is how it works. When Alice wants to talk to Bob, she first contacts the key server. The key server sends Alice a new secret key KAB plus the key KAB encrypted with Bob's key KB. Both these messages are encrypted with KA, so only Alice can read them. Alice sends the message that is encrypted with Bob's key, called the ticket, to Bob. Bob decrypts it and gets KAB, which is now a session key known only to Alice and Bob—and to the key server, of course.
One of the features of Kerberos is that the key server, called the KDC in Kerberos terminology, does not have to update its state very often. Of course, the key server has to remember the key that it shares with each user. But when Alice asks the KDC to set up a key between her and Bob, the KDC performs the function and then forgets all about it. It does not keep track of which keys between users have been set up. This is a nice property because it allows a heavily loaded key server to be distributed over several machines in a simple manner. As there is no state to be updated, Alice can talk to one copy of the key server one moment and to another copy the next moment.
It turns out that the cryptographic protocols needed for a Kerberos-style system are very complicated. Initially, designing such protocols looks quite easy to do, but even experienced cryptographers have published proposals, only to have them broken later on. The flaws that creep in are very subtle. We're not going to explain these protocols here; they are too dangerous to experiment with and modify by hand. Even we shy away from designing this type of protocol anew. If you want to use a protocol of this sort, use the latest version of Kerberos. Kerberos has been around for quite a while, and many competent people have looked at it.
Sometimes it is not possible to use Kerberos. The protocol is far from simple, and it imposes some restrictions. Servers have to memorize all tickets that they have accepted, and every participant needs a reliable clock. There are several situations in which these requirements cannot be met. Further, we find it more informative to study a simpler design.
We can create a simpler and more robust solution if we don't put so much emphasis on efficiency. It turns out to be especially useful to allow the key server to maintain state. Modern computers are far more powerful than they were in the days when Kerberos was first designed, and they should not have any trouble maintaining state for tens of thousands of participants. Even a very large system with 100,000 participants is not a problem: if each participant requires a 1 kilobyte state in the key server, storing all states requires only 100 megabytes of memory. The key server still needs to be fast enough to set up all the requested keys, but that too is much less of a problem with modern, fast computers.
We will only discuss the situation in which there is a single key server. There are techniques that you can use to distribute the key server state over several computers, but we won't go into the details, because you really don't want to have a key server for tens of thousands of participants; it's too risky. The danger of large key servers is that all the keys are in a single place. That makes the key server a very attractive target for attack. The key server must also be online at all times, which means an attacker can always communicate with the key server at will. The current state of the art does not protect computers from network attacks very well, and putting all your keys in a single place is an invitation to disaster. For smaller systems, the total “value” of the keys kept by the key server is smaller, so this threat is reduced.1 In the next few chapters we will explore a solution to the key management system that is better suited to very large systems. We will restrict our discussion of key servers to fairly small systems—up to a few thousand participants or so.
17.3.1 Secure Connection
Here is a brief description of a simpler solution. First, we assume that Alice and the key server share a key KA. Instead of using this key directly, they use it to run a key negotiation protocol, like the ones we discussed in Chapter 14. (If KA is a password, you'd really prefer to use one of the protocols suitable for low-entropy passwords that we discussed in Section 14.12, assuming the patent issues are not a problem for you.) The key negotiation protocol sets up a fresh key K′A between the key server and Alice. All other participants also perform the same protocol with the key server, and they all set up fresh keys.
Alice and the key server use K′A to create a secure communication channel (see Chapter 7 for details). Using the secure channel, Alice and the key server can communicate securely. Confidentiality, authentication, and replay protection are all provided by the secure channel. All further communications happen over this secure channel. All other participants create a similar secure channel with the key server.
17.3.2 Setting Up a Key
It is now much easier to design a protocol that sets up a key between Alice and Bob. We only need to consider the case where messages get lost, delayed, or deleted by the attacker, because the secure channel protects us from all other types of manipulation. The protocol can now be something fairly simple. Alice asks the key server to set up a key between her and Bob. The key server responds by sending a new key KAB to both Alice and Bob. The key server can even send the message to Bob through Alice, so that it does not need to communicate with Bob directly. If this happens, Alice simply becomes the equivalent of a network router transiting a secure channel between the key server and Bob.
This does pose one limitation on the system: Bob must run the key negotiation protocol with the key server before Alice asks the key server to set up a shared key with Bob. Whether this turns out to be a problem depends on the exact circumstances, as do the possible solutions to this limitation.
17.3.3 Rekeying
Like all keys, the K′A key must have a limited lifetime. This is easy to arrange, as Alice can always rerun the key negotiation protocol (using the original key KA for authentication) to set up a fresh K′A key. A key lifetime of a few hours seems reasonable for most situations.
Because we can always rekey, the key server does not have to store the secure channel state in a reliable manner. Suppose the key server crashes and loses all state information. As long as it remembers KA (and the corresponding keys for the other participants), there is no problem. All we have to do to recover is run the key negotiation protocol between the key server and every participant again. So although the key server is not stateless, it does not have to modify its long-term state—the part that is stored on nonvolatile media—when running the protocols.
17.3.4 Other Properties
Perhaps our solution is not simpler than Kerberos from an implementation point of view, but it is simpler from a conceptual point of view. The secure channel makes it much easier to oversee the possible lines of attack against the protocol. Using the key negotiation protocol and the secure channel we already designed is a good example of how modularization can help in the design of cryptographic protocols.
Using the key negotiation protocol to set up the secure channel has another advantage: we get forward secrecy. If Alice's key KA is compromised today, her old secure channel keys K′A are not revealed, and therefore all her old communications are still secure.
In the earlier parts of the book, we gave a detailed example design of the cryptographic function we discussed. We won't do that here, nor will we for the rest of the book. The cryptography is fairly straightforward, and we could certainly have described a key server system, but it would not be very useful. Designing key management systems is more a problem of collecting a suitable set of requirements for the particular application and getting the user interface right than a problem of cryptography. To be able to explain the design choices for a concrete example here, we would have to invent and document the entire surrounding social and organizational structure, the threat environment, and the application that needs the key management.
If you want to implement a central key server, you should use Kerberos if possible. It is widely available and widely used.
In those situations where Kerberos is not suitable, you will have to design and build something like the solution we described, but that will be a major operation. For the most common type of cryptographic applications we have seen, you should count on spending as much time on the key server system as you did on the entire application. Our discussion here should help guide your thinking.
Exercise 17.1 For the protocol in Section 17.3, what is a reasonable lifetime to use for the keys KA′? Why? What bad things could happen if the lifetime is longer? What bad things could happen if the lifetime is shorter?
Exercise 17.2 For the protocol in Section 17.3, how might an attacker be able to learn KA′ before it times out? What bad things would the attacker be able to do with that knowledge? What bad things would the attacker not be able to do with that knowledge?
Exercise 17.3 For the protocol in Section 17.3, how might an attacker be able to learn KA′ after it times out? What bad things would the attacker be able to do with that knowledge? What bad things would the attacker not be able to do with that knowledge?
Exercise 17.4 For the protocol in Section 17.3, consider an attacker who intercepts all communications. Can the attacker retroactively read data between Alice and Bob if KA and KB are both later exposed?
Exercise 17.5 For the protocol in Section 17.3, could an attacker gain any advantage in breaking the protocol by forcibly rebooting the key server?
Exercise 17.6 For the protocol in Section 17.3, could an attacker mount a denial-of-service attack against two parties wishing to communicate, and if so, how?
Exercise 17.7 For the protocol in Section 17.3, are there policy or legal risks with having the key server generate KAB? Are there things Alice and Bob would not say in a situation where the key server generates KAB that they would say if the key were known only to them?
1 We don't like to leave any unaddressed threat in the system, but in key management, you always end up with a compromise solution.