Attacks on Stream Ciphers	Dr. Rick Smith Computer and Information Sciences
Dr. Smith Home | Research | Classes | Blackboard | Cryptosmith | QMCS Home | UST A-Z | UST Home last update: Friday, November 16, 2007

Stream ciphers are easy to build but hard to use safely. We will use the following image to show why:

The image contains two different message. For now, simply look at this image and identify the two messages.

Encryption with XOR

All encryption relies on information that is secret, unpredictable, and hard for outsiders to guess. Typically, we talk about such information as being both secret and random. In general, encryption consists of combining a known message (the plain text) with secret information (the key) to yield an encrypted message that outsiders can't read.

The simplest but potentially the strongest type of encryption uses the exclusive or operation (also called "xor," denoted by ⊕) to encrypt the plain text bit-by-bit with the key.

The exclusive or operation (A xor B, or A ⊕ B, if you prefer).works bit-by-bit as follows:

Essentially, if the two bits differ, the result is 1; if the two bits match, the result is 0.

If variable a represents a plain text message and k represents the encyrption key, then a xor k yields an encrypted message. If the encrypted message is A, then A xor k essentially decrypts the message, removing the influence of the key bit.

Essentially, a stream cipher uses a sequence of random-seeming bits to hide a message. Let's call the readable message the plain text and the sequence of random-seeming bits the key. To encrypt, take bits from the plain text and bits from the key, and combine them one at a time. We use to combine each message bit with a key bit.

The recipient must decrypt the message to read it. In order to decrypt it, the recipient must be able to produce exactly the same key used by the sender. The recipient applies the xor operation bit-by-bit to the encrypted message and the key to produce the plain text message. This is how we keep the message secret from eavesdroppers: no one else can read the message except those who can reproduce the same key.

Stream Cipher Encryption

A stream cipher is a cipher that transforms its plain text one bit at a time. All modern stream ciphers use the xor operation.

To show a stream cipher graphically, we use a message built as a 2-dimensional, bit-mapped image ("Send Cash"). That is our plain text. The image is 128 bits high by 128 bits wide, with 0 bits indicating white space and 1 bits indicating black.

(I realize that black and white are less exciting than color, but the matrix algebra is much simpler this way. Colors require another matrix dimension, and that makes the xor operation a lot harder to apply).

For a key, we have collected a 128 by 128 matrix of random bits. In fact, the bits come from a web site, random.org, that uses radio noise to generate random data for experiments like this.

We show the encryption here: the plain text is combined bit-by-bit with the key ("encryption key") to yield the encrypted message.

	⊕		=>
Plain text message	xor	Encryption key	yields	"Send Cash" Encrypted

Both the encryption key and the encrypted message look like gray blocks. In fact, it's hard to tell the difference without looking very closely. That's exactly how keys and encrypted data are supposed to look: they should look like non-uniform patterns of 0s and 1s. If you look very, very closely, you will find they contain different bits:

The closeup bitmaps are taken from the upper left corner of the encrypted message and from the encryption key. If you look closely, you will see that these two bitmaps are mirror images: the white areas in one are dark areas in the other. This is because the upper left corner of the original message is blank space: it is a white area made up of 0 bits. When we xor a 0 bit and a key bit, we negate the key bit. When we encrypt a block of white space, we get the inverted image of the corresponding key bits. (This yields another security problem described later).

We recover the original message by applying xor to the encrypted message and the encryption key:

	⊕		=>
Plain text message	xor	Encryption key	yields	"Send Cash" Encrypted

A typical stream cipher is Rivest Cipher #4 (RC4), which appears in Web browsers. It is traditionally used to encrypt messages exchanged with 'secure' Web sites when sending sensitive information like passwords or credit card numbers. In practice, RC4 shares a relatively small amount of secret information between the client and the Web site. This small amount of secret information is used to generate a sequence of random-looking bits that serve as the "key" for encrypting and decrypting data.

Many modern ciphers are block ciphers that transform data in blocks of multiple bits, usually 64 or 128 bits at a time. The Data Encryption Standard (DES) and the Advanced Encryption Standard (AES) are block ciphers. There are standard techniques called cryptographic modes that allow a designer to use a block cipher as a stream cipher. These techniques use a shared secret to generate a sequence of encrypted blocks that are combined with the plain text using the xor operation.

The strongest type of encryption is the one time pad, a technique that uses the xor operation with vast amounts of secretly shared random data. The design is deceptively simple: the sender and recipient share in secret a vast amount of totally random, unpredictable data bits. When one end sends a message of a certain length, it retrieves that many bits from the collection of random bits. The retrieved random bits serve as the key. It encrypts by applying the xor operation bit-by-bit to the message and the key.

When the message arrives, the recipient retrieves key bits from the random pool to match the message's length. It decrypts by applying xor bit-by-bit to the encrypted message and the key. This yields the message. Neither the sender nor the recipient ever use that same key again.

That last step is essential to making the encryption perfect.

People rarely use one time pads in practice for two reasons:

• It's hard to generate truly random data in large amounts
• It's hard to distribute enough random data to the sites that have to communicate

There are a few well known uses of one time pads. The "hot line" that connected Washington, DC, with Moscow during the Cold War used a one time pad. Soviet spies relied heavily on one time pads towards the end of World War II and afterwards. In fact, Moscow misused the one time pads, which allowed US cryptanalysts to crack thousands of spy messages early in the Cold War.

Reused Keys: The Classic Problem

If you use the same encryption key for two different messages, then an eavesdropper can eliminate the encryption key (and thus, the encryption) by applying xor to the encrypted messages by themselves. In other words,

Let a,b be plaintext messages, let A,B be corresponding encrypted messages, with k as the key;

If a ⊕ k = A,

and b ⊕ k = B,

then a ⊕ b = A ⊕ B.

For example, let us take the encryption key from our first example and xor it with a different image:

	⊕		=>
Smiley picture	xor	Encryption key	yields	Encrypted Smiley

Again, the encrypted form looks like a grey block and, again, you will see differences if you look closely. You might notice that this time the corners will match the key bits exactly: when we xor 1 with another value, we get that value back.

Now, it gets interesting. Look what happens when we xor the encrypted images together:

	⊕		=>
"Send Cash" Encrypted	xor	Smiley Encrypted	yields	Both messages overlaid

When we use xor to combine the two encrypted messages, the encryption keys cancel each other out. We are left with the plain text messages overlaid, one upon the other.

This isn't just a problem for imagery. If you xor two text messages together, it may still look like nonsense to most people, but a codebreaker will be able to find statistical patterns. A properly encrypted message looks statistically random. If you simply mix two pieces of text together, it won't be random since text itself is made up of patterns.

Try it yourself

It's easy to repeat this example if you have software that will read a bitmapped graphic from a GIF file into a 2D array of binary values. I used Matlab^® to produce these examples. All you need to do is download the GIF files for the plaintext images and the key. Apply xor to the appropriate pair of matrices, bit by bit, and you will get the same results.

This has been a real problem

Reused keys have cropped up fairly often, both with one time pads and with stream ciphers.

The most notorious example of reusing one time pads yielded a project called "Bride" and later "Venona" in which US cryptanalysts cracked thousands of messages sent by Soviet spies in the 1940s and 1950s.

Misused stream ciphers have cropped up in various cryptographic systems. The classic mistake is to use a shared secret key for a single connection and apply the key to the data stream in each direction. Thus an eavesdropper can eliminate the key simply by collecting the data stream in each direction and xor'ing the two together. Early versions of the SSL protocol (Secure Socket Layer, which is typically used by Web browsers to protect Web traffic) had this problem, as did some early Microsoft crypto implementations, most notably PPTP.

Dealing with the Problems

Reusing the key

The general solution is don't do that. Traditionally, developers were inclined to slap a shared secret key directly into cipher with no muss or fuss. While this provided a little secrecy, it didn't do justice to the level of security modern ciphers could provide.

In practice, careful designers don't use secret keys directly. Instead, they use the shared secret to generate additional keys, often by applying a cryptographic hash function. For example, version 3 of the SSL protocol applies a cryptographic hash to secret information shared between the Web browser and the secure Web site. This produces separate keys for encrypting data to and from your Web browser plus separate "integrity" keys that help detect changes made to messages in either direction.

Modifying known plaintext

This problem can't be fixed by relying exclusively on encryption, especially with stream ciphers. You need to use a separate mechanism to protect the message's integrity. An effective approach is to use a cryptographic hash on the message contents combined with a secret key (an "integrity" key).

References

National Security Agency (undated). Venona. web page.

Schneier, B. N. (1994) Practical Cryptography (2nd edition). Prentice Hall.

Smith, R. E. (1997) Internet Cryptography. Addison Wesley.

Stinson, D. R. (1995) Cryptography: Theory and Practice. CRC Press.

This work by Dr. Rick Smith is licensed under a Creative Commons Attribution-Share Alike 3.0 United States License.