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

This particular mish-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:

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:

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

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

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

  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:

  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 the individual images above in GIF format, plus the plaintext smiley and key block below:

 

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.