Internet Engineering Task Force M. Khandelwal Internet-Draft R. Desetti Updates: 2328, 5340 (if approved) Nivetti Systems Intended status: Standards Track May 9, 2016 Expires: November 10, 2016 OSPF LSA sequence number generation draft-manjuldtv-ospf-sequence-number-00 Abstract The mechanism for LS sequence number generation as specified in RFC 2328 and RFC 5340 is completely predictable. This makes it prone to certain security attacks which exploit the predictable nature of LS sequence numbers. This draft updates the RFC 2328 to make LS sequence number generation an implementation choice rather than a fixed increment by 1 for successive LSAs. Status of This Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at http://datatracker.ietf.org/drafts/current/. 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." This Internet-Draft will expire on November 10, 2016. Copyright Notice Copyright (c) 2016 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of Khandelwal & Desetti Expires November 10, 2016 [Page 1] Internet-Draft OSPF LSA sequence number generation May 2016 the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1. Requirements Language . . . . . . . . . . . . . . . . . . 3 2. LS sequence number generation . . . . . . . . . . . . . . . . 3 2.1. Updates to RFC 2328 . . . . . . . . . . . . . . . . . . . 4 2.2. Updates to RFC 5340 . . . . . . . . . . . . . . . . . . . 7 3. Backward Compatibility . . . . . . . . . . . . . . . . . . . 7 4. Implementation Advice . . . . . . . . . . . . . . . . . . . . 8 5. Security Considerations . . . . . . . . . . . . . . . . . . . 9 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 9 7. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 9 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 9 8.1. Normative References . . . . . . . . . . . . . . . . . . 9 8.2. Informative References . . . . . . . . . . . . . . . . . 10 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 10 1. Introduction In OSPF protocol (see RFC 2328 [RFC2328]), an LSA is identified by {LS type, Link State ID, and Advertising Router}. Multiple instances of the LSA may exist in the routing domain at the same time. A specific LSA instance is characterized by {LS age, LS sequence number and LS checksum}. All these fields are contained in the LSA header. LS sequence number together with LS age and LS checksum are used in finding the recent LSA when multiple instances exist. As per RFC 2328 [RFC2328], successive instances of an LSA are given successive LS sequence numbers. The mechanism for LS sequence number generation as specified in RFC 2328 makes it completely predictable. This is prone to certain security attacks which exploit the predictable nature of LS sequence numbers. Incrementing LS sequence numbers by 1 for successive LSAs is not actually required for the OSPF protocol to function. This draft makes LS sequence number generation an implementation choice rather than a fixed increment by 1 for successive LSAs. This update is backward compatible. Khandelwal & Desetti Expires November 10, 2016 [Page 2] Internet-Draft OSPF LSA sequence number generation May 2016 1.1. Requirements Language 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. LS sequence number generation This document updates RFC 2328 with regard to LS sequence number generation. After first providing general comments on updated LS sequence number generation, specific updates to RFC 2328 are detailed. A OSPF router generates LS sequence number under various conditions: o When a router initially comes up and creates LSAs for the first time. o When it is updating an existing LSA (because of changes in the contents or age has reached LSRefreshTime). o Receives a self-originated LSA which is newer than than the last instance that the router actually originated. In all these cases, the LS sequence number generated is an implementation dependent matter except for the following conditions: o It MUST be different from previous LS sequence number, if one exists. o It MUST NOT be 0x80000000. If a previous sequence number exists, the new LS sequence number can be higher or lower than the previous sequence number. If the new LS sequence number is higher than the previous sequence number then it can be used directly. If the new sequence number is lower than the previous sequence number, then special considerations apply. OSPF design does not allow directly using a new sequence number which is lower than the previous sequence number. Wrap-around of sequence numbers is required. This is done by prematurely aging the LSA by generating a new LSA with LS sequence number as MaxSequenceNumber and age as the MaxAge and flooding it. As soon as this flood has been acknowledged by all adjacent neighbors, then LSA with the new sequence number should be generated. Implementors should be aware that this process is likely to delay generation of new LSA. Khandelwal & Desetti Expires November 10, 2016 [Page 3] Internet-Draft OSPF LSA sequence number generation May 2016 2.1. Updates to RFC 2328 In the rest of this section, specific changes to specific sections of RFC 2328 are detailed. In each case, old text and updated text are provided. 1. Section 12.1.6 The sequence number -N (0x80000000) is reserved (and unused). This leaves -N + 1 (0x80000001) as the smallest (and therefore oldest) sequence number; this sequence number is referred to as the constant InitialSequenceNumber. A router uses InitialSequenceNumber the first time it originates any LSA. Afterwards, the LSA's sequence number is incremented each time the router originates a new instance of the LSA. When an attempt is made to increment the sequence number past the maximum value of N - 1 (0x7fffffff; also referred to as MaxSequenceNumber), the current instance of the LSA must first be flushed from the routing domain. This is done by prematurely aging the LSA (see Section 14.1) and reflooding it. As soon as this flood has been acknowledged by all adjacent neighbors, a new instance can be originated with sequence number of InitialSequenceNumber. updated to The sequence number -N (0x80000000) is reserved (and unused). This leaves -N + 1 (0x80000001) as the smallest sequence number; this sequence number is referred to as the constant InitialSequenceNumber. Largest sequence number will be N - 1 (0x7fffffff; also referred to as the constant MaxSequenceNumber). A router originating LSA for the first time can use any sequence number between InitialSequenceNumber and the maximum value of MaxSequenceNumber (both values included). Afterwards, each time the router originates a new instance of the LSA, it will select a new LS sequence number (which is different from previous sequence number and 0x80000000). If the new LS sequence number is higher than the previous sequence number then it can be originated directly by setting LS sequence number to new LS sequence number. If the new sequence number is lower than the previous sequence number, then special considerations apply. Wrap-around of sequence numbers is required. This is done by prematurely aging the LSA by generating a new LSA with LS sequence number as MaxSequenceNumber and age as the MaxAge and flooding it. As soon as this flood has been acknowledged by all adjacent neighbors, a new LSA instance can be originated with sequence number as the new sequence number. Same approach is followed Khandelwal & Desetti Expires November 10, 2016 [Page 4] Internet-Draft OSPF LSA sequence number generation May 2016 when an attempt is made to select a new sequence number when the previous sequence number is MaxSequenceNumber. 2. Section 12.4 Whenever a new instance of an LSA is originated, its LS sequence number is incremented, its LS age is set to 0, its LS checksum is calculated, and the LSA is added to the link state database and flooded out the appropriate interfaces. See Section 13.2 for details concerning the installation of the LSA into the link state database. See Section 13.3 for details concerning the flooding of newly originated LSAs. updated to Whenever a new instance of an LSA is to be originated, a new LS sequence number is selected (which is different from previous sequence number and 0x80000000). If the new LS sequence number is higher than the previous sequence number then it can be originated directly by setting LS sequence number to new sequence number, its LS age is set to 0, its LS checksum is calculated, and the LSA is added to the link state database and flooded out the appropriate interfaces. If the new sequence number is lower than the previous sequence number, then special considerations apply. Wrap-around of sequence numbers is required. This is done by prematurely aging the LSA by generating a new LSA with LS sequence number as MaxSequenceNumber and age as the MaxAge and flooding it. As soon as this flood has been acknowledged by all adjacent neighbors, then an LSA with the new sequence number can be generated by setting LS sequence number to new sequence number, its LS age is set to 0, its LS checksum is calculated, and the LSA is added to the link state database and flooded out the appropriate interfaces. See Section 13.2 for details concerning the installation of the LSA into the link state database. See Section 13.3 for details concerning the flooding of newly originated LSAs. 3. Section 13.4 However, if the received self-originated LSA is newer than the last instance that the router actually originated, the router must take special action. The reception of such an LSA indicates that there are LSAs in the routing domain that were originated by the router before the last time it was restarted. In most cases, the router must then advance the LSA's LS sequence number one past the received LS sequence number, and originate a new instance of the LSA. Khandelwal & Desetti Expires November 10, 2016 [Page 5] Internet-Draft OSPF LSA sequence number generation May 2016 updated to However, if the received self-originated LSA is newer than the last instance that the router actually originated, the router must take special action. The reception of such an LSA indicates that there are LSAs in the routing domain that were originated by the router before the last time it was restarted. In most cases, the router must then obtain a new sequence number (which is different from previous sequence number and 0x80000000) , and originate a new instance of the LSA. If the new LS sequence number is higher than the previous sequence number then it can be originated directly. If the new sequence number is lower than the previous sequence number, then special considerations apply. Wrap-around of sequence numbers is required. This is done by prematurely aging the LSA by generating a new LSA with LS sequence number as MaxSequenceNumber and age as the MaxAge and flooding it. As soon as this flood has been acknowledged by all adjacent neighbors, then an LSA with the new sequence number can be generated. 4. Section 14.1 Premature aging is used when it is time for a self-originated LSA's sequence number field to wrap. At this point, the current LSA instance (having LS sequence number MaxSequenceNumber) must be prematurely aged and flushed from the routing domain before a new instance with sequence number equal to InitialSequenceNumber can be originated. See Section 12.1.6 for more information. updated to Premature aging is used when it is time for a self-originated LSA's sequence number field to wrap. At this point, the current LSA instance must be prematurely aged and flushed from the routing domain before a new instance with a new sequence number can be originated. See Section 12.1.6 for more information. 5. Appendix A.4.1 LS sequence number Detects old or duplicate LSAs. Successive instances of an LSA are given successive LS sequence numbers. See Section 12.1.6 for more details. Khandelwal & Desetti Expires November 10, 2016 [Page 6] Internet-Draft OSPF LSA sequence number generation May 2016 updated to LS sequence number Detects old or duplicate LSAs. See Section 12.1.6 for more details. 6. Appendix B InitialSequenceNumber The value used for LS Sequence Number when originating the first instance of any LSA. Its value is the signed 32-bit integer 0x80000001. updated to InitialSequenceNumber The minimum value in LS Sequence Number space. Its value is the signed 32-bit integer 0x80000001. 2.2. Updates to RFC 5340 RFC 5340 [RFC5340] inherits LS sequence number generation algorithms from RFC 2328. The proposed changes to RFC 2328 in this document apply to RFC 5340 as well. 3. Backward Compatibility Multiple instances of an LSA may exist in the routing domain at the same time. Given two instances, it is then necessary to determine whether they are duplicates, if not, which instance is more recent. This is accomplished by examining the LS age, LS sequence number and LS checksum fields that are also contained in the LSA header. The actual algorithm for this determination is presented in Section 13.1 of RFC 2328. These are the uses of LS sequence number field. In any of these use cases, there is no dependence on the fact that successive LSA instances should have successive LS sequence numbers. Hence relaxing the LS sequence number generation as proposed in this document should have no backward compatibility issues. Any existing implementation which is based on RFC 2328 in which successive LSAs have successive LS sequence numbers inter-operates with an implementation which is based on this document. Khandelwal & Desetti Expires November 10, 2016 [Page 7] Internet-Draft OSPF LSA sequence number generation May 2016 RFC 5340 (OSPF for IPv6) inherits LS sequence number generation algorithms from RFC 2328. Backward compatibility is applicable to RFC 5340 as well. 4. Implementation Advice Note: This section is not normative. The existing LS sequence number generation proposed in the RFC 2328 makes it completely predictable. This makes it prone to certain security attacks which exploits the predictability of LS sequence numbers. An example of such an attack is described in the paper [Persistent]. We briefly describe the attack. Interested readers may refer the paper for more details. The paper refers to the attack as "Disguised LSA" and is of persistent nature. This attack is launched from a compromised router inside a routing domain. In this attack, the compromised router alters the LSA of an uncompromised router (victim). Normally, such an attempt does not have persistence because the victim generates a new LSA when it sees such self-originated LSAs (referred to as "fight-back" mechanism in the paper). But the paper makes disguised LSA persistent because all the fields { LS sequence number, checksum} are predictable. It alters the existing LSA of victim to suit its needs but sets the sequence number to +1 of the existing LSA and alters the LSA so that checksum matches with checksum that would be generated by the victim when it generates the new LSA. When this disguised LSA reaches the victim, it does not fight back because it compares only the fields { LS sequence number, checksum, age} to check for duplicates and not the actual content of LSA. This attack enables an insider attacker to fully control the entire content of an LSA. We think this attack is powerful. We propose the following approach to mitigate this attack. The attack depends on the predictability of sequence numbers used by a router. If a router randomizes the next sequence number, then the attack loses its power -- persistence. Note, however, that completely random sequence numbers is not acceptable -- OSPF has an ordering of sequence numbers. RFC 2328 suggests that next sequence number is +1 of previous sequence number. But if have an implementation where next sequence number is a random number in the range, say, [prev_sequence_number+1 ... prev_sequence_number+100], then the attack will have very low probability of success. Khandelwal & Desetti Expires November 10, 2016 [Page 8] Internet-Draft OSPF LSA sequence number generation May 2016 5. Security Considerations The primary motivation for this document is to mitigate a security vulnerability associated with RFC 2328. The security vulnerability is described in Section 4. A suggested solution is also provided in Section 4 to mitigate the reported attack. The only update proposed by this document to RFC 2328 is to make LS sequence number generation an implementation dependent choice. It is expected that flexibility in LS sequence number generation provides the implementations the opportunity to fix the security attacks associated with the current predictable sequence number generation strategy. Hence, implementations need to be aware of the security implications of the specific design decisions they make with regard to their LS sequence number generation strategies. 6. IANA Considerations There are no IANA considerations. 7. Acknowledgments Thanks to Manish Bajpai and Prof. Sandeep Shukla for their useful inputs. Thanks to Dr. Gabi Nakibly for his comments on the implementation advice. 8. References 8.1. Normative References [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, . [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, DOI 10.17487/RFC2328, April 1998, . [RFC5340] Coltun, R., Ferguson, D., Moy, J., and A. Lindem, "OSPF for IPv6", RFC 5340, DOI 10.17487/RFC5340, July 2008, . Khandelwal & Desetti Expires November 10, 2016 [Page 9] Internet-Draft OSPF LSA sequence number generation May 2016 8.2. Informative References [Persistent] Nakibly, G., Kirshon, A., Gonikman, D., and D. Boneh, "Persistent OSPF attacks", NDSS , 2012. Authors' Addresses Manjul Khandelwal Nivetti Systems Pvt. Ltd. Bengaluru India Phone: +91 9886192675 Email: manjul@nivettisystems.com Ramakrishna Rao TV Desetti Nivetti Systems Pvt. Ltd. Bengaluru India Phone: +91 9845554451 Email: ramakrishnadtv@nivettisystems.com Khandelwal & Desetti Expires November 10, 2016 [Page 10]