▶ 13.2 Crypto Keys on a Network
Key management has always posed a challenge for communications networks. Military and intelligence organizations spent much of the 20th century trying out different strategies and discovering their strengths and weaknesses.
Key management comes down to two problems:
Ensure that the right people have the right crypto keys
Prevent the wrong people from uncovering any crypto keys
It is hard to keep these in balance. An example of this made headlines in late 2009. The Predator drones used by the U.S. military to observe battlefield targets remotely were being monitored by opposing militias. Anyone who could afford the inexpensive software could intercept and watch a drone’s video feed. This allowed militias to monitor or evade U.S. military operations.
As the story unfolded, this turned out to be a practical trade-off between security and usability. The drones had a wireless control channel through which an officer controlled the craft from another continent; that channel was heavily encrypted. The video channel, however, was used by numerous people in the U.S. military, including people in the area covered by the drone. If the video was encrypted, U.S. soldiers on the ground would have less access to it, making their difficult job even harder. There was no practical technique to make encrypted video easily available to soldiers on the ground. It was more practical to leave the video feed unprotected.
The Default Keying Risk
Another situation that occasionally crops up with crypto devices (or any devices with built-in secrets) is default keying. Some manufacturers install “default” settings for secret keys and passwords. This was especially common among internet routers until the late 1990s, when attackers penetrated numerous internet service providers by using the vendors’ default passwords.
The problem with default keying should be obvious: Anyone who buys the same device has a copy of the same key, unless we change it. Thus, everyone who uses the default key is automatically sharing a cryptonet, whether or not it is intentional.
Careful vendors make it impossible to use a default key. For example, the device setup process on modern operating systems demand that the user choose an initial administrative password. Earlier systems had default passwords that rarely changed. For example, many minicomputers in the 1970s and 1980s had a built-in administrative account for vendor maintenance personnel: The user name was “FIELD” and the password was always “SERVICE.” Site administrators had to explicitly change or remove the account. Otherwise, a knowledgeable attacker would have easy entry to their system.
This problem resurfaced in 2010 with SCADA systems. These are computer-based devices that control factory equipment and power grids. Certain SCADA products were customarily distributed with default passwords. When security experts raised warnings about SCADA-based viruses and other malware, SCADA system developers had to admit that they were relying on default passwords to control certain large-scale systems.
Key Distribution Objectives
In practice, the two key management problems noted earlier lead to the following two objectives in every key management system:
Ensure that keys are changed periodically. This reduces the risk that a cryptanalyst will collect enough ciphertext to crack that particular key. It also reduces the damage caused if the key was leaked without discovering it.
Change keys when a key holder should no longer have that key. When we manage physical keys for door locks, we can verify that a key holder returns a physical key. On the other hand, it’s easy to make a copy of an encryption key and still return the “original copy.” Therefore, we can’t tell if a crypto key user has surrendered all copies of that key. The only way to truly revoke their access to the cryptonet is to change the key.
The standard solution is to provide safe and effective techniques to rekey the crypto connections as needed without losing access to the encrypted data. This always has been a tricky problem.
Key Distribution Strategies
In a sense, key distribution is like network wiring: Those who share a particular key can exchange data, and those without the key are left out. Sharing a particular key is like being on a network bus connection; you can see everything and speak to everyone. However, instead of calling it a bus, we call it a net: a cryptonet. We organize cryptonets in different ways to achieve different results. Here are the basic strategies for managing keys:
■ Single cryptonet—Use a single encryption key and distribute it to everyone in the community. This is also known as the one big cryptonet strategy. It is easy to establish but very, very hard to maintain.
■ Groups of cryptonets—Identify subcommunities and distribute different keys to different subcommunities. Some designers arrange the groups into hierarchies or other structures.
■ Pairwise key sharing—Every pair of endpoints gets a unique set of keys. If Bob is going to have an encrypted conversation with his suitemates, he needs a separate key to talk to each one.
■ Key distribution center—Every endpoint gets a single secret key, and they use it to talk to a key distribution center (KDC). When Bob wants to talk to Alice, his computer contacts the KDC, which creates a unique key to use in his conversation with Alice. The KDC uses Alice’s own key to ensure that she can retrieve a readable copy of the key it sent to Bob.
■ Public-key distribution—Anyone who needs to create authentic traffic or receive encrypted traffic produces a personal public/private key pair and publishes the public key in a certificate. The public key then is used to provide authenticity and secrecy.
Each of these techniques has its own benefits and shortcomings, as each tries to achieve the overall objectives of key management. Some are open to other security problems.
Key Distribution Techniques
In practice, there are four specific techniques used to implement these different strategies. They are:
Manual keying
Simple rekeying
Secret-key techniques: wrapping, distribution, hashing
Public-key techniques: Diffie–Hellman and RSA
All of these techniques have been tried in the past; many are still widely used today. In practice, however, systems relying on the first two tend to be brittle and subject to failure. Safe and secure systems tend to use more sophisticated techniques.
As we look at these techniques, we will consider this example:
Alice and Bob live in the same dorm, although on different floors. They are near enough so they can use a wireless LAN connection to talk between their computers. To keep others from listening in, they have been experimenting with key-exchange techniques.
13.2.1 Manual Keying: A Building Block
In manual keying, we produce one encryption key for each cryptonet or communicating pair and distribute that key to the appropriate endpoints. For example, Alice constructs a hexadecimal crypto key to use with their wireless LAN conversations. She configures her wireless card to use that key. She also writes the key on a sticky note and gives it to Bob.
This is the simplest and most obvious way of distributing keys to encrypt communications. We can use this to implement one or many cryptonets or to deploy pairwise keys to pairs of endpoints. It is often a starting point for crypto keying.
However, this is very hard to do regularly and safely. To meet our objective of changing keys regularly, we have to distribute keys almost continuously. The more we handle and distribute keys, the more likely the risk of losing or disclosing one.
If we are using cryptonets, we have to worry about getting the keys properly distributed before we shift to a new key. Occasionally, one or more endpoints won’t get new keys in time.
The most instructive example of manual keying comes from the banking industry.
An Incident: In the late 1970s, a large bank deployed a digital network that used the new Data Encryption Standard to protect its traffic. Initial keys were distributed when the devices were first installed. After a few years, the bank decided to try replacing the original keys with new ones. To do this, they would have to generate and distribute 2000 copies of the new key.
They spent a year planning the rekeying process. The appropriate recipient was identified at each bank. Following older banking procedures, the new key would be sent by registered mail—the safest method available at the time. Each recipient would acknowledge the parcel and send back a signed receipt by mail. This would all take place with plenty of time to allow an orderly transition of all sites at once, so that no one would fall off the network.
The result was a disaster. By the time the keys were sent, a number of the intended recipients had retired or changed jobs; their mail was ignored or discarded. Other branches received the keys but failed to send back the receipt. Internationally, the “registered mail” marking suggested valuable contents, so many parcels were stolen and never arrived at their branches. It took the bank over 2 years to finish the rekeying process.
Although the banker’s story involved one big cryptonet, the same problems apply in other cases. If we use pairwise keying or relatively small cryptonets, we replace those keys one pair at a time or one cryptonet at a time. If we have one big cryptonet, we have no choice: We must replace all of the keys at once. If anyone has the old key when we shift to the new one, they won’t be able to read the new traffic.
To some extent, every cryptosystem will require some type of manual keying. The moral of the story is to do it rarely and to make the most out of manually distributed keys.
13.2.2 Simple Rekeying
There is only one way to avoid rekeying manually: We rekey, somehow using the key we already have. In a sense, we use the existing key to “bootstrap” a new key into operation. The simplest approach, called self-rekeying, transforms an existing key into a new one. Another approach uses the existing key to distribute a new one. Although both of these strategies yield a nominally different crypto key, both are vulnerable if attackers recover an older key.
These are enot recommended as crypto building blocks!
Self-Rekeying
In this technique, everyone on the cryptonet shares the same crypto key and a standard PRNG. The PRNG may be based on a one-way hash or other one-way cipher. When it is time to change keys, someone sends an announcement to every endpoint on the cryptonet; then the endpoints all feed the crypto key into the PRNG. The output is used as the new crypto key. FIGURE 13.8 illustrates the process.
FIGURE 13.8 Bad idea: self-rekeying.
Because each replacement key eventually becomes an expiring key, we have a cycle: We take the output of a PRNG and feed it in as input. This cycle is similar to the weak key stream algorithm examined in Chapter 7 (Figure 7.11). It suffers from the same type of problem: If we recover an earlier part of this sequence, we can reproduce the rest of it.
This technique sacrifices forward secrecy, as discussed in Section 8.3.1. If attackers recover an older key, they can recover every message encrypted with that key and everything encrypted with any future key. All they need to do is feed the old key into the PRNG to get the subsequent key and repeat the cycle. Self-rekeying does not ensure forward secrecy.
The only way self-rekeying provides additional protection is if we also hide the PRNG from attackers. This violates Shannon’s maxim, which says that the enemy knows our system. However, older military systems have occasionally relied on such assumptions. Self-rekeying is sometimes called key update in military circles.
For example, Alice and Bob could agree that every other day they will feed the old crypto key into an MD5 hash and use the starting bytes of the output as their new crypto key. They can do all of this by hand if they share an MD5 program. Of course, if Henry (or someone else) figures out that they’re using MD5 and he uncovers an earlier key, then he can read all of their messages. Moreover, Henry then could use the key to masquerade as Bob to Alice or as Alice to Bob.
This technique fails when we look at it in the light of our two objectives. Although it does limit the amount of information encrypted with any single key, it provides no protection if attackers recover any of our older keys. Moreover, it’s almost pointless to self-rekey when people leave the cryptonet. If the people kept copies of old keys, they could use the PRNG to generate all of the future keys.
New Keys Encrypted with Old
This technique is slightly more effective. Its security, however, relies on the ineptitude of one’s attackers. It also shares the forward secrecy problem with self-rekeying. This is not a strong basis for security. Instead of using a PRNG, we produce a new, truly random key; then we encrypt the new key using the existing key and distribute it to the cryptonet (FIGURE 13.9).
FIGURE 13.9 Another bad idea: a new key encrypted with an old one.
In this case, Alice generates a new key on her computer. She sends it to Bob over the encrypted wireless LAN, which uses their old crypto key. Bob receives the message. They both agree on a time to enter the new key into their wireless interfaces.
This approach poses more of a challenge to an attacker, especially one with limited resources. However, it’s practical to attack this arrangement. If attackers intercept all traffic between Bob and Alice and keep the most recent traffic before the keys change, they can unravel each key change. Thus, if they’ve uncovered an earlier key, they can uncover the subsequent keys.
This is a lot more difficult to attack than self-rekeying. Still, there’s no reason to choose a weak key distribution strategy. We might as well choose something without an obvious weakness.
13.2.3 Secret-Key Building Blocks
Banks encountered a great deal of trouble updating and distributing DES encryption keys in the late 1970s and early 1980s. The American Bankers Association promoted a standard for key distribution, which became ANSI X9.17. This standard described several techniques for distributing and validating DES keys. Although the techniques became obsolete, they provide a starting point for secret-key management. We will examine the following techniques:
■ Key wrapping
■ Key-distribution centers
■ Shared secret hashing
Each of these provides a way to use an existing, shared key to establish a temporary key. Because we use the shared key sparingly and only to produce new working keys, attackers have a much harder time trying to crack it.
These techniques all serve as effective crypto building blocks. Although they do not resist all possible attacks individually, standard crypto protocols combine the building blocks in order to resist the principal attacks. We should strive to use standard crypto protocols whenever possible instead of designing our own.
Key Wrapping
Key wrapping uses a KEK to encrypt the key we distribute. We first encountered key wrapping in Section 8.2.2. When encrypting the contents of a file, we encrypt it with a CEK. We then wrap the CEK with a KEK when sharing it. When encrypting network traffic, we use slightly different terms; we encrypt network traffic with a traffic-encryption key (TEK). We then wrap the TEK with a KEK when sharing it. FIGURE 13.10 illustrates the process.
FIGURE 13.10 ANSI X9.17: Wrapping new keys for distribution.
Superficially, Figure 13.10 may look the same as Figure 13.9. The vital difference is that the earlier figure doesn’t use a separate KEK. Instead, it uses the previous TEK to encrypt a new TEK. In practice, we must never use a TEK to encrypt another encryption key. We only use the KEK to encrypt another key. Although this does not yield “perfect” forward secrecy, it greatly improves security over the previous techniques.
In a sense, X9.17 doesn’t make key distribution significantly easier. If we decide to use the same KEK for many sites, then we face the problems of having one big cryptonet. If we assign a separate KEK to each pair of sites, then the number of distributed keys increases quadratically with each new recipient.
Key Distribution Center
The KDC greatly simplifies key management. Each host must establish its own, secret “KDC key” to share with the KDC. Each host uses its KDC key to unwrap traffic keys produced by the KDC. If the host needs to communicate with another host, the KDC provides it with two wrapped copies of the same traffic key: One wrapped with the sender’s KDC key and the other wrapped with the recipient’s KDC key (FIGURE 13.11).
FIGURE 13.11 Keys wrapped by a key distribution center.
We first encountered the KDC when discussing ticket-based authentication in Section 12.5.2. The “tickets” issued by a Kerberos authentication server contain the two wrapped keys described previously. Although we can use the shared keys to authenticate the two participants, we also can use them to protect data traffic.
For example, Bob wants to retrieve his email from the mail server. We saw this earlier in Figure 12.23. He contacts the KDC, which constructs a ticket, as shown in Figure 13.11. Bob forwards the ticket to the mail server, when he connects to it.
To share the key with the mail server, Bob extracts his wrapped temporary key from the ticket. He uses his personal KDC key to unwrap the temporary key. The mail server extracts its own wrapped key from the ticket and uses its own KDC key to unwrap the temporary key. Now that both have a copy of the temporary key, they can use it to authenticate each other and to transfer email securely.
This technique is too simple to use by itself. For example, there is no way to detect a replay attack. If attackers intercept Bob’s earlier requests and manage to extract the wrapped key, then they can intercept his new ticket request and replay the old one. Bob then uses the previous (leaked) key when he talks to the mail server.
ANSI addressed some of these risks when it standardized a simple KDC for banking applications in 1985. By then, researchers had moved forward to address other KDC weaknesses. The Kerberos system was being developed in the mid-1980s, and it incorporated improvements to address the latest vulnerabilities found by researchers. Today, the X9.17 KDCs are obsolete, but the Kerberos protocol still is being used in numerous systems, including Microsoft Windows.
Shared Secret Hashing
If two sites share a secret, they can combine the shared secret with additional shared entropy to establish traffic encryption keys. Modern 802.11 wireless systems use this technique to convert a shared secret into the traffic keys that actually encrypt messages between wireless hosts.
FIGURE 13.12 illustrates the process. First, each host generates a random nonce and sends it to the other. Next, each host uses a one-way hash to combine the shared secret, the nonces, and other connection-specific information. We use the hash result to construct our traffic key.
FIGURE 13.12 Hashing a shared secret to build a traffic key.
An interesting feature of this technique is that it never transmits a key over the network, whether or not it’s encrypted. An eavesdropper may pick up some of the inputs to the key generation process, including the nonces and well-known connection data like MAC addresses. Without the shared secret, however, there is no way to construct the traffic keys.
Because both Bob and Alice use a new nonce value, there is no way to replay earlier key exchange messages. If an attacker masquerades as Bob, it does no good to replay Bob’s earlier nonce. The resulting shared secret will still rely partly on Alice’s new nonce value and yield a completely different shared secret.
In practice, two hosts may need two or more keys to carry on a secure conversation. When we need more bits than the one-way hash provides, we repeat the hash process to produce more bits. We retain the bits produced previously and also use them as input to the hash process to produce more output bits.
13.2.4 Public-Key Building Blocks
Diffie–Hellman and RSA are the classic public-key cryptographic techniques. (See Section 8.3.) Both provide ways to establish a shared secret between two endpoints. We can use those techniques to roll over a shared secret key.
Each public-key technique provides slightly different capabilities, benefits, and shortcomings. Both are used in fundamental internet security protocols. When used by themselves, both of these techniques are vulnerable to “bucket brigade” attacks. In practice, we use these techniques as part of more sophisticated protocols that block or detect such attacks.
Secret Sharing with Diffie–Hellman
Two users can construct a shared secret by sharing Diffie–Hellman public keys. We described this in Section 8.3.1. Each user combines his or her own private key with the other’s public key to yield the shared secret. FIGURE 13.13 illustrates the process.
FIGURE 13.13 Creating an anonymous Diffie–Hellman shared secret.
When communicating across a network, we use Diffie–Hellman to construct an anonymous temporary shared secret. We do this by constructing a new Diffie–Hellman key pair each time we establish a network session. We don’t use a public key out of a certificate, so we can’t verify the public key’s source.
Alice generates a random number from which she creates a Diffie–Hellman private key. She then computes the corresponding public key and transmits it to Bob. Inside his own computer, Bob performs the same steps and sends Alice his own public key. They then both perform the Diffie–Hellman shared secret computation.
This produces an identical shared secret inside each computer. Eavesdroppers may intercept the public keys, but they can’t construct the shared secret. The only efficient way to construct the secret is by using a public key and a private key.
Because this creates a new shared secret for each session, it provides perfect forward secrecy, as discussed in Section 8.3.1. If an attacker manages to recover the shared secret from a different session, it provides no information about the shared secrets used in other sessions. The Internet Key Exchange (IKE) protocol uses this technique (Section 13.4.3).
Wrapping a Secret with RSA
If Alice has Bob’s RSA public key, Alice can use it to share a secret with Bob. We described this in Section 8.4.1. Alice encrypts the secret with the public key, and Bob decrypts it with the private key. This appears in several security protocols, including SSL. FIGURE 13.14 illustrates the messages exchanged between two computers.
FIGURE 13.14 Wrapping a shared secret key with RSA.
The process takes place as follows: Alice receives Bob’s public key via a trustworthy route, possibly by extracting it from a certificate. Because we encrypted the data with the public key, we retrieve it by decrypting with the private key.
Thus, anyone with Bob’s public key can send him information that only he can decrypt. Early public-key email mechanisms relied on this asymmetry. SSL also takes advantage of it; individual browsers don’t need their own public keys, but they can all send secret information to secured servers.
If we need to authenticate Alice, then we need to take additional steps. On the other hand, we must authenticate Bob’s public key before we use it. Otherwise, there is a risk of a bucket brigade attack.
13.2.5 Public-Key Versus Secret-Key Exchanges
Given these two different approaches to key distribution, how do we choose one over the other? In the 1990s, some experts assumed that public keys would replace secret keys everywhere, yet secret-key techniques remain popular for many applications. Here we compare properties of the two approaches.
Choosing Secret-Key Techniques
Secret-key techniques have a longer history than public-key technology. Precomputer techniques were overwhelmingly based on shared secret keys. Many techniques remain widely used. Here are situations that often favor secret-key techniques.
■ Computational resources are limited—Secret-key algorithms require far fewer computing resources than public-key algorithms offering similar security. Secret keys are far smaller. Calculations are much simpler, both for encryption and for key generation. As we strive to fit more and more computing into smaller and smaller spaces, secret-key techniques will arrive in a new, tiny application first.
■ User community is clearly identified ahead of time—Secret-key techniques rely exclusively on shared secrets to keep other things secret. It’s not practical to distribute secrets to everyone in a constantly changing community. Therefore, we need to identify our user community and distribute keys to them before we can protect our communications.
■ Revocation must be timely and reliable—Because we know who our users are and we know who has which keys, we can revoke a person’s access reliably. For cryptonets, we distribute fresh keys to everyone, except to those being revoked. If we are using a key server, like a KDC, we revoke access by deleting those users’ KDC keys.
■ Small-user community—If we don’t have trustworthy central servers to manage and distribute keys, then key distribution becomes a serious headache as the community grows. We achieve the highest level of security when we minimize the size of our cryptonets and ideally have only two users in each one. With minimum-sized cryptonets, however, the number of keys grows quadratically as we add new users.
■ Trustworthy central servers are available—If we trust our central servers, we can rely on them to distribute our keys. This makes it easier to manage a large community using secret keys. For example, Microsoft uses the KDC-based Kerberos technology to handle authentication and key distribution within its enterprise LAN products.
Choosing Public-Key Techniques
Here are situations that often favor public-key techniques for key management.
■ User community membership is unpredictable—If we can’t identify our user community beforehand, public-key cryptography provides us with ways to “bootstrap” keying material to the new users.
■ Large community eand untrustworthy server computers—Secret-key techniques become difficult as the user community grows in size, unless we can trust our server systems. Strictly speaking, any server can be penetrated by an adequately motivated attacker. If the crypto protects truly critical information, then it might be safer to use public-key cryptography.
■ Inefficient revocation is an acceptable risk—Public-key cryptography is most effective when we can distribute public keys broadly to all potential users. If, however, we need to revoke a public key, we can’t guarantee that everyone will hear that the key has been revoked. There are techniques, like revocation lists and online certificate validation services, that reduce the risk of accepting a revoked key. However, such services rob us of a major public-key benefit: the ability to validate and use a key offline.