idnits 2.17.1 draft-xia-sidr-fsbgp-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** There is 1 instance of lines with control characters in the document. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (July 2, 2011) is 4682 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Missing Reference: 'SBGP' is mentioned on line 113, but not defined == Unused Reference: 'RFC4271' is defined on line 397, but no explicit reference was found in the text -- Possible downref: Non-RFC (?) normative reference: ref. 'S-BGP' -- Possible downref: Normative reference to a draft: ref. 'I-D.ng-sobgp-bgp-extensions' -- Possible downref: Non-RFC (?) normative reference: ref. 'IRV' -- Possible downref: Non-RFC (?) normative reference: ref. 'SPV' -- Possible downref: Non-RFC (?) normative reference: ref. 'SA' -- Possible downref: Non-RFC (?) normative reference: ref. 'TR-FSBGP' Summary: 1 error (**), 0 flaws (~~), 3 warnings (==), 7 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 INTERNET-DRAFT Xia Yin 3 Intended Status: Proposed Standard Tsinghua Univ. 4 Expires: January 3, 2012 Yang Xiang 5 Tsinghua Univ. 6 Zhiliang Wang 7 Tsinghua Univ. 8 Jianping Wu 9 Tsinghua Univ. 10 July 2, 2011 12 Efficient Secure BGP AS Path using FS-BGP 13 draft-xia-sidr-fsbgp-00.txt 15 Abstract 17 This draft proposes Fast Secure BGP (FS-BGP), an efficient mechanism 18 for securing AS paths and preventing prefix hijacking by signing 19 critical AS path segments (i.e., adjacent AS triples). FS-BGP can 20 achieve similar level of security as S-BGP, but with much higher 21 efficiency. 23 Status of this Memo 25 This Internet-Draft is submitted in full conformance with the 26 provisions of BCP 78 and BCP 79. This document may not be modified, 27 and derivative works of it may not be created, except to publish it 28 as an RFC and to translate it into languages other than English. 30 Internet-Drafts are working documents of the Internet Engineering 31 Task Force (IETF), its areas, and its working groups. Note that 32 other groups may also distribute working documents as 33 Internet-Drafts. 35 Internet-Drafts are draft documents valid for a maximum of six months 36 and may be updated, replaced, or obsoleted by other documents at any 37 time. It is inappropriate to use Internet-Drafts as reference 38 material or to cite them other than as "work in progress." 40 The list of current Internet-Drafts can be accessed at 41 http://www.ietf.org/1id-abstracts.html 43 The list of Internet-Draft Shadow Directories can be accessed at 44 http://www.ietf.org/shadow.html 46 Copyright and License Notice 48 Copyright (c) 2011 IETF Trust and the persons identified as the 49 document authors. All rights reserved. 51 This document is subject to BCP 78 and the IETF Trust's Legal 52 Provisions Relating to IETF Documents 53 (http://trustee.ietf.org/license-info) in effect on the date of 54 publication of this document. Please review these documents 55 carefully, as they describe your rights and restrictions with respect 56 to this document. Code Components extracted from this document must 57 include Simplified BSD License text as described in Section 4.e of 58 the Trust Legal Provisions and are provided without warranty as 59 described in the Simplified BSD License. 61 Table of Contents 63 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 64 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 65 3. Background . . . . . . . . . . . . . . . . . . . . . . . . . . 3 66 4. Secure Feasible AS Paths . . . . . . . . . . . . . . . . . . . 5 67 5. FS-BGP: Fast Secure BGP . . . . . . . . . . . . . . . . . . . 6 68 5.1. Signing Critical AS Path Segments . . . . . . . . . . . . 6 69 5.2. Prevent Effective Hijacking in FS-BGP . . . . . . . . . . 7 70 6. Security Considerations . . . . . . . . . . . . . . . . . . . 9 71 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 9 72 8. Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . 9 73 9 References . . . . . . . . . . . . . . . . . . . . . . . . . . 9 74 9.1 Normative References . . . . . . . . . . . . . . . . . . . 10 75 9.2 Informative References . . . . . . . . . . . . . . . . . . 11 76 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 11 78 1. Introduction 80 In order to improve the security of BGP, several extensions have been 81 proposed, which fall into two categories: anomaly detection and 82 cryptographic based authentication. However, anomaly detection 83 approaches [Whisper] [PGBGP] can not guarantee security and 84 correctness. Cryptographic approaches, which are being pursued by the 85 SIDR WG, use the Public Key Infrastructure (PKI) to authenticate 86 routing announcements. There are a bunch of solutions including S-BGP 87 [S-BGP] [I-D.lepinski-bgpsec-protocol] and many others. However, S- 88 BGP may consume significant resources of computation and storage. The 89 other solutions either compromise in the security [IRV] [I-D. ng- 90 sobgp-bgp-extensions] [psBGP] [SPV], or bring in more complexity on 91 certification distribution [SA]. 93 Towards these unsolved issues, we propose an efficient approach, FS- 94 BGP (Fast Secure BGP), to secure AS path. Through signing critical AS 95 path segments (i.e., adjacent AS triples), FS-BGP can achieve similar 96 level of security as S-BGP, but with much higher efficiency. 97 Analysis, evaluations, and more discussions can be found in our 98 recent technical report [TR-FSBGP]. 100 2. Terminology 102 (i): AS i 103 : AS path from AS n to the origin AS 0 104 f: AS path of prefix f 105 : critical AS path segment, adjacent AS triple in a path 106 <1, 0, f>: origin critical AS path segment in a path of prefix f 107 {msg}i: signature on msg generated by AS i 109 3. Background 111 In BGP, UPDATE messages can not be validated, so neither the origin 112 AS nor the AS path is guaranteed to be correct. Secure BGP (S-BGP) 113 [SBGP] is the dominant solution to this problem, and it uses a PKI to 114 help authenticating involved parties and messages. Specifically, S- 115 BGP uses Route Attestations (RAs) for path authentication. 117 As shown in Figure 1, a RA is all signatures signed by ASes along the 118 path to authenticate the existence and position of ASes in the path. 119 We define {msg}i as the signature on msg generated with AS i's 120 private key. In Figure 1, each AS i equivalently signs the 121 corresponding extended AS path and the prefix f. The 122 inclusion of the recipient AS i+1 in each signature is necessary to 123 prevent cut-and-paste attack. 125 +-------------------------------------------------------------+ 126 | (n+1) <-- (n) <-- ... <-- (i) <-- ... <-- (1) <-- (0) | 127 | s_0 s_0 s_0 s_0 | 128 | s_1 s_1 s_1 \\ | 129 | . . \\ {1, 0, f}0 | 130 | . . {2, 1, s_0}1 | 131 | . . \\ | 132 | s_i s_i {2, 1, 0, f}1 | 133 | . \\ | 134 | . {i+1, i, s_i-1}i | 135 | . \\ | 136 | s_n {i+1, i, i-1, ..., 1, 0, f}i | 137 | \\ | 138 | {n+1, n, s_n-1}n | 139 | \\ | 140 | {n+1, n, n-1, ..., 1, 0, f}n | 141 +-------------------------------------------------------------+ 142 Figure 1. RAs in S-BGP. 144 The main concern about deploying S-BGP in practice is the huge 145 computational cost for signing and verifying signatures. The 146 dominating barrier for adopting S-BGP is the overhead of processing 147 RAs, that is to authenticate paths. Toward this direction, there are 148 a bunch of solutions for reducing the overhead of path 149 authentication. 151 soBGP [I-D.ng-sobgp-bgp-extensions] maintains all authenticated AS 152 edges in a database, but faces the problem of forged paths. IRV [IRV] 153 builds an authentication server in each AS, but brings the problem of 154 maintaining and inter-connecting these servers, and introduces query 155 latencies. SPV [SPV] accelerates the signing process by pre-generated 156 one-time signatures based on a single root value, but involves a 157 significant amount of state information, and its security can only be 158 guaranteed probabilistically. Signature Amortization (S-A) [SA] uses 159 one bit vector for each neighbor of an AS to indicate the allowed 160 recipients of a route, such that only one signing is needed for 161 multiple recipients. However, each AS will need to pre-establish a 162 neighbor list corresponding to the bit vector, and to distribute it 163 to all other ASes. 165 As we can see, existing methods usually compromise security, and most 166 of them only improve the performance of signing. However, 167 verification happens more frequently than signing, since one 168 signature often needs to be verified at multiple places. 170 According to the above analysis, it is important to design an 171 efficient method to secure AS paths. Our solution, FS-BGP, builds on 172 the assumption that a PKI is ready for use, and focuses on AS path 173 authentication. 175 4. Secure Feasible AS Paths 177 S-BGP can not prevent replay of outdated routes. It can only use 178 expiration-date to roughly control the window of exposure to replay 179 attack. As a result, though it only signs currently announcing path, 180 it actually authenticates all announced feasible paths. Under a 181 stable AS-level topology, we call a path feasible when the path 182 satisfies the import and export policies of all ASes along the path. 184 Since failures often occur in the global routing system, many 185 feasible paths can be easily announced and become authenticated. 186 Thus, if a protocol can guarantee that all authenticated paths are 187 feasible path, then it can achieve similar level of security as S- 188 BGP. So we wonder that is it possible to efficiently secure feasible 189 paths but not blindly sign every currently announcing path. 191 BGP is a policy-based routing protocol. An AS only exports a route to 192 a neighbor if it is willing to forward traffic to the corresponding 193 prefix from that neighbor. Although complex policies (i.e., route 194 filters [RFC2622]) exist, AS usually does not differentiate between 195 prefixes or nonadjacent ASes. For example, in Figure 2, when AS n 196 decides whether routes learned from AS n-1 can be exported to AS n+1, 197 it only considers its relation with the two neighbors, but does not 198 consider other ASes along the path (). We call this 199 the Neighbor Based Importing and Exporting (NBIE). 201 +----------------------------------------------------------+ 202 | / ... (x_0) ... \ | 203 | / . \ | 204 | (n+1) <-- (n) <-- (n-1) <-- ... . ... <-- (0) | 205 | \ . / | 206 | \ ... (x_k) ... / | 207 +----------------------------------------------------------+ 208 Figure 2. In S-BGP, AS n signs k paths which share a mutual 209 AS path segment . 211 NBIE abstracts the basic functionality of BGP. According to our 212 measurement results in whois database, only a small portion of 213 routing polices (route filters) violate the NBIE assumption. 214 Nevertheless, the purpose of route filters is to protect the routing 215 system against distribution of inaccurate routing information 216 [RFC2622]. In other words, the use of route filters is mainly due to 217 security considerations rather than policy requirements. We believe 218 that under a security environment (i.e., FS-BGP or S-BGP), these 219 filters are not needed any more. In deed, our schema can flexibly 220 support complicated routing polices [TR-FSBGP]. 222 5. FS-BGP: Fast Secure BGP 224 5.1. Signing Critical AS Path Segments 226 Following our key observation above, we propose Fast Secure BGP (FS- 227 BGP) to grantee the authentication of feasible paths. Given a 228 feasible path p=, we define its set of critical path 229 segments as c_i, 0 , for i=0 232 c_i = 233 \ , for 0 actually describes an routing export policy of 238 its owner AS i, and implies that AS i can export all routes imported 239 from AS i-1 to AS i+1. 241 More specifically, FS-BGP uses Critical Segment Attestations (CSA) to 242 authenticate paths. A CSA is simply the signature of the critical 243 path segment signed by its owner. In a path p=, the 244 CSA s_i signed by AS i is defined as: 246 / {1,0,f}0 , for i=0 247 s_i = 248 \ {i+1,i,i-1}i , for 0. 261 +------------------------------------------------------------+ 262 | (n+1) <-- (n) <-- ... <-- (i) <-- ... <-- (1) <-- (0) | 263 | s_0 s_0 s_0 s_0 | 264 | s_1 s_1 s_1 \\ | 265 | . . \\ {1,0,f}0 | 266 | . . {2,1,0}1 | 267 | . . | 268 | s_i s_i | 269 | . \\ | 270 | . {i+1,i,i-1}i | 271 | . | 272 | s_n | 273 | \\ | 274 | {n+1,n,n-1}n | 275 +------------------------------------------------------------+ 276 Figure 3. CSAs in FS-BGP. 278 We argue that, under the NBIE rule, if every AS along a path signs 279 its critical path segment, then the path can be authenticated as a 280 feasible path [TR-FSBGP]. However, since not all feasible paths are 281 actually announced, it is possible to forge a path if the security 282 mechanism relies on CSA only, as shown in Section 5.2. We will 283 provide effective solution to this problem. 285 5.2. Prevent Effective Hijacking in FS-BGP 287 In FS-BGP, an AS using FS-BGP can forge paths that are not actually 288 announced by others, but avoids CSA based detection. Forged paths can 289 be constructed by concatenating critical segments, and used for 290 prefix hijacking. 292 Although forging paths in FS-BGP is possible, there are still some 293 restrictions on how paths can be forged. First, a path can only be 294 forged by combining non-forged paths which share mutual segments. 295 Second, some part of a forged path must be treated as sub-optimal or 296 suppressed by some AS along the path. Third, forged paths are still 297 feasible, and can only be used for prefixes associated with the 298 originating critical segment in the path. Last, forged paths can not 299 be very short [TR-FSBGP]. 301 Although there are limitations on forged paths, prefix hijacking is 302 still possible. In this section, we discuss solutions to prevent 303 prefix hijacking. We only concern effective hijacking, in a sense 304 that, the recipient of a forged route indeed changes its forwarding 305 path. 307 Firstly, we divide all feasible paths into three categories: 309 Optimal path: the best path that passes all the decision steps in 310 BGP. 312 Sub-optimal path: paths with the same Local Preference as the 313 optimal path, but not chosen as the best one. 315 Suppressed path: paths with lower Local Preferences than the 316 optimal and sub-optimal paths. For example, paths that are more 317 expensive (i.e., through a provider), are often suppressed by a 318 low preference. 320 We argue that, if a forged path is no shorter than the non-forged 321 path BGP should announce, it can not be used for effective hijacking 322 [TR-FSBGP]. Under a stable AS-level topology, a router will use its 323 optimal path for every prefix. If BGP is purely a shortest path 324 routing protocol (optimal path is always the shortest one), 325 manipulator can not effectively hijack any prefix by forging paths. 326 However, policy routing makes hijacking possible. 328 We know only suppressed path can be shorter than the optimal path 329 (since a sub-optimal path has the same local preference as the 330 optimal path, its length can not be shorter). Thus, if there is a 331 mechanism to guarantee that all suppressed paths are no shorter than 332 their corresponding optimal paths, manipulator can no longer 333 effectively hijack a prefix either. This idea can be implemented by 334 using AS Path Pre-pending (ASPP). 336 We call such a mechanism Suppressed Path Padding (SPP), and Figure 4 337 depicts the pseudo code for deciding how many times an AS i should 338 pad itself in a path. If a path is imported from a neighbor AS i-1 339 with the highest local preference, AS i only appears once (line 1 and 340 2). Otherwise, the number of occurrences k_i must be large enough 341 such that no suppressed path can be shorter than the corresponding 342 optimal path. Given a path p, denote the optimal path to the same 343 prefix as p by opt(p), then k_i is set as the largest Path Length 344 difference between any suppressed path p imported from this neighbor 345 and the corresponding opt(p) (line 4 to 7). 347 +-----------------------------------------------------------+ 348 | Algorithm: Suppressed Path Padding | 349 | INPUT: local AS i, neighbor AS i-1 | 350 | OUTPUT: k_i: number of times that AS i needs to be padded | 351 | in the paths import from AS i-1 | 352 | 1: IF AS i-1 has the highest local preference THEN | 353 | 2: RETURN 1 | 354 | 3: k_i <- 1 | 355 | 4: FOR ALL path p imported from AS i-1 DO | 356 | 5: opt(p) <- the optimal path corresponding to p | 357 | 6: IF length(p) - length(opt(p)) > k_i THEN | 358 | 7: k_i <- length(p) - length(opt(p)) | 359 | 8: RETURN k_i | 360 +-----------------------------------------------------------+ 361 Figure 4. SPP (Suppressed Path Padding). 363 It is worth noting that, SPP is quite general. When necessary, it can 364 and also should be used even in S-BGP. Consider the case when the 365 optimal route fails. At this time, S-BGP will announce a previously 366 sub-optimal or suppressed path temporarily, and this path can be used 367 later by the manipulator to launch an effective attack, if it is 368 short enough. S-BGP can not prevent this attack, while our SPP works 369 effectively. 371 6. Security Considerations 373 The entire document is about security consideration. More theoretical 374 analysis and experiment results can be found in our technical report 375 [TR-FSBGP]. 377 7. IANA Considerations 379 This document requires no IANA actions. 381 8. Conclusions 383 This draft proposes Fast Secure BGP (FS-BGP), an efficient mechanism 384 for securing feasible AS paths and preventing prefix hijacking by 385 signing critical AS path segments. We believe that FS-BGP can achieve 386 similar level of security as S-BGP. Our experiment results show that, 387 FS-BGP has a much higher efficiency. 389 9 References 390 9.1 Normative References 392 [RFC2622] Alaettinoglu, C., Villamizar, C., Gerich, E., Kessens, D., 393 Meyer, D., Bates, T., Karrenberg, D., and M. Terpstra, 394 "Routing Policy Specification Language (RPSL)", RFC 2622, 395 June 1999. 397 [RFC4271] Rekhter, Y., Ed., Li, T., Ed., and S. Hares, Ed., "A 398 Border Gateway Protocol 4 (BGP-4)", RFC 4271, January 399 2006. 401 [S-BGP] S. Kent, C. Lynn, J. Mikkelson, and K. Seo, "Secure Border 402 Gateway Protocol (S-BGP)", IEEE Journal on Selected Areas 403 in Communications, 18:103-116, 2000. 405 [I-D.lepinski-bgpsec-protocol] M. Lepinski, "BGPSEC Protocol 406 Specification", draft-lepinski-bgpsec-protocol, work-in- 407 progress, 2011. 409 [I-D.ng-sobgp-bgp-extensions] J. Ng, "Extensions to BGP to Support 410 Secure Origin BGP (soBGP)", draft-ng-sobgp-bgp-extensions, 411 2004. 413 [IRV] G. Goodell, W. Aiello, T. Griffin, J. Ioannidis, P. D. 414 McDaniel, and A. D. Rubin, "Working around BGP: An 415 Incremental Approach to Improving Security and Accuracy in 416 Interdomain Routing", In NDSS, 2003. 418 [psBGP] P. C. van Oorschot, T. Wan, and E. Kranakis, "On 419 interdomain routing security and pretty secure BGP 420 (psBGP)", ACM Trans. Inf. Syst. Secur., 10(3), 2007. 422 [SPV] Y.-C. Hu, A. Perrig, and M. A. Sirbu, "SPV: secure path 423 vector routing for securing BGP", In SIGCOMM, pages 179- 424 192, 2004. 426 [SA] D. M. Nicol, S. W. Smith, and M. Zhao, "Evaluation of 427 efficient security for BGP route announcements using 428 parallel simulation", Simulation Modeling Practice and 429 Theory, 12(3-4):187-216, 2004. 431 [TR-FSBGP] Yang Xiang, Zhiliang Wang, Xia Yin, Xingang Shi, and 432 Jianping Wu, "FS-BGP: An Efficient Approach to Securing AS 433 Paths", Tsinghua University, Technical Report, THUTR-2011- 434 FSBGP, 2011. 436 9.2 Informative References 438 [Whisper] L. Subramanian, V. Roth, I. Stoica, S. Shenker, and R. H. 439 Katz, "Listen and Whisper: Security Mechanisms for BGP", In NSDI, 440 pages 127-140, 2004. 442 [PGBGP] J. Karlin, S. Forrest, and J. Rexford, "Pretty Good BGP: 443 Improving BGP by Cautiously Adopting Routes", In ICNP, pages 290-299, 444 2006. 446 Authors' Addresses 448 Xia Yin 449 Tsinghua University, Beijing, 100084 P.R. China 451 Email: yxia@csnet1.cs.tsinghua.edu.cn 453 Yang Xiang 454 Tsinghua University, Beijing, 100084 P.R. China 456 Email: xiangy08@csnet1.cs.tsinghua.edu.cn 458 Zhiliang Wang 459 Tsinghua University, Beijing, 100084 P.R. China 461 Email: wzl@csnet1.cs.tsinghua.edu.cn 463 Jianping Wu 464 Tsinghua University, Beijing, 100084 P.R. China 466 Email: jianping@csnet1.cs.tsinghua.edu.cn