6.033 Handout 29

Sample Quiz 2 questions: 1994 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  
0                          1  
1                         25  
2                         24  
3                         10  
4                         15  
5                         25  
Total                    100    

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

Problem 5. (25 points) The network level of the Internet names hosts with 4-byte host addresses. These names are assigned regionally, with all hosts in one major region receiving host addresses for which the first byte is the same. A region is divided into sub-regions in which all host addresses have the same value for the second byte, and so on. This hierarchical naming scheme is used by the routing system to reduce the size of the tables it must maintain.

a. Explain briefly how hierarchical naming of host addresses might reduce the size of routing tables.

b. Ben Bitdiddle is thinking about designing a system for wireless attachment of portable computers to the Internet. He has decided that the basic architecture should consist of a number of fixed base stations, each of which will communicate by radio with those portable computers in its area. He plans to make each base station a sub-sub-region, using the third byte of the Internet address to identify it. Alyssa points out that this plan limits the number of portables that can simultaneously work with one base station. The base station uses up one of the host addresses for its sub-sub-region. How many portables can work with one base station?

c. Ben proposes not to permanently assign host addresses to portable computers. Instead, when a portable is switched on, it will ask some base station to dynamically assign a host address for it to use. When dynamic address assignment is used, what else has to happen in order for other computers to initiate communication with a portable?

(Problem 5 continues on the next page)

(Problem 5, continued)

d. Ben wants his design to work with the portable computer mounted on the handlebars of his bicycle. The base stations he will use were designed for cellular phones, so they have the ability at the physical transport level to transfer (or "handoff") a conversation from one base station to another as the signal strength changes. But in Ben's design a handoff means that the host address of the portable must change. Ben wants to be able to maintain connections through handoffs, so that he can transfer long files without disruption while cycling across town. His first idea is to modify the File Transfer Protocol to allow handoff. Whether or not he figures out how to do the modification, what is the main defect in this proposal?

e. Briefly suggest a way of accomplishing handoff entirely within the network layer.