Abstract:
Tor is a tool for Internet privacy with millions of daily users.
The Tor system benefits in many ways from information gathered
about the operation of its network. Measurements guide operators
in diagnosing problems, direct the efforts of developers, educate users about
the level of privacy they obtain, and inform policymakers about Tor's impact.
However, data collection and reporting can degrade user privacy, contradicting
Tor's goals. Existing approaches to measuring Tor have limited capabilities and
security weaknesses.
We present Stormy, a general-purpose, privacy-preserving measurement system
that overcomes these limitations. Stormy uses secure multiparty
computation (MPC) to compute any function of the observations made by Tor
relays, while keeping those observations secret. Stormy makes use of
existing efficient MPC protocols that are secure in the malicious model, and in
addition it includes a novel input-sharing protocol that is secure,
efficient, and fault tolerant. The protocol is non-interactive, which is
consistent with how relays currently submit measurements, and it allows the
relays to go offline after input submission, even while ensuring that an honest
relay will not have its input excluded or modified. The input-sharing protocol
is compatible with MPC protocols computing on authenticated values and may be of
independent interest.
We show how Stormy can be deployed in two realistic models: (1) run
primarily by a small set of dedicated authorities, or (2) run decentralized
across the relays in the Tor network. Stormy scales efficiently to Tor's
thousands of relays, tolerates network churn, and provides security depending
only on either Tor's existing trust assumption that at least one authority is
honest (in the first model) or the existing assumption that a large fraction of relay bandwidth is
honest (in the second model).
We demonstrate how to use the system to compute two broadly-applicable
statistics: the median of relay inputs and the cardinality of set-union across
relays. We implement Stormy and experimentally evaluate system
performance. When Stormy is run among authorities we can perform 151 median
computations or 533 set-union cardinalities over 7,000 relay inputs in a single
day. When run among the relays themselves, Stormy can perform 36 median
computations or 134 set union cardinalities per day. Thus, both deployments
enable non-trivial analytics to be securely computed in the Tor network.
@inproceedings{wjsyg-stormy-ccs19,
author = {Wails, Ryan and Johnson, Aaron and Starin, Daniel and Yerukhimovich, Arkady and Gordon, S. Dov},
title = {Stormy: Statistics in Tor by Measuring Securely},
booktitle = {Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security},
series = {CCS '19},
year = {2019},
pages = {615--632},
url = {http://doi.acm.org/10.1145/3319535.3345650},
doi = {10.1145/3319535.3345650},
}