Extra Credit 4

Due: May 25, 2018 at 11:59pm (Extended; due date is now May 30)
Points: 20

Questions

1. (40 points) Consider double encryption, where c = E_k′(E_k(m)) and the keys k and k′ are each n bits long. Assume that each encipherment takes one time unit. A cryptanalyst will use a known plaintext attack to determine the key from two messages m₀ and m₁ and their corresponding ciphertexts c₀ and c₁.
   1. The cryptanalyst computes E_x(m₀) for each possible key x and stores each in a table. How many bits of memory does the table require? How many time units does it take to compute the entry?
   2. The cryptanalyst computes y = D_x′(c₀), where D is the decipherment function corresponding to E, for each possible key x′, and then checks the table to see if y is in it. If so, (x, x′) is a candidate for the key pair. How should the table be organized to allow the cryptographer to find a match for y in time O(1)? How many time units will pass before a match must occur?
   3. How can the cryptographer confirm that (x, x′) is in fact the desired key pair?
   4. What are the maximum amounts of time and memory needed for the attack? What are the expected amounts of time and memory?

Matt Bishop Office: 2209 Watershed Sciences Phone: +1 (530) 752-8060 Email: [email protected]

ECS 153, Computer Security Version of May 14, 2018 at 1:09AM

You can also obtain a PDF version of this.