Publications
This is a complete list of all NRL publications on Onion Routing along with on-line copies where possible.
Other publications on anonymous communication, including papers by the Onion Routing team can be found
at the Free Haven Anonymity Bibliography.
“Probabilistic Analysis of Onion Routing in a Black-box Model [Extended Abstract]”, WPES’07:
Proceedings of the 2007 ACM Workshop on Privacy in Electronic Society, ACM Press, October 2007,
pp. 1–10. [PDF]
We perform a probabilistic analysis of onion routing. The analysis is presented in a blackbox 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 bestcase anonymity
against an adversary that controls a fraction sqrt(b).
“Deploying Low-Latency Anonymity: Design Challenges and Social Factors”, IEEE Security &
Privacy, September/October 2007 (Vol. 5, No. 5), pp. 83-87.
(Note: This article is a much updated and abbreviated version of “Challenges in deploying low-latency
anonymity”.) [Plaintext]
Tor (the Onion Routing) is an open source, distributed, low-latency anonymity network.
This article examines how Tor works, the underlying design philosophy, and some of the
challenges in building, deploying, and sustaining a network for anonymous
communications.
“Improving Efficiency and Simplicity of Tor circuit establishment and hidden services”, Proceedings of
the 2007 Privacy Enhancing Technologies Symposium, Springer-Verlag, LNCS 4776. [PDF]
In this paper we demonstrate how to reduce the overhead and delay of circuit
establishment in the Tor anonymizing network by using predistributed Diffie-Hellman
values. We eliminate the use of RSA encryption and decryption from circuit setup, and we
reduce the number of DH exponentiations vs. the current Tor circuit setup protocol while
maintaining immediate forward secrecy. We also describe savings that can be obtained by
precomputing during idle cycles values that can be determined before the protocol starts.
We introduce the distinction of eventual vs. immediate forward secrecy and present
protocols that illustrate the distinction. These protocols are even more efficient in
communication and computation than the one we primarily propose, but they provide only
eventual forward secrecy. We describe how to reduce the overhead and the complexity of
hidden server connections by using our DH-values to implement valet nodes and eliminate
the need for rendezvous points as they exist today. We also discuss the security of the new
elements and an analysis of efficiency improvements.
“A Model of Onion Routing with Provable Anonymity”, Financial Cryptography and Data Security,
11th International Conference, FC 2007, LNCS forthcoming. [PDF]
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.
“Valet Services: Improving Hidden Servers with a Personal Touch”, Proceedings of the 2006 Privacy
Enhancing Technologies Workshop, Springer-Verlag, LNCS 4285. [PDF]
Location hidden services have received increasing attention as a means to resist censorship
and protect the identity of service operators. Research and vulnerability analysis to date
has mainly focused on how to locate the hidden service. But while the hiding techniques
have improved, almost no progress has been made in increasing the resistance against DoS
attacks directly or indirectly on hidden services. In this paper we suggest improvements
that should be easy to adopt within the existing hidden service design, improvements that
will both reduce vulnerability to DoS attacks and add QoS as a service option. In addition
we show how to hide not just the location but the existence of the hidden service from
everyone but the users knowing its service address. Not even the public directory servers
will know how a private hidden service can be contacted, or know it exists.
“Locating Hidden Servers”, Proceedings of the 2006 IEEE Symposium on Security and Privacy, IEEE
CS Press, Oakland, CA, May 2006. [PDF]
Hidden services were deployed on the Tor anonymous communication network in 2004.
Announced properties include server resistance to distributed DoS. Both the EFF and
Reporters Without Borders have issued guides that describe using hidden services via Tor
to protect the safety of dissidents as well as to resist censorship.
We present fast and cheap attacks that reveal the location of a hidden server. Using a single
hostile Tor node we have located deployed hidden servers in a matter of minutes. Although
we examine hidden services over Tor, our results apply to any client using a variety of
anonymity networks. In fact, these are the first actual intersection attacks on any deployed
public network: thus confirming general expectations from prior theory and simulation.
We recommend changes to route selection design and implementation for Tor. These
changes require no operational increase in network overhead and are simple to make; but
they prevent the attacks we have demonstrated. They have been implemented.
“Challenges in deploying low-latency anonymity”, NRL CHACS Report 5540-625, 2005. [PDF]
There are many unexpected or unexpectedly difficult obstacles to deploying anonymous
communications. Drawing on our experiences deploying Tor (the second-generation onion
routing network), we describe social challenges and technical issues that must be faced in
building, deploying, and sustaining a scalable, distributed, low-latency anonymity
network.
“Tor: The Second-Generation Onion Router”, in Proceedings of the 13th USENIX Security
Symposium, August 2004. [PostScript] [Gziped Postscript] [PDF]
We present Tor, a circuit-based low-latency anonymous communication service. This
second-generation Onion Routing system addresses limitations in the original design by
adding perfect forward secrecy, congestion control, directory servers, integrity checking,
configurable exit policies, and a practical design for location-hidden services via
rendezvous points. Tor works on the real-world Internet, requires no special privileges or
kernel modifications, requires little synchronization or coordination between nodes, and
provides a reasonable tradeoff between anonymity, usability, and efficiency. We briefly
describe our experiences with an international network of more than 30 nodes. We close
with a list of open problems in anonymous communication.
“Onion Routing Access Configurations,” DISCEX 2000: Proceedings of the DARPA Information
Survivability Conference and Exposition, Volume I Hilton Head, SC, IEEE CS Press, January 2000,
pp. 34–40. [PostScript] [Gziped Postscript] [PDF]
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. Thus it hides not only the data being sent, but who is talking to whom.
Onion Routing’s anonymous connections are bidirectional and near real-time, and can be
used anywhere a socket connection can be used. Proxy aware applications, such as web
browsing and e-mail, require no modification to use Onion Routing, and do so through a
series of proxies. Other applications, such as remote login, can also use the system without
modification. Access to an onion routing network can be configured in a variety of ways
depending on the needs, policies, and facilities of those connecting. This paper describes
some of these access configurations and also provides a basic overview of Onion Routing
and comparisons with related work.
“Towards an Analysis of Onion Routing Security,” Workshop on Design Issues in Anonymity and
Unobservability Berkeley, CA, July 2000. [PostScript] [Gziped Postscript] [PDF]
This paper presents a security analysis of Onion Routing, an application independent
infrastructure for traffic-analysis-resistant and anonymous Internet connections. It also
includes an overview of the current system design, definitions of security goals and new
adversary models.
“Onion Routing,” Proceeding of AIPA ’99, March 1999. [PostScript] [Gziped Postscript] [PDF]
The primary goal of Onion Routing is to provide private, traffic analysis resistant
communications over a public network at reasonable cost and efficiency. Communications
are intended to be private in the sense that both the public network itself and any
eavesdropper on the network cannot determine the contents of messages flowing from
Alice and Bob, and she cannot tell that Alice and Bob are communicating with each other.
A secondary goal is to provide anonymity to the sender and receiver, so that Alice may
receive messages but be unable to identify the sender, even though she may be able to
reply those messages. For example, open source intelligence gathering via the web and
pseudonym based email communications that hide the true identities of both sender and
receiver.
“Onion Routing for Anonymous and Private Internet Connections,” Communications of the ACM, vol.
42, num. 2, February 1999. [PostScript] [Gziped Postscript] [PDF]
Preserving privacy means not only hiding the content of messages, but also hiding who is
talking to whom (traffic analysis). Much like a physical envelope, the simple application of
cryptography within a packet-switched network hides the messages being sent, but can
reveal who is talking to whom, and how often. Onion Routing is a general purpose
infrastructure for private communication over a public network. It provides anonymous
connections that are strongly resistant to both eavesdropping and traffic analysis. The
connections are bidirectional, near real-time, and can be used for both connection-based
and connectionless traffic. Onion Routing interfaces with off the shelf software and
systems through specialized proxies, making it easy to integrate into existing systems.
Prototypes have been running since July 1997. As of this article’s publication, the
prototype network is processing more than 1 million Web connections per month from
more than six thousand IP addresses in twenty countries and in all six main top level
domains.
Onion Routing operates by dynamically building anonymous connections within a network
of real-time Chaum Mixes. A Mix is a store and forward device that accepts a number of
fixed-length messages from numerous sources, performs cryptographic transformations on
the messages, and then forwards the messages to the next destination in a random order. A
single Mix makes tracking of a particular message either by specific bit-pattern, size, or
ordering with respect to other messages difficult. By routing through numerous Mixes in
the network, determining who is talking to whom becomes even more difficult. Onion
Routing’s network of core onion-routers (Mixes) is distributed, fault-tolerant, and under
the control of multiple administrative domains, so no single onion-router can bring down
the network or compromise a user’s privacy, and cooperation between compromised onionrouters is thereby confounded.
“Anonymous Connections and Onion Routing,” IEEE Journal on Selected Areas in Communication
Special Issue on Copyright and Privacy Protection, 1998. [Postscript] [Gziped Postscript] [PDF]
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 and near realtime, and can be used anywhere a socket connection can be used. (In some contexts not
even socket connections are needed to use onion routing.) 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 differently 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 browsing and email, require no
modification to use onion routing, and do so through a series of proxies. A prototype of
onion routing is running in our lab. 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.
“Private Web Browsing,” Journal of Computer Security Special Issue on Web Security, Volume 5,
Number 3, 1997, pp. 237-248. [Postscript] [Gziped Postscript] [PDF]
This paper describes a communications primitive, anonymous connections, that support
bidirectional and near real-time channels that are resistant to both eavesdropping and
traffic analysis. The connections are made anonymous, although communication need not
be. These anonymous connections are versatile and support private use of many different
Internet services. For our purposes, privacy means maintaining the confidentiality of both
the data stream and the identity of communicating parties. These are both kept confidential
from network elements as well as external observers. Private Web browsing is achieved by
unmodified Web browsers using anonymous connections by means of HTTP proxies.
Private Web browsing may be made anonymous too by a specialized proxy that removes
identifying information from the HTTP data stream. This article specifies anonymous
connections, describes our implementation, and discusses its application to Web browsing
via HTTP proxies.
“Privacy on the Internet,” INET ’97, Kuala Lumpur, Malaysia, June 1997. [HTML]
The World Wide Web is rapidly becoming an important tool for modern day
communication and commerce. But electronic messages sent over the Internet can be
easily snooped and tracked revealing who is talking to whom and what they are talking
about. Is privacy important and how can it be guaranteed? This paper describes how a
freely available system, onion routing, can be used to provide privacy for a wide variety of
Internet services, including Virtual Private Networks, Web browsing, e-mail, remote login,
and electronic cash.
“Protocols using Anonymous Connections: Mobile Applications,” Security Protocols, 5th International
Workshop Proceedings, B. Christianson, B. Crispo, M. Lomas, and M. Roe (editors), Springer-Verlag
LNCS 1361, 1998, pp. 13-23. [Postscript] [Gziped Postscript] [PDF]
This paper describes security protocols that use anonymous channels, which do not reveal
their endpoints, as primitive, much in the way that key distribution protocols take
encryption as primitive. This abstraction allows us to focus on high level security goals of
these protocols much as abstracting away from encryption clarifies and emphasizes high
level security goals of key distribution protocols. The protocols described are for mobile
applications that protect the location information of the participating principals.
“Anonymous Connections and Onion Routing,” Proceedings of the 18th Annual Symposium on
Security and Privacy, IEEE CS Press, Oakland, CA, May 1997, pp. 44-54. [Postscript] [Gziped
Postscript] [PDF]
Onion Routing provides anonymous connections that are strongly resistant to both
eavesdropping and traffic analysis. Unmodified Internet applications can use these
anonymous connections by means of proxies. The proxies may also make communication
anonymous by removing identification from the data stream. Onion Routing has been
implemented on Sun Solaris 2.4 with proxies for Web browsing, remote logins, and e-mail.
This paper’s contribution is a detailed specification of the implemented onion routing
system, a vulnerability analysis base on this specification, and performance results.
“Internet Communication Resistant to Traffic Analysis,” 1997 NRL Review, Washington, DC, April
1997, pp. 109-111.
Determining who is talking to whom (called traffic analysis) is an important source of
intelligence information. As military grade communication devices increasingly depend on
the public communications infrastructure, it is important to use that infrastructure in ways
that are resistant to traffic analysis. It may also be useful to communicate anonymously, for
example when gathering intelligence from public databases. We describe bidirectional and
real-time Anonymous Connections that are strongly resistant to eavesdropping and traffic
analysis attacks by both insiders and outsiders. If necessary, communication is made
anonymous by removing identifying information from the data stream. These anonymous
connections have been prototyped in a system that protects the privacy of communication
over the Internet and, in particular, the World Wide Web. Anonymous connections can
protect both identity and location in many switched communication systems, such as
wired, cellular, or satellite phone networks.
“Proxies for Anonymous Routing,” Proceedings of the 12th Annual Computer Security Applications
Conference, IEEE CS Press, San Diego, CA, December 1996, pp. 95-104. [Postscript] [Gziped
Postscript] [PDF]
Using traffic analysis, it is possible to infer who is talking to whom over a public network.
This paper describes a flexible communication infrastructure, Onion Routing, which is
resistant to traffic analysis. Onion Routing lives just beneath the application layer, and is
designed to interface with a wide variety of unmodified Internet services by means of
proxies. Onion Routing has been implemented on Sun Solaris 2.4; in addition, proxies for
World Wide Web browsing (HTTP), remote logins (RLOGIN), e-mail (SMTP), and file
transfers (FTP) have been implemented.
Onion Routing provides application independent, real-time, and bi-directional anonymous
connections that are resistant to both eavesdropping and traffic analysis. Applications
making use of Onion Routing’s anonymous connections may (and usually should) identify
their users over the anonymous connection. User anonymity may be layered on top of the
anonymous connections by removing identifying information from the data stream. Our
goal here is anonymous connections, not anonymous communication. The use of a packet
switched public network should not automatically reveal who is talking to whom. This is
the traffic analysis that Onion Routing complicates.
“Hiding Routing Information,” Information Hiding, R. Anderson (editor), Springer-Verlag LLNCS
1174, 1996, pp. 137-150. [Postscript] [Gziped Postscript] [PDF]
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. Proxies for FTP and SMTP are
under development.
Original (Old) Onion Routing briefing slides. [Postscript] [Gziped Postscript] [PDF]
These slides describe Onion Routing and uses of Onion Routing in 1996.
Generation 2 Onion Routing briefing slides. [Postscript] [Gziped Postscript] [PDF]
These slides describe motivation for and uses of Tor and hidden services. They evolved
through late 2003 and early 2004, and were presented at many venues as they evolved. The
earliest parts were shown at the DARPA Fault Tolerant Networks PI meeting, July 2003.
The version given here was presented at the National Science Foundation, June 2004. A
version of them was also used to present the Tor design paper at the USENIX Security
Symposium, August 2004. See the Tor site for other slides and other versions.
Onion Routing Home Page
Onion Routing Executive Summary
The Traffic Analysis Problem…
The Onion Routing Solution
A Brief History of Onion Routing
Onion Routing Publications
Other Privacy Sites
Our Sponsors
Some Privacy Test Sites
NRL Onion Routing Archives, Test Data, Specs
Historical page reflecting onion-router.net as of 2005, not regularly maintained. Address questions to Paul
Syverson.