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]
