GLOBAL INTERNET ROUTING FORENSICS: VALIDATION OF BGP PATHS USING ICMP TRACEBACK: GLOBAL INTERNET ROUTING FORENSICS: VALIDATION OF BGP PATHS USING ICMP TRACEBACK Eunjong Kim, Dan Massey and Indrajit Ray Department of Computer Science Colorado State University {kimeu, massey, indrajit}@cs.colostate.edu 2005 digital forensics


Outline: Outline 1. Introduction 2. BGP and its vulnerabilities 3. Cryptographic approaches 4. Enhanced BGP iTrace 5. Summary and conclusion


1. Introduction: 1. Introduction The Internet plays an important role a variety of end system security techniques encrypted connections and VPNs But the unsecured Internet infrastructure the Internet consists of thousands of Autonomous Systems (AS). The Border Gateway Protocol (BGP) [12] is the inter-AS routing protocol to cope with events new links and new ASes, the failure of links changes in routing polices. [12] Y. Rekhter and T. Li. Border Gateway Protocol 4. RFC 1771, July 1995.


Slide4: AS1 AS6 AS8 AS7 AS3 131.179.96.130 (UCLA) 129.82.100.64 (CSU Web server) origin BGP presents interesting challenges path validation routing forensics


Slide5: any particular BGP path change no any alarms at remote sites. to cause significant damage to the affected site. In this paper for detecting invalid routes and present an approach for gathering and extracting routing data which can be used later on for forensic analysis.


2. BGP and its vulnerabilities: 2. BGP and its vulnerabilities BGP is a path vector routing algorithm each router advertises its best route to a destination does not learn the full Internet topology only a best path to each destination. Based on the partial topology information, it is hard to confirm the validity of a particular path and tend to accept any path that is advertised. This leads to the following possible exploits: misconfiguration deliberate attacks


2.1. MISCONFIGURATION: 2.1. MISCONFIGURATION Mahajan et al define two types of BGP misconfiguration in [10]. origin misconfiguration the accidental injection of routes into global BGP tables announcing part of someone else’s address space (hijacks) and propagating private network prefixes. export misconfiguration in violation of an ISP’s policy. Misconfigurations increase routing load by generating unnecessary BGP updates. The incorrect announcement can disrupt connectivity either partially or globally. [10] R. Mahajan, D. Wetherall, and T. Anderson. Understanding BGP misconfiguration. In ACM SIGCOMM 2002, August 2002.


2.2. DELIBERATE ATTACKS: 2.2. DELIBERATE ATTACKS Two main attacks in the network falsification and denial-of-service (DoS). A falsification is defined as a bogus BGP protocol message [18]. falsify withdrawn routes, path attributes and network layer reachability information (NLRL) components of theUPDATE message. the blackhole attack a malicious AS injects wrong routing information to attract traffic, thus gaining control of a path. can be prevented by using IPsec and proper certificates. [18] Y.C. Hu, A. Perrig and M. Sirbu. SPV: Secure Path Vector Routing for Secure BGP. In ACM SIGCOMM Computer Communication Review, pages 179–192, October 2004.


Slide9: Denial-of-service(DoS) is an AS may accidentally filter out routes it otherwise announces An attacker may be able to make a router perform resource-intensive operations such as public-key certification verification or signature generations make the router slow down.


3. Related work: 3. Related work Perlman examined Byzantine behavior within routing protocols in her dissertation [11] and was among the first to consider routing security. In [4], Pei et al. review the various approaches to improving the resiliency of the Internet routing protocols. We categorize the previous works into two classes Cryptographic based approaches Non cryptographic based approaches. [11] R. Perlman. Network layer protocols with Byzantine roubustness. PhD thesis, MIT Lab. for Computer Science, 1988. [4] D. Pei, D. Massey and L.Zhang. A Framework for Resilient Internet Routing Protocol. IEEE Network, 18(2):5–12, April 2004.


3.1. CRYPTOGRAPHIC APPROACHES: 3.1. CRYPTOGRAPHIC APPROACHES Secure BGP (S-BGP): [14] protects the entire BGP UPDATE message by adding PKI to authorize prefix ownership and validate routes, a new attribute ensure the authorization of routing UPDATE and prevents route modification of intermediate BGP speakers, IPSec to provide routing message confidentiality. Secure Origin BGP (soBGP): [8]. verifies the origin of route advertisements and prevents the advertisement of unauthorized prefixes All information security is handled by three type of certificates. The Entity Certificate binds a node or router in the network to a public key. Authorization Certificates used to verify an AS Policy Certificates [14] S. Kent, C. Lynn, and K. Seo. Secure border gateway protocol (S-BGP). IEEE JSAC Special Issue on Network Security, 2000. [8] J. Ng. Extension to BGP to Support Secure Origin BGP, October 2002.


Slide12: SecurePathVector (SPV):[18] improves on S-BGP symmetric cryptography for security cryptographic hash function to provide very good performance. [18] Y.C. Hu, A. Perrig and M. Sirbu. SPV: Secure Path Vector Routing for Secure BGP. In ACM SIGCOMM Computer Communication Review, pages 179–192, October 2004.


3.2. NON CRYPTOGRAPHIC APPROACHES: 3.2. NON CRYPTOGRAPHIC APPROACHES Non-cryptographic based solutions provide fewer guarantees, but can be deployed more readily Multiple origin AS (MOAS): announce themselves as the origin of a prefix. occurs for various reasons misconfiguration, multihoming, or malicious attacks [16]. Zhao et al. use the BGP community attribute for a list of the valid originating ASes [17]. [16] X. Zhao, D. Pei, L. Wag, D. Massey, A. Mankin, S. F. Wu, and L. Zhang. An analysis of BGP multiple origin AS (MOAS) conflicts. In SIGCOMM Internet Measurement Workshop, November 2001. [17] X. Zhao, D. Pei, L. Wag, D. Massey, A. Mankin, S. F. Wu, and L. Zhang. Detection of Invalid Routing Announements in the Internet. In International Conference on Network and Distributed Systems (DSN), June 2002.


Slide14: RouteFiltering: With proper filters, bad routes will be stopped from propagating near or at its source Wang et al. proposed path filtering approach for protecting BGP routes to the top level DNS servers [7]. Interdomain RoutingValidation (IRV): [5] recipients of BGP UPDATE messages to corroborate the received information. IRV is independent of the routing protocol and is used in conjunction with BGP. [5] G. Goodell,W. Aiello, T. Griffin, J. Ioannidis, P. McDaniel, and A. Rubin.Working around BGP:Anincremental approach to improving security and accuracy of interdomain routing. [7] L.Wang, X.Zhao, D. Pei, R. Bush, D. Massey, A. Mankin, S.F.Wu and L. Zhang. Protecting BGP Routes to Top Level DNS Server. IEEE Transactions on Paralle and Distributed Systems, 14(9):851–860, September 2003.


Slide15: Routing Path Verification: [3] Pei et al. developed an approach to detecting invalid routing announcement in Routing Information Protocol (RIP) uses probing message for invalid route verification. Source Tracing: [15] The key idea behind secure traceroute is to securely trace the path of existing traffic, to prevent adversaries from misleading the tracer Secure traceroute responses are also authenticated, to verify their origin and prevent spoofing or tampering. [3] D. Pei, D. Massey, and L. Zhang. Detection of Invalid Routing Announements in the RIP Protocol. In IEEE Global Communication conference (Globecom), December 2003. [15] V. N. Padmanabhan and D. R. Simon. Secure Tracerout to Detect Faulty or Malicious Routing. In ACM SIGCOMM Computer Communication Review, pages 77–82, 2003.


Slide16: ICMP Traceback (iTrace): [2] Defined to carry information on routes. used to deal with DOS attacks by verifying the source IP. When an IP packet passes through a router, iTrace is generated with a low probability of about 1/20000 and sent to the destination. Lee et al propose to use cumulative IP information to verify the true IP packet origin [6]. When a router receives a IP packet and forward it, it generates an iTrace message and appends its own IP address this iTrace message is sent to the next hop but to the destination. When a router receives an iTrace message, it appends its own IP address to the iTrace message. [2] Steven M. Bellovin. ICMP Traceback Messages. Internet Draft, March 2001. [6] Henry C.J.Lee, Vrizlynn L.L.Thing, Yi Xu, and Miao Ma. ICMP Traceback with Cumulative Path, An Efficient Solution for IP Traceback. In 5th International Conference on Information and Communications Security, October 2003.


4. Enhanced BGP iTrace: 4. Enhanced BGP iTrace We want to provide both path and origin validation use the advanced filtering technique with well-defined filtering rules and ICMP traceback. non cryptography-based protection techniques regarded ineffective but more deployable


4.1. AS-PATH verification with ICMP traceback messages: 4.1. AS-PATH verification with ICMP traceback messages Ideally, each router has to authenticate any route announcement and update message to detect false routing information before accepting it. is not properly applied current BGP protocol. Our approach uses ICMP Traceback (iTrace) message with a small modification for this purpose.


Slide19: When data packets traverse along the route, each router on the path generates iTrace messages. traced packet source and destination address, previous link, and the AS-PATH carried in an ICMP packet. Figure 1 presents the current traceback message format and Figure 2 shows the individual element structure. ICMP Traceback message body consists of a series of individual elements. More details are found in [2]. [2] Steven M. Bellovin. ICMP Traceback Messages. Internet Draft, March 2001


Slide21: AS1 AS9 AS6 AS8 AS7 AS10 AS11 AS2 AS3 AS5 AS4 131.179.96.130 (UCLA) 129.82.100.64 (CSU Web server) origin Arbitrary node No conflict, the valid path is AS8 AS7 AS6 AS1


Inconsistency triggers an alarm: Inconsistency triggers an alarm There are three different situations. The first one, AS-PATH is not directly connected to the destination. immediately sets a flag and sends an emergency message to a system operator. The second one, AS-PATH is not match any previous AS-PATH information. two possible way. a false origin or malicious router sends a wrong reachability information to its neighbors. Misconfiguration The third one, one router on the path announces a wrong AS-PATH information to make the AS-PATH is longer than the real one. a router misconfigures the path to reach the destination or intentionally injects a wrong reachability information.


Slide23: AS1 AS9 AS6 AS8 AS7 AS10 AS11 AS2 AS3 AS5 AS4 131.179.96.130 (UCLA) 129.82.100.64 (CSU Web server) origin AS13 False origin AS12 AS13 is not itself and AS12 is not the next hop, inconsistent, triggers an alarm With this iTrace message, the destination node not only verifies wrong AS-PATH but also detect and locate a false origin.


Slide24: AS1 AS6 AS2 AS3 AS5 AS4 131.179.96.130 (UCLA) 129.82.100.64 (CSU Web server) origin Nothing is inconsistent but the destination never gets iTrace message originated from AS7 or AS8. may be AS4 gets wrong reachability information from its neighbors or injects it by itself. Only based on this information, the reason can’t be determined but it knows AS-PATHs from both AS4 and AS5 may not be correct.


4.2. FILTERING: 4.2. FILTERING BGP is policy based protocol uses routing filtering to enforce various routing policies. But getting complete routing filters is very difficult needs to know all routing policies and relationship of ASes, and to view a global AS topology. we use the route filtering technique with both general policies and advance filtering mechanism for routers to help verify the validity of the route announcement for the security purpose.


Slide27: verifie all BGP UPDATE messages based on general policies, path history, MOAS conflict information, and ICMP traceback messages. verified new path be added into the BGP routing table and updated in the local database. General Policies: control the type of routes announced and accepted by a BGP peers. violate global guidelines that are published Statistical analysis over history: back-up paths, already verified kept in the local routing database and periodically updated and verified.


Slide28: MOAS conflict based verification: occur when multiple ASes announce themselves as the origin of a particular prefix. When a router receives the route announcements from the multiple origins, filters check each path and origin validity. Route validation process also checks the MOAS list the local routing database keeps. If the path or origin of the announcement is not valid, or if the origin is not in the MOAS list, filters reject the announcement. AS-PATH Validation with ICMP Traceback messages: explained in Section 4.1.


5. Summary and conclusion: 5. Summary and conclusion an integration of several existing partial solutions a more effective, efficient and concrete solution. The proposed approach verifies the UPDATE messages with well-defined filtering technique and filtering rules To provide efficient path validation mechanisms, use ICMP traceback message with small modification.


Slide30: The difference between our approach and other path validation approaches uses real data traffic to validate the correct path. We hope our work provides some improvement for BGP routing protocol with incremental deployability and scalability to adapt well to the real world.


Comments: Comments Good approach but didn’t show any experiments in this paper ICMP taceback Message is generated about the probability of 1/20,000, under the DOS attacks Can it work? How about the performance?