idnits 2.17.1 draft-campen-sipping-stack-loop-detect-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3978, Section 5.1 on line 14. -- Found old boilerplate from RFC 3978, Section 5.5 on line 401. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 378. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 385. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 391. ** This document has an original RFC 3978 Section 5.4 Copyright Line, instead of the newer IETF Trust Copyright according to RFC 4748. ** This document has an original RFC 3978 Section 5.5 Disclaimer, instead of the newer disclaimer which includes the IETF Trust according to RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year -- 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.) -- The document date (February 26, 2006) is 6627 days in the past. Is this intentional? 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: 3 errors (**), 0 flaws (~~), 2 warnings (==), 7 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group B. Campen 3 Internet-Draft Estacado Systems 4 Expires: August 30, 2006 February 26, 2006 6 An Efficient Loop Detection Algorithm for SIP Proxies 7 draft-campen-sipping-stack-loop-detect-00 9 Status of this Memo 11 By submitting this Internet-Draft, each author represents that any 12 applicable patent or other IPR claims of which he or she is aware 13 have been or will be disclosed, and any of which he or she becomes 14 aware will be disclosed, in accordance with Section 6 of BCP 79. 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 This Internet-Draft will expire on August 30, 2006. 34 Copyright Notice 36 Copyright (C) The Internet Society (2006). 38 Abstract 40 This document defines a loop-detection algorithm with a cumulative 41 O(n) complexity (O(1) average complexity for each proxy) and average 42 O(log n) state-space, where n is the number of proxies that the 43 message passes through. Also, the backwards-compatibility and 44 security of this algorithm are discussed. 46 Comments are solicited, and should be directed to the SIPPING working 47 group list at 'sipping@ietf.org'. 49 Table of Contents 51 1. Conventions and Definitions . . . . . . . . . . . . . . . . . 3 52 2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 53 3. The Stack Cycle Detection Algorithm in brief . . . . . . . . . 3 54 4. Applying the stack algorithm . . . . . . . . . . . . . . . . . 3 55 4.1. Basic ordering of proxies . . . . . . . . . . . . . . . . 3 56 4.2. Differentiating between spirals and loops . . . . . . . . 4 57 4.3. Representation of state . . . . . . . . . . . . . . . . . 4 58 5. Normative language . . . . . . . . . . . . . . . . . . . . . . 5 59 6. Properties of this algorithm . . . . . . . . . . . . . . . . . 5 60 6.1. Robustness against non-compliant proxies . . . . . . . . . 5 61 6.2. Robustness against a malicious UAC . . . . . . . . . . . . 6 62 6.3. Robustness against malicious proxies . . . . . . . . . . . 7 63 6.4. Robustness against value collisions . . . . . . . . . . . 7 64 6.5. Special consideration: High availability and load 65 balancing . . . . . . . . . . . . . . . . . . . . . . . . 7 66 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 8 67 8. Security Considerations . . . . . . . . . . . . . . . . . . . 8 68 9. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 8 69 10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 8 70 10.1. Normative References . . . . . . . . . . . . . . . . . . . 8 71 10.2. Informative References . . . . . . . . . . . . . . . . . . 8 72 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 10 73 Intellectual Property and Copyright Statements . . . . . . . . . . 11 75 1. Conventions and Definitions 77 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 78 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 79 document are to be interpreted as described in RFC-2119 [RFC2119]. 81 2. Introduction 83 The [maxforwards-problems] draft shows that a forking loop can be 84 used to easily bring down a collection of SIP proxies. Loop 85 detection offers a strategy to prevent this sort of attack, but the 86 loop-detection algorithm defined in [RFC3261] sec 16.3 takes O(n) 87 runtime at each node, where n is the depth of the Via stack at that 88 node. This document shows how a more efficient loop detection 89 algorithm [stack-cycle-detection] may be applied to loop detection 90 for SIP requests. The paper referenced shows that the runtime of 91 this algorithm is O(1) for each node (O(n) overall) with an average 92 state space of O(log(n)). Other desirable characteristics of this 93 algorithm are summarized here. 95 3. The Stack Cycle Detection Algorithm in brief 97 Suppose we have a set of nodes. Assign a unique number (node value) 98 to each of these nodes. As a request passes through a node, look for 99 a stack of node values in the request, and pop every value found that 100 is higher than the current node's value. Then, push the current node 101 value onto the stack. 103 Suppose we have a loop. Take the node in the loop with the lowest 104 node value (call it A). The first time the message passes through A, 105 A pushes its node value onto the stack (since every node pushes its 106 value onto the stack). No other node in the loop will pop A's node 107 value, since A's node value is lowest. When the message returns to 108 A, A is guaranteed to pop the stack until it finds its own node 109 value, and detects the loop. 111 4. Applying the stack algorithm 113 4.1. Basic ordering of proxies 115 In order for this algorithm to work, we must have a numbering scheme 116 for all the SIP proxies in the world. Using a randomly chosen (at 117 least 32-bit) number could suffice, as the probability of a collision 118 is very small. However, if a collision occurs, it is likely to occur 119 again with non-trivial frequency, because the proxy node values have 120 a long lifetime. Therefore, it is desirable to attempt a unique 121 naming scheme. An easy way to do this is to base the node value on 122 IP address, but there are cases where this will not be acceptable 123 (see Section 6.5). 125 Unfortunately, allowing the node values to be constant for long 126 periods of time means that proxies with relatively low node values 127 will do a larger share of the work than other proxies. However, 128 allowing node values to change is problematic, as we must ensure that 129 the node values are invariant throughout the forwarding of any 130 request. 132 An easy way of accomplishing this is to use a hash of CallId and the 133 proxy's unique id. Because CallId is invariant throughout the 134 forwarding of a request, the proxy node values would be invariant 135 throughout and specific to that request. However, the node values 136 will be different for every request, allowing work to be distributed 137 more fairly. 139 4.2. Differentiating between spirals and loops 141 In order to differentiate between spirals and loops with this 142 approach, we would need to keep a record of the various headers that 143 influence routing behavior, which is what the branch parameter hash 144 specified in sec 16.6 of [RFC3261] is intended to do. However, since 145 we are already capturing information about the proxy and the request 146 in a hash, it is appropriate to capture the rest of the information 147 normally found in the branch parameter hash. In this scheme, a node 148 no longer corresponds to a proxy, but to a state within a finite- 149 state-machine, where each state is defined by 150 a. The proxy the request is passing through. 151 b. The CallId of the request (in other words, which request this 152 is). 153 c. Any information that might affect the routing of the request 154 (Request-Uri and topmost route header value, at a bare minimum). 155 If we observe a loop within the state machine, we have found a 156 genuine loop that must be stopped. Spirals will not manifest as 157 loops within this state machine, because c will differ. 159 4.3. Representation of state 161 Now that we have identified the state that must be captured in the 162 loop detection stack, we must have somewhere in the message to store 163 this stack. To this end, we propose a new header called LDStack that 164 will contain a lower-case string of hex-digits representing 64 bits 165 (ie, 16 lower-case hex digits). 167 This value will be constructed as a 64-bit hash of the proxy's unique 168 id (this could be based on IP address, for instance), the CallId 169 header value, the Request-Uri, the URI in the topmost route header, 170 and any other information that may change throughout forwarding that 171 impacts the routing decisions of this proxy. The values of To, From, 172 and CSeq are unnecessary, since they are invariant throughout 173 forwarding. We have only included the value of CallId in order to 174 make node values specific to given requests. 176 The first LDStack header value will be understood to represent the 177 top of the stack. 179 5. Normative language 181 A proxy that uses this algorithm MUST adhere to the following 182 procedure. 184 1. Compute a fresh hash according to Section 4.3. 185 2. Pop LDStack header field values that satisfy either of the 186 following conditions: 187 -The LDStack header value is garbage (ie, does not consist of a 188 16 lower-case hex digit string) 189 -The 64-bit integer represented by the LDStack header value is 190 greater than the 64-bit integer calculated in step 1. (this can 191 be done as either a lexical comparison or an integer 192 comparison; the results will be the same) 193 3. If the 64-bit value remaining at the top of the stack is equal 194 to the value calculated in step 1, respond with a 482. Otherwise, 195 push the value calculated in step 1 (in lower-case hex 196 representation) onto the stack as a new LDStack header value, and 197 continue processing the message as specified in section 16.3 of 198 RFC 3261. 200 6. Properties of this algorithm 202 As with any proposed addition to SIP, we must examine this 203 algorithm's backwards-compatibility and resistance to malicious 204 messages. 206 6.1. Robustness against non-compliant proxies 208 It is important to note that this algorithm still works when non- 209 participating proxies are present in the loop. This is because the 210 non-participating proxies may be considered non-entities with respect 211 to the algorithm. When all non-compliant proxies are removed from 212 consideration, we still will have a loop in the compliant proxies, 213 and the algorithm will still function. 215 To motivate further, let us consider the trivial case, where we have 216 only one compliant proxy. The first time this message passes through 217 this node, it will push the first (and only) LDStack header into the 218 message. No other proxy will modify the loop-detection stack, and 219 when the message comes back to the only compliant proxy, it will find 220 the node value that was inserted earlier, and halt the loop. 222 However, it should be noted that proxies participating in the 223 algorithm incorrectly will likely cause the algorithm to fail. The 224 algorithm will also fail to function if there are proxies or other 225 sip elements inside the loop that re-order or remove the LDStack 226 headers. 228 6.2. Robustness against a malicious UAC 230 It is also important to note that a malicious UAC will be unable to 231 cause the algorithm to fail in detecting a loop by pre-loading 232 garbage LDStack header values. To motivate this, consider the 233 following: 235 Suppose a malicious UAC has pre-loaded some number of LDStack headers 236 into a request. (These may be ordered in any fashion) Take the 237 minimal node value x within the chain of nodes that this message will 238 pass through (recall that a node is a _state_ describing what proxy 239 the message is passing through, which request this is, and the values 240 of its Request-Uri and topmost route header). Consider the pre- 241 loaded LDStack headers. Take the first header whose value y is less 242 than or equal to x. (if there is no such value y, all of the forged 243 node values will be removed, and the algorithm proceeds unimpeded) If 244 y is equal to x, a loop will be detected, which is opposite the 245 intention of the malicious UAC. If y is less than x, when this 246 request first passes through node with value x, the stack will be 247 reduced to x, then y, then some progression of arbitrary LDStack 248 headers. These arbitrary headers have never been inspected, and 249 never will be, because y is lower than any node value in the chain. 250 Hence, these arbitrary headers do not impact the algorithm in any way 251 from here on, and may be considered as non-existent for all intents 252 and purposes. When we consider these values as non-existent, we have 253 a valid loop-detection stack (even y may be considered non-existent 254 because it will never be inspected again). If x is before the loop, 255 the request will enter the loop with a valid loop-detection stack, 256 and the algorithm will work as intended. If x is inside the loop, it 257 is the minimal element within the loop (because it was the minimal 258 element overall), and the next time the request comes through x, the 259 loop will be detected. 261 In the event that a proxy discovers a malformed LDStack value, it is 262 necessary that the proxy remove that value, or respond with an error. 264 This is because if proxies are allowed to attempt interpretation of 265 this header value, we could have different proxies interpreting it in 266 different ways, leading to failure in the algorithm. 268 6.3. Robustness against malicious proxies 270 Because this algorithm relies on all participating nodes to properly 271 implement the algorithm, a malicious proxy inside the loop could 272 easily cause loop detection to fail. However, any malicious proxy 273 inside the loop will be exposed to the effects of an attack, making 274 it an expensive method for causing DoS. It is also worth noting that 275 RFC 3261 loop detection may also be defeated, by altering the branch 276 parameters of requests as they are forwarded, or even deleting Via 277 header field values while not decreasing the value of Max-forwards. 279 Malicious proxies outside of the loop (in the "tail") will be unable 280 to tamper with the algorithm, by a similar argument as presented in 281 Section 6.2. 283 The possibility that a malicious proxy might cause this algorithm to 284 falsely detect a loop is moot, because that proxy could just choose 285 to not forward the request. 287 In short, this algorithm would present no new avenues of exploit to 288 malicious proxies, with regards to loop-detection. 290 It is worth noting that a proxy designed to generate artificially 291 high hash values will be unlikely to do much of the work required by 292 this algorithm. (Because the hash values are higher than what is 293 currently on top of the stack, it needs to do only one comparison, 294 and push its hash onto the stack) This sort of misbehavior could be 295 used to artificially inflate performance statistics of closed-source 296 sip elements. 298 6.4. Robustness against value collisions 300 In order for a value collision to occur, two proxies must generate 301 identical 64-bit hashes. This is astronomically unlikely, and will 302 only cause a single request to fail. Further, since the hashes are 303 based on the CallId header value, they will change with each request, 304 meaning that a repeated collision is just as unlikely as the 305 original. Further, there is no case where a hash collision will 306 cause a loop to go undetected. 308 6.5. Special consideration: High availability and load balancing 310 Because the hash generated may be based in part on the proxy's IP 311 address, it is reasonable to ask what happens in systems where 312 several different machines are acting as a single logical SIP 313 element, or in systems where several logical SIP elements are 314 collocated. In these cases, using an IP address is not appropriate, 315 but the desire still remains for a unique id. 317 This is an open issue, and merits discussion. 319 7. IANA Considerations 321 TBD 323 8. Security Considerations 325 Security considerations are discussed in Section 6.2 and Section 6.3. 327 9. Acknowledgments 329 Thanks goes to the individuals who gave their input on the viability 330 of this algorithm. These include Robert Sparks, Adam Roach, Scott 331 Lawrence, and Scott Godin. Also, thanks goes to Nicolas Grunbaum, 332 who pointed out the problem mentioned in Section 6.5 334 10. References 336 10.1. Normative References 338 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 339 Requirement Levels", BCP 14, RFC 2119, March 1997. 341 [RFC3261] Rosenberg, J., Schulzrinne, H., Camarillo, G., Johnston, 342 A., Peterson, J., Sparks, R., Handley, M., and E. 343 Schooler, "SIP: Session Initiation Protocol", RFC 3261, 344 June 2002. 346 10.2. Informative References 348 [maxforwards-problems] 349 Sparks, R., Ed., Lawrence, S., and A. Hawrylyshen, 350 "Problems with Max-Forwards Processing (and Potential 351 Solutions)". 353 [stack-cycle-detection] 354 Nivasch, G., "Cycle Detection Using a Stack 355 (http://yucs.org/~gnivasch/stackalg/index.html)", 356 January 2004. 358 Author's Address 360 Byron Campen 361 Estacado Systems 362 17210 Campbell Road 363 Suite 250 364 Dallas, Texas 75254-4203 365 USA 367 Email: bcampen@estacado.net 369 Intellectual Property Statement 371 The IETF takes no position regarding the validity or scope of any 372 Intellectual Property Rights or other rights that might be claimed to 373 pertain to the implementation or use of the technology described in 374 this document or the extent to which any license under such rights 375 might or might not be available; nor does it represent that it has 376 made any independent effort to identify any such rights. Information 377 on the procedures with respect to rights in RFC documents can be 378 found in BCP 78 and BCP 79. 380 Copies of IPR disclosures made to the IETF Secretariat and any 381 assurances of licenses to be made available, or the result of an 382 attempt made to obtain a general license or permission for the use of 383 such proprietary rights by implementers or users of this 384 specification can be obtained from the IETF on-line IPR repository at 385 http://www.ietf.org/ipr. 387 The IETF invites any interested party to bring to its attention any 388 copyrights, patents or patent applications, or other proprietary 389 rights that may cover technology that may be required to implement 390 this standard. Please address the information to the IETF at 391 ietf-ipr@ietf.org. 393 Disclaimer of Validity 395 This document and the information contained herein are provided on an 396 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 397 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET 398 ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, 399 INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE 400 INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 401 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 403 Copyright Statement 405 Copyright (C) The Internet Society (2006). This document is subject 406 to the rights, licenses and restrictions contained in BCP 78, and 407 except as set forth therein, the authors retain all their rights. 409 Acknowledgment 411 Funding for the RFC Editor function is currently provided by the 412 Internet Society.