Internet DRAFT - draft-etienne-ospfv2-auth-flaws
draft-etienne-ospfv2-auth-flaws
Network Working Group J. Etienne
Internet-Draft May 9, 2001
Expires: November 7, 2001
Flaws in packet's authentication of OSPFv2
draft-etienne-ospfv2-auth-flaws-00.txt
Status of this Memo
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026.
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 November 7, 2001.
Copyright Notice
Copyright (C) The Internet Society (2001). All Rights Reserved.
Abstract
OSPF is the Interior Gateway Protocol currently supported by the IETF
and is widely deployed across the internet. The current strongest
authentication method for OSPFv2 is the cryptographic authentication
(RFC2328.D [4]) which uses shared secret key to authenticate the
packets. This memo explains the different security flaws we found in
the anti-replay and the MACs calculation. The second part presents
practical exploitations of these weaknesses: an attacker directly
connected to a link, can (i) replay LSAs, (ii) break neighborhood
and (iii) flap routes.
Etienne Expires November 7, 2001 [Page 1]
Internet-Draft OSPFv2 authentication flaws May 2001
Table of Contents
1. Attacker model . . . . . . . . . . . . . . . . . . . . . . . 3
2. Current Authentications . . . . . . . . . . . . . . . . . . 3
2.1 Description . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 anti-replay protection . . . . . . . . . . . . . . . . . . . 4
2.3 a timestamp as sequence number . . . . . . . . . . . . . . . 4
2.4 a counter as sequence number . . . . . . . . . . . . . . . . 5
2.5 MAC calculation . . . . . . . . . . . . . . . . . . . . . . 5
2.5.1 secret-suffix method . . . . . . . . . . . . . . . . . . . . 5
2.5.2 Unprotected IP header . . . . . . . . . . . . . . . . . . . 5
2.5.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3. Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.1 LSA replay . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.2 breaking neighborhood . . . . . . . . . . . . . . . . . . . 6
3.2.1 Higher sequence attack . . . . . . . . . . . . . . . . . . . 6
3.2.2 Hello replay back attack . . . . . . . . . . . . . . . . . . 7
3.2.3 Type of network . . . . . . . . . . . . . . . . . . . . . . 7
3.3 Route flapping . . . . . . . . . . . . . . . . . . . . . . . 7
3.3.1 Consequences . . . . . . . . . . . . . . . . . . . . . . . . 8
3.3.2 Timer issues . . . . . . . . . . . . . . . . . . . . . . . . 8
4. Security considerations . . . . . . . . . . . . . . . . . . 8
References . . . . . . . . . . . . . . . . . . . . . . . . . 9
Author's Address . . . . . . . . . . . . . . . . . . . . . . 9
Full Copyright Statement . . . . . . . . . . . . . . . . . . 10
Etienne Expires November 7, 2001 [Page 2]
Internet-Draft OSPFv2 authentication flaws May 2001
1. Attacker model
In this memo, we assume the attacker can read and write packets on
the network. He hasn't the secret key and he is unable to produce a
valid MAC without it.
If the attacker knows the secret key of any link, he becomes an
insider and the security of the whole OSPF domain is compromised. He
would be able to modify the LSAs database to perform various
efficient attacks (e.g. to make a given network unreachable, reroute
packets to perform man-in-the-middle attack or traffic analysis).
Resisting to insider's attacks requires deep modifications of the
protocol and it is outside the scope of this memo.
2. Current Authentications
The OSPFv2's authentication (RFC2328.D [4]) is configured on a per-
interface basis. Each router connected to a given link shares the
same parameters (i.e. key value, key lifetime and authentication
algorithm). OSPFv2 has 3 authentications methods:
1. The "NULL authentication" provides no security.
2. The "Simple password authentication" uses a password sent in
clear on the network. If the attacker can read the packets, he
has the password and can freely forge packets.
3. The "Cryptographic authentication" (RFC2328.D.3 [4]) which uses a
shared secret key to include a MAC in each packet.
Because the NULL and the simple password authentication are already
known to be weak, we focus on the cryptographic authentication.
2.1 Description
The cryptographic authentication provides a secure way to
authenticate the packet and some protections against packet's replay.
The packets are signed with a Message Authentication Code (MAC)
calculated with the secret suffix method using MD5 (RFC1321 [2]).
The result is obtained by applying MD5 over the OSPF payload (IP
header not included) and, then, the secret key : MAC = MD5( OSPF
paylaod | secret key ). An external node can't generate a valid MAC
because we assume it ignores the secret key and it is believed to be
infeasible to recompute the key from the MAC and the OSPF packet.
The anti-replay is handled by a sequence number set in sent packets
and verified during packet reception. (WORK: ref) The sequence
number must be non-decreasing and may be a counter, number of seconds
Etienne Expires November 7, 2001 [Page 3]
Internet-Draft OSPFv2 authentication flaws May 2001
since reboot or since 1960. A received packet is accepted only if
its sequence number is greater or equal to the last one received from
the same source.
In brief, when a router sends a packet, it sets the sequence number,
then computes the MAC and appends it to the OSPF packet. When a
router receives a packet, it is accepted only if the MAC and the
sequence number are valid. Unfortunately, the cryptographic
authentication has known flaws in the anti-replay, the MAC algorithm
and we found new ones in the MAC coverage.
2.2 anti-replay protection
The following features of the cryptographic authentication allow a
packet to be replayed:
1. A received packet is accepted if its sequence number is greater
than or equal to the previous one (RFC2328.D.5.3.(2) [4]). So a
packet can be replayed just after itself.
2. The sequence numbers are reused after a boot or a roll over
(RFC2328.D.5.p3 [4]). So packets can be replayed after a reboot.
3. The keying is static and the sequence numbers aren't stored in a
non-volatile memory. When a router goes off-line, its neighbors
forget its sequence numbers and an attacker can replay its
packets.
Each reason is independently sufficient to permit a packet's replay.
The sequence number is the base of the anti-replay mechanism, so we
present the different possibilities offered by the cryptographic
authentication.
2.3 a timestamp as sequence number
Using a timestamp as sequence number is often a bad idea: it forces
one to either accept several successive packets with the same
sequence numbers or to assume that no more than one packet is sent
during a clock period. It would unnecessarily create a dependency
between the clock frequency and the network throughput. OSPF has
chosen the former and expects the implementors to use the number of
seconds since reboot or since 1960 (RFC2328.D.3 [4]). This likely
causes the greater than or equal to vulnerability.
Using the seconds since 1960 will avoid to roll over until 2096 but
it is possible to successfully replay a packet multiple times until
the destination accepts a higher sequence number. This delay can be
up to 10 seconds (default hello interval) and more in case of packet
Etienne Expires November 7, 2001 [Page 4]
Internet-Draft OSPFv2 authentication flaws May 2001
loss. Using the seconds since reboot doesn't solve the previous
vulnerability and adds a new one because sequences numbers are reused
after each reboot.
2.4 a counter as sequence number
With a timestamp, if a receiver accepts 2 packets sent within the
same time slice (e.g. pkt1 then pkt2), an attacker can still replay
the first one (pkt1). Using a packet counter makes this impossible.
Nevertheless the last packet (pkt2) can still be replayed.
A packet counter will likely be reused across reboot. Further a
large router may send 2^32 OSPF packets during its lifetime and the
sequence number would roll over. So a packet counter still has
flaws.
2.5 MAC calculation
The MAC calculation of the cryptographic authentication has two
problems: it uses the secret-suffix method which is known to be weak
and applies it only on the OSPF payload, leaving the IP header
unprotected.
2.5.1 secret-suffix method
[7] considers the secret-suffix method possibly weak. [6] and [5]
explains that an attacker may search for MD5( OSPF packet )
collisions, and then use them for any key. This search is efficient
because it can be parallelized and done off-line. Nevertheless, this
weakness is theoretical and unlikely to be turned into an practical
attack.
2.5.2 Unprotected IP header
The IP header (RFC0791.3.1 [1]) isn't covered by the MAC so a
modification would not be detected. If the protocol relies on its
fields, it may be the base of an attack. We focus on the fields that
may influence OSPF and not prevent the packet from reaching the OSPF
layer (i.e. pass the IP layer). The matching fields are:
o The total length is the length of the whole ip packet. To make it
larger is useless because OSPF uses its own length field included
the packet header (RFC2328.A.3.1 [4]) so unforgeable. To make it
smaller will cause the authentication to fail. We think it can't
be used in an attack.
o The source address indicates the origin of the packet and is used
by OSPF to know which neighbor sent the packet (RFC2328.8.2 [4])
Etienne Expires November 7, 2001 [Page 5]
Internet-Draft OSPFv2 authentication flaws May 2001
on broadcast, point-to-multipoint, NBMA networks.
o The destination address indicates the destination of the packet.
The IP layer uses it to accept or reject the packets.
2.5.3 Summary
In brief, a packet can be replayed and, on broadcast Point-to-
MultiPoint or NBMA network, it can be done between hosts which aren't
necessarily the original ones.
3. Attacks
Combining the exposed weaknesses, it is possible to perform efficient
attacks. In this section, we describe three of them: (i) how to
replay a LSA, (ii) a Denial Of Service(DoS) able to disconnect a
router from a link, and (iii) how to flap a route to consume CPU and
network bandwidth.
3.1 LSA replay
LSAs are flooded by using LinkStateUpdate packets (RFC2328.A.3.5 [4])
so to replay an LSA, an attacker must first defeat the packet's anti-
replay. Moreover, the LSA must be considered newer than the current
one (RFC2328.13.1 [4]). It is mostly determined from the LSA
sequence number (RFC2328.12.6.1 [4]) which is a counter reused across
reboot.
Nevertheless, when the original router receives the replayed LSA
(RFC2328.13.4 [4]), it will flood the real LSA with a even higher
sequence number again. In this case, the DoS doesn't last long. If
the original router never receives the replayed LSA (e.g. it is off
or the packet has been replayed on each link connecting it to other
routers), the DoS will last at most 1 hour, i.e. until the LSA is
refreshed by the original router, or expires in each router.
3.2 breaking neighborhood
The router's neighborhood is the base of the inter-router
communication in OSPF. We present 2 attacks able to break it using
packet replay and ip address spoofing and how to use them on
different types of links.
3.2.1 Higher sequence attack
In this attack, an attacker destroys the neighborhood by successfully
replaying a packet with a sequence number greater than the ones from
Etienne Expires November 7, 2001 [Page 6]
Internet-Draft OSPFv2 authentication flaws May 2001
the real source, so the destination ignores the real packets until
they reach a higher sequence number. If no HELLO packet is accepted
by the destination during RouterDeadInterval seconds (default value:
40 RFC2328.9 [4]), the neighborhood is broken and the router is
declared dead. This attack has limits on the sequence numbers but
works even if the neighbor isn't identified by its ip address.
3.2.2 Hello replay back attack
The HELLO packet lists the recently seen routers, so if an attacker
replays a HELLO packet back to its source, the source won't see
itself in the list and will deduce the connection isn't
bidirectional. The source will set the neighbor's state to 'Init'
(RFC2328.10.3 [4]) preventing any adjacency.
This attack requires the neighbor to be identified by its ip address
but it is independent of the sequence numbers. If two routers on a
neighborhood don't have the same sequence numbers, it is possible to
replay HELLO packet back to the router with the highest ones. If
they have the exact same values, it is possible because of the
greater or equal weakness.
If the sequence numbers are far enough apart, this attack is similar
to the higher sequence one and the neighborhood is broken. If they
are too close, e.g. all routers use seconds since reboot and have
rebooted at the same time or use seconds since 1960 and have a
synchronized clock, the neighborhood still exists but will be
considered unidirectional until the real packets reach a higher
sequence number i.e. in the next RouterDeadInterval seconds.
3.2.3 Type of network
On broadcast, NBMA or Point to MultiPoint networks, the neighbor is
identified by its ip address, so both attacks can be used. On a
point-to-point network or a virtual link, the neighbor is identified
by its RouterID (RFC2328.1.2 [4]) so the hello replay back attack is
non applicable. The higher-sequence attack can be applied if the
source router reuses sequence numbers across reboot, the attacker
logs the packets and waits for the router to reboot, then replays
them. If the source uses seconds since 1960, this attack can't break
the neighborhood on this type of link.
3.3 Route flapping
When a router is declared no longer adjacent (i.e. dead or with a
non-bidirectional communication), a new LSA is originated to express
this topology change. It is flooded throughout the area. Depending
on the route aggregation configuration, it may be converted into a
Etienne Expires November 7, 2001 [Page 7]
Internet-Draft OSPFv2 authentication flaws May 2001
summary-LSA and flooded in the whole autonomous system (AS).
Further, it may be exported in other autonomous systems.
With both attacks, the real packets are accepted again after
RouterDeadInterval, the router is redeclared alive, and another LSA
is originated. The attacker may attack again and so on... So an
attacker can flap a route.
3.3.1 Consequences
Each new LSA consumes network because it is flooded, and CPU because
it triggers a route recalculation. Inside the area of the attack,
all the routers will recompute a complete Shortest Path Tree
(RFC2328.16.1 [4]); an expensive operation\footnote{The calculation
uses the Dijkstra's algorithm. Its complexity is $O(l*log(n))$ with
l links and n nodes}. Outside this area, if the LSA is flooded as a
Summary LSA, the routers will recompute a route from it (RFC2328.16.5
[4]); a less expensive operation, but done by all the routers of the
AS. Outside the AS, the cost of this attack will depend on the
protocols used. For example, if the route is exported with BGP, it
will likely dampen the route (RFC1771.apx.6 [3]).
3.3.2 Timer issues
The delay between the neighborhood fall and its re-establishment may
be short. If two instances of a LSA arrives in less than
MinLSArrival (default value: 1sec RFC2328.B [4]), the second one is
discarded and the attack is stopped. Nevertheless, a OSPF router
isn't allowed to renew a LSA more than once per MinLSInterval
(default value: 5sec RFC2328.B [4]). If it has to, the second LSA is
delayed. So the LSA will likely not be discarded because of
MinLSArrival.
An attacker may attack numerous links, forcing all routers to
recompute routes over and over. Cisco implements a feature, 'set
timer spf' (default value: 5sec), which delays the SPF calculation
when the router receives a new LSA. It efficiently bounds the
effects of this attack but it is based on a non-standard feature.
4. Security considerations
This memo presents weaknesses in the current strongest method of
authentication. The cryptographic authentication anti-replay was
known to be weak but its flaws were believed harmless. We found a
new flaw in the MAC calculation which allows an attacker to fake the
source and destination IP addresses. Combined, these weaknesses
allow efficient DoS and the injection of obsolete routes. We present
some of the attacks but we strongly there are others as well.
Etienne Expires November 7, 2001 [Page 8]
Internet-Draft OSPFv2 authentication flaws May 2001
We have designed the "anti-replay authentication" (WORK: ref) that
fixes these flaws, without, to the best of our knowledge, adding new
ones. This method isn't described in this draft, because it isn't
yet fully specified in the OSPF context. The MAC covers the IP
header preventing an attacker from forging it. This method provides
a new way to handle anti-replay with static key which is safe across
reset. Keeping the core structure of the cryptographic
authentication, it can be easily plugged in an existing
implementation so we think it may be a good replacement of the
cryptographic authentication.
References
[1] Postel, J., "Internet Protocol", STD 5, RFC 791, Sep 1981.
[2] Rivest, R., "The MD5 Message-Digest Algorithm", RFC 1321, April
1992.
[3] Rekhter, Y. and T. Li, "A Border Gateway Protocol 4 (BGP-4)",
RFC 1771, March 1995.
[4] Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998.
[5] Bellare, M., Canetti, R. and H. Crawczyk, "Keying hash function
for Message Authentication", Advances in cryptology Crypto 96
vol 1109, 1996.
[6] Preneel, B. and P. Van Oorshot, "MDX-MAC and building fast MACs
from hash functions", Advances in cryptology Crypto 96 , 1995.
[7] Kaliski, B. and M. Robshaw, "Message authentication with MD5",
Cryptobyte Vol1 no1, 1995.
Author's Address
Jerome Etienne
EMail: jme@off.net
URI: http://www.off.net/~jme
Etienne Expires November 7, 2001 [Page 9]
Internet-Draft OSPFv2 authentication flaws May 2001
Full Copyright Statement
Copyright (C) The Internet Society (2001). All Rights Reserved.
This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain it
or assist in its implementation may be prepared, copied, published
and distributed, in whole or in part, without restriction of any
kind, provided that the above copyright notice and this paragraph are
included on all such copies and derivative works. However, this
document itself may not be modified in any way, such as by removing
the copyright notice or references to the Internet Society or other
Internet organizations, except as needed for the purpose of
developing Internet standards in which case the procedures for
copyrights defined in the Internet Standards process must be
followed, or as required to translate it into languages other than
English.
The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on an
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
TASK FORCE DISCLAIMS 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.
Acknowledgement
Funding for the RFC Editor function is currently provided by the
Internet Society.
Etienne Expires November 7, 2001 [Page 10]
