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]