Mark Stamp - Information Security

The bad news is that, unlike a simple substitution, the double transposition does nothing to disguise the letters that appear in the message. The good news is that the double transposition appears to thwart an attack that relies on the statistical information contained in the plaintext, since the plaintext statistics are dispersed throughout the ciphertext.

Even this simplified version of the double transposition is not entirely trivial to break. The idea of smearing plaintext information through the ciphertext is so useful that it is employed by modern block ciphers, as we will see in the next chapter.

The one‐time pad, which is also known as the Vernam cipher, is a provably secure cryptosystem. Historically it has been used in various times and places, but it's not practical for most situations. However, it does nicely illustrate some important concepts that we'll see again later.

For simplicity, let's consider an alphabet with only eight letters. Our alphabet and the corresponding binary representation of letters appear in Table 2.1. It's important to note that the mapping between letters and bits is not secret. This mapping serves a similar purpose as, say, the ASCII code, which is not much of a secret either.

Table 2.1 Abbreviated alphabet

Suppose that Trudy, who is working as a Nazi spy in London during World War II, wants to use a one‐time pad to encrypt the plaintext message

She first consults Table 2.1to convert the plaintext letters to the bit string

The one‐time pad key consists of a randomly selected string of bits that is the same length as the message. The key is then XORed with the plaintext to yield the ciphertext. For the mathematically inclined, a fancier way to say this is that we add the plaintext and key bits modulo 2.

We denote the XOR of bit with bit as . Since , decryption is accomplished by XOR‐ing the same key with the ciphertext. Modern symmetric ciphers utilize this magical property of the XOR in various ways, as we'll see in the next chapter.

Now suppose that Trudy uses the key

which is the correct length to encrypt her message above. Then to encrypt, Trudy computes the ciphertext as

Converting these ciphertext bits back into letters, the ciphertext message to be transmitted is srlhssthsr.

When her fellow Nazi spy, Eve, receives Trudy's message, she decrypts it using the same shared key and thereby recovers the plaintext

Let's consider a couple of scenarios. First, suppose that Trudy has an enemy, Charlie, within the Nazi spy organization. Charlie claims that the actual key used to encrypt Trudy's message is

Eve decrypts the ciphertext using the key given to her by Charlie and obtains

Eve, who doesn't really understand crypto, orders that Trudy be brought in for questioning.

Now let's consider a different scenario. Suppose that the Allies in London intercept Trudy's ciphertext, raising suspicions that she might be spying for the Nazis. The Allies are eager to read the message and Trudy is “encouraged″ to provide the key to her super‐secret message. Trudy claims that she is actually working against the Nazis, and to prove it, she provides the “key″

When the Allies “decrypt″ the ciphertext using this “key,″ they find

The Allies proceed to give Trudy a medal for her work against the Nazis.

While not a proof, these examples serve to illustrate why the one‐time pad is secure in a stronger sense than the ciphers we have previously considered. The bottom line is that if the key is chosen at random, and used only once, then an attacker who obtains the ciphertext has no useful information about the message itself—any “plaintext″ of the same length can be generated by a suitable choice of “key,″ and all possible plaintexts are equally likely. From a cryptographer's point of view, it doesn't get any better than that.

Of course, we are assuming that the one‐time pad cipher is used correctly. The key (or pad) must be chosen at random and used only once. And, since it is a symmetric cipher, the key must be known by both the encryptor and the intended recipient—and nobody else can know the key.

Since we can't do better than provable security, why don't we always use the one‐time pad? Unfortunately, the cipher is impractical for most applications. Why is this the case? The crucial problem is that the pad is the same length as the message and since the pad is the key, it must be securely shared with the intended recipient before the ciphertext can be decrypted. If we can securely transmit the pad, why not simply transmit the plaintext by the same means and do away with the encryption?

Below, we'll see an historical example, where it actually did make sense to use a one‐time pad—in spite of its limitations. However, for modern high data‐rate systems, a one‐time pad cipher would generally be impractical.

Why is it that the one‐time pad can only be used once? Suppose we have two plaintext messages and , and we encrypted these as as and , that is, we have two messages encrypted with the same “one‐time″ pad . In the cryptanalysis business, this is known as a depth. From these two one‐time pad ciphertexts in depth, we can compute