3.1 Why is it important to study the Feistel cipher? Get solution
3.2 What is the difference between a block cipher and a stream cipher? Get solution
3.3 Why is it not practical to use an arbitrary reversible substitution cipher of the kind shown in Table 3.1? Get solution
3.4 What is a product cipher? Get solution
3.5 What is the difference between diffusion and confusion? Get solution
3.6 Which parameters and design choices determine the actual algorithm of a Feistel cipher? Get solution
3.7 What is the purpose of the S-boxes in DES? Get solution
3.8 Explain the avalanche effect. Get solution
3.9 What is the difference between differential and linear cryptanalysis? Get solution
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.
a. 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 2 n bits. But, if there are 2 n! possible mappings, it
should take log2 2 n! bits to discriminate among the different mappings, and so the key length
should be log2 2 n!. However, log2 2n! <n x 2n. Explain the discrepancy.
b. 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. Get solution
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 keysk, 1, 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.) Get solution
3.3 Consider a block encryption algorithm that encrypts blocks of length n, and let N = 2
n . 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 ≠ i ≠ t. If 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.
a. 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
≠ t' ≠ N - t? Get solution
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 ≠ m <= 2n. Put another way, p maps the set of n-bit integers into itself and no two integers map into the sameinteger. DES is such a permutation for 64-bit integers. We say that p has a fixed point at m if p(m) = m. Thatis, if p is an encryption mapping, then a fixed point corresponds to a message that encrypts to itself. We areinterested 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. Get solution
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. Get solution
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. Get solution
3.7 Suppose the DES F function mapped every 32-bit input R, regardless of the value of the input K, to
a. 32-bit string of ones,
b. bitwise complement of R.
Hint: Use the following properties of the XOR operation:
1. What function would DES then compute?
What would the decryption look like?
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 Get solution
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
a. Derive K1, the first-round subkey.
b. Derive L0, R0.
c. Expand R0 to get E[R0], where E[·] is the expansion function of Figure 3.8.
d. Calculate A = E[R0] K1.
Group the 48-bit result of (d) into sets of 6 bits and evaluate the corresponding S-box
substitutions.
e. Group the 48-bit result of (d) into sets of 6 bits and evaluate the corresponding S-box
substitutions.
f. Concatenate the results of (e) to get a 32-bit result, B.
g. Apply the permutation to get P(B).
h. Calculate R1 = P(B) L0.
i. Write down the ciphertext. Get solution
3.9 Show that DES decryption is, in fact, the inverse of DES encryption. Get solution
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 ≠ I ≠16
TDi(R||L) = the transformation defined by the ith iteration of the decryption algorithm, for 1 ≠ I ≠16
T17(R||L) = L||R. This transformation occurs after the sixteenth iteration of the encryption
algorithm.
a. 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?
b.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? Get solution
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? Get solution
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. Get solution
3.13Let X' be the bitwise complement of X. Prove that if the complement of the plaintext block is takenand 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 lengthA, and B, (A B)' = A x B.
It has been said that a brute-force attack on DES requires searching a key space of 256 keys. Does the result of part (a) change that?
b. It has been said that a brute-force attack on DES requires searching a key space of 2 56 keys. Does the result of part (a) change that? Get solution
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. Get solution
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 m2]) = EL(k, m1) EL(k, m1) for all 128-bit patterns 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. Get solution
3.16 Refer to Figure C.2, which depicts key generation for S-DES.
a. How important is the initial P10 permutation function?
b. How important are the two LS-1 shift functions? Get solution
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. Get solution
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 thesecond 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).
Solution: OK
