Last Year's Quiz 2
---------------------------------------------------------------------------------------
This quiz contains five problems whose relative weights are indicated below. Please
place each answer on the page with the question and hand in this booklet at the end of
the examination.
Put your name on this cover sheet AND at the bottom of each page of this booklet. The
booklet may be separated for grading so that each problem can be evaluated by one
grader. Be sure that you don't put part of the answer to a problem on the back of a
sheet for another problem!
Beware: some parts of some problems are much harder than others. Read them all
through first and attack them in the order that allows you to make the most progress.
Write down any assumptions and show your work, or you risk losing partial credit. Be
neat. If we can't figure out your answer we can't give you credit. For problems that
require a numerical answer, be sure to indicate the units of your answer.
---------------------------------------------------------------------------------------
Problem 0. (1 point). Circle your recitation instance and write your name:
1. 10:00---Tennenhouse/McDonald
2. 11:00---Tennenhouse/DeHon 5. 11:00---Corbató/McDonald 7. 11:00---Waldspurger/Manning
6. 12:00---Waldspurger/DeHon
3. 1:00---Kaashoek/Manning 8. 1:00---Corbató/Joseph
4. 2:00---Kaashoek/Joseph
For Official Use Only
----------------------------
Problem Your Score Maximum
Score
Problem 1. (25 points) Lucifer is determined to figure out Alice's password by a brute-force attack. From watching her log in he knows that her password is eight characters long and all lower-case letters. He sets out to try all possible combinations of eight lower-case letters.
a. Assuming he has to try about half the possibilities before he runs across the right one, one trial can be done in one machine cycle, and he has a 60 MHz computer available, about how long will the project take?
b. How long will it take if Alice chooses an eight-character password that includes upper- and lower-case letters, numbers, and special characters? There are 78 characters available for her to choose from.
c. Suppose processors continue to get faster, improving by a factor of three every two years. How long will it be until Alice's new password can be cracked as easily as her old one?
Problem 2. (24 points) Louis Reasoner is fascinated with the discovery that some encryption algorithms are commutative.
For this problem we use the usual notation: A message M that is encrypted with key k is written {M}k. A commutative scheme has the interesting property that for every message and every pair of keys k1 and k2, {{M}k1}k2 = {{M}k2}k1. That is, you get the same result no matter which order two encryptions with different keys are done.
Louis has proposed that Alice, in San Francisco, and Bob, in Boston, use the following scheme for secure delivery of messages between their computers, which are connected via the Internet:
Alice chooses a never-before-used (nonce) encryption key, Ka, encrypts her message M, and sends the result, {M}Ka, to Bob. Bob chooses another nonce encryption key, Kb, encrypts the already-encrypted message to produce {{M}Ka}Kb and sends the doubly-encrypted result back to Alice. By commutativity, this message is identical to {{M}Kb}Ka, which is a message that Alice can decrypt with her nonce Ka. She does so, revealing {M}Kb. This result she sends back to Bob, who can now decrypt it with his nonce Kb to reveal M.
The appealing thing about this scheme is that Alice and Bob did not have to agree on a secret key in advance. Louis calls this the "No-Prior-Agreement" protocol.
a. Is it possible for a passive intruder (that is, one who just listens to the encrypted messages) to discover M? If so, describe how. If not, explain why not.
b. Is it possible for an active intruder (that is, one who can also insert, delete, or replay messages) to discover M? If so, describe how. If not, explain why not.
Problem 3. (10 points) One way of speeding up a name resolution system is to implement a cache that remembers recently looked-up {name, object} pairs. Synonyms are multiple names for the same object. What problems do synonyms pose for cache designers?
Problem 4. (15 points) Alyssa is trying to organize her notes on virtual memory systems, and it occurred to her that virtual memory systems can usefully be analyzed as naming systems. She has gone through her 6.033 notes and made a numbered list of some technical terms from the lectures on naming systems; that list is on the right, below. She then listed some mechanisms found in virtual memory systems on the left. But she isn't sure which naming concept goes with which mechanism. Help Alyssa out by placing in each blank on the left the number of the term on the right that best applies to this mechanism. Hint: no number needs to be used twice.
1. Search path
____ a. page map
2. Naming network
____ b. virtual address
3. Closure
____ c. physical address
4. Object
____ d. a TLB entry
5. Name
____ e. the processor register
that points to the 6. Context
page map
7. None of the above