2. (20 points) Insecurity of Feistel structure. In this exercise, we consider a 2-round Feistel structure as in Figure 2. PL PR F 1 Ki F A K2 CL CR Figure 2: Two-round Feistel structure. 3 pt Let FK : {0,1} + {0,1}l and FKz: {0, 1} + {0,1}l be functions that are indistinguishable from a random function. We will show that given any ciphertext CL||CR, we can obtain the original plaintext PL||PR without knowing the keys Ki and K2. For the setting, we assume we have a device where we can encrypt messages. (a) Give general formulas for C and CR in terms of FK, FK,, P and PR. [Note that they are not the same as in Assignment 2!] (b) We encrypt 0 ||0C on the device and obtain a||5. Express a and b using the formulas from part (a). (c) We encrypt (C FK (0%))||0' on the device and obtain c||d. Explain why we can compute C1 Fk (0). (d) Express c and d using the formulas from (a). (e) Using the result from (d), show how to obtain PR. (f) Find a final encryption to make, so that you can obtain PL. (Hint: You can now use PR.] 3 pt 3 pt 3 pt 3 pt 5 pt 2. (20 points) Insecurity of Feistel structure. In this exercise, we consider a 2-round Feistel structure as in Figure 2. PL PR F 1 Ki F A K2 CL CR Figure 2: Two-round Feistel structure. 3 pt Let FK : {0,1} + {0,1}l and FKz: {0, 1} + {0,1}l be functions that are indistinguishable from a random function. We will show that given any ciphertext CL||CR, we can obtain the original plaintext PL||PR without knowing the keys Ki and K2. For the setting, we assume we have a device where we can encrypt messages. (a) Give general formulas for C and CR in terms of FK, FK,, P and PR. [Note that they are not the same as in Assignment 2!] (b) We encrypt 0 ||0C on the device and obtain a||5. Express a and b using the formulas from part (a). (c) We encrypt (C FK (0%))||0' on the device and obtain c||d. Explain why we can compute C1 Fk (0). (d) Express c and d using the formulas from (a). (e) Using the result from (d), show how to obtain PR. (f) Find a final encryption to make, so that you can obtain PL. (Hint: You can now use PR.] 3 pt 3 pt 3 pt 3 pt 5 pt