Network Working Group B. Campen Internet-Draft Estacado Systems Expires: August 30, 2006 February 26, 2006 An Efficient Loop Detection Algorithm for SIP Proxies draft-campen-sipping-stack-loop-detect-00 Status of this Memo By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she becomes aware will be disclosed, in accordance with Section 6 of BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. This Internet-Draft will expire on August 30, 2006. Copyright Notice Copyright (C) The Internet Society (2006). Abstract This document defines a loop-detection algorithm with a cumulative O(n) complexity (O(1) average complexity for each proxy) and average O(log n) state-space, where n is the number of proxies that the message passes through. Also, the backwards-compatibility and security of this algorithm are discussed. Comments are solicited, and should be directed to the SIPPING working group list at 'sipping@ietf.org'. Campen Expires August 30, 2006 [Page 1] Internet-Draft sipping-stack-loop-detect February 2006 Table of Contents 1. Conventions and Definitions . . . . . . . . . . . . . . . . . 3 2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 3. The Stack Cycle Detection Algorithm in brief . . . . . . . . . 3 4. Applying the stack algorithm . . . . . . . . . . . . . . . . . 3 4.1. Basic ordering of proxies . . . . . . . . . . . . . . . . 3 4.2. Differentiating between spirals and loops . . . . . . . . 4 4.3. Representation of state . . . . . . . . . . . . . . . . . 4 5. Normative language . . . . . . . . . . . . . . . . . . . . . . 5 6. Properties of this algorithm . . . . . . . . . . . . . . . . . 5 6.1. Robustness against non-compliant proxies . . . . . . . . . 5 6.2. Robustness against a malicious UAC . . . . . . . . . . . . 6 6.3. Robustness against malicious proxies . . . . . . . . . . . 7 6.4. Robustness against value collisions . . . . . . . . . . . 7 6.5. Special consideration: High availability and load balancing . . . . . . . . . . . . . . . . . . . . . . . . 7 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 8 8. Security Considerations . . . . . . . . . . . . . . . . . . . 8 9. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 8 10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 8 10.1. Normative References . . . . . . . . . . . . . . . . . . . 8 10.2. Informative References . . . . . . . . . . . . . . . . . . 8 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 10 Intellectual Property and Copyright Statements . . . . . . . . . . 11 Campen Expires August 30, 2006 [Page 2] Internet-Draft sipping-stack-loop-detect February 2006 1. Conventions and Definitions The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC-2119 [RFC2119]. 2. Introduction The [maxforwards-problems] draft shows that a forking loop can be used to easily bring down a collection of SIP proxies. Loop detection offers a strategy to prevent this sort of attack, but the loop-detection algorithm defined in [RFC3261] sec 16.3 takes O(n) runtime at each node, where n is the depth of the Via stack at that node. This document shows how a more efficient loop detection algorithm [stack-cycle-detection] may be applied to loop detection for SIP requests. The paper referenced shows that the runtime of this algorithm is O(1) for each node (O(n) overall) with an average state space of O(log(n)). Other desirable characteristics of this algorithm are summarized here. 3. The Stack Cycle Detection Algorithm in brief Suppose we have a set of nodes. Assign a unique number (node value) to each of these nodes. As a request passes through a node, look for a stack of node values in the request, and pop every value found that is higher than the current node's value. Then, push the current node value onto the stack. Suppose we have a loop. Take the node in the loop with the lowest node value (call it A). The first time the message passes through A, A pushes its node value onto the stack (since every node pushes its value onto the stack). No other node in the loop will pop A's node value, since A's node value is lowest. When the message returns to A, A is guaranteed to pop the stack until it finds its own node value, and detects the loop. 4. Applying the stack algorithm 4.1. Basic ordering of proxies In order for this algorithm to work, we must have a numbering scheme for all the SIP proxies in the world. Using a randomly chosen (at least 32-bit) number could suffice, as the probability of a collision is very small. However, if a collision occurs, it is likely to occur again with non-trivial frequency, because the proxy node values have Campen Expires August 30, 2006 [Page 3] Internet-Draft sipping-stack-loop-detect February 2006 a long lifetime. Therefore, it is desirable to attempt a unique naming scheme. An easy way to do this is to base the node value on IP address, but there are cases where this will not be acceptable (see Section 6.5). Unfortunately, allowing the node values to be constant for long periods of time means that proxies with relatively low node values will do a larger share of the work than other proxies. However, allowing node values to change is problematic, as we must ensure that the node values are invariant throughout the forwarding of any request. An easy way of accomplishing this is to use a hash of CallId and the proxy's unique id. Because CallId is invariant throughout the forwarding of a request, the proxy node values would be invariant throughout and specific to that request. However, the node values will be different for every request, allowing work to be distributed more fairly. 4.2. Differentiating between spirals and loops In order to differentiate between spirals and loops with this approach, we would need to keep a record of the various headers that influence routing behavior, which is what the branch parameter hash specified in sec 16.6 of [RFC3261] is intended to do. However, since we are already capturing information about the proxy and the request in a hash, it is appropriate to capture the rest of the information normally found in the branch parameter hash. In this scheme, a node no longer corresponds to a proxy, but to a state within a finite- state-machine, where each state is defined by a. The proxy the request is passing through. b. The CallId of the request (in other words, which request this is). c. Any information that might affect the routing of the request (Request-Uri and topmost route header value, at a bare minimum). If we observe a loop within the state machine, we have found a genuine loop that must be stopped. Spirals will not manifest as loops within this state machine, because c will differ. 4.3. Representation of state Now that we have identified the state that must be captured in the loop detection stack, we must have somewhere in the message to store this stack. To this end, we propose a new header called LDStack that will contain a lower-case string of hex-digits representing 64 bits (ie, 16 lower-case hex digits). This value will be constructed as a 64-bit hash of the proxy's unique Campen Expires August 30, 2006 [Page 4] Internet-Draft sipping-stack-loop-detect February 2006 id (this could be based on IP address, for instance), the CallId header value, the Request-Uri, the URI in the topmost route header, and any other information that may change throughout forwarding that impacts the routing decisions of this proxy. The values of To, From, and CSeq are unnecessary, since they are invariant throughout forwarding. We have only included the value of CallId in order to make node values specific to given requests. The first LDStack header value will be understood to represent the top of the stack. 5. Normative language A proxy that uses this algorithm MUST adhere to the following procedure. 1. Compute a fresh hash according to Section 4.3. 2. Pop LDStack header field values that satisfy either of the following conditions: -The LDStack header value is garbage (ie, does not consist of a 16 lower-case hex digit string) -The 64-bit integer represented by the LDStack header value is greater than the 64-bit integer calculated in step 1. (this can be done as either a lexical comparison or an integer comparison; the results will be the same) 3. If the 64-bit value remaining at the top of the stack is equal to the value calculated in step 1, respond with a 482. Otherwise, push the value calculated in step 1 (in lower-case hex representation) onto the stack as a new LDStack header value, and continue processing the message as specified in section 16.3 of RFC 3261. 6. Properties of this algorithm As with any proposed addition to SIP, we must examine this algorithm's backwards-compatibility and resistance to malicious messages. 6.1. Robustness against non-compliant proxies It is important to note that this algorithm still works when non- participating proxies are present in the loop. This is because the non-participating proxies may be considered non-entities with respect to the algorithm. When all non-compliant proxies are removed from consideration, we still will have a loop in the compliant proxies, and the algorithm will still function. Campen Expires August 30, 2006 [Page 5] Internet-Draft sipping-stack-loop-detect February 2006 To motivate further, let us consider the trivial case, where we have only one compliant proxy. The first time this message passes through this node, it will push the first (and only) LDStack header into the message. No other proxy will modify the loop-detection stack, and when the message comes back to the only compliant proxy, it will find the node value that was inserted earlier, and halt the loop. However, it should be noted that proxies participating in the algorithm incorrectly will likely cause the algorithm to fail. The algorithm will also fail to function if there are proxies or other sip elements inside the loop that re-order or remove the LDStack headers. 6.2. Robustness against a malicious UAC It is also important to note that a malicious UAC will be unable to cause the algorithm to fail in detecting a loop by pre-loading garbage LDStack header values. To motivate this, consider the following: Suppose a malicious UAC has pre-loaded some number of LDStack headers into a request. (These may be ordered in any fashion) Take the minimal node value x within the chain of nodes that this message will pass through (recall that a node is a _state_ describing what proxy the message is passing through, which request this is, and the values of its Request-Uri and topmost route header). Consider the pre- loaded LDStack headers. Take the first header whose value y is less than or equal to x. (if there is no such value y, all of the forged node values will be removed, and the algorithm proceeds unimpeded) If y is equal to x, a loop will be detected, which is opposite the intention of the malicious UAC. If y is less than x, when this request first passes through node with value x, the stack will be reduced to x, then y, then some progression of arbitrary LDStack headers. These arbitrary headers have never been inspected, and never will be, because y is lower than any node value in the chain. Hence, these arbitrary headers do not impact the algorithm in any way from here on, and may be considered as non-existent for all intents and purposes. When we consider these values as non-existent, we have a valid loop-detection stack (even y may be considered non-existent because it will never be inspected again). If x is before the loop, the request will enter the loop with a valid loop-detection stack, and the algorithm will work as intended. If x is inside the loop, it is the minimal element within the loop (because it was the minimal element overall), and the next time the request comes through x, the loop will be detected. In the event that a proxy discovers a malformed LDStack value, it is necessary that the proxy remove that value, or respond with an error. Campen Expires August 30, 2006 [Page 6] Internet-Draft sipping-stack-loop-detect February 2006 This is because if proxies are allowed to attempt interpretation of this header value, we could have different proxies interpreting it in different ways, leading to failure in the algorithm. 6.3. Robustness against malicious proxies Because this algorithm relies on all participating nodes to properly implement the algorithm, a malicious proxy inside the loop could easily cause loop detection to fail. However, any malicious proxy inside the loop will be exposed to the effects of an attack, making it an expensive method for causing DoS. It is also worth noting that RFC 3261 loop detection may also be defeated, by altering the branch parameters of requests as they are forwarded, or even deleting Via header field values while not decreasing the value of Max-forwards. Malicious proxies outside of the loop (in the "tail") will be unable to tamper with the algorithm, by a similar argument as presented in Section 6.2. The possibility that a malicious proxy might cause this algorithm to falsely detect a loop is moot, because that proxy could just choose to not forward the request. In short, this algorithm would present no new avenues of exploit to malicious proxies, with regards to loop-detection. It is worth noting that a proxy designed to generate artificially high hash values will be unlikely to do much of the work required by this algorithm. (Because the hash values are higher than what is currently on top of the stack, it needs to do only one comparison, and push its hash onto the stack) This sort of misbehavior could be used to artificially inflate performance statistics of closed-source sip elements. 6.4. Robustness against value collisions In order for a value collision to occur, two proxies must generate identical 64-bit hashes. This is astronomically unlikely, and will only cause a single request to fail. Further, since the hashes are based on the CallId header value, they will change with each request, meaning that a repeated collision is just as unlikely as the original. Further, there is no case where a hash collision will cause a loop to go undetected. 6.5. Special consideration: High availability and load balancing Because the hash generated may be based in part on the proxy's IP address, it is reasonable to ask what happens in systems where Campen Expires August 30, 2006 [Page 7] Internet-Draft sipping-stack-loop-detect February 2006 several different machines are acting as a single logical SIP element, or in systems where several logical SIP elements are collocated. In these cases, using an IP address is not appropriate, but the desire still remains for a unique id. This is an open issue, and merits discussion. 7. IANA Considerations TBD 8. Security Considerations Security considerations are discussed in Section 6.2 and Section 6.3. 9. Acknowledgments Thanks goes to the individuals who gave their input on the viability of this algorithm. These include Robert Sparks, Adam Roach, Scott Lawrence, and Scott Godin. Also, thanks goes to Nicolas Grunbaum, who pointed out the problem mentioned in Section 6.5 10. References 10.1. Normative References [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [RFC3261] Rosenberg, J., Schulzrinne, H., Camarillo, G., Johnston, A., Peterson, J., Sparks, R., Handley, M., and E. Schooler, "SIP: Session Initiation Protocol", RFC 3261, June 2002. 10.2. Informative References [maxforwards-problems] Sparks, R., Ed., Lawrence, S., and A. Hawrylyshen, "Problems with Max-Forwards Processing (and Potential Solutions)". [stack-cycle-detection] Nivasch, G., "Cycle Detection Using a Stack (http://yucs.org/~gnivasch/stackalg/index.html)", Campen Expires August 30, 2006 [Page 8] Internet-Draft sipping-stack-loop-detect February 2006 January 2004. Campen Expires August 30, 2006 [Page 9] Internet-Draft sipping-stack-loop-detect February 2006 Author's Address Byron Campen Estacado Systems 17210 Campbell Road Suite 250 Dallas, Texas 75254-4203 USA Email: bcampen@estacado.net Campen Expires August 30, 2006 [Page 10] Internet-Draft sipping-stack-loop-detect February 2006 Intellectual Property Statement The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79. Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org. Disclaimer of Validity This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Copyright Statement Copyright (C) The Internet Society (2006). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. Acknowledgment Funding for the RFC Editor function is currently provided by the Internet Society. Campen Expires August 30, 2006 [Page 11]