Information Security. Mark Stamp

      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

and we see that the key has disappeared from the problem. In this case, the ciphertext does yield some information about the underlying plaintext. Another way to see this is to consider an exhaustive key search. If the pad is only used once, then the attacker has no way to know whether the guessed key is correct or not. But if two messages are in depth, for the correct key, both putative plaintexts must make sense. This provides the attacker with a means to distinguish the correct key from incorrect guesses. The problem only gets worse (or better, from a cryptanalyst's perspective) the more times the key is reused.

      Let's consider an example of one‐time pad encryptions that are in depth. Using the same bit encoding as in Table 2.1, suppose we have

      and both are encrypted with the same key . Then

      and

      If Trudy the cryptanalyst knows that the messages are in depth, she immediately sees that the second and fourth letters of and are the same, since the corresponding ciphertext letters are identical. But far more devastating is the fact that Trudy can now guess a putative message and check her results using . Suppose that Trudy, who only knows and , suspects that . Then she can find