Information Security. Mark Stamp

returns. This type of “lunchtime attack″ takes many forms.

      Potentially more advantageous for the attacker is an adaptively chosen plaintext attack. In this scenario, Trudy chooses the plaintext, views the resulting ciphertext, and chooses the next plaintext based on the observed ciphertext. In some cases, this can make Trudyś job significantly easier.

      Related key attacks are also relevant in some applications. The idea here is to look for a weakness in the system when the keys are related in some special way.

      There are other types of attacks that cryptographers occasionally worry about—mostly when they feel the need to publish another academic paper. In any case, a cipher can only be considered secure if no potentially useful shortcut attack is known.

      Finally, there is one particular attack scenario that applies to public key cryptography, but not the symmetric key case. Suppose Trudy intercepts a ciphertext that was encrypted with Aliceś public key. If Trudy suspects that the plaintext message was either “yes″ or “no,″ then she can encrypt both of these putative plaintexts with Aliceś public key. If either matches the ciphertext, then the message has been broken. This is known as a forward search. Although a forward search attack is not applicable to symmetric ciphers, weĺl see that this approach can be used to attack hash functions in some applications.

      We've previously seen that the size of the keyspace must be large enough to prevent an attacker from trying all possible keys. The forward search attack implies that in public key crypto, we must also ensure that the size of the plaintext message space is large enough so that the attacker cannot simply encrypt all possible plaintext messages. As weĺl see in Chapter 4, this is easy to achieve in practice.

2.8 Summary

In this chapter we covered several classic cryptosystems, including the simple substitution, the double transposition, codebooks, and the one‐time pad. Each of these illustrates some important points that weĺl return to again in later chapters. We also discussed some elementary aspects of cryptography and cryptanalysis.

      In the next chapter weĺl turn our attention to modern symmetric key ciphers. Subsequent chapters cover public key cryptography, and hash functions. Cryptography will appear again in later parts of the book. In particular, crypto is a crucial ingredient in security protocols. Contrary to some author's misguided efforts, the fact is that thereś no avoiding cryptography in information security.

2.9 Problems

      1 In the field of information security, Kerckhoff's principle is like motherhood and apple pie, all rolled up into one.Define Kerckhoff's principle in the context of cryptography.Give a real‐world example where Kerckhoff's principle has been violated. Did this cause any security problems?Kerckhoff's principle is sometimes applied more broadly than its strict cryptographic definition. Give a definition of Kerckhoff's principle that could apply more generally.

      2 Edgar Allan Poeś 1843 short story, “The Gold Bug,″ features a cryptanalytic attack.What type of cipher is broken and how?What happens as a result of this cryptanalytic success?

      3 Given that the Caesarś cipher was used, find the plaintext that corresponds to the ciphertext

      4 Find the plaintext and the key, given the ciphertextHint: The message was encrypted with a simple substitution, where the key is a shift of the alphabet.

      5 Suppose that we have a computer that can test keys each second.What is the expected time (in years) to find a key by exhaustive search if the keyspace is of size ?What is the expected time (in years) to find a key by exhaustive search if the keyspace is of size ?What is the expected time (in years) to find a key by exhaustive search if the keyspace is of size ?

      6 The weak ciphers used during the election of 1876 employed a fixed permutation of the words for a given length sentence. To see that this is weak, find the permutation of that was used to produce the scrambled sentences below, where “San Francisco″ is treated as a single word:first try try if you and don't again at succeedonly you you you as believe old are are aswinter was in the I summer ever San Francisco coldest spentNote that the same permutation was used for all three sentences, i.e., the three sentences are in depth.

      7 This problem deals with the concepts of confusion and diffusion.Define “confusion″ and “diffusion″ as used in cryptography.Which classic cipher discussed in this chapter employs only confusion?Which classic cipher discussed in this chapter employs only diffusion?Which cipher discussed in this chapter employs both confusion and diffusion?

      8 Recover the plaintext and key for the simple substitution example that appears in 2.2 on page .

      9 Determine the plaintext and key for the ciphertext that appears in the quote at the beginning of this chapter. Hint: The message was encrypted with a simple substitution cipher and the plaintext contains no spaces or punctuation.

      10 Decrypt the following message, which was encrypted using a simple substitution cipher:

      11 Write a program to help an analyst decrypt a simple substitution cipher. Your program should accept the ciphertext as input, compute letter frequency counts, and display these for the analyst. Your program should then allow the analyst to guess a key and display the results of the putative decryption using the specified putative key. Of course, you may add other features to your program that you consider useful. Use your program to help solve Problem 10, and comment on the usefulness of your program, as compared to working only with pencil and paper.

      12 Extend the program described in Problem 11 so that it includes the following features:Make an initial decryption of the message. The recommended way to proceed is to use monograph (i.e., individual letter) frequencies to make an initial guess for the key. Call this the “best key.″Use digraph frequencies to compute a score for any putative key.Generate new putative keys by swapping each pair of letters in the best key—if the score from ii) improves for a given swap, update the best key; if not, leave the best key unchanged.Iterate the process in iii) until the score does not improve for an entire pass through the key (i.e., all pairs have been swapped). The best key is your putative solution.Some errors in the key will likely remain, so your program must also include all of the functionality of the program in Problem 11. Use your program to solve Problem 10 and give the fraction of the key that is correctly recovered automatically, and the fraction of plaintext letters that are determined correctly.

      13 Jakobsenś algorithm [59] is an extremely efficient and effective simple substitution solver. Implement Jakobsenś algorithm and test your program on 10 distinct simple substitution ciphertext messages of each of the lengths , that is, 10 messages of length , 10 messages of length , and so on. On the same axes, graph the average fraction of the key that is correctly recovered, and the average fraction of plaintext letters that are correctly determined for each of these lengths.

      14 Decrypt the following ciphertext:This message was encrypted with a double transposition (of the type discussed in this chapter) using a matrix of 7 rows and 10 columns. Hint: The first word is “ there .″

      15 Outline an automated attack on a double transposition cipher (of the type discussed in the text), assuming that the size of the matrix is known.

      16 A double transposition cipher can be made much stronger by using the following approach. First, the plaintext is put into an array, as described in the text. Next, permute the columns, and then write out the intermediate ciphertext column by column. That is, column 1 gives the first ciphertext letters, column 2 gives the next , and so on. Then repeat the process, that is, put the intermediate ciphertext into an array, permute the columns, and write out the ciphertext column by column. Use this approach, with a array, and permutations and to encrypt the plaintext attackatdawn .

      17 Using the letter encodings in Table 2.1, the two ciphertext messageswere encrypted with the same one‐time pad. Find all dictionary words that are possible plaintext pairs and in each