▶ 8.2 The Reused Key Stream Problem
Stream ciphers using the xor operation were first put into operation on teletype networks in the 1920s. Most messages were copied and transmitted from punched paper tape. The encryption key was also punched on tape. To encrypt the data, they installed a very simple circuit that computed the xor of the data and key values at each punch on the tape.
Gilbert Vernam, the developer, realized that an attacker could crack the encryption if they used the same key tape to transmit more than one message. Cryptosystem designers seem to learn this lesson all over again every generation or two.
Soviet spies used one-time pads in the 1940s. (See Section 7.3.) In 1998, Microsoft used the RC4 cipher to protect data transmitted across dial-up telephone connections. In both cases, the encryption method seemed reasonably strong, yet in both cases, attackers found a way to penetrate the encryption. Both made the same mistake: They encrypted their data with a reused key stream.
Following World War II, the far-flung Soviet spy network was hard-pressed to provide one-time pads for all of its overseas agents. Each spy needed one digit of “pad” for every digit of information sent back to Moscow. This required a vast amount of typing and preparation. To save time, the pad producers made extra copies of some pads and sent them to spies in different parts of the world. This was not a problem unless an enemy cryptanalyst obtained ciphertexts from the two different sources and matched them up.
And that is exactly what happened. Cryptanalysts at the U.S. Army Security Agency found that messages from agents in different parts of the world used the same pads for encryption. The Soviets apparently hoped that cryptanalysts in different countries would look only at messages within their own countries. The Army cryptanalysts cracked numerous messages that shed light on the atomic spy rings of the 1940s and 1950s. Notable figures, including Klaus Fuchs and the Rosenbergs, appeared in those messages. At the time, however, the messages never appeared as evidence in court. The government preferred to keep the projects secret in hopes of reading more Soviet messages.
We illustrate the root of the Soviets’ problem with another encryption example. FIGURE 8.3 encrypts two images: a smiley face and a written message saying “SEND CASH.” We encrypt each image using xor. Both encryptions use the same key stream. We combine the two ciphertexts using xor, and the result appears in FIGURE 8.4.
FIGURE 8.3 Reusing the same key stream.
Courtesy of Dr. Richard Smith.
FIGURE 8.4 Eliminating both key streams with xor.
Courtesy of Dr. Richard Smith.
The xor eliminates the key stream from both messages. What remains are the two original plaintext messages, one layered atop the other. We see this clearly when combining two images. With text, the xor combines individual characters from each message. Although the result isn’t as visually dramatic as it is with images, the jumble is relatively simple for a cryptanalyst to decode.
The Army Security Agency and its successor, the NSA, used this technique to decrypt thousands of Soviet spy messages from the 1940s. Unfortunately, the agency briefed too many people on the project. Kim Philby, a senior British intelligence official, was also a Soviet spy. The Soviets corrected their encryption procedures to prevent subsequent messages from being decrypted. However, this was not the last time someone reused a key stream.
In the 1990s, Microsoft introduced its version of the Point-to-Point Tunneling Protocol (PPTP) to connect Windows computers securely. Microsoft’s PPTP used the RC4 stream cipher in several ways. One technique derived the encryption key from a password provided at the start of the PPTP connection. PPTP would derive the same key every time the users provided that same password. Thus, an attacker could take the data sent during two separate PPTP sessions, combine them with xor, and eliminate the key stream. The attacker would still need to split out the two overlaid plaintext streams, but that is a much easier cryptanalytic task.
There are several ways to avoid this problem. In fact, Microsoft’s PPTP suffered this problem only when using shorter encryption keys. When using longer keys, it used a one-way hash to combine the password with connection-specific data. Because the connection data was different in different directions, as well as different when new connections were made, the resulting hash yielded different keys for different connections. Well-designed encryption systems all take similar steps when using stream ciphers.
8.2.1 Avoiding Reused Keys
Figure 8.2 shows a simple way to use a passphrase as an encryption key. If the user chooses the same passphrase to encrypt two different documents, the program will use the same internal key in both cases. This will encrypt both documents with the same key stream, which makes the documents vulnerable to the attack shown in Figure 8.4.
One approach would be to warn the users to choose separate passphrases for separate documents. This is risky and unnecessary. People have a great deal of trouble memorizing passwords and passphrases in any case; we must not make matters more difficult. Moreover, we can design the file encryption software to use a different internal key every time it encrypts a file.
Changing the Internal Key
We can, in fact, safely reuse a passphrase as long as the program uses a different internal key for each file. In Figure 8.2, we take the passphrase and hash it to produce the internal key. If we combine the passphrase with different data each time and then compute the hash, we get a different encryption key for each file.
For example, we could combine the passphrase and the file name to form a longer text string and calculate its hash. This yields a different hash, and thus a different key, for each file. However, this approach could cause problems. First, and most obviously, we might have two different files in different directories that have the same name, and thus the same encryption key.
Another problem may arise if we rename a file. When we try to decrypt a renamed file, the program will hash the new file name with the passphrase and derive a different key. We can only decrypt the file if we derive the same internal key that encrypted it. We can bypass this problem if the program adds a plaintext heading to the encrypted file, and saves the file name in the header; then it can extract the file name from that header and use the name to construct the key.
Let’s assume that the program saves extra data in a file header and derives the key from the extra data. If we take this idea one step farther, we see that the program shouldn’t be limited to using the file name. The extra data just needs to be different from one file to another. The data also should not be chosen by potential attackers. We can follow those two rules and generate a new internal key every time we encrypt a file.
Combining the Key with a Nonce
We achieve this by saving a nonce in the file’s header. Thus, we use two building blocks—the one-way hash and the nonce—to construct the internal key. This yields a highly random key that varies from one use to another, even if we use the same passphrase.
When we introduced the nonce in Section 6.5.1, we noted its two requirements, and both requirements apply here. First, we choose a different nonce so that the operation is different each time. In this case, we choose a new nonce each time we reencrypt the file. Second, we don’t allow potential attackers to choose the nonce’s value. We may choose either a random number that’s large enough not to repeat, or we may use a counter or clock value.
FIGURE 8.5 shows how we create the secret key using a nonce. Each time we encrypt the file, the program constructs a new internal key. First, it accepts the passphrase; then the program chooses the nonce. The time of day is often a good choice, assuming it has always changed since the last time we saved the file.
FIGURE 8.4 Eliminating both key streams with xor.
The program can also use a large random number. If so, it should use either a truly random number, or a pseudorandom number generator that has a truly random seed. In any case, the nonce should be large enough and changeable enough so that it’s unlikely that anyone else who uses the same passphrase would choose it.
The program uses the nonce and the passphrase to construct its internal key. It combines the passphrase with the nonce and computes the hash over both of them. This hash value becomes the internal key.
When the program encrypts the file, it writes a copy of the nonce to the encrypted file, saving it in a header at the beginning. The nonce is not encrypted. It must be available as plaintext to create the internal key.
When the program decrypts the file, it reverses the process. First, it collects the passphrase as usual, then it extracts the nonce from the file being decrypted. The program constructs the internal key by hashing the passphrase and nonce together. The program must concatenate the two in exactly the same way to generate the same internal key.
Clearly, we are not keeping the nonce secret. It does not have to remain secret for the encryption to remain safe. All of the entropy in the file’s internal encryption key resides in the text passphrase. If the passphrase is reasonably long and is kept secret, the file should be safe against cracking.
Whenever the program reencrypts a previously encrypted file, it chooses a different nonce. This yields a different internal key. Otherwise, an attacker might be able to extract information by combining the old and new encrypted files together.
Software Checklist for Internal Keys Using Nonces
Here is a checklist of requirements for creating and handling internal keys using nonces.
When encrypting a file, the software shall use an internally generated key (the internal key). The internal key shall be constructed from the user-supplied passphrase and an internally generated nonce.
When reencrypting a previously encrypted file, the software shall generate a new nonce.
The software shall generate the nonce in a fashion that avoids the risk of generating the same nonce when encrypting different files. For example, the nonce could be generated by a high-precision time-of-day clock or by a high-quality random number generator.
The software shall construct the internal key by formatting the passphrase and the nonce in a uniform manner and applying a specific hash function. This ensures that a particular passphrase and nonce will always generate the same internal key.
After generating the internal key, the software shall store the internal key in RAM only as long as it is needed for encryption or decryption.
The software shall erase the internal key from RAM as soon as it is no longer needed.
The software shall not write the internal key to the hard drive unless its storage area also is protected by strong encryption.
These requirements apply only if we use nonces to avoid reused keys. The nonce provides a relatively simple solution to the problem, but it is not the only solution. We can increase security while avoiding reused keys if we create a completely new key every time we encrypt a file.
8.2.2 Key Wrapping: Another Building Block
When an attacker tries to crack an encryption key from a known ciphertext, additional ciphertext makes the job easier. Practical attacks on RC4 rely on hundreds of thousands of bytes of ciphertext. If we encrypt a large number of files with the same passphrase, we are trusting our files to that same, small amount of entropy.
A safer way to protect these files is to generate a new, random internal key whenever we encrypt the file. We then encrypt the key itself using the passphrase. We call this key wrapping. FIGURE 8.6 illustrates the process.
FIGURE 8.6 Wrapping a key: The KEK encrypts the CEK.
If we choose the key randomly, then an attacker can’t apply a known plaintext attack or dictionary attack to it. Moreover, we make the known ciphertext attack against the passphrase much more difficult. Such attacks require a great deal of known ciphertext. Here, we only encrypt individual keys with the passphrase, and that doesn’t produce very much ciphertext.
Key wrapping uses two separate and unrelated keys to encrypt the file. We encrypt the actual data in the file with the content encrypting key (CEK). We must generate a new, truly random CEK whenever we encrypt the file. We then use the passphrase to produce a key encrypting key (KEK). We produce the wrapped key by encrypting the CEK with the KEK.
Here’s how we encrypt a file using wrapped keys:
The program collects the passphrase from the user.
The program hashes the password to produce the KEK.
The program uses a reliable source of random numbers to generate the CEK.
The program “wraps” the CEK by encrypting it with the KEK.
The program encrypts the plaintext file using the CEK as the key.
The program creates the encrypted file by combining the wrapped key with the ciphertext.
To decrypt the file, the program starts by opening the encrypted file and collecting the passphrase from the user. The program generates the KEK from the passphrase and “unwraps” the CEK; then the program decrypts the file’s ciphertext. When the program reencrypts the file, it generates a new, random CEK and uses it to encrypt the file.
Multiple Recipients
What happens if we want to share a file with two different groups of people who have different shared passphrases? For example, Alice and Bob use the same passphrase to encrypt all of their shared project files because Bob doesn’t want to memorize additional passphrases. Now they are working on another project that includes Tina. Alice wants to give Tina a different passphrase. Bob refuses to memorize another passphrase. How can we enforce Least Privilege and still share files?
They can’t just encrypt two different copies of the file: one with the passphrase shared by Alice and Bob, and another with the passphrase shared by Alice and Tina. It would be hard to keep changes updated in both copies. A better approach is to share the same ciphertext and CEK among everyone, but to wrap the CEK separately with each passphrase. The task has to be built into the file encryption program. Because Alice is the only one who knows both passphrases, she must create the initial version of the file as follows:
■ Generate a CEK as usual.
■ Encrypt the file as usual.
■ For each passphrase, do the following:
Collect the passphrase and convert it into a KEK.
Wrap the CEK with this KEK.
Save the wrapped key with the encrypted file and with any other wrapped keys already saved there.
When Bob retrieves the file, he uses the passphrase he always shares with Alice. Internally, the program constructs a KEK from their passphrase. This KEK decrypts one of the two wrapped keys. This yields the CEK to decrypt the actual file. When Tina retrieves the file, she uses a different passphrase. This decrypts the other wrapped key, yielding the same KEK. Unlike files with a single passphrase, this file must reuse its CEK when encrypting new contents. Only Alice can replace the CEK, because she is the only person who knows both passphrases.
Key Wrapping and Cryptoperiods
We know that we mustn’t overuse a passphrase when encrypting files. If we randomly select our encryption keys and wrap them with our passphrase, we largely eliminate the risk of overuse. We no longer use the secrecy in the passphrase itself to encrypt the files; instead, we use newly generated random keys. The passphrase only protects the keys themselves. Thus, we can use the same passphrase for the maximum cryptoperiod with a minimum of risk.
Under NIST guidelines, the maximum cryptoperiod is 2 years. After that, we should choose a new passphrase.
Key “Splitting”
The simplest technique for key wrapping is called key splitting. It uses xor to perform the wrapping, as shown in FIGURE 8.7. In key splitting, the ideal KEK is not constructed from a passphrase. Both the CEK and KEK should be generated from a truly random source.
FIGURE 8.7 Key splitting with xor.
When we wrap keys, we perform two completely separate encryptions. The first encryption protects the data by using the CEK. The second encryption protects the CEK by using the KEK. We can use the same encryption algorithm for both, but it’s not necessary to do so. Because the CEK and KEK are chosen randomly, attackers can’t apply a known plaintext attack. Therefore, we can safely use the simplest possible encryption algorithm: xor.
Software Checklist for Wrapped Keys
Here’s a checklist of requirements for using wrapped keys to avoid the risk of reusing an encryption key. Even though the requirements use the term “wrapping,” they also apply to key splitting.
Whenever the software encrypts a file, it shall generate a new CEK.
The software shall use truly random numbers to generate the CEK.
The software shall use the hashed passphrase to generate the KEK, which it shall use to wrap the CEK.
When reencrypting a previously encrypted file, the software shall generate a new CEK. Alternatively, if the software supports multiple KEKs to protect a single file, the software shall reuse the CEK to retain existing wrapped keys.
After creating a CEK, the software shall create a wrapped copy of the CEK.
The software shall store the unwrapped CEK in RAM only as long as it is needed for the current encryption or decryption operation.
The software shall erase the unwrapped CEK from RAM as soon as the current encryption or decryption operation is finished.
The software shall not write the unwrapped CEK to the hard drive.
8.2.3 Separation of Duty: A Basic Principle
Sometimes we need to split a job between two or more people to ensure it’s done correctly. FIGURE 8.8 illustrates a particularly famous and critical example. The double-padlocked file cabinet stood in the control center of a Titan II nuclear missile site from the 1960s.
FIGURE 8.8 Separation of Duty for an early nuclear missile (photographed at the Titan Missile Museum).
Courtesy of Dr. Richard Smith.
The file drawer contained special codes required to launch the missile. The missile commander and deputy commander each had a separate padlock securing the drawer. Both officers had to unlock the cabinet in order to retrieve the codes. If either officer did not believe the launch orders were legitimate, then the codes stayed in the drawer and the missile couldn’t launch.
We often have cases where we can’t allow a person to act alone and take a serious action. The general solution is to break the action into steps that no single person can take independently. This is Separation of Duty.
However, the concept far predates nuclear weapons. It is a common tool in businesses. When paying suppliers, for example, companies break the process into multiple steps, each performed by a separate person. For example, one person enters the payments into the company ledgers, another person fills out the checks, and a third person signs the checks. Each step produces a record that auditors review periodically.
Some companies also implement Separation of Duty to authorize electronic funds transfers. One person on the team logs in and creates a transfer or a series of transfers; then a separate person logs in and separately authorizes the transfers. No transfer takes place until both steps are finished. This reduces the risk of fraud, and it also makes it more difficult for a hacker to single-handedly authorize a transfer. The hacker would have to retrieve authentication credentials for two separate individuals.
By enforcing Least Privilege, no one person can perform all of the steps independently. The check signer never gets blank checks. The check writer can’t add payments to the ledger. Individual checks are numbered and all are accounted for. No person can act alone to spend company money. At best, a person can insert a bill into the payment process, which leaves an obvious trail.
Separation of Duty Using Encryption
Our file encryption program can implement a simple form of Separation of Duty. For example, Bob wants Alice and Tina to look at the encrypted file only if both are present. In other words, neither Alice nor Tina has permission to look at the file by herself. They can’t decrypt the file unless each one provides her passphrase, one after the other.
Alice and Tina must choose individual secret passphrases. We will use these passphrases to construct two different KEKs, one to wrap keys for Alice and the other to wrap keys for Tina.
To implement Separation of Duty, we use key splitting. Again, the file encryption program has to include this procedure. The encryption takes place as follows:
■ Generate a CEK as usual.
■ Encrypt the file as usual.
■ Generate another random key, called S1.
■ Compute CEK xor S1 to yield S2.
■ Wrap S1 with Alice’s passphrase KEK.
■ Wrap S2 with Tina’s passphrase KEK.
To decrypt, the program first collects the passphrases from Alice and Tina. If both are present and provide their passphrases, the program can unwrap the two key splits. Once unwrapped, the program xors the two together. This produces the CEK, so the program can decrypt the file.
8.2.4 DVD Key Handling
The DVD-CSS uses a combination of key wrapping and key splitting to store encryption keys on a DVD. The first set of keys resides on the hidden first track of the DVD (FIGURE 8.9). (See Section 7.5 for an introduction to the DVD-CSS.)
FIGURE 8.9 Keys on the DVD hidden track.
The first important key on the DVD is the “disk key.” It is a random key generated for the specific DVD edition. The hidden track contains a set of 409 wrapped disk keys. Each key is encrypted using a secret “player key” assigned to a particular manufacturer of DVD players. When a player loads a DVD, it searches the hidden track for the disk key wrapped with its player key. The player unwraps the disk key and then calculates the key’s hash. If the answer matches the “hashed disk key” on the hidden track, then the player has decrypted the disk key.
The DVD’s actual contents are encrypted separately using a “title key” and a set of “sector keys.” Each sector on the DVD is encrypted with its own sector key. This key is saved in the sector’s header, split with the title key. FIGURE 8.10 illustrates the process of decrypting a DVD sector.
FIGURE 8.10 Decrypting a DVD sector.
The DVD producer begins with a digitized film or other program material in plaintext; then the producer generates a title key. The program material is encrypted, sector by sector, each using a separately generated key. The key is split with the title key and saved with the encrypted sector.
The producer may now share the encrypted program material with potential publishers. The program material doesn’t need special protection because it has been encrypted. The producer must just ensure that the title key remains secret.
To publish a DVD, the DVD publisher receives the program material from the producer. The publisher’s staff works with the encrypted program material. They do not need the title key to construct the DVD for publication.
To finalize the disk for publication, the publisher generates a disk key. The key is then encrypted with the 409 player keys and written to the hidden track. This allows any approved DVD player to retrieve the disk key. The disk key is specific to that particular edition of the DVD; the publisher may change it in later editions.
The publisher also saves a wrapped copy of the title key on the disk. The publisher wraps the title key with the disk key and saves the wrapped key on the disk.
Implementing Separation of Duty with Encryption
DVD-CSS uses secret keys to implement Separation of Duty between the content producer, publisher, DVD player manufacturer, and DVD purchaser. Shared secret keys remain secret under threat of legal action. To receive a key, the applicant must sign a contract with the CSS management authority. The recipient must agree to keep the key secret and use it only as allowed in the contract. The system’s architecture penalizes a key’s recipient if their own key is leaked.
Modern mobile devices rely heavily on cryptography to protect their contents from theft. Although wrapped secret keys play an important role in mobile security, shared secrets are too vulnerable to use extensively. If an attacker retrieves an important shared secret key, existing manufactured devices lose their security benefits and much of their commercial value.