Internet Engineering Task Force Yang, Ed. Internet-Draft Shi Intended status: Informational Xiang Expires: September 12, 2017 Wang Wu Yin Tsinghua Univ. March 11, 2017 Fast route attestation on AS Path Segment draft-yang-sidr-fra-04 Abstract This draft proposes Fast Route Attestation (FRA), a mechanism for securing AS paths and preventing prefix hijacking by signing and verifying critical AS path segments (i.e., adjacent AS triples along AS path). When full-deployed, FRA can achieve similar level of security as BGPSec, but with much higher efficiency. When partial- deployed, FRA offers more security benefits than BGPSec. Status of This Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. 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 September 12, 2017. Copyright Notice Copyright (c) 2017 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 Yang, et al. Expires September 12, 2017 [Page 1] Internet-Draft FRA March 2017 carefully, as they describe your rights and restrictions with respect 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. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 3. Background . . . . . . . . . . . . . . . . . . . . . . . . . 3 4. FRA: Fast Route Attestation . . . . . . . . . . . . . . . . . 5 4.1. Neighbor Based Importing and Exporting . . . . . . . . . 5 4.2. Signing Critical AS Path Segments efficiently . . . . . . 6 4.3. More benefits in partial-deployment scenario . . . . . . 8 4.4. Other supports to FRA . . . . . . . . . . . . . . . . . . 8 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 9 6. Security Considerations . . . . . . . . . . . . . . . . . . . 9 7. Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . 9 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 9 8.1. Normative References . . . . . . . . . . . . . . . . . . 9 8.2. Informative References . . . . . . . . . . . . . . . . . 11 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 11 1. Introduction In order to secure inter-domain routing, several extensions of BGP have been proposed, which fall into two categories: anomaly detection and cryptographic based authentication. However, anomaly detection approaches [Whisper] [PGBGP] only detect and report routing anomalies. They can not guarantee security in advance. Cryptographic approaches, like S-BGP [S-BGP] and BGPSec [RFC7353], use the Public Key Infrastructure (PKI) to authenticate routing announcements. However, they may consume significant resources of computation and storage. The other solutions either compromise in the security [IRV] [I-D.ng-sobgp-bgp-extensions] [psBGP] [SPV], or bring in more complexity on certification distribution [SA]. Towards these unsolved issues, we propose an efficient approach, FRA (Fast Route Attestation), to secure AS path. Through signing and verifying critical AS path segments (i.e., adjacent AS triples along AS path), FRA can achieve similar level of security as S-BGP/BGPSec, but with much higher efficiency. Besides, when partial-deployed, FRA offers more security benefits than BGPSec, promoting ISPs to deploy the security mechanism. It is the critical part of FS-BGP. Analysis, evaluations, and more discussions of FRA can be found in the recent technical report [TR-FSBGP]. Yang, et al. Expires September 12, 2017 [Page 2] Internet-Draft FRA March 2017 2. Terminology (AS_i): AS i : AS path from AS n to the origin AS 0 f: AS path of prefix f originated from AS 0 : critical AS path segment, adjacent AS triple in a path : origin critical AS path segment in a path of prefix f {msg}i: signature on msg generated by AS i 3. Background In BGP, UPDATE messages will not be validated, so neither the origin AS nor the AS path is guaranteed to be correct. Secure BGP (S-BGP) [S-BGP] is the dominant solution to this problem, and it is based on RPKI [RFC6480] to help authenticating involved parties and messages. Specifically, S-BGP uses Route Attestations (RAs) for path authentication. On the basis of S-BGP, BGPSec [RFC7353] was proposed to secure inter-domain routing, which has been standardized by IETF. As shown in Figure 1, an RA is all signatures signed by ASes along the path to authenticate the existence and position of ASes in the path. We define {msg}i as the signature on msg generated with AS i's private key. In Figure 1, each AS i equivalently signs the corresponding extended AS path and the prefix f. The inclusion of the recipient AS i+1 in each signature is necessary to prevent cut-and-paste attack. Yang, et al. Expires September 12, 2017 [Page 3] Internet-Draft FRA March 2017 +---------------------------------------------------------------------------------+ | (AS_n+1) <-- (AS_n) <-- ... <-- (AS_i) <-- ... <-- (AS_1) <-- (AS_0) | | s_0 s_0 s_0 s_0 | | s_1 s_1 s_1 \\ | | . . \\ {AS_1, AS_0, f}0 | | . . {AS_2, AS_1, s_0}1 | | . . \\ | | s_i s_i {AS_2, AS_1, AS_0, f}1 | | . \\ | | . {AS_i+1, AS_i, s_i-1}i | | . \\ | | s_n {AS_i+1, AS_i, AS_i-1, ..., AS_1, AS_0, f}i | | \\ | | {AS_n+1, AS_n, s_n-1}n | | \\ | | {AS_n+1, AS_n, AS_n-1, ..., AS_1, AS_0, f}n | +---------------------------------------------------------------------------------+ Figure 1: RA in BGPSec. The main concern about deploying BGPSec in practice is its huge computational cost for signing and verifying signatures while authenticating AS path. So there are a bunch of solutions for reducing the overhead of path authentication. soBGP [I-D.ng-sobgp-bgp-extensions] maintains all authenticated AS edges in a database, but faces the problem of forged paths. IRV [IRV] builds an authentication server in each AS, but brings the problem of maintaining and inter-connecting these servers, and introduces query latencies. SPV [SPV] accelerates the signing process by pre-generated one-time signatures based on a single root value, but involves a significant amount of state information, and its security can only be guaranteed probabilistically. Signature Amortization (S-A) [SA] uses one bit vector for each neighbor of an AS to indicate the allowed recipients of a route, such that only for multiple recipients router only needs to sign once. However, each AS will need to pre-establish a neighbor list corresponding to the bit vector, and to distribute it to all other ASes. As we can see, existing methods usually compromise security, and most of them only improve the performance of signing. However, verification happens more frequently than signing, since one signature often needs to be verified at multiple places. Besides, when BGPSec is partial-deployed, it can only improve limited security benefits. This influence the deployment of BGPSec seriously. Many ISPs insist that unless majority of ASes deploys BGPSec, they would not benefit much from deploying BGPSec. Yang, et al. Expires September 12, 2017 [Page 4] Internet-Draft FRA March 2017 To overcome these weeknesses, Path-End Validation [PATH-END] has been proposed. Since AS paths of BGP updates are usually very short, most attackers try to forge paths at their first two hops. Path-End Validation aims to protect the two hops from modification. The researchers show that if the first two hops of AS paths are authenticated, attackers can only attract little traffic by forging other parts of AS path. That is, Path-End Validation provides less security protection than BGPSec when full-deployed. However, according to simulation results, ASes can benefit more during the long partial-deployed period. So Path-End Validation provides a tangible path to significant improvements in inter-domain routing security before BGPSec is fully deployed. Though Path-End Validation provides a way to improve inter-domain routing security, it has its own shortcoming. When deployed widely, it cannot reach the security level of BGPSec. Thus we wonder if there is a method which has higher computational efficiency than BGPSec with the similar security benefit when full-deployed. In addition, the method improves security obviously like Path-End Validation during the long interim period. Our solution, Fast Route Attestation (FRA), based on the assumption that RPKI has been used for origin authentication, focuses on path authentication. Importantly, FRA can satisfy such requirements well. 4. FRA: Fast Route Attestation 4.1. Neighbor Based Importing and Exporting BGP is a policy-based routing protocol. An AS only exports a route to a neighbor if it is willing to forward traffic to the corresponding prefix from that neighbor. Although complex policies (i.e. , route filters [RFC2622]) exist, AS usually does not differentiate with prefixes or nonadjacent ASes. For example, in Figure 2, when AS n decides whether routes learned from AS n-1 can be exported to AS n+1, it only considers its relation with its two direct neighbors, but does not consider other ASes along the path (). We call this the Neighbor Based Importing and Exporting (NBIE). Yang, et al. Expires September 12, 2017 [Page 5] Internet-Draft FRA March 2017 +-----------------------------------------------------------------------+ | / ... (AS_x_0) ... \ | | / . \ | | (AS_n+1) <-- (AS_n) <-- (AS_n-1) <-- ... . ... <-- (AS_0) | | \ . / | | \ ... (AS_x_k) ... / | +-----------------------------------------------------------------------+ Figure 2: In BGPSec, AS n signs k paths which share a mutual AS path segment . NBIE abstracts the basic functionality of BGP. According to our measurement results in whois database, only a small portion of routing polices (route filters) violate NBIE assumption. Nevertheless, the purpose of route filters is to protect the routing system against distribution of inaccurate routing information [RFC2622]. In other words, the use of route filters is mainly due to security considerations rather than policy requirements. We believe that under a security environment (i.e., FRA/FS-BGP or BGPSec), these ASes will not need filters any more. In deed, our schema can also flexibly support complicated routing polices [TR-FSBGP]. 4.2. Signing Critical AS Path Segments efficiently Following NBIE assumption above, we propose Fast Route Attestation (FRA) to guarantee the authentication of AS paths. Given a path p=, we define its set of critical path segments as c_i, 0 , for i=0 c_i = \ , for 0 actually describes an export policy of AS i, implying that AS i exports all routes imported from AS i-1 to AS i+1. More specifically, FRA uses Critical Segment Attestations (CSA) to authenticate paths. A CSA is simply the signature of the critical path segment signed by its owner. In a path p=, the CSA s_i signed by AS i is defined as: / {1,0,f}0 , for i=0 s_i = \ {i+1,i,i-1}i , for 0. Moreover, there are situations where several distinct prefixes can be reached along the same AS path. As BGPSec is sensitive to prefix, one AS must sign several times if it deploys BGPSec. While adopting FRA mechanism, the AS just signs critical path segment one time. +---------------------------------------------------------------------------------+ | (AS_n+1) <-- (AS_n) <-- ... <-- (AS_i) <-- ... <-- (AS_1) <-- (AS_0) | | s_0 s_0 s_0 s_0 | | s_1 s_1 s_1 \\ | | . . \\ {AS_1,AS_0,AS_f}0 | | . . {AS_2,AS_1,AS_0}1 | | . . | | s_i s_i | | . \\ | | . {AS_i+1,AS_i,AS_i-1}i | | . | | s_n | | \\ | | {AS_n+1,AS_n,AS_n-1}n | +---------------------------------------------------------------------------------+ Figure 3: CSAs in FRA. Then we explain that FRA mechanism can achieve similar level of security as S-BGP/BGPSec. For every secure path in BGPSec, it is also authenticated in FRA. For instance, is secure in BGPSec. That is to say, ASes along the path all deploy BGPSec, signing and verifying the path. If they adopt FRA, they also sign its corresponding critical path segment. Since ASes along the path are fully-deployed, the critical path segments can constitute the complete path. If some attacker k intends to forge a link between k and AS i, receivers will verify the CSA. Because the CSA s_i (i.e. {AS_i+1,AS_i,AS_i-1}i) means i+1 is the true next-hop, the forged update will be dropped. Yang, et al. Expires September 12, 2017 [Page 7] Internet-Draft FRA March 2017 In this section, we argue that under the NBIE rule, if every AS along a path signs its critical path segment, the path can be authenticated. So as long as all the ASes along an AS path adopt FRA mechanism, the path must be authenticated. Considering its efficiency we discussed above, FRA can achieve similar level of security as BGPSec with less time cost. 4.3. More benefits in partial-deployment scenario As BGPSec is likely to coexist with legacy BGP for a long time, we must consider the effects of them in partial-deployment period. In general, when not fully deployed, FRA can prevent more attacks than BGPSec. In BGPSec, one AS regards a route secure/insecure according to those ASes along the path. Only if they all have deployed BGPSec, this route is regarded as a secure route. However, if there is any AS which still runs legacy BGP, it would be regarded as an insecure one. But under FRA mechanism, this changes. A route will not be regarded secure/insecure roughly. Instead, FRA can provide different levels of protections to authenticate AS path. For instance, suppose that is a path of prefix f. If an attacker a intends to forge a path but a is not AS i-1's true neighbor, the forged path may be dropped by FRA authentication. Specifically, if AS i-1 deploys FRA mechanism, it should sign a critical path segment . Since AS a is not AS i-1's neighbor, the critical path segment will not appear in UPDATE messages. Thus, the attacker has to forge the CSA, which can be detected by FRA adopters. Briefly speaking, even if it is during partial-deployment period, FRA can provide more benefit than BGPSec. According to the example aforementioned, the isolated deployment on AS i-1 can prevent attackers from forging path to it. However, the same benefit with BGPSec needs the deployment on all ASes along the true path. Since full-deployed BGPSec is not a short-term job, FRA makes sense because of its better benefit in interim period. When majority still runs legacy BGP, FRA guarantees users better security than BGPSec. Besides, because FRA authenticates the whole path of BGP updates when fully deployed, it can provide a similar security benefit as BGPSec. 4.4. Other supports to FRA FRA uses certificates to handle UPDATE messages. As FRA takes effect even if some ASes along the path don't deploy it, the certificates of FRA must involve extra info. Yang, et al. Expires September 12, 2017 [Page 8] Internet-Draft FRA March 2017 Based on RPKI [RFC6480], FRA can also validate source address of BGP. Thus, FRA certificates must include ASNs, prefixes and their maximum length, which are similar to RPKI's ROAs. In order to sign critical AS path segments, any AS must be accessible to public keys of all ASes. They are stored in some public repositories. Relying parties can download them to their local caches and validate UPDATEs with FRA. Besides, ASNs of all the ASes having deployed FRA are also involved in certificates. When FRA is partial-deployed, ASes can check all adopters' CSAs along the path. Thus, attackers cannot remove any CSAs to forge path. 5. IANA Considerations This document includes no request to IANA. 6. Security Considerations The entire document is about security consideration. More theoretical analysis and experiment results can be found in our technical report [TR-FSBGP]. 7. Conclusions This draft proposes Fast Route Attestation (FRA), an efficient mechanism for securing AS paths and preventing prefix hijacking by signing critical AS path segments with cache machenism. FRA can achieve provide higher security benefits than BGPSec even in very limited partial adoption. Also, we believe it can achieve higher level of security than Path-End validation when full-deployed. 8. References 8.1. Normative References [I-D.ng-sobgp-bgp-extensions] Ng, J., "Extensions to BGP to Support Secure Origin BGP (soBGP)", 2004. [IRV] Goodell, G., Aiello, W., Griffin, T., Ioannidis, J., McDaniel, P., and A. Rubin, "Working around BGP: An Incremental Approach to Improving Security and Accuracy in Interdomain Routing", 2003. Yang, et al. Expires September 12, 2017 [Page 9] Internet-Draft FRA March 2017 [PATH-END] Cohen, Avichai., Gilad, Yossi., Herzberg, Amir., and Michael. Schapira, "Jumpstarting BGP Security with Path- End Validation", 2016. [psBGP] van Oorschot, P., Wan, T., and E. Kranakis, "On interdomain routing security and pretty secure BGP (psBGP)", 2007. [RFC2622] Alaettinoglu, C., Villamizar, C., Gerich, E., Kessens, D., Meyer, D., Bates, T., Karrenberg, D., and M. Terpstra, "Routing Policy Specification Language (RPSL)", RFC 2622, DOI 10.17487/RFC2622, June 1999, . [RFC4271] Rekhter, Y., Ed., Li, T., Ed., and S. Hares, Ed., "A Border Gateway Protocol 4 (BGP-4)", RFC 4271, DOI 10.17487/RFC4271, January 2006, . [RFC6480] Lepinski, M. and S. Kent, "An Infrastructure to Support Secure Internet Routing", RFC 6480, DOI 10.17487/RFC6480, February 2012, . [RFC7353] Bellovin, S., Bush, R., and D. Ward, "Security Requirements for BGP Path Validation", RFC 7353, DOI 10.17487/RFC7353, August 2014, . [S-BGP] Kent, S., Lynn, C., Mikkelson, J., and K. Seo, "Secure Border Gateway Protocol (S-BGP)", 2000. [SA] Nicol, D., Smith, S., and M. Zhao, "Evaluation of efficient security for BGP route announcements using parallel simulation", 2004. [SPV] Hu, Y., Perrig, A., and M. Sirbu, "SPV: secure path vector routing for securing BGP", 2004. [TR-FSBGP] Xiang, Yang., Wang, Zhiliang., Yin, Xia., Shi, Xingang., and Jianping. Wu, "FS-BGP: An Efficient Approach to Securing AS Paths", 2011. Yang, et al. Expires September 12, 2017 [Page 10] Internet-Draft FRA March 2017 8.2. Informative References [PGBGP] Karlin, J., Forrest, S., and J. Rexford, "Pretty Good BGP: Improving BGP by Cautiously Adopting Routes", 2006. [Whisper] Subramanian, L., Roth, V., Stoica, I., Shenker, S., and R. Katz, "Listen and Whisper: Security Mechanisms for BGP", 2004. Authors' Addresses Yan Yang (editor) Tsinghua Univ. Beijing CN Email: yangyan15@mails.tsinghua.edu.cn Xingang Shi Tsinghua Univ. Beijing CN Email: shixg@cernet.edu.cn Yang Xiang Tsinghua Univ. Beijing CN Email: xiangy08@csnet1.cs.tsinghua.edu.cn Zhiliang Wang Tsinghua Univ. Beijing CN Email: wzl@csnet1.cs.tsinghua.edu.cn Yang, et al. Expires September 12, 2017 [Page 11] Internet-Draft FRA March 2017 Jianping Wu Tsinghua Univ. Beijing CN Email: jianping@csnet1.cs.tsinghua.edu.cn Xia Yin Tsinghua Univ. Beijing CN Email: yxia@csnet1.cs.tsinghua.edu.cn Yang, et al. Expires September 12, 2017 [Page 12]