Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Computational complexity of traffic hijacking under BGP and S-BGP
Université catholique du Louvain, Belgium.ORCID iD: 0000-0002-9675-9729
2015 (English)In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 600, p. 143-154Article in journal (Refereed) Published
Abstract [en]

Harmful Internet hijacking incidents put in evidence how fragile interdomain routing is. In particular, the Border Gateway Protocol (BGP), which is used to exchange routing information between Internet entities, called Autonomous Systems (ASes), proved to be prone to attacks launched by a single malicious AS. Recent research contributions pointed out that even S-BGP, the secure variant of BGP that is being deployed, is not fully able to blunt traffic attraction attacks. Given a traffic flow between two ASes, we study how difficult it is for a malicious AS to devise a strategy for hijacking or intercepting that flow. The goal of the attack is to attract a traffic flow towards the malicious AS. While in the hijacking attack connectivity between the endpoints of a flow can be disrupted, in the interception attack connectivity must be maintained. We show that this problem marks a sharp difference between BGP and S-BGP. Namely, while it is solvable, under reasonable assumptions, in polynomial time for the type of attacks that are usually performed in BGP, it is NP-hard for S-BGP. Our study has several by-products. E.g., we solve a problem left open in the literature, stating when performing a hijacking in S-BGP is equivalent to performing an interception.

Place, publisher, year, edition, pages
Elsevier, 2015. Vol. 600, p. 143-154
Keywords [en]
Interdomain routing, Routing stability, Network protocols, BGP, Hijacking attack, Interception attack, Computational complexity
National Category
Communication Systems Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-222328DOI: 10.1016/j.tcs.2015.07.038ISI: 000362131800012Scopus ID: 2-s2.0-84941259471OAI: oai:DiVA.org:kth-222328DiVA, id: diva2:1180764
Note

QC 20180207

Available from: 2018-02-06 Created: 2018-02-06 Last updated: 2018-02-07Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Chiesa, Marco
In the same journal
Theoretical Computer Science
Communication SystemsComputer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 6 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf