Stream Ciphers

Whenever your browser establishes a “secure” connection to a web site, it encrypts the data. Traditionally, the browser and site use a stream cipher called Rivest Cipher #4 (RC4), although some sites use newer techniques.

Stream ciphers use a deceptively simple mechanism: you combine the plaintext data, bit by bit, with “key” bits, using the exclusive or operation. This is often abbreviated xor, and denoted by ⊕ - a circle with a cross.

A conventional stream cipher like RC4 consists of three parts:

  • a shared secret,
  • a process for generating a random-looking bit stream, and
  • the xor operation.

RC4, for example, can use 128 bits of shared, secret data to generate a random-looking bit stream. This bit stream is then combined, bit by bit, with the message being sent.

When Alice sends a message to Bob, encryption happens as follows. Ahead of time, Alice and Bob share their secret. When Alice has a message to send to Bob, she uses the shared secret and the RC4 cipher to encrypt it. Upon receipt of the encrypted message, Bob uses the shared secret and the RC4 cipher to decrypt it. This is much more convenient that a one-time pad, which requires a separate shared secret equal to the size of every message sent.

The process for generating the bit stream is the heart of the technique, and usually referred to as the cryptographic algorithm. Even if an eavesdropper (call him Peeping Tom) happens to see part of this bit stream, he should not be able to predict other parts of the bit stream. Ideally, Tom would need a copy of the shared secret in order to recover the message. There should be no way to recover the message that's easier than trying to guess the 128-bit secret through trial and error.

This make things much simpler for Alice and Bob. Before sending a message, they share a 128-bit secret. When Alice sends her message, she starts up the RC4 algorithm, feeds it her key, and encrypts her message, bit by bit, using xor. Upon receipt, Bob runs RC4, enters his copy of the shared secret, and gets back the same bit stream. He decrypts the message by applying xor to the message and the bit stream.

The security of a stream cipher depends on the quality of the algorithm, but it also depends on proper use. In particular, neither Alice nor Bob should intentionally use that shared secret ever again to send a message. In fact, if Bob replies to Alice's message, he must use a different shared secret. If he uses the same shared secret, he will encrypt his message with the same bit stream that Alice used. Then Peeping Tom can retrieve both messages scrambled together, as shown here.

Wordpress tag: 
Post category: 

Encrypting with XOR: A Graphic Example

The exclusive or operation - a logical function applied to binary bits, like AND, OR, and NOT - is a fundamental encryption technique. It is often used in stream ciphers, which are widely used in web browsers when connecting to secure web servers.

 

When used properly, this technique provides strong protection. In fact, it is the basis for the one-time pad, the only provably uncrackable encryption. However, this protection is easily eroded if the cipher is not used correctly.

Xor is a trivial operation for computer logic to perform (click here for the details). The operation often appears as a built-in machine instruction so that software can perform it in a single machine operation.

If Alice wants to send a secret message to her friend Bob, she takes the sequence of bits in the message (the plain text) and a sequence of bits known only by her and Bob - the key. To encrypt, she combines the plain text and the key, bit by bit, using xor.

In a one-time pad, Alice and Bob must use a different set of secret, randomly generated bits for every message they exchange.

In a stream cipher, Alice and Bob share a much smaller number of secret bits and use them to generate a long, hard-to-guess sequence of bits. The stream cipher relies on a cryptographic algorithmto generate that long sequence from a small, shared secret. This generated sequence is then combined with the message using xor.

A Graphic Example

Below we have the handwritten message "Send Cash" embedded in a 128 by 128-bit image. Black indicates no color, so the black text in the image contains zero bits, and the white space contains 1 bits. 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 will combine the two matrices using xor:

Message saying \" width=

Encryption key

Message "Send Cash"

XOR

Encryption Key

When we apply xor bit-by-bit to the two matrices, we get the following 128 by 128 matrix of encrypted bits:

Encrypted \" width=

Encrypted "Send Cash"

Yes, this looks like nothing more than a mottled gray block, and it doesn't look a lot different from the gray-block image of the encryption key. If we look closely, the actual bits are different. Here is a closeup of the upper-left corner of the key bits and the encrypted bits. Most of the bits are identical in the two closeups. The bits in the lower-right closeup are different.

Upper left corner of the key
Upper left corner of the encrypted data

In the closeup, most of the image is the same in both the key and the ciphertext. The plaintext "Send Cash" message consists of white space (one bits) except where the black letters (zero bits) appear. The xor operation combines black bits in the key with white bits in the message to yield black bits in the encrypted message. 

The closeup's lower right corner captures part of the letter "S" in the message. The black plaintext combines with black key bits to yield white. White key bits are also reversed by the black plaintext.

Even though the key image and the encrypted message look similarly gray, they contain different bits. That difference hides the encrypted message.

Try it yourself

These example images are 128 by 128 bit maps in GIF format. If you have a program that can read GIF files, save them as bit maps, and apply the xor operation bit-by-bit, then you can easily repeat this operation. The examples here were processed by Matlab, a commercial package, but there are numerous other packages that can reproduce the example.

Download these images:

If you apply the xor operation to the first two bit maps, you produce the third. If you combine the key with the encrypted message (k ⊕ e), you will reproduce original "Send Cash" message.

Exclusive-Or - ⊕ - xor

The following table shows how the xor operation transforms individual bits. Let m be a bit from the plain text message, and kbe a bit from the key. The ⊕ column shows the resulting bit.

mk
000
011
101
110

We can also describe the xor operation in terms of traditional logic operations AND, OR, and NOT. Here we use "C" programming language notation: NOT = !, AND = &, OR = |.

(!m & k) | (m & !k)

To decrypt a message, Bob takes his own copy of the key bits, and applies the same xor transformation to the message, bit by bit.

Post category: 

One-Time Pads

The one-time pad is the only encryption technique that has been mathematically proven to be uncrackable. While hard to use, it has often been the choice for highly sensitive traffic. Soviet spies used one-time pads in the 1940s and -50s. The Washington-Moscow "hot line" also uses one-time pads. However, the technique is hard to use correctly.

 

To use a one-time pad, Alice and Bob must produce a huge number of random bits and share them secretly. When Alice has a message to send to Bob, she retrieves a number of random bits equal to the length of her message, and uses them to be the message’s key. She applies the exclusive or operation (xor) to the key and the message to produce the encrypted message.

The key must be exactly the same size as the message. The key must also consist of completely random bits that are kept secret from everyone except Alice and Bob.

When Bob receives the message, he retrieves the same bits from his copy of the random bit collection. He must retrieve the same random bits in exactly the same order that Alice used them. Then Bob uses the sequence of random bits to decrypt the message. He applies the xor operation to the message and the key to retrieve the plain text.

When properly used, it is mathematically impossible to crack a message encrypted by a one time pad. This was first described by Claude Shannon in the 1940s as part of the development of information theory. A one-time pad is impossible to crack because knowledge of the cipher text does not reduce uncertainty about the contents of the original, plain text message.

One time pads are not generally practical:

  • It’s hard to provide enough randomly-generated bits to both Bob and Alice to protect all anticipated messages.
  • It’s hard to keep that much data secret.
  • It’s hard to use the bits in the right order at both ends.
  • It’s hard to avoid reusing the bits by mistake.

Web browsers and servers use conventional stream ciphers like RC4 instead of one time pads because they are much easier to use and provide very strong, if not provably impenetrable, security.

When Soviet spies used one-time pads, they used a decimal number code instead of binary bits. In binary, the xor operation is essentially an "add without carry" in which we discard the overflow: in particular, 1+1=0. In a decimal code, add without carry just discards the overflow, as in 7+7 = 4, or 8+8=6. Decryption used the opposite "subtract without borrow" with the same set of digits used as the key. 

The one-time pads were printed up in tiny books, and the spies would discard pages of numbers as they were used in messages. Marcus Ranum has a photo of such a book in his One-Time PAD FAQ.

There is a lot of confusion about one-time pads (see the article). Some vendors use the term simply because one-time pads are provably secure, and they hope that the name by itself will convey impenetrability to their product. Such products are called snake oil in the crypto community. Even worse, some people on the Net will try to explain one-time pads and get it wrong. The hardest thing for many people is the notion of entropy or true randomness. No, you don't get random numbers from Excel!

Related Ciphers

Here are some other cipher terms that often appear in conjunction with one-time pads:

  • Vigenère cipher - a code in which each letter in the plain text is replaced by a corresponding letter taken from one of several different alphabets. The different alphabets are usually constructed by shifting the plain text alphabet by different numbers of steps. The "key" identifies the sequence of alphabets used. Cipher discs are often used to implement Vigenère ciphers. 
  • Vernam cipher - A Vigenère cipher in which the alphabet consists only of the binary values 0 and 1. Vernam's original cipher used a repeating key (reusing the bit stream) but the cipher remained easy to break even with very long keys. He subsequently developed a version where the key did not repeat; this was the first implementation of a one-time pad.
  • Stream cipher - a Vernam cipher in which the key is generated by a pseudo-random number generator, to eliminate the repeating bit stream.

References

Ranum, M. (1995) One-Time-Pad (Vernam's Cipher) Frequently Asked Questions. web site.

Shannon, C. (1949) Communication Theory of Secrecy Systems. Bell System Technical Journal 28 (4): 656–715.

Wordpress tag: 
Post category: 

That's not a one-time pad!

It's amazing how subtle a one-time pad really is. On one level they're deceptively simple: you simply match up the text of your message with a collection of "random bits" you share with the recipient. To decrypt, the recipient matches up a copy of those "random bits" to retrieve the message.

The trick is in the definition of "random bits."

If all the characters come from a truly unpredictable source, then you have a one-time pad. And, if you really want to use a one-time pad, you must share as many random bits as you imagine you will ever need for messages. That's a lot of random bits!

No shortcuts are allowed. If you try to 'compress' the random bits, or 'reconstruct' them using an algorithm, then it's no longer a one-time pad. If you get them from any sort of structured source then, again, it's not a one-time pad.

Another essential feature: the collection of random bits must not be shared with anyone except the intended senders and recipients of the messages. If other people can find the set of random bits - for example, if it's based on a published text of some sort - then it's not secret enough for a true one-time pad. Someone might get away with using it for a while, but it's not a really secure approach.

Moreover, the bits must never be used for more than one message. One-time pads have been cracked many times in practice, usually because the random bits were used to encrypt more than one message.

Let me run over some inaccurate examples presented in various web sites as one-time pads. I'll skip the "snake oil" encryption products that inaccurately claim unbreakability by calling themselves one-time pads. There are enough bogus examples without them.

The Key to Rebecca

Several web pages claim that the spy in Ken Follet's novel The Key to Rebecca uses a one-time pad. The book describes how the spy used Daphne du Maurier's classic novel Rebecca as a codebook to encrypt his messages. One particularly mistaken web site claims that the codebook was "du Maurier's Rebecca of Sunnybrook Farm" (a book actually by author Kate Douglas Wiggin).

To be fair, that particular web site provides a fine description of the encryption process, even if the process is mislabeled. Each message uses the next page in the novel as its key. To encrypt a message, the spy would do an 'add without carry' of the characters in the message with corresponding characters taken from that page of the book. To decrypt, the recipient at the Wehrmacht would take the corresponding page of the novel and use the opposite 'subtract without borrow' operation to recover the plain text message.

However, this does not describe a one-time pad. This is simply a Vigenère cipher for which the key is taken from a book.

It is not a one-time pad for the simple reason that the key itself - the text of the novel Rebecca - is not random. The key consists of English prose text which itself has numerous patterns. The key will retain detectable patterns when combined with a plain text message in German.

If the book Rebecca consisted entirely of randomly generated characters, then it would come closer to being a one-time pad, though it would be far less entertaining as a mystery-romance novel.

Music CDs, MP3s, etc.

A few web sites claim that you can use a well-known music CD, MP3 recording, or other media file as the random bits for a one-time pad.

It should be obvious what the problem is: if the track contains random noise, then it might be more appropriate for a one-time pad. Music and other entertainment media files, by definition, contain patterns: chords, refrains, voiced words, images, etc. If random noise were entertaining, we wouldn't have needed to actually broadcast radio signals in the previous century: people would have just listened to the static between stations.

Secrecy

The other problem with these examples are that they all use prepackaged data as the "random data." Even if the prepackaged data were boring collections of random characters, or audio/visual static, the packages would be available to third parties. Published data is, by definition, not secret. No matter how random it might be, we eliminate the theoretical secrecy of the one-time pad by using data that is available to people besides Alice and Bob.

Post category: 

Stream Cipher Reuse: A Graphic Example

Take a look at the following image. You should see two different 'messages' here.

Smiley overlaying the \" title=

  Two messages

This particular mis-mash of messages reflects the failure of otherwise strong cryptography: the improper implementation of a one-time pad or a stream cipher.

This same mistake let American cryptanalysts decode thousands of Soviet spy messages in the 1940s and -50s. The decoded messages helped uncover espionage at the Manhattan Project. The Soviets made the mistake of reusing the keys for their one-time pads.

The mistake has also cropped up with stream ciphers used on computer networks. If you use the same stream of bits to encrypt two or more different messages, an attacker can eliminate the encryption by combining the two messages. Particularly notorious examples include the tragically misnamed Wired Equivalent Privacy (WEP) in 802.11/WiFi products, and Microsoft's first implementation of the Point to Point Tunneling Protocol (PPTP).

So why does this happen?

The problem is based on the behavior of the add without overflow operation used in one-time pads, which in the digital world involves the exclusive-or operation (called "xor" for short - click here for an explanation).

If used properly, xor is an effective way to encrypt data. However, it leaks data if not used carefully. The leakage arises from the binary logic of the combination (click here for an explanation).

Reusing the Key

In a different example, we worked with a 128 x 128 image containing this message:

Message saying \" title=

 "Send Cash" message

 

We encrypted this image by applying the xor operation. We used a random 128 by 128 bit map for the encryption key. This yielded the following gray block:

Encrypted \" title=

Encrypted "Send Cash"

 

Let's use the same encryption key to encrypt another 128 by 128 bit mapped image:

Smiley imageEncryption key

Smiley image              XOR    Encryption Key

Both the key and the encrypted data yield images that look like similar gray blocks. This is how it should be: a matrix randomly scattered with 0 and 1 bits should look gray. The encryption key and the encrypted data should look random, with no distinct patterns.

Thus, the encrypted Smiley yields another gray block:

Encrypted Smiley

Encrypted Smiley

 

Now, let's combine the two encrypted images using xor:

Encrypted SmileyEncrypted Send Cash

  Encrypted Smiley   XOR  Encrypted "Send Cash"

Again, each looks like nothing more than a gray block. A closer look (as in this other example) will show that individual bits may differ.

The xor operation eliminates the key from both images, and leaves us with the images themselves:

Smiley overlaying the \" title=

  Two messages

 

In real-world cases like Venona, WEP, and PPTP, we aren't usually encrypting images. However, the underlying plain text, whether literally text or encoded network protocol data, has distinctive patterns. Skilled cryptanalysts can identify these patterns and can extract the two messages from the mixed-up data.

Try it yourself

These example images are 128 by 128 bit maps in GIF format. If you have a program that can read GIF files, save them as bit maps, and apply the xor operation bit-by-bit, then you can easily repeat this operation.

The examples here were processed by Matlab, a commercial package, but there are numerous other packages that can reproduce the example. Download these images:

Apply the xor operation to the first two bit maps to produce the third. Combine the key with the encrypted message (k ⊕ e) to reproduce original "Send Cash" message.

Use the same process on the Smiley to produce its encrypted form. When you combine the two encrypted messages, you end up with the overlaid images. -

The Logic Equations

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,

 

and 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.

 

You can work this out from the description of xor provided on this other page. In terms of fundamental digital operations AND (&), OR (|) and NOT (~), the xor operation is defined as follows:

a ⊕ k = (~a & k) | (a & ~k)

If you substitute this definition in the equations above, you find that combining the encrypted messages yields the same result as combining the plain text messages.

References

Borisov, N., Goldberg, I., Wagner, D. (2001) Intercepting Mobile Communications: The Insecurity of 802.11. 7th Annual International Conference on Mobile Computing and Networking (ACM SIGMOBILE). Rome, Italy, July.

Benson, R. (2001) The Venona Story. web page. National Security Agency, Center for Cryptologic History. The NSA's web site has a whole section devoted to  the Venona story.

Schneier, B., Mudge. (1998) Cryptanalysis of Microsoft's Point to Point Tunneling Protocol (PPTP). Proceedings of the 5th ACM Conference on Communications and Computer Security. November.

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

Post category: