An official website of the United States government
Abstract The popularity of Tor has made it an attractive target for a variety of deanonymization and fingerprinting attacks. Location-based path selection algorithms have been proposed as a countermeasure to defend against such attacks. However, adversaries can exploit the location-awareness of these algorithms by strategically placing relays in locations that increase their chances of being selected as a client’s guard. Being chosen as a guard facilitates website fingerprinting and traffic correlation attacks over extended time periods. In this work, we rigorously define and analyze the guard placement attack . We present novel guard placement attacks and show that three state-of-the-art path selection algorithms—Counter-RAPTOR, DeNASA, and LASTor—are vulnerable to these attacks, overcoming defenses considered by all three systems. For instance, in one attack, we show that an adversary contributing only 0.216% of Tor’s total bandwidth can attain an average selection probability of 18.22%, 84× higher than what it would be under Tor currently. Our findings indicate that existing location-based path selection algorithms allow guards to achieve disproportionately high selection probabilities relative to the cost required to run the guard. Finally, we propose and evaluate a generic defense mechanism that provably defends any path selection algorithm against guard placement attacks. We run our defense mechanism on each of the three path selection algorithms, and find that our mechanism significantly enhances the security of these algorithms against guard placement attacks with only minimal impact to the goals or performance of the original algorithms.
more »
« less
DeNASA: Destination-Naive AS-Awareness in Anonymous Communications
Abstract Prior approaches to AS-aware path selection in Tor do not consider node bandwidth or the other characteristics that Tor uses to ensure load balancing and quality of service. Further, since the AS path from the client’s exit to her destination can only be inferred once the destination is known, the prior approaches may have problems constructing circuits in advance, which is important for Tor performance. In this paper, we propose and evaluate DeNASA, a new approach to AS-aware path selection that is destination-naive, in that it does not need to know the client’s destination to pick paths, and that takes advantage of Tor’s circuit selection algorithm. To this end, we first identify the most probable ASes to be traversed by Tor streams. We call this set of ASes the Suspect AS list and find that it consists of eight highest ranking Tier 1 ASes. Then, we test the accuracy of Qiu and Gao AS-level path inference on identifying the presence of these ASes in the path, and we show that inference accuracy is 90%. We develop an AS-aware algorithm called DeNASA that uses Qiu and Gao inference to avoid Suspect ASes. DeNASA reduces Tor stream vulnerability by 74%. We also show that DeNASA has performance similar to Tor. Due to the destination-naive property, time to first byte (TTFB) is close to Tor’s, and due to leveraging Tor’s bandwidth-weighted relay selection, time to last byte (TTLB) is also similar to Tor’s.
more »
« less
- Award ID(s):
- 1423163
- PAR ID:
- 10018814
- Date Published:
- Journal Name:
- Proceedings on Privacy Enhancing Technologies
- Volume:
- 2016
- Issue:
- 4
- ISSN:
- 2299-0984
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Tor users derive anonymity in part from the size of the Tor user base, but Tor struggles to attract and support more users due to performance limitations. Previous works have proposed modifications to Tor’s path selection algorithm to enhance both performance and security, but many proposals have unintended consequences due to incorporating information related to client location. We instead propose selecting paths using a global view of the network, independent of client location, and we propose doing so with a machine learning classifier to predict the performance of a given path before building a circuit. We show through a variety of simulated and live experimental settings, across different time periods, that this approach can significantly improve performance compared to Tor’s default path selection algorithm and two previously proposed approaches. In addition to evaluating the security of our approach with traditional metrics, we propose a novel anonymity metric that captures information leakage resulting from location-aware path selection, and we show that our path selection approach leaks no more information than the default path selection algorithm.more » « less
-
We study the problem of load-balancing in path selection in anonymous networks such as Tor. We first find that the current Tor path selection strategy can create significant imbalances. We then develop a (locally) optimal algorithm for selecting paths and show, using flow-level simulation, that it results in much better balancing of load across the network. Our initial algorithm uses the complete state of the network, which is impractical in a distributed setting and can compromise users' privacy. We therefore develop a revised algorithm that relies on a periodic, differentially private summary of the network state to approximate the optimal assignment. Our simulations show that the revised algorithm significantly outpe forms the current strategy while maintaining provable privacy guarantees.more » « less
-
The trajectory-aware lowest-cost path selection problem aims to find the lowest-cost path using trajectory data. Trajectory data is valuable since it carries information about travel cost along paths, and also reflects travelers' routing preference. Path-centric travel cost estimation models using trajectory data grows popular recently, which considers the auto-correlation of the energy consumption on different segments of a path. However, path-centric models are more computationally expensive than edge-centric models. The main challenge of this problem is that the travel cost of every candidate path explored during the process of searching for the lowest-cost path need to be estimated, resulting in high computational cost. The current path selection algorithms that use path-centric cost estimation models still follow the pattern of "path + edge" when exploring candidate paths, which may result in redundant computation. We introduce a trajectory-aware graph model in which each node is a maximal trajectory-aware path. Two nodes in the trajectory-aware graph are linked by an edge if their union forms a trajectory-union path. We then propose a path selection algorithm to find a path in the proposed trajectory-aware graph which corresponds to the lowest-cost path in the input spatial network. We prove theoretically the proposed algorithm is correct and complete. Moreover, we prove theoretically that the proposed path selection algorithm cost much less computational time than the algorithm used in the related work, and validate it through experiments using real-world trajectory data.more » « less
-
The Border Gateway Protocol (BGP) is a distributed protocol that manages interdomain routing without requiring a centralized record of which autonomous systems (ASes) connect to which others. Many methods have been devised to infer the AS topology from publicly available BGP data, but none provide a general way to handle the fact that the data are notoriously incomplete and subject to error. This paper describes a method for reliably inferring AS-level connectivity in the presence of measurement error using Bayesian statistical inference acting on BGP routing tables from multiple vantage points. We employ a novel approach for counting AS adjacency observations in the AS-PATH attribute data from public route collectors, along with a Bayesian algorithm to generate a statistical estimate of the AS-level network. Our approach also gives us a way to evaluate the accuracy of existing reconstruction methods and to identify advantageous locations for new route collectors or vantage points.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1515/popets-2016-0044
