1. (30+10 points) Combiner LFSR - Divide-and-conquer attack In this exercise, we will explore the divide-and-conquer attack on a combiner LFSR. Consider the combiner LFSR in Figure 1. (0) (0) (0) 20 21 22 ... +mod 28 Z 0 1 2 3 (1) (1) (1) 20 21 22 ... 0 1 2 3 4 5 6 7 Figure 1: A combiner LFSR. For addition, we take the 2 and 241) to be the most significant bits. So, for instance, 00000001 is 1, and 01000000 is 64. The output bytes are given as numbers from 0 to 255. (a) Give an upper bound on the security strength of this combiner LFSR by only considering an ex- 2 pt haustive key search. (b) Let the output stream of the combiner LFSR be given by Z = (36, 136). We guess that the initial 8 pt state for the 4-bit LFSR is 1111. Compute the first sixteen bits of the output stream for this LFSR (using this initial state). (C) Assume that the guess of 1111 for the 4-bit LFSR is correct. Give the first sixteen bits of the output 6 pt stream for the 8-bit LFSR. (d) Mount a linear attack on the 8-bit LFSR to obtain its current state (after 8 iterations). [You only 10 pt need the first 8 output bits. Since it is not decimated, you can use the method from Assignment 1 Exercise 3b.] (e) Explain why your guess 1111 of the initial state was not correct. 4 pt BONUS Perform the full divide-and-conquer attack on this combiner LFSR. [There is no need to do this by +10 pt hand, but please provide clear references and/or code.] 1. (30+10 points) Combiner LFSR - Divide-and-conquer attack In this exercise, we will explore the divide-and-conquer attack on a combiner LFSR. Consider the combiner LFSR in Figure 1. (0) (0) (0) 20 21 22 ... +mod 28 Z 0 1 2 3 (1) (1) (1) 20 21 22 ... 0 1 2 3 4 5 6 7 Figure 1: A combiner LFSR. For addition, we take the 2 and 241) to be the most significant bits. So, for instance, 00000001 is 1, and 01000000 is 64. The output bytes are given as numbers from 0 to 255. (a) Give an upper bound on the security strength of this combiner LFSR by only considering an ex- 2 pt haustive key search. (b) Let the output stream of the combiner LFSR be given by Z = (36, 136). We guess that the initial 8 pt state for the 4-bit LFSR is 1111. Compute the first sixteen bits of the output stream for this LFSR (using this initial state). (C) Assume that the guess of 1111 for the 4-bit LFSR is correct. Give the first sixteen bits of the output 6 pt stream for the 8-bit LFSR. (d) Mount a linear attack on the 8-bit LFSR to obtain its current state (after 8 iterations). [You only 10 pt need the first 8 output bits. Since it is not decimated, you can use the method from Assignment 1 Exercise 3b.] (e) Explain why your guess 1111 of the initial state was not correct. 4 pt BONUS Perform the full divide-and-conquer attack on this combiner LFSR. [There is no need to do this by +10 pt hand, but please provide clear references and/or code.]