Total marks: 30

Due date: February 10 (Friday), 2:30 pm

Deadline extension (with no penalty): February 11 (Saturday), 6:00 pm

1. Multiple encryption (Slide 2.51, 6 marks)

Let E be a block cipher with key space K = }0, 1|64 , plaintext space M = }0, 1|64 , and ciphertext space C  =  }0, 1|64 .   The encryption scheme  Four-E  has key space K  =  }0, 1|256 .   A plaintext m e }0, 1|64  is encrypted under key k = (k1 , k2 , k3 , k4 ) (where k1 , k2 , k3 , k4  eR  }0, 1|64 ) as follows:

Enck(m) = Ek4 (Ek3 (Ek2 (Ek1 (m)))).

(a)  Give a formula for the decryption process.

(b)  Describe and analyze a known-plaintext attack on Four-E that has total running time  approx- imately  2128  E or E − 1  operations.  (You can ignore the time to sort or store things in a large table.)  Estimate the storage requirements of your attack.  Justify why the number of known plaintext-ciphertext pairs you have is sufficient to uniquely determine the secret key with high probability.

2. AES operations (Slide 2.69, 8 marks)

(a)  Compute f7 × aa in GF (28 ). Use the conventions on slide 2.59 for the representation of GF (28 )

elements. Show your work.

(b)  Consider the AES column a = 00000000. Compute MixColumn(a). Show your work.

(c)  Consider the AES column a = 01010101. Compute MixColumn(a). Show your work.

(d)  Consider the AES column a = 01234567. Compute MixColumn(a). Show your work.

You may use the following tables for multiplication in GF (28 ) by 02, multiplication in GF (28 ) by 03, and xor of hexadecimal digitsMultiplication in GF (28 ) by 02; for example, 6d × 02 = da. 0       1      2      3      4      5      6      7      8      9      a      b      c d

Multiplication in

1      2      3 4

06

36

66

56

c6

f6

a6

96

9d

ad

fd

cd

5d

6d

3d

0d

xor of hexadecimal digits; for example, a e c = 6.

e 0     1    2    3    4    5    6    7    8    9    a    b c d    e     f

b

a

9

8

f

e

d

c

3

2

1

0

7

6

5

4

3. Hash functions #1 (Slide 3.15, 4 marks) Let F : }0, 1|2n  → }0, 1|n  and G : }0, 1|2n  → }0, 1|n  be two hash functions.  Define the function H : }0, 1|2n  → }0, 1|n  by H(x) = G(F (x), F (x)).  (Here, the comma “,” denotes concatenation.) Prove that if F and G are collision resistant, then H is also collision resistant.

Note: As mentioned in lectures, such a statement is best proven using the contrapositive statement.

4. Hash functions #2 (Slide 3.21, 8 marks)

Suppose that f : }0, 1|512  → }0, 1|256  is a compression function that is preimage resistant.  Define H : }0, 1|1024 → }0, 1|256  as follows. Given x e }0, 1|1024 , write

x = xL lxR       where     xL , xR  e }0, 1|512 .

Then define

H(x) = f(xL e xR ).

(a)  Prove or disprove: H is preimage resistant.

(b)  Prove or disprove: H is second-preimage resistant.

(c)  Prove or disprove: H is collision resistant.

5. MACs (Slide 4.12, 4 marks)

Suppose that EMAC (as described on slide 4.12 for authenticating variable-length messages) is used with one key (so k = s). Show that this variant of EMAC is insecure.