MCS-377 Homework (Fall 2004)

When turning in a homework problem, if it is one from the book, you should indicate not only the exercise number, but also which kind of exercise it is: review question, problem, or discussion question. The code I will use for this is as follows: 1.r5 is review question 5 of chapter 1; 1.p7 is problem 7 of chapter 1; 1.d1 is discussion problem 1 of chapter 1. Please use this code when you turn in the problems, and I will use them in reporting back your standing on the homework. For any problems that are not from the book, I will specify the problem number to use, which will have an x in it (e.g., 2.x1).

Note that I will add problems to this list from time to time, but unless I warn you otherwise, only by adding entire new chapters at the end. So if you check back, tell your browser to reload the page (in case it has an old version cached) and then look and see if there are any new chapters after what used to be the last chapter with problems

Chapter 1

Problem 1.r5, p. 61.
Problem 1.r9, p. 61.
Problem 1.r23, p. 62.
Problem 1.p7, p. 64.

Chapter 2

Problem 2.r8, p. 170.
Problem 2.r19, p. 171. Assume the organization's web and mail servers are different. For example, they might be www.foo.com and mail.foo.com, each with a type A record with a different IP address. Web access to foo.com should be just like to www.foo.com, whereas mail addressed to foo.com should go to mail.foo.com. What RR type is used to provide the translation of foo.com in each context? (The book just asks about the mail context; I want both.) There may be more than one correct answer.
Problem 2.p5, p. 172.
Problem 2.p17, p. 173. Also, what are some of the comparative advantages and disadvantages of the alternatives described in parts (b) and (c)?
Problem 2.p21, p. 176.
Problem 2.x1: SMTP and POP3 are both used for email, but play different roles. Explain the difference in their roles. Make your explanation concrete by mentioning typical commands from each of the two protocols and explaining their general function.

Chapter 3

Problem 3.r6, p. 286.
Problem 3.p4, p. 287. This problem refers to an unlabeled figure on p. 288, to which you need to make the following corrections before working the problem:
1. Add a dotted arrow pointing to the start state, "Wait for 0 from below".
2. In the action on that state's loop edge, replace "andpkt" by "sndpkt".
3. The right-hand edge of the figure is chopped off; on the line printed as "make_pkt(sndpkt, NAK, c", tack on "hksum)".
The "deadlock" may not be a state where packets stop being sent; it can be a situation where no forward progress is made on delivering new data, even though packets go back and forth. Also, the problem should be worked within the context of no lost packets, only corruption, and with the assumption that even corruption will not continue forever.
Problem 3.x1: Indicate whether each statement is true or false. If false, briefly explain why.
1. Each TCP segment has a sequence number one greater than its predecessor.
2. A TCP sender can send as much data as the current congestion window before it has to wait for acknowledgments.
3. If a TCP receiver receives a corrupt segment, it sends a NAK.
4. In TCP's slow-start mode, each segment acknowledged causes the congestion window to expand by one segment.
5. In TCP's congestion-avoidance mode, each segment acknowledged causes the congestion window to expand by one segment.
6. A lost TCP segment will result in a timeout.
Problem 3.x2: The X in the following diagram is a lost segment. The TCP segments flowing in the left-to-right direction each carry 1000 bytes of data, whereas those in the right-to-left direction are pure ACKs. Add the sequence and ACK numbers to the nine arrows that don't already have them.
Problem 3.x3: Normally if a TCP host receives a segment with sequence number 1000 and length 1460 (for example), it will respond with an ACK of 2460, since that is the sequence number of the next byte anticipated. Suppose instead that it sent two ACKs, one with the ACK number field being 2000 and the second with it being 2460. In terms of the simplified TCP sender of Figure 3.33 (p. 240), is there any harm in this "divided ACK"? Next, consider the TCP congestion control algorithm as summarized in Table 3.3 on page 269. What would the impact of the divided ACK be on this algorithm? Is this a good or a bad thing?
Problem 3.x4:
1. How does TCP provide flow control?
2. What two ways does TCP, as currently standardized, use to detect congestion?
3. What two additional ways for TCP to detect congestion have been proposed?

Chapter 4

Problem 4.r16, p. 401. Be sure to justify your answer. Assume no TCP or IP options are used.
Problem 4.p10, p. 406.
Problem 4.p11, p. 406.
Problem 4.p21, p. 408.
Problem 4.p23, p. 408.
Problem 4.x1: We have seen two general approaches to multicast routing: one exemplified by DVMRP and PIM Dense Mode, the other exemplified by CBT and PIM Sparse Mode (at least initially; PIM Sparse mode has the ability to switch approaches).
1. What are the names of these two approaches?
2. Which one of them has more in common with the spanning trees used by Ethernet switches to avoid cycles?
3. Briefly explain what the similarity is.
Problem 4.x2: Use the command
```
/sbin/ifconfig eth0
```
on an MCS-department Linux machine to find the mask and the "inet addr" (i.e., IP address). How many 1 bits does the mask contain? Use that as the value of x to express the subnet address in the form a.b.c.d/x. To find a.b.c.d, take the machine's IP address and change the rightmost 32-x bits to zeros.

Chapter 5

Problem 5.p11, p. 496.
Problem 5.p12, p. 496.
Problem 5.p17, p. 498. In Figure 5.42, there is no interface number on the links leading from R6 and R5 to R4. Assume these are interface 0 in each case.
Problem 5.x1: A computer wants to send the data bits 11010010, followed by three CRC bits. What should those CRC bits be, if the generator is 1001? Show your work.
Problem 5.x2: (For this problem, note an erratum on p. 461: change 2^m-1 to 2^m-1.) Suppose two nearby computers, A and B, both have numerous frames queued up for transmission on the same Ethernet segment. Call these frames A1, A2, etc. at A, and B1, B2, etc. at B. Assume there are no other computers trying to transmit on this Ethernet segment. At time 0, A makes an initial attempt to transmit A1 and B makes an initial attempt to transmit B1. They collide. A chooses K=0 and B chooses K=1. The result is that the first frame successfully transmitted is A1. Afterward there is another collision, between A2 and B1. Suppose A2 wins, i.e., A again picks a smaller K than B does. After A2 is done being transmitted, A3 collides with B1. When A and B back off and retry their transmissions, which is more likely to go first, A3 or B1? Explain why. You need not calculate the exact probability that the more likely one goes first, but you should at least provide a lower bound on this probability that is greater than 1/2.

Chapter 6

Problem 6.r6, p. 560.
Problem 6.p3, p. 560.
Problem 6.p5, p. 560.
Problem 6.p8, p. 561.
Problem 6.x1: Do either of the following:
- Section 6.3 says that address 3 in an 802.11 frame contains a router's MAC address. In class, I suggested it could instead be the MAC address of another host on the same subnet as the AP. Resolve this disagreement, in one of the following ways: by reference to the text of the 802.11 standard, by reference to another credible text, by experimentation with ethereal on a system that can capture 802.11 frames (which ethereal under Windows, unfortunately, cannot), or by making a convincing argument why one of the two contenting claims makes more sense.
- The text's description of Mobile IP assumes that only unicast datagrams are sent to the permanent address. By default, broadcast datagrams are not forwarded. However, an option allows them to be forwarded. Explain how this optional forwarding works. That is, what mechanism is used for the optional forwarding? Some issues to consider are whether the forwarded packet winds up (re-)broadcast on the visited network, and whether there is any sacrifice of transparency.

Chapter 8

Problem 8.x1: Read one of the following papers, determined by the start of your last name. Write a one-page summary, in your own words, of the paper. All these papers were published in the Proceedings of the 13th USENIX Security Symposium, August, 2004.

Last names A-C
"Very Fast Containment of Scanning Worms," by Nicholas Weaver, Stuart Staniford, and Vern Paxson, pp. 29-44.
Last names D-Ha
"Network-in-a-Box: How to Set Up a Secure Wireless Network in Under a Minute," by Dirk Balfanz, Glenn Durfee, Rebecca E. Grinter, Diana K. Smetters, and Paul Stewart, pp. 207-222.
Last names He-Ho
"Privacy-Preserving Sharing and Correlation of Security Alerts," by Patrick Lincoln, Phillip Porras, and Vitaly Shmatikov, pp. 239-254.
Last names K-Sche
"Autograph: Toward Automated, Distributed Worm Signature Detection," by Hyang-Ah Kim and Brad Karp, pp. 271-286.
Last names Schm-W
"Tor: The Second-Generation Onion Router," by Roger Dingledine, Nick Mathewson, and Paul Syverson, pp. 303-320.
Problem 8.x2: Do review problems 8.r1 and 8.r3 from page 722, but label your answers as a single problem, 8.x2.
Problem 8.x3: 8.p7 mentions that BGP can use MD5 for signatures. However, this leaves open how a message digest function can be used (without also using either public-key or symmetric-key cryptography) for signatures. In particular, where does a key fit into this? Answer this question of mine (not the original 8.p7 question), refering to the RFC about BGP's use of MD5 if you need to.
Problem 8.x4: On p. 683, Kurose and Ross say that "no one has argued with [Rivest's] claim" that finding an MD5 collision is hard. This is outdated. Find up-to-date information on MD5 collision attacks, and briefly summarize it.
Problem 8.p10, p. 724. That is, can any of the three parties be impersonated? Why or why not?
Problem 8.p11, p. 724.
Problem 8.p13, p. 725

Instructor: Max Hailperin