Mark Stamp - Information Security

Suppose that Trudy intercepts the following ciphertext, which she suspects was produced by a simple substitution cipher, where the key could be any permutation of the alphabet:

(2.2)

Since it's too much work for Trudy to try all possible keys, can she be more clever? Assuming the plaintext is English, Trudy can make use of expected English letter relative frequencies in Figure 2.2together with the frequency counts for the ciphertext, which are given in Figure 2.3.

Figure 2.2 English letter relative frequencies

From the ciphertext frequency counts in Figure 2.3, we see that “ F″ is the most common letter in the encrypted message and, according to Figure 2.2, “ E″ is the most common letter in the English language. Trudy therefore surmises that it's likely that “ F″ has been substituted for “ E.″ Continuing in this manner, Trudy can try likely substitutions until she recognizes words, at which point she can be confident in her guesses.

Figure 2.3 Frequency counts for ciphertext in 2.2

Initially, the easiest word to determine might be the first word, since Trudy doesn't know where inter‐word spaces belong in the text. Since the third plaintext letter appears to be “ e,″ and given the high frequency counts of the first two letter, Trudy might reasonably guess (correctly, as it turns out) that the first word of the plaintext is “ the.″ Making these substitutions into the remaining ciphertext, she will be able to guess more letters and the puzzle will begin to unravel. Trudy will likely make some missteps along the way, but with sensible use of the statistical information available, she will find the plaintext in considerably less time than 4450 millennia.

This attack on the simple substitution shows that a large keyspace is not sufficient to ensure security. It also shows that cipher designers must guard against clever attacks. How can we protect against attacks when new attacks are developed all the time? The answer is that we can't and, as a result, a cipher must be subjected to extensive analysis by skilled cryptographers before we can trust it—the more skilled cryptographers who have tried to break a cipher and failed, the more confidence we have in the cipher.

There are several reasonable definitions of a secure cipher. Ideally, we would like to have a rigorous mathematical proof that there is no feasible attack on a system, but such ciphers are few and far between, and provably secure ciphers are impractical for most uses.

Lacking a proof that a cipher is secure, we could require that the best‐known attack on the system is impractical, in the sense of being computationally infeasible. While this would seem to be the most crucial property, we'll use a slightly different definition. We say that a cryptosystem is secure if the best‐known attack requires as much work as an exhaustive key search. In other words, no shortcut attack is known.

Note that by our definition, a secure cipher with a small number of keys could be easier to break than an insecure one with a large number of keys. While this may seem counterintuitive, there is a method to the madness. The rationale for our definition is that a cipher can never offer more security than an exhaustive key search, so the key size could be considered its “advertised″ level of security. If a shortcut attack is known, the algorithm fails to provide its advertised level of security, as indicated by the key length. In short, a shortcut attack indicates that the cipher has a fundamental design flaw.

Note also that in practice, we must select a cipher that is secure (in the sense of our definition) and has a large enough key space so that an exhaustive key search is impractical. Both factors are necessary when choosing a cipher to protect sensitive data.

In this section we discuss another classic cipher that illustrates some important basic concepts. The double transposition presented here is a weaker form of the usual double transposition cipher. We use this form of the cipher since it provides a slightly simpler means of illustrating all of the points that we want to make.

To encrypt with a double transposition cipher, we first write the plaintext into an array of a given size and then permute the rows and columns according to specified permutations. For example, suppose we write the plaintext attackatdawninto a array

If we transpose (or permute) the rows according to and transpose the columns according to , we obtain

The ciphertext is read from the final array as

(2.3)

For this double transposition cipher, the key consists of the row and column permutations. Anyone who knows the key can simply put the ciphertext into the appropriate sized matrix and undo the permutations to recover the plaintext For example, to decrypt ( 2.3), the ciphertext is first put into a array. Then the columns are numbered as and rearranged to , and the rows are numbered and rearranged into ,

and we see that we have recovered the plaintext, attackatdawn.