Counter-RAPTOR: Safeguarding Tor Against Active Routing Attacks

Yixin Sun, Anne Edmundson, Nick Feamster, Mung Chiang, Prateek Mittal

TL;DR

Counter-RAPTOR introduces a two-pronged defense—proactive relay selection and reactive BGP monitoring—to protect the Tor network from active routing attacks. By prioritizing "resilient" Autonomous Systems (ASes) during guard relay selection, the system improves client security by an average of 36% with minimal impact on performance.

What Problem Does This Paper Address?

The Tor network relies on anonymity through layered encryption, but it has a "network-level" Achilles' heel. If an adversary can observe both the entry point (guard relay) and the exit point of a Tor circuit, they can use traffic correlation (matching packet timing and sizes) to deanonymize the user.

While previous research focused on passive adversaries who happen to be on the path, the recent RAPTOR attacks showed that malicious Autonomous Systems (ASes) can use active BGP hijacking or interception to intentionally pull Tor traffic through their infrastructure. Current Tor relay selection algorithms prioritize high bandwidth but ignore how easily an AS can be "spoofed" or hijacked via BGP. This paper addresses the lack of BGP-awareness in Tor’s design.

Methods

The authors propose a framework consisting of three main components:

  1. Resilience Measurement: They adapted existing AS-resilience metrics to the Tor ecosystem. They specifically developed a new extension to measure resilience against interception attacks, where an attacker doesn't just drop traffic but stealthily forwards it to the intended destination after inspecting it.
  2. Proactive Defense (Counter-RAPTOR): They designed a new guard relay selection algorithm. Instead of choosing guards based solely on bandwidth, it incorporates a resilience score $R(i)$. The algorithm uses a tunable parameter ($\alpha$) to balance security and performance and employs Tille’s algorithm for unequal probability sampling to prevent "fingerprinting" attacks that might reveal a client's location based on their unique relay preferences.
  3. Reactive Defense (BGP Monitoring): They built a live monitoring system that ingests BGP updates from BGPStream. It uses three detection analytics:
  4. Origin AS Check: Verifying if the AS announcing a prefix actually owns it.
  5. Frequency Analytic: Flagging ASes that rarely announce a specific prefix.
  6. Time Analytic: Flagging announcements that last for unusually short durations (typical of hijacks).

Datasets

  • Tor Consensus Data: Hourly snapshots of the Tor network relays and their bandwidth.
  • CAIDA AS Topology: Used to infer the relationships (provider-customer, peer-to-peer) between over 52,000 ASes.
  • BGPStream: A live feed of BGP announcements and withdrawals.
  • Team Cymru & Maxmind: Used for IP-to-ASN and GeoIP mappings.
  • Shadow Emulator: Used for large-scale network performance evaluation.

Key Insights and Ideas

  • The Bandwidth-Resilience Paradox: ASes with the highest Tor bandwidth (like OVH) often have lower resilience. This is because they are often "stub" or near-stub networks with many providers and peers but few customers, making it easier for an external attacker to hijack their prefixes.
  • Location Matters: Resilience is highly heterogeneous. A relay might be very secure for a client in one country but easily hijacked for a client in another, depending on the BGP paths between them.
  • Interception vs. Hijack: Interception attacks are harder to execute because the attacker must satisfy a "safety condition"—they need a valid path back to the true origin that doesn't loop through the hijacked path. Consequently, the network is generally more resilient to interception than simple hijacking.
  • Anonymity vs. Security Trade-off: Changing relay selection probabilities can potentially leak information about a client's location (fingerprinting). The authors mitigate this by using randomized sampling and showing that the entropy loss is negligible (around 2-4%).

Key Results

  • Security Gains: The Counter-RAPTOR selection algorithm improved the probability of a client being resilient to hijacks by 36% on average, with some clients seeing improvements as high as 166%.
  • Performance: In Shadow emulator tests, the system showed minimal performance loss for 320KB and 5MB downloads compared to the "Vanilla" Tor implementation.
  • Detection Accuracy: The monitoring system achieved a low false positive rate of 0.19%. It successfully detected 100% of simulated attacks and a real-world hijack performed by the researchers using the PEERING testbed.

Limitations and Future Work

  • AS Path Inference: The resilience calculations rely on predicting BGP paths using "Gao-Rexford" incentives (e.g., preferring customers over peers). However, real-world BGP policy is often more complex and opaque, which can lead to inaccuracies in path prediction.
  • Monitoring Pollution: While the monitoring system is effective, the authors note that a "benign" list of known multi-homed prefixes would be necessary to further reduce false alerts.
  • Adversarial Adaptation: A sophisticated attacker might try to "poison" the monitoring analytics by making their attacks look like normal, frequent routing changes. Future work is needed to make these analytics more robust against such strategic evasion.

Summary updated

Abstract

Tor is vulnerable to network-level adversaries who can observe both ends of the communication to deanonymize users. Recent work has shown that Tor is susceptible to the previously unknown active BGP routing attacks, called RAPTOR attacks, which expose Tor users to more network-level adversaries. In this paper, we aim to mitigate and detect such active routing attacks against Tor. First, we present a new measurement study on the resilience of the Tor network to active BGP prefix attacks. We show that ASes with high Tor bandwidth can be less resilient to attacks than other ASes. Second, we present a new Tor guard relay selection algorithm that incorporates resilience of relays into consideration to proactively mitigate such attacks. We show that the algorithm successfully improves the security for Tor clients by up to 36% on average (up to 166% for certain clients). Finally, we build a live BGP monitoring system that can detect routing anomalies on the Tor network in real time by performing an AS origin check and novel detection analytics. Our monitoring system successfully detects simulated attacks that are modeled after multiple known attack types as well as a real-world hijack attack (performed by us), while having low false positive rates.
BibTeX
@inproceedings{sun2017counter,
  author = {Yixin Sun and Anne Edmundson and Nick Feamster and Mung Chiang and Prateek Mittal},
  title = {{Counter-RAPTOR: Safeguarding Tor Against Active Routing Attacks}},
  booktitle = {IEEE Symposium on Security and Privacy},
  year = {2017},
  url = {https://openreview.net/forum?id=sP_ashU1Fx},
}

Loading related content...

Figure