- Distributed Measurement with Private Set-Union Cardinality [pdf] [BibTeX]
Ellis Fenske, Akshaya Mani, Aaron Johnson, and Micah Sherr
To appear in Proceedings of the 24th ACM Conference on Computer and Communications Security (CCS 2017).
Show abstract
This paper introduces a cryptographic protocol for efficiently aggregating a count of unique items across a set of data parties privately — that is, without exposing any information other than the count. Our protocol allows for more secure and useful statistics gathering in privacy-preserving distributed systems such as anonymity networks; for example, it allows operators of anonymity networks such as Tor to securely answer the questions: how many unique users are using the distributed service? and how many hidden services are being accessed? We formally prove the correctness and security of our protocol in the Universal Composability framework against an active adversary that compromises all but one of the aggregation parties. We also show that the protocol provides security against adaptive corruption of the data parties, which prevents them from being victims of targeted compromise. To ensure safe measurements, we also show how the output can satisfy differential privacy.
We present a proof-of-concept implementation of the private set-union cardinality protocol (PSC) and use it to demonstrate that PSC operates with low computational overhead and reasonable bandwidth. In particular, for reasonable deployment sizes, the protocol run at timescales smaller than the typical measurement period would be and thus is suitable for distributed measurement.
- PeerFlow: Secure Load Balancing in Tor [pdf] [BibTeX]
Aaron Johnson, Rob Jansen, Nicholas Hopper, Aaron Segal, and Paul Syverson
In Proceedings on Privacy Enhancing Technologies (PoPETS 2017), Vol. 2017, Number 2, April 2017.
Show abstract
We present PeerFlow, a system to securely load balance client traffic in Tor. Security in Tor requires that no adversary handle too much traffic. However, Tor relays are run by volunteers who cannot be trusted to report the relay bandwidths, which Tor clients use for load balancing. We show that existing methods to determine the bandwidths of Tor relays allow an adversary with little bandwidth to attack large amounts of client traffic. These methods include Tor's current bandwidth-scanning system, TorFlow, and the peer-measurement system EigenSpeed. We present an improved design called PeerFlow that uses a peer-measurement process both to limit an adversary's ability to increase his measured bandwidth and to improve accuracy. We show our system to be secure, fast, and efficient. We implement PeerFlow in Tor and demonstrate its speed and accuracy in large-scale network simulations.
- Avoiding The Man on the Wire: Improving Tor's Security with Trust-Aware Path Selection [pdf] [BibTeX]
- Technical Report (Full Version) [pdf] [BibTeX]
Aaron Johnson, Rob Jansen, Aaron D. Jaggard, Joan Feigenbaum, and Paul Syverson
In Proceedings of the 24th Network and Distributed System Security Symposium (NDSS 2017).
Show abstract
Tor users are vulnerable to deanonymization by an adversary that can observe some Tor relays
or some parts of the network. We demonstrate that previous network-aware path-selection
algorithms that propose to solve this problem are vulnerable to attacks across multiple Tor
connections. We suggest that users use trust to choose the paths through Tor that
are less likely to be observed, where trust is flexibly modeled as a probability
distribution on the location of the user's adversaries, and we present the Trust-Aware Path
Selection algorithm for Tor that helps users
avoid traffic-analysis attacks while still choosing paths that could have
been selected by many other users. We evaluate this algorithm in two settings using a high-level map
of Internet routing: (i) users try to avoid a single global
adversary that has an independent chance to control each Autonomous System organization, Internet
Exchange Point organization, and Tor relay family, and (ii) users try to avoid
deanonymization by any single country. We also examine the performance of Trust-Aware Path
selection using the Shadow network simulator.
- Safely Measuring Tor [pdf] [BibTeX]
Rob Jansen and Aaron Johnson
In Proceedings of the 23rd ACM Conference on Computer and Communications Security (CCS 2016).
Show abstract
Tor is a popular network for anonymous communication. The usage and operation of Tor is not well-understood, however, because its privacy goals make common measurement approaches ineffective or risky. We present PrivCount, a system for measuring the Tor network designed with user privacy as a primary goal. PrivCount securely aggregates measurements across Tor relays and over time to produce differentially private outputs. PrivCount improves on prior approaches by enabling flexible exploration of many diverse kinds of Tor measurements while maintaining accuracy and privacy for each. We use PrivCount to perform a measurement study of Tor of sufficient breadth and depth to inform accurate models of Tor users and traffic. Our results indicate that Tor has 710,000 users connected but only 550,000 active at a given time, that Web traffic now constitutes 91% of data bytes on Tor, and that the strictness of relays' connection policies significantly affects the type of application data they forward.
- Defending Tor from Network Adversaries: A Case Study of Network Path Prediction [pdf] [BibTeX]
Joshua Juen, Aaron Johnson, Anupam Das, Nikita Borisov, and Matthew Caesar
In Proceedings on Privacy Enhancing Technologies (PoPETS 2015), Vol. 2015, Number 2, June 2015.
Show abstract
The Tor anonymity network has been shown vulnerable to traffic analysis attacks by autonomous systems (ASes) and Internet exchanges (IXes), which can observe different overlay hops belonging to the same circuit. We evaluate whether network path prediction techniques provide an accurate picture of the threat from such adversaries, and whether they can be used to avoid this threat. We perform a measurement study by collecting 17.2 million traceroutes from Tor relays to destinations around the Internet. We compare the collected traceroute paths to predicted paths using state-of-the-art path inference techniques. We find that traceroutes present a very different picture, with the set of ASes seen in the traceroute path differing from the predicted path 80% of the time. We also consider the impact that prediction errors have on Tor security. Using a simulator to choose paths over a week, our traceroutes indicate a user has nearly a 100% chance of at least one compromise in a week with 11\% of total paths containing an AS compromise and less than 1% containing an IX compromise when using default Tor selection. We find modifying the path selection to choose paths predicted to be safe lowers total paths with an AS compromise to 0.14% but still presents a 5-11% chance of at least one compromise in a week while making 5% of paths fail, with 96% of failures due to false positives in path inferences. Our results demonstrate more measurement and better path prediction is necessary to mitigate the risk of AS and IX adversaries to Tor.
- Hidden-service statistics reported by relays [pdf] [BibTeX]
David Goulet, Aaron Johnson, George Kadianakis, and Karsten Loesing
Tor Technical Report 2015-04-001, April 2015.
Media coverage of resulting statistics: BBC News,
Ars Technica
Show abstract
In order to understand how hidden services are being used in Tor, relays can collect and
report statistics about the hidden-service activity they observe. However, such statistics
might harm the privacy of individual Tor users. We describe how relays can be used to
collect statistics about hidden services, how they might be useful, and how they can be
published in a way that protects individual privacy.
- 20,000 In League Under the Sea: Anonymous Communication, Trust, MLATs, and Undersea Cables [pdf] [BibTeX]
Aaron D. Jaggard, Aaron Johnson, Sarah Cortes, Paul Syverson, and Joan Feigenbaum
In Proceedings on Privacy Enhancing Technologies (PoPETS 2015), Vol. 2015, Number 1, April 2015.
Show abstract
Motivated by the effectiveness of correlation attacks
against Tor, the censorship arms race, and observations of malicious
relays in Tor, we propose that Tor users capture their trust in network
elements using probability distributions over the sets of elements
observed by network adversaries. We present a modular system that allows
users to efficiently and conveniently create such distributions and use
them to improve their security.
To illustrate this system, we present two novel types of adversaries. First,
we study a powerful, pervasive adversary that can compromise an unknown
number of Autonomous System organizations, Internet Exchange Point organizations,
and Tor relay families.
Second, we initiate the study of how an adversary might use Mutual Legal Assistance
Treaties (MLATs)
to enact surveillance. As part of this, we identify submarine cables as a
potential subject of trust and incorporate data about these into our MLAT analysis by
using them as a proxy for adversary power.
Finally, we present preliminary experimental results that show the potential for our trust
framework to be used by Tor clients and services to improve security.
- Security Analysis of Accountable Anonymity in Dissent [pdf] [BibTeX]
- Technical Report (Full Version) [pdf] [BibTeX]
Ewa Syta, Aaron Johnson, Henry Corrigan-Gibbs, Shu-Chun Weng, David Wolinsky, and Bryan Ford
In ACM Transactions on Information and System Security (TISSEC),
Volume 17, Issue 1, Article No. 4, August 2014.
Show abstract
Users often wish to communicate anonymously on the Internet,
for instance, in group discussion forums or over instant messaging.
Existing solutions are vulnerable to misbehaving users, however,
who may abuse their anonymity to disrupt communication.
Dining Cryptographers networks leave groups vulnerable to denial-of-service and Sybil
attacks, mix networks are difficult to protect
against traffic analysis, and accountable voting schemes
are unsuited to general anonymous messaging.
DISSENT, originally introduced by Corrigan-Gibbs and Ford [2010], is the first general
communication protocol that offers
provable anonymity and accountability for moderate-size groups, while
efficiently handling unbalanced communication demands among users.
We provide a full description of an improved DISSENT protocol, define its precise security
properties, and give rigorous proofs of these properties.
Our improved protocol is a direct result of this security analysis, which
identified several non-trivial attacks on the original protocol stemming from subtle
design flaws.
- The Sniper Attack: Anonymously Deanonymizing and Disabling the Tor Network [pdf] [BibTeX]
Rob Jansen, Florian Tschorsch, Aaron Johnson, and Björn Scheuermann
In Proceedings of the 21st Network and Distributed System Security Symposium (NDSS 2014).
Show abstract
Tor is a distributed onion-routing network used for achieving anonymity and resisting censorship online. Because of Tor's growing popularity, it is attracting increasingly larger threats against which it was not securely designed. In this paper, we present the Sniper Attack, an extremely low cost but highly destructive denial of service attack against Tor that an adversary may use to anonymously disable arbitrary Tor relays. The attack utilizes valid protocol messages to boundlessly consume memory by exploiting Tor's end-to-end reliable data transport. We design and evaluate a prototype of the attack to show its feasibility and efficiency: our experiments show that an adversary may consume a victim relay's memory by as much as 2187 KiB/s while using at most only 92 KiB/s of upstream bandwidth. We extend our experimental results to estimate the threat against the live Tor network and find that a strategic adversary could disable all of the top 20 exit relays in only 29 minutes, thereby reducing Tor's bandwidth capacity by 35 percent. We also show how the attack enables the deanonymization of hidden services through selective denial of service by forcing them to choose guard nodes in control of the adversary. Finally, we discuss defenses against the Sniper Attack that provably render the attack ineffective, and suggest defenses against deanonymization by denial-of-service attacks in general that significantly mitigate the threat.
- Users Get Routed: Traffic Correlation on Tor by Realistic Adversaries [pdf] [BibTeX]
Aaron Johnson, Chris Wacek, Rob Jansen, Micah Sherr, and Paul Syverson
In Proceedings of the 20th ACM Conference on Computer and Communications Security (CCS 2013).
Media coverage: The Register, Vice, The Irish Times, Ars Technica, Finnish Broadcasting Company (YLE), NewScientist, MIT Technology Review
Show abstract
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.
- Privacy-Preserving Data Exploration in Genome-Wide Association Studies
Aaron Johnson and Vitaly Shmatikov
In Proceedings of the 19th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 2013).
Show abstract
Genome-wide association studies (GWAS) have become a popular method
for analyzing sets of DNA sequences in order to discover the genetic
basis of disease. Unfortunately, statistics published as the result of
GWAS can be used to identify individuals participating in the study.
To prevent privacy breaches, even previously published results have
been removed from public databases, impeding researchers' access to
the data and hindering collaborative research. Existing techniques for
privacy-preserving GWAS focus on answering specific questions, such as
correlations between a given pair of SNPs (DNA sequence variations).
This does not fit the typical GWAS process, where the analyst may not
know in advance which SNPs to consider and which statistical tests to use,
how many SNPs are significant for a given dataset, etc.
We present a set of practical, privacy-preserving data mining algorithms
for GWAS datasets. Our framework supports exploratory data
analysis, where the analyst does not know a priori how many and which SNPs
to consider. We develop privacy-preserving algorithms for computing the
number and location of SNPs that are significantly associated with the
disease, the significance of any statistical test between a given SNP
and the disease, any measure of correlation between SNPs, and the block
structure of correlations. We evaluate our algorithms on real-world
datasets and demonstrate that they produce significantly more accurate
results than prior techniques while guaranteeing differential privacy.
- Poster: Onions for Sale: Putting Privacy on the Market [pdf] [ppt]
Aaron Johnson, Rob G. Jansen, and Paul Syverson
In Proceedings of the 17th International Conference on Financial Cryptography and Data Security (FC 2013).
Show abstract
We propose that Tor support the purchase of its services.
- LIRA: Lightweight Incentivized Routing for Anonymity [pdf] [BibTeX]
Rob G. Jansen, Aaron Johnson, and Paul Syverson
In Proceedings of the 20th Network and Distributed System Security Symposium (NDSS 2013).
Show abstract
Tor, the most popular deployed distributed onion routing network, suffers from
performance and scalability problems stemming from a lack of incentives for
volunteers to contribute. Insufficient capacity limits scalability and harms the
anonymity of its users. We introduce LIRA, a lightweight scheme that creates
performance incentives for users to contribute bandwidth resources to the Tor
network. LIRA uses a novel cryptographic lottery: winners may be guessed
with tunable probability by any user or bought in exchange for resource
contributions. The traffic of those winning the lottery is prioritized through
Tor. The uncertainty of whether a buyer or a guesser is getting priority
improves the anonymity of those purchasing winners, while the performance
incentives encourage contribution. LIRA is more lightweight than prior reward
schemes that pay for service and provides better anonymity than schemes that
simply give priority to traffic originating from fast relays. We analyze
LIRA's efficiency, anonymity, and incentives, present a prototype
implementation, and describe experiments that show it indeed improves
performance for those servicing the network.
- Dissent in Numbers: Making Strong Anonymity Scale [pdf] [BibTeX]
David Isaac Wolinsky, Henry Corrigan-Gibbs, Bryan Ford, and Aaron Johnson
In Proceedings of the Tenth USENIX Symposium on Operating Systems Design and Implementation (OSDI '12).
Show abstract
Current anonymous communication systems exhibit a trade-off between weak anonymity among many nodes, via onion routing, or strong anonymity among a few nodes, via DC-nets. To addresses this trade-off we introduce Dissent, a practical anonymity system that increases by 1-2 orders of magnitude the anonymity set sizes achievable using traffic-analysis-resistant techniques. Dissent's design achieves these gains via a client/server architecture, in which many unreliable clients partially offload communication and computation costs to a smaller and more robust, but 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 reduces communication and processing costs to 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 PlanetLab, Dissent scales to 2,000 online participants and offers latencies as low as 3 seconds for network sizes of 500. An anonymous Web browsing application also shows that Dissent's performance suffices for interactive communication within smaller local-area groups.
- Probabilistic Analysis of Onion Routing in a Black-box Model [pdf] [BibTeX]
Joan
Feigenbaum, Aaron Johnson, and Paul Syverson
In ACM Transactions on Information and System Security (TISSEC), Volume 15 Issue 3, November 2012.
Show abstract
We perform a probabilistic analysis of onion routing. The analysis is presented in a black-box model of
anonymous communication in the Universally Composable framework that abstracts the essential properties
of onion routing in the presence of an active adversary who controls a portion of the network and knows all
a priori distributions on user choices of destination. Our results quantify how much the adversary can gain
in identifying users by exploiting knowledge of their probabilistic behavior. In particular, we show that, in
the limit as the network gets large, a user u's anonymity is worst either when the other users always choose
the destination u is least likely to visit or when the other users always choose the destination u chooses. This
worst-case anonymity with an adversary that controls a fraction b of the routers is shown to be comparable to the best-case anonymity against an adversary that controls a fraction
√b.
- Scalable Anonymous Group Communication in the Anytrust Model [pdf] [BibTeX]
David Isaac Wolinsky, Henry Corrigan-Gibbs, Bryan Ford, and Aaron Johnson
In Proceedings of the Fifth European Workshop on System Security (EuroSec 2012).
Show abstract
Anonymous communication capabilities are useful and desirable, but practical onion routing approaches are vulnerable to traffic analysis and DoS attacks — especially against a 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 “server” 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.
- Trust-based Anonymous Communication: Adversary Models and Routing Algorithms [pdf] [BibTeX]
Aaron Johnson, Paul Syverson, Roger Dingledine, and Nick Mathewson
In Proceedings of the 18th ACM Conference on Computer and Communications Security (CCS 2011).
Show abstract
We introduce a novel model of routing security that incorporates the ordinarily overlooked variations in trust that users have for different parts of the network. We focus on anonymous communication, and in particular onion routing, although we expect the approach to apply more broadly.
This paper provides two main contributions. First, we present a novel model to consider the various security concerns for route selection in anonymity networks when users vary their trust over parts of the network. Second, to show the usefulness of our model, we present as an example a new algorithm to select paths in onion routing. We analyze its effectiveness against deanonymization and other information leaks, and particularly how it fares in our model versus existing algorithms, which do not consider trust. In contrast to those, we find that our trust-based routing strategy can protect anonymity against an adversary capable of attacking a significant fraction of the network.
- Preventing Active Timing Attacks in Low-Latency Anonymous Communication (Extended Abstract) [pdf] [BibTeX]
Joan
Feigenbaum, Aaron Johnson, and Paul Syverson
In Proceedings of the 10th Privacy Enhancing Technologies Symposium (PETS 2010).
Show abstract
Low-latency anonymous communication protocols in general,
and the popular onion-routing protocol in particular, are broken
against simple timing attacks. While there have been few proposed solutions
to this problem when the adversary is active, several padding
schemes have been proposed to defend against a passive adversary that
just observes timing patterns. Unfortunately active adversaries can break
padding schemes by inserting delays and dropping messages.
We present a protocol that provides anonymity against an active adversary
by using a black-box padding scheme that is effective against a passive
adversary. Our protocol reduces, in some sense, providing anonymous
communication against active attacks to providing a padding scheme
against passive attacks.
Our analytical results show that anonymity can be made arbitrarily good
at the cost of some added latency and required bandwidth. We also perform
measurements on the Tor network to estimate the real-world performance
of our protocol, showing that the added delay is not excessive.
- More Anonymous Onion Routing Through Trust [pdf] [BibTeX]
Aaron Johnson and Paul
Syverson
In Proceedings of the 22nd IEEE Computer Security Foundations
Symposium (CSF 2009).
Show abstract
We consider using trust information to improve the security
of onion-routing networks. In particular, we introduce a model of trust in
network nodes and use it to design path-selection strategies that minimize the
probability that the adversary can successfully perform a correlation
attack. We first describe the general case in which onion routers can be
assigned arbitrary levels of trust. Selecting a strategy can be formulated in a
straightforward way as a linear program, but it is exponential in size. We thus
analyze a natural simplification of path selection for this case. More
importantly, however, when choosing routes in practice, only a very coarse
assessment of trust in specific onion routers is likely to be
feasible. Therefore, we focus next on the special case in which there are only
two trust levels. For this more practical case we identify three optimal
route-selection strategies such that at least one is optimal, depending on the
trust levels of the two classes, their size, and the reach of the
adversary. This can yield practical input into routing decisions . We set out
the relevant parameters and choices for making such decisions.
-
Online and Offline Selling in Limit Order Markets [pdf] [BibTeX]
Kevin L. Chang and Aaron Johnson
In Proceedings of the 4th International Workshop on Internet and
Network Economics (WINE 2008).
Show abstract
Completely automated electronic securities exchanges and algorithms for trading
in these exchanges have become very important for modern finance. Kakade et
al. introduced the limit order market model, which is a prevalent paradigm in
electronic markets. In this paper, we consider both online and offline
algorithms for maximizing revenue when selling in limit order markets. We first
prove that the standard reservation price algorithm has an optimal competitive
ratio for this problem. This ratio is not constant, and so we consider
computing solutions offline. We show that the offline optimization problem is
NP-hard, even for very restricted instances. We complement the hardness result
by presenting an approximation scheme that runs in polynomial time for a wide class of instances.
-
Probabilistic Analysis of Onion Routing in a Black-box
Model (Extended abstract) [pdf] [BibTeX]
Joan
Feigenbaum, Aaron Johnson, and Paul Syverson
In Proceedings of the 2007 ACM Workshop on Privacy in Electronic
Society (WPES 2007).
Show abstract
We perform a probabilistic analysis of onion routing. The
analysis is presented in a black-box model of anonymous
communication that abstracts the essential properties of onion
routing in the presence of an active adversary that controls a
portion of the network and knows all a priori distributions
on user choices of destination. Our results quantify how
much the adversary can gain in identifying users by exploiting
knowledge of their probabilistic behavior. In particular,
we show that a user u's anonymity is worst either when the
other users always choose the destination u is least likely to
visit or when the other users always choose the destination u
chooses. This worst-case anonymity with an adversary that
controls a fraction b of the routers is comparable to the best-case
anonymity against an adversary p that controls a fraction
√b.
-
Private Web Search [pdf] [BibTeX] [software]
Felipe Saint-Jean, Aaron Johnson, Dan Boneh, and Joan
Feigenbaum
In Proceedings of the 2007 ACM Workshop on Privacy in Electronic
Society (WPES 2007).
Show abstract
Web search is currently a source of growing concern about
personal privacy. It is an essential and central part of most
users' activity online and therefore one through which a significant
amount of personal information may be revealed. To
help users protect their privacy, we have designed and implemented
Private Web Search (PWS), a usable client-side tool
that minimizes the information that users reveal to a search
engine. Our tool protects users against attacks that involve
active components and timing information, to which more
general Web-browsing privacy tools (including the combination
of FoxTor and Privoxy) are vulnerable. PWS is a
Firefox plugin that functions as an HTTP proxy and as a
client for the Tor anonymity network. It configures Firefox
so that search queries executed from the PWS search
box are routed through the HTTP proxy and Tor client, filtering
potentially sensitive or identifying components of the
request and response.
-
A Model of Onion Routing with Provable Anonymity [pdf] [BibTeX]
Joan
Feigenbaum, Aaron Johnson, and Paul
Syverson
In Proceedings of Financial Cryptography and Data Security '07 (FC 2007).
Show abstract
Onion routing is a scheme for anonymous communication
that is designed for practical use. Until now, however, it has had no formal
model and therefore no rigorous analysis of its anonymity guarantees.
We give an IO-automata model of an onion-routing protocol and, under
possibilistic definitions, characterize the situations in which anonymity
and unlinkability are guaranteed.
