EE418-Assignment 4 Solved

1.    [Com] Let n = pq be the product of two distinct large primes. Given an input x, define the hash of the input as h(x) = x2 (mod n).

(a)    Why is h preimage resistant? (Of course, there are some values, such as 1, 4, 9, 16, ... for which it is easy to find a preimage. But usually it is difficult.) (b) Why is h not collision resistant?

2.    [Com]

(a)    Given a hash function where the hash value is a 256-bits long binary string, how many attempts (queries) are required to find two messages m and m0 that are different but have the same hash value (i.e., collision), with the average success probability of 0.75?

(b)    Let n = pq where p and q are large distinct prime numbers. a is an integer that is relatively prime to φ(n) and b is chosen such that ab = 1 mod φ(n). Consider the following hash function. Given m1,m2 ∈ Zn, the hash function takes message m as input, which is a concatenation of m1 and m2, mathematically written as m = m1||m2. The hash is computed as

 

Is this hash function second preimage resistant? Explain why or why not.

(c)    Let n = pq where p and q are large distinct prime numbers. a is an integer that is relatively prime to φ(n) and b is chosen such that ab ≡ 1 mod φ(n). Consider the following iterated hash function, which takes a message m = m1||m2 as input, where mi ∈ Zn and || means concatenation. The hash is computed as

h1 = ha0 · mb1 mod n h2 = ha1 · mb2 mod n

where h0 is the initial value (known and fixed), and h(m) = h2 is the final hash value. It this hash function second preimage resistant? Explain why or why not.

3.    [Com]  In a family of four, what is the probability that no two people have birthdays in the same month? (Assume that all months have equal probabilities.)

4.    [Com] (Hash, Preimage Resistance, 5pts × 3 = 15pts) Suppose that h : X 7→ Y is an (|X| = N,|Y| = M)-hash function, let h−1(y) = {x : h(x) = y}

and let sy = |h−1(y)| for any y ∈ Y. Suppose that we try to solve Preimage for the function h, using Algorithm 4.1 in Handout 7, assuming that we only have oracle access for h. For a given y ∈ Y, suppose that X0 is chosen to be a random subset of X having cardinality q.

(a)    Prove that the success probability of Algorithm 4.1 in Handout 7, given y, is

 .

(b)    Prove that the average success probability of Algorithm 4.1 Handout 7 (over all y ∈ Y) is

 .

(c)    In the case q = 1, show that the success probability in part (b) is 1/M.

5.    [Com] (Hash, Collision Resistance, 5pts × 2 = 10pts) Suppose h1 : {0,1}2m 7→ {0,1}m is a collision resistant hash function. Define h2 : {0,1}4m 7→ {0,1}m as follows:

(a)    Write x ∈ {0,1}4m as x = x1||x2, where x1,x2 ∈ {0,1}2m.

(b)    Define h2(x) = h1(h1(x1)||h1(x2)).

Prove that h2 is collision resistant.

Hint: Prove by contradition that h2 is collision resistant: assume that there exists x1,x2 ∈ {0,1}4m, such that x1 6= x2, but h2(x1) = h2(x2). Also use the fact that h1 is collision resistant, i.e., there does not exist x1,x2 ∈ {0,1}2m such that x1 6= x2 but h1(x1) = h1(x2); in other words, h1(x1) = h1(x2) implies x1 = x2.

6.    [Com] (CBC-MAC, 10pts × 2 = 20pts) Consider the CBC-MAC as illustration in Fig. 1, where the initial vector (IV) is a block of zeros. The corresponding equations for CBC encryption are given as

                                                                                Ci = EK{Ci−1 ⊕ mi}, for i = 1,2,...,n.                                                               (1)

Recall that in the original CBC-MAC, Cn represents the generated MAC.

Now, “A” wants to modify the original CBC-MAC by using the last block of message mn as the IV, following the original CBC-MAC protocol up to step (n − 1), and then releasing Cn−1 as the MAC. The new equation of the iteration of the modified CBC-MAC is given as follows:

                                                                             Ci = EK{Ci−1 ⊕ mi}, for i = 1,2,...,n − 1.                                                            (2)

(a)    Draw a block diagram of the modified CBC-MAC.

(b)    If the same encryption algorithm and the same encryption key are used for both the original and modified CBC-MAC, show that the modified CBC-MAC does not give the same output as te original CBC-MAC for a message m = m1||m2||...||mn.

(Hint: Proof by induction.)

 

Figure 1: CBC-MAC

7.    [Pro] (CBC-MAC, 20 pts) Consider a CBC-MAC given in Figure 1 with block size t = 16 and IV = 1010000011111010. Assume message m is given as a binary string consists of n message blocks of size t (i.e., m = m1||m2||...mn) and the encryption in CBC-MAC given in Figure 3 is done as follows: • If i corresponding to ith encryption box Ei is an even number then encryption is done using Hill

Cipher with key  (Recall in Hill cipher encryption of a plaintext x is given by

EK(x) = xK).

• If i corresponding to ith encryption box Ei is an odd number then encryption is done using Vigen`ere Cipher with key Ki = 1001001111001001.

Further assume that all the operations in the CBC-MAC given in Figure 3 are done in mod2.

(a)   Implement the CBC-MAC algorithm explained in the text above using Python/MATLAB.

(b)    Use your Python/MATLAB implementation to find the CBC-MAC of the message, m = 1001100100111000110001010001111011001111101010100101101101011000011011100101 01111000000010001001