Extra Credit 4

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


  1. (40 points) Consider double encryption, where c = Ek′(Ek(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 m0 and m1 and their corresponding ciphertexts c0 and c1.
    1. The cryptanalyst computes Ex(m0) 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 = Dx′(c0), 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?

UC Davis sigil
Matt Bishop
Office: 2209 Watershed Sciences
Phone: +1 (530) 752-8060
Email: mabishop@ucdavis.edu
ECS 153, Computer Security
Version of May 14, 2018 at 1:09AM

You can also obtain a PDF version of this.

Valid HTML 4.01 Transitional Built with BBEdit Built on a Macintosh