[Page 90 (continued)]3.7. Key Terms, Review Questions, and Problems Key Terms avalanche effect block cipher confusion Data Encryption Standard (DES) differential cryptanalysis diffusion Feistel cipher irreversible mapping key linear cryptanalysis permutation product cipher reversible mapping round round function subkey substitution
[Page 91]Review Questions | 3.1 | Why is it important to study the Feistel cipher? | | 3.2 | What is the difference between a block cipher and a stream cipher? | | 3.3 | Why is it not practical to use an arbitrary reversible substitution cipher of the kind shown in Table 3.1? | | 3.4 | What is a product cipher? | | 3.5 | What is the difference between diffusion and confusion? | | 3.6 | Which parameters and design choices determine the actual algorithm of a Feistel cipher? | | 3.7 | What is the purpose of the S-boxes in DES? | | 3.8 | Explain the avalanche effect. | | 3.9 | What is the difference between differential and linear cryptanalysis? |
Problems | 3.1 | In Section 3.1, under the subsection on the motivation for the Feistel cipher structure, it was stated that, for a block of n bits, the number of different reversible mappings for the ideal block cipher is 2n!. Justify. In that same discussion, it was stated that for the ideal block cipher, which allows all possible reversible mappings, the size of the key is n x 2n bits. But, if there are 2n! possible mappings, it should take log2 2n! bits to discriminate among the different mappings, and so the key length should be log2 2n!. However, log2 2n! <n x 2n. Explain the discrepancy.
| | 3.2 | Consider a Feistel cipher composed of 16 rounds with block length 128 bits and key length 128 bits. Suppose that, for a given k, the key scheduling algorithm determines values for the first 8 round keys, k1, k2, ..., k8, and then sets k9 = k8, k10 = k7, k11 = k6, ..., k16 = k1 Suppose you have a ciphertext c. Explain how, with access to an encryption oracle, you can decrypt c and determine m using just a single oracle query. This shows that such a cipher is vulnerable to a chosen plaintext attack. (An encryption oracle can be thought of as a device that, when given a plaintext, returns the corresponding ciphertext. The internal details of the device are not known to you and you cannot break open the device. You can only gain information from the oracle by making queries to it and observing its responses.) | | 3.3 | Consider a block encryption algorithm that encrypts blocks of length n, and let N = 2n. Say we have t plaintext-ciphertext pairs Pi, Ct = E(K, Pi), where we assume that the key K selects one of the N! possible mappings. Imagine that we wish to find K by exhaustive search. We could generate key K' and test whether C = E(K', Pi) for 1  K' encrypts each Pi to its proper Ci then we have evidence that K = K'. However, it may be the case that the mappings E(K, ·) and E(K', ·) exactly agree on the t plaintext-ciphertext pairs Pi, Ci and agree on no other pairs. What is the probability that E(K, ·) and E(K', ·) are in fact distinct mappings? What is the probability that E(K, ·) and E(K', ·) agree on another t' plaintext-ciphertext pairs where 0 3.4 | Let p be a permutation of the integers 0, 1, 2, ... (2n - 1) such that p(m) gives the permuted value of m, 0 2p maps the set of n-bit integers into itself and no two integers map into the same integer. DES is such a permutation for 64-bit integers. We say that p has a fixed point at m if p(m) = m. That is, if p is an encryption mapping, then a fixed point corresponds to a message that encrypts to itself. We are interested in the probability that p has no fixed points. Show the somewhat unexpected result that over 60% of mappings will have at least one fixed point. |
| |
[Page 92] | | 3.5 | Consider the substitution defined by row 1 of S-box S1 in Table 3.3. Show a block diagram similar to Figure 3.1 that corresponds to this substitution. | | 3.6 | Compute the bits number 1, 16, 33, and 48 at the output of the first round of the DES decryption, assuming that the ciphertext block is composed of all ones and the external key is composed of all ones. | | 3.7 | Suppose the DES F function mapped every 32-bit input R, regardless of the value of the input K, to 32-bit string of ones, bitwise complement of R.
Hint: Use the following properties of the XOR operation: What function would DES then compute? What would the decryption look like? (A  A ( A A 0 = A 1 = bitwise complement of where A, B, C are n-bit strings of bits 0 is an n-bit string of zeros 1 is an n-bit string of one
| | 3.8 | This problem provides a numerical example of encryption using a one-round version of DES. We start with the same bit pattern for the key K and the plaintext, namely: in hexadecimal notation: | 0 1 2 3 4 5 6 7 8 9 A B C D E F | in binary notation: | 0000 0001 0010 0011 0100 0101 0110 0111 | | | 1000 1001 1010 1011 0100 1101 1110 1111 |
Derive K1, the first-round subkey. Derive L0, R0. Expand R0 to get E[R0], where E[·] is the expansion function of Figure 3.8. Calculate A = E[R0] Group the 48-bit result of (d) into sets of 6 bits and evaluate the corresponding S-box substitutions. Concatenate the results of (e) to get a 32-bit result, B. Apply the permutation to get P(B). Calculate R1 = P(B) Write down the ciphertext.
| | 3.9 | Show that DES decryption is, in fact, the inverse of DES encryption. | | 3.10 | The 32-bit swap after the sixteenth iteration of the DES algorithm is needed to make the encryption process invertible by simply running the ciphertext back through the algorithm with the key order reversed. This was demonstrated in Problem 3.7. However, it still may not be entirely clear why the 32-bit swap is needed. To demonstrate why, solve the following exercises. First, some notation: A||B | = the concatenation of the bit strings A and B | Ti(R||L) | = the transformation defined by the ith iteration of the encryption algorithm, for 1 16 | TDi(R||L) | = the transformation defined by the ith iteration of the decryption algorithm, for 1 16 | T17(R||L) | = L||R. This transformation occurs after the sixteenth iteration of the encryption algorithm. |
[Page 93]Show that the composition TD1(IP(IP-1(T17(T16(L15||R15))))) is equivalent to the transformation that interchanges the 32-bit halves, L15 and R15. That is, show that TD1(IP(IP-1(T17(T16(L15||R15))))) = R15||L15 Now suppose that we did away with the final 32-bit swap in the encryption algorithm. Then we would want the following equality to hold: TD1(IP(IP-1(T16(L15||R15))))) = R15||L15 Does it?
| | 3.11 | Compare the initial permutation table (Table 3.2a) with the permuted choice one table (Table 3.4b). Are the structures similar? If so, describe the similarities. What conclusions can you draw from this analysis? | | 3.12 | When using the DES algorithm for decryption, the 16 keys (K1, K2, ..., K16) are used in reverse order. Therefore, the right-hand side of Figure 3.5 is no longer valid. Design a key-generation scheme with the appropriate shift schedule (analogous to Table 3.4d) for the decryption process. | | 3.13 | Let X' be the bitwise complement of X. Prove that if the complement of the plaintext block is taken and the complement of an encryption key is taken, then the result of DES encryption with these values is the complement of the original ciphertext. That is, If Y = E(K, X) Then Y' = E(K', X') Hint: Begin by showing that for any two bit strings of equal length, A and B, (A A x It has been said that a brute-force attack on DES requires searching a key space of 256keys. Does the result of part (a) change that?
| | 3.14 | Show that in DES the first 24 bits of each subkey come from the same subset of 28 bits of the initial key and that the second 24 bits of each subkey come from a disjoint subset of 28 bits of the initial key. | | 3.15 | For any block cipher, the fact that it is a nonlinear function is crucial to its security. To see this, suppose that we have a linear block cipher EL that encrypts 128-bit blocks of plaintext into 128-bit blocks of ciphertext. Let EL(k, m) denote the encryption of a 128-bit message m under a key k (the actual bit length of k is irrelevant). Thus EL(k, [m1 k, m1) EL(m1, m2 Describe how, with 128 chosen ciphertexts, an adversary can decrypt any ciphertext without knowledge of the secret key k. (A "chosen ciphertext" means that an adversary has the ability to choose a ciphertext and then obtain its decryption. Here, you have 128 plaintext/ciphertext pairs to work with and you have the ability to chose the value of the ciphertexts.) Note: The following problems refer to simplified DES, described in Appendix C. | | 3.16 | Refer to Figure C.2, which depicts key generation for S-DES. How important is the initial P10 permutation function? How important are the two LS-1 shift functions?
| | 3.17 | The equations for the variables q and r for S-DES are defined in the section on S-DES analysis. Provide the equations for s and t. | |
[Page 94] | | 3.18 | Using S-DES, decrypt the string (10100010) using the key (0111111101) by hand. Show intermediate results after each function (IP, Fk, SW, Fk, IP-1). Then decode the first 4 bits of the plaintext string to a letter and the second 4 bits to another letter where we encode A through P in base 2 (i.e., A = 0000, B = 0001,..., P = 1111). Hint: As a midway check, after the application of SW, the string should be (00010011). |
Programming Problems | 3.19 | Create software that can encrypt and decrypt using a general substitution block cipher. | | 3.20 | Create software that can encrypt and decrypt using S-DES. Test data: Use plaintext, ciphertext, and key of Problem 3.15. |
|
