Using the Same Stream-Cipher Encryption Key

A stream cipher is a cipher that encrypts and decrypts data one unit at a time, where a unit is usually 1 byte. (RC4 is the most famous and most used stream cipher. In addition, it is the only stream cipher provided in the default CAPI installation in Windows.) An explanation of how stream ciphers work will help you realize the weakness of using the same stream-cipher key. First an encryption key is provided to an internal algorithm called a keystream generator. The keystream generator outputs an arbitrary length stream of key bits. The stream of key bits is XORed with a stream of plaintext bits to produce a final stream of ciphertext bits. Decrypting the data requires reversing the process: XORing the key stream with the ciphertext to yield plaintext.

A symmetric cipher is a system that uses the same key to encrypt and decrypt data, as opposed to an asymmetric cipher, such as RSA, which uses two different but related keys to encrypt and decrypt data. Other examples of symmetric ciphers include DES, 3DES, AES (Advanced Encryption Standard, the replacement for DES), IDEA (used in Pretty Good Privacy [PGP]), and RC2. All these algorithms are also block ciphers; they encrypt and decrypt data a block at a time rather than as a continuous stream of bits. A block is usually 64 or 128 bits in size.

Why People Use Stream Ciphers

Using stream ciphers, you can avoid the memory management game. For example, if you encrypt 13 bytes of plaintext, you get 13 bytes of ciphertext back. However, if you encrypt 13 bytes of plaintext by using DES, which encrypts using a 64-bit block size, you get 16 bytes of ciphertext back. The remainder three bytes are padding because DES can encrypt only full 64-bit blocks. Therefore, when encrypting 13 bytes, DES encrypts the first eight bytes and then pads the remaining five bytes with three bytes, usually null to create another eight-byte block that it then encrypts. Now, I m not saying that developers are lazy, but, frankly, if you can get away with not having to get into memory management games, the happier you may be!

People also use stream ciphers because they are fast. RC4 is about 10 times faster than DES in software, all other issues being equal. As you can see, good reasons exist for using stream ciphers. But pitfalls await the unwary.

The Pitfalls of Stream Ciphers

First, stream ciphers are not weak; many are strong and have withstood years of attack. Their weakness stems from the way developers use the algorithms, not from the algorithms themselves.

Note that each unique stream-cipher key derives the same key stream. Although we want randomness in key generation, we do not want randomness in key stream generation. If the key streams were random, we would never be able to find the key stream again, and hence, we could never decrypt the data. Here is where the problem lies. If a key is reused and an attacker can gain access to one ciphertext to which she knows the plaintext, she can XOR the ciphertext and the plaintext to derive the key stream. From now on, any plaintext encrypted with that key can be derived. This is a major problem.

Actually, the attacker cannot derive all the plaintext of the second message; she can derive up to the same number of bytes that she knew in the first message. In other words, if she knew the first 23 bytes from one message, she can derive the first 23 bytes in the second message by using this attack method.

To prove this for yourself, try the following CAPI code:

/* RC4Test.cpp */ #define MAX_BLOB 50 BYTE bPlainText1[MAX_BLOB]; BYTE bPlainText2[MAX_BLOB]; BYTE bCipherText1[MAX_BLOB]; BYTE bCipherText2[MAX_BLOB]; BYTE bKeyStream[MAX_BLOB]; BYTE bKey[MAX_BLOB]; ////////////////////////////////////////////////////////////////// // Setup - set the two plaintexts and the encryption key. void Setup() { ZeroMemory(bPlainText1, MAX_BLOB); ZeroMemory(bPlainText2, MAX_BLOB); ZeroMemory(bCipherText1, MAX_BLOB); ZeroMemory(bCipherText2, MAX_BLOB); ZeroMemory(bKeyStream, MAX_BLOB); ZeroMemory(bKey, MAX_BLOB); strncpy(reinterpret_cast<char*>(bPlainText1), "Hey Frodo, meet me at Weathertop, 6pm.", MAX_BLOB-1); strncpy(reinterpret_cast<char*>(bPlainText2), "Saruman has me prisoner in Orthanc.", MAX_BLOB-1); strncpy(reinterpret_cast<char*>(bKey), GetKeyFromUser(), MAX_BLOB-1); // External function } ////////////////////////////////////////////////////////////////// // Encrypt - encrypts a blob of data using RC4. void Encrypt(LPBYTE bKey, LPBYTE bPlaintext, LPBYTE bCipherText, DWORD dwHowMuch) { HCRYPTPROV hProv; HCRYPTKEY hKey; HCRYPTHASH hHash; /* The way this works is as follows: Acquire a handle to a crypto provider. Create an empty hash object. Hash the key provided into the hash object. Use the hash created in step 3 to derive a crypto key. This key also stores the algorithm to perform the encryption. Use the crypto key from step 4 to encrypt the plaintext. */ DWORD dwBuff = dwHowMuch; CopyMemory(bCipherText, bPlaintext, dwHowMuch); if (!CryptAcquireContext(&hProv, NULL, NULL, PROV_RSA_FULL, CRYPT_VERIFYCONTEXT)) throw; if (!CryptCreateHash(hProv, CALG_MD5, 0, 0, &hHash)) throw; if (!CryptHashData(hHash, bKey, MAX_BLOB, 0)) throw; if (!CryptDeriveKey(hProv, CALG_RC4, hHash, CRYPT_EXPORTABLE, &hKey)) throw; if (!CryptEncrypt(hKey, 0, TRUE, 0, bCipherText, &dwBuff, dwHowMuch)) throw; if (hKey) CryptDestroyKey(hKey); if (hHash) CryptDestroyHash(hHash); if (hProv) CryptReleaseContext(hProv, 0); } void main() { Setup(); // Encrypt the two plaintexts using the key, bKey. try { Encrypt(bKey, bPlainText1, bCipherText1, MAX_BLOB); Encrypt(bKey, bPlainText2, bCipherText2, MAX_BLOB); } catch (...) { printf("Error - %d", GetLastError()); return; } // Now do the magic. // Get each byte from the known ciphertext or plaintext. for (int i = 0; i < MAX_BLOB; i++) { BYTE c1 = bCipherText1[i]; // Ciphertext #1 bytes BYTE p1 = bPlainText1[i]; // Plaintext #1 bytes BYTE k1 = c1 ^ p1; // Get keystream bytes. BYTE p2 = k1 ^ bCipherText2[i]; // Plaintext #2 bytes // Print each byte in the second message. printf("%c", p2); } }

You can find this example code on the companion CD in the folder Secureco\Chapter 6\RC4Test. When you run this code, you ll see the plaintext from the second message, even though you knew the contents of the first message only!

In fact, it is possible to attack stream ciphers used this way without knowing any plaintext. If you have two ciphertexts, you can XOR the streams together to yield the XOR of the two plaintexts. And it s feasible to start performing statistical frequency analysis on the result. Letters in all languages have specific occurrence rates or frequencies. For example, in the English language, E, T, and A are among the most commonly used letters. Given enough time, an attacker might be able to determine the plaintext of one or both messages. (In this case, knowing one is enough to know both.)


	To be accurate, you should never use the same key to encrypt data regardless of encryption algorithm, including block ciphers such as DES and 3DES. If two plaintexts are the same text or certain parts of the plaintexts are the same, the ciphertexts might be the same. The attacker might not know the plaintext, but he does know that the plaintexts are the same or that a portion of the plaintexts is the same. That said, sometimes the attacker does know some plaintext. For example, many file types contain well-defined headers, which can often be easily deduced by an attacker.

What If You Must Use the Same Key?

My first thought is that if you must use the same key more than once, you need to revisit your design! That said, if you absolutely must use the same key when using a stream cipher, you should use a salt and store the salt with the encrypted data. A salt is a value, selected at random, sent or stored unencrypted with the encrypted message. Combining the key with the salt helps foil attackers.

Salt values are perhaps most commonly used in Unix-based systems, where they are used in the creation of password hashes. Password hashes were originally stored in a plaintext, world-readable file (/etc/passwd) on those systems. Anyone could peruse this file and compare his or her own password hash with those of other users on the system. If two hashes matched, the two passwords were the same! Windows does not salt its passwords, although in Windows 2000 and later the password hashes themselves are encrypted prior to permanent storage, which has the same effect. This functionality, known as Syskey, is optional (but highly recommended) on Windows NT 4.0 Service Pack 3 and later.

You can change the CAPI code, shown earlier in The Pitfalls of Stream Ciphers, to use a salt by making this small code change:

 if (!CryptCreateHash(hProv, CALG_MD5, 0, 0, &hHash)) throw; if (!CryptHashData(hHash, bKey, MAX_BLOB,0)) throw; if (!CryptHashData(hHash, bSalt, cbSaltSize, 0)) throw; if (!CryptDeriveKey(hProv, CALG_RC4, hHash, CRYPT_EXPORTABLE, &hKey)) throw;

This code simply hashes the salt into the key; the key is secret, and the salt is sent with the message unencrypted.


	The bits in a salt value consist of random data. The bits in the key must be kept secret, while the bits in the salt value can be made public and are transmitted in the clear. Salt values are most useful for transmitting or storing large numbers of nearly identical packets using the same encryption key. Normally, two identical packets would encrypt into two identical ciphertext packets. However, this would indicate to an eavesdropper that the packets are identical, and the packets might then be attacked simultaneously. If the salt value is changed with every packet sent, different ciphertext packets will always be generated, even if the plaintext packets are the same. Because salt values need not be kept secret and can be transmitted in plaintext with each ciphertext packet, it is much easier to change salt values once per packet than it is to change the key value itself.


	All ciphers in the .NET Framework classes are block ciphers. Therefore, you have little chance of making the kinds of mistakes I ve described in this section when you use these classes.