--- 1/draft-ietf-grow-route-leak-problem-definition-02.txt 2015-10-12 20:15:06.792130114 -0700 +++ 2/draft-ietf-grow-route-leak-problem-definition-03.txt 2015-10-12 20:15:06.824130898 -0700 @@ -1,23 +1,23 @@ Global Routing Operations K. Sriram Internet-Draft D. Montgomery Intended status: Informational US NIST -Expires: January 6, 2016 D. McPherson +Expires: April 14, 2016 D. McPherson E. Osterweil Verisign, Inc. B. Dickson Twitter, Inc. - July 5, 2015 + October 12, 2015 Problem Definition and Classification of BGP Route Leaks - draft-ietf-grow-route-leak-problem-definition-02 + draft-ietf-grow-route-leak-problem-definition-03 Abstract A systemic vulnerability of the Border Gateway Protocol routing system, known as 'route leaks', has received significant attention in recent years. Frequent incidents that result in significant disruptions to Internet routing are labeled "route leaks", but to date we have lacked a common definition of the term. In this document, we provide a working definition of route leaks, keeping in mind the real occurrences that have received significant attention. @@ -35,21 +35,21 @@ 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 January 6, 2016. + This Internet-Draft will expire on April 14, 2016. Copyright Notice Copyright (c) 2015 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 @@ -57,26 +57,36 @@ to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 2. Working Definition of Route Leaks . . . . . . . . . . . . . . 3 3. Classification of Route Leaks Based on Documented Events . . 3 - 4. Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 - 5. Security Considerations . . . . . . . . . . . . . . . . . . . 7 - 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 7 - 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 7 - 8. Informative References . . . . . . . . . . . . . . . . . . . 7 - Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 10 + 3.1. Type 1: U-Shaped Turn with Full Prefix . . . . . . . . . 4 + 3.2. Type 2: Lateral ISP-ISP-ISP Leak . . . . . . . . . . . . 5 + 3.3. Type 3: Leak of Transit-Provider Prefixes to Peer . . . . 5 + 3.4. Type 4: Leak of Peer Prefixes to Transit Provider . . . . 5 + 3.5. Type 5: U-Shaped Turn with More Specific Prefix . . . . . 6 + 3.6. Type 6: Prefix Re-Origination with Data Path to + Legitimate Origin . . . . . . . . . . . . . . . . . . . . 6 + 3.7. Type 7: Accidental Leak of Internal Prefixes and More + Specifics . . . . . . . . . . . . . . . . . . . . . . . . 6 + 4. Additional Comments about the Classification . . . . . . . . 7 + 5. Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 + 6. Security Considerations . . . . . . . . . . . . . . . . . . . 7 + 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 8 + 8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 8 + 9. Informative References . . . . . . . . . . . . . . . . . . . 8 + Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 11 1. Introduction Frequent incidents [Huston2012][Cowie2013][Toonk2015-A][Toonk2015-B][ Cowie2010][Madory][Zmijewski][Paseka][LRL][Khare] that result in significant disruptions to Internet routing are commonly called "route leaks". Examination of the details of some of these incidents reveals that they vary in their form and technical details. Before we can discuss solutions to "the route leak problem" we need a clear, technical definition of the problem and its most common forms. In @@ -96,44 +107,46 @@ A proposed working definition of route leak is as follows: A "route leak" is the propagation of routing announcement(s) beyond their intended scope. That is, an AS's announcement of a learned BGP route to another AS is in violation of the intended policies of the receiver, the sender and/or one of the ASes along the preceding AS path. The intended scope is usually defined by a set of local redistribution/filtering policies distributed among the ASes involved. Often, these intended policies are defined in terms of the pair-wise peering business relationship between ASes (e.g., customer, - provider, peer). For literature related to AS relationships and - routing policies, see [Gao][Gill][Luckie]. For measurements of - valley-free violations in Internet routing, see [Giotsas][Wijchers]. + transit provider, peer). For literature related to AS relationships + and routing policies, see [Gao] [Luckie] [Gill]. For measurements of + valley-free violations in Internet routing, see [Anwar] [Giotsas] + [Wijchers]. The result of a route leak can be redirection of traffic through an unintended path which may enable eavesdropping or traffic analysis, and may or may not result in an overload or black-hole. Route leaks can be accidental or malicious, but most often arise from accidental misconfigurations. The above definition is not intended to be all encompassing. Perceptions vary widely about what constitutes a route leak. Our aim here is to have a working definition that fits enough observed - incidents so that the IETF community has a basis for starting to work - on route leak mitigation methods. + incidents so that the IETF community has a basis for developing + solutions for route leak detection and mitigation. 3. Classification of Route Leaks Based on Documented Events As illustrated in Figure 1, a common form of route leak occurs when a multi-homed customer AS (such as AS3 in Figure 1) learns a prefix - update from one provider (ISP1) and leaks the update to another - provider (ISP2) in violation of intended routing policies, and - further the second provider does not detect the leak and propagates - the leaked update to its customers, peers, and transit ISPs. + update from one transit provider (ISP1) and leaks the update to + another transit provider (ISP2) in violation of intended routing + policies, and further the second transit provider does not detect the + leak and propagates the leaked update to its customers, peers, and + transit ISPs. /\ /\ \ route-leak(P)/ \ propagated / \ / +------------+ peer +------------+ ______| ISP1 (AS1) |----------->| ISP2 (AS2)|----------> / ------------+ prefix(P) +------------+ route-leak(P) | prefix | \ update /\ \ propagated \ (P) / \ / \ @@ -146,172 +159,204 @@ +---------------+ Figure 1: Illustration of the basic notion of a route leak. We propose the following taxonomy for classification of route leaks aiming to cover several types of recently observed route leaks, while acknowledging that the list is not meant to be exhaustive. In what follows, we refer to the AS that announces a route that is in violation of the intended policies as the "offending AS". - o Type 1 "U-Turn with Full Prefix": A multi-homed AS learns a prefix - route from one upstream ISP and simply propagates the prefix to - another upstream ISP. Neither the prefix nor the AS path in the - update is altered. This is similar to a straight forward path- - poisoning attack [Kapela-Pilosov], but with full prefix. It - should be noted that attacks or leaks of this type are often +3.1. Type 1: U-Shaped Turn with Full Prefix + + Description: A multi-homed AS learns a route from one upstream ISP + and simply propagates it to another upstream ISP. Neither the prefix + nor the AS path in the update is altered. This is similar to a + straight forward path-poisoning attack [Kapela-Pilosov], but with + full prefix. It should be noted that leaks of this type are often accidental (i.e. not malicious). The update basically makes a - U-turn at the attacker's multi-homed AS. The attack (accidental - or deliberate) often succeeds because the second ISP prefers - customer announcement over peer announcement of the same prefix. - Data packets would reach the legitimate destination albeit via the - offending AS, unless they are dropped at the offending AS due to - its inability to handle resulting large volumes of traffic. + U-shaped turn at the offending AS's multi-homed AS. The leak often + succeeds because the second ISP prefers customer announcement over + peer announcement of the same prefix. Data packets would reach the + legitimate destination albeit via the offending AS, unless they are + dropped at the offending AS due to its inability to handle resulting + large volumes of traffic. - * Example incidents: Examples of Type 1 route-leak incidents are - (1) the Dodo-Telstra incident in March 2012 [Huston2012], (2) - the Moratel-PCCW route leak of Google prefixes in November 2012 + o Example incidents: Examples of Type 1 route-leak incidents are (1) + the Dodo-Telstra incident in March 2012 [Huston2012], (2) the + Moratel-PCCW route leak of Google prefixes in November 2012 [Paseka], (3) the VolumeDrive-Atrato incident in September 2014 - [Madory], (4) the Hathway-Airtel route leak of 336 Google - prefixes causing widespread interruption of Google services in - Europe and Asia [Toonk2015-A], and (5) the massive Telekom - Malaysia route-leaks of about 179,000 prefixes, which in turn - Level3 accepted and propagated [Toonk2015-B]. + [Madory], (4) the Hathway-Airtel route leak of 336 Google prefixes + causing widespread interruption of Google services in Europe and + Asia [Toonk2015-A], and (5) the massive Telekom Malaysia route- + leaks of about 179,000 prefixes, which in turn Level3 accepted and + propagated [Toonk2015-B]. - o Type 2 "U-Turn with More Specific Prefix": A multi-homed AS learns - a prefix route from one upstream ISP and announces a sub-prefix - (subsumed in the prefix) to another upstream ISP. The AS path in - the update is not altered. Update is crafted by the attacker to - have a subprefix to maximize the success of the attack while - reverse path is kept open by the path poisoning techniques as in - [Kapela-Pilosov]. Data packets reach the legitimate destination - albeit via the offending AS. +3.2. Type 2: Lateral ISP-ISP-ISP Leak - * Example incidents: One example is the demo performed at - DEFCON-16 in August 2008 [Kapela-Pilosov]. Another example is - the earlier-mentioned incident of route leaks from Telekom - Malaysia via Level3, in which out of about 179,000 total route- - leaked prefixes, about 10,000 were more specifics of previously - announced aggregates [Toonk2015-B]. [Note: An attacker who - deliberately performs a Type 1 route leak (with full prefix) - can just as easily perform a Type 2 route leak (with subprefix) - to achieve a greater impact.] + Description: The term "lateral" here is synonymous with "non-transit" + or "peer-to-peer". This type of route leak typically occurs when, + for example, three sequential ISP peers (e.g. ISP-A, ISP-B, and ISP- + C) are involved, and ISP-B receives a route from ISP-A and in turn + leaks it to ISP-C. The typical routing policy between laterally + (i.e. non-transit) peering ISPs is that they should only propagate to + each other their respective customer prefixes. - o Type 3 "Prefix Mis-Origination with Data Path to Legitimate - Origin": A multi-homed AS learns a prefix route from one upstream - ISP and announces the prefix to another upstream ISP as if it is - being originated by it (i.e. strips the received AS path, and re- - originates the prefix). This amounts to mis-origination or - hijacking. However, somehow (not attributable to the use of path - poisoning trick by the attacker) a reverse path is present, and - data packets reach the legitimate destination albeit via the - offending AS. But sometimes the reverse path may not be there, - and data packets get dropped following receipt by the offending - AS. + o Example incidents: In [Mauch-nanog][Mauch], route leaks of this + type are reported by monitoring updates in the global BGP system + and finding three or more very large ISP ASNs in a sequence in a + BGP update's AS path. Mauch [Mauch] observes that these are + anomalies and potentially route leaks because very large ISPs such + as ATT, Sprint, Verizon, and Globalcrossing do not in general buy + transit services from each other. However, he also notes that + there are exceptions when one very large ISP does indeed buy + transit from another very large ISP, and accordingly exceptions + are made in his detection algorithm for known cases. - * Example incidents: Examples of Type 3 route leak include (1) - the China Telecom incident in April 2010 - [Hiran][Cowie2010][Labovitz], (2) the Belarusian GlobalOneBel - route leak incidents in February-March 2013 and May 2013 - [Cowie2013], (3) the Icelandic Opin Kerfi-Simmin route leak - incidents in July-August 2013 [Cowie2013], and (4) the Indosat - route leak incident in April 2014 [Zmijewski]. +3.3. Type 3: Leak of Transit-Provider Prefixes to Peer - o Type 4 "Leak of Internal Prefixes and Accidental Deaggregation": - An offending AS simply leaks its internal prefixes to one or more - of its transit ASes and/or ISP peers. The leaked internal - prefixes are often deaggregated subprefixes (i.e. more specifics) - of already announced aggregate prefixes. Further, the AS - receiving those leaks fails to filter them. Typically these - leaked announcements are due to some transient failures within the - AS; they are short-lived, and typically withdrawn quickly - following the announcements. + Description: This type of route leak occurs when an offending AS + leaks routes learned from its transit provider to a lateral (i.e. + non-transit) peer. - * Example incidents: Leaks of internal prefix-routes occur - frequently (e.g. multiple times in a week), and the number of - prefixes leaked range from hundreds to thousands per incident. - One highly conspicuous and widely disruptive leak of internal - prefixes happened recently in August 2014 when AS701 and AS705 - leaked about 22,000 more specifics of already announced - aggregates [Huston2014][Toonk2014]. + o Example incidents: The incidents reported in [Mauch] include the + Type 3 leaks. - o Type 5 "Lateral ISP-ISP-ISP Leak": This type of route leak - typically occurs when, for example, three sequential ISP peers - (e.g. ISP-A, ISP-B and ISP-C) are involved, and ISP-B receives a - prefix-route from ISP-A and in turn leaks it to ISP-C. The - typical routing policy between laterally (i.e. non-hierarchically) - peering ISPs is that they should only propagate to each other - their respective customer prefixes. +3.4. Type 4: Leak of Peer Prefixes to Transit Provider - * Example incidents: In [Mauch-nanog][Mauch], route leaks of this - type are reported by monitoring updates in the global BGP - system and finding three or more very large ISP ASNs in a - sequence in a BGP update's AS path. Mauch [Mauch] observes - that these are anomalies and potentially route leaks because - very large ISPs such as ATT, Sprint, Verizon, and - Globalcrossing do not in general buy transit services from each - other. However, he also notes that there are exceptions when - one very large ISP does indeed buy transit from another very - large ISP, and accordingly exceptions are made in his detection - algorithm for known cases. + Description: This type of route leak occurs when an offending AS + leaks routes learned from a lateral (i.e. non-transit) peer to its + (the AS's) own transit provider. These leaked routes typically + originate from the customer cone of the lateral peer. - o Type 6 "Leak of Provider Prefixes to Peer": This type of route - leak occurs when an offending AS leaks prefix-routes learned from - its provider to a lateral peer. + o Example incidents: Some of the example incidents cited for Type 1 + route leaks above are also inclusive of Type 4 route leaks. For + instance, in the Dodo-Telstra incident [Huston2012], the leaked + routes from Dodo to Telstra included routes that Dodo learned from + its transit providers as well as lateral peers. - * Example incidents: The incidents reported in [Mauch] include - the Type 6 leaks. +3.5. Type 5: U-Shaped Turn with More Specific Prefix - o Type 7 "Leak of Peer Prefixes to Provider": This type of route - leak occurs when an offending AS leaks prefix-routes learned from - a lateral peer to its (the AS's) own provider. These leaked - prefix-routes typically originate from the customer cone of the - lateral peer. + Description: A multi-homed AS learns a route from one upstream ISP + and announces a subprefix (subsumed in the prefix) to another + upstream ISP. The AS path in the update is not altered. Update is + crafted by the offending AS to have a subprefix to maximize the + success of the attack while reverse path is kept open by the path + poisoning techniques as in [Kapela-Pilosov]. Data packets reach the + legitimate destination albeit via the offending AS. - * Example incidents: Some of the example incidents cited for Type - 1 route leaks above are also inclusive of Type 7 route leaks. - For instance, in the Dodo-Telstra incident [Huston2012], the - leaked routes from Dodo to Telstra included routes that Dodo - learned from its providers as well as lateral peers. + o Example incidents: One example is the demo performed at DEFCON-16 + in August 2008 [Kapela-Pilosov]. Another example is the earlier- + mentioned incident of route leaks from Telekom Malaysia via + Level3, in which out of about 179,000 total route-leaked prefixes, + about 10,000 were more specifics of previously announced less + specific prefixes [Toonk2015-B]. [Note: An attacker who + deliberately performs a Type 1 route leak (with full prefix) can + just as easily perform a Type 5 route leak (with subprefix) to + achieve a greater impact.] -4. Summary +3.6. Type 6: Prefix Re-Origination with Data Path to Legitimate Origin + + Description: A multi-homed AS learns a route from one upstream ISP + and announces the prefix to another upstream ISP as if it is being + originated by it (i.e. strips the received AS path, and re-originates + the prefix). This can be called re-origination or mis-origination. + However, somehow (not attributable to the use of path poisoning trick + by the offending AS) a reverse path is present, and data packets + reach the legitimate destination albeit via the offending AS. But + sometimes the reverse path may not be there, and data packets get + dropped following receipt by the offending AS. + + o Example incidents: Examples of Type 6 route leak include (1) the + China Telecom incident in April 2010 [Hiran][Cowie2010][Labovitz], + (2) the Belarusian GlobalOneBel route leak incidents in February- + March 2013 and May 2013 [Cowie2013], (3) the Icelandic Opin Kerfi- + Simmin route leak incidents in July-August 2013 [Cowie2013], and + (4) the Indosat route leak incident in April 2014 [Zmijewski]. + +3.7. Type 7: Accidental Leak of Internal Prefixes and More Specifics + + Description: An offending AS simply leaks its internal prefixes to + one or more of its transit-provider ASes and/or ISP peers. The + leaked internal prefixes are often more specifics subsumed by an + already announced less specific prefix. The more specifics were not + intended to be routed in eBGP. Further, the AS receiving those leaks + fails to filter them. Typically these leaked announcements are due + to some transient failures within the AS; they are short-lived, and + typically withdrawn quickly following the announcements. However, + these more specifics may momentarily cause the routes to be preferred + over other aggregate route announcements, thus redirecting traffic + from its normal best path. + + o Example incidents: Leaks of internal routes occur frequently (e.g. + multiple times in a week), and the number of prefixes leaked range + from hundreds to thousands per incident. One highly conspicuous + and widely disruptive leak of internal routes happened recently in + August 2014 when AS701 and AS705 leaked about 22,000 more + specifics of already announced aggregates [Huston2014][Toonk2014]. + +4. Additional Comments about the Classification + + It is worth noting that Types 1 through 4 are similar in that a route + is leaked in violation of policy in each case, but what varies is the + context of the leaked-route source AS and destination AS roles. + + It is also worth noting that Type 5 route leak involves a subprefix + and is a special case of Type 1, which involves a full prefix. + Similarly, subprefix versions of other types of route leaks may also + be considered, for example, for Types 2, 3, and 4. Similarly, Type 6 + (i.e. prefix mis-origination with data path to legitimate origin) can + be also conceived to happen in conjunction with Types 2, 3, and 4. + While these possibilities are acknowledged, simply enumerating more + types to consider all such special cases does not add value as far as + solution development for route leaks is concerned. Hence, the + special cases mentioned here are not included in enumerating route + leak types. + +5. Summary We attempted to provide a working definition of route leak. We also presented a taxonomy for categorizing route leaks. It covers not all but at least several forms of route leaks that have been observed and are of concern to Internet user and network operator communities. We hope that this work provides the IETF community a basis for pursuing possible BGP enhancements for route leak detection and mitigation. -5. Security Considerations +6. Security Considerations No security considerations apply since this is a problem definition document. -6. IANA Considerations +7. IANA Considerations No updates to the registries are suggested by this document. -7. Acknowledgements +8. Acknowledgements The authors wish to thank Jared Mauch, Jeff Haas, Warren Kumari, Amogh Dhamdhere, Jakob Heitz, Geoff Huston, Randy Bush, Ruediger - Volk, Andrei Robachevsky, Chris Morrow, and Sandy Murphy for - comments, suggestions, and critique. The authors are also thankful - to Padma Krishnaswamy, Oliver Borchert, and Okhee Kim for their - comments and review. + Volk, Andrei Robachevsky, Charles van Niman, Chris Morrow, and Sandy + Murphy for comments, suggestions, and critique. The authors are also + thankful to Padma Krishnaswamy, Oliver Borchert, and Okhee Kim for + their comments and review. -8. Informative References +9. Informative References + + [Anwar] Anwar, R., Niaz, H., Choffnes, D., Cunha, I., Gill, P., + and N. Katz-Bassett, "Investigating Interdomain Routing + Policies in the Wild", ACM Internet Measurement + Conference (IMC), October 2015, + . [Cowie2010] - Cowie, J., "China's 18 Minute Mystery", Dyn Research/ - Renesys Blog, November 2010, + Cowie, J., "China's 18 Minute Mystery", Dyn + Research/Renesys Blog, November 2010, . [Cowie2013] Cowie, J., "The New Threat: Targeted Internet Traffic Misdirection", Dyn Research/Renesys Blog, November 2013, . [draft-dickson-sidr-route-leak-def] @@ -320,60 +365,59 @@ . [draft-dickson-sidr-route-leak-reqts] Dickson, B., "Route Leaks -- Requirements for Detection and Prevention thereof", IETF Internet Draft (expired), March 2012, . [Gao] Gao, L. and J. Rexford, "Stable Internet routing without - global coordination", IEEE/ACM Transactions on Networking, - December 2001, . [Gill] Gill, P., Schapira, M., and S. Goldberg, "A Survey of Interdomain Routing Policies", ACM SIGCOMM Computer Communication Review, January 2014, - . + . [Giotsas] Giotsas, V. and S. Zhou, "Valley-free violation in Internet routing - Analysis based on BGP Community data", - IEEE ICC 2012, June 2012, - . + IEEE ICC 2012, June 2012. [Hiran] Hiran, R., Carlsson, N., and P. Gill, "Characterizing Large-scale Routing Anomalies: A Case Study of the China Telecom Incident", PAM 2013, March 2013, . [Huston2012] Huston, G., "Leaking Routes", March 2012, . [Huston2014] Huston, G., "What's so special about 512?", September 2014, . [Kapela-Pilosov] Pilosov, A. and T. Kapela, "Stealing the Internet: An Internet-Scale Man in the Middle Attack", DEFCON-16 Las Vegas, NV, USA, August 2008, . + presentations/defcon-16-pilosov-kapela.pdf>. [Khare] Khare, V., Ju, Q., and B. Zhang, "Concurrent Prefix Hijacks: Occurrence and Impacts", IMC 2012, Boston, MA, November 2012, . + paper/12-imc-hijack.pdf>. [Labovitz] Labovitz, C., "Additional Discussion of the April China BGP Hijack Incident", Arbor Networks IT Security Blog, November 2010, . [LRL] Khare, V., Ju, Q., and B. Zhang, "Large Route Leaks", Project web page, 2012, @@ -388,24 +432,24 @@ [Madory] Madory, D., "Why Far-Flung Parts of the Internet Broke Today", Dyn Research/Renesys Blog, September 2014, . [Mauch] Mauch, J., "BGP Routing Leak Detection System", Project web page, 2014, . [Mauch-nanog] - Mauch, J., "Detecting Routing Leaks by Counting", NANOG-41 - Albuquerque, NM, USA, October 2007, + Mauch, J., "Detecting Routing Leaks by Counting", + NANOG-41 Albuquerque, NM, USA, October 2007, . + mauch-lightning.pdf>. [Paseka] Paseka, T., "Why Google Went Offline Today and a Bit about How the Internet Works", CloudFare Blog, November 2012, . [Toonk2014] Toonk, A., "What caused today's Internet hiccup", August 2014, . @@ -416,22 +460,22 @@ what-caused-the-google-service-interruption/>. [Toonk2015-B] Toonk, A., "Massive route leak causes Internet slowdown", June 2015, . [Wijchers] Wijchers, B. and B. Overeinder, "Quantitative Analysis of BGP Route Leaks", RIPE-69, November 2014, - . + . [Zmijewski] Zmijewski, E., "Indonesia Hijacks the World", Dyn Research/Renesys Blog, April 2014, . Authors' Addresses Kotikalapudi Sriram