Review Questions
3.1 Why is it important to study the Feistel cipher? Get 3.1 exercise solution
3.2 What is the difference between a block cipher and a stream cipher? Get 3.2 exercise solution
3.3 Why is it not practical to use an arbitrary reversible substitution cipher of the kind shown in Table 3.1? Get 3.3 exercise solution
3.4 What is a product cipher? Get 3.4 exercise solution
3.5 What is the difference between diffusion and confusion? Get 3.5 exercise solution
3.6 Which parameters and design choices determine the actual algorithm of a Feistel cipher? Get 3.6 exercise solution
3.7 Explain the avalanche effect.
Get 3.7 exercise solution
Problems
3.1
a. 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. 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 * 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! 6 n
* 2n. Explain the discrepancy. Get 3.1 exercise solution
3.2
Consider a Feistel cipher composed of sixteen rounds with a block
length of 128 bits and a key length of 128 bits. Suppose that, for a
given k, the key scheduling algorithm determines values for the first
eight round keys, k1, k2,ck8, and then sets k9 = k8, k10 = k7, k11 =
k6,c, 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 3.2 exercise solution
3.3
Let p be a permutation of the integers 0, 1, 2, c, (2n - 1), such that
p(m) gives the permuted value of m, 0 … m 6 2n. Put another way, p 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. Get 3.3 exercise solution
3.4
Consider a block encryption algorithm that encrypts blocks of length n,
and let N = 2n. Say we have t plaintext–ciphertext pairs Pi, Ci = 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 Ci = 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–cipher text 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? b. What is the probability that E(K, #)
and E(K′, #) agree on another t′ plaintext– ciphertext pairs where 0 …
t′ … N - t? Get 3.4 exercise solution
3.5
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, m2) 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.) Get 3.5 exercise solution
3.6
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? 2. What would the decryption
look like?
(A ⊕ B) ⊕ C = A ⊕ (B ⊕ C)
A ⊕ A = 0
A ⊕ 0 = A
A ⊕ 1 = bitwise complement of A
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 Get 3.6 exercise solution
3.7 Show that DES decryption is, in fact, the inverse of DES encryption. Get 3.7 exercise solution
3.8
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: A7B = the concatenation of
the bit strings A and BT i(R7L) = the transformation defined by the ith
iteration of the encryption algorithm for 1 <= I <= 16 TDi(R7L) =
the transformation defined by the ith iteration of the encryption
algorithm for 1 <=I<= 16
T17(R7L) = L7R, where this transformation occurs after the sixteenth
iteration of the encryption algorithm a. Show that the composition
TD1(IP(IP-1(T17(T16(L157R15)))))
is equivalent to the transformation
that interchanges the 32-bit halves, L15 and R15. That is, show that
TD1(IP(IP-1(T17(T16(L157R15))))) = R157L15
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(L157R15)))) =
L157R15
Does it?
Note: The following problems refer to details of DES that are described
in Appendix S.
Get 3.8 exercise solution
3.9
Consider the substitution defined by row 1 of S-box S1 in Table S.2.
Show a block diagram similar to Figure 3.2 that corresponds to this
substitution. Get 3.9 exercise solution
3.10
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 3.10 exercise solution
3.11
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:
Hexadecimal notation: 0 1 2 3 4 5 6 7 8 9
A B C D E F
Binary notation: 0000 0001 0010 0011 0100 0101 0110
0111 1000 1001 1010 1011 1100 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 Table S.1. d.
Calculate A = E[R0] ⊕ K1. 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 3.11 exercise solution
3.12
Compare the initial permutation table (Table S.1a) with the permuted
choice one table (Table S.3b). Are the structures similar? If so,
describe the similarities. What conclusions can you draw from this
analysis? Get 3.12 exercise solution
3.13
When using the DES algorithm for decryption, the 16 keys (K1, K2, c,
K16) are used in reverse order. Therefore, the right-hand side of
Figure S.1 is not valid for decryption. Design a key-generation scheme
with the appropriate shift schedule (analogous to Table S.3d) for the
decryption process. Get 3.13 exercise solution
3.14
a. 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 ⊕ B)′ = A′⊕ B.
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? Get 3.14 exercise solution
3.15
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.
Note: The following problems refer to simplified DES, described in
Appendix G. Get 3.15 exercise solution
3.16
Refer to Figure G.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 3.16 exercise 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 3.17 exercise 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 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). Get 3.18 exercise solution
