Internet DRAFT - draft-manjuldtv-ospf-sequence-number

draft-manjuldtv-ospf-sequence-number







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,
              <http://www.rfc-editor.org/info/rfc2119>.

   [RFC2328]  Moy, J., "OSPF Version 2", STD 54, RFC 2328,
              DOI 10.17487/RFC2328, April 1998,
              <http://www.rfc-editor.org/info/rfc2328>.

   [RFC5340]  Coltun, R., Ferguson, D., Moy, J., and A. Lindem, "OSPF
              for IPv6", RFC 5340, DOI 10.17487/RFC5340, July 2008,
              <http://www.rfc-editor.org/info/rfc5340>.







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]