Problem 3. For the substitution permutation network from Problem 2:

(a) Find a linear approximation, analogous to Figure 3 in Heys, which relates the plaintext bits P1, P2, P4, and P5 to a suitable subset of the inputs to the last round of S-boxes, i.e., a subset of the bits H1, . . . , H6.

(b) What is the total bias of the linear approximation you found in part (a)? What does this mean?

(c) Suppose you are given the following known plaintext/ciphertext pairs for this cipher, all encrypted with the same (unknown) key: Plaintext Ciphertext 100111 100100 000111 110010 001100 111001 011000 011101 001000 001101 011010 101001 Using the linear approximation from part (a), determine the first and third bits of the subkey K4. (Bonus question: why is this information insufficient to determine the second bit of the subkey K4?) NOTE: this problem has been specifically constructed so that a very small number of plaintexts and ciphertexts is sufficient to determine two subkey bits. Unlike the general method of Heys, a probabilistic analysis is not necessary in this problem the bits in question can be determined with certainty.

(a) Find a linear approximation, analogous to Figure 3 in Heys, which , P2, P4, and P5 to a suitable subset of the inputs to the last round of S-boxes, i.e., a subset of the bits relates the plaintext bits P 12 ,JR (a) Find a linear approximation, analogous to Figure 3 in Heys, which , P2, P4, and P5 to a suitable subset of the inputs to the last round of S-boxes, i.e., a subset of the bits relates the plaintext bits P 12 ,JR