Problem 1 Linear Feedback Shift Register Key Streams (10 marks)

Stream ciphers such as the one-time pad require a secret key stream of random bits which is bitwise x-ored with the plaintext to produce a ciphertext. In this problem, you will cryptanalyze one possible approach for generating such a key stream.

Let m be a positive integer and c₀, c₁, . . . , c_m1 {0, 1} a sequence of m fixed bits. Let z₀, z₁, . . . , z_m1 be any sequence of m bits and define z_m, z_m+1, z_m+1, . . . via the linear recurrence z_n+m c_m1z_n+m1 + c_m2z_n+m2 + + c₁z_n+1 + c₀z_n (mod 2) , (1)

with the usual arithmetic modulo 2. The fixed bits c₀, c₁, . . . c_m1 are the coefficients of the linear recurrence (1) and the intial values z₀, z₁, . . . , z_m1 are its seed. If the seed and the coefficients are appropriately chosen, then (1) generates a sequence of 2^m pseudorandom bits¹ (z_i) i0 from a seed of length m. This type of construction is popular since it can be implemented very efficiently in hardware using a linear feedback shift register ; see pp. 36-37 of the Stinson-Paterson book.

(a) (2 marks) Let m = 4 and consider the recurrence z_n+4 z_n+3 + z_n (mod 2) with seed (z₀, z₁, z₂, z₃) = (1, 0, 1, 0). Write down the first 19 bits z₀, z₁, . . . , z₁₈ generated by this recurrence and seed.

(b) (4 marks) A user with knowledge of the coefficients and of any m consecutive bits z_i , z_i+1, . . . , z_i+m1 (such as the seed, corresponding to the case i = 0) can use (1) to generate the entire sequence of bits (z_n)ni starting at z_i . This user is then able to decrypt everything from that point in the plaintext onwards. Explain how an attacker who intercepts a sequence of any 2m consecutive bits z_i , z_i+1, . . . , z_i+2m1 can potentially obtain the (unknown) coefficients c₀, c₁, . . . , c_m1 and thus completely break the stream cipher. Your description need not be long, but it should be clear and concise.

(c) (4 marks) Suppose the sequence (1, 1, 1, 1, 0, 0, 1, 1) of 8 consecutive bits was generated using an unknown linear recurrence of the form (1) with m = 4. Use your attack of part (b) to find the coefficients c₀, c₁, c₂, c₃ of this recurrence. (Suggestion: check your answer, i.e. ensure that the coefficients you obtain define a recurrence that produces the second four bits from the first four.)

¹Since there are only 2^m 1 distinct non-zero bit patterns of length m, there must be repetition after at most 2 ^m 1 bits. So in practice, m must be large.