Assignment 7, due Apr 2

Always, on every assignment, please write your name legibly as it appears on your University ID and on the class list! All assignments will be due at the start of class on the day indicated (usually a Friday), and unless there is what insurance companies call "an act of God" - something outside your control; the only exceptions to this rule will be by advance arrangement.

1. Background: Look at the capability format used in Tannenbaum's Amoeba system.

   a) Which fields need to be widened to something like 128 or 400 bits each for the resulting capability to be universally secure? (For this problem, what matters is that the fields are definitely narrower than this.) (1 point)

   b) For each field you identified above that needs to be wide, identify and clearly document an attack that a malicious programmer could perform if the field was not sufficiently widened. (1 point)

2. Background: The statement that 402 bits is enough is very conservative. 402 bits are enough to address every bit in the universe, and this means that a lookup table with a 400 bit address would have only one bit per entry, which is to say, the table is of no use for inverting a trapdoor function.

   The estimated mass of the visible universe is from 10⁵⁰ to 10⁶⁰ kilograms, depending on how you estimate it. The mass of the sun is about 2×10³⁰ kilograms. The nearest star is over one light year away from the solar system.

   a) How big is enough, assuming that each entry in the lookup table is n bits and there are 2ⁿ entries in the table? Assume you have 2^{402 bits to work with. (1 point)}

   b) Access to an arbitrary bit somewhere in the universe is slow because of the finite speed of light. Suppose we wanted our trapdoor function to be uninvertable in times shorter than one year. How big does the key need to be? (1 point)

3. Background: With Diffie-Hellman key exchange, both participants contribute to the key that will be used, and neither participant controls the outcome of the computation. As a result, while the end result is that both participants end up sharing a secret key, neither knows, at the outset what key they will share. In effect, they end up sharing a random number that neither could anticipate to begin with.
4. A question: Alice knows the secret X and wants to communicate this to Bob. How do they use the Diffie-Hellman algorithm so that, in the end, X is known to both Alice and Bob, but could not be learned by Carol, who eavesdrops on all communication between Alice and Bob? (1 point)