Exercise Sheet

1. Let L be a 9 bit LFSR with connection polynomial c(x) = x⁸ + x⁴ + x + 1 and seed s = [1, 0, 1, 1, 1, 0, 0, 1, 0] (i.e. the last bit of s, 0, is the next keystream bit). Compute 10 bits of the keystream, the feedback bits and show the intermediate states of the register.

2. Consider a modified version of the Cipher block chaining mode, where the initialisation vector is not chosen at random, but chosen randomly once (like the key) and then increased by one for each encryption. Show that this modified version is not IND-CPA-secure. Note that the initialisaton vector is always part of the ciphertext.

3. Perform hashing, with the second round of the MD4 hash function adapted as follows:

(H₁, H₂, H₃, H₄) := (A, B, C, D)

for i := 0 to 3 do

t := A + G(B, C, D) + M_i

(A, B, C, D) := (D, t << i, B, C)

end

(A, B, C, D) := (H₁ + A, H₂ + B, H₃ + C, H₄ + D)

Assume that we compute a 16 bit hash, i.e., A, B, C, D are 4 bit words, G takes three 4 bit arguments and the message blocks are 16 bits partitoned into 4 bit chunks. Addition is modulo 2⁴. Initially let (A, B, C, D) = (0x2, 0x5, 0x9, 0xD).

Compute the 16 bit hash for the 32 bit message given as hexadecimal number 0xFAB1756E.

4. Compute a simplified PMAC as follows: Let n = 4 and use the field F₂[x]/(x⁴ + x + 1). Define the encryption function E by E(K, M ) = K  ⊕ M . Choose K to be 0110 and L to be 1010 and form the hash of the message 11000011. Show the calculations.