1 \documentclass[times,
10pt,twocolumn
]{article
}
10 \renewcommand\url{\begingroup \def\UrlLeft{<
}\def\UrlRight{>
}\urlstyle{tt
}\Url}
11 \newcommand\emailaddr{\begingroup \def\UrlLeft{<
}\def\UrlRight{>
}\urlstyle{tt
}\Url}
13 % If an URL ends up with '%'s in it, that's because the line *in the .bib/.tex
14 % file* is too long, so break it there (it doesn't matter if the next line is
15 % indented with spaces). -DH
18 %\ifx\pdfoutput\undefined
25 \newenvironment{tightlist
}{\begin{list
}{$
\bullet$
}{
26 \setlength{\itemsep}{0mm
}
27 \setlength{\parsep}{0mm
}
28 % \setlength{\labelsep}{0mm}
29 % \setlength{\labelwidth}{0mm}
30 % \setlength{\topsep}{0mm}
35 %% Use dvipdfm instead. --DH
38 % \pdfpagewidth=\the\paperwidth
39 % \pdfpageheight=\the\paperheight
42 \title{Tor: The Second-Generation Onion Router
}
43 % Putting the 'Private' back in 'Virtual Private Network'
45 %\author{Roger Dingledine \\ The Free Haven Project \\ arma@freehaven.net \and
46 %Nick Mathewson \\ The Free Haven Project \\ nickm@freehaven.net \and
47 %Paul Syverson \\ Naval Research Lab \\ syverson@itd.nrl.navy.mil}
53 We present Tor, a circuit-based low-latency anonymous communication
54 system. This second-generation Onion Routing system addresses limitations
55 in the original design. We add perfect forward secrecy, congestion
56 control, directory servers, integrity checking, variable exit policies,
57 and a practical design for rendezvous points. Tor works on the real-world
58 Internet, requires no special privileges or kernel modifications, requires
59 little synchronization or coordination between nodes, and provides a
60 reasonable trade-off between anonymity, usability, and efficiency. We
61 close with a list of open problems in anonymous communication systems.
65 %\textbf{Keywords:} anonymity, peer-to-peer, remailer, nymserver, reply block
68 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
73 Onion Routing is a distributed overlay network designed to anonymize
74 low-latency TCP-based applications such as web browsing, secure shell,
75 and instant messaging. Clients choose a path through the network and
76 build a
\emph{virtual circuit
}, in which each node (or ``onion router'')
77 in the path knows its predecessor and successor, but no other nodes in
78 the circuit. Traffic flowing down the circuit is sent in fixed-size
79 \emph{cells
}, which are unwrapped by a symmetric key at each node
80 (like the layers of an onion) and relayed downstream. The original
81 Onion Routing project published several design and analysis papers
82 \cite{or-ih96,or-jsac98,or-discex00,or-pet00
}. While a wide area Onion
83 Routing network was deployed for some weeks, the only long-running and
84 publicly accessible implementation of the original design was a fragile
85 proof-of-concept that ran on a single machine. Even this simple deployment
86 processed tens of thousands of connections daily from thousands of users
87 worldwide. But many critical design and deployment issues were never
88 resolved, and the design has not been updated in several years. Here
89 we describe Tor, a protocol for asynchronous, loosely federated onion
90 routers that provides the following improvements over the old Onion
95 \item \textbf{Perfect forward secrecy:
} The original Onion Routing
96 design was vulnerable to a single hostile node recording traffic and
97 later compromising successive nodes in the circuit and forcing them
98 to decrypt it. Rather than using a single onion to lay each circuit,
99 Tor now uses an incremental or
\emph{telescoping
} path-building design,
100 where the initiator negotiates session keys with each successive hop in
101 the circuit. Once these keys are deleted, subsequently compromised nodes
102 cannot decrypt old traffic. As a side benefit, onion replay detection
103 is no longer necessary, and the process of building circuits is more
104 reliable, since the initiator knows when a hop fails and can then try
105 extending to a new node.
107 \item \textbf{Separation of protocol cleaning from anonymity:
}
108 The original Onion Routing design required a separate ``application
109 proxy'' for each supported application protocol---most of which were
110 never written, so many applications were never supported. Tor uses the
111 standard and near-ubiquitous SOCKS
\cite{socks4
} proxy interface, allowing
112 us to support most TCP-based programs without modification. This design
113 change allows Tor to use the filtering features of privacy-enhancing
114 application-level proxies such as Privoxy
\cite{privoxy
} without having
115 to incorporate those features itself.
117 \item \textbf{Many TCP streams can share one circuit:
} The
118 original Onion Routing design built a separate circuit for each
119 application-level request. This hurt performance by requiring
120 multiple public key operations for every request, and also presented
121 a threat to anonymity from building so many different circuits; see
122 Section~
\ref{sec:maintaining-anonymity
}. Tor multiplexes multiple TCP
123 streams along each virtual circuit, to improve efficiency and anonymity.
125 \item \textbf{Leaky-pipe circuit topology:
} Through in-band signalling
126 within the circuit, Tor initiators can direct traffic to nodes partway
127 down the circuit. This novel approach allows both for long-range
128 padding to frustrate traffic shape and volume attacks at the initiator
129 \cite{defensive-dropping
}, and, because circuits are used by more than one
130 application, allows traffic to exit the circuit from the middle---thus
131 frustrating traffic shape and volume attacks based on observing the end
134 \item \textbf{No mixing, padding, or traffic shaping:
} The original Onion
135 Routing design called for batching and reordering the cells arriving from
136 each circuit. It also included padding between onion routers and, in a
137 later design, between onion proxies (that is, users) and onion routers
138 \cite{or-ih96,or-jsac98
}. The trade-off between padding protection
139 and cost was discussed, but no general padding scheme was suggested. In
140 \cite{or-pet00
} it was theorized
\emph{traffic shaping
} would generally
141 be used, but details were not provided. Recent research
\cite{econymics
}
142 and deployment experience
\cite{freedom21-security
} suggest that this
143 level of resource use is not practical or economical; and even full link
144 padding is still vulnerable
\cite{defensive-dropping
}. Thus, until we
145 have a proven and convenient design for traffic shaping or low-latency
146 mixing that will improve anonymity against a realistic adversary, we
147 leave these strategies out.
149 \item \textbf{Congestion control:
} Earlier anonymity designs do not
150 address traffic bottlenecks. Unfortunately, typical approaches to
151 load balancing and flow control in overlay networks involve inter-node
152 control communication and global views of traffic. Tor's decentralized
153 congestion control uses end-to-end acks to maintain reasonable anonymity
154 while allowing nodes at the edges of the network to detect congestion
155 or flooding attacks and send less data until the congestion subsides.
157 \item \textbf{Directory servers:
} The original Onion Routing design
158 planned to flood link-state information through the network---an approach
159 that can be unreliable and open to partitioning attacks or outright
160 deception. Tor takes a simplified view toward distributing link-state
161 information. Certain more trusted onion routers also act as directory
162 servers: they provide signed
\emph{directories
} that describe known
163 routers and their availability. Users periodically download these
164 directories via HTTP.
166 \item \textbf{Variable exit policies:
} Tor provides a consistent mechanism
167 for each node to specify and advertise a policy describing the hosts
168 and ports to which it will connect. These exit policies are critical
169 in a volunteer-based distributed infrastructure, because each operator
170 is comfortable with allowing different types of traffic to exit the Tor
171 network from his node.
173 \item \textbf{End-to-end integrity checking:
} The original Onion Routing
174 design did no integrity checking on data. Any onion router on the
175 circuit could change the contents of data cells as they passed by---for
176 example, to alter a connection request on the fly so it would connect
177 to a different webserver, or to `tag' encrypted traffic and look for
178 corresponding corrupted traffic at the network edges
\cite{minion-design
}.
179 Tor hampers these attacks by checking data integrity before it leaves
182 \item \textbf{Improved robustness to failed nodes:
} A failed node
183 in the old design meant that circuit-building failed, but thanks to
184 Tor's step-by-step circuit building, users can notice failed nodes
185 while building circuits and route around them. Additionally, liveness
186 information from directories allows users to avoid unreliable nodes in
189 \item \textbf{Rendezvous points and location-protected servers:
}
190 Tor provides an integrated mechanism for responder anonymity via
191 location-protected servers. Previous Onion Routing designs included
192 long-lived ``reply onions'' that could be used to build virtual circuits
193 to a hidden server, but these reply onions did not provide forward
194 security, and would become useless if any node in the path went down
195 or rotated its keys. In Tor, clients negotiate
{\it rendezvous points
}
196 to connect with hidden servers; reply onions are no longer required.
199 Unlike anonymity systems like Freedom
\cite{freedom2-arch
}, Tor only
200 attempts to anonymize TCP streams. Because it does not require patches
201 (or built-in support) in an operating system's network stack, this
202 approach has proven valuable to Tor's portability and deployability.
204 We have implemented most of the above features. Our source code is
205 available under a free license, and we believe it to be unencumbered by
206 patents. We have recently begun deploying a widespread alpha network
207 to test the design in practice, to get more experience with usability
208 and users, and to provide a research platform for experimenting with
211 We review previous work in Section~
\ref{sec:related-work
}, describe
212 our goals and assumptions in Section~
\ref{sec:assumptions
},
213 and then address the above list of improvements in
214 Sections~
\ref{sec:design
}-
\ref{sec:rendezvous
}. We summarize
215 in Section~
\ref{sec:analysis
} how our design stands up to
216 known attacks, and conclude with a list of open problems in
217 Section~
\ref{sec:maintaining-anonymity
} and future work for the Onion
218 Routing project in Section~
\ref{sec:conclusion
}.
220 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
222 \Section{Related work
}
223 \label{sec:related-work
}
225 Modern anonymity systems date to Chaum's Mix-Net design
226 \cite{chaum-mix
}. Chaum
227 proposed hiding the correspondence between sender and recipient by
228 wrapping messages in layers of public key cryptography, and relaying them
229 through a path composed of ``Mixes.'' These mixes in turn decrypt, delay,
230 and re-order messages, before relaying them along the sender-selected
231 path towards their destinations.
233 Subsequent relay-based anonymity designs have diverged in two
234 principal directions. Some have attempted to maximize anonymity at
235 the cost of introducing comparatively large and variable latencies,
236 including Babel
\cite{babel
}, Mixmaster
\cite{mixmaster-spec
}, and
237 Mixminion
\cite{minion-design
}. Because of this
238 decision, these
\emph{high-latency
} networks are well-suited for anonymous
239 email, but introduce too much lag for interactive tasks such as web browsing,
240 internet chat, or SSH connections.
242 Tor belongs to the second category:
\emph{low-latency
} designs that
243 attempt to anonymize interactive network traffic. These systems handle
244 a variety of bidirectional protocols. They also provide more convenient
245 mail delivery than the high-latency fire-and-forget anonymous email
246 networks, because the remote mail server provides explicit delivery
247 confirmation. But because these designs typically
248 involve many packets that must be delivered quickly, it is
249 difficult for them to prevent an attacker who can eavesdrop both ends of the
250 communication from correlating the timing and volume
251 of traffic entering the anonymity network with traffic leaving it. These
252 protocols are also vulnerable against active attacks in which an
253 adversary introduces timing patterns into traffic entering the network, and
255 for correlated patterns among exiting traffic.
256 Although some work has been done to frustrate
257 these attacks,
\footnote{
258 The most common approach is to pad and limit communication to a constant
260 the variation in traffic shape. Doing so can have prohibitive bandwidth
261 costs and/or performance limitations.
262 } most designs protect primarily against traffic analysis rather than traffic
263 confirmation
\cite{or-jsac98
}---that is, they assume that the attacker is
264 attempting to learn who is talking to whom, not to confirm a prior suspicion
265 about who is talking to whom.
267 The simplest low-latency designs are single-hop proxies such as the
268 Anonymizer
\cite{anonymizer
}, wherein a single trusted server strips the
269 data's origin before relaying it. These designs are easy to
270 analyze, but require end-users to trust the anonymizing proxy.
271 Concentrating the traffic to a single point increases the anonymity set
272 (the set of people a given user is hiding among), but it can make traffic
273 analysis easier: an adversary need only eavesdrop on the proxy to observe
276 More complex are distributed-trust, circuit-based anonymizing systems.
277 In these designs, a user establishes one or more medium-term bidirectional
278 end-to-end circuits, and tunnels TCP streams in fixed-size cells.
279 Establishing circuits is computationally expensive and typically
281 cryptography, whereas relaying cells is comparatively inexpensive and
282 typically requires only symmetric encryption.
283 Because a circuit crosses several servers, and each server only knows
284 the adjacent servers in the circuit, no single server can link a
285 user to her communication partners.
287 The Java Anon Proxy (also known as JAP or Web MIXes) uses fixed shared
288 routes known as
\emph{cascades
}. As with a single-hop proxy, this
289 approach aggregates users into larger anonymity sets, but again an
290 attacker only needs to observe both ends of the cascade to bridge all
291 the system's traffic. The Java Anon Proxy's design provides
292 protection by padding between end users and the head of the cascade
293 \cite{web-mix
}. However, it is not demonstrated whether the current
294 implementation's padding policy improves anonymity.
296 PipeNet
\cite{back01, pipenet
}, another low-latency design proposed at
297 about the same time as the original Onion Routing design, provided
298 stronger anonymity at the cost of allowing a single user to shut
299 down the network simply by not sending. Low-latency anonymous
300 communication has also been designed for other environments such as
301 ISDN
\cite{isdn-mixes
}.
303 In P2P designs like Tarzan
\cite{tarzan:ccs02
} and MorphMix
304 \cite{morphmix:fc04
}, all participants both generate traffic and relay
305 traffic for others. These systems aim to prevent a peer
306 or observer from knowing whether a given peer originated a request
307 or just relayed it from another peer. While Tarzan and MorphMix use
308 layered encryption as above, Crowds
\cite{crowds-tissec
} simply assumes
309 an adversary who cannot observe the initiator: it uses no public-key
310 encryption, so nodes on a circuit can read that circuit's traffic.
312 Hordes
\cite{hordes-jcs
} is based on Crowds but also uses multicast
313 responses to hide the initiator. Herbivore
\cite{herbivore
} and P5
314 \cite{p5
} go even further, requiring broadcast. They make anonymity
315 and efficiency trade-offs to make broadcast more practical.
316 These systems are designed primarily for communication between peers,
317 although Herbivore users can make external connections by
318 requesting a peer to serve as a proxy.
320 Systems like Freedom and the original Onion Routing build the circuit
321 all at once, using a layered ``onion'' of public-key encrypted messages,
322 each layer of which provides a set of session keys and the address of the
323 next server in the circuit. Tor as described herein, Tarzan, MorphMix,
324 Cebolla
\cite{cebolla
}, and AnonNet
\cite{anonnet
} build the circuit
325 in stages, extending it one hop at a time.
326 Section~
\ref{subsubsec:constructing-a-circuit
} describes how this
327 approach makes perfect forward secrecy feasible.
329 Circuit-based anonymity designs must choose which protocol layer
330 to anonymize. They may choose to intercept IP packets directly, and
331 relay them whole (stripping the source address) along the circuit
332 \cite{freedom2-arch,tarzan:ccs02
}. Alternatively, like
333 Tor, they may accept TCP streams and relay the data in those streams
334 along the circuit, ignoring the breakdown of that data into TCP frames
335 \cite{morphmix:fc04,anonnet
}. Finally, they may accept application-level
336 protocols (such as HTTP) and relay the application requests themselves
338 Making this protocol-layer decision requires a compromise between flexibility
339 and anonymity. For example, a system that understands HTTP can strip
340 identifying information from those requests, can take advantage of caching
341 to limit the number of requests that leave the network, and can batch
342 or encode those requests in order to minimize the number of connections.
343 On the other hand, an IP-level anonymizer can handle nearly any protocol,
344 even ones unforeseen by their designers (though these systems require
345 kernel-level modifications to some operating systems, and so are more
346 complex and less portable). TCP-level anonymity networks like Tor present
347 a middle approach: they are fairly application neutral (so long as the
348 application supports, or can be tunneled across, TCP), but by treating
349 application connections as data streams rather than raw TCP packets,
350 they avoid the well-known inefficiencies of tunneling TCP over TCP
351 \cite{tcp-over-tcp-is-bad
}.
353 Distributed-trust anonymizing systems need to prevent attackers from
354 adding too many servers and thus compromising too many user paths.
355 Tor relies on a small set of well-known directory servers, run by
356 independent parties, to make decisions about which nodes can
357 join. Tarzan and MorphMix allow unknown users to run servers, and use
358 a limited resource (like IP addresses) to prevent an attacker from
359 controlling too much of the network. Crowds suggests requiring
360 written, notarized requests from potential crowd members.
362 Anonymous communication is essential for censorship-resistant
363 systems like Eternity
\cite{eternity
}, Free~Haven
\cite{freehaven-berk
},
364 Publius
\cite{publius
}, and Tangler
\cite{tangler
}. Tor's rendezvous
365 points enable connections between mutually anonymous entities; they
366 are a building block for location-hidden servers, which are needed by
367 Eternity and Free~Haven.
369 % didn't include rewebbers. No clear place to put them, so I'll leave
370 % them out for now. -RD
372 \Section{Design goals and assumptions
}
373 \label{sec:assumptions
}
376 Like other low-latency anonymity designs, Tor seeks to frustrate
377 attackers from linking communication partners, or from linking
378 multiple communications to or from a single user. Within this
379 main goal, however, several design considerations have directed
382 \textbf{Deployability:
} The design must be one that can be implemented,
383 deployed, and used in the real world. This requirement precludes designs
384 that are expensive to run (for example, by requiring more bandwidth
385 than volunteers are willing to provide); designs that place a heavy
386 liability burden on operators (for example, by allowing attackers to
387 implicate onion routers in illegal activities); and designs that are
388 difficult or expensive to implement (for example, by requiring kernel
389 patches, or separate proxies for every protocol). This requirement also
390 precludes systems in which non-anonymous parties (such as websites)
391 must run our software. (We do not meet this goal for the current
393 however; see Section~
\ref{sec:rendezvous
}.)
395 \textbf{Usability:
} A hard-to-use system has fewer users---and because
396 anonymity systems hide users among users, a system with fewer users
397 provides less anonymity. Usability is thus not only a convenience for Tor:
398 it is a security requirement
\cite{econymics,back01
}. Tor should
400 require modifying applications; should not introduce prohibitive delays;
401 and should require the user to make as few configuration decisions
404 \textbf{Flexibility:
} The protocol must be flexible and well-specified,
405 so that it can serve as a test-bed for future research in low-latency
406 anonymity systems. Many of the open problems in low-latency anonymity
407 networks, such as generating dummy traffic or preventing Sybil attacks
408 \cite{sybil
}, may be solvable independently from the issues solved by
409 Tor. Hopefully future systems will not need to reinvent Tor's design.
410 (But note that while a flexible design benefits researchers,
411 there is a danger that differing choices of extensions will make users
412 distinguishable. Experiments should be run on a separate network.)
414 \textbf{Simple design:
} The protocol's design and security
415 parameters must be well-understood. Additional features impose implementation
416 and complexity costs; adding unproven techniques to the design threatens
417 deployability, readability, and ease of security analysis. Tor aims to
418 deploy a simple and stable system that integrates the best well-understood
419 approaches to protecting anonymity.
421 \SubSection{Non-goals
}
422 \label{subsec:non-goals
}
423 In favoring simple, deployable designs, we have explicitly deferred
424 several possible goals, either because they are solved elsewhere, or because
425 their solution is an open research problem.
427 \textbf{Not Peer-to-peer:
} Tarzan and MorphMix aim to scale to completely
428 decentralized peer-to-peer environments with thousands of short-lived
429 servers, many of which may be controlled by an adversary. This approach
430 is appealing, but still has many open problems
431 \cite{tarzan:ccs02,morphmix:fc04
}.
433 \textbf{Not secure against end-to-end attacks:
} Tor does not claim
434 to provide a definitive solution to end-to-end timing or intersection
435 attacks. Some approaches, such as running an onion router, may help;
436 see Section~
\ref{sec:analysis
} for more discussion.
438 \textbf{No protocol normalization:
} Tor does not provide
\emph{protocol
439 normalization
} like Privoxy or the Anonymizer. For complex and variable
440 protocols such as HTTP, Tor must be layered with a filtering proxy such
441 as Privoxy to hide differences between clients, and expunge protocol
442 features that leak identity. Similarly, Tor does not currently integrate
443 tunneling for non-stream-based protocols like UDP; this too must be
444 provided by an external service.
445 % Actually, tunneling udp over tcp is probably horrible for some apps.
446 % Should this get its own non-goal bulletpoint? The motivation for
447 % non-goal-ness would be burden on clients / portability. -RD
448 % No, leave it as is. -RD
450 \textbf{Not steganographic:
} Tor does not try to conceal which users are
451 sending or receiving communications; it only tries to conceal with whom
454 \SubSection{Threat Model
}
455 \label{subsec:threat-model
}
457 A global passive adversary is the most commonly assumed threat when
458 analyzing theoretical anonymity designs. But like all practical
459 low-latency systems, Tor does not protect against such a strong
460 adversary. Instead, we assume an adversary who can observe some fraction
461 of network traffic; who can generate, modify, delete, or delay traffic
462 on the network; who can operate onion routers of its own; and who can
463 compromise some fraction of the onion routers on the network.
465 In low-latency anonymity systems that use layered encryption, the
466 adversary's typical goal is to observe both the initiator and the
467 receiver. Passive attackers can confirm a suspicion that Alice is
468 talking to Bob if the timing and volume patterns of the traffic on the
469 connection are distinct enough; active attackers can induce timing
470 signatures on the traffic to
\emph{force
} distinct patterns. Tor provides
471 some defenses against these
\emph{traffic confirmation
} attacks, for
472 example by encouraging users to run their own onion routers, but it does
473 not provide complete protection. Rather, we aim to prevent
\emph{traffic
474 analysis
} attacks, where the adversary uses traffic patterns to learn
475 which points in the network he should attack.
477 Our adversary might try to link an initiator Alice with any of her
478 communication partners, or he might try to build a profile of Alice's
479 behavior. He might mount passive attacks by observing the edges of the
480 network and correlating traffic entering and leaving the network---either
481 by relationships in packet timing; relationships in the volume
482 of data sent; or relationships in any externally visible user-selected
483 options. The adversary can also mount active attacks by compromising
484 routers or keys; by replaying traffic; by selectively denying service
485 to trustworthy routers to encourage users to send their traffic through
486 compromised routers, or denying service to users to see if the traffic
488 network stops; or by introducing patterns into traffic that can later be
489 detected. The adversary might attack the directory servers to give users
490 differing views of network state. Additionally, he can try to decrease
491 the network's reliability by attacking nodes or by performing antisocial
492 activities from reliable servers and trying to get them taken down;
493 making the network unreliable flushes users to other less anonymous
494 systems, where they may be easier to attack.
496 We consider each of these attacks in more detail below, and summarize
497 in Section~
\ref{sec:attacks
} how well the Tor design defends against
500 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
502 \Section{The Tor Design
}
505 The Tor network is an overlay network; each node is called an onion router
506 (OR). Onion routers run as normal user-level processes without needing
508 privileges. Currently, each OR maintains a long-term TLS
\cite{TLS
}
509 connection to every other
510 OR. (We examine some ways to relax this clique-topology assumption in
511 Section~
\ref{subsec:restricted-routes
}.) A subset of the ORs also act as
512 directory servers, tracking which routers are in the network;
513 see Section~
\ref{subsec:dirservers
} for directory server details.
515 runs local software called an onion proxy (OP) to fetch directories,
516 establish paths (called
\emph{virtual circuits
}) across the network,
517 and handle connections from user applications. These onion proxies accept
518 TCP streams and multiplex them across the virtual circuit. The onion
519 router on the other side
520 % I don't mean other side, I mean wherever it is on the circuit. But
521 % don't want to introduce complexity this early? Hm. -RD
522 of the circuit connects to the destinations of
523 the TCP streams and relays data.
525 Each onion router uses three public keys: a long-term identity key, a
526 short-term onion key, and a short-term link key. The identity
527 (signing) key is used to sign TLS certificates, to sign its router
528 descriptor (a summary of its keys, address, bandwidth, exit policy,
529 etc), and to sign directories if it is a directory server. Changing
530 the identity key of a router is considered equivalent to creating a
531 new router. The onion (decryption) key is used for decrypting requests
532 from users to set up a circuit and negotiate ephemeral keys. Finally,
533 link keys are used by the TLS protocol when communicating between
534 onion routers. Both short-term keys are rotated periodically and
535 independantly, to limit the impact of compromised keys.
537 Section~
\ref{subsec:cells
} discusses the structure of the fixed-size
538 \emph{cells
} that are the unit of communication in Tor. We describe
539 in Section~
\ref{subsec:circuits
} how virtual circuits are
540 built, extended, truncated, and destroyed. Section~
\ref{subsec:tcp
}
541 describes how TCP streams are routed through the network, and finally
542 Section~
\ref{subsec:congestion
} talks about congestion control and
548 ORs communicate with one another, and with users' OPs, via TLS
549 connections with ephemeral keys. This prevents an attacker from
550 impersonating an OR, conceals the contents of the connection with
551 perfect forward secrecy, and prevents an attacker from modifying data
554 Traffic passes along these connections in fixed-size cells. Each cell
555 is
256 bytes (but see Section~
\ref{sec:conclusion
} for a discussion of
556 allowing large cells and small cells on the same network), and
557 consists of a header and a payload. The header includes a circuit
558 identifier (circID) that specifies which circuit the cell refers to
559 (many circuits are be multiplexed over the single TLS connection), and
560 a command to describe what to do with the cell's payload. (Circuit
561 identifiers are connection-specific; a single circuit has a different
562 circID on each connection it uses.)
563 % XXX Say that each OR can have many circuits with same circID, so
564 % XXX long as they're on different connections, and that ORs know
565 % XXX which circIDs/connection pairs are linked by a circuit.
566 Based on their command, cells are either
\emph{control
} cells, which are
567 always interpreted by the node that receives them, or
\emph{relay
} cells,
568 which carry end-to-end stream data. The controls cells commands are:
569 \emph{padding
} (currently used for keepalive, but also usable for link
570 padding);
\emph{create
} or
\emph{created
} (used to set up a new circuit);
571 and
\emph{destroy
} (to tear down a circuit).
573 Relay cells have an additional header (the relay header) after the
574 cell header, containing the stream identifier (many streams can
575 be multiplexed over a circuit); an end-to-end checksum for integrity
576 checking; the length of the relay payload; and a relay command.
577 % XXX Mention _here_ that relay headers are {en|de}crypted as they
578 % XXX progress along the circuit.
580 relay commands are:
\emph{relay
581 data
} (for data flowing down the stream),
\emph{relay begin
} (to open a
582 stream),
\emph{relay end
} (to close a stream cleanly),
\emph{relay
583 teardown
} (to close a broken stream),
\emph{relay connected
}
584 (to notify the OP that a relay begin has succeeded),
\emph{relay
585 extend
} and
\emph{relay extended
} (to extend the circuit by a hop,
586 and to acknowledge),
\emph{relay truncate
} and
\emph{relay truncated
}
587 (to tear down only part of the circuit, and to acknowledge),
\emph{relay
588 sendme
} (used for congestion control), and
\emph{relay drop
} (used to
589 implement long-range dummies).
591 We describe each of these cell types and commands in more detail below.
593 \SubSection{Circuits and streams
}
594 \label{subsec:circuits
}
596 % I think when we say ``the user,'' maybe we should say ``the user's OP.''
598 The original Onion Routing design built one circuit for each
599 TCP stream. Because building a circuit can take several tenths of a
600 second (due to public-key cryptography delays and network latency),
601 this design imposed high costs on applications like web browsing that
602 open many TCP streams.
604 In Tor, each circuit can be shared by many TCP streams. To avoid
605 delays, users construct circuits preemptively. To limit linkability
606 among their streams, users' OPs build a new circuit
607 periodically if the previous one has been used,
608 and expire old used circuits that no longer have any open streams.
609 OPs consider making a new circuit once a minute: thus
610 even heavy users spend a negligible amount of time and CPU in
611 building circuits, but only a limited number of requests can be linked
612 to each other through a given exit node. Also, because circuits are built
613 in the background, OPs can recover from failed circuit creation
614 without delaying streams and thereby harming user experience.
616 \subsubsection{Constructing a circuit
}
617 \label{subsubsec:constructing-a-circuit
}
619 %XXXX Discuss what happens with circIDs here.
621 Users construct a circuit incrementally, negotiating a symmetric key with
622 each OR on the circuit, one hop at a time. To begin creating a new
624 (call her Alice) sends a
\emph{create
} cell to the first node in her
625 chosen path. This cell's payload contains the first half of the
626 Diffie-Hellman handshake ($g^x$), encrypted to the onion key of the OR (call
627 him Bob). Bob responds with a
\emph{created
} cell containing the second
628 half of the DH handshake, along with a hash of the negotiated key
631 Once the circuit has been established, Alice and Bob can send one
632 another relay cells encrypted with the negotiated
633 key.
\footnote{Actually, the negotiated key is used to derive two
634 symmetric keys: one for each direction.
} More detail is given in
637 To extend the circuit further, Alice sends a
\emph{relay extend
} cell
638 to Bob, specifying the address of the next OR (call her Carol), and
639 an encrypted $g^
{x_2
}$ for her. Bob copies the half-handshake into a
640 \emph{create
} cell, and passes it to Carol to extend the circuit.
641 When Carol responds with a
\emph{created
} cell, Bob wraps the payload
642 into a
\emph{relay extended
} cell and passes it back to Alice. Now
643 the circuit is extended to Carol, and Alice and Carol share a common key
646 In order to extend the circuit to a third node or beyond, Alice
647 proceeds as above, always telling the last node in the circuit to
648 extend one hop further.
649 % XXX Briefly mention path selection.
651 This circuit-level handshake protocol achieves unilateral entity
652 authentication (Alice knows she's handshaking with Bob/Carol, but
653 Bob/Carol doesn't care who is opening the circuit---Alice has no key
654 and is trying to remain anonymous) and unilateral key authentication
655 (Alice and Bob/Carol agree on a key, and Alice knows Bob/Carol is the
656 only other person who should know it). It also achieves forward
657 secrecy and key freshness. Formally, the protocol is as follows
658 (Where $E_
{PK_
{Bob
}}(
\cdot)$ is encryption with Bob's public key,
659 $H$ is a secure hash function, and $|$ is concatenation.)
663 \mathrm{Alice
} \rightarrow \mathrm{Bob
}&: E_
{PK_
{Bob
}}(g^x) \\
664 \mathrm{Bob
} \rightarrow \mathrm{Alice
}&: g^y, H(K |
\mathrm{``handshake"
}) \\
668 In the second step, Bob proves that it was he who who received $g^x$,
669 and who came up with $y$. We use PK encryption in the first step
670 (rather than, say, using the first two steps of STS, which has a
671 signature in the second step) because a single cell is too small to
672 hold both a public key and a signature. Preliminary analysis with the
673 NRL protocol analyzer
\cite{meadows96
} shows the above protocol to be
674 secure (including providing PFS) under the traditional Dolev-Yao
677 \subsubsection{Relay cells
}
678 Once Alice has established the circuit (so she shares keys with each
679 OR on the circuit), she can send relay cells.
680 % XXX Describe _here_ what happens with relay cells that are not
681 % XXX targeted at a given node; how they're decrypted; how they're
682 % XXX encrypted. The easiest expository order should probably be: What ORs
683 % XXX Do With Unrecognized Streams; What Alice Does To Build Relay
684 % XXX Cells; What ORs Do With Streams They Recognize.
685 Recall that every relay header has a stream ID in the relay header
687 which stream the cell belongs.
688 This stream ID allows a relay cell to be addressed to any of the ORs
690 construct a relay cell addressed to a given OR, Alice iteratively
691 encrypts the cell payload (that is, the relay header and payload)
692 with the symmetric key of each hop up to that OR. Then, at each hop
693 down the circuit, the OR decrypts the cell payload and checks whether
694 it recognizes the stream ID. A stream ID is recognized either if it
695 is an already open stream at that OR, or if it is equal to zero. The
696 zero stream ID is treated specially, and is used for control messages,
697 e.g. starting a new stream. If the stream ID is unrecognized, the OR
698 passes the relay cell downstream. This
\emph{leaky pipe
} circuit topology
699 allows Alice's streams to exit at different ORs on a single circuit.
700 Alice may choose different exit points because of their exit policies,
701 or to keep the ORs from knowing that two streams
702 originate at the same person.
704 To tear down a whole circuit, Alice sends a
\emph{destroy
} control
706 in the circuit receives the
\emph{destroy
} cell, closes all open streams on
707 that circuit, and passes a new
\emph{destroy
} cell forward. But since circuits
708 can be built incrementally, they can also be torn down incrementally:
709 Alice can instead send a relay truncate cell to a node along the circuit. That
710 node will send a
\emph{destroy
} cell forward, and reply with an acknowledgment
711 (a
\emph{relay truncated
} cell). Alice might truncate her circuit so
713 to different nodes without signaling to the first few nodes (or somebody
714 observing them) that she is changing her circuit. That is, nodes in the
715 middle of a truncated are not even aware when the circuit is
716 truncated, because they see only the encrypted relay cells.
717 Similarly, if a node on the circuit goes down,
718 the adjacent node can send a
\emph{relay truncated
} cell back to
720 ``break a node and see which circuits go down'' attack is weakened.
722 \SubSection{Opening and closing streams
}
725 When Alice's application wants to open a TCP connection to a given
726 address and port, it asks the OP (via SOCKS) to make the connection. The
727 OP chooses the newest open circuit (or creates one if none is available),
728 chooses a suitable OR on that circuit to be the exit node (usually the
729 last node, but maybe others due to exit policy conflicts; see
730 Section~
\ref{sec:exit-policies
}), chooses a new random stream ID for
732 and delivers a relay begin cell to that exit node. It uses a stream ID
733 of zero for the begin cell (so the OR will recognize it), and the relay
734 payload lists the new stream ID and the destination address and port.
735 Once the exit node completes the connection to the remote host, it
736 responds with a relay connected cell through the circuit. Upon receipt,
737 the OP notifies the application that it can begin talking.
739 There's a catch to using SOCKS, though -- some applications hand the
740 alphanumeric address to the proxy, while others resolve it into an IP
741 address first and then hand the IP to the proxy. When the application
742 does the DNS resolution first, Alice broadcasts her destination. Common
743 applications like Mozilla and ssh have this flaw.
745 In the case of Mozilla, we're fine: the filtering web proxy called Privoxy
746 does the SOCKS call safely, and Mozilla talks to Privoxy safely. But a
747 portable general solution, such as for ssh, is an open problem. We can
748 modify the local nameserver, but this approach is invasive, brittle, and
749 not portable. We can encourage the resolver library to do resolution
750 via TCP rather than UDP, but this approach is hard to do right, and also
751 has portability problems. We can provide a tool similar to
\emph{dig
} that
752 can do a private lookup through the Tor network. Our current answer is to
753 encourage the use of privacy-aware proxies like Privoxy wherever possible,
755 Ending a Tor stream is analogous to ending a TCP stream: it uses a
756 two-step handshake for normal operation, or a one-step handshake for
757 errors. If one side of the stream closes abnormally, that node simply
758 sends a relay teardown cell, and tears down the stream. If one side
759 of the stream closes the connection normally, that node sends a relay
760 end cell down the circuit. When the other side has sent back its own
761 relay end, the stream can be torn down. This two-step handshake allows
762 for TCP-based applications that, for example, close a socket for writing
763 but are still willing to read. Remember that all relay cells use layered
764 encryption, so only the destination OR knows what type of relay cell
767 \SubSection{Integrity checking on streams
}
769 Because the old Onion Routing design used a stream cipher, traffic was
770 vulnerable to a malleability attack: even though the attacker could not
771 decrypt cells, he could make changes to an encrypted
772 cell to create corresponding changes to the data leaving the network.
773 (Even an external adversary could do this, despite link encryption!)
775 This weakness allowed an adversary to change a padding cell to a destroy
776 cell; change the destination address in a relay begin cell to the
777 adversary's webserver; or change a user on an ftp connection from
778 typing ``dir'' to typing ``delete~*''. Any node or external adversary
779 along the circuit could introduce such corruption in a stream.
781 Tor prevents external adversaries from mounting this attack simply by
782 using TLS. Addressing the insider malleability attack, however, is
785 We could do integrity checking of the relay cells at each hop, either
786 by including hashes or by using a cipher mode like EAX
\cite{eax
},
787 but we don't want the added message-expansion overhead at each hop, and
788 we don't want to leak the path length or pad to some max path length.
789 Because we've already accepted that our design is vulnerable to end-to-end
790 timing attacks, we can perform integrity checking only at the edges of
791 the circuit without introducing any new anonymity attacks. When Alice
793 with each hop, they both start a SHA-
1 with some derivative of that key,
794 % Not just the exit hop, but each hop: any hop can be an exit node. -RD
795 thus starting out with randomness that only the two of them know. From
796 then on they each incrementally add to the SHA-
1 all the data bytes
797 entering or exiting from the circuit, and each such relay cell includes
798 the first
4 bytes of the current value of the hash.
800 The attacker must be able to guess all previous bytes between Alice
801 and Bob on that circuit (including the pseudorandomness from the key
802 negotiation), plus the bytes in the current cell, to remove or modify the
803 cell. Attacks on SHA-
1 where the adversary can incrementally add to a
804 hash to produce a new valid hash don't work,
805 because all hashes are end-to-end encrypted across the circuit.
806 The computational overhead isn't so bad, compared to doing an AES
807 crypt at each hop in the circuit. We use only four bytes per cell to
808 minimize overhead; the chance that an adversary will correctly guess a
809 valid hash, plus the payload the current cell, is acceptly low, given
810 that Alice or Bob tear down the circuit if they receive a bad hash.
812 \SubSection{Rate limiting and fairness
}
814 Volunteers are generally more willing to run services that can limit
815 their bandwidth usage. To accomodate them, Tor servers use a token
816 bucket approach to limit the number of bytes they
817 % XXX cite token bucket?
818 receive. Tokens are added to the bucket each second (when the bucket is
819 full, new tokens are discarded.) Each token represents permission to
820 receive one byte from the network---to receive a byte, the connection
821 must remove a token from the bucket. Thus if the bucket is empty, that
822 connection must wait until more tokens arrive. The number of tokens we
823 add enforces a long-term average rate of incoming bytes, while still
824 permitting short-term bursts above the allowed bandwidth. Current bucket
825 sizes are set to ten seconds worth of traffic.
827 Further, we want to avoid starving any Tor streams. Entire circuits
828 could starve if we read greedily from connections and one connection
829 uses all the remaining bandwidth. We solve this by dividing the number
830 of tokens in the bucket by the number of connections that want to read,
831 and reading at most that number of bytes from each connection. We iterate
832 this procedure until the number of tokens in the bucket is under some
833 threshold (eg
10KB), at which point we greedily read from connections.
835 Because the Tor protocol generates roughly the same number of outgoing
836 bytes as incoming bytes, it is sufficient in practice to rate-limit
838 % Is it? Fun attack: I send you lots of 1-byte-at-a-time TCP frames.
839 % In response, you send lots of 256 byte cells. Can I use this to
840 % make you exceed your outgoing bandwidth limit by a factor of 256? -NM
841 % Can we resolve this by, when reading from edge connections, rounding up
842 % the bytes read (wrt buckets) to the nearest multiple of 256? -RD
844 Further, inspired by Rennhard et al's design in
\cite{anonnet
}, a
845 circuit's edges heuristically distinguish interactive streams from bulk
846 streams by comparing the frequency with which they supply cells. We can
847 provide good latency for interactive streams by giving them preferential
848 service, while still getting good overall throughput to the bulk
849 streams. Such preferential treatment presents a possible end-to-end
850 attack, but an adversary who can observe both
851 ends of the stream can already learn this information through timing
854 \SubSection{Congestion control
}
855 \label{subsec:congestion
}
857 Even with bandwidth rate limiting, we still need to worry about
858 congestion, either accidental or intentional. If enough users choose the
859 same OR-to-OR connection for their circuits, that connection can become
860 saturated. For example, an adversary could make a large HTTP PUT request
861 through the onion routing network to a webserver he runs, and then
862 refuse to read any of the bytes at the webserver end of the
863 circuit. Without some congestion control mechanism, these bottlenecks
864 can propagate back through the entire network. We describe our
867 \subsubsection{Circuit-level
}
869 To control a circuit's bandwidth usage, each OR keeps track of two
870 windows. The
\emph{package window
} tracks how many relay data cells the OR is
871 allowed to package (from outside streams) for transmission back to the OP,
872 and the
\emph{deliver window
} tracks how many relay data cells it is willing
873 to deliver to streams outside the network. Each window is initialized
874 (say, to
1000 data cells). When a data cell is packaged or delivered,
875 the appropriate window is decremented. When an OR has received enough
876 data cells (currently
100), it sends a relay sendme cell towards the OP,
877 with stream ID zero. When an OR receives a relay sendme cell with stream
878 ID zero, it increments its packaging window. Either of these cells
879 increments the corresponding window by
100. If the packaging window
880 reaches
0, the OR stops reading from TCP connections for all streams
881 on the corresponding circuit, and sends no more relay data cells until
882 receiving a relay sendme cell.
884 The OP behaves identically, except that it must track a packaging window
885 and a delivery window for every OR in the circuit. If a packaging window
886 reaches
0, it stops reading from streams destined for that OR.
888 \subsubsection{Stream-level
}
890 The stream-level congestion control mechanism is similar to the
891 circuit-level mechanism above. ORs and OPs use relay sendme cells
892 to implement end-to-end flow control for individual streams across
893 circuits. Each stream begins with a package window (e.g.
500 cells),
894 and increments the window by a fixed value (
50) upon receiving a relay
895 sendme cell. Rather than always returning a relay sendme cell as soon
896 as enough cells have arrived, the stream-level congestion control also
897 has to check whether data has been successfully flushed onto the TCP
898 stream; it sends a relay sendme only when the number of bytes pending
899 to be flushed is under some threshold (currently
10 cells worth).
901 Currently, non-data relay cells do not affect the windows. Thus we
902 avoid potential deadlock issues, e.g. because a stream can't send a
903 relay sendme cell because its packaging window is empty.
906 \subsubsection{Needs more research
}
908 We don't need to reimplement full TCP windows (with sequence numbers,
909 the ability to drop cells when we're full and retransmit later, etc),
910 because the TCP streams already guarantee in-order delivery of each
911 cell. But we need to investigate further the effects of the current
912 parameters on throughput and latency, while also keeping privacy in mind;
913 see Section~
\ref{sec:maintaining-anonymity
} for more discussion.
915 \Section{Other design decisions
}
917 \SubSection{Resource management and denial-of-service
}
920 Providing Tor as a public service provides many opportunities for an
921 attacker to mount denial-of-service attacks against the network. While
922 flow control and rate limiting (discussed in
923 Section~
\ref{subsec:congestion
}) prevent users from consuming more
924 bandwidth than routers are willing to provide, opportunities remain for
926 consume more network resources than their fair share, or to render the
927 network unusable for other users.
929 First of all, there are several CPU-consuming denial-of-service
930 attacks wherein an attacker can force an OR to perform expensive
931 cryptographic operations. For example, an attacker who sends a
932 \emph{create
} cell full of junk bytes can force an OR to perform an RSA
933 decrypt. Similarly, an attacker can
934 fake the start of a TLS handshake, forcing the OR to carry out its
935 (comparatively expensive) half of the handshake at no real computational
936 cost to the attacker.
938 Several approaches exist to address these attacks. First, ORs may
939 require clients to solve a puzzle
\cite{puzzles-tls
} while beginning new
940 TLS handshakes or accepting
\emph{create
} cells. So long as these
941 tokens are easy to verify and computationally expensive to produce, this
942 approach limits the attack multiplier. Additionally, ORs may limit
943 the rate at which they accept create cells and TLS connections, so that
944 the computational work of processing them does not drown out the (comparatively
945 inexpensive) work of symmetric cryptography needed to keep cells
946 flowing. This rate limiting could, however, allow an attacker
947 to slow down other users when they build new circuits.
949 % What about link-to-link rate limiting?
951 Attackers also have an opportunity to attack the Tor network by mounting
952 attacks on its hosts and network links. Disrupting a single circuit or
953 link breaks all currently open streams passing along that part of the
954 circuit. Indeed, this same loss of service occurs when a router crashes
955 or its operator restarts it. The current Tor design treats such attacks
956 as intermittent network failures, and depends on users and applications
957 to respond or recover as appropriate. A future design could use an
958 end-to-end TCP-like acknowledgment protocol, so that no streams are
959 lost unless the entry or exit point itself is disrupted. This solution
960 would require more buffering at the network edges, however, and the
961 performance and anonymity implications from this extra complexity still
962 require investigation.
964 \SubSection{Exit policies and abuse
}
965 \label{subsec:exitpolicies
}
967 Exit abuse is a serious barrier to wide-scale Tor deployment. Anonymity
968 presents would-be vandals and abusers with an opportunity to hide
969 the origins of their activities. Attackers can harm the Tor network by
970 implicating exit servers for their abuse. Also, applications that commonly
971 use IP-based authentication (such as institutional mail or web servers)
972 can be fooled by the fact that anonymous connections appear to originate
975 We stress that Tor does not enable any new class of abuse. Spammers
976 and other attackers already have access to thousands of misconfigured
977 systems worldwide, and the Tor network is far from the easiest way
978 to launch these antisocial or illegal attacks.
979 %Indeed, because of its limited
980 %anonymity, Tor is probably not a good way to commit crimes.
982 onion routers can easily be mistaken for the originators of the abuse,
983 and the volunteers who run them may not want to deal with the hassle of
984 repeatedly explaining anonymity networks, we must block or limit attacks
985 and other abuse that travel through the Tor network.
987 To mitigate abuse issues, in Tor, each onion router's
\emph{exit policy
}
988 describes to which external addresses and ports the router will permit
989 stream connections. On one end of the spectrum are
\emph{open exit
}
990 nodes that will connect anywhere. On the other end are
\emph{middleman
}
991 nodes that only relay traffic to other Tor nodes, and
\emph{private exit
}
992 nodes that only connect to a local host or network. Using a private
993 exit (if one exists) is a more secure way for a client to connect to a
994 given host or network---an external adversary cannot eavesdrop traffic
995 between the private exit and the final destination, and so is less sure of
996 Alice's destination and activities. Most onion routers will function as
997 \emph{restricted exits
} that permit connections to the world at large,
998 but prevent access to certain abuse-prone addresses and services. In
999 general, nodes can require a variety of forms of traffic authentication
1002 %The abuse issues on closed (e.g. military) networks are different
1003 %from the abuse on open networks like the Internet. While these IP-based
1004 %access controls are still commonplace on the Internet, on closed networks,
1005 %nearly all participants will be honest, and end-to-end authentication
1006 %can be assumed for important traffic.
1008 Many administrators will use port restrictions to support only a
1009 limited set of well-known services, such as HTTP, SSH, or AIM.
1010 This is not a complete solution, since abuse opportunities for these
1011 protocols are still well known. Nonetheless, the benefits are real,
1012 since administrators seem used to the concept of port
80 abuse not
1013 coming from the machine's owner.
1015 A further solution may be to use proxies to clean traffic for certain
1016 protocols as it leaves the network. For example, much abusive HTTP
1017 behavior (such as exploiting buffer overflows or well-known script
1018 vulnerabilities) can be detected in a straightforward manner.
1019 Similarly, one could run automatic spam filtering software (such as
1020 SpamAssassin) on email exiting the OR network.
1022 ORs may also choose to rewrite exiting traffic in order to append
1023 headers or other information to indicate that the traffic has passed
1024 through an anonymity service. This approach is commonly used
1025 by email-only anonymity systems. When possible, ORs can also
1026 run on servers with hostnames such as
{\it anonymous
}, to further
1027 alert abuse targets to the nature of the anonymous traffic.
1029 A mixture of open and restricted exit nodes will allow the most
1030 flexibility for volunteers running servers. But while many
1031 middleman nodes help provide a large and robust network,
1032 having only a few exit nodes reduces the number of points
1033 an adversary needs to monitor for traffic analysis, and places a
1034 greater burden on the exit nodes. This tension can be seen in the
1036 cascade model, wherein only one node in each cascade needs to handle
1037 abuse complaints---but an adversary only needs to observe the entry
1038 and exit of a cascade to perform traffic analysis on all that
1039 cascade's users. The Hydra model (many entries, few exits) presents a
1040 different compromise: only a few exit nodes are needed, but an
1041 adversary needs to work harder to watch all the clients; see
1042 Section~
\ref{sec:conclusion
}.
1044 Finally, we note that exit abuse must not be dismissed as a peripheral
1045 issue: when a system's public image suffers, it can reduce the number
1046 and diversity of that system's users, and thereby reduce the anonymity
1047 of the system itself. Like usability, public perception is also a
1048 security parameter. Sadly, preventing abuse of open exit nodes is an
1049 unsolved problem, and will probably remain an arms race for the
1050 forseeable future. The abuse problems faced by Princeton's CoDeeN
1051 project
\cite{darkside
} give us a glimpse of likely issues.
1053 \SubSection{Directory Servers
}
1054 \label{subsec:dirservers
}
1056 First-generation Onion Routing designs
\cite{freedom2-arch,or-jsac98
} used
1057 in-band network status updates: each router flooded a signed statement
1058 to its neighbors, which propagated it onward. But anonymizing networks
1059 have different security goals than typical link-state routing protocols.
1060 For example, delays (accidental or intentional)
1061 that can cause different parts of the network to have different pictures
1062 of link-state and topology are not only inconvenient---they give
1063 attackers an opportunity to exploit differences in client knowledge.
1064 We also worry about attacks to deceive a
1065 client about the router membership list, topology, or current network
1066 state. Such
\emph{partitioning attacks
} on client knowledge help an
1067 adversary to efficiently deploy resources
1068 when attacking a target.
1070 Tor uses a small group of redundant, well-known onion routers to
1071 track changes in network topology and node state, including keys and
1072 exit policies. Each such
\emph{directory server
} also acts as an HTTP
1073 server, so participants can fetch current network state and router
1074 lists (a
\emph{directory
}), and so other onion routers can upload
1075 their router descriptors. Onion routers periodically publish signed
1076 statements of their state to each directory server, which combines this
1077 state information with its own view of network liveness, and generates
1078 a signed description of the entire network state. Client software is
1079 pre-loaded with a list of the directory servers and their keys; it uses
1080 this information to bootstrap each client's view of the network.
1082 When a directory server receives a signed statement from an onion
1083 router, it recognizes the onion router by its identity key. Directory
1084 servers do not automatically advertise unrecognized ORs. (If they did,
1085 an adversary could take over the network by creating many servers
1086 \cite{sybil
}.) Instead, new nodes must be approved by the directory
1087 server administrator before they are included. Mechanisms for automated
1088 node approval are an area of active research, and are discussed more
1089 in Section~
\ref{sec:maintaining-anonymity
}.
1091 Of course, a variety of attacks remain. An adversary who controls
1092 a directory server can track certain clients by providing different
1093 information---perhaps by listing only nodes under its control, or by
1094 informing only certain clients about a given node. Even an external
1095 adversary can exploit differences in client knowledge: clients who use
1096 a node listed on one directory server but not the others are vulnerable.
1098 Thus these directory servers must be synchronized and redundant.
1099 Valid directories are those signed by a threshold of the directory
1102 The directory servers in Tor are modeled after those in Mixminion
1103 \cite{minion-design
}, but our situation is easier. First, we make the
1104 simplifying assumption that all participants agree on the set of
1105 directory servers. Second, while Mixminion needs to predict node
1106 behavior, Tor only needs a threshold consensus of the current
1107 state of the network.
1109 Tor directory servers build a consensus directory through a simple
1110 four-round broadcast protocol. In round one, each server dates and
1111 signs its current opinion, and broadcasts it to the other directory
1112 servers; then in round two, each server rebroadcasts all the signed
1113 opinions it has received. At this point all directory servers check
1114 to see whether any server has signed multiple opinions in the same
1115 period. Such a server is either broken or cheating, so the protocol
1116 stops and notifies the administrators, who either remove the cheater
1117 or wait for the broken server to be fixed. If there are no
1118 discrepancies, each directory server then locally computes an algorithm
1120 on the set of opinions, resulting in a uniform shared directory. In
1121 round three servers sign this directory and broadcast it; and finally
1122 in round four the servers rebroadcast the directory and all the
1123 signatures. If any directory server drops out of the network, its
1124 signature is not included on the final directory.
1126 The rebroadcast steps ensure that a directory server is heard by
1127 either all of the other servers or none of them, even when some links
1128 are down (assuming that any two directory servers can talk directly or
1129 via a third). Broadcasts are feasible because there are relatively few
1130 directory servers (currently
3, but we expect as many as
9 as the network
1131 scales). Computing the shared directory locally is a straightforward
1132 threshold voting process: we include an OR if a majority of directory
1133 servers believe it to be good.
1135 To avoid attacks where a router connects to all the directory servers
1136 but refuses to relay traffic from other routers, the directory servers
1137 must build circuits and use them to anonymously test router reliability
1140 Using directory servers is simpler and more flexible than flooding.
1141 For example, flooding complicates the analysis when we
1142 start experimenting with non-clique network topologies. And because
1143 the directories are signed, they can be cached by other onion routers.
1144 Thus directory servers are not a performance
1145 bottleneck when we have many users, and do not aid traffic analysis by
1146 forcing clients to periodically announce their existence to any
1149 \Section{Rendezvous points and location privacy
}
1150 \label{sec:rendezvous
}
1152 Rendezvous points are a building block for
\emph{location-hidden
1153 services
} (also known as
\emph{responder anonymity
}) in the Tor
1154 network. Location-hidden services allow Bob to offer a TCP
1155 service, such as a webserver, without revealing its IP.
1156 This type of anonymity protects against distributed DoS attacks:
1157 attackers are forced to attack the onion routing network as a whole
1158 rather than just Bob's IP.
1160 Our design for location-hidden servers has the following goals.
1161 \textbf{Flood-proof:
} Bob needs a way to filter incoming requests,
1162 so an attacker cannot flood Bob simply by sending many requests.
1163 \textbf{Robust:
} Bob should be able to maintain a long-term pseudonymous
1164 identity even in the presence of router failure. Bob's service must
1165 not be tied to a single OR, and Bob must be able to tie his service
1166 to new ORs.
\textbf{Smear-resistant:
} if a social attacker offers a
1167 location-hidden service that is illegal or disreputable, it should not
1168 appear---even to a casual observer---that a rendezvous router is hosting
1169 that service.
\textbf{Application-transparent:
} Although we require users
1170 to run special software to access location-hidden servers, we must not
1171 require them to modify their applications.
1173 We provide location-hiding for Bob by allowing him to advertise
1174 several onion routers (his
\emph{introduction points
}) as contact
1175 points. He may do this on any robust efficient
1176 key-value lookup system with authenticated updates, such as a
1177 distributed hash table (DHT) like CFS
\cite{cfs:sosp01
}\footnote{
1178 Rather than rely on an external infrastructure, the Onion Routing network
1179 can run the DHT; to begin, we can run a simple lookup system on the
1180 directory servers.
} Alice, the client, chooses an OR as her
1181 \emph{rendezvous point
}. She connects to one of Bob's introduction
1182 points, informs him about her rendezvous point, and then waits for him
1183 to connect to the rendezvous point. This extra level of indirection
1184 helps Bob's introduction points avoid problems associated with serving
1185 unpopular files directly (for example, if Bob chooses
1186 an introduction point in Texas to serve anti-ranching propaganda,
1187 or if Bob's service tends to get attacked by network vandals).
1188 The extra level of indirection also allows Bob to respond to some requests
1191 We give an overview of the steps of a rendezvous. These steps are
1192 performed on behalf of Alice and Bob by their local onion proxies;
1193 application integration is described more fully below.
1195 \item Bob chooses some introduction points, and advertises them on
1197 \item Bob establishes a Tor circuit to each of his introduction points,
1199 \item Alice learns about Bob's service out of band (perhaps Bob told her,
1200 or she found it on a website). She retrieves the details of Bob's
1201 service from the DHT.
1202 \item Alice chooses an OR to serve as the rendezvous point (RP) for this
1203 transaction. She establishes a circuit to RP, and gives it a
1204 rendezvous cookie, which it will use to recognize Bob.
1205 \item Alice opens an anonymous stream to one of Bob's introduction
1206 points, and gives it a message (encrypted for Bob) which tells him
1207 about herself, her chosen RP and the rendezvous cookie, and the
1208 first half of an ephemeral
1209 key handshake. The introduction point sends the message to Bob.
1210 \item If Bob wants to talk to Alice, he builds a new circuit to Alice's
1211 RP and provides the rendezvous cookie and the second half of the DH
1212 handshake (along with a hash of the session key they now share).
1213 \item The RP connects Alice's circuit to Bob's. Note that RP can't
1214 recognize Alice, Bob, or the data they transmit.
1215 \item Alice now sends a
\emph{relay begin
} cell along the circuit. It
1216 arrives at Bob's onion proxy. Bob's onion proxy connects to Bob's
1218 \item An anonymous stream has been established, and Alice and Bob
1219 communicate as normal.
1222 When establishing an introduction point, Bob provides the onion router
1223 with a public ``introduction'' key. The hash of this public key
1224 identifies a unique service, and (since Bob is required to sign his
1225 messages) prevents anybody else from usurping Bob's introduction point
1226 in the future. Bob uses the same public key when establishing the other
1227 introduction points for that service. Bob periodically refreshes his
1230 The message that Alice gives
1231 the introduction point includes a hash of Bob's public key to identify
1232 the service, along with an optional initial authentication token (the
1233 introduction point can do prescreening, for example to block replays). Her
1234 message to Bob may include an end-to-end authentication token so Bob
1235 can choose whether to respond.
1236 The authentication tokens can be used to provide selective access:
1237 important users get tokens to ensure uninterrupted access to the
1238 service. During normal situations, Bob's service might simply be offered
1239 directly from mirrors, and Bob gives out tokens to high-priority users. If
1240 the mirrors are knocked down by distributed DoS attacks, those users
1241 can switch to accessing Bob's service via the Tor rendezvous system.
1243 \SubSection{Integration with user applications
}
1245 Bob configures his onion proxy to know the local IP and port of his
1246 service, a strategy for authorizing clients, and a public key. Bob
1247 publishes the public key, an expiration time (``not valid after''), and
1248 the current introduction points for his service into the DHT, all indexed
1249 by the hash of the public key. Note that Bob's webserver is unmodified,
1250 and doesn't even know that it's hidden behind the Tor network.
1252 Alice's applications also work unchanged---her client interface
1253 remains a SOCKS proxy. We encode all of the necessary information
1254 into the fully qualified domain name Alice uses when establishing her
1255 connection. Location-hidden services use a virtual top level domain
1256 called `.onion': thus hostnames take the form x.y.onion where x is the
1257 authentication cookie, and y encodes the hash of PK. Alice's onion proxy
1258 examines addresses; if they're destined for a hidden server, it decodes
1259 the PK and starts the rendezvous as described in the table above.
1261 \subsection{Previous rendezvous work
}
1263 Ian Goldberg developed a similar notion of rendezvous points for
1264 low-latency anonymity systems
\cite{ian-thesis
}. His design differs from
1265 ours in three ways. First, Goldberg suggests that Alice should manually
1266 hunt down a current location of the service via Gnutella; whereas our
1267 use of CFS makes lookup faster, more robust, and transparent to the
1268 user. Second, in Tor the client and server negotiate ephemeral keys
1269 via Diffie-Hellman, so plaintext is not exposed at any point. Third,
1270 our design tries to minimize the exposure associated with running the
1271 service, to encourage volunteers to offer introduction and rendezvous
1272 point services. Tor's introduction points do not output any bytes to the
1273 clients, and the rendezvous points don't know the client or the server,
1274 and can't read the data being transmitted. The indirection scheme is
1275 also designed to include authentication/authorization---if Alice doesn't
1276 include the right cookie with her request for service, Bob need not even
1277 acknowledge his existence.
1280 \label{sec:analysis
}
1282 In this section, we discuss how well Tor meets our stated design goals
1283 and its resistance to attacks.
1285 \SubSection{Meeting Basic Goals
}
1286 % None of these seem to say very much. Should this subsection be removed?
1288 \item [Basic Anonymity:
] Because traffic is encrypted, changing in
1289 appearance, and can flow from anywhere to anywhere within the
1290 network, a simple observer that cannot see both the initiator
1291 activity and the corresponding activity where the responder talks to
1292 the network will not be able to link the initiator and responder.
1293 Nor is it possible to directly correlate any two communication
1294 sessions as coming from a single source without additional
1295 information. Resistance to more sophisticated anonymity threats is
1297 \item[Deployability:
] Tor requires no specialized hardware. Tor
1298 requires no kernel modifications; it runs in user space (currently
1299 on Linux, various BSDs, and Windows). All of these imply a low
1300 technical barrier to running a Tor node. There is an assumption that
1301 Tor nodes have good relatively persistent net connectivity
1302 (currently
T1 or better);
1303 % Is that reasonable to say? We haven't really discussed it -P.S.
1304 % Roger thinks otherwise; he will fix this. -NM
1305 however, there is no padding overhead, and operators can limit
1306 bandwidth on any link. Tor is freely available under the modified
1307 BSD license, and operators are able to choose their own exit
1308 policies, thus reducing legal and social barriers to
1311 \item[Usability:
] As noted, Tor runs in user space. So does the onion
1312 proxy, which is comparatively easy to install and run. SOCKS-aware
1313 applications require nothing more than to be pointed at the onion
1314 proxy; other applications can be redirected to use SOCKS for their
1315 outgoing TCP connections by drop-in libraries such as tsocks.
1317 \item[Flexibility:
] Tor's design and implementation is fairly modular,
1318 so that, for example, a scalable P2P replacement for the directory
1319 servers would not substantially impact other aspects of the system.
1320 Tor runs on top of TCP, so design options that could not easily do
1321 so would be difficult to test on the current network. However, most
1322 low-latency protocols are designed to run over TCP. We are currently
1323 working with the designers of MorphMix to render our two systems
1324 interoperable. So for, this seems to be relatively straightforward.
1325 Interoperability will allow testing and direct comparison of the two
1326 rather different designs.
1328 \item[Simple design:
] Tor opts for practicality when there is no
1329 clear resolution of anonymity trade-offs or practical means to
1330 achieve resolution. Thus, we do not currently pad or mix; although
1331 it would be easy to add either of these. Indeed, our system allows
1332 long-range and variable padding if this should ever be shown to have
1333 a clear advantage. Similarly, we do not currently attempt to
1334 resolve such issues as Sybil attacks to dominate the network except
1335 by such direct means as personal familiarity of director operators
1336 with all node operators.
1339 \SubSection{Attacks and Defenses
}
1342 Below we summarize a variety of attacks, and discuss how well our
1343 design withstands them.
1345 \subsubsection*
{Passive attacks
}
1347 \item \emph{Observing user traffic patterns.
} Observations of connection
1348 between an end user and a first onion router will not reveal to whom
1349 the user is connecting or what information is being sent. It will
1350 reveal patterns of user traffic (both sent and received). Simple
1351 profiling of user connection patterns is not generally possible,
1352 however, because multiple application connections (streams) may be
1353 operating simultaneously or in series over a single circuit. Thus,
1354 further processing is necessary to try to discern even these usage
1357 \item \emph{Observing user content.
} At the user end, content is
1358 encrypted; however, connections from the network to arbitrary
1359 websites may not be. Further, a responding website may itself be
1360 considered an adversary. Filtering content is not a primary goal of
1361 Onion Routing; nonetheless, Tor can directly make use of Privoxy and
1362 related filtering services via SOCKS and thus anonymize their
1363 application data streams.
1365 \item \emph{Option distinguishability.
} Configuration options can be a
1366 source of distinguishable patterns. In general there is economic
1367 incentive to allow preferential services
\cite{econymics
}, and some
1368 degree of configuration choice can be a factor in attracting many users
1369 to provide anonymity. So far, however, we have
1370 not found a compelling use case in Tor for any client-configurable
1371 options. Thus, clients are currently distinguishable only by their
1373 %Actually, circuitrebuildperiod is such an option. -RD
1375 \item \emph{End-to-end Timing correlation.
} Tor only minimally hides
1376 end-to-end timing correlations. If an attacker can watch patterns of
1377 traffic at the initiator end and the responder end, then he will be
1378 able to confirm the correspondence with high probability. The
1379 greatest protection currently against such confirmation is if the
1380 connection between the onion proxy and the first Tor node is hidden,
1381 possibly because it is local or behind a firewall. This approach
1382 requires an observer to separate traffic originating the onion
1383 router from traffic passes through it. We still do not, however,
1384 predict this approach to be a large problem for an attacker who can
1385 observe traffic at both ends of an application connection.
1387 \item \emph{End-to-end Size correlation.
} Simple packet counting
1388 without timing consideration will also be effective in confirming
1389 endpoints of a connection through Onion Routing; although slightly
1390 less so. This is because, even without padding, the leaky pipe
1391 topology means different numbers of packets may enter one end of a
1392 circuit than exit at the other.
1394 \item \emph{Website fingerprinting.
} All the above passive
1395 attacks that are at all effective are traffic confirmation attacks.
1396 This puts them outside our general design goals. There is also
1397 a passive traffic analysis attack that is potentially effective.
1398 Instead of searching exit connections for timing and volume
1399 correlations it is possible to build up a database of
1400 ``fingerprints'' containing file sizes and access patterns for many
1401 interesting websites. If one now wants to
1402 monitor the activity of a user, it may be possible to confirm a
1403 connection to a site simply by consulting the database. This attack has
1404 been shown to be effective against SafeWeb
\cite{hintz-pet02
}. Onion
1405 Routing is not as vulnerable as SafeWeb to this attack: There is the
1406 possibility that multiple streams are exiting the circuit at
1407 different places concurrently. Also, fingerprinting will be limited to
1408 the granularity of cells, currently
256 bytes. Larger cell sizes
1409 and/or minimal padding schemes that group websites into large sets
1410 are possible responses. But this remains an open problem. Link
1411 padding or long-range dummies may also make fingerprints harder to
1413 such fingerprinting should not be confused with the latency attacks
1414 of
\cite{back01
}. Those require a fingerprint of the latencies of
1415 all circuits through the network, combined with those from the
1416 network edges to the targeted user and the responder website. While
1417 these are in principal feasible and surprises are always possible,
1418 these constitute a much more complicated attack, and there is no
1419 current evidence of their practicality.)
1421 \item \emph{Content analysis.
} Tor explicitly provides no content
1422 rewriting for any protocol at a higher level than TCP. When
1423 protocol cleaners are available, however (as Privoxy is for HTTP),
1424 Tor can integrate them in order to address these attacks.
1428 \subsubsection*
{Active attacks
}
1430 \item \emph{Key compromise.
} We consider the impact of a compromise
1431 for each type of key in turn, from the shortest- to the
1432 longest-lived. If a circuit session key is compromised, the
1433 attacker can unwrap a single layer of encryption from the relay
1434 cells traveling along that circuit. (Only nodes on the circuit can
1435 see these cells.) If a TLS session key is compromised, an attacker
1436 can view all the cells on TLS connection until the key is
1437 renegotiated. (These cells are themselves encrypted.) If a TLS
1438 private key is compromised, the attacker can fool others into
1439 thinking that he is the affected OR, but still cannot accept any
1440 connections. If an onion private key is compromised, the attacker
1441 can impersonate the OR in circuits, but only if the attacker has
1442 also compromised the OR's TLS private key, or is running the
1443 previous OR in the circuit. (This compromise affects newly created
1444 circuits, but because of perfect forward secrecy, the attacker
1445 cannot hijack old circuits without compromising their session keys.)
1446 In any case, an attacker can only take advantage of a compromise in
1447 these mid-term private keys until they expire. Only by
1448 compromising a node's identity key can an attacker replace that
1449 node indefinitely, by sending new forged mid-term keys to the
1450 directories. Finally, an attacker who can compromise a
1451 \emph{directory's
} identity key can influence every client's view
1452 of the network---but only to the degree made possible by gaining a
1453 vote with the rest of the the directory servers.
1455 \item \emph{Iterated compromise.
} A roving adversary who can
1456 compromise ORs (by system intrusion, legal coersion, or extralegal
1457 coersion) could march down length of a circuit compromising the
1458 nodes until he reaches the end. Unless the adversary can complete
1459 this attack within the lifetime of the circuit, however, the ORs
1460 will have discarded the necessary information before the attack can
1461 be completed. (Thanks to the perfect forward secrecy of session
1462 keys, the attacker cannot cannot force nodes to decrypt recorded
1463 traffic once the circuits have been closed.) Additionally, building
1464 circuits that cross jurisdictions can make legal coercion
1465 harder---this phenomenon is commonly called ``jurisdictional
1466 arbitrage.'' The Java Anon Proxy project recently experienced this
1468 the German government successfully ordered them to add a backdoor to
1469 all of their nodes
\cite{jap-backdoor
}.
1471 \item \emph{Run a recipient.
} By running a Web server, an adversary
1472 trivially learns the timing patterns of those connecting to it, and
1473 can introduce arbitrary patterns in its responses. This can greatly
1474 facilitate end-to-end attacks: If the adversary can induce certain
1475 users to connect to connect to his webserver (perhaps by providing
1476 content targeted at those users), she now holds one end of their
1477 connection. Additonally, here is a danger that the application
1478 protocols and associated programs can be induced to reveal
1479 information about the initiator. This is not directly in Onion
1480 Routing's protection area, so we are dependent on Privoxy and
1481 similar protocol cleaners to solve the problem.
1483 \item \emph{Run an onion proxy.
} It is expected that end users will
1484 nearly always run their own local onion proxy. However, in some
1485 settings, it may be necessary for the proxy to run
1486 remotely---typically, in an institutional setting where it was
1487 necessary to monitor the activity of those connecting to the proxy.
1488 The drawback, of course, is that if the onion proxy is compromised,
1489 then all future connections through it are completely compromised.
1491 \item \emph{DoS non-observed nodes.
} An observer who can observe some
1492 of the Tor network can increase the value of this traffic analysis
1493 if it can attack non-observed nodes to shut them down, reduce
1494 their reliability, or persuade users that they are not trustworthy.
1495 The best defense here is robustness.
1497 \item \emph{Run a hostile node.
} In addition to the abilties of a
1498 local observer, an isolated hostile node can create circuits through
1499 itself, or alter traffic patterns, in order to affect traffic at
1500 other nodes. Its ability to directly DoS a neighbor is now limited
1501 by bandwidth throttling. Nonetheless, in order to compromise the
1502 anonymity of the endpoints of a circuit by its observations, a
1503 hostile node is only significant if it is immediately adjacent to
1506 \item \emph{Run multiple hostile nodes.
} If an adversary is able to
1507 run multiple ORs, and is able to persuade the directory servers
1508 that those ORs are trustworthy and independant, then occasionally
1509 some user will choose one of those ORs for the start and another of
1510 those ORs as the end of a circuit. When this happens, the user's
1511 anonymity is compromised for those circuits. If an adversary can
1512 control $m$ out of $N$ nodes, he should be able to correlate at most
1513 $
\frac{m
}{N
}$ of the traffic in this way---although an adersary
1514 could possibly attract a disproportionately large amount of traffic
1515 by running an exit node with an unusually permisssive exit policy.
1517 \item \emph{Compromise entire path.
} Anyone compromising both
1518 endpoints of a circuit can confirm this with high probability. If
1519 the entire path is compromised, this becomes a certainty; however,
1520 the added benefit to the adversary of such an attack is small in
1521 relation to the difficulty.
1523 \item \emph{Run a hostile directory server.
} Directory servers control
1524 admission to the network. However, because the network directory
1525 must be signed by a majority of servers, the threat of a single
1526 hostile server is minimized.
1528 \item \emph{Selectively DoS a Tor node.
} As noted, neighbors are
1529 bandwidth limited; however, it is possible to open up sufficient
1530 circuits that converge at a single onion router to
1531 overwhelm its network connection, its ability to process new
1534 \item \emph{Introduce timing into messages.
} This is simply a stronger
1535 version of passive timing attacks already discussed above.
1537 \item \emph{Tagging attacks.
} A hostile node could try to ``tag'' a
1538 cell by altering it. This would render it unreadable, but if the
1539 connection is, for example, an unencrypted request to a Web site,
1540 the garbled content coming out at the appropriate time could confirm
1541 the association. However, integrity checks on cells prevent
1542 this attack from succeeding.
1544 \item \emph{Replace contents of unauthenticated protocols.
} When a
1545 relaying an unauthenticated protocol like HTTP, a hostile exit node
1546 can impersonate the target server. Thus, whenever possible, clients
1547 should prefer protocols with end-to-end authentication.
1549 \item \emph{Replay attacks.
} Some anonymity protocols are vulnerable
1550 to replay attacks. Tor is not; replaying one side of a handshake
1551 will result in a different negotiated session key, and so the rest
1552 of the recorded session can't be used.
1553 % ``NonSSL Anonymizer''?
1555 \item \emph{Smear attacks.
} An attacker could use the Tor network to
1556 engage in socially dissapproved acts, so as to try to bring the
1557 entire network into disrepute and get its operators to shut it down.
1558 Exit policies can help reduce the possibilities for abuse, but
1559 ultimately, the network will require volunteers who can tolerate
1560 some political heat.
1562 \item \emph{Distribute hostile code.
} An attacker could trick users
1563 into running subverted Tor software that did not, in fact, anonymize
1564 their connections---or worse, trick ORs into running weakened
1565 software that provided users with less anonymity. We address this
1566 problem (but do not solve it completely) by signing all Tor releases
1567 with an official public key, and including an entry the directory
1568 describing which versions are currently believed to be secure. To
1569 prevent an attacker from subverting the official release itself
1570 (through threats, bribery, or insider attacks), we provide all
1571 releases in source code form, encourage source audits, and
1572 frequently warn our users never to trust any software (even from
1573 us!) that comes without source.
1576 \subsubsection*
{Directory attacks
}
1578 \item \emph{Destroy directory servers.
} If a single directory
1579 server drops out of operation, the others still arrive at a final
1580 directory. So long as any directory servers remain in operation,
1581 they will still broadcast their views of the network and generate a
1582 consensus directory. (If more than half are destroyed, this
1583 directory will not, however, have enough signatures for clients to
1584 use it automatically; human intervention will be necessary for
1585 clients to decide whether to trust the resulting directory.)
1587 \item \emph{Subvert a directory server.
} By taking over a directory
1588 server, an attacker can influence (but not control) the final
1589 directory. Since ORs are included or excluded by majority vote,
1590 the corrupt directory can at worst cast a tie-breaking vote to
1591 decide whether to include marginal ORs. How often such marginal
1592 cases will occur in practice, however, remains to be seen.
1594 \item \emph{Subvert a majority of directory servers.
} If the
1595 adversary controls more than half of the directory servers, he can
1596 decide on a final directory, and thus can include as many
1597 compromised ORs in the final directory as he wishes. Other than
1598 trying to ensure that directory server operators are truly
1599 independent and resistant to attack, Tor does not address this
1602 \item \emph{Encourage directory server dissent.
} The directory
1603 agreement protocol requires that directory server operators agree on
1604 the list of directory servers. An adversary who can persuade some
1605 of the directory server operators to distrust one another could
1606 split the quorum into mutually hostile camps, thus partitioning
1607 users based on which directory they used. Tor does not address
1610 \item \emph{Trick the directory servers into listing a hostile OR.
}
1611 Our threat model explicitly assumes directory server operators will
1612 be able to filter out most hostile ORs. If this is not true, an
1613 attacker can flood the directory with compromised servers.
1615 \item \emph{Convince the directories that a malfunctioning OR is
1616 working.
} In the current Tor implementation, directory servers
1617 assume that if they can start a TLS connection to an an OR, that OR
1618 must be running correctly. It would be easy for a hostile OR to
1619 subvert this test by only accepting TLS connections from ORs, and
1620 ignoring all cells. Thus, directory servers must actively test ORs
1621 by building circuits and streams as appropriate. The benefits and
1622 hazards of a similar approach are discussed in
\cite{mix-acc
}.
1626 \subsubsection*
{Attacks against rendezvous points
}
1628 \item \emph{Make many introduction requests.
} An attacker could
1629 attempt to deny Bob service by flooding his Introduction Point with
1630 requests. Because the introduction point can block requests that
1631 lack authentication tokens, however, Bob can restrict the volume of
1632 requests he receives, or require a certain amount of computation for
1633 every request he receives.
1635 \item \emph{Attack an introduction point.
} An attacker could try to
1636 disrupt a location-hidden service by disabling its introduction
1637 point. But because a service's identity is attached to its public
1638 key, not its introduction point, the service can simply re-advertise
1639 itself at a different introduction point.
1641 \item \emph{Compromise an introduction point.
} If an attacker controls
1642 an introduction point for a service, it can flood the service with
1643 introduction requests, or prevent valid introduction requests from
1644 reaching the hidden server. The server will notice a flooding
1645 attempt if it receives many introduction requests. To notice
1646 blocking of valid requests, however, the hidden server should
1647 periodically test the introduction point by sending its introduction
1648 requests, and making sure it receives them.
1650 \item \emph{Compromise a rendezvous point.
} Controlling a rendezvous
1651 point gains an attacker no more than controlling any other OR along
1652 a circuit, since all data passing along the rendezvous is protected
1653 by the session key shared by the client and server.
1658 \Section{Open Questions in Low-latency Anonymity
}
1659 \label{sec:maintaining-anonymity
}
1661 % There must be a better intro than this! -NM
1662 In addition to the open problems discussed in
1663 Section~
\ref{subsec:non-goals
}, many other questions remain to be
1664 solved by future research before we can be truly confident that we
1665 have built a secure low-latency anonymity service.
1667 Many of these open issues are questions of balance. For example,
1668 how often should users rotate to fresh circuits? Too-frequent
1669 rotation is inefficient and expensive, but too-infrequent rotation
1670 makes the user's traffic linkable. Instead of opening a fresh
1671 circuit; clients can also limit linkability exit from a middle point
1672 of the circuit, or by truncating and re-extending the circuit, but
1673 more analysis is needed to determine the proper trade-off.
1674 %[XXX mention predecessor attacks?]
1676 A similar question surrounds timing of directory operations:
1677 how often should directories be updated? With too-infrequent
1678 updates clients receive an inaccurate picture of the network; with
1679 too-frequent updates the directory servers are overloaded.
1681 %do different exit policies at different exit nodes trash anonymity sets,
1682 %or not mess with them much?
1684 %% Why would they? By routing traffic to certain nodes preferentially?
1686 %[XXX Choosing paths and path lengths: I'm not writing this bit till
1687 % Arma's pathselection stuff is in. -NM]
1689 %%%% Roger said that he'd put a path selection paragraph into section
1690 %%%% 4 that would replace this.
1692 %I probably should have noted that this means loops will be on at least
1693 %five hop routes, which should be rare given the distribution. I'm
1694 %realizing that this is reproducing some of the thought that led to a
1695 %default of five hops in the original onion routing design. There were
1696 %some different assumptions, which I won't spell out now. Note that
1697 %enclave level protections really change these assumptions. If most
1698 %circuits are just two hops, then just a single link observer will be
1699 %able to tell that two enclaves are communicating with high probability.
1700 %So, it would seem that enclaves should have a four node minimum circuit
1701 %to prevent trivial circuit insider identification of the whole circuit,
1702 %and three hop minimum for circuits from an enclave to some nonclave
1703 %responder. But then... we would have to make everyone obey these rules
1704 %or a node that through timing inferred it was on a four hop circuit
1705 %would know that it was probably carrying enclave to enclave traffic.
1706 %Which... if there were even a moderate number of bad nodes in the
1707 %network would make it advantageous to break the connection to conduct
1708 %a reformation intersection attack. Ahhh! I gotta stop thinking
1709 %about this and work on the paper some before the family wakes up.
1710 %On Sat, Oct 25, 2003 at 06:57:12AM -0400, Paul Syverson wrote:
1711 %> Which... if there were even a moderate number of bad nodes in the
1712 %> network would make it advantageous to break the connection to conduct
1713 %> a reformation intersection attack. Ahhh! I gotta stop thinking
1714 %> about this and work on the paper some before the family wakes up.
1715 %This is the sort of issue that should go in the 'maintaining anonymity
1716 %with tor' section towards the end. :)
1717 %Email from between roger and me to beginning of section above. Fix and move.
1719 Throughout this paper, we have assumed that end-to-end traffic
1720 analysis will immediately and automatically defeat a low-latency
1721 anonymity system. Even high-latency anonymity
1722 systems can be vulnerable to end-to-end traffic analysis, if the
1723 traffic volumes are high enough, and if users' habits are sufficiently
1724 distinct
\cite{limits-open,statistical-disclosure
}.
\emph{Can
1725 anything be done to make low-latency systems resist these attacks as
1726 well as high-latency systems?
}
1727 Tor already makes some effort to conceal the starts and
1728 ends of streams by wrapping all long-range control commands in
1729 identical-looking relay cells, but more analysis is needed. Link
1730 padding could frustrate passive observers who count packets; long-range
1731 padding could work against observers who own the first hop in a
1732 circuit. But more research needs to be done in order to find an
1733 efficient and practical approach. Volunteers prefer not to run
1734 constant-bandwidth padding; but more sophisticated traffic shaping
1735 approaches remain somewhat unanalyzed.
1738 on long-range padding
\cite{defensive-dropping
} shows promise. One
1739 could also try to reduce correlation in packet timing by batching and
1740 re-ordering packets, but it is unclear whether this could improve
1741 anonymity without introducing so much latency as to render the
1744 Even if passive timing attacks were wholly solved, active timing
1745 attacks would remain.
\emph{What can
1746 be done to address attackers who can introduce timing patterns into
1747 a user's traffic?
} % [XXX mention likely approaches]
1749 %%% I think we cover this by framing the problem as ``Can we make
1750 %%% end-to-end characteristics of low-latency systems as good as
1751 %%% those of high-latency systems?'' Eliminating long-term
1752 %%% intersection is a hard problem.
1754 %Even regardless of link padding from Alice to the cloud, there will be
1755 %times when Alice is simply not online. Link padding, at the edges or
1756 %inside the cloud, does not help for this.
1758 In order to scale to large numbers of users, and to prevent an
1759 attacker from observing the whole network at once, it may be necessary
1760 for low-latency anonymity systems to support far more servers than Tor
1761 currently anticipates. This introduces several issues. First, if
1762 approval by a centralized set of directory servers is no longer
1763 feasible, what mechanism should be used to prevent adversaries from
1764 signing up many spurious servers?
1765 Second, if clients can no longer have a complete
1766 picture of the network at all times, how can should they perform
1767 discovery while preventing attackers from manipulating or exploiting
1768 gaps in client knowledge? Third, if there are too many servers
1769 for every server to constantly communicate with every other, what kind
1770 of non-clique topology should the network use? Restricted-route
1771 topologies promise comparable anonymity with better scalability
1772 \cite{danezis-pets03
}, but whatever topology we choose, we need some
1773 way to keep attackers from manipulating their position within it.
1774 Fourth, since no centralized authority is tracking server reliability,
1775 How do we prevent unreliable servers from rendering the network
1776 unusable? Fifth, do clients receive so much anonymity benefit from
1777 running their own servers that we should expect them all to do so, or
1778 do we need to find another incentive structure to motivate them?
1779 (Tarzan and MorphMix present possible solutions.)
1781 % [[ XXX how to approve new nodes (advogato, sybil, captcha (RTT));]
1783 Alternatively, it may be the case that one of these problems proves
1784 intractable, or that the drawbacks to many-server systems prove
1785 greater than the benefits. Nevertheless, we may still do well to
1786 consider non-clique topologies. A cascade topology may provide more
1787 defense against traffic confirmation.
1788 % XXX Why would it? Cite. -NM
1789 Does the hydra (many inputs, few outputs) topology work
1790 better? Are we going to get a hydra anyway because most nodes will be
1793 As mentioned in Section~
\ref{subsec:dos
}, Tor could improve its
1794 robustness against node failure by buffering transmitted stream data
1795 at the network's edges until the data has been acknowledged by the
1796 other end of the stream. The efficacy of this approach remains to be
1797 tested, however, and there may be more effective means for ensuring
1798 reliable connections in the presence of unreliable nodes.
1800 %%% Keeping this original paragraph for a little while, since it
1801 %%% is not the same as what's written there now.
1803 %Because Tor depends on TLS and TCP to provide a reliable transport,
1804 %when one of the servers goes down, all the circuits (and thus streams)
1805 %traveling over that server must break. This reduces anonymity because
1806 %everybody needs to reconnect right then (does it? how much?) and
1807 %because exit connections all break at the same time, and it also harms
1808 %usability. It seems the problem is even worse in a peer-to-peer
1809 %environment, because so far such systems don't really provide an
1810 %incentive for nodes to stay connected when they're done browsing, so
1811 %we would expect a much higher churn rate than for onion routing.
1812 %there ways of allowing streams to survive the loss of a node in the
1815 % Roger or Paul suggested that we say something about incentives,
1816 % too, but I think that's a better candidate for our future work
1817 % section. After all, we will doubtlessly learn very much about why
1818 % people do or don't run and use Tor in the near future. -NM
1820 %We should run a squid at each exit node, to provide comparable anonymity
1821 %to private exit nodes for cache hits, to speed everything up, and to
1822 %have a buffer for funny stuff coming out of port 80.
1823 % on the other hand, it hampers PFS, because ORs have pages in the cache.
1824 %I previously elsewhere suggested bulk transfer proxies to carve
1825 %up big things so that they could be downloaded in less noticeable
1826 %pieces over several normal looking connections. We could suggest
1827 %similarly one or a handful of squid nodes that might serve up
1828 %some of the more sensitive but common material, especially if
1829 %the relevant sites didn't want to or couldn't run their own OR.
1830 %This would be better than having everyone run a squid which would
1831 %just help identify after the fact the different history of that
1832 %node's activity. All this kind of speculation needs to move to
1833 %future work section I guess. -PS]
1835 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1837 \Section{Future Directions
}
1838 \label{sec:conclusion
}
1840 Tor brings together many innovations into
1841 a unified deployable system. But there are still several attacks that
1842 work quite well, as well as a number of sustainability and run-time
1843 issues remaining to be ironed out. In particular:
1845 % Many of these (Scalability, cover traffic, morphmix)
1846 % are duplicates from open problems.
1849 \item \emph{Scalability:
} Tor's emphasis on design simplicity and
1850 deployability has led us to adopt a clique topology, a
1851 semi-centralized model for directories and trusts, and a
1852 full-network-visibility model for client knowledge. None of these
1853 properties will scale to more than a few hundred servers, at most.
1854 Promising approaches to better scalability exist (see
1855 Section~
\ref{sec:maintaining-anonymity
}), but more deployment
1856 experience would be helpful in learning the relative importance of
1858 \item \emph{Cover traffic:
} Currently we avoid cover traffic because
1859 of its clear costs in performance and bandwidth, and because its
1860 security benefits have not well understood. With more research
1861 \cite{SS03,defensive-dropping
}, the price/value ratio may change,
1862 both for link-level cover traffic and also long-range cover traffic.
1863 \item \emph{Better directory distribution:
} Even with the threshold
1864 directory agreement algorithm described in Section~
\ref{subsec:dirservers
},
1865 the directory servers are still trust bottlenecks. We must find more
1866 decentralized yet practical ways to distribute up-to-date snapshots of
1867 network status without introducing new attacks. Also, directory
1868 retrieval presents a scaling problem, since clients currently
1869 download a description of the entire network state every
15
1870 minutes. As the state grows larger and clients more numerous, we
1871 may need to move to a solution in which clients only receive
1872 incremental updates to directory state, or where directories are
1873 cached at the ORs to avoid high loads on the directory servers.
1874 \item \emph{Implementing location-hidden servers:
} While
1875 Section~
\ref{sec:rendezvous
} describes a design for rendezvous
1876 points and location-hidden servers, these feature has not yet been
1877 implemented. While doing so, will likely encounter additional
1878 issues, both in terms of usability and anonymity, that must be
1880 \item \emph{Further specification review:
} Although we have a public,
1881 byte-level specification for the Tor protocols, this protocol has
1882 not received extensive external review. We hope that as Tor
1883 becomes more widely deployed, more people will become interested in
1884 examining our specification.
1885 \item \emph{Wider-scale deployment:
} The original goal of Tor was to
1886 gain experience in deploying an anonymizing overlay network, and
1887 learn from having actual users. We are now at the point in design
1888 and development where we can start deploying a wider network. Once
1889 we have are ready for actual users, we will doubtlessly be better
1890 able to evaluate some of our design decisions, including our
1891 robustness/latency trade-offs, our performance trade-offs (including
1892 cell size), our abuse-prevention mechanisms, and
1893 our overall usability.
1894 % XXX large and small cells on same network.
1895 % XXX work with morphmix spec
1898 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1900 %% commented out for anonymous submission
1901 %\Section{Acknowledgments}
1902 % Peter Palfrader, Geoff Goodell, Adam Shostack, Joseph Sokol-Margolis,
1904 % for editing and comments
1905 % Matej Pfajfar, Andrei Serjantov, Marc Rennhard for design discussions
1906 % Bram Cohen for congestion control discussions
1907 % Adam Back for suggesting telescoping circuits
1909 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1911 \bibliographystyle{latex8
}
1912 \bibliography{tor-design
}
1918 % avoid contractions (it's, can't, etc.)
1919 % prefer ``for example'' or ``such as'' to e.g.
1920 % prefer ``that is'' to i.e.
1921 % 'mix', 'mixes' (as noun)
1923 % 'mix', 'mixing' (as verb)
1924 % 'middleman' [Not with a hyphen; the hyphen has been optional
1925 % since Middle English.]
1927 % 'Cypherpunk', 'Cypherpunks', 'Cypherpunk remailer'
1928 % 'Onion Routing design', 'onion router' [note capitalization]
1930 % Try not to use \cite as a noun.
1931 % 'Authorizating' sounds great, but it isn't a word.
1932 % 'First, second, third', not 'Firstly, secondly, thirdly'.
1933 % 'circuit', not 'channel'
1934 % Typography: no space on either side of an em dash---ever.
1935 % Hyphens are for multi-part words; en dashs imply movement or
1936 % opposition (The Alice--Bob connection); and em dashes are
1937 % for punctuation---like that.
1938 % A relay cell; a control cell; a \emph{create} cell; a
1939 % \emph{relay truncated} cell. Never ``a \emph{relay truncated}.''
1941 % 'Substitute ``Damn'' every time you're inclined to write ``very;'' your
1942 % editor will delete it and the writing will be just as it should be.'