Efficient Secure BGP AS Path using FRA
draft-yang-sidr-fra-00
This document is an Internet-Draft (I-D).
Anyone may submit an I-D to the IETF.
This I-D is not endorsed by the IETF and has no formal standing in the
IETF standards process.
The information below is for an old version of the document.
| Document | Type |
This is an older version of an Internet-Draft whose latest revision state is "Expired".
|
|
|---|---|---|---|
| Authors | Yan Yang , Xingang Shi , Yang Xiang , Zhiliang Wang , Jianping Wu , Xia Yin | ||
| Last updated | 2016-12-24 | ||
| RFC stream | (None) | ||
| Formats | |||
| Stream | Stream state | (No stream defined) | |
| Consensus boilerplate | Unknown | ||
| RFC Editor Note | (None) | ||
| IESG | IESG state | I-D Exists | |
| Telechat date | (None) | ||
| Responsible AD | (None) | ||
| Send notices to | (None) |
draft-yang-sidr-fra-00
Internet Engineering Task Force Yang, Ed.
Internet-Draft Shi
Intended status: Informational Xiang
Expires: June 27, 2017 Wang
Wu
Yin
Tsinghua Univ.
December 24, 2016
Efficient Secure BGP AS Path using FRA
draft-yang-sidr-fra-00
Abstract
This draft proposes Fast Route Attestation (FRA), an efficient
mechanism for securing AS paths and preventing prefix hijacking by
signing critical AS path segments (i.e., adjacent AS triples). FRA
can achieve similar level of security as S-BGP/BGPSec, but with much
higher efficiency.
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 June 27, 2017.
Copyright Notice
Copyright (c) 2016 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
carefully, as they describe your rights and restrictions with respect
Yang, et al. Expires June 27, 2017 [Page 1]
Internet-Draft FRA December 2016
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. Secure Feasible AS Paths . . . . . . . . . . . . . . . . . . 5
5. FRA: Fast Route Attestation . . . . . . . . . . . . . . . . . 6
5.1. Signing Critical AS Path Segments . . . . . . . . . . . . 6
5.2. Prevent Effective Hijacking with FRA . . . . . . . . . . 7
5.3. Benefit in partial-deployment period . . . . . . . . . . 9
5.4. Contents of FRA Certificates . . . . . . . . . . . . . . 10
6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10
7. Security Considerations . . . . . . . . . . . . . . . . . . . 10
8. Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . 10
9. References . . . . . . . . . . . . . . . . . . . . . . . . . 11
9.1. Normative References . . . . . . . . . . . . . . . . . . 11
9.2. Informative References . . . . . . . . . . . . . . . . . 12
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 12
1. Introduction
In order to improve the security of BGP, several extensions have been
proposed, which fall into two categories: anomaly detection and
cryptographic based authentication. However, anomaly detection
approaches [Whisper] [PGBGP] can not guarantee security and
correctness. Cryptographic approaches, which are being pursued by
the SIDR WG, use the Public Key Infrastructure (PKI) to authenticate
routing announcements. There are a bunch of solutions including
S-BGP [S-BGP], BGPSec [RFC7353] and many others. 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
critical AS path segments (i.e., adjacent AS triples), FRA can
achieve similar level of security as S-BGP/BGPSec, but with much
higher efficiency. FRA is the critical part of FS-BGP [TR-FSBGP].
Analysis, evaluations, and more discussions can be found in the
recent technical report [TR-FSBGP].
Yang, et al. Expires June 27, 2017 [Page 2]
Internet-Draft FRA December 2016
2. Terminology
(i): AS i
<n, ..., 0>: AS path from AS n to the origin AS 0
<n, ..., 0>f: AS path of prefix f
<i+1, i, i-1>: critical AS path segment, adjacent AS triple in a path
<1, 0, f>: 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 can 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 uses a PKI
to help authenticating involved parties and messages. Specifically,
S-BGP uses Route Attestations (RAs) for path authentication. BGPSec
[RFC7353] also uses RAs to validate the path, which has been
standardized by IETF.
As shown in Figure 1, a 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 <i+1, i, ..., 0> 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 June 27, 2017 [Page 3]
Internet-Draft FRA December 2016
+-------------------------------------------------------------+
| (n+1) <-- (n) <-- ... <-- (i) <-- ... <-- (1) <-- (0) |
| s_0 s_0 s_0 s_0 |
| s_1 s_1 s_1 \\ |
| . . \\ {1, 0, f}0 |
| . . {2, 1, s_0}1 |
| . . \\ |
| s_i s_i {2, 1, 0, f}1 |
| . \\ |
| . {i+1, i, s_i-1}i |
| . \\ |
| s_n {i+1, i, i-1, ..., 1, 0, f}i |
| \\ |
| {n+1, n, s_n-1}n |
| \\ |
| {n+1, n, n-1, ..., 1, 0, f}n |
+-------------------------------------------------------------+
Figure 1: RAs in S-BGP/BGPSec.
The main concern about deploying S-BGP/BGPSec in practice is the huge
computational cost for signing and verifying signatures. The
dominating barrier for adopting them is the overhead of processing
RAs, that is to authenticate paths. Toward this direction, 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 one
signing is needed for multiple recipients. 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.
According to the above analysis, it is important to design an
efficient method to secure AS paths. Our solution, FRA, builds on
Yang, et al. Expires June 27, 2017 [Page 4]
Internet-Draft FRA December 2016
the assumption that a PKI is ready for use, and focuses on AS path
authentication.
4. Secure Feasible AS Paths
Both S-BGP and BGPSec can not prevent replay of outdated routes. It
can only use expiration-date to roughly control the window of
exposure to replay attack. As a result, though it only signs
currently announcing path, it actually authenticates all announced
feasible paths. Under a stable AS-level topology, we call a path
feasible when the path satisfies the import and export policies of
all ASes along the path.
Since failures often occur in the global routing system, many
feasible paths can be easily announced and become authenticated.
Thus, if a protocol can guarantee that all authenticated paths are
feasible path, then it can achieve similar level of security as S-
BGP/BGPSec. So we wonder that is it possible to efficiently secure
feasible paths but not blindly sign every currently announcing path.
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 between 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 the two
neighbors, but does not consider other ASes along the path (<n-2,
..., 1, 0>). We call this the Neighbor Based Importing and Exporting
(NBIE).
+----------------------------------------------------------+
| / ... (x_0) ... \ |
| / . \ |
| (n+1) <-- (n) <-- (n-1) <-- ... . ... <-- (0) |
| \ . / |
| \ ... (x_k) ... / |
+----------------------------------------------------------+
Figure 2: In BGPSec, AS n signs k paths which share a mutual AS path
segment <n+1, n, n-1>.
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 the 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
Yang, et al. Expires June 27, 2017 [Page 5]
Internet-Draft FRA December 2016
security considerations rather than policy requirements. We believe
that under a security environment (i.e., FRA/FS-BGP or BGPSec), these
filters are not needed any more. In deed, our schema can flexibly
support complicated routing polices [TR-FSBGP].
5. FRA: Fast Route Attestation
5.1. Signing Critical AS Path Segments
Following our key observation above, we propose Fast Route
Attestation (FRA) to guarantee the authentication of feasible paths.
Given a feasible path p=<n+1, n, ..., 0>, we define its set of
critical path segments as c_i, 0<i<=n, where
/ <1,0,f> , for i=0
c_i =
\ <i+1,i,i-1> , for 0<i<=n
We call AS i the owner of c_i. Particularly, c_0 is called the
originating critical path segment owned by AS 0. A critical path
segment <i+1, i, i-1> actually describes an routing export policy of
its owner AS i, and implies that AS i can export 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=<n+1, n, ..., 0>, 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<i<=n
The inclusion of the prefixes f in s_0 is necessary, because AS 0
might be multi-homing and only announces part of its prefixes to AS
1. Figure 3 and Figure 1 compare the signatures in FRA and BGPSec.
Obviously, the number of distinct critical path segments is far less
than the number of distinct paths. As a result, the number of
signing and verification operations in FRA can be greatly reduced,
after using a small cache. In Figure 2, AS n needs to sign each of
the k paths individually in BGPSec. However, in FRA, all the k
different paths can reuse one signature of the common critical
segment <n+1, n, n-1>.
Yang, et al. Expires June 27, 2017 [Page 6]
Internet-Draft FRA December 2016
+------------------------------------------------------------+
| (n+1) <-- (n) <-- ... <-- (i) <-- ... <-- (1) <-- (0) |
| s_0 s_0 s_0 s_0 |
| s_1 s_1 s_1 \\ |
| . . \\ {1,0,f}0 |
| . . {2,1,0}1 |
| . . |
| s_i s_i |
| . \\ |
| . {i+1,i,i-1}i |
| . |
| s_n |
| \\ |
| {n+1,n,n-1}n |
+------------------------------------------------------------+
Figure 3: CSAs in FRA.
We argue that, under the NBIE rule, if every AS along a path signs
its critical path segment, then the path can be authenticated as a
feasible path [TR-FSBGP]. However, since not all feasible paths are
actually announced, it is possible to forge a path if the security
mechanism relies on CSA only, as shown in Section 5.2. We will
provide effective solution to this problem.
5.2. Prevent Effective Hijacking with FRA
Under FRA, an AS can still forge paths that are not actually
announced by others, but avoids CSA based detection. Forged paths
can be constructed by concatenating critical segments, and used for
prefix hijacking.
Although forging paths under FRA is possible, there are still some
restrictions on how paths can be forged. First, a path can only be
forged by combining non-forged paths which share mutual segments.
Second, some part of a forged path must be treated as sub-optimal or
suppressed by some AS along the path. Third, forged paths are still
feasible, and can only be used for prefixes associated with the
originating critical segment in the path. Last, forged paths can not
be very short [TR-FSBGP].
Although there are limitations on forged paths, prefix hijacking is
still possible. In this section, we discuss solutions to prevent
prefix hijacking. We only concern effective hijacking, in a sense
that, the recipient of a forged route indeed changes its forwarding
path.
Firstly, we divide all feasible paths into three categories:
Yang, et al. Expires June 27, 2017 [Page 7]
Internet-Draft FRA December 2016
Optimal path: the best path that passes all the decision steps in
BGP.
Sub-optimal path: paths with the same Local Preference as the
optimal path, but not chosen as the best one.
Suppressed path: paths with lower Local Preferences than the
optimal and sub-optimal paths. For example, paths that are more
expensive (i.e., through a provider), are often suppressed by a
low preference.
We argue that, if a forged path is no shorter than the non-forged
path BGP should announce, it can not be used for effective hijacking
[TR-FSBGP]. Under a stable AS-level topology, a router will use its
optimal path for every prefix. If BGP is purely a shortest path
routing protocol (optimal path is always the shortest one),
manipulator can not effectively hijack any prefix by forging paths.
However, policy routing makes hijacking possible.
We know only suppressed path can be shorter than the optimal path
(since a sub-optimal path has the same local preference as the
optimal path, its length can not be shorter). Thus, if there is a
mechanism to guarantee that all suppressed paths are no shorter than
their corresponding optimal paths, manipulator can no longer
effectively hijack a prefix either. This idea can be implemented by
using AS Path Pre-pending (ASPP).
We call such a mechanism Suppressed Path Padding (SPP), and Figure 4
depicts the pseudo code for deciding how many times an AS i should
pad itself in a path. If a path is imported from a neighbor AS i-1
with the highest local preference, AS i only appears once (line 1 and
2). Otherwise, the number of occurrences k_i must be large enough
such that no suppressed path can be shorter than the corresponding
optimal path. Given a path p, denote the optimal path to the same
prefix as p by opt(p), then k_i is set as the largest Path Length
difference between any suppressed path p imported from this neighbor
and the corresponding opt(p) (line 4 to 7).
Yang, et al. Expires June 27, 2017 [Page 8]
Internet-Draft FRA December 2016
+-----------------------------------------------------------+
| Algorithm: Suppressed Path Padding |
| INPUT: local AS i, neighbor AS i-1 |
| OUTPUT: k_i: number of times that AS i needs to be padded |
| in the paths import from AS i-1 |
| 1: IF AS i-1 has the highest local preference THEN |
| 2: RETURN 1 |
| 3: k_i <- 1 |
| 4: FOR ALL path p imported from AS i-1 DO |
| 5: opt(p) <- the optimal path corresponding to p |
| 6: IF length(p) - length(opt(p)) > k_i THEN |
| 7: k_i <- length(p) - length(opt(p)) |
| 8: RETURN k_i |
+-----------------------------------------------------------+
Figure 4: SPP (Suppressed Path Padding).
It is worth noting that, SPP is quite general. When necessary, it
can and also should be used even in BGPSec. Consider the case when
the optimal route fails. At this time, BGPSec will announce a
previously sub-optimal or suppressed path temporarily, and this path
can be used later by the manipulator to launch an effective attack,
if it is short enough. BGPSec can not prevent this attack, while our
SPP works effectively.
5.3. Benefit in partial-deployment period
As the deployment of BGPSec is likely to coexist with legacy BGP for
a long time, we must consider the effects of BGPSec and FRA in
partial-deployment period. In general, when not fully deployed, FRA
can prevent more attacks than BGPSec.
Under BGPSec, one AS regards a route secure/insecure according to
those ASes along the path. Only if they all have deployed it, this
route is a secure route. However, if there is any AS which still
runs legacy BGP, the route is regarded as an insecure one.
But under FRA, the situations differ. 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
<n, ..., 0> is a feasible AS path of prefix f. If an attacker a
intends to forge a path <n, ..., i+1, a, i-1, ..., 0> 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 <a, i-1, i-2>. 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 users. Briefly speaking, even if it is during
Yang, et al. Expires June 27, 2017 [Page 9]
Internet-Draft FRA December 2016
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. When majority still runs legacy BGP,
FRA guarantees users better security than BGPSec.
5.4. Contents of FRA Certificates
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.
Based on RPKI [RFC6480], FRA can 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, the certificates also
include the private keys of ASes. ASes' public keys 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 CSAs
along the path. Thus, attackers cannot remove any CSAs to forge
path.
6. IANA Considerations
This document includes no request to IANA.
7. Security Considerations
The entire document is about security consideration. More
theoretical analysis and experiment results can be found in our
technical report [TR-FSBGP].
8. Conclusions
This draft proposes Fast Route Attestation (FRA), an efficient
mechanism for securing feasible AS paths and preventing prefix
hijacking by signing critical AS path segments. We believe that FS-
BGP can achieve similar level of security as S-BGP/BGPSec. Our
experiment results show that, FRA has a much higher efficiency.
Yang, et al. Expires June 27, 2017 [Page 10]
Internet-Draft FRA December 2016
9. References
9.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.
[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,
<http://www.rfc-editor.org/info/rfc2622>.
[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,
<http://www.rfc-editor.org/info/rfc4271>.
[RFC6480] Lepinski, M. and S. Kent, "An Infrastructure to Support
Secure Internet Routing", RFC 6480, DOI 10.17487/RFC6480,
February 2012, <http://www.rfc-editor.org/info/rfc6480>.
[RFC7353] Bellovin, S., Bush, R., and D. Ward, "Security
Requirements for BGP Path Validation", RFC 7353,
DOI 10.17487/RFC7353, August 2014,
<http://www.rfc-editor.org/info/rfc7353>.
[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.
Yang, et al. Expires June 27, 2017 [Page 11]
Internet-Draft FRA December 2016
[TR-FSBGP]
Xiang, Yang., Wang, Zhiliang., Yin, Xia., Shi, Xingang.,
and Jianping. Wu, "FS-BGP: An Efficient Approach to
Securing AS Paths", 2011.
9.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 June 27, 2017 [Page 12]
Internet-Draft FRA December 2016
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 June 27, 2017 [Page 13]