A Survey on Routing in Anonymous Communication Protocols
---
paper_title: Dovetail: Stronger Anonymity in Next-Generation Internet Routing

paper_content:

Given current research initiatives advocating “clean slate” Internet designs, researchers have the opportunity to design an internetwork layer routing protocol that provides efficient anonymity by decoupling identity from network location. Prior work in anonymity for the next-generation Internet fully trusts the user’s ISP. We propose Dovetail, which provides anonymity against an active attacker located at any single point within the network, including the user’s ISP. A major design challenge is to provide this protection without including an applicationlayer proxy in data transmission. We address this in path construction by using a matchmaker node (an end host) to overlap two path segments at a dovetail node (a router). The dovetail then trims away part of the path so that data transmission bypasses the matchmaker. We develop a systematic mechanism to measure the topological anonymity of our designs, and we demonstrate their privacy and efficiency by Internet-scale simulations at the AS-level.
---
paper_title: LAP: Lightweight Anonymity and Privacy

paper_content:

Popular anonymous communication systems often require sending packets through a sequence of relays on dilated paths for strong anonymity protection. As a result, increased end-to-end latency renders such systems inadequate for the majority of Internet users who seek an intermediate level of anonymity protection while using latency-sensitive applications, such as Web applications. This paper serves to bridge the gap between communication systems that provide strong anonymity protection but with intolerable latency and non-anonymous communication systems by considering a new design space for the setting. More specifically, we explore how to achieve near-optimal latency while achieving an intermediate level of anonymity with a weaker yet practical adversary model (i.e., protecting an end-host's identity and location from servers) such that users can choose between the level of anonymity and usability. We propose Lightweight Anonymity and Privacy (LAP), an efficient network-based solution featuring lightweight path establishment and stateless communication, by concealing an end-host's topological location to enhance anonymity against remote tracking. To show practicality, we demonstrate that LAP can work on top of the current Internet and proposed future Internet architectures.
---
paper_title: A Taxonomy for Routing Protocols in Mobile Ad Hoc Networks

paper_content:

A Mobile Ad hoc NETwork (manet) is a mobile, multi-hop wireless ::: network which is capable of autonomous operation. It is characterized ::: by energy-constrained nodes, bandwidth-constrained, variable-capacity ::: wireless links and dynamic topology, leading to frequent and ::: unpredictable connectivity changes. ::: ::: In the absence of a fixed infrastructure, manet nodes cooperate to ::: provide routing services, relying on each other to forward packets to ::: their destination. Routing protocols designed for the fixed network ::: are not effective in the dynamic and resource-constrained manet ::: environment; many alternative routing protocols have been suggested. ::: ::: This report provides an overview of a number of manet routing ::: protocols. More importantly, it defines a taxonomy that is suitable ::: for examining a wide variety of protocols in a structured way and ::: exploring tradeoffs associated with various design choices. The ::: emphasis is on practical design and implementation issues rather than ::: complexity analysis.
---
paper_title: Statistical Disclosure Attacks

paper_content:

An improvement over the previously known disclosure attack is presented that allows, using statistical methods, to effectively deanonymize users of a mix system. Furthermore the statistical disclosure attack is computationally efficient, and the conditions for it to be possible and accurate are much better understood. The new attack can be generalized easily to a variety of anonymity systems beyond mix networks.
---
paper_title: Location diversity in anonymity networks

paper_content:

Anonymity networks have long relied on diversity of node location for protection against attacks---typically an adversary who can observe a larger fraction of the network can launch a more effective attack. We investigate the diversity of two deployed anonymity networks, Mixmaster and Tor, with respect to an adversary who controls a single Internet administrative domain. Specifically, we implement a variant of a recently proposed technique that passively estimates the set of administrative domains (also known as autonomous systems, or ASes) between two arbitrary end-hosts without having access to either end of the path. Using this technique, we analyze the AS-level paths that are likely to be used in these anonymity networks. We find several cases in each network where multiple nodes are in the same administrative domain. Further, many paths between nodes, and between nodes and popular endpoints, traverse the same domain.
---
paper_title: Sampled traffic analysis by internet-exchange-level adversaries

paper_content:

Existing low-latency anonymity networks are vulnerable to traffic analysis, so location diversity of nodes is essential to defend against attacks. Previous work has shown that simply ensuring geographical diversity of nodes does not resist, and in some cases exacerbates, the risk of traffic analysis by ISPs. Ensuring high autonomous-system (AS) diversity can resist this weakness. However, ISPs commonly connect to many other ISPs in a single location, known as an Internet eXchange (IX). This paper shows that IXes are a single point where traffic analysis can be performed. We examine to what extent this is true, through a case study of Tor nodes in the UK. Also, some IXes sample packets flowing through them for performance analysis reasons, and this data could be exploited to de-anonymize traffic. We then develop and evaluate Bayesian traffic analysis techniques capable of processing this sampled data.
---
paper_title: As-awareness in Tor path selection

paper_content:

Tor is an anonymous communications network with thousands of router nodes worldwide. An intuition reflected in much of the literature on anonymous communications is that, as an anonymity network grows, it becomes more secure against a given observer because the observer will see less of the network. In particular, as the Tor network grows from volunteers operating relays all over the world, it becomes less and less likely for a single autonomous system (AS) to be able to observe both ends of an anonymous connection. Yet, as the network continues to grow significantly, no analysis has been done to determine if this intuition is correct. Further, modifications to Tor's path selection algorithm to help clients avoid an AS-level observer have not been proposed and analyzed. Five years ago a previous study examined the AS-level threat against client and destination addresses chosen a priori to be likely or interesting to examine. Using an AS-level path inference algorithm with improved accuracy, more extensive Internet routing data, and, most importantly, a model of typical Tor client AS-level sources and destinations based on data gathered from the live network, we demonstrate that the threat of a single AS observing both ends of an anonymous Tor connection is greater than previously thought. We look at the growth of the Tor network over the past five years and show that its explosive growth has had only a small impact on the network's robustness against an AS-level attacker. Finally, we propose and evaluate the effectiveness of some simple, AS-aware path selection algorithms that avoid the computational overhead imposed by full AS-level path inference algorithms. Our results indicate that a novel heuristic we propose is more effective against an AS-level observer than other commonly proposed heuristics for improving location diversity in path selection.
---
paper_title: Low-resource routing attacks against tor

paper_content:

Tor has become one of the most popular overlay networks for anonymizing TCP traffic. Its popularity is due in part to its perceived strong anonymity properties and its relatively low latency service. Low latency is achieved through Tor's ability to balance the traffic load by optimizing Tor router selection to probabilistically favor routers with high bandwidth capabilities. We investigate how Tor's routing optimizations impact its ability to provide strong anonymity. Through experiments conducted on PlanetLab, we show the extent to which routing performance optimizations have left the system vulnerable to end-to-end traffic analysis attacks from non-global adversaries with minimal resources. Further, we demonstrate that entry guards, added to mitigate path disruption attacks, are themselves vulnerable to attack. Finally, we explore solutions to improve Tor's current routing algorithms and propose alternative routing strategies that prevent some of the routing attacks used in our experiments.
---
paper_title: Correlation-Based Traffic Analysis Attacks on Anonymity Networks

paper_content:

In this paper, we address attacks that exploit the timing behavior of TCP and other protocols and applications in low-latency anonymity networks. Mixes have been used in many anonymous communication systems and are supposed to provide countermeasures to defeat traffic analysis attacks. In this paper, we focus on a particular class of traffic analysis attacks, flow-correlation attacks, by which an adversary attempts to analyze the network traffic and correlate the traffic of a flow over an input link with that over an output link. Two classes of correlation methods are considered, namely time-domain methods and frequency-domain methods. Based on our threat model and known strategies in existing mix networks, we perform extensive experiments to analyze the performance of mixes. We find that all but a few batching strategies fail against flow-correlation attacks, allowing the adversary to either identify ingress and egress points of a flow or to reconstruct the path used by the flow. Counterintuitively, some batching strategies are actually detrimental against attacks. The empirical results provided in this paper give an indication to designers of Mix networks about appropriate configurations and mechanisms to be used to counter flow-correlation attacks.
---
paper_title: Mix-Networks with Restricted Routes

paper_content:

We present a mix network topology that is based on sparse expander graphs, with each mix only communicating with a few neighbouring others. We analyse the anonymity such networks provide, and compare it with fully connected mix networks and mix cascades. We prove that such a topology is efficient since it only requires the route length of messages to be relatively small in comparison with the number of mixes to achieve maximal anonymity. Additionally mixes can resist intersection attacks while their batch size, that is directly linked to the latency of the network, remains constant. A worked example of a network is also presented to illustrate how these results can be applied to create secure mix networks in practise. © Springer-Verlag Berlin Heidelberg 2003.
---
paper_title: ISDN-MIXes: Untraceable Communication with Very Small Bandwidth Overhead

paper_content:

Untraceable communication for services like telephony is often considered infeasible in the near future because of bandwidth limitations. We present a technique, called ISDN-Mixes, which shows that this is not the case.
---
paper_title: Route Fingerprinting in Anonymous Communications

paper_content:

Peer discovery and route set-up are an integral part of the processes by which anonymizing peer-to-peer systems are made secure. When systems are large, and individual nodes only gain random knowledge of part of the network, their traffic can be detected by the uniqueness of the information they have learnt. We discuss this problem, which occurred in the initial design of Tarzan, and other related problems from the literature.
---
paper_title: Bridging and Fingerprinting: Epistemic Attacks on Route Selection

paper_content:

Users building routes through an anonymization network must discover the nodes comprising the network. Yet, it is potentially costly, or even infeasible, for everyone to know the entire network. We introduce a novel attack, the route bridging attack, which makes use of what route creators do not know of the network. We also present new discussion and results concerning route fingerprinting attacks, which make use of what route creators do know of the network. We prove analytic bounds for both route fingerprinting and route bridging and describe the impact of these attacks on published anonymity-network designs. We also discuss implications for network scaling and client-server vs. peer-to-peer systems. © 2008 Springer-Verlag Berlin Heidelberg.
---
paper_title: Route Fingerprinting in Anonymous Communications

paper_content:

Peer discovery and route set-up are an integral part of the processes by which anonymizing peer-to-peer systems are made secure. When systems are large, and individual nodes only gain random knowledge of part of the network, their traffic can be detected by the uniqueness of the information they have learnt. We discuss this problem, which occurred in the initial design of Tarzan, and other related problems from the literature.
---
paper_title: Ad-hoc on-demand distance vector routing

paper_content:

An ad-hoc network is the cooperative engagement of a collection of mobile nodes without the required intervention of any centralized access point or existing infrastructure. We present Ad-hoc On Demand Distance Vector Routing (AODV), a novel algorithm for the operation of such ad-hoc networks. Each mobile host operates as a specialized router, and routes are obtained as needed (i.e., on-demand) with little or no reliance on periodic advertisements. Our new routing algorithm is quite suitable for a dynamic self starting network, as required by users wishing to utilize ad-hoc networks. AODV provides loop-free routes even while repairing broken links. Because the protocol does not require global periodic routing advertisements, the demand on the overall bandwidth available to the mobile nodes is substantially less than in those protocols that do necessitate such advertisements. Nevertheless we can still maintain most of the advantages of basic distance vector routing mechanisms. We show that our algorithm scales to large populations of mobile nodes wishing to form ad-hoc networks. We also include an evaluation methodology and simulation results to verify the operation of our algorithm.
---
paper_title: OSPF: Anatomy of an Internet Routing Protocol

paper_content:

From the Publisher: ::: Written for TCP/IP network administrators, protocol designers, and network application developers, this book gives the most complete and practical view ever into the inner workings of Internet routing. The book focuses on OSPF (Open Shortest Path First), a common TCP/IP routing protocol that provides robust and efficient routing support in the most demanding Internet environments. A methodical and detailed description of the protocol is offered and OSPF's role within the wider context of a TCP/IP network is demonstrated. ::: Practical throughout, the book provides not only a theoretical description of Internet routing, but also a real-world look into how theory translates into practice. It shows how algorithms are implemented, and how the routing protocols function in a working network where transmission lines and routers routinely break down. ::: You will find clear explanations of such routing fundamentals as how a router forwards packets, IP addressing, CIDR (Classless Inter-Domain Routing), the routing table, Internet routing architecture, and the two main routing technologies: Distance Vector and link-state algorithms. OSPF is discussed in depth, with an examination of the rationale behind OSPF's design decisions and how it has evolved to keep pace with the rapidly changing Internet environment. OSPF topics covered by the book include the following: ::: OSPF areas and virtual links NBMA (Nonbroadcast multi-access) and Point-to-MultiPoint network segments OSPF configuration and management Interaction with other routing protocols OSPF cryptographic authentication OSPF protocol extensions, including the Demand Circuit extensions and the multicast extensions to OSPF (MOSPF) An OSPF FAQ ::: ::: IP multicast and multicast routing are also discussed. Methods for debugging routing problems are explained, including a catalog of available debugging tools. The book also offers side-by-side comparisons of all the unicast and multicast routing protocols currently in use in the Internet. ::: You will come away from this book with a sophisticated understanding of Internet routing and of the OSPF protocol in particular. Moreover, the book's practical focus will enable you to put this deeper understanding to work in your network environment.
---
paper_title: An excess-based economic model for resource allocation in peer-to-peer networks

paper_content:

This paper describes economic aspects of gnunet, a peer-topeer framework for anonymous distributed file-sharing. gnunet is decentralized; all nodes are equal peers. In particular, there are no trusted entities in the network. This paper describes an economic model to perform resource allocation and defend against malicious participants in this context. The approach presented does not use credentials or payments; rather, it is based on trust. The design is much like that of a cooperative game in which peers take the role of players. Nodes must cooperate to achieve individual goals. In such a scenario, it is important to be able to distinguish between nodes exhibiting friendly behavior and those exhibiting malicious behavior. gnunet aims to provide anonymity for its users. Its design makes it hard to link a transaction to the node where it originated from. While anonymity requirements make a global view of the end-points of a transaction infeasible, the local link-to-link messages can be fully authenticated. Our economic model is based entirely on this local view of the network and takes only local decisions.
---
paper_title: Untraceable electronic mail, return addresses, and digital pseudonyms

paper_content:

A technique based on public key cryptography is presented that allows an electronic mail system to hide who a participant communicates with as well as the content of the communication - in spite of an unsecured underlying telecommunication system. The technique does not require a universally trusted authority. One correspondent can remain anonymous to a second, while allowing the second to respond via an untraceable return address. The technique can also be used to form rosters of untraceable digital pseudonyms from selected applications. Applicants retain the exclusive ability to form digital signatures corresponding to their pseudonyms. Elections in which any interested party can verify that the ballots have been properly counted are possible if anonymously mailed ballots are signed with pseudonyms from a roster of registered voters. Another use allows an individual to correspond with a record-keeping organization under a unique pseudonym, which appears in a roster of acceptable clients.
---
paper_title: Reliable MIX cascade networks through reputation

paper_content:

We describe a MIX cascade protocol and a reputation system that together increase the reliability of a network of MIX cascades. In our protocol, MIX nodes periodically generate a communally random seed that, along with their reputations, determines cascade configuration. Nodes send test messages to monitor their cascades. Senders can also demonstrate message decryptions to convince honest cascade members that a cascade is misbehaving. By allowing any node to declare the failure of its own cascade, we eliminate the need for global trusted witnesses.
---
paper_title: Mix-Networks with Restricted Routes

paper_content:

We present a mix network topology that is based on sparse expander graphs, with each mix only communicating with a few neighbouring others. We analyse the anonymity such networks provide, and compare it with fully connected mix networks and mix cascades. We prove that such a topology is efficient since it only requires the route length of messages to be relatively small in comparison with the number of mixes to achieve maximal anonymity. Additionally mixes can resist intersection attacks while their batch size, that is directly linked to the latency of the network, remains constant. A worked example of a network is also presented to illustrate how these results can be applied to create secure mix networks in practise. © Springer-Verlag Berlin Heidelberg 2003.
---
paper_title: Anonymity, unobservability, and pseudeonymity — a proposal for terminology

paper_content:

Based on the nomenclature of the early papers in the field, we propose a set of terminology which is both expressive and precise. More particularly, we define anonymity, unlinkability, unobservability, and pseudonymity (pseudonyms and digital pseudonyms, and their attributes). ::: ::: We hope that the adoption of this terminology might help to achieve better progress in the field by avoiding that each researcher invents a language of his/her own from scratch. Of course, each paper will need additional vocabulary, which might be added consistently to the terms defined here.
---
paper_title: Stop-and-Go-MIXes Providing Probabilistic Anonymity in an Open System

paper_content:

Currently known basic anonymity techniques depend on identity verification. If verification of user identities is not possible due to the related management overhead or a general lack of information (e.g. on the Internet), an adversary can participate several times in a communication relationship and observe the honest users. In this paper we focus on the problem of providing anonymity without identity verification. The notion of probabilistic anonymity is introduced. Probabilistic anonymity is based on a publicly known security parameter, which determines the security of the protocol. For probabilistic anonymity the insecurity, expressed as the probability of having only one honest participant, approaches 0 at an exponential rate as the security parameter is changed linearly. Based on our security model we propose a new MIX variant called “Stop-and-Go-MIX” (SG-MIX) which provides anonymity without identity verification, and prove that it is probabilistically secure.
---
paper_title: Mixminion: design of a type III anonymous remailer protocol

paper_content:

We present Mixminion, a message-based anonymous remailer protocol with secure single-use reply blocks. Mix nodes cannot distinguish Mixminion forward messages from reply messages, so forward and reply messages share the same anonymity set. We add directory servers that allow users to learn public keys and performance statistics of participating remailers, and we describe nymservers that provide long-term pseudonyms using single-use reply blocks as a primitive. Our design integrates link encryption between remailers to provide forward anonymity. Mixminion works in a real-world Internet environment, requires little synchronization or coordination between nodes, and protects against known anonymity-breaking attacks as well as or better than other systems with similar design parameters.
---
paper_title: Taxonomy of Mixes and Dummy Traffic

paper_content:

This paper presents an analysis of mixes and dummy traffic policies, which are building blocks of anonymous services. The goal of the paper is to bring together all the issues related to the analysis and design of mix networks. We discuss continuous and pool mixes, topologies for mix networks and dummy traffic policies. We point out the advantages and disadvantages of design decisions for mixes and dummy policies. Finally, we provide a list of research problems that need further work.
---
paper_title: ISDN-MIXes: Untraceable Communication with Very Small Bandwidth Overhead

paper_content:

Untraceable communication for services like telephony is often considered infeasible in the near future because of bandwidth limitations. We present a technique, called ISDN-Mixes, which shows that this is not the case.
---
paper_title: Project “anonymity and unobservability in the Internet”

paper_content:

It is a hard problem to achieve anonymity for real-time services in the Internet (e.g. Web access). All existing concepts fail when we assume a very strong attacker model (i.e. an attacker is able to observe all communication links). We also show that these attacks are real- world attacks. This paper outlines alternative models which mostly render these attacks useless. Our present work tries to increase the efficiency of these measures.
---
paper_title: Systems for anonymous communication

paper_content:

We present an overview of the eld of anonymous communications, from its establishment in 1981 by David Chaum to today. Key systems are presented categorized according to their underlying principles: semitrusted relays, mix systems, remailers, robust & veriable mixes, and onion routing systems. We include extended discussions of the threat models and usage models that dierent schemes provide, and the tradeos between the security properties oered and the communication characteristics dierent systems support.
---
paper_title: Mixminion: design of a type III anonymous remailer protocol

paper_content:

We present Mixminion, a message-based anonymous remailer protocol with secure single-use reply blocks. Mix nodes cannot distinguish Mixminion forward messages from reply messages, so forward and reply messages share the same anonymity set. We add directory servers that allow users to learn public keys and performance statistics of participating remailers, and we describe nymservers that provide long-term pseudonyms using single-use reply blocks as a primitive. Our design integrates link encryption between remailers to provide forward anonymity. Mixminion works in a real-world Internet environment, requires little synchronization or coordination between nodes, and protects against known anonymity-breaking attacks as well as or better than other systems with similar design parameters.
---
paper_title: Mix-Networks with Restricted Routes

paper_content:

We present a mix network topology that is based on sparse expander graphs, with each mix only communicating with a few neighbouring others. We analyse the anonymity such networks provide, and compare it with fully connected mix networks and mix cascades. We prove that such a topology is efficient since it only requires the route length of messages to be relatively small in comparison with the number of mixes to achieve maximal anonymity. Additionally mixes can resist intersection attacks while their batch size, that is directly linked to the latency of the network, remains constant. A worked example of a network is also presented to illustrate how these results can be applied to create secure mix networks in practise. © Springer-Verlag Berlin Heidelberg 2003.
---
paper_title: Mixminion: design of a type III anonymous remailer protocol

paper_content:

We present Mixminion, a message-based anonymous remailer protocol with secure single-use reply blocks. Mix nodes cannot distinguish Mixminion forward messages from reply messages, so forward and reply messages share the same anonymity set. We add directory servers that allow users to learn public keys and performance statistics of participating remailers, and we describe nymservers that provide long-term pseudonyms using single-use reply blocks as a primitive. Our design integrates link encryption between remailers to provide forward anonymity. Mixminion works in a real-world Internet environment, requires little synchronization or coordination between nodes, and protects against known anonymity-breaking attacks as well as or better than other systems with similar design parameters.
---
paper_title: AnoA: A Framework for Analyzing Anonymous Communication Protocols

paper_content:

Anonymous communication (AC) protocols such as the widely used Tor network have been designed to provide anonymity over the Internet to their participating users. While AC protocols have been the subject of several security and anonymity analyses in the last years, there still does not exist a framework for analyzing these complex systems and their different anonymity properties in a unified manner. ::: ::: In this work we present AnoA: a generic framework for defining, analyzing, and quantifying anonymity properties for AC protocols. In addition to quantifying the (additive) advantage of an adversary in an indistinguishability-based definition, AnoA uses a multiplicative factor, inspired from differential privacy. AnoA enables a unified quantitative analysis of well-established anonymity properties, such as sender anonymity, sender unlinkability, and relationship anonymity. AnoA modularly specifies adversarial capabilities by a simple wrapper-construction, called adversary classes. We examine the structure of these adversary classes and identify conditions under which it suffices to establish anonymity guarantees for single messages in order to derive guarantees for arbitrarily many messages. This then leads us to the definition of Plug’n’Play adversary classes (PAC), which are easy-to-use, expressive, and satisfy this condition. We prove that our framework is compatible with the universal composability (UC) framework and show how to apply AnoA to a simplified version of Tor against passive adversaries, leveraging a recent realization proof in the UC framework.
---
paper_title: Low-cost traffic analysis of Tor

paper_content:

Tor is the second generation onion router supporting the anonymous transport of TCP streams over the Internet. Its low latency makes it very suitable for common tasks, such as Web browsing, but insecure against traffic-analysis attacks by a global passive adversary. We present new traffic-analysis techniques that allow adversaries with only a partial view of the network to infer which nodes are being used to relay the anonymous streams and therefore greatly reduce the anonymity provided by Tor. Furthermore, we show that otherwise unrelated streams can be linked back to the same initiator Our attack is feasible for the adversary anticipated by the Tor designers. Our theoretical attacks are backed up by experiments performed on the deployed, albeit experimental, Tor network. Our techniques should also be applicable to any low latency anonymous network. These attacks highlight the relationship between the field of traffic-analysis and more traditional computer security issues, such as covert channel analysis. Our research also highlights that the inability to directly observe network links does not prevent an attacker from performing traffic-analysis: the adversary can use the anonymising network as an oracle to infer the traffic load on remote nodes in order to perform traffic-analysis.
---
paper_title: Improving performance and anonymity in the Tor network

paper_content:

Anonymous communication aims to hide the relationship between communicating parties on the Internet. It is the technical basis for achieving privacy and overcoming censorship. Presently there are only a few systems that are of practical relevance for providing anonymity. One of the most widespread and well researched is Tor which is based on onion routing. Usage of Tor, however, often leads to long delays which are not tolerated by end-users. This, in return, discourages many of them from using the system and lowers the protection for the remaining ones. In this paper we analyze the bottlenecks in the Tor network and propose new methods of path selection that better utilize available capacities in the heterogeneous network and allow performance-improved onion routing. Our methods are based on the combination of remotely measured current load of the nodes and an estimation of their maximum capacity. We evaluate the proposed methods in a Tor network running in PlanetLab where we tried as far as possible to recreate real-world conditions. Finally, we present a practical approach to empirically analyze the strength of anonymity that different methods of path selection provide in comparison to each other. We show the risk of the currently used method for path selection in Tor and provide a countermeasure to protect against this risk by effectively detecting nodes that lie about their capacity.
---
paper_title: An improved algorithm for tor circuit scheduling

paper_content:

Tor is a popular anonymity-preserving network, consisting of routers run by volunteers all around the world. It protects Internet users' privacy by relaying their network traffic through a series of routers, thus concealing the linkage between the sender and the recipient. Despite the advantage of Tor's anonymizing capabilities, it also brings extra latency, which discourages more users from joining the network. One of the factors that causes the latency lies in Tor's circuit scheduling algorithm, which allows busy circuits (those with continuous traffic) to crowd out bursty circuits (those with short bursts of traffic). In this work, we propose and implement a more advanced scheduling algorithm which treats circuits differently, based on their recent activity. In this way, bursty circuits such as those used for web browsing can gain higher priority over busy ones such as used for bulk transfer; the performance for most activities over Tor is improved, while minimal overhead is incurred. Our algorithm has been incorporated into the latest build of Tor.
---
paper_title: PIR-Tor: Scalable Anonymous Communication Using Private Information Retrieval

paper_content:

Existing anonymous communication systems like Tor do not scale well as they require all users to maintain up-to-date information about all available Tor relays in the system. Current proposals for scaling anonymous communication advocate a peer-to-peer (P2P) approach. While the P2P paradigm scales to millions of nodes, it provides new opportunities to compromise anonymity. In this paper, we step away from the P2P paradigm and advocate a client-server approach to scalable anonymity. We propose PIR-Tor, an architecture for the Tor network in which users obtain information about only a few onion routers using private information retrieval techniques. Obtaining information about only a few onion routers is the key to the scalability of our approach, while the use of private retrieval information techniques helps preserve client anonymity. The security of our architecture depends on the security of PIR schemes which are well understood and relatively easy to analyze, as opposed to peer-to-peer designs that require analyzing extremely complex and dynamic systems. In particular, we demonstrate that reasonable parameters of our architecture provide equivalent security to that of the Tor network. Moreover, our experimental results show that the overhead of PIR-Tor is manageable even when the Tor network scales by two orders of magnitude.
---
paper_title: Anonymous Connections and Onion Routing

paper_content:

Onion routing is an infrastructure for private communication over a public network. It provides anonymous connections that are strongly resistant to both eavesdropping and traffic analysis. Onion routing's anonymous connections are bidirectional, near real-time, and can be used anywhere a socket connection can be used. Any identifying information must be in the data stream carried over an anonymous connection. An onion is a data structure that is treated as the destination address by onion routers; thus, it is used to establish an anonymous connection. Onions themselves appear different to each onion router as well as to network observers. The same goes for data carried over the connections they establish. Proxy-aware applications, such as Web browsers and e-mail clients, require no modification to use onion routing, and do so through a series of proxies. A prototype onion routing network is running between our lab and other sites. This paper describes anonymous connections and their implementation using onion routing. This paper also describes several application proxies for onion routing, as well as configurations of onion routing networks.
---
paper_title: Scalable onion routing with torsk

paper_content:

We introduce Torsk, a structured peer-to-peer low-latency anonymity protocol. Torsk is designed as an interoperable replacement for the relay selection and directory service of the popular Tor anonymity network, that decreases the bandwidth cost of relay selection and maintenance from quadratic to quasilinear while introducing no new attacks on the anonymity provided by Tor, and no additional delay to connections made via Tor. The resulting bandwidth savings make a modest-sized Torsk network significantly cheaper to operate, and allows low-bandwidth clients to join the network. Unlike previous proposals for P2P anonymity schemes, Torsk does not require all users to relay traffic for others. Torsk utilizes a combination of two P2P lookup mechanisms with complementary strengths in order to avoid attacks on the confidentiality and integrity of lookups. We show by analysis that previously known attacks on P2P anonymity schemes do not apply to Torsk, and report on experiments conducted with a 336-node wide-area deployment of Torsk, demonstrating its efficiency and feasibility.
---
paper_title: Hiding Routing Information

paper_content:

This paper describes an architecture, Onion Routing, that limits a network's vulnerability to traffic analysis. The architecture provides anonymous socket connections by means of proxy servers. It provides real-time, bi-directional, anonymous communication for any protocol that can be adapted to use a proxy service. Specifically, the architecture provides for bi-directional communication even though no-one but the initiator's proxy server knows anything but previous and next hops in the communication chain. This implies that neither the respondent nor his proxy server nor any external observer need know the identity of the initiator or his proxy server. A prototype of Onion Routing has been implemented. This prototype works with HTTP (World Wide Web) proxies. In addition, an analogous proxy for TELNET has been implemented. roxies for FTP and SMTP are under development.
---
paper_title: Torchestra: reducing interactive traffic delays over tor

paper_content:

Tor is an onion routing network that protects users' privacy by relaying traffic through a series of nodes that run Tor software. As a consequence of the anonymity that it provides, Tor is used for many purposes. According to several measurement studies, a small fraction of users using Tor for bulk downloads account for the majority of traffic on the Tor network. These bulk downloads cause delays for interactive traffic, as many different circuits share bandwidth across each pair of nodes. The resulting delays discourage people from using Tor for normal web activity. We propose a potential solution to this problem: separate interactive and bulk traffic onto two different TCP connections between each pair of nodes. Previous proposals to improve Tor's performance for interactive traffic have focused on prioritizing traffic from less active circuits; however, these prioritization approaches are limited in the benefit they can provide, as they can only affect delays due to traffic processing in Tor itself. Our approach provides a simple way to reduce delays due to additional factors external to Tor, such as the effects of TCP congestion control and queuing of interactive traffic behind bulk traffic in buffers. We evaluate our proposal by simulating traffic using several methods and show that Torchestra provides up to 32% reduction in delays for interactive traffic compared to the Tor traffic prioritization scheme of Tang and Goldberg [18] and up to 40% decrease in delays when compared to vanilla Tor.
---
paper_title: Defending Anonymous Communications Against Passive Logging Attacks

paper_content:

We study the threat that passive logging attacks pose to anonymous communications. Previous work analyzed these attacks under limiting assumptions. We first describe a possible defense that comes from breaking the assumption of uniformly random path selection. Our analysis shows that the defense improves anonymity in the static model, where nodes stay in the system, but fails in a dynamic model, in which nodes leave and join. Additionally, we use the dynamic model to show that the intersection attack creates a vulnerability in certain peer-to-peer systems for anonymous communications. We present simulation results that show that attack times are significantly lower in practice than the upper bounds given by previous work. To determine whether users' Web traffic has communication patterns required by the attacks, we collected and analyzed the Web requests of users. We found that, for our study frequent and repeated communication to the same Web site is common.
---
paper_title: Improving Security and Performance in the Tor Network through Tunable Path Selection

paper_content:

The Tor anonymous communication network uses self-reported bandwidth values to select routers for building tunnels. Since tunnels are allocated in proportion to this bandwidth, this allows a malicious router operator to attract tunnels for compromise. Although Tor limits the self-reported bandwidth, it uses a high maximum value, effectively choosing performance over high anonymity for all users. We propose a router selection algorithm that allows users to control the trade-off between performance and anonymity. We also propose an opportunistic bandwidth measurement algorithm to replace self-reported values that is more sensitive to load and more responsive to changing network conditions. Our mechanism effectively blends the traffic from users of different preferences, making partitioning attacks difficult. We implemented the opportunistic measurement and tunable performance extensions and examined their performance both through simulation and in the real Tor network. Our results show that users can get dramatic increases in either performance or anonymity with little to no sacrifice in the other metric, or a more modest improvement in both. Our mechanisms are also invulnerable to the previously published low-resource attacks on Tor.
---
paper_title: A Survey of Anonymous Communication Channels

paper_content:

We present an overview of the field of anonymous communications, from its establishment in 1981 from David Chaum to today. Key systems are presented categorized according to their underlying principles: semi-trusted relays, mix systems, remailers, onion routing, and systems to provide robust mixing. We include extended discussions of the threat models and usage models that different schemes provide, and the trade-offs between the security properties offered and the communication characteristics different systems support.
---
paper_title: As-awareness in Tor path selection

paper_content:

Tor is an anonymous communications network with thousands of router nodes worldwide. An intuition reflected in much of the literature on anonymous communications is that, as an anonymity network grows, it becomes more secure against a given observer because the observer will see less of the network. In particular, as the Tor network grows from volunteers operating relays all over the world, it becomes less and less likely for a single autonomous system (AS) to be able to observe both ends of an anonymous connection. Yet, as the network continues to grow significantly, no analysis has been done to determine if this intuition is correct. Further, modifications to Tor's path selection algorithm to help clients avoid an AS-level observer have not been proposed and analyzed. Five years ago a previous study examined the AS-level threat against client and destination addresses chosen a priori to be likely or interesting to examine. Using an AS-level path inference algorithm with improved accuracy, more extensive Internet routing data, and, most importantly, a model of typical Tor client AS-level sources and destinations based on data gathered from the live network, we demonstrate that the threat of a single AS observing both ends of an anonymous Tor connection is greater than previously thought. We look at the growth of the Tor network over the past five years and show that its explosive growth has had only a small impact on the network's robustness against an AS-level attacker. Finally, we propose and evaluate the effectiveness of some simple, AS-aware path selection algorithms that avoid the computational overhead imposed by full AS-level path inference algorithms. Our results indicate that a novel heuristic we propose is more effective against an AS-level observer than other commonly proposed heuristics for improving location diversity in path selection.
---
paper_title: Low-resource routing attacks against tor

paper_content:

Tor has become one of the most popular overlay networks for anonymizing TCP traffic. Its popularity is due in part to its perceived strong anonymity properties and its relatively low latency service. Low latency is achieved through Tor's ability to balance the traffic load by optimizing Tor router selection to probabilistically favor routers with high bandwidth capabilities. We investigate how Tor's routing optimizations impact its ability to provide strong anonymity. Through experiments conducted on PlanetLab, we show the extent to which routing performance optimizations have left the system vulnerable to end-to-end traffic analysis attacks from non-global adversaries with minimal resources. Further, we demonstrate that entry guards, added to mitigate path disruption attacks, are themselves vulnerable to attack. Finally, we explore solutions to improve Tor's current routing algorithms and propose alternative routing strategies that prevent some of the routing attacks used in our experiments.
---
paper_title: IMUX: Managing Tor Connections from Two to Infinity, and Beyond

paper_content:

We consider proposals to improve the performance of the Tor overlay network by increasing the number of connections between re- lays, such as Torchestra and PCTCP. We introduce a new class of attacks that can apply to these designs, socket exhaustion, and show that these attacks are effective against PCTCP. We also describe IMUX, a design that generalizes the principles behind these designs while still mitigating against socket exhaustion attacks. We demonstrate empirically that IMUX resists socket exhaustion while finding that web clients can realize up to 25% increase in performance compared to Torchestra. Finally, we empirically evaluate the interaction between these designs and the recently proposed KIST design, which aims to improve performance by intelligently scheduling kernel socket writes.
---
paper_title: LASTor: A Low-Latency AS-Aware Tor Client

paper_content:

The widely used Tor anonymity network is designed to enable low-latency anonymous communication. However, in practice, interactive communication on Tor-which accounts for over 90% of connections in the Tor network [1]-incurs latencies over 5x greater than on the direct Internet path. In addition, since path selection to establish a circuit in Tor is oblivious to Internet routing, anonymity guarantees can breakdown in cases where an autonomous system (AS) can correlate traffic across the entry and exit segments of a circuit. In this paper, we show that both of these shortcomings in Tor can be addressed with only client-side modifications, i.e., without requiring a revamp of the entire Tor architecture. To this end, we design and implement a new Tor client, LASTor. First, we show that LASTor can deliver significant latency gains over the default Tor client by simply accounting for the inferred locations of Tor relays while choosing paths. Second, since the preference for low latency paths reduces the entropy of path selection, we design LASTor's path selection algorithm to be tunable. A user can choose an appropriate tradeoff between latency and anonymity by specifying a value between 0 (lowest latency) and 1 (highest anonymity) for a single parameter. Lastly, we develop an efficient and accurate algorithm to identify paths on which an AS can correlate traffic between the entry and exit segments. This algorithm enables LASTor to avoid such paths and improve a user's anonymity, while the low runtime of the algorithm ensures that the impact on end-to-end latency of communication is low. By applying our techniques to measurements of real Internet paths and by using LASTor to visit the top 200 websites from several geographically-distributed end-hosts, we show that, in comparison to the default Tor client, LASTor reduces median latencies by 25% while also reducing the false negative rate of not detecting a potential snooping AS from 57% to 11%.
---
paper_title: Scalable Link-Based Relay Selection for Anonymous Routing

paper_content:

The performance of an anonymous path can be described using many network metrics --- e.g., bandwidth, latency, jitter, loss, etc. However, existing relay selection algorithms have focused exclusively on producing paths with high bandwidth. In contrast to traditional node-based path techniques in which relay selection is biased by relays' node-characteristics (i.e., bandwidth), this paper presents the case for link-based path generation in which relay selection is weighted in favor of the highest performing links. Link-based relay selection supports more flexible routing, enabling anonymous paths with low latency, jitter, and loss, in addition to high bandwidth. Link-based approaches are also more secure than node-based techniques, eliminating "hotspots" in the network that attract a disproportionate amount of traffic. For example, misbehaving relays cannot advertise themselves as "low-latency" nodes to attract traffic, since latency has meaning only when measured between two endpoints. We argue that link-based path selection is practical for certain anonymity networks, and describe mechanisms for efficiently storing and disseminating link information.
---
paper_title: Survey on anonymous communications in computer networks

paper_content:

Anonymous communications aim to preserve communications privacy within the shared public network environment. It can provide security well beyond content privacy and integrity. The scientific studies of anonymous communications are largely originated from Chaum's two seminal approaches: mixnet and DC-net. In this paper, we present an overview of the research in this field. We start with the basic definitions of anonymous communications. We then describe the cryptographic primitives, the network protocols, and some of the representative anonymous communication systems. We also describe verifiable mixnets and their applications to electronic voting. Finally, we briefly cite some other anonymous systems.
---
paper_title: Improving performance and anonymity in the Tor network

paper_content:

Anonymous communication aims to hide the relationship between communicating parties on the Internet. It is the technical basis for achieving privacy and overcoming censorship. Presently there are only a few systems that are of practical relevance for providing anonymity. One of the most widespread and well researched is Tor which is based on onion routing. Usage of Tor, however, often leads to long delays which are not tolerated by end-users. This, in return, discourages many of them from using the system and lowers the protection for the remaining ones. In this paper we analyze the bottlenecks in the Tor network and propose new methods of path selection that better utilize available capacities in the heterogeneous network and allow performance-improved onion routing. Our methods are based on the combination of remotely measured current load of the nodes and an estimation of their maximum capacity. We evaluate the proposed methods in a Tor network running in PlanetLab where we tried as far as possible to recreate real-world conditions. Finally, we present a practical approach to empirically analyze the strength of anonymity that different methods of path selection provide in comparison to each other. We show the risk of the currently used method for path selection in Tor and provide a countermeasure to protect against this risk by effectively detecting nodes that lie about their capacity.
---
paper_title: An improved algorithm for tor circuit scheduling

paper_content:

Tor is a popular anonymity-preserving network, consisting of routers run by volunteers all around the world. It protects Internet users' privacy by relaying their network traffic through a series of routers, thus concealing the linkage between the sender and the recipient. Despite the advantage of Tor's anonymizing capabilities, it also brings extra latency, which discourages more users from joining the network. One of the factors that causes the latency lies in Tor's circuit scheduling algorithm, which allows busy circuits (those with continuous traffic) to crowd out bursty circuits (those with short bursts of traffic). In this work, we propose and implement a more advanced scheduling algorithm which treats circuits differently, based on their recent activity. In this way, bursty circuits such as those used for web browsing can gain higher priority over busy ones such as used for bulk transfer; the performance for most activities over Tor is improved, while minimal overhead is incurred. Our algorithm has been incorporated into the latest build of Tor.
---
paper_title: PIR-Tor: Scalable Anonymous Communication Using Private Information Retrieval

paper_content:

Existing anonymous communication systems like Tor do not scale well as they require all users to maintain up-to-date information about all available Tor relays in the system. Current proposals for scaling anonymous communication advocate a peer-to-peer (P2P) approach. While the P2P paradigm scales to millions of nodes, it provides new opportunities to compromise anonymity. In this paper, we step away from the P2P paradigm and advocate a client-server approach to scalable anonymity. We propose PIR-Tor, an architecture for the Tor network in which users obtain information about only a few onion routers using private information retrieval techniques. Obtaining information about only a few onion routers is the key to the scalability of our approach, while the use of private retrieval information techniques helps preserve client anonymity. The security of our architecture depends on the security of PIR schemes which are well understood and relatively easy to analyze, as opposed to peer-to-peer designs that require analyzing extremely complex and dynamic systems. In particular, we demonstrate that reasonable parameters of our architecture provide equivalent security to that of the Tor network. Moreover, our experimental results show that the overhead of PIR-Tor is manageable even when the Tor network scales by two orders of magnitude.
---
paper_title: DefenestraTor: Throwing out windows in Tor

paper_content:

Tor is one of the most widely used privacy enhancing technologies for achieving online anonymity and resisting censorship. While conventional wisdom dictates that the level of anonymity offered by Tor increases as its user base grows, the most significant obstacle to Tor adoption continues to be its slow performance. We seek to enhance Tor's performance by offering techniques to control congestion and improve flow control, thereby reducing unnecessary delays. ::: ::: To reduce congestion, we first evaluate small fixed-size circuit windows and a dynamic circuit window that adaptively re-sizes in response to perceived congestion. While these solutions improve web page response times and require modification only to exit routers, they generally offer poor flow control and slower downloads relative to Tor's current design. To improve flow control while reducing congestion, we implement N23, an ATM-style per-link algorithm that allows Tor routers to explicitly cap their queue lengths and signal congestion via back-pressure. Our results show that N23 offers better congestion and flow control, resulting in improved web page response times and faster page loads compared to Tor's current design and other window-based approaches. We also argue that our proposals do not enable any new attacks on Tor users' privacy
---
paper_title: Improving Security and Performance in the Tor Network through Tunable Path Selection

paper_content:

The Tor anonymous communication network uses self-reported bandwidth values to select routers for building tunnels. Since tunnels are allocated in proportion to this bandwidth, this allows a malicious router operator to attract tunnels for compromise. Although Tor limits the self-reported bandwidth, it uses a high maximum value, effectively choosing performance over high anonymity for all users. We propose a router selection algorithm that allows users to control the trade-off between performance and anonymity. We also propose an opportunistic bandwidth measurement algorithm to replace self-reported values that is more sensitive to load and more responsive to changing network conditions. Our mechanism effectively blends the traffic from users of different preferences, making partitioning attacks difficult. We implemented the opportunistic measurement and tunable performance extensions and examined their performance both through simulation and in the real Tor network. Our results show that users can get dramatic increases in either performance or anonymity with little to no sacrifice in the other metric, or a more modest improvement in both. Our mechanisms are also invulnerable to the previously published low-resource attacks on Tor.
---
paper_title: DeNASA: Destination-Naive AS-Awareness in Anonymous Communications

paper_content:

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.
---
paper_title: Scalable and Anonymous Group Communication with MTor

paper_content:

This paper presents MTor, a low-latency anony- mous group communication system. We construct MTor as an extension to Tor, allowing the construction of multi-source multicast trees on top of the existing Tor infrastructure. MTor does not depend on an external service to broker the group communication, and avoids central points of failure and trust. MTor's substantial bandwidth savings and graceful scalabil- ity enable new classes of anonymous applications that are currently too bandwidth-intensive to be viable through tradi- tional unicast Tor communication—e.g., group file transfer, collaborative editing, streaming video, and real-time audio conferencing. We detail the design of MTor and then analyze its performance and anonymity. By simulating MTor in Shadow and TorPS us- ing realistic models of the live Tor network's topology and recent consensus records from the live Tor network, we show that MTor achieves a 29% savings in network bandwidth and a 73% reduction in transmission time as compared to the base- line approach for anonymous group communication among 20 group members. We also demonstrate that MTor scales gracefully with the number of group participants, and allows dynamic group composition over time. Importantly, as more Tor users switch to group communication, we show that the overall performance and utilization for group communication improves. Finally, we discuss the anonymity implications of MTor and measure its resistance to traffic correlation.
---
paper_title: Route Fingerprinting in Anonymous Communications

paper_content:

Peer discovery and route set-up are an integral part of the processes by which anonymizing peer-to-peer systems are made secure. When systems are large, and individual nodes only gain random knowledge of part of the network, their traffic can be detected by the uniqueness of the information they have learnt. We discuss this problem, which occurred in the initial design of Tarzan, and other related problems from the literature.
---
paper_title: Chord: A scalable peer-to-peer lookup service for internet applications

paper_content:

A fundamental problem that confronts peer-to-peer applications is to efficiently locate the node that stores a particular data item. This paper presents Chord, a distributed lookup protocol that addresses this problem. Chord provides support for just one operation: given a key, it maps the key onto a node. Data location can be easily implemented on top of Chord by associating a key with each data item, and storing the key/data item pair at the node to which the key maps. Chord adapts efficiently as nodes join and leave the system, and can answer queries even if the system is continuously changing. Results from theoretical analysis, simulations, and experiments show that Chord is scalable, with communication cost and the state maintained by each node scaling logarithmically with the number of Chord nodes.
---
paper_title: Systems for anonymous communication

paper_content:

We present an overview of the eld of anonymous communications, from its establishment in 1981 by David Chaum to today. Key systems are presented categorized according to their underlying principles: semitrusted relays, mix systems, remailers, robust & veriable mixes, and onion routing systems. We include extended discussions of the threat models and usage models that dierent schemes provide, and the tradeos between the security properties oered and the communication characteristics dierent systems support.
---
paper_title: AP3: cooperative, decentralized anonymous communication

paper_content:

This paper describes a cooperative overlay network that provides anonymous communication services for participating users. The Anonymizing Peer-to-Peer Proxy (AP3) system provides clients with three primitives: (i) anonymous message delivery, (ii) anonymous channels, and (iii) secure pseudonyms. AP3 is designed to be lightweight, low-cost and provides "probable innocence" anonymity to participating users, even under a large-scale coordinated attack by a limited fraction of malicious overlay nodes. Additionally, we use AP3's primitives to build novel anonymous group communication facilities (multicast and anycast), which shield the identity of both publishers and subscribers.
---
paper_title: Resource discovery in distributed networks

paper_content:

In large distributed networks of computers, it is often the case that a subset of machines wants to cooperate to perform a task. Before they can do so, these machines need to learn of the existence of each other. In this paper we are interested in distributed algorithms whereby machines in a network learn of other machines in the network by making queries to machines they already know. The algorithms should be efficient both in terms of the time required and in terms of the total network communication required until all machines have discovered all other machines. We propose a very simple algorithm called Name-Dropper whereby all machines learn about each other within O(log’ n) rounds with high probability, where n is the number of machines in the network. The total number of connections required is O(n log2 n) and the total number of pointers which must be communicated is O(n2 log2 n), with high probability. Each of the preceding bounds is optimal to within polylogarithmic factors.
---
paper_title: Kademlia: A Peer-to-Peer Information System Based on the XOR Metric

paper_content:

We describe a peer-to-peer distributed hash table with provable consistency and performance in a fault-prone environment. Our system routes queries and locates nodes using a novel XOR-based metric topology that simplifies the algorithm and facilitates our proof. The topology has the property that every message exchanged conveys or reinforces useful contact information. The system exploits this information to send parallel, asynchronous query messages that tolerate node failures without imposing timeout delays on users.
---
paper_title: gap - Practical Anonymous Networking

paper_content:

This paper describes how anonymity is achieved in gnunet, a framework for anonymous distributed and secure networking.
---
paper_title: Chord: A scalable peer-to-peer lookup service for internet applications

paper_content:

A fundamental problem that confronts peer-to-peer applications is to efficiently locate the node that stores a particular data item. This paper presents Chord, a distributed lookup protocol that addresses this problem. Chord provides support for just one operation: given a key, it maps the key onto a node. Data location can be easily implemented on top of Chord by associating a key with each data item, and storing the key/data item pair at the node to which the key maps. Chord adapts efficiently as nodes join and leave the system, and can answer queries even if the system is continuously changing. Results from theoretical analysis, simulations, and experiments show that Chord is scalable, with communication cost and the state maintained by each node scaling logarithmically with the number of Chord nodes.
---
paper_title: Scalable onion routing with torsk

paper_content:

We introduce Torsk, a structured peer-to-peer low-latency anonymity protocol. Torsk is designed as an interoperable replacement for the relay selection and directory service of the popular Tor anonymity network, that decreases the bandwidth cost of relay selection and maintenance from quadratic to quasilinear while introducing no new attacks on the anonymity provided by Tor, and no additional delay to connections made via Tor. The resulting bandwidth savings make a modest-sized Torsk network significantly cheaper to operate, and allows low-bandwidth clients to join the network. Unlike previous proposals for P2P anonymity schemes, Torsk does not require all users to relay traffic for others. Torsk utilizes a combination of two P2P lookup mechanisms with complementary strengths in order to avoid attacks on the confidentiality and integrity of lookups. We show by analysis that previously known attacks on P2P anonymity schemes do not apply to Torsk, and report on experiments conducted with a 336-node wide-area deployment of Torsk, demonstrating its efficiency and feasibility.
---
paper_title: AP3: cooperative, decentralized anonymous communication

paper_content:

This paper describes a cooperative overlay network that provides anonymous communication services for participating users. The Anonymizing Peer-to-Peer Proxy (AP3) system provides clients with three primitives: (i) anonymous message delivery, (ii) anonymous channels, and (iii) secure pseudonyms. AP3 is designed to be lightweight, low-cost and provides "probable innocence" anonymity to participating users, even under a large-scale coordinated attack by a limited fraction of malicious overlay nodes. Additionally, we use AP3's primitives to build novel anonymous group communication facilities (multicast and anycast), which shield the identity of both publishers and subscribers.
---
paper_title: Measuring Freenet in the Wild: Censorship-Resilience under Observation

paper_content:

Freenet, a fully decentralized publication system designed for censorship-resistant communication, exhibits long delays and low success rates for finding and retrieving content. In order to improve its performance, an in-depth understanding of the deployed system is required. Therefore, we performed an extensive measurement study accompanied by a code analysis to identify bottlenecks of the existing algorithms and obtained a realistic user model for the improvement and evaluation of new algorithms.
---
paper_title: Salsa: a structured approach to large-scale anonymity

paper_content:

Highly distributed anonymous communications systems have the promise to reduce the effectiveness of certain attacks and improve scalability over more centralized approaches. Existing approaches, however, face security and scalability issues. Requiring nodes to have full knowledge of the other nodes in the system, as in Tor and Tarzan, limits scalability and can lead to intersection attacks in peer-to-peer configurations. MorphMix avoids this requirement for complete system knowledge, but users must rely on untrusted peers to select the path. This can lead to the attacker controlling the entire path more often than is acceptable.To overcome these problems, we propose Salsa, a structured approach to organizing highly distributed anonymous communications systems for scalability and security. Salsa is designed to select nodes to be used in anonymous circuits randomly from the full set of nodes, even though each node has knowledge of only a subset of the network. It uses a distributed hash table based on hashes of the nodes' IP addresses to organize the system. With a virtual tree structure, limited knowledge of other nodes is enough to route node lookups throughout the system. We use redundancy and bounds checking when performing lookups to prevent malicious nodes from returning false information without detection. We show that our scheme prevents attackers from biasing path selection, while incurring moderate overheads, as long as the fraction of malicious nodes is less than 20%. Additionally, the system prevents attackers from obtaining a snapshot of the entire system until the number of attackers grows too large (e.g. 15% for 10000 peers and 256 groups). The number of groups can be used as a tunable parameter in the system, depending on the number of peers, that can be used to balance performance and security.
---
paper_title: Octopus: A Secure and Anonymous DHT Lookup

paper_content:

Distributed Hash Table (DHT) lookup is a core technique in structured peer-to-peer (P2P) networks. Its decentralized nature introduces security and privacy vulnerabilities for applications built on top of them, we thus set out to design a lookup mechanism achieving both security and anonymity, heretofore an open problem. We present the design of Octopus, which uses attacker identification mechanisms to discover and remove malicious nodes, severely limiting an adversary's ability to carry out active attacks, and splits lookup queries over separate anonymous paths and introduces dummy queries to achieve high levels of anonymity. We analyze the security of Octopus by developing an event-based simulator to show that the attacker discovery mechanisms can rapidly identify malicious nodes with low error rate. We calculate the anonymity of Octopus using probabilistic modeling and show that Octopus can achieve near-optimal anonymity. We evaluate Octopus's efficiency on Planet lab and show that Octopus has reasonable lookup latency and low bandwidth overhead.
---
paper_title: The small-world phenomenon: an algorithmic perspective

paper_content:

Long a matter of folklore, the ``small-world phenomenon'''' --the principle that we are all linked by short chains of acquaintances --was inaugurated as an area of experimental study in the social sciences through the pioneering work of Stanley Milgram in the 1960''s. This work was among the first to make the phenomenon quantitative, allowing people to speak of the ``six degrees of separation'''' between any two people in the United States. Since then, a number of network models have been proposed as frameworks in which to study the problem analytically. One of the most refined of these models was formulated in recent work of Watts and Strogatz; their framework provided compelling evidence that the small-world phenomenon is pervasive in a range of networks arising in nature and technology, and a fundamental ingredient in the evolution of the World Wide Web. But existing models are insufficient to explain the striking algorithmic component of Milgram''s original findings: that individuals using local information are collectively very effective at actually constructing short paths between two points in a social network. Although recently proposed network models are rich in short paths, we prove that no decentralized algorithm, operating with local information only, can construct short paths in these networks with non-negligible probability. We then define an infinite family of network models that naturally generalizes the Watts-Strogatz model, and show that for one of these models, there is a decentralized algorithm capable of finding short paths with high probability. More generally, we provide a strong characterization of this family of network models, showing that there is in fact a unique model within the family for which decentralized algorithms are effective.
---
paper_title: Freenet: A Distributed Anonymous Information Storage and Retrieval System

paper_content:

We describe Freenet, an adaptive peer-to-peer network application that permits the publication, replication, and retrieval of data while protecting the anonymity of both authors and readers. Freenet operates as a network of identical nodes that collectively pool their storage space to store data files and cooperate to route requests to the most likely physical location of data. No broadcast search or centralized location index is employed. Files are referred to in a location-independent manner, and are dynamically replicated in locations near requestors and deleted from locations where there is no interest. It is infeasible to discover the true origin or destination of a file passing through the network, and difficult for a node operator to determine or be held responsible for the actual physical contents of her own node.
---
paper_title: Route Fingerprinting in Anonymous Communications

paper_content:

Peer discovery and route set-up are an integral part of the processes by which anonymizing peer-to-peer systems are made secure. When systems are large, and individual nodes only gain random knowledge of part of the network, their traffic can be detected by the uniqueness of the information they have learnt. We discuss this problem, which occurred in the initial design of Tarzan, and other related problems from the literature.
---
paper_title: Secure routing for structured peer-to-peer overlay networks

paper_content:

Structured peer-to-peer overlay networks provide a substrate for the construction of large-scale, decentralized applications, including distributed storage, group communication, and content distribution. These overlays are highly resilient; they can route messages correctly even when a large fraction of the nodes crash or the network partitions. But current overlays are not secure; even a small fraction of malicious nodes can prevent correct message delivery throughout the overlay. This problem is particularly serious in open peer-to-peer systems, where many diverse, autonomous parties without preexisting trust relationships wish to pool their resources. This paper studies attacks aimed at preventing correct message delivery in structured peer-to-peer overlays and presents defenses to these attacks. We describe and evaluate techniques that allow nodes to join the overlay, to maintain routing state, and to forward messages securely in the presence of malicious nodes.
---
paper_title: Bridging and Fingerprinting: Epistemic Attacks on Route Selection

paper_content:

Users building routes through an anonymization network must discover the nodes comprising the network. Yet, it is potentially costly, or even infeasible, for everyone to know the entire network. We introduce a novel attack, the route bridging attack, which makes use of what route creators do not know of the network. We also present new discussion and results concerning route fingerprinting attacks, which make use of what route creators do know of the network. We prove analytic bounds for both route fingerprinting and route bridging and describe the impact of these attacks on published anonymity-network designs. We also discuss implications for network scaling and client-server vs. peer-to-peer systems. © 2008 Springer-Verlag Berlin Heidelberg.
---
paper_title: Anonymity, unobservability, and pseudeonymity — a proposal for terminology

paper_content:

Based on the nomenclature of the early papers in the field, we propose a set of terminology which is both expressive and precise. More particularly, we define anonymity, unlinkability, unobservability, and pseudonymity (pseudonyms and digital pseudonyms, and their attributes). ::: ::: We hope that the adoption of this terminology might help to achieve better progress in the field by avoiding that each researcher invents a language of his/her own from scratch. Of course, each paper will need additional vocabulary, which might be added consistently to the terms defined here.
---
paper_title: Dining Cryptographers Revisited

paper_content:

Dining cryptographers networks (or DC-nets) are a privacy-preserving primitive devised by Chaum for anonymous message publication. A very attractive feature of the basic DC-net is its non-interactivity. Subsequent to key establishment, players may publish their messages in a single broadcast round, with no player-to-player communication. This feature is not possible in other privacy-preserving tools like mixnets. A drawback to DC-nets, however, is that malicious players can easily jam them, i.e., corrupt or block the transmission of messages from honest parties, and may do so without being traced. Several researchers have proposed valuable methods of detecting cheating players in DC-nets. This is usually at the cost, however, of multiple broadcast rounds, even in the optimistic case, and often of high computational and/or communications overhead, particularly for fault recovery. We present new DC-net constructions that simultaneously achieve non-interactivity and high-probability detection and identification of cheating players. Our proposals are quite efficient, imposing a basic cost that is linear in the number of participating players. Moreover, even in the case of cheating in our proposed system, just one additional broadcast round suffices for full fault recovery. Among other tools, our constructions employ bilinear maps, a recently popular cryptographic technique for reducing communication complexity.
---
paper_title: The dining cryptographers in the disco: unconditional sender and recipient untraceability with computationally secure serviceability

paper_content:

In Journal of Cryptology 1/1 (1988) 65–75, CHAUM describes a beautiful technique, the DC-net, which should allow participants to send and receive messages anonymously in an arbitrary network. The untraceability of the senders is proved to be unconditional, but that of the recipients implicitly assumes a reliable broadcast network. This assumption is unrealistic in some networks, but it can be removed completely by using the fail-stop key generation schemes by WAIDNER (these proceedings). In both cases, however, each participant can untraceably and permanently disrupt the entire DC-net.
---
paper_title: Chord: A scalable peer-to-peer lookup service for internet applications

paper_content:

A fundamental problem that confronts peer-to-peer applications is to efficiently locate the node that stores a particular data item. This paper presents Chord, a distributed lookup protocol that addresses this problem. Chord provides support for just one operation: given a key, it maps the key onto a node. Data location can be easily implemented on top of Chord by associating a key with each data item, and storing the key/data item pair at the node to which the key maps. Chord adapts efficiently as nodes join and leave the system, and can answer queries even if the system is continuously changing. Results from theoretical analysis, simulations, and experiments show that Chord is scalable, with communication cost and the state maintained by each node scaling logarithmically with the number of Chord nodes.
---
paper_title: The dining cryptographers problem: Unconditional sender and recipient untraceability

paper_content:

Keeping confidential who sends which messages, in a world where any physical transmission can be traced to its origin, seems impossible. The solution presented here is unconditionally or cryptographically secure, depending on whether it is based on one-time-use keys or on public keys, respectively. It can be adapted to address efficiently a wide variety of practical considerations.
---
paper_title: Dissent: accountable anonymous group messaging

paper_content:

Users often wish to participate in online groups anonymously, but misbehaving users may abuse this anonymity to disrupt the group's communication. Existing messaging protocols such as DC-nets leave groups vulnerable to denial-of-service and Sybil attacks, Mix-nets are difficult to protect against traffic analysis, and accountable voting protocols are unsuited to general anonymous messaging. We present the first general messaging protocol that offers provable anonymity with accountability for moderate-size groups, and efficiently handles unbalanced loads where few members wish to transmit in a given round. The N group members first cooperatively shuffle an N x N matrix of pseudorandom seeds, then use these seeds in N "pre-planned" DC-nets protocol runs. Each DC-nets run transmits the variable-length bulk data comprising one member's message, using the minimum number of bits required for anonymity under our attack model. The protocol preserves message integrity and one-to-one correspondence between members and messages, makes denial-of-service attacks by members traceable to the culprit, and efficiently handles large, unbalanced message loads. A working prototype demonstrates the protocol's practicality for anonymous messaging in groups of 40+ members.
---
paper_title: Networks without user observability—design options

paper_content:

In usual communication networks, the network operator or an intruder could easily observe when, how much and with whom the users communicate (traffic analysis), even if the users employ end-to-end encryption. When ISDNs are used for almost everything, this becomes a severe threat. Therefore, we summarize basic concepts to keep the recipient and sender or at least their relationship unobservable, consider some possible implementations and necessary hierarchical extensions, and propose some suitable performance and reliability enhancements.
---
paper_title: Dissent in numbers: Making strong anonymity scale

paper_content:

Current anonymous communication systems make a trade-off between weak anonymity among many nodes, via onion routing, and strong anonymity among few nodes, via DC-nets. We develop novel techniques in Dissent, a practical group anonymity system, to increase by over two orders of magnitude the scalability of strong, traffic analysis resistant approaches. Dissent derives its scalability from a client/server architecture, in which many unreliable clients depend on a smaller and more robust, but administratively decentralized, set of servers. Clients trust only that at least one server in the set is honest, but need not know or choose which server to trust. Unlike the quadratic costs of prior peer-to-peer DC-nets schemes, Dissent's client/server design makes communication and processing costs linear in the number of clients, and hence in anonymity set size. Further, Dissent's servers can unilaterally ensure progress, even if clients respond slowly or disconnect at arbitrary times, ensuring robustness against client churn, tail latencies, and DoS attacks. On DeterLab, Dissent scales to 5,000 online participants with latencies as low as 600 milliseconds for 600-client groups. An anonymous Web browsing application also shows that Dissent's performance suffices for interactive communication within smaller local-area groups.
---
paper_title: Xor-trees for efficient anonymous multicast and reception

paper_content:

We examine the problem of efficient anonymous multicast and reception in general communication networks. We present algorithms that achieve anonymous communication, are protected against traffic analysis, and require O (1) amortized communication complexity on each link and low computational comlexity. The algorithms support sender anonymity, receiver(s) anonymity, or sender-receiver anonymity.
---
paper_title: Herbivore: A Scalable and Efficient Protocol for Anonymous Communication

paper_content:

Anonymity is increasingly important for networked applications amidst concerns over censorship and privacy. In this paper, we describe Herbivore, a peer-to-peer, scalable, tamper-resilient communication system that provides provable anonymity and privacy. Building on dining cryptographer networks, Herbivore scales by partitioning the network into anonymizing cliques. Adversaries able to monitor all network traffic cannot deduce the identity of a sender or receiver beyond an anonymizing clique. In addition to strong anonymity, Herbivore simultaneously provides high efficiency and scalability, distinguishing it from other anonymous communication protocols. Performance measurements from a prototype implementation show that the system can achieve high bandwidths and low latencies when deployed over the Internet.
---
paper_title: Dining Cryptographers Revisited

paper_content:

Dining cryptographers networks (or DC-nets) are a privacy-preserving primitive devised by Chaum for anonymous message publication. A very attractive feature of the basic DC-net is its non-interactivity. Subsequent to key establishment, players may publish their messages in a single broadcast round, with no player-to-player communication. This feature is not possible in other privacy-preserving tools like mixnets. A drawback to DC-nets, however, is that malicious players can easily jam them, i.e., corrupt or block the transmission of messages from honest parties, and may do so without being traced. Several researchers have proposed valuable methods of detecting cheating players in DC-nets. This is usually at the cost, however, of multiple broadcast rounds, even in the optimistic case, and often of high computational and/or communications overhead, particularly for fault recovery. We present new DC-net constructions that simultaneously achieve non-interactivity and high-probability detection and identification of cheating players. Our proposals are quite efficient, imposing a basic cost that is linear in the number of participating players. Moreover, even in the case of cheating in our proposed system, just one additional broadcast round suffices for full fault recovery. Among other tools, our constructions employ bilinear maps, a recently popular cryptographic technique for reducing communication complexity.
---
paper_title: The dining cryptographers in the disco: unconditional sender and recipient untraceability with computationally secure serviceability

paper_content:

In Journal of Cryptology 1/1 (1988) 65–75, CHAUM describes a beautiful technique, the DC-net, which should allow participants to send and receive messages anonymously in an arbitrary network. The untraceability of the senders is proved to be unconditional, but that of the recipients implicitly assumes a reliable broadcast network. This assumption is unrealistic in some networks, but it can be removed completely by using the fail-stop key generation schemes by WAIDNER (these proceedings). In both cases, however, each participant can untraceably and permanently disrupt the entire DC-net.
---
paper_title: The dining cryptographers problem: Unconditional sender and recipient untraceability

paper_content:

Keeping confidential who sends which messages, in a world where any physical transmission can be traced to its origin, seems impossible. The solution presented here is unconditionally or cryptographically secure, depending on whether it is based on one-time-use keys or on public keys, respectively. It can be adapted to address efficiently a wide variety of practical considerations.
---
paper_title: Dissent: accountable anonymous group messaging

paper_content:

Users often wish to participate in online groups anonymously, but misbehaving users may abuse this anonymity to disrupt the group's communication. Existing messaging protocols such as DC-nets leave groups vulnerable to denial-of-service and Sybil attacks, Mix-nets are difficult to protect against traffic analysis, and accountable voting protocols are unsuited to general anonymous messaging. We present the first general messaging protocol that offers provable anonymity with accountability for moderate-size groups, and efficiently handles unbalanced loads where few members wish to transmit in a given round. The N group members first cooperatively shuffle an N x N matrix of pseudorandom seeds, then use these seeds in N "pre-planned" DC-nets protocol runs. Each DC-nets run transmits the variable-length bulk data comprising one member's message, using the minimum number of bits required for anonymity under our attack model. The protocol preserves message integrity and one-to-one correspondence between members and messages, makes denial-of-service attacks by members traceable to the culprit, and efficiently handles large, unbalanced message loads. A working prototype demonstrates the protocol's practicality for anonymous messaging in groups of 40+ members.
---
paper_title: Dissent in numbers: Making strong anonymity scale

paper_content:

Current anonymous communication systems make a trade-off between weak anonymity among many nodes, via onion routing, and strong anonymity among few nodes, via DC-nets. We develop novel techniques in Dissent, a practical group anonymity system, to increase by over two orders of magnitude the scalability of strong, traffic analysis resistant approaches. Dissent derives its scalability from a client/server architecture, in which many unreliable clients depend on a smaller and more robust, but administratively decentralized, set of servers. Clients trust only that at least one server in the set is honest, but need not know or choose which server to trust. Unlike the quadratic costs of prior peer-to-peer DC-nets schemes, Dissent's client/server design makes communication and processing costs linear in the number of clients, and hence in anonymity set size. Further, Dissent's servers can unilaterally ensure progress, even if clients respond slowly or disconnect at arbitrary times, ensuring robustness against client churn, tail latencies, and DoS attacks. On DeterLab, Dissent scales to 5,000 online participants with latencies as low as 600 milliseconds for 600-client groups. An anonymous Web browsing application also shows that Dissent's performance suffices for interactive communication within smaller local-area groups.
---
paper_title: Scalable Anonymous Group Communication in the Anytrust Model

paper_content:

Anonymous communication capabilities are useful and desirable, but practical onion routing approaches are vulnerable to traffic analysisand DoS attacks—especially againsta powerful adversary, such as a repressive government or compromised ISP. To fill this gap we introduce D3, the first practical anonymous group communication system offering anonymity and disruption resistance against strong traffic analysis and collusion attacks, with scalability to hundreds of group members and quick response to churn. D3 builds on a trust model we call anytrust. Anytrust is a decentralized client/server network model, in which each of many clients—representing group members—trust only that at least one of a smaller but diverse set of “servers” or “super-peers” behaves honestly, but clients need not know which server to trust. By combining and adapting verifiable shuffle and DC-nets techniques to anytrust, D3 achieves short shuffle latencies and efficient tree-based DC-nets ciphertext combining, while guaranteeing message anonymity and integrity, transmission proportionality among group members, and adaptability to both network/node failures and active disruption. Experiments with a working prototype demonstrate that D3 is practical at scales infeasible in prior systems offering comparable security.
---
paper_title: Herbivore: A Scalable and Efficient Protocol for Anonymous Communication

paper_content:

Anonymity is increasingly important for networked applications amidst concerns over censorship and privacy. In this paper, we describe Herbivore, a peer-to-peer, scalable, tamper-resilient communication system that provides provable anonymity and privacy. Building on dining cryptographer networks, Herbivore scales by partitioning the network into anonymizing cliques. Adversaries able to monitor all network traffic cannot deduce the identity of a sender or receiver beyond an anonymizing clique. In addition to strong anonymity, Herbivore simultaneously provides high efficiency and scalability, distinguishing it from other anonymous communication protocols. Performance measurements from a prototype implementation show that the system can achieve high bandwidths and low latencies when deployed over the Internet.
---
paper_title: Practical Attacks Against The I2P Network

paper_content:

Anonymity networks, such as Tor or I2P, were built to allow users to access network resources without revealing their identity. Newer designs, like I2P, run in a completely decentralized fashion, while older systems, like Tor, are built around central authorities. The decentralized approach has advantages no trusted central party, better scalability, but there are also security risks associated with the use of distributed hash tables DHTs in this environment. ::: ::: I2P was built with these security problems in mind, and the network is considered to provide anonymity for all practical purposes. Unfortunately, this is not entirely justified. In this paper, we present a group of attacks that can be used to deanonymize I2P users. Specifically, we show that an attacker, with relatively limited resources, is able to deanonymize a I2P user that accesses a resource of interest with high probability.
---
paper_title: I2P’s Usage Characterization

paper_content:

We present the first monitoring study aiming to characterize the usage of the I2P network, a low-latency anonymous network based on garlic routing. We design a distributed monitoring architecture for the I2P network and show through three one-week measurement experiments the ability of the system to identify a significant number of all running applications, among web servers and file-sharing clients.
---
paper_title: Chain-Based Anonymous Routing for Wireless Ad Hoc Networks

paper_content:

Wireless ad hoc networks are so vulnerable to passive attacks and eavesdropping adversaries due to their shared medium which makes network traffic easy to capture and analyze. Therefore, security and privacy protections are of extreme importance for protocols and applications in such networks. In this paper, we introduce a new framework for anonymous routing, named chain-based routing, to improve the privacy. In our framework, nodes on a path are virtually bound to each other like a chain. Each node is only aware of its associated links in a flow and does not require any other information about source, destination, or other parts of the chain. Based on this framework, we propose an on-demand routing protocol, called Chain-based Anonymous Routing (CAR), which uses unicast-based broadcast data transfer to fulfill anonymous communication in wireless ad hoc networks. Through hiding identifiers of nodes inside the chain, CAR realizes sender, receiver, and relationship anonymity in addition to untraceability in the network. Moreover, it is resistant to a wide range of passive attacks while adapting to implement other security mechanisms in the presence of active attacks.
---
paper_title: TEAP: trust-enhanced anonymous on-demand routing protocol for mobile ad hoc networks

paper_content:

Security plays a major role in implementing mobile ad hoc networks (MANET) for communication in an adverse environment. This study introduces the concept of anonymity for an informant who identifies and reports anonymously the misbehaviour of the users in the network. The trust-enhanced anonymous on-demand routing protocol (TEAP) is proposed to restrain the misuse of anonymity in two methods. In the first method, a user is revealed as a misbehaving user to other users, if it does not send any cooperative message, upon receiving two warnings. In the second method, if a user attempts to send multiple claims against a particular user for the same reason it will also be termed as a misbehaving user. The TEAP protocol is designed based upon broadcast with trapdoor information is a cryptography concept which is used to detect the misbehaving users anonymously in the network. The simulation results prove the necessity of anonymity in MANET and the effectiveness of this protocol in achieving such anonymity.
---
paper_title: Low-cost traffic analysis of Tor

paper_content:

Tor is the second generation onion router supporting the anonymous transport of TCP streams over the Internet. Its low latency makes it very suitable for common tasks, such as Web browsing, but insecure against traffic-analysis attacks by a global passive adversary. We present new traffic-analysis techniques that allow adversaries with only a partial view of the network to infer which nodes are being used to relay the anonymous streams and therefore greatly reduce the anonymity provided by Tor. Furthermore, we show that otherwise unrelated streams can be linked back to the same initiator Our attack is feasible for the adversary anticipated by the Tor designers. Our theoretical attacks are backed up by experiments performed on the deployed, albeit experimental, Tor network. Our techniques should also be applicable to any low latency anonymous network. These attacks highlight the relationship between the field of traffic-analysis and more traditional computer security issues, such as covert channel analysis. Our research also highlights that the inability to directly observe network links does not prevent an attacker from performing traffic-analysis: the adversary can use the anonymising network as an oracle to infer the traffic load on remote nodes in order to perform traffic-analysis.
---
paper_title: Improving stream correlation attacks on anonymous networks

paper_content:

The level of anonymity offered by low latency, interactive, anonymous networks is unknown. This paper implements correlation attacks on the deployed Tor network and a simulated Tor network under defined network conditions. The accuracy of the attacks act as a metric for the networks anonymity in the face of a passive adversary. From observation of the deployed Tor network, several techniques were developed to compensate for some of the modifications the Tor protocol induces in traffic. These techniques increase correlation accuracy by 10% to 40% for differing correlation functions. Almost 50% of traffic streams on the simulated network are identified immediately with 10% of experimental traffic on the real Tor network identified.
---
paper_title: Route Fingerprinting in Anonymous Communications

paper_content:

Peer discovery and route set-up are an integral part of the processes by which anonymizing peer-to-peer systems are made secure. When systems are large, and individual nodes only gain random knowledge of part of the network, their traffic can be detected by the uniqueness of the information they have learnt. We discuss this problem, which occurred in the initial design of Tarzan, and other related problems from the literature.
---
paper_title: On the impossibility of efficient self-stabilization in virtual overlays with churn

paper_content:

Virtual overlays generate topologies for greedy routing, like rings or hypercubes, on connectivity restricted networks. They have been proposed to achieve efficient content discovery in the Darknet mode of Freenet, for instance, which provides a private and secure communication platform for dissidents and whistle-blowers. Virtual overlays create tunnels between nodes with neighboring addresses in the topology. The routing performance hence is directly related to the length of the tunnels, which have to be set up and maintained at the cost of communication overhead in the absence of an underlying routing protocol. In this paper, we show the impossibility to efficiently maintain sufficiently short tunnels. Specifically, we prove that in a dynamic network either the maintenance or the routing eventually exceeds polylog cost in the number of participants. Our simulations additionally show that the length of the tunnels increases fast if standard maintenance protocols are applied. Thus, we show that virtual overlays can only offer efficient routing at the price of high maintenance costs.
---
paper_title: Users get routed: traffic correlation on tor by realistic adversaries

paper_content:

We present the first analysis of the popular Tor anonymity network that indicates the security of typical users against reasonably realistic adversaries in the Tor network or in the underlying Internet. Our results show that Tor users are far more susceptible to compromise than indicated by prior work. Specific contributions of the paper include(1)a model of various typical kinds of users,(2)an adversary model that includes Tor network relays, autonomous systems(ASes), Internet exchange points (IXPs), and groups of IXPs drawn from empirical study,(3) metrics that indicate how secure users are over a period of time,(4) the most accurate topological model to date of ASes and IXPs as they relate to Tor usage and network configuration,(5) a novel realistic Tor path simulator (TorPS), and(6)analyses of security making use of all the above. To show that our approach is useful to explore alternatives and not just Tor as currently deployed, we also analyze a published alternative path selection algorithm, Congestion-Aware Tor. We create an empirical model of Tor congestion, identify novel attack vectors, and show that it too is more vulnerable than previously indicated.
---
paper_title: Dissent in numbers: Making strong anonymity scale

paper_content:

Current anonymous communication systems make a trade-off between weak anonymity among many nodes, via onion routing, and strong anonymity among few nodes, via DC-nets. We develop novel techniques in Dissent, a practical group anonymity system, to increase by over two orders of magnitude the scalability of strong, traffic analysis resistant approaches. Dissent derives its scalability from a client/server architecture, in which many unreliable clients depend on a smaller and more robust, but administratively decentralized, set of servers. Clients trust only that at least one server in the set is honest, but need not know or choose which server to trust. Unlike the quadratic costs of prior peer-to-peer DC-nets schemes, Dissent's client/server design makes communication and processing costs linear in the number of clients, and hence in anonymity set size. Further, Dissent's servers can unilaterally ensure progress, even if clients respond slowly or disconnect at arbitrary times, ensuring robustness against client churn, tail latencies, and DoS attacks. On DeterLab, Dissent scales to 5,000 online participants with latencies as low as 600 milliseconds for 600-client groups. An anonymous Web browsing application also shows that Dissent's performance suffices for interactive communication within smaller local-area groups.
---
paper_title: Stealthy traffic analysis of low-latency anonymous communication using throughput fingerprinting

paper_content:

Anonymity systems such as Tor aim to enable users to communicate in a manner that is untraceable by adversaries that control a small number of machines. To provide efficient service to users, these anonymity systems make full use of forwarding capacity when sending traffic between intermediate relays. In this paper, we show that doing this leaks information about the set of Tor relays in a circuit (path). We present attacks that, with high confidence and based solely on throughput information, can (a) reduce the attacker's uncertainty about the bottleneck relay of any Tor circuit whose throughput can be observed, (b) exactly identify the guard relay(s) of a Tor user when circuit throughput can be observed over multiple connections, and (c) identify whether two concurrent TCP connections belong to the same Tor user, breaking unlinkability. Our attacks are stealthy, and cannot be readily detected by a user or by Tor relays. We validate our attacks using experiments over the live Tor network. We find that the attacker can substantially reduce the entropy of a bottleneck relay distribution of a Tor circuit whose throughput can be observed-the entropy gets reduced by a factor of 2 in the median case. Such information leaks from a single Tor circuit can be combined over multiple connections to exactly identify a user's guard relay(s). Finally, we are also able to link two connections from the same initiator with a crossover error rate of less than 1.5% in under 5 minutes. Our attacks are also more accurate and require fewer resources than previous attacks on Tor.
---
paper_title: Towards Measuring Resilience in Anonymous Communication Networks

paper_content:

Prior research on anonymous communication networks has focused, to a large extent, on achieving, measuring, and evaluating anonymity properties. In this work we address another important security property that has so far received much less attention, namely resilience against denial-of-service attacks that degrade the performance of the network. We formally define resilience and propose a metric for quantifying the resilience of anonymous communication networks (ACNs) against active adversaries. Our metric expresses the degradation in quality of service of an ACN as the decrease in performance resulting from the adversarial removal or disabling of network nodes. We illustrate the practicality of the metric by applying it to a simulated version of the Tor network, and providing an evaluation of the resilience of Tor towards various adversarial strategies.
---
paper_title: Trawling for Tor Hidden Services: Detection, Measurement, Deanonymization

paper_content:

Tor is the most popular volunteer-based anonymity network consisting of over 3000 volunteer-operated relays. Apart from making connections to servers hard to trace to their origin it can also provide receiver privacy for Internet services through a feature called "hidden services". In this paper we expose flaws both in the design and implementation of Tor's hidden services that allow an attacker to measure the popularity of arbitrary hidden services, take down hidden services and deanonymize hidden services. We give a practical evaluation of our techniques by studying: (1) a recent case of a botnet using Tor hidden services for command and control channels; (2) Silk Road, a hidden service used to sell drugs and other contraband; (3) the hidden service of the DuckDuckGo search engine.
---
paper_title: Anonymity Loves Company: Usability and the Network Effect

paper_content:

Apparatus is described for monitoring phase currents and torsional vibrations of a turbine-generator which are indicative of the dynamic response of the machine during operation under load. The monitoring system disclosed includes probes which are operable to sense rotation of the main shaft of the turbine-generator and to feed the resulting signals to a vibration network. The vibration network eliminates from the signals any false components present at frequencies equal to multiples of the rate of rotation of the shaft and produces a composite vibration signal containing only true components of shaft torsional vibration. The composite vibration signal and a set of three phase current signals determined by stepping down, filtering, and amplifying the generator line currents are monitored continuously but recorded only when at least one of two signals derived from selected components of the composite vibration signal and phase current signals exceeds reference levels in an alarm system included in the monitor.
---
paper_title: Scalable and Anonymous Group Communication with MTor

paper_content:

This paper presents MTor, a low-latency anony- mous group communication system. We construct MTor as an extension to Tor, allowing the construction of multi-source multicast trees on top of the existing Tor infrastructure. MTor does not depend on an external service to broker the group communication, and avoids central points of failure and trust. MTor's substantial bandwidth savings and graceful scalabil- ity enable new classes of anonymous applications that are currently too bandwidth-intensive to be viable through tradi- tional unicast Tor communication—e.g., group file transfer, collaborative editing, streaming video, and real-time audio conferencing. We detail the design of MTor and then analyze its performance and anonymity. By simulating MTor in Shadow and TorPS us- ing realistic models of the live Tor network's topology and recent consensus records from the live Tor network, we show that MTor achieves a 29% savings in network bandwidth and a 73% reduction in transmission time as compared to the base- line approach for anonymous group communication among 20 group members. We also demonstrate that MTor scales gracefully with the number of group participants, and allows dynamic group composition over time. Importantly, as more Tor users switch to group communication, we show that the overall performance and utilization for group communication improves. Finally, we discuss the anonymity implications of MTor and measure its resistance to traffic correlation.
---
paper_title: Circuit fingerprinting attacks: passive deanonymization of tor hidden services

paper_content:

This paper sheds light on crucial weaknesses in the design of hidden services that allow us to break the anonymity of hidden service clients and operators passively. In particular, we show that the circuits, paths established through the Tor network, used to communicate with hidden services exhibit a very different behavior compared to a general circuit. We propose two attacks, under two slightly different threat models, that could identify a hidden service client or operator using these weaknesses. We found that we can identify the users' involvement with hidden services with more than 98% true positive rate and less than 0.1% false positive rate with the first attack, and 99% true positive rate and 0.07% false positive rate with the second. We then revisit the threat model of previous website fingerprinting attacks, and show that previous results are directly applicable, with greater efficiency, in the realm of hidden services. Indeed, we show that we can correctly determine which of the 50 monitored pages the client is visiting with 88% true positive rate and false positive rate as low as 2.9%, and correctly deanonymize 50 monitored hidden service servers with true positive rate of 88% and false positive rate of 7.8% in an open world setting.
---
paper_title: Methods for Improving Resilience in Communication Networks and P2P Overlays

paper_content:

ABSTRACT Resilience to failures and deliberate attacks is becoming an essential requirement in most communication networks today. This also applies to P2P Overlays which on the one hand are created on top of communication infrastructures, and therefore are equally affected by failures of the underlying infrastructure, but which on the other hand introduce new possibilities like the creation of arbitrary links within the overlay. In this article, we present a survey of strategies to improve resilience in communication networks as well as in P2P overlay networks. Furthermore, our intention is to point out differences and similarities in the resilience-enhancing measures for both types of networks. By revising some basic concepts from graph theory, we show that many concepts for communication networks are based on well-known graph-theoretical problems. Especially, some methods for the construction of protection paths in advance of a failure are based on very hard problems, indeed many of them are in NP and can only be solved heuristically or on certain topologies. P2P overlay networks evidently benefit from resilience-enhancing strategies in the underlying communication infrastructure, but beyond that, their specific properties pose the need for more sophisticated mechanisms. The dynamic nature of peers requires to take some precautions, like estimating the reliability of peers, redundantly storing information, and provisioning a reliable routing.
---
paper_title: Chain-Based Anonymous Routing for Wireless Ad Hoc Networks

paper_content:

Wireless ad hoc networks are so vulnerable to passive attacks and eavesdropping adversaries due to their shared medium which makes network traffic easy to capture and analyze. Therefore, security and privacy protections are of extreme importance for protocols and applications in such networks. In this paper, we introduce a new framework for anonymous routing, named chain-based routing, to improve the privacy. In our framework, nodes on a path are virtually bound to each other like a chain. Each node is only aware of its associated links in a flow and does not require any other information about source, destination, or other parts of the chain. Based on this framework, we propose an on-demand routing protocol, called Chain-based Anonymous Routing (CAR), which uses unicast-based broadcast data transfer to fulfill anonymous communication in wireless ad hoc networks. Through hiding identifiers of nodes inside the chain, CAR realizes sender, receiver, and relationship anonymity in addition to untraceability in the network. Moreover, it is resistant to a wide range of passive attacks while adapting to implement other security mechanisms in the presence of active attacks.
---
paper_title: A.D.: Traffic analysis against low-latency anonymity networks using available bandwidth estimation

paper_content:

We introduce a novel remotely-mounted attack that can expose the network identity of an anonymous client, hidden service, and anonymizing proxies. To achieve this, we employ single-end controlled available bandwidth estimation tools and a colluding network entity that can modulate the traffic destined for the victim. To expose the circuit including the source, we inject a number of short or one large burst of traffic. Although timing attacks have been successful against anonymity networks, they require either a Global Adversary or the compromise of substantial number of anonymity nodes. Our technique does not require compromise of, or collaboration with, any such entity. ::: ::: To validate our attack, we performed a series of experiments using different network conditions and locations for the adversaries on both controlled and real-world Tor circuits. Our results demonstrate that our attack is successful in controlled environments. In real-world scenarios, even an under-provisioned adversary with only a few network vantage points can, under certain conditions, successfully identify the IP address of both Tor users and Hidden Servers. However, Tor's inherent circuit scheduling results in limited quality of service for its users. This at times leads to increased false negatives and it can degrade the performance of our circuit detection. We believe that as high speed anonymity networks become readily available, a well-provisioned adversary, with a partial or inferred network "map", will be able to partially or fully expose anonymous users.
---
paper_title: Traffic Analysis: Protocols, Attacks, Design Issues and Open Problems

paper_content:

We present the traffic analysis problem and expose the most important protocols, attacks and design issues. Afterwards, we propose directions for further research. ::: ::: As we are mostly interested in efficient and practical Internet based protocols, most of the emphasis is placed on mix based constructions. The presentation is informal in that no complex definitions and proofs are presented, the aim being more to give a thorough introduction than to present deep new insights.
---
paper_title: Alpenhorn: bootstrapping secure communication without leaking metadata

paper_content:

Alpenhorn is the first system for initiating an encrypted connection between two users that provides strong privacy and forward secrecy guarantees for metadata (i.e., information about which users connected to each other) and that does not require out-of-band communication other than knowing the other user's Alpenhorn username (email address). This resolves a significant shortcoming in all prior works on private messaging, which assume an out-of-band key distribution mechanism. ::: ::: Alpenhorn's design builds on three ideas. First, Alpenhorn provides each user with an address book of friends that the user can call. Second, when a user adds a friend for the first time, Alpenhorn ensures the adversary does not learn the friend's identity, by using identity-based encryption in a novel way to privately determine the friend's public key. Finally, when calling a friend, Alpenhorn ensures forward secrecy of metadata by storing pairwise shared secrets in friends' address books, and evolving them over time, using a new keywheel construction. Alpenhorn relies on a number of servers, but operates in an anytrust model, requiring just one of the servers to be honest. ::: ::: We implemented a prototype of Alpenhorn, and integrated it into the Vuvuzela private messaging system (which did not previously provide privacy or forward secrecy of metadata when initiating conversations). Experimental results show that Alpenhorn can scale to many users, supporting 10 million users on three Alpenhorn servers with an average dial latency of 150 seconds and a client bandwidth overhead of 3.7 KB/sec.
---
paper_title: A Practical Congestion Attack on Tor Using Long Paths

paper_content:

In 2005, Murdoch and Danezis demonstrated the first practical congestion attack against a deployed anonymity network. They could identify which relays were on a target Tor user's path by building paths one at a time through every Tor relay and introducing congestion. However, the original attack was performed on only 13 Tor relays on the nascent and lightly loaded Tor network. ::: ::: We show that the attack from their paper is no longer practical on today's 1500-relay heavily loaded Tor network. The attack doesn't scale because a) the attacker needs a tremendous amount of bandwidth to measure enough relays during the attack window, and b) there are too many false positives now that many other users are adding congestion at the same time as the attacks. ::: ::: We then strengthen the original congestion attack by combining it with a novel bandwidth amplification attack based on a flaw in the Tor design that lets us build long circuits that loop back on themselves. We show that this new combination attack is practical and effective by demonstrating a working attack on today's deployed Tor network. By coming up with a model to better understand Tor's routing behavior under congestion, we further provide a statistical analysis characterizing how effective our attack is in each case.
---

Title: A Survey on Routing in Anonymous Communication Protocols

Section 1: INTRODUCTION
Description 1: Introduce the context and importance of anonymous communication protocols, including the societal benefits and privacy threats.

Section 2: ANONYMOUS ROUTING PROTOCOL CHARACTERISTICS
Description 2: Introduce the routing characteristics, deployability, and performance metrics considered in the taxonomy and discuss the relationship between these characteristics.

Section 3: Routing Characteristics
Description 3: Present and discuss the fundamental building blocks of routing in anonymous communication protocols which include node management, transfer/retrieval of node information, path selection, and forwarding or relaying.

Section 4: Network Structure
Description 4: Discuss the network features relevant to anonymous routing including topology, connection type, and symmetry among nodes.

Section 5: Routing Information
Description 5: Discuss the information available to the routing decision-maker and how this information is managed and updated.

Section 6: Communication Model
Description 6: Discuss the methods of route creation, node selection, and forwarding strategies in anonymous communication protocols.

Section 7: Performance and Deployability
Description 7: Discuss metrics for evaluating the performance and deployability of anonymous communication protocols, including latency, communication mode, implementation, and application context.

Section 8: Correlation Among Routing Features
Description 8: Address the correlations and dependencies among different routing features.

Section 9: ROUTING CLASSIFICATION OF AC PROTOCOLS
Description 9: Present and discuss the categorization of anonymous communication protocols based on their routing types and characteristics.

Section 10: Mixnet-Based Protocols
Description 10: Review mixnet-based protocols, their mix selection strategies, and prominent applications like remailers.

Section 11: Tor-Related Protocols
Description 11: Review Tor-related protocols and discuss their features, including onion-routing, node selection, and defense mechanisms.

Section 12: Random Walks, Structured and Unstructured DHT-Based Protocols
Description 12: Review Random Walk and DHT-based protocols, including hop-by-hop routing strategies and the use of DHT for node lookups.

Section 13: DCnets
Description 13: Discuss DCnet-based protocols, their communication models, detection and recovery from disruptions, and scalability issues.

Section 14: Miscellaneous Protocols
Description 14: Review alternative source-routed and broadcasting AC protocols that do not fit into the previous categories.

Section 15: DISCUSSION
Description 15: Discuss the challenges and trade-offs between different classes of routing protocols, their security implications, and relevance for real-world applications.

Section 16: CONCLUDING REMARKS
Description 16: Summarize the findings, lessons learned, and the relationship between routing decisions and goals such as security, anonymity, scalability, and performance.