Securing Interdomain Routing Techniques

How Small Groups Can Secure Interdomain Routing Martin Suchara in collaboration with I. Avramopoulos and J. Rexford

Interdomain Routing (BGP) is not Secure BGP is vulnerable to: Deliberate attacks Misconfigurations Yet, users demand: Confidentiality Integrity Availability 2

Securing Interdomain Routing Users demand: Confidentiality Integrity Availability Existing crypto solutions Focus of this work 3

Overview The routing system and its vulnerabilities I. II. Why should small groups secure BGP III. Securing BGP in small groups effectiveness of techniques IV. Our approach a) SBone secure overlay routing b) Shout hijacking the hijacker V. Conclusion 4

Interdomain Routing Terminology Autonomous Systems (ASes) = independently administered networks in a loose federation Prefix = set of IP addresses Origin = genuine owner of an address prefix Route = AS-level path to the origin Origin of 12.34.* 1 2 1 AS #1 Yale AS #2 AT&T AS #3 Princeton 5 Data packets Routing announcements

Interdomain Routing Protocol Based on Trust BGP is prefix-based path-vector protocol Each AS maintains a set of routes to all prefixes One best route is used Originate 12.34.* 2 1 1 AS1 12.34.* AS2 AS1 12.34.* AS #1 12.34.* AS #2 AS #3 AS #4 6 1

Interdomain Routing Export & Policies Customer-provider and peer-peer relationships Selecting a route: by assumption the most profitable, shortest route preferred At most one profitable route exported customer- provider National ISP (#1) National ISP (#2) Regional ISP (#3) Regional ISP (#4) Regional ISP (#5) Cust. #6 Cust. #7 peer-peer 7 12.34.*

Interdomain Routing Export & Policies Customer-provider and peer-peer relationships Selecting a route: by assumption the most profitable, shortest route preferred At most one profitable route exported National ISP (#1) National ISP (#2) Regional ISP (#3) Regional ISP (#4) Regional ISP (#5) Cust. #6 Cust. #7 Use: 6 Remember: 3 6 8 12.34.*

Interdomain Routing One Cannot Learn Many Routes Customer-provider and peer-peer relationships Selecting a route: by assumption the most profitable, shortest route preferred At most one profitable route exported National ISP (#1) National ISP (#2) Regional ISP (#3) Regional ISP (#4) Regional ISP (#5) Cust. #6 Cust. #7 Use: 6 Remember: 3 6 9 12.34.*

Vulnerabilities Example 1 Invalid origin attack Nodes 1, 3 and 4 route to the adversary The true destination is blackholed 1 2 3 4 5 6 7 Genuine origin Attacker 10 12.34.* 12.34.*

Vulnerabilities Example 2 Adversary spoofs a shorter path Node 4 routes through 1 instead of 2 The traffic may be blackholed or intercepted No attack 1 2 3 4 5 6 7 Thinks route thru 2 shorter Genuine origin 11 12.34.*

Vulnerabilities Example 2 Adversary spoofs a shorter path Node 4 routes through 1 instead of 2 The traffic may be blackholed or intercepted Announce 1 7 1 2 3 4 5 6 7 Thinks route thru 1 shorter Genuine origin 12 12.34.*

Overview The routing system and its vulnerabilities I. Why should small groups secure BGP II. III. Securing BGP in small groups effectiveness of techniques IV. Our approach a) SBone secure overlay routing b) Shout hijacking the hijacker V. Conclusion 13

State of the Art S-BGP and soBGP Mechanism: identify which routes are invalid and filter them S-BGP Certificates to verify origin AS Cryptographic attestations added to routing announcements at each hop soBGP Build a (partial) AS level topology database 14

Limitations of the Secure Protocols Previous solutions Benefits only for large deployments (~10,000s) No incentive for early adopters No deployment for over a decade Our goal: Provide incentives to early adopters! 15

Our Approach Secure routing within a small group 10-20 cooperating nodes All participants routes are secured Challenges Non-participants outnumber participants Participants rely on non-participants Each AS exports only one route Focus on raising the bar for the adversary rather than residual vulnerabilities 16

Overview The routing system and its vulnerabilities I. II. Why should small groups secure BGP III. Securing BGP in small groups effectiveness of techniques IV. Our approach a) Sbone secure overlay routing b) Shout hijacking the hijacker V. Conclusion 17

Experimental Evaluations Performance of existing techniques They work well in large scale deployments How do they do in small groups? Evaluate performance of state-of-the art: soBGP Evaluate partial deployment If two ASes participate, a valid link connecting them must be in the registry 18

Experimental Setup All Experiments Method simulation of BGP announcements on the AS-level Internet topology Topology information from RouteViews Adversary and origin chosen at random Participants implement secure protocol 1 or 5 adversaries Performance metric fraction of the Internet ASes with valid routes Average of 100 runs 19

soBGP Random Participation, 1 adversary % of the Internet with valid routes Participants have a higher chance to have a valid route! Percentage of ASes Groups of 1 30 participants Participant ASes All ASes 20 Number of Participant ASes

soBGP Deployment by 30 Random + Some Largest ISPs Percentage of ASes Better performance Cooperation of many large ISPs needed! Participant ASes All ASes 21 Number of Large ISPs

Perfect Detection Simulations: give ability to detect routes that don t work Is this sufficient to secure routing? How useful is it to have perfect detection? Can be done in practice: Data-plane probing verifies validity of route by using it 22

Perfect Detection at 30 Random + Some Largest ISPs Percentage of ASes Perfect detection helps but not sufficient by itself! Participant ASes All ASes 23 Number of Large ISPs

Lessons Learned Observation Justification Participation of large ISPs is important They learn many routes some of which are valid Perfect detection of bad routes is desirable Better (but not ideal) performance The non-participants are worse off than the participants The participants reject implicated routes while non- participants accept all Need to increase path diversity Perfect detection not enough 24

Overview The routing system and its vulnerabilities I. II. Why should small groups secure BGP III. Securing BGP in small groups effectiveness of techniques IV. Our approach a) Sbone secure overlay routing b) Shout hijacking the hijacker V. Conclusion 25

Our Approach Key Ideas Circumvent the adversary with secure overlay routing Hijack the hijacker: all participants announce the protected prefix Hire a few large ISPs to help Detect invalid routes accurately with data plane detectors 26

Our Approach Key Ideas Circumvent the adversary with secure overlay routing Hijack the hijacker: all participants announce the protected prefix Hire a few large ISPs to help Detect invalid routes accurately with data plane detectors 27

Our Approach Key Ideas Circumvent the adversary with secure overlay routing Hijack the hijacker: all participants announce the protected prefix Hire a few large ISPs to help Detect invalid routes accurately with data plane detectors 28

Our Approach Key Ideas Circumvent the adversary with secure overlay routing Hijack the hijacker: all participants announce the protected prefix Hire a few large ISPs to help Detect invalid routes accurately with data plane detectors 29

Overview The routing system and its vulnerabilities I. II. Why should small groups secure BGP III. Securing BGP in small groups effectiveness of techniques IV. Our approach a) SBone secure overlay routing b) Shout hijacking the hijacker V. Conclusion 30

Secure Overlay Routing (SBone) Protects intra-group traffic Overlay of participants networks Bad paths detected by probing Use peer route Use provider route Use longer route 1 1 2 2 Participant Nonparticipant 5 5 4 3 Detected as bad ; 12.34.1.1 12.34.* 6 7 7 31 12.34.* ; 12.34.1.1

Secure Overlay Routing (SBone) Traffic may go thru an intermediate node Uses path thru intermediate node 3 Forwards traffic for 1 ? 1 2 ? ? 12.8.1.1 ? 5 4 3 ; 12.34.1.1 ; 12.8.1.1 12.34.* 6 7 32 12.34.* ; 12.34.1.1

SBone 30 Random + Help of Some Large ISPs Percentage of Participating ASes Good performance even for small groups! 5 large ISPs 3 large ISPs 1 large ISP 0 large ISPs 33 Group Size (ASes)

SBone Multiple Adversaries Solution: enlist more large ISPs! Percentage of Participating ASes With 5 adversaries, the performance degrades 5 large ISPs 3 large ISPs 1 large ISP 0 large ISPs 34 Group Size (ASes)

SBone - Summary Observation Justification SBone offers good availability even for very small groups It better exposes path diversity Non-participants are not secure yet They lack the ability to tunnel around problems 35

Overview The routing system and its vulnerabilities I. II. Why should small groups secure BGP III. Securing BGP in small groups effectiveness of techniques IV. Our approach a) SBone secure overlay routing b) Shout hijacking the hijacker V. Conclusion 36

Hijacking the Hijacker Shout Secure traffic from non-participants All participants announce the protected prefix Once the traffic enters the overlay, it is securely forwarded to the true prefix owner Use shortest path Prefers short customer s path leading to adversary 1 4 12.34.* 1 2 12.34.* 3 4 5 12.34.* 6 7 Node 4 shouts 37 12.34.* 12.34.*

Shout + SBone 1 Adversary Percentage of ASes With as few as 10 participants + 3 large ISPs, 95% of all ASes can reach the victim! 5 large ISPs 3 large ISPs 1 large ISP 0 large ISPs 38 Group Size (ASes)

Shout + SBone 5 Adversaries Percentage of ASes More adversaries larger groups required! 5 large ISPs 3 large ISPs 1 large ISP 0 large ISPs 39 Group Size (ASes)

Performance and Scalability of Shout Shout can be used reactively Only shout if an attack is detected Changes in routing table sizes negligible Alternate routes must be saved in routing tables The average table size increased by less than 5% After shouting path lengths increase modestly Paths less than 1.35 times longer Detailed results next 40

Shout + SBone Increase in Path Length With as few as 3 large ISPs the penalty is negligible! Length Ratio 0 large ISPs 1 large ISP 3 large ISPs 5 large ISPs 41 Group Size (ASes)

Shout - Summary Observation Justification Can secure communication from non-participants It suffices if non-participant reaches any participant Routing table sizes do not increase Increases < 5% Shout does not inflate path lengths significantly Path lengths increase by <15% with 3 large ISPs 42

Overview The routing system and its vulnerabilities I. II. Why should small groups secure BGP III. Securing BGP in small groups effectiveness of techniques IV. Our approach a) SBone secure overlay routing b) Shout hijacking the hijacker V. Conclusion 43

Conclusion BGP should be secured by small groups To be effective, the group members should (i) Detect and filter compromised routes accurately (ii) Cooperate to expose path diversity (iii) Coax non-participants to pick valid routes (iv) Enlist a few large ISPs 44

Conclusion SBone and Shout are novel mechanisms that achieve these goals The proposed solution (i) Secures address space of a small group of participants (ii) Allows both participants and non-participants pick valid routes (iii) Provides incentives to the adopters 45

Future Work Deployment in larger groups where participants don t trust each other Secure routing protocol on the overlay? Analytic models of the deployment Predict which additional ASes to enlist to boost performance? Effects of the structure of the graph on the outcomes? 46

Thank you for your attention! 47

Discussion 1. Effects of subprefix hijacking 2. What if participants not willing to choose less profitable routes? 3. What if N large ISPs are used instead of N largest ones? 4. Average results and error bars 48

1. Subprefix Hijacking Threat: adversary deaggregates the victim s prefix, all traffic is directed to the adversary Key security mechanisms Deaggregate the prefix and use shout to announce it Tunnel endpoints already secure if announced with /24 prefixes Only deaggregate when attack detected Attack detected if at least one participant sees an unauthorized subprefix

1. Subprefix Hijacking Avoiding Detection If the adversary conceals the attack, <5% ASes are affected! Percentage of ASes 5 large ISPs 3 large ISPs 1 large ISP 50 Group Size (ASes)