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:
- 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.
- 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.
- Reactive Defense (BGP Monitoring): They built a live monitoring system that ingests BGP updates from BGPStream. It uses three detection analytics:
- Origin AS Check: Verifying if the AS announcing a prefix actually owns it.
- Frequency Analytic: Flagging ASes that rarely announce a specific prefix.
- 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