MCS-377 Homework (Fall 2006)

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.r4, p. 61.
Problem 1.r5, p. 61.
Problem 1.r9, p. 61.
Problem 1.r23, p. 62.
Problem 1.p6, p. 64.
Problem 1.p7, p. 64.

Chapter 2

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.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.
Problem 2.x2: List at least five types of header lines that can be used in the HTTP protocol. What is the function of each?
Problem 2.x3: Use the command dig www.gustavus.edu to trace the chain of CNAMES that leads from www.gustavus.edu to a numerical IP address.

Chapter 3

Problem 3.r6, p. 286.
Problem 3.p4, p. 287. Ignore the first sentence, "Consider our motivation..." 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)".
4. Each line of the form "make_pkt(sndpkt, ...)" should be changed to "sndpkt = make_pkt(...)".
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:
1. Express the IP address 10100011000101000110000100001111 in dotted decimal.
2. Express the IP address 194.79.127.10 in binary.
3. How many 1 bits does 255.255.192.0 start with?
4. How many 1 bits does 255.255.224.0 start with?
5. Write in dotted decimal form an address with 20 bits that are 1 followed by 12 that are 0.
6. Write in dotted decimal form an address with 22 bits that are 1 followed by 10 that are 0.
Problem 4.x3: 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. Also, indicate which of the following IP addresses would be reached directly and which would be reached by way of the gateway router: 138.236.71.64, 138.236.72.64, 138.236.64.72, and 216.114.254.180.

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, as determined by the initial letter 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 15th USENIX Security Symposium, July 31-August 4, 2006.

Last name starting with F
"Keyboards and Covert Channels" by Gaurav Shah, Andres Molina, and Matt Blaze, pp. 59-75
Last name starting with H
"SANE: A Protection Architecture for Enterprise Networks" by Martin Casado et al., pp. 137-151
Last name starting with K
"PHAS: A Prefix Hijack Alert System" by Mohit Lad et al., pp. 153-166
Last name starting with L
"Passive Data Link Layer 802.11 Wireless Device Driver Fingerprinting" by Jason Franklin et al., pp. 167-178
Last name starting with R
"Rule-Based Static Analysis of Network Protocol Implementations" by Octavian Udrea, Cristian Lumezanu, and Jeffrey S. Foster, pp. 193-208
Last name starting with S
"Dynamic Application-Layer Protocol Analysis for Network Intrusion Detection" by Holger Dreger et al., p. 257-272
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