\documentclass[times,10pt,twocolumn]{article} \usepackage{latex8} %\usepackage{times} \usepackage{url} \usepackage{graphics} \usepackage{amsmath} \pagestyle{empty} \renewcommand\url{\begingroup \def\UrlLeft{<}\def\UrlRight{>}\urlstyle{tt}\Url} \newcommand\emailaddr{\begingroup \def\UrlLeft{<}\def\UrlRight{>}\urlstyle{tt}\Url} % If an URL ends up with '%'s in it, that's because the line *in the .bib/.tex % file* is too long, so break it there (it doesn't matter if the next line is % indented with spaces). -DH %\newif\ifpdf %\ifx\pdfoutput\undefined % \pdffalse %\else % \pdfoutput=1 % \pdftrue %\fi \newenvironment{tightlist}{\begin{list}{$\bullet$}{ \setlength{\itemsep}{0mm} \setlength{\parsep}{0mm} % \setlength{\labelsep}{0mm} % \setlength{\labelwidth}{0mm} % \setlength{\topsep}{0mm} }}{\end{list}} \begin{document} %% Use dvipdfm instead. --DH %\ifpdf % \pdfcompresslevel=9 % \pdfpagewidth=\the\paperwidth % \pdfpageheight=\the\paperheight %\fi \title{Tor: Design of a Next-Generation Onion Router} %\author{Roger Dingledine \\ The Free Haven Project \\ arma@freehaven.net \and %Nick Mathewson \\ The Free Haven Project \\ nickm@freehaven.net \and %Paul Syverson \\ Naval Research Lab \\ syverson@itd.nrl.navy.mil} \maketitle \thispagestyle{empty} \begin{abstract} We present Tor, a connection-based low-latency anonymous communication system. It is intended as an update and replacement for onion routing and addresses many limitations in the original onion routing design. Tor 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. \end{abstract} %\begin{center} %\textbf{Keywords:} anonymity, peer-to-peer, remailer, nymserver, reply block %\end{center} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Overview} \label{sec:intro} Onion routing is a distributed overlay network designed to anonymize low-latency TCP-based applications such as web browsing, secure shell, and instant messaging. Users choose a path through the network and build a \emph{virtual circuit}, in which each node in the path knows its predecessor and successor, but no others. Traffic flowing down the circuit is sent in fixed-size \emph{cells}, which are unwrapped by a symmetric key at each node, revealing the downstream node. The original onion routing project published several design and analysis papers \cite{or-jsac98,or-discex00,or-ih96,or-pet00}. While there was briefly a wide area onion routing network, % how long is briefly? a day, a month? -RD the only long-running and publicly accessible implementation was a fragile proof-of-concept that ran on a single machine. Many critical design and deployment issues were never implemented, and the design has not been updated in several years. Here we describe Tor, a protocol for asynchronous, loosely federated onion routers that provides the following improvements over the old onion routing design: \begin{tightlist} \item \textbf{Perfect forward secrecy:} The original onion routing design is vulnerable to a single hostile node recording traffic and later forcing successive nodes in the circuit to decrypt it. Rather than using onions to lay the circuits, Tor uses an incremental or \emph{telescoping} path-building design, where the initiator negotiates session keys with each successive hop in the circuit. Onion replay detection is no longer necessary, and the process of building circuits is more reliable, since the initiator knows which hop failed and can try extending to a new node. \item \textbf{Applications talk to the onion proxy via Socks:} The original onion routing design required a separate proxy for each supported application protocol, resulting in a lot of extra code --- most of which was never written, so most applications were not supported. Tor uses the unified and standard Socks \cite{socks4,socks5} interface, allowing us to support any TCP-based program without modification. \item \textbf{Many applications can share one circuit:} The original onion routing design built one circuit for each request. Aside from the performance issues of doing public key operations for every request, it also turns out that regular communications patterns mean building lots of circuits, which can endanger anonymity. The very first onion routing design \cite{or-ih96} protected against this to some extent by hiding network access behind an onion router/firewall that was also forwarding traffic from other nodes. However, even if this meant complete protection, many users can benefit from onion routing for which neither running one's own node nor such firewall configurations are adequately convenient to be feasible. Those users, especially if they engage in certain unusual communication behaviors, may be identifiable \cite{wright03}. To complicate the possibility of such attacks Tor multiplexes many connections down each circuit, but still rotates the circuit periodically to avoid too much linkability from requests on a single circuit. \item \textbf{No mixing or traffic shaping:} The original onion routing design called for full link padding both between onion routers and between onion proxies (that is, users) and onion routers \cite{or-jsac98}. The later analysis paper \cite{or-pet00} suggested \emph{traffic shaping} to provide similar protection but use less bandwidth, but did not go into detail. However, recent research \cite{econymics} and deployment experience \cite{freedom21-security} indicate that this level of resource use is not practical or economical; and even full link padding is still vulnerable to active attacks \cite{defensive-dropping}. %[An upcoming FC04 paper. I'll add a cite when it's out. -RD] \item \textbf{Leaky pipes:} Through in-band signalling within the circuit, Tor initiators can direct traffic to nodes partway down the circuit. This allows for long-range padding to frustrate traffic shape and volume attacks at the initiator \cite{defensive-dropping}, but because circuits are used by more than one application, it also allows traffic to exit the circuit from the middle -- thus frustrating traffic shape and volume attacks based on observing exit points. %Or something like that. hm. Tone this down maybe? Or support it. -RD %How's that? -PS \item \textbf{Congestion control:} Earlier anonymity designs do not address traffic bottlenecks. Unfortunately, typical approaches to load balancing and flow control in overlay networks involve inter-node control communication and global views of traffic. Our decentralized ack-based congestion control maintains reasonable anonymity while allowing nodes at the edges of the network to detect congestion or flooding attacks and send less data until the congestion subsides. \item \textbf{Directory servers:} Rather than attempting to flood link-state information through the network, which can be unreliable and open to partitioning attacks or outright deception, Tor takes a simplified view towards distributing link-state information. Certain more trusted onion routers also serve as directory servers; they provide signed \emph{directories} describing all routers they know about, and which are currently up. Users periodically download these directories via HTTP. \item \textbf{End-to-end integrity checking:} Without integrity checking on traffic going through the network, any onion router on the path can change the contents of cells as they pass by, e.g. to redirect a connection on the fly so it connects to a different webserver, or to tag encrypted traffic and look for the tagged traffic at the network edges \cite{minion-design}. \item \textbf{Robustness to failed nodes:} A failed node in a traditional mix network means lost messages, but in Tor, users can notice failed nodes while building circuits and route around them. We further provide a simple mechanism that allows connections to be established despite recent node failure or slightly dated information from a directory server. Tor permits onion routers to have \emph{router twins} --- nodes that share the same private decryption key. Note that because connections now have perfect forward secrecy, an onion router still cannot read the traffic on a connection established through its twin even while that connection is active. Also, which nodes are twins can change dynamically depending on current circumstances, and twins may or may not be under the same administrative authority. \item \textbf{Exit policies:} Tor provides a consistent mechanism for each node to specify and advertise its own exit policy. Exit policies are critical in a volunteer-based distributed infrastructure, because each operator is comfortable with allowing different types of traffic to exit the Tor network from his node. \item \textbf{Rendezvous points and location-protected servers:} Tor provides an integrated mechanism for responder-anonymity location-protected servers \end{tightlist} We review previous work in Section \ref{sec:background}, describe our goals and assumptions in Section \ref{sec:assumptions}, and then address the above list of improvements in Sections \ref{sec:design}-\ref{sec:maintaining-anonymity}. We then summarize how our design stands up to known attacks, and conclude with a list of open problems. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Background and threat model} \label{sec:background} \SubSection{Related work} \label{sec:related-work} Modern anonymity designs date to Chaum's Mix-Net\cite{chaum-mix} design of 1981. Chaum proposed hiding sender-recipient connections by wrapping messages in several layers of public key cryptography, and relaying them through a path composed of Mix servers. Mix servers in turn decrypt, delay, and re-order messages, before relay them along the path towards their destinations. Subsequent relay-based anonymity designs have diverged in two principal directions. Some have attempted to maximize anonymity at the cost of introducing comparatively large and variable latencies, for example, Babel\cite{babel}, Mixmaster\cite{mixmaster-spec}, and Mixminion\cite{minion-design}. Because of this decision, such \emph{high-latency} networks are well-suited for anonymous email, but introduce too much lag for interactive tasks such as web browsing, internet chat, or SSH connections. Tor belongs to the second category: \emph{low-latency} designs that attempt to anonymize interactive network traffic. Because such traffic tends to involve a relatively large numbers of packets, it is difficult to prevent an attacker who can eavesdrop entry and exit points from correlating packets entering the anonymity network with packets leaving it. Although some work has been done to frustrate these attacks, most designs protect primarily against traffic analysis rather than traffic confirmation \cite{or-jsac98}. One can pad and limit communication to a constant rate or at least to control the variation in traffic shape. This can have prohibitive bandwidth costs and/or performance limitations. One can also use a cascade (fixed shared route) with a relatively fixed set of users. This assumes a significant degree of agreement and provides an easier target for an active attacker since the endpoints are generally known. However, a practical network with both of these features and thousands of active users has been run for many years (the Java Anon Proxy, aka Web MIXes, \cite{web-mix}). Another low latency design that was proposed independently and at about the same time as onion routing was PipeNet \cite{pipenet}. This provided anonymity protections that were stronger than onion routing's, but at the cost of allowing a single user to shut down the network simply by not sending. It was also never implemented or formally published. The simplest low-latency designs are single-hop proxies such as the Anonymizer \cite{anonymizer}, wherein a single trusted server removes identifying users' data before relaying it. These designs are easy to analyze, but require end-users to trust the anonymizing proxy. More complex are distributed-trust, channel-based anonymizing systems. In these designs, a user establishes one or more medium-term bidirectional end-to-end tunnels to exit servers, and uses those tunnels to deliver a number of low-latency packets to and from one or more destinations per tunnel. Establishing tunnels is comparatively expensive and typically requires public-key cryptography, whereas relaying packets along a tunnel is comparatively inexpensive. Because a tunnel crosses several servers, no single server can learn the user's communication partners. Systems such as earlier versions of Freedom and onion routing build the anonymous channel all at once (using an onion). Later designs of Freedom and onion routing as described herein build the channel in stages as does AnonNet \cite{anonnet}. Amongst other things, this makes perfect forward secrecy feasible. Some systems, such as Crowds \cite{crowds-tissec}, do not rely on the changing appearance of packets to hide the path; rather they employ mechanisms so that an intermediary cannot be sure when it is receiving from/sending to the ultimate initiator. There is no public-key encryption needed for Crowds, but the responder and all data are visible to all nodes on the path so that anonymity of connection initiator depends on filtering all identifying information from the data stream. Crowds is also designed only for HTTP traffic. Hordes \cite{hordes-jcs} is based on Crowds but also uses multicast responses to hide the initiator. Herbivore \cite{herbivore} and P5 \cite{p5} go even further requiring broadcast. They each use broadcast in very different ways, and tradeoffs are made to make broadcast more practical. Both Herbivore and P5 are designed primarily for communication between communicating peers, although Herbivore permits external connections by requesting a peer to serve as a proxy. Allowing easy connections to nonparticipating responders or recipients is a practical requirement for many users, e.g., to visit nonparticipating Web sites or to exchange mail with nonparticipating recipients. Distributed-trust anonymizing systems differ in how they prevent attackers from controlling too many servers and thus compromising too many user paths. Some protocols rely on a centrally maintained set of well-known anonymizing servers. Current Tor design falls into this category. Others (such as Tarzan and MorphMix) allow unknown users to run servers, while using a limited resource (DHT space for Tarzan; IP space for MorphMix) to prevent an attacker from owning too much of the network. Crowds uses a centralized ``blender'' to enforce Crowd membership policy. For small crowds it is suggested that familiarity with all members is adequate. For large diverse crowds, limiting accounts in control of any one party is more difficult: ``(e.g., the blender administrator sets up an account for a user only after receiving a written, notarized request from that user) and each account to one jondo, and by monitoring and limiting the number of jondos on any one net- work (using IP address), the attacker would be forced to launch jondos using many different identities and on many different networks to succeed'' \cite{crowds-tissec}. Many systems have been designed for censorship resistant publishing. The first of these was the Eternity Service \cite{eternity}. Since then, there have been many alternatives and refinements, of which we note but a few \cite{eternity,gap-pets03,freenet-pets00,freehaven-berk,publius,tangler,taz}. From the beginning, traffic analysis resistant communication has been recognized as an important element of censorship resistance because of the relation between the ability to censor material and the ability to find its distribution source. Tor is not primarily for censorship resistance but for anonymous communication. However, Tor's rendezvous points, which enable connections between mutually anonymous entities, also facilitate connections to hidden servers. These building blocks to censorship resistance and other capabilities are described in Section~\ref{sec:rendezvous}. [XXX I'm considering the subsection as ended here for now. I'm leaving the following notes in case we want to revisit any of them. -PS] Channel-based anonymizing systems also differ in their use of dummy traffic. [XXX] Finally, several systems provide low-latency anonymity without channel-based communication. Crowds and [XXX] provide anonymity for HTTP requests; [...] [XXX Mention error recovery?] anonymizer\\ pipenet\\ freedom v1\\ freedom v2\\ onion routing v1\\ isdn-mixes\\ crowds\\ real-time mixes, web mixes\\ anonnet (marc rennhard's stuff)\\ morphmix\\ P5\\ gnunet\\ rewebbers\\ tarzan\\ herbivore\\ hordes\\ cebolla (?)\\ [XXX Close by mentioning where Tor fits.] \Section{Design goals and assumptions} \label{sec:assumptions} \subsection{Goals} % Are these really our goals? ;) -NM Like other low-latency anonymity designs, Tor seeks to frustrate attackers from linking communication partners, or from linking multiple communications to or from a single point. Within this main goal, however, several design considerations have directed Tor's evolution. First, we have tried to build a {\bf deployable} system. [XXX why?] This requirement precludes designs that are expensive to run (for example, by requiring more bandwidth than volunteers will easily provide); designs that place a heavy liability burden on operators (for example, by allowing attackers to implicate operators in illegal activities); and designs that are difficult or expensive to implement (for example, by requiring kernel patches to many operating systems, or ). Second, the system must be {\bf usable}. A hard-to-use system has fewer users --- and because anonymity systems hide users among users, a system with fewer users provides less anonymity. Thus, usability is not only a convenience, but is a security requirement for anonymity systems. Third, the protocol must be {\bf extensible}, so that it can serve as a test-bed for future research in low-latency anonymity systems. (Note that while an extensible protocol benefits researchers, there is a danger that differing choices of extensions will render users distinguishable. Thus, implementations should not permit different protocol extensions to coexist in a single deployed network.) The protocol's design and security parameters must be {\bf conservative}. Additional features impose implementation and complexity costs. [XXX Say that we don't want to try to come up with speculative solutions to problems we don't KNOW how to solve? -NM] [XXX mention something about robustness? But we really aren't that robust. We just assume that tunneled protocols tolerate connection loss. -NM] \subsection{Non-goals} In favoring conservative, deployable designs, we have explicitly deferred a number of goals --- not because they are not desirable in anonymity systems --- but because solving them is either solved elsewhere, or an area of active research without a generally accepted solution. Unlike Tarzan or Morphmix, Tor does not attempt to scale to completely decentralized peer-to-peer environments with thousands of short-lived servers. Tor does not claim to provide a definitive solution to end-to-end timing or intersection attacks for users who do not run their own Onion Routers. % Does that mean we do claim to solve intersection attack for % the enclave-firewall model? -RD Tor does not provide \emph{protocol normalization} like the Anonymizer or Privoxy. In order to provide client indistinguishibility for complex and variable protocols such as HTTP, Tor must be layered with a filtering proxy such as Privoxy. Similarly, Tor does not currently integrate tunneling for non-stream-based protocols; this too must be provided by an external service. Tor is not steganographic: it doesn't try to conceal which users are sending or receiving communications. \SubSection{Adversary Model} \label{subsec:adversary-model} Like all practical low-latency systems, Tor is not secure against a global passive adversary, which is the most commonly assumed adversary for analysis of theoretical anonymous communication designs. The adversary we assume is weaker than global with respect to distribution, but it is not merely passive. We assume a threat model that expands on that from \cite{or-pet00}. The basic adversary components we consider are: \begin{description} \item[Observer:] can observe a connection (e.g., a sniffer on an Internet router), but cannot initiate connections. Observations may include timing and/or volume of packets as well as appearance of individual packets (including headers and content). \item[Disrupter:] can delay (indefinitely) or corrupt traffic on a link. Can change all those things that an observer can observe up to the limits of computational ability (e.g., cannot forge signatures unless a key is compromised). \item[Hostile initiator:] can initiate (or destroy) connections with specific routes as well as vary the timing and content of traffic on the connections it creates. A special case of the disrupter with additional abilities appropriate to its role in forming connections. \item[Hostile responder:] can vary the traffic on the connections made to it including refusing them entirely, intentionally modifying what it sends and at what rate, and selectively closing them. Also a special case of the disrupter. \item[Key breaker:] can break the key used to encrypt connection initiation requests sent to a Tor-node. % Er, there are no long-term private decryption keys. They have % long-term private signing keys, and medium-term onion (decryption) % keys. Plus short-term link keys. Should we lump them together or % separate them out? -RD % % Hmmm, I was talking about the keys used to encrypt the onion skin % that contains the public DH key from the initiator. Is that what you % mean by medium-term onion key? (``Onion key'' used to mean the % session keys distributed in the onion, back when there were onions.) % Also, why are link keys short-term? By link keys I assume you mean % keys that neighbor nodes use to superencrypt all the stuff they send % to each other on a link. Did you mean the session keys? I had been % calling session keys short-term and everything else long-term. I % know I was being sloppy. (I _have_ written papers formalizing % concepts of relative freshness.) But, there's some questions lurking % here. First up, I don't see why the onion-skin encryption key should % be any shorter term than the signature key in terms of threat % resistance. I understand that how we update onion-skin encryption % keys makes them depend on the signature keys. But, this is not the % basis on which we should be deciding about key rotation. Another % question is whether we want to bother with someone who breaks a % signature key as a particular adversary. He should be able to do % nearly the same as a compromised tor-node, although they're not the % same. I reworded above, I'm thinking we should leave other concerns % for later. -PS \item[Compromised Tor-node:] can arbitrarily manipulate the connections under its control, as well as creating new connections (that pass through itself). \end{description} All feasible adversaries can be composed out of these basic adversaries. This includes combinations such as one or more compromised Tor-nodes cooperating with disrupters of links on which those nodes are not adjacent, or such as combinations of hostile outsiders and link observers (who watch links between adjacent Tor-nodes). Note that one type of observer might be a Tor-node. This is sometimes called an honest-but-curious adversary. While an observer Tor-node will perform only correct protocol interactions, it might share information about connections and cannot be assumed to destroy session keys at end of a session. Note that a compromised Tor-node is stronger than any other adversary component in the sense that replacing a component of any adversary with a compromised Tor-node results in a stronger overall adversary (assuming that the compromised Tor-node retains the same signature keys and other private state-information as the component it replaces). In general we are more focused on traffic analysis attacks than traffic confirmation attacks. A user who runs a Tor proxy on his own machine, connects to some remote Tor-node and makes a connection to an open Internet site, such as a public web server, is vulnerable to traffic confirmation. That is, an active attacker who suspects that the particular client is communicating with the particular server will be able to confirm this if she can attack and observe both the connection between the Tor network and the client and that between the Tor network and the server. Even a purely passive attacker will be able to confirm if the timing and volume properties of the traffic on the connnection are unique enough. This is not to say that Tor offers no resistance to traffic confirmation; it does. We defer discussion of this point and of particular attacks until Section~\ref{sec:attacks}, after we have described Tor in more detail. However, we note here some basic assumptions that affect the threat model. [XXX I think this next subsection should be cut, leaving its points for the attacks section. But I'm leaving it here for now. The above line refers to the immediately following SubSection.-PS] \SubSection{Known attacks against low-latency anonymity systems} \label{subsec:known-attacks} We discuss each of these attacks in more detail below, along with the aspects of the Tor design that provide defense. We provide a summary of the attacks and our defenses against them in Section~\ref{sec:attacks}. Passive attacks: simple observation, timing correlation, size correlation, option distinguishability, Active attacks: key compromise, iterated subpoena, run recipient, run a hostile node, compromise entire path, selectively DOS servers, introduce timing into messages, directory attacks, tagging attacks \SubSection{Assumptions} For purposes of this paper, we assume all directory servers are honest % No longer true, see subsec:dirservers below -RD and trusted. Perhaps more accurately, we assume that all users and nodes can perform their own periodic checks on information they have from directory servers and that all will always have access to at least one directory server that they trust and from which they obtain all directory information. Future work may include robustness techniques to cope with a minority dishonest servers. Somewhere between ten percent and twenty percent of nodes are assumed to be compromised. In some circumstances, e.g., if the Tor network is running on a hardened network where all operators have had background checks, the percent of compromised nodes might be much lower. It may be worthwhile to consider cases where many of the `bad' nodes are not fully compromised but simply (passive) observing adversaries or that some nodes have only had compromise of the keys that decrypt connection initiation requests. But, we assume for simplicity that `bad' nodes are compromised in the sense spelled out above. We assume that all adversary components, regardless of their capabilities are collaborating and are connected in an offline clique. We do not assume any hostile users, except in the context of % This sounds horrible. What do you mean we don't assume any hostile % users? Surely we can tolerate some? -RD rendezvous points. Nonetheless, we assume that users vary widely in both the duration and number of times they are connected to the Tor network. They can also be assumed to vary widely in the volume and shape of the traffic they send and receive. [XXX what else?] %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{The Tor Design} \label{sec:design} \Section{Other design decisions} \SubSection{Exit policies and abuse} \label{subsec:exitpolicies} \SubSection{Directory Servers} \label{subsec:dirservers} First-generation Onion Routing designs \cite{or-jsac98,freedom2-arch} did % is or-jsac98 the right cite here? what's our stock OR cite? -RD in-band network status updates: each router flooded a signed statement to its neighbors, which propagated it onward. But anonymizing networks have different security goals than typical link-state routing protocols. For example, we worry more about delays (accidental or intentional) which cause different parts of the network to have different pictures of link-state and topology. We also worry about attacks to deceive a client about the router membership list, topology, or current network state. Such \emph{partitioning attacks} on client knowledge help an adversary with limited resources to efficiently deploy those resources when attacking a target. Instead, Tor uses a small group of redundant directory servers to track network topology and node state such as current keys and exit policies. The directory servers are normal onion routers, but there are only a few of them and they are more trusted. They listen on a separate port as an HTTP server, both so participants can fetch current network state and router lists (a \emph{directory}), and so other onion routers can upload a signed summary of their keys, address, bandwidth, exit policy, etc (\emph{server descriptors}. Of course, a variety of attacks remain. An adversary who controls a directory server can track certain clients by providing different information --- perhaps by listing only nodes under its control as working, or by informing only certain clients about a given node. Moreover, an adversary without control of a directory server can still exploit differences among client knowledge. If Eve knows that node $M$ is listed on server $D_1$ but not on $D_2$, she can use this knowledge to link traffic through $M$ to clients who have queried $D_1$. Thus these directory servers must be synchronized and redundant. The software is distributed with the signature public key of each directory server, and directories must be signed by a threshold of these keys. The directory servers in Tor are modeled after those in Mixminion \cite{minion-design}, but our situation is easier. Firstly, we make the simplifying assumption that all participants agree on who the directory servers are. Secondly, Mixminion needs to predict node behavior --- that is, build a reputation system for guessing future performance of nodes based on past performance, and then figure out a way to build a threshold consensus of these predictions. Tor just needs to get a threshold consensus of the current state of the network. The threshold consensus can be reached with standard Byzantine agreement techniques \cite{castro-liskov}. % Should I just stop the section here? Is the rest crap? -RD But this library, while more efficient than previous Byzantine agreement systems, is still complex and heavyweight for our purposes: we only need to compute a single algorithm, and we do not require strict in-order computation steps. The Tor directory servers build a consensus directory through a simple four-round broadcast protocol. First, each server signs and broadcasts its current opinion to the other directory servers; each server then rebroadcasts all the signed opinions it has received. At this point all directory servers check to see if anybody's cheating. If so, directory service stops, the humans are notified, and that directory server is permanently removed from the network. Assuming no cheating, each directory server then computes a local algorithm on the set of opinions, resulting in a uniform shared directory. Then the servers sign this directory and broadcast it; and finally all servers rebroadcast the directory and all the signatures. The rebroadcast steps ensure that a directory server is heard by either all of the other servers or none of them (some of the links between directory servers may be down). Broadcasts are feasible because there are so few directory servers (currently 3, but we expect to use as many as 9 as the network scales). The actual local algorithm for computing the shared directory is straightforward, and is described in the Tor specification \cite{tor-spec}. % we should, uh, add this to the spec. oh, and write it. -RD \Section{Rendezvous points: location privacy} \label{sec:rendezvous} Rendezvous points are a building block for \emph{location-hidden services} (aka responder anonymity) in the Tor network. Location-hidden services means Bob can offer a tcp service, such as a webserver, without revealing the IP of that service. We provide this censorship resistance for Bob by allowing him to advertise several onion routers (his \emph{Introduction Points}) as his public location. Alice, the client, chooses a node for her \emph{Meeting Point}. She connects to one of Bob's introduction points, informs him about her meeting point, and then waits for him to connect to the meeting point. This extra level of indirection means Bob's introduction points don't open themselves up to abuse by serving files directly, eg if Bob chooses a node in France to serve material distateful to the French. The extra level of indirection also allows Bob to respond to some requests and ignore others. We provide the necessary glue so that Alice can view webpages from Bob's location-hidden webserver with minimal invasive changes. Both Alice and Bob must run local onion proxies. The steps of a rendezvous: \begin{tightlist} \item Bob chooses some Introduction Points, and advertises them on a Distributed Hash Table (DHT). \item Bob establishes onion routing connections to each of his Introduction Points, and waits. \item Alice learns about Bob's service out of band (perhaps Bob told her, or she found it on a website). She looks up the details of Bob's service from the DHT. \item Alice chooses and establishes a Meeting Point (MP) for this transaction. \item Alice goes to one of Bob's Introduction Points, and gives it a blob (encrypted for Bob) which tells him about herself, the Meeting Point she chose, and the first half of an ephemeral key handshake. The Introduction Point sends the blob to Bob. \item Bob chooses whether to ignore the blob, or to onion route to MP. Let's assume the latter. \item MP plugs together Alice and Bob. Note that MP can't recognize Alice, Bob, or the data they transmit (they share a session key). \item Alice sends a Begin cell along the circuit. It arrives at Bob's onion proxy. Bob's onion proxy connects to Bob's webserver. \item Data goes back and forth as usual. \end{tightlist} When establishing an introduction point, Bob provides the onion router with a public ``introduction'' key. The hash of this public key identifies a unique service, and (since Bob is required to sign his messages) prevents anybody else from usurping Bob's introduction point in the future. Bob uses the same public key when establish the other introduction points for that service. The blob that Alice gives the introduction point includes a hash of Bob's public key to identify the service, an optional initial authentication token (the introduction point can do prescreening, eg to block replays), and (encrypted to Bob's public key) the location of the meeting point, a meeting cookie Bob should tell the meeting point so he gets connected to Alice, an optional authentication token so Bob choose whether to respond, and the first half of a DH key exchange. When Bob connects to the meeting place and gets connected to Alice's pipe, his first cell contains the other half of the DH key exchange. % briefly talk about our notion of giving cookies to people proportional % to how important they are, for location-protected servers hardened % against DDoS threat? -RD \subsection{Integration with user applications} For each service Bob offers, he configures his local onion proxy to know the local IP and port of the server, a strategy for authorizating Alices, and a public key. We assume the existence of a robust decentralized efficient lookup system which allows authenticated updates, eg \cite{cfs:sosp01}. (Each onion router could run a node in this lookup system; also note that as a stopgap measure, we can just run a simple lookup system on the directory servers.) Bob publishes into the DHT (indexed by the hash of the public key) the public key, an expiration time (``not valid after''), and the current introduction points for that service. Note that Bob's webserver is completely oblivious to the fact that it's hidden behind the Tor network. As far as Alice's experience goes, we require that her client interface remain a SOCKS proxy, and we require that she shouldn't have to modify her applications. Thus we encode all of the necessary information into the hostname (more correctly, fully qualified domain name) that Alice uses, eg when clicking on a url in her browser. Location-hidden services use the special top level domain called `.onion': thus hostnames take the form x.y.onion where x encodes the hash of PK, and y is the authentication cookie. Alice's onion proxy examines hostnames and recognizes when they're destined for a hidden server. If so, it decodes the PK and starts the rendezvous as described in the table above. \subsection{Previous rendezvous work} Ian Goldberg developed a similar notion of rendezvous points for low-latency anonymity systems \cite{ian-thesis}. His ``service tag'' is the same concept as our ``hash of service's public key''. We make it a hash of the public key so it can be self-authenticating, and so the client can recognize the same service with confidence later on. His design differs from ours in the following ways though. Firstly, Ian suggests that the client should manually hunt down a current location of the service via Gnutella; whereas our use of the DHT makes lookup faster, more robust, and transparent to the user. Secondly, the client and server can share ephemeral DH keys, so at no point in the path is the plaintext exposed. Thirdly, our design is much more practical for deployment in a volunteer network, in terms of getting volunteers to offer introduction and meeting point services. The introduction points do not output any bytes to the clients. And the meeting points don't know the client, the server, or the stuff being transmitted. The indirection scheme is also designed with authentication/authorization in mind -- if the client doesn't include the right cookie with its request for service, the server doesn't even acknowledge its existence. \Section{Maintaining anonymity sets} \label{sec:maintaining-anonymity} packet counting attacks work great against initiators. need to do some level of obfuscation for that. standard link padding for passive link observers. long-range padding for people who own the first hop. are we just screwed against people who insert timing signatures into your traffic? Even regardless of link padding from Alice to the cloud, there will be times when Alice is simply not online. Link padding, at the edges or inside the cloud, does not help for this. how often should we pull down directories? how often send updated server descs? when we start up the client, should we build a circuit immediately, or should the default be to build a circuit only on demand? should we fetch a directory immediately? would we benefit from greater synchronization, to blend with the other users? would the reduced speed hurt us more? does the "you can't see when i'm starting or ending a stream because you can't tell what sort of relay cell it is" idea work, or is just a distraction? does running a server actually get you better protection, because traffic coming from your node could plausibly have come from elsewhere? how much mixing do you need before this is actually plausible, or is it immediately beneficial because many adversary can't see your node? do different exit policies at different exit nodes trash anonymity sets, or not mess with them much? do we get better protection against a realistic adversary by having as many nodes as possible, so he probably can't see the whole network, or by having a small number of nodes that mix traffic well? is a cascade topology a more realistic way to get defenses against traffic confirmation? does the hydra (many inputs, few outputs) topology work better? are we going to get a hydra anyway because most nodes will be middleman nodes? using a circuit many times is good because it's less cpu work good because of predecessor attacks with path rebuilding bad because predecessor attacks can be more likely to link you with a previous circuit since you're so verbose bad because each thing you do on that circuit is linked to the other things you do on that circuit Because Tor runs over TCP, when one of the servers goes down it seems that all the circuits (and thus streams) going over that server must break. This reduces anonymity because everybody needs to reconnect right then (does it? how much?) and because exit connections all break at the same time, and it also reduces usability. It seems the problem is even worse in a p2p environment, because so far such systems don't really provide an incentive for nodes to stay connected when they're done browsing, so we would expect a much higher churn rate than for onion routing. Are there ways of allowing streams to survive the loss of a node in the path? %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Attacks and Defenses} \label{sec:attacks} Below we summarize a variety of attacks and how well our design withstands them. \begin{enumerate} \item \textbf{Passive attacks} \begin{itemize} \item \emph{Simple observation.} \item \emph{Timing correlation.} \item \emph{Size correlation.} \item \emph{Option distinguishability.} \end{itemize} \item \textbf{Active attacks} \begin{itemize} \item \emph{Key compromise.} \item \emph{Iterated subpoena.} \item \emph{Run recipient.} \item \emph{Run a hostile node.} \item \emph{Compromise entire path.} \item \emph{Selectively DoS servers.} \item \emph{Introduce timing into messages.} \item \emph{Tagging attacks.} the exit node can change the content you're getting to try to trick you. similarly, when it rejects you due to exit policy, it could give you a bad IP that sends you somewhere else. \end{itemize} \item \textbf{Directory attacks} \begin{itemize} \item foo \end{itemize} \end{enumerate} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Future Directions and Open Problems} \label{sec:conclusion} Tor brings together many innovations into a unified deployable system. But there are still several attacks that work quite well, as well as a number of sustainability and run-time issues remaining to be ironed out. In particular: \begin{itemize} \item \emph{Scalability:} Since Tor's emphasis currently is on simplicity of design and deployment, the current design won't easily handle more than a few hundred servers, because of its clique topology. Restricted route topologies \cite{danezis-pets03} promise comparable anonymity with much better scaling properties, but we must solve problems like how to randomly form the network without introducing net attacks. % [cascades are a restricted route topology too. we must mention % earlier why we're not satisfied with the cascade approach.]-RD % [We do. At least \item \emph{Cover traffic:} Currently we avoid cover traffic because it introduces clear performance and bandwidth costs, but and its security properties are not well understood. With more research \cite{SS03,defensive-dropping}, the price/value ratio may change, both for link-level cover traffic and also long-range cover traffic. In particular, we expect restricted route topologies to reduce the cost of cover traffic because there are fewer links to cover. \item \emph{Better directory distribution:} Even with the threshold directory agreement algorithm described in \ref{subsec:dirservers}, the directory servers are still trust bottlenecks. We must find more decentralized yet practical ways to distribute up-to-date snapshots of network status without introducing new attacks. \item \emph{Implementing location-hidden servers:} While Section \ref{sec:rendezvous} provides a design for rendezvous points and location-hidden servers, this feature has not yet been implemented. We will likely encounter additional issues, both in terms of usability and anonymity, that must be resolved. \item \emph{Wider-scale deployment:} The original goal of Tor was to gain experience in deploying an anonymizing overlay network, and learn from having actual users. We are now at the point where we can start deploying a wider network. We will see what happens! % ok, so that's hokey. fix it. -RD \end{itemize} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\Section{Acknowledgments} %% commented out for anonymous submission %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \bibliographystyle{latex8} \bibliography{tor-design} \end{document} % Style guide: % U.S. spelling % avoid contractions (it's, can't, etc.) % 'mix', 'mixes' (as noun) % 'mix-net' % 'mix', 'mixing' (as verb) % 'Mixminion Project' % 'Mixminion' (meaning the protocol suite or the network) % 'Mixmaster' (meaning the protocol suite or the network) % 'middleman' [Not with a hyphen; the hyphen has been optional % since Middle English.] % 'nymserver' % 'Cypherpunk', 'Cypherpunks', 'Cypherpunk remailer' % % 'Whenever you are tempted to write 'Very', write 'Damn' instead, so % your editor will take it out for you.' -- Misquoted from Mark Twain