Skip to main content

Fast route attestation on AS Path Segment
draft-yang-sidr-fra-02

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 2017-02-16 (Latest revision 2016-12-28)
RFC stream (None)
Formats
Additional resources
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-02
Internet Engineering Task Force                                Yang, Ed.
Internet-Draft                                                       Shi
Intended status: Informational                                     Xiang
Expires: August 20, 2017                                            Wang
                                                                      Wu
                                                                     Yin
                                                          Tsinghua Univ.
                                                       February 16, 2017

               Fast route attestation on AS Path Segment
                         draft-yang-sidr-fra-02

Abstract

   This draft proposes Fast Route Attestation (FRA), an efficient
   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 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.

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 August 20, 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

Yang, et al.             Expires August 20, 2017                [Page 1]
Internet-Draft                     FRA                     February 2017

   publication of this document.  Please review these documents
   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 period  . . . . . . .   8
     4.4.  Contents of FRA Certificates  . . . . . . . . . . . . . .   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 and correctness in
   advance.  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 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

Yang, et al.             Expires August 20, 2017                [Page 2]
Internet-Draft                     FRA                     February 2017

   [TR-FSBGP].  Analysis, evaluations, and more discussions of FRA can
   be found in the recent technical report [TR-FSBGP].

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 originated from AS 0

   <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 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, 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 August 20, 2017                [Page 3]
Internet-Draft                     FRA                     February 2017

   +-------------------------------------------------------------+
   | (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: RA in BGPSec.

   The main concern about deploying 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.

   Besides, when BGPSec is partial-deployed, it can only improve limited
   security benefits.  This influence the deployment of BGPSec

Yang, et al.             Expires August 20, 2017                [Page 4]
Internet-Draft                     FRA                     February 2017

   seriously.  Many ISPs insist that unless majority of ASes deploys
   BGPSec, they would not benefit much from deploying BGPSec.

   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 path are
   authenticated, attackers can only attract little traffic by forging
   other part 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 interdomain routing
   security before BGPSec is fully deployed.

   Though Path-End Validation provides a way to improve interdomain
   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 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, FRA, builds on the assumption that
   RPKI has been used for origin authentication, focusing 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
   (<n-2, ..., 1, 0>).  We call this the Neighbor Based Importing and
   Exporting (NBIE).

Yang, et al.             Expires August 20, 2017                [Page 5]
Internet-Draft                     FRA                     February 2017

   +----------------------------------------------------------+
   |                              / ... (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
   security considerations rather than policy requirements.  We believe
   that under a security environment (i.e., FRA/FS-BGP or BGPSec), more
   ASes will not need these filters.  In deed, our schema can also
   flexibly support complicated routing polices [TR-FSBGP].

4.2.  Signing Critical AS Path Segments efficiently

   Following our key observation above, we propose Fast Route
   Attestation (FRA) to guarantee the authenticate AS paths.  Given a
   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 as the owner of c_i.  Particularly, c_0 is called the
   originating critical path segment owned by AS 0.  Under NBIE policy,
   a critical path segment <i+1, i, i-1> 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=<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

Yang, et al.             Expires August 20, 2017                [Page 6]
Internet-Draft                     FRA                     February 2017

   Importantly, the prefixes f in s_0 is necessary, because AS 0 might
   be multi-homing and can only announce part of its prefixes to AS 1 to
   balance traffic.

   Indeed, FRA have much higher efficiency than BGPSec.  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, we can reduce the number of signing
   and verifying operations in FRA by 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>.  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 using FRA mechanism, the
   AS just signs critical path segment one time.

   +------------------------------------------------------------+
   |  (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.

   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, <n, n-1, ..., 0> is secure
   in BGPSec.  That is to say, ASes along the path all deploy BGPSec,
   signing and verifying the path.  If they use 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 path.  Because the CSA s_i (i.e.
   {i+1,i,i-1}i) means i+1 is the true next-hop, the forged update will
   be dropped.

Yang, et al.             Expires August 20, 2017                [Page 7]
Internet-Draft                     FRA                     February 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 use FRA
   mechanism, the path must be authenticated.  Considering its
   efficiency we discussed above, FRA can achieve similar level of
   security as S-BGP/BGPSec with less time cost.

4.3.  More benefits in partial-deployment period

   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 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 mechanism, it 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
   <n, ..., 0> is a 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
   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.  Besides, because
   FRA authenticates the whole path of BGP updates, it can provide a
   similar security benefit as BGPSec.

4.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.

Yang, et al.             Expires August 20, 2017                [Page 8]
Internet-Draft                     FRA                     February 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, 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.

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 when partially-
   deployed.  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 August 20, 2017                [Page 9]
Internet-Draft                     FRA                     February 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,
              <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.

   [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 August 20, 2017               [Page 10]
Internet-Draft                     FRA                     February 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 August 20, 2017               [Page 11]
Internet-Draft                     FRA                     February 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 August 20, 2017               [Page 12]