5.13: Exercises

Last updated
Save as PDF

Page ID: 58761

Jerome H. Saltzer & M. Frans Kaashoek
Massachusetts Institute of Technology via MIT OpenCourseWare

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$

Exercise $\PageIndex{1}$

1983-3-5b

Louis Reasoner has been using a simple RPC protocol that works as follows$^*$:

client ⇒ service: {nonce, procedure, arguments} service ⇒ client: {nonce, response}

The client sets a timer, and if it does not receive a response before the timer expires, it restarts the protocol from the beginning, repeating this sequence as many times as necessary until a response returns. The service maintains a table of nonces and responses, and when it receives a request containing a duplicate nonce it repeats the response, rather than repeating execution of the procedure. The client similarly maintains a list of nonces for which no response has yet been received, and it discards any responses for nonces not in that list, assuming that they are duplicates. One possible response is "unknown procedure", meaning that the service received a request it didn't know how to handle. The link layer checksums all frames and discards any that are damaged in transmission. All messages fit in one frame.

Louis wants to make this protocol secure against eavesdroppers. He has discovered that the client and the service already share a key, K_cs , for a shared-secret-key cryptographic system. So the first thing he tries is to encrypt the requests and responses of the simple RPC protocol:

client ⇒ service: ENCRYPT ({nonce, procedure, arguments}, K_cs) service ⇒ client: ENCRYPT ({nonce, response}, K_cs)

This seems to work, but Louis has heard that if you use the same key to repeatedly transform predictable fields such as procedure names, someone may eventually discover the key by cryptanalysis. So he wants to use a different key for each RPC call. To minimize the coding effort, he changes the protocol to work as follows:

client ⇒ service: ENCRYPT ({K_tn}, K_cs) client ⇒ service: ENCRYPT ({nonce, procedure, arguments}, K_tn) service ⇒ client: ENCRYPT ({nonce, response}, K_tn)

in which K_tn is a one-time key chosen by the client to be used only for the n'th RPC call. When the service receives a key, it decrypts it and uses it until the service gets another key message. Louis figures that since K_cs is now being used only to encrypt temporary keys, which look like random numbers, it should be safer from cryptanalysis.

At first, this protocol, too, seems to work. Then Louis notices that the client is receiving the response “unknown procedure” much more often than it used to. Explain why, using a timing diagram to demonstrate an example of the failure, and offer a suggestion to fix the problem.

$^*$ Throughout the exercises, the notation {a, b, c} denotes a message constructed of the named items, marshaled in some unspecified way that is unimportant for the purposes of the problem so long as the recipient knows how to unmarshal the individual arguments.

Exercise $\PageIndex{2}$

1994–2–1a...c

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, of which there are 26. He sets out to try all possible combinations of eight lower-case letters.

a) Assuming that 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 600 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 16 special characters, creating a total of 78 possible characters?

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?

Exercise $\PageIndex{3}$

1983–2–4b

Tracy Swallow has a bright idea for avoiding the need to store passwords securely. She suggests transforming the user's name with a key-driven cryptographic transformation using a systemwide "password key" and giving the result back to the user to present as a password. A user who wishes to log in simply presents his or her name and this password; the system can authenticate the user by again transforming the user's name with the password key to see if the result is the same as the presented password. Thus no central file of passwords is needed. What is wrong with Tracy’s idea?

Exercise $\PageIndex{4}$

1994–2–2a,b

Louis Reasoner is fascinated with the discovery that some cryptographic transformations are commutative. A commutative transformation has the interesting property that for every message and every pair of keys k₁ and k₂ ,

TRANSFORM (TRANSFORM (M, k₁), k₂) = TRANSFORM (TRANSFORM (M, k₂), k₁)

That is, you get the same result no matter in which order you do two transformations with different keys.

Louis did some further research, identified a high-quality commutative transformation, and used it to devise a commutative implementation of two confidentiality primitives he calls ENCRYPT_C and DECRYPT_C . He has proposed that Alice, in San Francisco, and Bob, in Boston, use the following scheme for secure private delivery of messages between their computers, which are connected via the Internet:

Alice chooses a random key, k_a, encrypts her message M with that key, and sends the result, ENCRYPT_C (M, k_a), to Bob.
Bob chooses another random key,k_b, encrypts the already-encrypted message to produce ENCRYPT_C (ENCRYPT_C (M, k_a), k_b) , and sends the doubly-encrypted result back to Alice.
By commutativity, this message is identical to ENCRYPT_C (ENCRYPT_C (M, k_b), k_a) , which is a message that Alice can decrypt with her key k_a. She does so, revealing ENCRYPT_C (M, k_b) .
She sends this result back to Bob, who can now decrypt it with his key k_b 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.

Exercise $\PageIndex{5}$

1995–2–3a...d

Secure Inc. is developing a remote file system, Secure RFS (SRFS), which automatically encrypts files to guarantee better privacy of information. When a request to store a file arrives, SRFS encrypts the file using the client's key. On arrival of a request to read a file, SRFS looks up the client key, decrypts the file, and sends the file back to the client. SRFS keeps for each client a separate key.

a) The designers of Secure Inc. are wondering how long it would take to crack a file that is encrypted using RSA with a 512-bit key. To crack an RSA-encrypted file, one has to factor the key. The designers found a 1993 paper that reports that factoring a 100 decimal digit number takes about 1 month using idle cycles from 300 3 MIPS workstations. It is estimated that factoring an additional 3 decimal digits roughly doubles the computation time needed. How many 3-MIPS computers would be needed to factor a 155 decimal digit number (which corresponds to about 512 bits) in one month?

b) If processors are doubling computation performance per year, how many workstations would it take to factor a 512-bit key in one month in the year 2001?

c) Assume that the cryptographic transformations can be done at 250 kilobytes per second. How much would the throughput be reduced for reading files stored by SRFS, if the current maximum throughput without cryptographic transformations is 800 kilobytes per second? (Assume that the cryptographic transformations cannot be pipelined with sending and receiving.)

d) Secure Inc. is also considering adding automatic compression of files to SRFS. Compression reduces redundancy of information in a file so that the file takes less disk space. Should they first compress files, then encrypt them, or should they first encrypt files and then compress them? Explain.

Exercise $\PageIndex{6}$

2008-3-12-13

Alice wants to communicate with Bob over an insecure network. She learned about one-time pads in Section 5.9, and decides to use a one-time pad to secure her communications. Since Alice wants to send a $k$-bit message to Bob in the future, she generates a random $k$-bit key r and hands it to Bob in person. When Alice comes to send Bob her message, she XOR's the message m with the key r to produce a ciphertext c , and sends this on the network. Bob XOR 's c with r to retrieve m .

a) Assume that Alice's message m is a concatenation of a header followed by some data. Consider an eavesdropper Eve who snoops on Alice’s conversation. If Eve can correctly guess the value of the header in Alice's message, which of the following are correct?

A. Eve's ability to decrypt the data bits in m is not improved by her knowledge of the header bits.

B. The data bits in Alice's message are confidential.

C. The data bits in Alice's message are securely authenticated.

Alice rapidly grows tired of the effort in exchanging one-time pads with Bob, and has an idea to simplify the key distribution process. Alice’s idea works as follows:

To send a $k$-bit message m₁ to Bob, Alice picks a $k$-bit random number r₁, computes ciphertext c₁ = m₁ ⊕ r₁, and sends c₁to Bob. Bob then picks his own $k$-bit random number r₂, computes c₂ = c₁ ⊕ r₂, and sends c₂ to Alice. Alice finally computes c₃ = c₂ ⊕ r₁ and sends c₃to Bob.

b) Which of the following statements are correct of Alice's new scheme?

A. Bob can correctly decrypt Alice's message m₁, without receiving r₁ ahead of time, assuming all messages between Alice and Bob are correctly delivered.

B. An active attacker Lucifer (who can intercept, drop, and replay messages) can decrypt the message.

C. A passive eavesdropper Eve can decrypt the message.

Exercise $\PageIndex{7}$

1995–2–4a

Bank of America is struggling to convince itself of the authenticity of a message it just received, and has asked your help in what to do next. So far, they know the following two facts to be true:

Louis says (Ben says (Transfer $1,000,000 to Alyssa))
Jim speaks for Ben

Ben's account has enough money for such a transaction, so if they can convince themselves that Ben really authorized the transaction, they will do the transfer. Which of the following things should they attempt to establish the truth of, and why?

A. Louis speaks for Jim

B. Ben speaks for Louis

C. Ben says (Jim speaks for Louis)

Exercise $\PageIndex{8}$

1984–2–4

Ben Bitdiddle has hit on a bright idea for fixing the problem that capabilities are hard to revoke. His plan is to invent something called timed capabilities. One of the fields of a timed capability is its expiration time, which is the time of creation plus $E$. A timed capability can be used like any other capability until the system clock reaches the expiration time; after that time, it becomes worthless. Analyze this proposal with respect to:

a) Performance.

b) Propogation.

c) Revocation.

d) Auditing.

e) Ease of use.

Exercise $\PageIndex{9}$

1984–2–3a,b

Two banks are developing an inter-bank funds transfer system. They are connected by a telephone line which runs in a duct along Main Street, and Alyssa P. Hacker is concerned that there might be foul play. The banks' expert, Ben Bitdiddle, says that the banks will use a shared-secret key K1 to encrypt their communications and a second shared-secret key K2 to authenticate their communications, using the following protocol:

Bank 1 ⇒ Bank 2{{“transfer from our Account Y”}_K2}^K1 Bank 1 ⇒ Bank 2{{“to your Account X”}_K2}^K1 Bank 1 ⇒ Bank 2{{“Amount Z”}_K2}^K1 Bank 2 ⇒ Bank 1{{“OK”}_K2}^K1

Alyssa immediately realizes that without knowing either K1 or K2 an intruder could subvert the banks.

a) With an Apple II in the manhole in middle of Main Street, describe how Alyssa could

Increase or decrease the amount of a transfer.
Cause a transfer to occur more than once.
Cause a transfer not to occur at all without arousing suspicion at the requesting bank.

b) Design a new protocol that eliminates these problems and uses only two messages.

Exercise $\PageIndex{10}$

2002–0–1,2

To attract attention to their Web site, OutofMoney.com has added a feature that broadcasts a stream of messages containing free stock market quotations. They intend the information to be public, so there is no need for confidentiality, but they are concerned about their reputation, so they want the stream of data to be authenticated.

Their current implementation signs every message with the company's private key, and clients authenticate the data by verifying it with the company's widely publicized public key. This technique works, but is proving problematic because the public-key algorithm uses too much computation time and the typical client, running a four-year-old pentium processor, can't keep up with the stream of messages on days when the stock market is crashing.

From reading this chapter, they learned that authentication using a shared-secretkey MAC is much faster. They have hired Ben Bitdiddle and Louis Reasoner as a consulting team to put this idea into practice. (Unfortunately, they didn't do any of the problem sets, so they don't know about the reputations of these two characters.) Louis's first proposal is as follows: any client who wishes to use the authenticated service starts by contacting the service and requesting a start message. The service signs this start message with the company's public key. The start message contains the shared-secret key that is currently being used to authenticate the stream of messages containing the stock market quotations.

a) Ben's intuition is that this can't possibly work, but he isn't sure why. Give Ben some help by explaining why.

Undaunted, Louis has been reading about delayed authentication and decides it is the ideal way to tackle this problem. The idea is the following: since the service is sending a stream of messages, for each message use a different shared-secret key to create its authentication tag, and then publicly disclose that shared-secret key after all clients have received that message.

In Louis's design, each message P_i is constructed as follows:

raw_message_i ← {i, D_i , K_i_-2} authtag_i ← SIGN (raw_message_i , K_i ) P_i ← {raw_message_i , authtag_i }

Thus P_icontains

its own sequence number, i
some data, D_i
the key K_i_-2 , which can be used to verify the data in message P_i_-2
an authentication tag created by signing the rest of the message with K_i

The key that authenticates this message will appear in message P_i₊₂ . Louis argues that even though the key K_i is sent in plaintext, if the client receives D_ibefore the service sends K_i, by the time the attacker knows K_i, it is too late for the attacker to modify D_i. As with Louis's previous system, a client begins by requesting a start message. This time, the start message contains the same data as the next message in the broadcast stream, but it is signed with the company's private key.

b) Again, Ben is (rightly) suspicious of this system, but he can't figure out what is wrong with it. Help him out by explaining the flaw and how to fix it.

Exercise $\PageIndex{11}$

2002–2–04

This chapter discusses both capabilities and access control lists as mechanisms for authorization. Which of the following statements are true?

A. A capability system associates a list of object references with each principal, indicating which objects the principal is allowed to use.

B. An access control list system associates a list of principals with each object, indicating which principals are allowed to use the object.

C. Revocation of a particular access permission of a principal is more difficult in an access control list system than in a capability system.

D. Protection in the UNIX file system is based on capabilities only.

Exercise $\PageIndex{12}$

2003–3–5

Alice decided to try out a new RFID Student Tracking System, so she created an access control list that allows a few close friends to track her. One of those friends, Bob, wants to ask Alice to join his design project team, so this morning he requested that the tracking system give him a callback if Alice walks by the Administration building. Alice, working in a nearby laboratory, belatedly realizes that Bob is probably going to pop that question, so she logs in to the tracking system and removes Bob from her access control list. She then logs out and leaves for lunch. As she walks by the Administration building, Bob comes running out of the library to greet her, saying that he just received a callback from the tracking system.

The designer of the tracking system made a security blunder. Which of the following is the most likely explanation?

A. The tracking system didn’t properly erase residues.

B. In her rush to leave for lunch, Alice removed Lucy, rather than Bob, from her ACL.

C. The tracking system has a time-of-check to time-of-use bug.

D. The system used a version of SSL that is subject to cipher substitution attacks.

E. The system did not require a face-to-face rendezvous between users and system administrator.

Exercise $\PageIndex{13}$

2007-3-3-4

Ben decides to start an Internet Service Provider. He buys an address space that contains 2²⁴ addresses (out of the total of 2³² in the Internet) that have never been used before. A few days after he buys this address space, someone launches a new worm similar in design to the Slammer worm described in Section 5.12.4.3. The new worm targets a buffer overflow in the FOO server, which listens on UDP port 5044. Ben monitors all traffic sent to his part of the Internet address space on port 5044 and plots the number of worm probes versus time below:

An S-shaped graph of the number of probes per second vs time. At time=0, the graph begins at 100 probes/second. Over time, it slowly increases at first, then rises sharply, then increases at a slower rate, approaching the horizontal asymptote of 10,000 probes/second.

Figure $\PageIndex{1}$: Graph of the frequency of worm probes in Ben's address space vs. time.

Assume the worm spreads by probing IP addresses chosen at random, and that its pseudorandom number generator is bug-free and generates a complete permutation of the integers before revisiting any integer. Ben learns from a security analyst that each infected machine sends 100 probes/second.

a) Give an estimate of the total number of machines that run the FOO server

A. 100 machines
B. 7.2 $\times$ 10¹⁸ machines
C. 25,600 machines
D. 8,000 machines

b) Ben thinks that the worm used a hit list of vulnerable addresses (i.e., addresses of FOO servers). Do you agree? If you do, what is the best estimate for the number of machines contained in the hit list?

A. no hit list
B. 100 machines
C. 256 machines
D. 25600 machines
E. 80 machines

Exercise $\PageIndex{14}$

2008-3-6-7

Ben Bitdiddle, the new head of Cyber Security for the Department of Homeland Security, studied the war story about the Slammer worm in Section 5.12.4.3. He wants to build a system that will detect and stop future worm attacks before they can reach 50% of the vulnerable hosts. Ben makes the following assumptions about the worms to be defended against:

Each worm instance sends 512 (2⁹) probes per second.
The worm's software probes all IP addresses at random.
Of the 2³² possible addresses on the Internet, there are 32,768 (2¹⁵) that are attached to active hosts that are vulnerable to the worm.
The worm begins by infecting a single vulnerable host.

a) Given the assumptions above, roughly how many seconds will it take for the size of the infected population to double, during the early stages of a worm outbreak?

A. 16 seconds
B. 256 seconds
C. 1024 seconds

Ben convinces a consortium of router vendors to develop a new, remotelyconfigurable packet-filtering feature, and develops a system that can propagate filter updates to all routers in the Internet within 15 minutes (900 seconds) of a detected outbreak. Once all routers have the filter, the filters will prevent all further worm infections. Ben's detection mechanism is a network monitor that can observe 1/256-th of the Internet address space. His system automatically sends a filter update whenever worm traffic directed to the set of addresses he monitors reaches a predefined threshold.

b) At what traffic threshold should Ben choose to stop the worm before it reaches 50% of the vulnerable hosts?

A. 10 worm probes/second
B. 100 worm probes/second
C. 1000 worm probes/second
D. 10,000 worm probes/second
E. 100,000 worm probes/second

Exercise $\PageIndex{15}$

Ben Bitdiddle visits the Web site amazing.com and obtains a fresh page signed with a private key. Which of these methods of obtaining the certificate for the server's public key can assure Ben that the private key used for the page's signature indeed belongs to the organization that owns the domain amazing.com? (Assume that the certificate is signed by a trusted certificate authority and is valid.)

A. Using HTTP, Ben downloads the certificate from http://amazing6033.com.

B. Using HTTP, Ben downloads the certificate from the certificate authority.

C. Ben finds the certificate by doing a Web search on Google.

D. Ben gets the certificate via email from a spammer.

Exercise $\PageIndex{16}$

1995–2–5a…c

Ben Bitdiddle and Louis Reasoner have founded a startup company, named Public Key Publication, Inc. (PKPI), whose business is distributing public keys. Their idea is that people who have a key pair for use with a public-key system need a way of letting other people know the public key of their key pair. Ben and Louis are not interested in creating keys, just in acting as a public key distributor.

Ben and Louis have designed the following protocol, in which Alice sends a private message to Bob. They need your help in debugging the protocol. K_Pxyz is the public key of principal xyz .

Message 1: Alice sends the message "what is Bob's private key?" to PKPI. Message 2: PKPI sends KPBob to Alice. Message 3: Alice sends Bob the message M, encrypted with the key KPBob.

Figure $\PageIndex{2}$: Messages 1 and 2 constitute the PKPI protocol. Message 3 is the beginning of Alice's protocol with Bob and is not under the control of PKPI; it is shown here only to place the PKPI protocol in context.

a) Louis believes that Eve, the passive eavesdropper, will find that she cannot learn anything by overhearing the PKPI protocol in use. Give an argument that supports Louis's position, or an example demonstrating that Louis is mistaken.

b) Louis originally hoped that Lucifer, the active attacker, wouldn't be able to cause any problems, either, but since reading this chapter he is not sure. Give an example of an active attack that demonstrates that Louis needs to revise the PKPI protocol to protect against Lucifer.

c) Ben suggests that the protocol could be improved by changing Message 2. What changes should be made so that Alice can be confident that no one but Bob can decrypt Message 3?

Exercise $\PageIndex{17}$

1983–3–3

Louis Reasoner's cousin Norris has discovered the following interesting fact, and would like to put it to use:

Interesting fact: 2¹⁵⁰ proton-sized objects will compactly fill the known universe.

Since nonces are used in so many different applications, Norris proposes to create the Norris Nonce Service for use by everyone. If you send a request to Norris's service it will return the next 200-bit integer, in increasing order, for use as a nonce. (Norris chose 200 in case the size of the universe turns out to have been underestimated.) What are some of the things that make this proposal harder to do than Norris probably suspects?