idnits 2.17.1 draft-ietf-tsvwg-tcp-nonce-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity -- however, there's a paragraph with a matching beginning. Boilerplate error? == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) Miscellaneous warnings: ---------------------------------------------------------------------------- -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- Couldn't find a document date in the document -- date freshness check skipped. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) No issues found here. Summary: 4 errors (**), 0 flaws (~~), 1 warning (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Internet Engineering Task Force David Wetherall 3 INTERNET DRAFT David Ely 4 draft-ietf-tsvwg-tcp-nonce-00.txt Neil Spring 5 University of Washington 6 January, 2001 7 Expires: July, 2001 9 Robust ECN Signaling with Nonces 11 Status of this Memo 13 This document is an Internet-Draft and is in full conformance with 14 all provisions of Section 10 of RFC2026. 16 Internet-Drafts are working documents of the Internet Engineering 17 Task Force (IETF), its areas, and its working groups. Note that 18 other groups may also distribute working documents as Internet- 19 Drafts. 21 Internet-Drafts are draft documents valid for a maximum of six months 22 and may be updated, replaced, or obsoleted by other documents at any 23 time. It is inappropriate to use Internet- Drafts as reference 24 material or to cite them other than as "work in progress." 26 The list of current Internet-Drafts can be accessed at 27 http://www.ietf.org/ietf/1id-abstracts.txt 29 The list of Internet-Draft Shadow Directories can be accessed at 30 http://www.ietf.org/shadow.html. 32 Abstract 34 This note describes a simple modification to ECN that protects 35 against accidental or malicious concealment of marked packets from 36 the TCP sender. This is valuable because it improves the robustness 37 of congestion control by preventing receivers from exploiting ECN to 38 gaining an unfair share of the bandwidth. The mechanism uses a 39 slightly different encoding than the existing two ECN bits in the IP 40 header, and also requires one additional bit in the TCP header. It is 41 computationally efficient for both routers and hosts. 43 1. Introduction 45 The correct operation of ECN requires the cooperation of the receiver 46 to return Congestion Experienced signals to the sender, but the 47 protocol lacks a mechanism to enforce this cooperation. This raises 48 the possibility that an unscrupulous or poorly implemented receiver 49 could always clear ECN-Echo and simply not return congestion signals 50 to the sender. This in turn would give the receivers a performance 51 advantage at the expense of competing connections that behave 52 properly. More generally, any device along the path (NAT box, 53 firewall, QOS bandwidth shapers, and so forth) could remove 54 congestion marks with impunity. 56 The above behaviors may or may not constitute a threat to the 57 operation of congestion control in the Internet. However, given of 58 the central role of congestion control, we feel it is prudent to 59 design the ECN signaling loop to be robust against as many threats as 60 possible. In this way ECN can provide a clear incentive for 61 improvement over the prior state-of-the-art without potential 62 incentives for abuse. In this note, we show how this can be achieved 63 while at the same time keeping the protocol simple and efficient. 65 Our signaling mechanism uses random one bit quantities to allow the 66 sender to verify that the receiver has implemented ECN signaling 67 correctly and that there is no other interference that conceals 68 marked (or dropped) packets in the signaling path. This provides 69 protection against both implementation errors and deliberate abuse. 70 In developing the nonce signaling mechanism we met the following 71 goals: 73 - It provides an additional check but does not change other aspects 74 of ECN, and nor does it reduce the benefits of ECN for behaving 75 receivers. 77 - It catches a misbehaving receiver with a high probability, and 78 never convicts an innocent receiver 80 - It is cheap in terms of per-packet overhead (one TCP header bit 81 more than the existing ECN mechanism) and processing 82 requirements. 84 - It is simple and, to the best of our knowledge, not prone to 85 other attacks 87 The rest of this note describes the mechanism, first with an overview 88 and then in terms of more detailed behavior at senders, routers and 89 receivers. 91 2. Overview of Solution 93 Our scheme builds on the existing ECN-Echo and CWR signaling 94 mechanism. Familiarity with ECN is assumed in this note. Also, for 95 simplicity, we describe our scheme in one direction only, though it 96 is run in both directions in parallel. 98 In a nutshell, our approach is to detect misbehavior by attaching a 99 random one bit nonce value to packets at the sender and having 100 acknowledgments from the receiver echo the nonce information that is 101 received. At routers, packet marking becomes the process of erasing 102 the nonce value. Therefore, once a packet has been marked by a 103 router, it cannot be unmarked by any party without successfully 104 guessing the value of the erased nonce. Thus receipt of correct nonce 105 information from the receiver provides the sender with a 106 probabilistic proof-of- receipt check for unmarked packets. The check 107 is used by the TCP sender to verify that the ECN-Echo bit is being 108 set correctly and that congestion indications in the form of marked 109 (or dropped) packets are not being concealed. Because one bit of 110 information is returned with each acknowledgement, senders have a 111 50-50 chance of catching a lying receiver every time they perform a 112 check. Because the check for each acknowledgement is an independent 113 trial it is highly likely that cheaters will be caught quickly if 114 there are repeated packet marks. 116 There are several areas of detail missing from the preceding high- 117 level description. We mention those areas to complete the overview. 119 First, the nonce values are echoed in the form of nonce sums. Each 120 nonce sum is carried in an acknowledgement, and represents the one 121 bit sum (XOR or parity) of nonces over the byte range represented by 122 the acknowledgement. To understand why the sum is used, rather than 123 individual echoes, consider the following argument. If every packet 124 were reliably ACKed, then the nonce carried in the unmarked packet 125 could simply be echoed. This would probabilistically prove to the 126 sender that the receiver received the packet and the packet was 127 unmarked. However, ACKs are not carried across the network reliably, 128 and not every packet is ACKed. In this case, the sender cannot 129 distinguish a lost ACK from one that was never sent in order to 130 conceal a marked packet. It would require additional mechanism, 131 beyond that used in TCP, to convey the nonce bits reliably. Instead, 132 we send the nonce sum that corresponds to the cumulative ACK. This 133 sum prevents individual marked packets from being concealed by not 134 acknowledging them. Note that because they are both one bit 135 quantities, the sum is no easier to guess than the individual nonces. 137 Second, resynchronization of the sender and receiver sums is needed 138 after congestion has occurred and packets have been marked. When 139 packets are marked, the nonce is cleared, and the sum of the nonces 140 at the receiver will no longer reflect the sum at the sender. While 141 this is conceptually fixed by having the receiver send a series of 142 partial sums for the ranges of unmarked packets that it has received, 143 this solution is clumsy because the required range information is not 144 already being sent. Fortunately, there is a simple solution that 145 does not require range information because ECN congestion indications 146 do not need to indicate the particular packets that were marked. We 147 observe that once nonces have been lost, the difference between 148 sender and receiver nonce sums will be fixed until there is further 149 loss. This means that it is possible to resynchronize the sender and 150 receiver after congestion by having the sender set its nonce sum to 151 that of the receiver. Because congestion indications do not need to 152 be conveyed more frequently than once per round trip, we suspend 153 checking while the CWR signal is being delivered and acknowledged by 154 the receiver. We reset the sender nonce sum to the receiver sum when 155 new data is acknowledged. This scheme is simple and has the benefit 156 that the receiver is not explicitly involved in the re- 157 synchronization process. 159 Third, we need to reconcile the nonces that are sent with packet with 160 acknowledgements that cover byte ranges. Acknowledged byte boundaries 161 need not match the transmitted boundaries, and during retransmissions 162 information can be resent with different byte boundaries. To handle 163 these factors, we compute nonces and nonce sums using an underlying 164 mapping of byte ranges to nonce values. Both sender and receiver 165 understand this mapping, and can convert to and from the nonces 166 carried on individual packets. 168 The next sections describe the detailed behavior of senders, routers 169 and receivers. We start with sender transmit behavior, and work our 170 way around the ECN signaling loop until we arrive back at sender 171 receive behavior. Comments in parenthesis highlight the changes 172 between the nonce mechanism and the existing ECN specification. 174 3. Sender Behavior (Transmit) 176 Senders in our scheme manage CWR and ECN-Echo as before. In addition 177 they must place nonces on packets as they are transmitted and check 178 the validity of the nonce sums on packets as they are received. This 179 section describes the transmit process. 181 To place a one bit nonce value on every IP packet requires first of 182 all a way to encode these bits in IP packets. We use the following 183 encoding of the ECN bits to identify different packet states. This 184 encoding must be understood by all ECN capable senders, routers, and 185 receivers in our scheme. (The second state below is currently unused 186 in the existing ECN specification, while the other states retain 187 their existing meanings.) 189 00 = ECN incapable 191 10 = ECN capable, unmarked (nonce = 0) 193 01 = ECN capable, unmarked (nonce = 1) 195 11 = ECN capable, marked (nonce lost) 197 Next, we require a simple way to map nonces to transmitted TCP 198 packets in a manner that is compatible with checking the nonce sum on 199 received TCP acknowledgements. This is complicated by several 200 factors. Nonces are sent per packet but acknowledgements cover byte 201 ranges that do not necessarily correspond to the original packet 202 ranges; this can depend on implementation buffering strategies. In 203 the case of retransmissions, the boundary of retransmitted packets 204 need not correspond to the original transmissions either (because of 205 path MTU changes, retransmission batching, and so forth). Finally, 206 there is ambiguity at the sender as to whether the original or 207 retransmitted packet was received. It is important that our 208 implementation behave correctly even in these rare cases so that a 209 receiver is never incorrectly labeled as misbehaving. 211 We associate nonce values with byte ranges instead of individual 212 packets to avoid these difficulties. Starting from the initial 213 sequence number, each block of SMSS bytes (the maximum segment size) 214 in the TCP byte stream is associated with a single pseudorandom nonce 215 bit. The byte range of the packet determines what nonce value it 216 will carry. If the packet, either original or a retransmission, spans 217 multiple blocks, we use the block in which the final byte of the 218 packet resides to determine which nonce value to transmit with the 219 packet. A series of small packets will carry the same nonce value 220 until an entire block's worth of SMSS bytes has been transmitted. 221 This is a useful tradeoff because sending partial packets makes a 222 flow less likely to cause congestion. Since no packet can carry more 223 than SMSS bytes, each block's nonce bit will be carried in at least 224 one packet. 226 The following table provides an example of how we decompose a byte 227 stream into blocks and how we assign nonce values to each block 228 (assuming a block size of 1460 bytes): 230 ------------------------------------------------------- 231 | Bytes: | 1...1460 | 1461...2920 | 2921 ... 4380 | 232 ------------------------------------------------------- 233 | Nonce: | 1 | 1 | 0 | 234 ------------------------------------------------------- 235 | Nonce Sum: | 1 | 0 | 1 | 236 ------------------------------------------------------- 238 4. Router Behavior 240 Routers must be able to identify packets sent by ECN capable 241 transports and mark them if indicated by active queue management. To 242 mark packets, routers change either of the unmarked states to the 243 single marked state. (The operation of marking has changed only in 244 that routers now need to recognize two states as meaning not marked 245 and so is still straightforward.) This erases the state of the 246 original nonce carried with the packet, which is key to our scheme. 247 Neither the receiver nor any other party can now unmark the packet 248 without successfully guessing the value of the original nonce. 250 5. Receiver Behavior (Receive and Transmit) 252 In addition to distinguishing marked and unmarked packets and setting 253 the ECN- Echo flag as before, receivers in our scheme maintain a 254 nonce sum as packets arrive, and return the sum that corresponds to a 255 particular acknowledgment with the acknowledgment. 257 To maintain the nonce sum, receivers use the same mapping as the 258 sender to convert the nonces carried in unmarked packets to the 259 nonces of the underlying blocks. These nonce values are summed over 260 the byte range covered by the acknowledgement. Computing this sum 261 correctly when packets of size SMSS are sent requires that all 262 packets up to the one acknowledged be received. New sums are computed 263 by taking the old value and XORing it with a new nonce. That is, the 264 sum is also a one bit quantity, and old nonce state does not need to 265 be maintained. 267 In the case of marked packets, one or more nonce values may be 268 unknown to the receiver. In this case the missing nonce values are 269 ignored when calculating the sum (or equivalently a value of zero is 270 assumed) and ECN-Echo will be set to signal congestion to the sender. 272 Returning the nonce sum corresponding to a given acknowledgement is 273 straightforward. It is carried in a single bit in the TCP header. 274 (This bit is in addition the CWR and ECN-Echo bits and would require 275 one of the reserved bits to be allocated.) 276 These nonce sums are checked for validity at the sender, as described 277 below. 279 6. Sender Behavior (Receive) 281 This section completes the description of sender behavior by 282 describing how senders check the validity of the nonce sums. 284 Checking is straightforward and is performed every time an 285 acknowledgement is received, except during congestion recovery. Given 286 the byte range covered by an acknowledgement and the mapping between 287 bytes and nonces, the sender is able to compute the correct nonce 288 sum. Minimal sender state is needed to do this because old nonce 289 values can be discarded as acknowledgments and the sum advance. 290 Checking consists of simply comparing the correct nonce sum and that 291 carried in the acknowledgement. 293 If ECN-Echo is not set, the receiver claims to have received no 294 marked packets, and can therefore compute the correct nonce sum. To 295 cheat, the receiver must successfully guess the sum of the nonces 296 that it did not receive (because at least one packet was marked and 297 the corresponding nonce was erased). Provided the individual nonces 298 are equally likely to be 0 or 1, their sum is equally likely to be 0 299 or 1. In other words, any guess is equally likely to be wrong and 300 has a 50-50 chance of being caught by the sender. Because each 301 acknowledgement (that covers a new block) is an independent trial, a 302 cheating receiver is highly likely to be caught after a small number 303 of lies. 305 If ECN-Echo is set, the receiver is sending a congestion signal and 306 it is not necessary to check the nonce sum. The congestion window 307 will be halved, CWR will be set on the next packet with new data 308 sent, and ECN-Echo will be cleared once the CWR signal is received. 309 During this recovery process, the sum may be incorrect because one or 310 more nonces were not received. This does not matter during recovery, 311 because TCP invokes congestion mechanisms at most once per RTT, 312 whether there are one or more losses during that period. However, 313 after recovery, it is necessary to re-synchronize the sender and 314 receiver nonce sums so that further acknowledgments can be checked. 315 If might be possible to send the missing nonces to the receiver, but 316 this would be cumbersome because TCP lacks the mechanism to do so 317 conveniently. Instead, we observe that if there are no more marked 318 packets, the sender and receiver sums should differ by a constant 319 amount. This leads to a simple re-synchronization mechanism where the 320 sender resets its nonce sum to that of the receiver when it receives 321 an acknowledgment for new data sent after the congestion window was 322 reduced. In most instances, this will be the first acknowledgement 323 without the ECN-Echo flag set. 325 A separate issue is the penalty for misbehavior that is caught by 326 checking. During normal operation, both with and without packet 327 marks and drops, no misbehavior will be uncovered unless some party 328 after the marking router is behaving incorrectly. A simple remedy in 329 this case would be to disable ECN at the sender, that is, not mark 330 packets as ECN capable. This simultaneously deprives the receiver of 331 the benefits of ECN and relieves the sender of the need to monitor 332 the receiver. However, an additional consideration is that the nonce 333 checking mechanism provides robustness beyond checking that marked 334 packets are signaled to the sender. It also ensures that dropped 335 packets cannot be concealed from the sender (because their nonces 336 have been lost). Drops could potentially be concealed by a faulty TCP 337 implementation, certain attacks, or even a hypothetical a TCP 338 accelerator willing to gamble that it can either successfully ``fast 339 start'' to a preset bandwidth quickly, retry with another connection, 340 or provide reliability at the application level. If robustness 341 against these faults is considered valuable (as opposed to simply 342 detecting a faulty ECN implementation) then it is not clear that the 343 nonce mechanism should be turned off. Instead, a penalty such as 344 reducing the congestion window by a factor of 4 may be preferable. 345 This would provide continued checking while punishing faulty 346 operation. Luckily, this issue is separate from the checking 347 mechanism and does not need to be handled uniformly by senders. 349 7. Conclusion 351 We have described a simple modification to the ECN signaling 352 mechanism that improves its robustness by preventing receivers from 353 concealing marked (or dropped) packets. The intent of this work is to 354 help improve the robustness of congestion control in the Internet. 355 The modification is retains the character and simplicity of existing 356 ECN signaling. It is also practical for deployment in the Internet. 357 It requires two bits in the IP header (ECT and CE with a slightly 358 different encoding) and one additional bit in the TCP header (as well 359 as CWR and ECN-Echo) and has simple processing rules. 361 Acknowledgements 363 This note grew out of research done by Stefan Savage, David Ely, 364 David Wetherall, Tom Anderson and Neil Spring. We are grateful for 365 feedback from Sally Floyd. 367 Authors' Addresses 369 David Wetherall 370 Email: djw@cs.washington.edu 371 Phone +1 (206) 616 4367 373 David Ely 374 Email: ely@cs.washington.edu 376 Neil Spring 377 Email: nspring@cs.washington.edu 379 Computer Science and Engineering, 352350 380 University of Washington 381 Seattle, WA 98195-2350 383 Send comments by electronic mail to all three authors. 385 This draft was created in January 2001. 386 It expires July 2001.