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. Tor is the successor to Onion Routing
55 and addresses various limitations in the original Onion Routing design.
56 Tor works in a real-world Internet environment, requires no special
57 privileges such as root- or kernel-level access,
58 requires little synchronization or coordination between nodes, and
59 provides a reasonable tradeoff between anonymity, usability, and efficiency.
60 We include a new, more practical design for rendezvous points, and we
61 provide a list of open problems in anonymous communication systems today.
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'')
78 predecessor and successor, but no others. Traffic flowing down the circuit
79 is sent in fixed-size
\emph{cells
}, which are unwrapped by a symmetric key
80 at each node (like the layers of an onion) and relayed downstream. The
81 original Onion Routing project published several design and analysis
83 \cite{or-ih96,or-jsac98,or-discex00,or-pet00
}. While
84 a wide area Onion Routing network was deployed for some weeks,
85 the only long-running and publicly accessible
86 implementation of the original design was a fragile proof-of-concept
87 that ran on a single machine. Even this simple deployment processed tens
88 of thousands of connections daily from thousands of users worldwide. But
89 many critical design and deployment issues were never resolved, and the
90 design has not been updated in several years. Here we describe Tor, a
91 protocol for asynchronous, loosely federated onion routers that provides
92 the following improvements over the old Onion Routing design:
96 \item \textbf{Perfect forward secrecy:
} The original Onion Routing
97 design was vulnerable to a single hostile node recording traffic and later
98 compromising successive nodes in the circuit and forcing them to
100 Rather than using a single onion to lay each circuit,
101 Tor now uses an incremental or
\emph{telescoping
}
102 path-building design, where the initiator negotiates session keys with
103 each successive hop in the circuit. Once these keys are deleted,
104 subsequently compromised nodes cannot decrypt old traffic.
105 As a side benefit, onion replay detection is no longer
106 necessary, and the process of building circuits is more reliable, since
107 the initiator knows when a hop fails and can then try extending to a new node.
109 % Perhaps mention that not all of these are things that we invented. -NM
111 \item \textbf{Separation of protocol cleaning from anonymity:
}
112 The original Onion Routing design required a separate ``application
114 supported application protocol---most
115 of which were never written, so many applications were never supported.
116 Tor uses the standard and near-ubiquitous SOCKS
117 \cite{socks4
} proxy interface, allowing us to support most TCP-based
118 programs without modification. This design change allows Tor to
119 use the filtering features of privacy-enhancing
120 application-level proxies such as Privoxy
\cite{privoxy
} without having to
121 incorporate those features itself.
123 \item \textbf{Many TCP streams can share one circuit:
} The original
124 Onion Routing design built a separate circuit for each application-level
126 This hurt performance by requiring multiple public key operations for
127 every request, and also presented
128 a threat to anonymity from building so many different circuits; see
129 Section~
\ref{sec:maintaining-anonymity
}.
130 Tor multiplexes multiple TCP streams along each virtual
131 circuit, to improve efficiency and anonymity.
133 \item \textbf{Leaky-pipe circuit topology:
} Through in-band signalling
134 within the circuit, Tor initiators can direct traffic to nodes partway
135 down the circuit. This allows for long-range padding to frustrate traffic
136 shape and volume attacks at the initiator
\cite{defensive-dropping
}.
137 Because circuits are used by more than one application, it also allows
138 traffic to exit the circuit from the middle---thus frustrating traffic
139 shape and volume attacks based on observing the end of the circuit.
141 \item \textbf{No mixing, padding, or traffic shaping:
} The original
142 Onion Routing design called for batching and reordering the cells arriving
143 from each circuit. It also included padding between onion routers and,
144 in a later design, between onion
145 proxies (that is, users) and onion routers
\cite{or-ih96,or-jsac98
}.
146 The tradeoff between padding protection and cost was discussed, but no
147 general padding scheme was suggested. In
148 \cite{or-pet00
} it was theorized
\emph{traffic shaping
} would generally
149 be used, but details were not provided.
150 Recent research
\cite{econymics
} and deployment
151 experience
\cite{freedom21-security
} suggest that this level of resource
152 use is not practical or economical; and even full link padding is still
153 vulnerable
\cite{defensive-dropping
}. Thus, until we have a proven and
154 convenient design for traffic shaping or low-latency mixing that
155 will improve anonymity against a realistic adversary, we leave these
158 \item \textbf{Congestion control:
} Earlier anonymity designs do not
159 address traffic bottlenecks. Unfortunately, typical approaches to load
160 balancing and flow control in overlay networks involve inter-node control
161 communication and global views of traffic. Tor's decentralized congestion
162 control uses end-to-end acks to maintain reasonable anonymity while
164 at the edges of the network to detect congestion or flooding attacks
165 and send less data until the congestion subsides.
167 \item \textbf{Directory servers:
} The original Onion Routing design
168 planned to flood link-state information through the network---an
169 approach which can be unreliable and
170 open to partitioning attacks or outright deception. Tor takes a simplified
171 view towards distributing link-state information. Certain more trusted
172 onion routers also act as directory servers: they provide signed
173 \emph{directories
} which describe the routers they know about and mark
175 are currently up. Users periodically download these directories via HTTP.
177 \item \textbf{End-to-end integrity checking:
} The original Onion Routing
178 design did no integrity checking on data. Any onion router on the circuit
179 could change the contents of cells as they pass by---for example, to
181 connection on the fly so it connects to a different webserver, or to
182 tag encrypted traffic and look for the tagged traffic at the network
183 edges
\cite{minion-design
}. Tor hampers these attacks by checking data
184 integrity before it leaves the network.
186 \item \textbf{Robustness to failed nodes:
} A failed node in the old design
187 meant that circuit-building failed, but thanks to Tor's step-by-step
188 circuit building, users can notice failed
189 nodes while building circuits and route around them. Additionally,
190 liveness information from directories allows users to avoid
191 unreliable nodes in the first place.
192 %We further provide a
193 %simple mechanism that allows connections to be established despite recent
194 %node failure or slightly dated information from a directory server. Tor
195 %permits onion routers to have \emph{router twins}---nodes that share
196 %the same private decryption key. Note that because connections now have
197 %perfect forward secrecy, an onion router still cannot read the traffic
198 %on a connection established through its twin even while that connection
199 %is active. Also, which nodes are twins can change dynamically depending
200 %on current circumstances, and twins may or may not be under the same
201 %administrative authority.
203 %[Commented out; Router twins provide no real increase in robustness
204 %to failed nodes. If a non-twinned node goes down, the
205 %circuit-builder notices this and routes around it. Circuit-building
206 %is offline, so there shouldn't even be a latency hit. -NM]
208 \item \textbf{Variable exit policies:
} Tor provides a consistent
210 each node to specify and advertise a policy describing the hosts and
211 ports to which it will connect. These exit policies
212 are critical in a volunteer-based distributed infrastructure, because
213 each operator is comfortable with allowing different types of traffic
214 to exit the Tor network from his node.
216 \item \textbf{Implementable in user-space:
} Unlike other anonymity systems
217 like Freedom
\cite{freedom2-arch
}, Tor only attempts to anonymize TCP
218 streams. Thus it does not require patches to an operating system's network
219 stack (or built-in support) to operate. Although this approach is less
220 flexible, it has proven valuable to Tor's portability and deployability.
222 \item \textbf{Rendezvous points and location-protected servers:
}
223 Tor provides an integrated mechanism for responder anonymity via
224 location-protected servers. Previous Onion Routing designs included
225 long-lived ``reply onions'' which could be used to build virtual circuits
226 to a hidden server, but a reply onion becomes useless if any node in
227 the path goes down or rotates its keys, and it also does not provide
228 forward security. In Tor's current design, clients negotiate
{\it
229 rendezvous points
} to connect with hidden servers; reply onions are no
233 We have implemented most of the above features. Our source code is
234 available under a free license, and is not encumbered by patents. We have
235 recently begun deploying a widespread alpha network to see how well the
236 design works in practice, to get more experience with usability and users,
237 and to provide a research platform for experimenting with new ideas.
239 We review previous work in Section~
\ref{sec:related-work
}, describe
240 our goals and assumptions in Section~
\ref{sec:assumptions
},
241 and then address the above list of improvements in
242 Sections~
\ref{sec:design
}-
\ref{sec:rendezvous
}. We
243 summarize in Section
\ref{sec:analysis
}
244 how our design stands up to known attacks, and conclude with a list of
247 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
249 \Section{Related work
}
250 \label{sec:related-work
}
252 Modern anonymity designs date to Chaum's Mix-Net
\cite{chaum-mix
} design of
253 1981. Chaum proposed hiding sender-recipient linkability by wrapping
254 messages in layers of public key cryptography, and relaying them
255 through a path composed of ``Mixes.'' These mixes in turn decrypt, delay,
256 and re-order messages, before relaying them along the sender-selected
257 path towards their destinations.
259 Subsequent relay-based anonymity designs have diverged in two
260 principal directions. Some have attempted to maximize anonymity at
261 the cost of introducing comparatively large and variable latencies,
262 for example, Babel
\cite{babel
}, Mixmaster
\cite{mixmaster-spec
}, and
263 Mixminion
\cite{minion-design
}. Because of this
264 trade-off, these
\emph{high-latency
} networks are well-suited for anonymous
265 email, but introduce too much lag for interactive tasks such as web browsing,
266 internet chat, or SSH connections.
268 Tor belongs to the second category:
\emph{low-latency
} designs that
269 attempt to anonymize interactive network traffic. These systems handle
270 a variety of bidirectional protocols. They also provide more convenient
271 mail delivery than the high-latency fire-and-forget anonymous email
272 networks, because the remote mail server provides explicit delivery
273 confirmation. But because these designs typically
274 involve a large number of packets that must be delivered quickly, it is
275 difficult for them to prevent an attacker who can eavesdrop both ends of the
276 communication from correlating the timing and volume
277 of traffic entering the anonymity network with traffic leaving it. These
278 protocols are also vulnerable against active attacks in which an
279 adversary introduces timing patterns into traffic entering the network, and
281 for correlated patterns among exiting traffic.
282 Although some work has been done to frustrate
283 these attacks,
\footnote{
284 The most common approach is to pad and limit communication to a constant
286 the variation in traffic shape. Doing so can have prohibitive bandwidth
287 costs and/or performance limitations.
288 } most designs protect primarily against traffic analysis rather than traffic
289 confirmation
\cite{or-jsac98
}---that is, they assume that the attacker is
290 attempting to learn who is talking to whom, not to confirm a prior suspicion
291 about who is talking to whom.
293 The simplest low-latency designs are single-hop proxies such as the
294 Anonymizer
\cite{anonymizer
}, wherein a single trusted server strips the
295 data's origin before relaying it. These designs are easy to
296 analyze, but require end-users to trust the anonymizing proxy.
297 Concentrating the traffic to a single point increases the anonymity set
298 (the set of people a given user is hiding among), but it can make traffic
299 analysis easier: an adversary need only eavesdrop on the proxy to observe
302 More complex are distributed-trust, circuit-based anonymizing systems.
303 In these designs, a user establishes one or more medium-term bidirectional
304 end-to-end circuits, and tunnels TCP streams in fixed-size cells.
305 Establishing circuits is expensive and typically requires public-key
306 cryptography, whereas relaying cells is comparatively inexpensive.
307 Because a circuit crosses several servers, no single server can link a
308 user to her communication partners.
310 The Java Anon Proxy (also known
311 as JAP or Web MIXes) uses fixed shared routes known as
312 \emph{cascades
}. As with a single-hop proxy, this approach aggregates
313 users into larger anonymity sets, but again an attacker only needs to
314 observe both ends of the cascade to bridge all the system's traffic.
315 The Java Anon Proxy's design provides protection by padding
316 between end users and the head of the cascade
\cite{web-mix
}. However, the
317 current implementation does no padding and thus remains vulnerable
318 to both active and passive bridging.
319 %XXX fix, yes it does, sort of.
321 PipeNet
\cite{back01, pipenet
}, another low-latency design proposed at
322 about the same time as the original Onion Routing design, provided
323 stronger anonymity at the cost of allowing a single user to shut
324 down the network simply by not sending. Low-latency anonymous
325 communication has also been designed for other environments such as
326 ISDN
\cite{isdn-mixes
}.
328 In P2P designs like Tarzan
\cite{tarzan:ccs02
} and MorphMix
329 \cite{morphmix:fc04
}, all participants both generate traffic and relay
330 traffic for others. Rather than aiming to hide the originator within a
331 group of other originators, these systems instead aim to prevent a peer
332 or observer from knowing whether a given peer originated the request
333 or just relayed it from another peer. While Tarzan and MorphMix use
334 layered encryption as above, Crowds
\cite{crowds-tissec
} simply assumes
335 an adversary who cannot observe the initiator: it uses no public-key
336 encryption, so nodes on a circuit can read that circuit's traffic. The
337 anonymity of the initiator relies on filtering all identifying information
338 from the data stream.
340 Hordes
\cite{hordes-jcs
} is based on Crowds but also uses multicast
341 responses to hide the initiator. Herbivore
\cite{herbivore
} and P5
342 \cite{p5
} go even further, requiring broadcast. They make anonymity
343 and efficiency tradeoffs to make broadcast more practical.
344 These systems are designed primarily for communication between peers,
345 although Herbivore users can make external connections by
346 requesting a peer to serve as a proxy. Allowing easy connections to
347 nonparticipating responders or recipients is important for usability,
348 for example so users can visit nonparticipating Web sites or exchange
349 mail with nonparticipating recipients.
351 Systems like Freedom and the original Onion Routing build the circuit
352 all at once, using a layered ``onion'' of public-key encrypted messages,
353 each layer of which provides a set of session keys and the address of the
354 next server in the circuit. Tor as described herein, Tarzan, MorphMix,
355 Cebolla
\cite{cebolla
}, and AnonNet
\cite{anonnet
} build the circuit
356 in stages, extending it one hop at a time. This approach makes perfect
357 forward secrecy feasible.
359 Circuit-based anonymity designs must choose which protocol layer
360 to anonymize. They may choose to intercept IP packets directly, and
361 relay them whole (stripping the source address) as the contents of
362 the circuit
\cite{freedom2-arch,tarzan:ccs02
}. Alternatively, like
363 Tor, they may accept TCP streams and relay the data in those streams
364 along the circuit, ignoring the breakdown of that data into TCP frames
365 \cite{morphmix:fc04,anonnet
}. Finally, they may accept application-level
366 protocols (such as HTTP) and relay the application requests themselves
368 This protocol-layer decision represents a compromise between flexibility
369 and anonymity. For example, a system that understands HTTP can strip
370 identifying information from those requests, can take advantage of caching
371 to limit the number of requests that leave the network, and can batch
372 or encode those requests in order to minimize the number of connections.
373 On the other hand, an IP-level anonymizer can handle nearly any protocol,
374 even ones unforeseen by their designers (though these systems require
375 kernel-level modifications to some operating systems, and so are more
376 complex and less portable). TCP-level anonymity networks like Tor present
377 a middle approach: they are fairly application neutral (so long as the
378 application supports, or can be tunneled across, TCP), but by treating
379 application connections as data streams rather than raw TCP packets,
380 they avoid the well-known inefficiencies of tunneling TCP over TCP
381 \cite{tcp-over-tcp-is-bad
}.
383 Distributed-trust anonymizing systems need to prevent attackers from
384 adding too many servers and thus compromising too many user paths.
385 Tor relies on a small set of well-known directory servers, run by
386 independent parties, to make
387 decisions about which nodes can join. Tarzan
388 and MorphMix allow unknown users to run servers, and limit an attacker
389 from becoming too much of the network based on a limited resource such
390 as number of IPs controlled. Crowds suggests requiring written, notarized
391 requests from potential crowd members.
393 Anonymous communication is essential for censorship-resistant
394 systems like Eternity
\cite{eternity
}, Free~Haven
\cite{freehaven-berk
},
395 Publius
\cite{publius
}, and Tangler
\cite{tangler
}. Tor's rendezvous
396 points enable connections between mutually anonymous entities; they
397 are a building block for location-hidden servers, which are needed by
398 Eternity and Free~Haven.
400 % didn't include rewebbers. No clear place to put them, so I'll leave
401 % them out for now. -RD
403 \Section{Design goals and assumptions
}
404 \label{sec:assumptions
}
407 Like other low-latency anonymity designs, Tor seeks to frustrate
408 attackers from linking communication partners, or from linking
409 multiple communications to or from a single user. Within this
410 main goal, however, several design considerations have directed
413 \textbf{Deployability:
} The design must be one which can be implemented,
414 deployed, and used in the real world. This requirement precludes designs
415 that are expensive to run (for example, by requiring more bandwidth
416 than volunteers are willing to provide); designs that place a heavy
417 liability burden on operators (for example, by allowing attackers to
418 implicate onion routers in illegal activities); and designs that are
419 difficult or expensive to implement (for example, by requiring kernel
420 patches, or separate proxies for every protocol). This requirement also
421 precludes systems in which users who do not benefit from anonymity are
422 required to run special software in order to communicate with anonymous
423 parties. (We do not meet this goal for the current rendezvous design,
424 however; see Section~
\ref{sec:rendezvous
}.)
426 \textbf{Usability:
} A hard-to-use system has fewer users---and because
427 anonymity systems hide users among users, a system with fewer users
428 provides less anonymity. Usability is not only a convenience for Tor:
429 it is a security requirement
\cite{econymics,back01
}. Tor should not
430 require modifying applications; should not introduce prohibitive delays;
431 and should require the user to make as few configuration decisions
434 \textbf{Flexibility:
} The protocol must be flexible and well-specified,
435 so that it can serve as a test-bed for future research in low-latency
436 anonymity systems. Many of the open problems in low-latency anonymity
437 networks, such as generating dummy traffic or preventing Sybil attacks
438 \cite{sybil
}, may be solvable independently from the issues solved by
439 Tor. Hopefully future systems will not need to reinvent Tor's design.
440 (But note that while a flexible design benefits researchers,
441 there is a danger that differing choices of extensions will make users
442 distinguishable. Experiments should be run on a separate network.)
444 \textbf{Simple design:
} The protocol's design and security
445 parameters must be well-understood. Additional features impose implementation
446 and complexity costs; adding unproven techniques to the design threatens
447 deployability, readability, and ease of security analysis. Tor aims to
448 deploy a simple and stable system that integrates the best well-understood
449 approaches to protecting anonymity.
451 \SubSection{Non-goals
}
452 \label{subsec:non-goals
}
453 In favoring simple, deployable designs, we have explicitly deferred
454 a number of goals, either because they are solved elsewhere, or because
455 they are an open research question.
457 \textbf{Not Peer-to-peer:
} Tarzan and MorphMix aim to scale to completely
458 decentralized peer-to-peer environments with thousands of short-lived
459 servers, many of which may be controlled by an adversary. This approach
460 is appealing, but still has many open problems
461 \cite{tarzan:ccs02,morphmix:fc04
}.
463 \textbf{Not secure against end-to-end attacks:
} Tor does not claim
464 to provide a definitive solution to end-to-end timing or intersection
465 attacks. Some approaches, such as running an onion router, may help;
466 see Section~
\ref{sec:analysis
} for more discussion.
468 \textbf{No protocol normalization:
} Tor does not provide
\emph{protocol
469 normalization
} like Privoxy or the Anonymizer. For complex and variable
470 protocols such as HTTP, Tor must be layered with a filtering proxy such
471 as Privoxy to hide differences between clients, and expunge protocol
472 features that leak identity. Similarly, Tor does not currently integrate
473 tunneling for non-stream-based protocols like UDP; this too must be
474 provided by an external service.
475 % Actually, tunneling udp over tcp is probably horrible for some apps.
476 % Should this get its own non-goal bulletpoint? The motivation for
477 % non-goal-ness would be burden on clients / portability. -RD
478 % No, leave it as is. -RD
480 \textbf{Not steganographic:
} Tor does not try to conceal which users are
481 sending or receiving communications; it only tries to conceal with whom
484 \SubSection{Threat Model
}
485 \label{subsec:threat-model
}
487 A global passive adversary is the most commonly assumed threat when
488 analyzing theoretical anonymity designs. But like all practical
489 low-latency systems, Tor does not protect against such a strong
490 adversary. Instead, we expect an adversary who can observe some fraction
491 of network traffic; who can generate, modify, delete, or delay traffic
492 on the network; who can operate onion routers of its own; and who can
493 compromise some fraction of the onion routers on the network.
495 %Large adversaries will be able to compromise a considerable fraction
496 %of the network. (In some circumstances---for example, if the Tor
497 %network is running on a hardened network where all operators have
498 %had background checks---the number of compromised nodes could be quite
499 %small.) Compromised nodes can arbitrarily manipulate the connections that
500 %pass through them, as well as creating new connections that pass through
501 %themselves. They can observe traffic, and record it for later analysis.
503 In low-latency anonymity systems that use layered encryption, the
504 adversary's typical goal is to observe both the initiator and the
505 receiver. Passive attackers can confirm a suspicion that Alice is
506 talking to Bob if the timing and volume properties of the traffic on the
507 connection are unique enough; active attackers are even more effective
508 because they can induce timing signatures on the traffic. Tor provides
509 some defenses against these
\emph{traffic confirmation
} attacks, for
510 example by encouraging users to run their own onion routers, but it does
511 not provide complete protection. Rather, we aim to prevent
\emph{traffic
512 analysis
} attacks, where the adversary uses traffic patterns to learn
513 which points in the network he should attack.
515 Our adversary might try to link an initiator Alice with any of her
516 communication partners, or he might try to build a profile of Alice's
517 behavior. He might mount passive attacks by observing the edges of the
518 network and correlating traffic entering and leaving the network---either
519 because of relationships in packet timing; relationships in the volume
520 of data sent; or relationships in any externally visible user-selected
521 options. The adversary can also mount active attacks by compromising
522 routers or keys; by replaying traffic; by selectively denying service
523 to trustworthy routers to encourage users to send their traffic through
524 compromised routers, or denying service to users to see if the traffic
526 network stops; or by introducing patterns into traffic that can later be
527 detected. The adversary might attack the directory servers to give users
528 differing views of network state. Additionally, he can try to decrease
529 the network's reliability by attacking nodes or by performing antisocial
530 activities from reliable servers and trying to get them taken down;
531 making the network unreliable flushes users to other less anonymous
532 systems, where they may be easier to attack.
534 We consider each of these attacks in more detail below, and summarize
535 in Section~
\ref{sec:attacks
} how well the Tor design defends against
538 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
540 \Section{The Tor Design
}
543 The Tor network is an overlay network; each node is called an onion router
544 (OR). Onion routers run as normal user-level processes without needing
546 privileges. Currently, each OR maintains a long-term TLS
\cite{TLS
}
547 connection to every other
548 OR. (We examine some ways to relax this clique-topology assumption in
549 Section~
\ref{subsec:restricted-routes
}.) A subset of the ORs also act as
550 directory servers, tracking which routers are currently in the network;
551 see Section~
\ref{subsec:dirservers
} for directory server details. Users
552 run local software called an onion proxy (OP) to fetch directories,
553 establish paths (called
\emph{virtual circuits
}) across the network,
554 and handle connections from user applications. Onion proxies accept
555 TCP streams and multiplex them across the virtual circuit. The onion
556 router on the other side
557 % I don't mean other side, I mean wherever it is on the circuit. But
558 % don't want to introduce complexity this early? Hm. -RD
559 of the circuit connects to the destinations of
560 the TCP streams and relays data.
562 Each onion router uses three public keys: a long-term identity key, a
563 short-term onion key, and a short-term link key. The identity
564 (signing) key is used to sign TLS certificates, to sign its router
565 descriptor (a summary of its keys, address, bandwidth, exit policy,
566 etc), and to sign directories if it is a directory server. Changing
567 the identity key of a router is considered equivalent to creating a
568 new router. The onion (decryption) key is used for decrypting requests
569 from users to set up a circuit and negotiate ephemeral keys. Finally,
570 link keys are used by the TLS protocol when communicating between
571 onion routers. We discuss rotating these keys in
572 Section~
\ref{subsec:rotating-keys
}.
574 Section~
\ref{subsec:cells
} discusses the structure of the fixed-size
575 \emph{cells
} that are the unit of communication in Tor. We describe
576 in Section~
\ref{subsec:circuits
} how virtual circuits are
577 built, extended, truncated, and destroyed. Section~
\ref{subsec:tcp
}
578 describes how TCP streams are routed through the network, and finally
579 Section~
\ref{subsec:congestion
} talks about congestion control and
585 % I think we should describe connections before cells. -NM
587 Traffic passes from one OR to another, or between a user's OP and an OR,
588 in fixed-size cells. Each cell is
256 bytes (but see
589 Section~
\ref{sec:conclusion
}
590 for a discussion of allowing large cells and small cells on the same
591 network), and consists of a header and a payload. The header includes an
592 anonymous circuit identifier (ACI) that specifies which circuit the
593 % Should we replace ACI with circID ? What is this 'anonymous circuit'
596 (many circuits can be multiplexed over the single TCP connection between
597 ORs or between an OP and an OR), and a command to describe what to do
598 with the cell's payload. Cells are either
\emph{control
} cells, which are
599 interpreted by the node that receives them, or
\emph{relay
} cells,
600 which carry end-to-end stream data. Controls cells can be one of:
601 \emph{padding
} (currently used for keepalive, but also usable for link
602 padding);
\emph{create
} or
\emph{created
} (used to set up a new circuit);
603 or
\emph{destroy
} (to tear down a circuit).
604 % We need to say that ACIs are connection-specific: each circuit has
605 % a different ACI along each connection. -NM
608 Relay cells have an additional header (the relay header) after the
609 cell header, containing the stream identifier (many streams can
610 be multiplexed over a circuit); an end-to-end checksum for integrity
611 checking; the length of the relay payload; and a relay command. Relay
612 commands can be one of:
\emph{relay
613 data
} (for data flowing down the stream),
\emph{relay begin
} (to open a
614 stream),
\emph{relay end
} (to close a stream cleanly),
\emph{relay
615 teardown
} (to close a broken stream),
\emph{relay connected
}
616 (to notify the OP that a relay begin has succeeded),
\emph{relay
617 extend
} and
\emph{relay extended
} (to extend the circuit by a hop,
618 and to acknowledge),
\emph{relay truncate
} and
\emph{relay truncated
}
619 (to tear down only part of the circuit, and to acknowledge),
\emph{relay
620 sendme
} (used for congestion control), and
\emph{relay drop
} (used to
621 implement long-range dummies).
623 We describe each of these cell types in more detail below.
625 \SubSection{Circuits and streams
}
626 \label{subsec:circuits
}
628 % I think when we say ``the user,'' maybe we should say ``the user's OP.''
630 The original Onion Routing design built one circuit for each
631 TCP stream. Because building a circuit can take several tenths of a
632 second (due to public-key cryptography delays and network latency),
633 this design imposed high costs on applications like web browsing that
634 open many TCP streams.
636 In Tor, each circuit can be shared by many TCP streams. To avoid
637 delays, users construct circuits preemptively. To limit linkability
638 among the streams, users rotate connections by building a new circuit
639 periodically if the previous one has been used,
640 and expire old used circuits that are no longer in use. Tor considers
641 making a new circuit once a minute: thus
642 even heavy users spend a negligible amount of time and CPU in
643 building circuits, but only a limited number of requests can be linked
644 to each other by a given exit node. Also, because circuits are built
645 in the background, failed routers do not affect user experience.
647 \subsubsection{Constructing a circuit
}
649 Users construct a circuit incrementally, negotiating a symmetric key with
650 each hop one at a time. To begin creating a new circuit, the user
651 (call her Alice) sends a
\emph{create
} cell to the first node in her
652 chosen path. The cell's payload is the first half of the
653 Diffie-Hellman handshake, encrypted to the onion key of the OR (call
654 him Bob). Bob responds with a
\emph{created
} cell containing the second
655 half of the DH handshake, along with a hash of the negotiated key
658 To extend a circuit past the first hop, Alice sends a
\emph{relay extend
}
659 cell to the last node in the circuit, specifying the address of the new
660 OR and an encrypted $g^x$ for it. That node copies the half-handshake
661 into a
\emph{create
} cell, and passes it to the new OR to extend the
662 circuit. When it responds with a
\emph{created
} cell, the penultimate OR
663 copies the payload into a
\emph{relay extended
} cell and passes it back.
664 % Nick: please fix my "that OR" pronouns -RD
666 The onion-level handshake protocol achieves unilateral entity
667 authentication (Alice knows she's handshaking with Bob, Bob doesn't
668 care who is opening the circuit---Alice has no key and is trying to
669 remain anonymous) and unilateral key authentication (Alice and Bob
670 agree on a key, and Alice knows Bob is the only other person who should
671 know it). We also want perfect forward secrecy and key freshness.
675 \mathrm{Alice
} \rightarrow \mathrm{Bob
}&: E_
{PK_
{Bob
}}(g^x) \\
676 \mathrm{Bob
} \rightarrow \mathrm{Alice
}&: g^y, H(K |
\mathrm{``handshake"
}) \\
680 The second step shows both that it was Bob
681 who received $g^x$, and that it was Bob who came up with $y$. We use
682 PK encryption in the first step (rather than, e.g., using the first two
683 steps of STS, which has a signature in the second step) because we
684 don't have enough room in a single cell for a public key and also a
685 signature. Preliminary analysis with the NRL protocol analyzer
\cite{meadows96
}
686 shows the above protocol to be secure (including providing PFS) under the
687 traditional Dolev-Yao model.
689 \subsubsection{Relay cells
}
690 Once Alice has established the circuit (so she shares a key with each
691 OR on the circuit), she can send relay cells.
692 The stream ID in the relay header indicates to which stream the cell belongs.
693 A relay cell can be addressed to any of the ORs on the circuit. To
694 construct a relay cell addressed to a given OR, Alice iteratively
695 encrypts the cell payload (that is, the relay header and payload)
696 with the symmetric key of each hop up to that OR. Then, at each hop
697 down the circuit, the OR decrypts the cell payload and checks whether
698 it recognizes the stream ID. A stream ID is recognized either if it
699 is an already open stream at that OR, or if it is equal to zero. The
700 zero stream ID is treated specially, and is used for control messages,
701 e.g. starting a new stream. If the stream ID is unrecognized, the OR
702 passes the relay cell downstream. This
\emph{leaky pipe
} circuit topology
703 allows Alice's streams to exit at different ORs on a single circuit.
704 Alice may choose different exit points because of their exit policies,
705 or to keep the ORs from knowing that two streams
706 originate at the same person.
708 To tear down a circuit, Alice sends a destroy control cell. Each OR
709 in the circuit receives the destroy cell, closes all open streams on
710 that circuit, and passes a new destroy cell forward. But since circuits
711 can be built incrementally, they can also be torn down incrementally:
712 Alice can instead send a relay truncate cell to a node along the circuit. That
713 node will send a destroy cell forward, and reply with an acknowledgment
714 (relay truncated). Alice might truncate her circuit so she can extend it
715 to different nodes without signaling to the first few nodes (or somebody
716 observing them) that she is changing her circuit. That is, nodes in the
717 middle are not even aware that the circuit was truncated, because the
718 relay cells are encrypted. Similarly, if a node on the circuit goes down,
719 the adjacent node can send a relay truncated back to Alice. Thus the
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.
905 \subsubsection{Needs more research
}
907 We don't need to reimplement full TCP windows (with sequence numbers,
908 the ability to drop cells when we're full and retransmit later, etc),
909 because the TCP streams already guarantee in-order delivery of each
910 cell. But we need to investigate further the effects of the current
911 parameters on throughput and latency, while also keeping privacy in mind;
912 see Section~
\ref{sec:maintaining-anonymity
} for more discussion.
914 \Section{Other design decisions
}
916 \SubSection{Resource management and denial-of-service prevention
}
919 Providing Tor as a public service provides many opportunities for an
920 attacker to mount denial-of-service attacks against the network. While
921 flow control and rate limiting (discussed in
922 Section~
\ref{subsec:congestion
}) prevent users from consuming more
923 bandwidth than routers are willing to provide, opportunities remain for
925 consume more network resources than their fair share, or to render the
926 network unusable for other users.
928 First of all, there are a number of CPU-consuming denial-of-service
929 attacks wherein an attacker can force an OR to perform expensive
930 cryptographic operations. For example, an attacker who sends a
931 \emph{create
} cell full of junk bytes can force an OR to perform an RSA
932 decrypt. Similarly, an attacker can
933 fake the start of a TLS handshake, forcing the OR to carry out its
934 (comparatively expensive) half of the handshake at no real computational
935 cost to the attacker.
937 Several approaches exist to address these attacks. First, ORs may
938 demand proof-of-computation tokens
\cite{hashcash
} before beginning new
939 TLS handshakes or accepting
\emph{create
} cells. So long as these
940 tokens are easy to verify and computationally expensive to produce, this
941 approach limits the DoS attack multiplier. Additionally, ORs may limit
942 the rate at which they accept create cells and TLS connections, so that
943 the computational work of processing them does not drown out the (comparatively
944 inexpensive) work of symmetric cryptography needed to keep cells
945 flowing. This rate limiting could, however, allows an attacker
946 to slow down other users when they build new circuits.
948 % What about link-to-link rate limiting?
950 Attackers also have an opportunity to attack the Tor network by mounting
951 attacks on its hosts and network links. Disrupting a single circuit or
952 link breaks all currently open streams passing along that part of the
953 circuit. Indeed, this same loss of service occurs when a router crashes
954 or its operator restarts it. The current Tor design treats such attacks
955 as intermittent network failures, and depends on users and applications
956 to respond or recover as appropriate. A future design could use an
957 end-to-end TCP-like acknowledgment protocol, so that no streams are
958 lost unless the entry or exit point itself is disrupted. This solution
959 would require more buffering at the network edges, however, and the
960 performance and anonymity implications from this extra complexity still
961 require investigation.
963 \SubSection{Exit policies and abuse
}
964 \label{subsec:exitpolicies
}
966 Exit abuse is a serious barrier to wide-scale Tor deployment. Anonymity
967 presents would-be vandals and abusers with an opportunity to hide
968 the origins of their activities. Attackers can harm the Tor network by
969 implicating exit servers for their abuse. Also, applications that commonly
970 use IP-based authentication (such as institutional mail or web servers)
971 can be fooled by the fact that anonymous connections appear to originate
974 We stress that Tor does not enable any new class of abuse. Spammers and
975 other attackers already have access to thousands of misconfigured systems
976 worldwide, and the Tor network is far from the easiest way to launch
977 these antisocial or illegal attacks. But because the onion routers can
978 easily be mistaken for the originators of the abuse, and the volunteers
979 who run them may not want to deal with the hassle of repeatedly explaining
980 anonymity networks, we must block or limit attacks and other abuse that
981 travel through the Tor network.
983 To mitigate abuse issues, in Tor, each onion router's
\emph{exit policy
}
984 describes to which external addresses and ports the router will permit
985 stream connections. On one end of the spectrum are
\emph{open exit
}
986 nodes that will connect anywhere. On the other end are
\emph{middleman
}
987 nodes that only relay traffic to other Tor nodes, and
\emph{private exit
}
988 nodes that only connect to a local host or network. Using a private
989 exit (if one exists) is a more secure way for a client to connect to a
990 given host or network---an external adversary cannot eavesdrop traffic
991 between the private exit and the final destination, and so is less sure of
992 Alice's destination and activities. Most onion routers will function as
993 \emph{restricted exits
} that permit connections to the world at large,
994 but prevent access to certain abuse-prone addresses and services. In
995 general, nodes can require a variety of forms of traffic authentication
998 %The abuse issues on closed (e.g. military) networks are different
999 %from the abuse on open networks like the Internet. While these IP-based
1000 %access controls are still commonplace on the Internet, on closed networks,
1001 %nearly all participants will be honest, and end-to-end authentication
1002 %can be assumed for important traffic.
1004 Many administrators will use port restrictions to support only a
1005 limited set of well-known services, such as HTTP, SSH, or AIM.
1006 This is not a complete solution, since abuse opportunities for these
1007 protocols are still well known. Nonetheless, the benefits are real,
1008 since administrators seem used to the concept of port
80 abuse not
1009 coming from the machine's owner.
1011 A further solution may be to use proxies to clean traffic for certain
1012 protocols as it leaves the network. For example, much abusive HTTP
1013 behavior (such as exploiting buffer overflows or well-known script
1014 vulnerabilities) can be detected in a straightforward manner.
1015 Similarly, one could run automatic spam filtering software (such as
1016 SpamAssassin) on email exiting the OR network.
1018 ORs may also choose to rewrite exiting traffic in order to append
1019 headers or other information to indicate that the traffic has passed
1020 through an anonymity service. This approach is commonly used
1021 by email-only anonymity systems. When possible, ORs can also
1022 run on servers with hostnames such as
{\it anonymous
}, to further
1023 alert abuse targets to the nature of the anonymous traffic.
1025 A mixture of open and restricted exit nodes will allow the most
1026 flexibility for volunteers running servers. But while many
1027 middleman nodes help provide a large and robust network,
1028 having only a small number of exit nodes reduces the number of nodes
1029 an adversary needs to monitor for traffic analysis, and places a
1030 greater burden on the exit nodes. This tension can be seen in the JAP
1031 cascade model, wherein only one node in each cascade needs to handle
1032 abuse complaints---but an adversary only needs to observe the entry
1033 and exit of a cascade to perform traffic analysis on all that
1034 cascade's users. The Hydra model (many entries, few exits) presents a
1035 different compromise: only a few exit nodes are needed, but an
1036 adversary needs to work harder to watch all the clients; see
1037 Section~
\ref{sec:conclusion
}.
1039 Finally, we note that exit abuse must not be dismissed as a peripheral
1040 issue: when a system's public image suffers, it can reduce the number
1041 and diversity of that system's users, and thereby reduce the anonymity
1042 of the system itself. Like usability, public perception is also a
1043 security parameter. Sadly, preventing abuse of open exit nodes is an
1044 unsolved problem, and will probably remain an arms race for the
1045 forseeable future. The abuse problems faced by Princeton's CoDeeN
1046 project
\cite{darkside
} give us a glimpse of likely issues.
1048 \SubSection{Directory Servers
}
1049 \label{subsec:dirservers
}
1051 First-generation Onion Routing designs
\cite{freedom2-arch,or-jsac98
} used
1052 in-band network status updates: each router flooded a signed statement
1053 to its neighbors, which propagated it onward. But anonymizing networks
1054 have different security goals than typical link-state routing protocols.
1055 For example, delays (accidental or intentional)
1056 that can cause different parts of the network to have different pictures
1057 of link-state and topology are not only inconvenient---they give
1058 attackers an opportunity to exploit differences in client knowledge.
1059 We also worry about attacks to deceive a
1060 client about the router membership list, topology, or current network
1061 state. Such
\emph{partitioning attacks
} on client knowledge help an
1062 adversary with limited resources to efficiently deploy those resources
1063 when attacking a target.
1065 Instead of flooding, Tor uses a small group of redundant, well-known
1066 directory servers to track changes in network topology and node state,
1067 including keys and exit policies. Directory servers are a small group
1068 of well-known, mostly-trusted onion routers. They listen on a
1069 separate port as an HTTP server, so that participants can fetch
1070 current network state and router lists (a
\emph{directory
}), and so
1071 that other onion routers can upload their router descriptors. Onion
1072 routers now periodically publish signed statements of their state to
1073 the directories only. The directories themselves combine this state
1074 information with their own views of network liveness, and generate a
1075 signed description of the entire network state whenever its contents
1076 have changed. Client software is pre-loaded with a list of the
1077 directory servers and their keys, and uses this information to
1078 bootstrap each client's view of the network.
1080 When a directory receives a signed statement from and onion router, it
1081 recognizes the onion router by its identity (signing) key.
1082 Directories do not automatically advertise ORs that they do not
1083 recognize. (If they did, an adversary could take over the network by
1084 creating many servers
\cite{sybil
}.) Instead, new nodes must be
1085 approved by the directory administrator before they are included.
1086 Mechanisms for automated node approval are an area of active research,
1087 and are discussed more in section~
\ref{sec:maintaining-anonymity
}.
1089 Of course, a variety of attacks remain. An adversary who controls a
1090 directory server can track certain clients by providing different
1091 information---perhaps by listing only nodes under its control
1092 as working, or by informing only certain clients about a given
1093 node. Moreover, an adversary without control of a directory server can
1094 still exploit differences among client knowledge. If Eve knows that
1095 node $M$ is listed on server $D_1$ but not on $D_2$, she can use this
1096 knowledge to link traffic through $M$ to clients who have queried $D_1$.
1098 Thus these directory servers must be synchronized and redundant. The
1099 software is distributed with the signature public key of each directory
1100 server, and directories must be signed by a threshold of these keys.
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 who the
1105 directory servers are. Second, Mixminion needs to predict node
1106 behavior, whereas Tor only needs a threshold consensus of the current
1107 state of the network.
1108 % Cite dir-spec or dir-agreement?
1110 Tor directory servers build a consensus directory through a simple
1111 four-round broadcast protocol. In round one, each server dates and
1112 signs its current opinion, and broadcasts it to the other directory
1113 servers; then in round two, each server rebroadcasts all the signed
1114 opinions it has received. At this point all directory servers check
1115 to see whether any server has signed multiple opinions in the same
1116 period. If so, the server is either broken or cheating, so the protocol
1117 stops and notifies the administrators, who either remove the cheater
1118 or wait for the broken server to be fixed. If there are no
1119 discrepancies, each directory server then locally computes an algorithm
1121 on the set of opinions, resulting in a uniform shared directory. In
1122 round three servers sign this directory and broadcast it; and finally
1123 in round four the servers rebroadcast the directory and all the
1124 signatures. If any directory server drops out of the network, its
1125 signature is not included on the final directory.
1127 The rebroadcast steps ensure that a directory server is heard by
1128 either all of the other servers or none of them, assuming that any two
1129 directory servers can talk directly, or via a third directory server (some of the
1130 links between directory servers may be down). Broadcasts are feasible
1131 because there are relatively few directory servers (currently
3, but we expect
1132 to transition to
9 as the network scales). The actual local algorithm
1133 for computing the shared directory is a straightforward threshold
1134 voting process: we include an OR if a majority of directory servers
1135 believe it to be good.
1137 To avoid attacks where a router connects to all the directory servers
1138 but refuses to relay traffic from other routers, the directory servers
1139 must build circuits and use them to anonymously test router reliability
1142 When Alice retrieves a consensus directory, she uses it if it
1143 is signed by a majority of the directory servers she knows.
1145 Using directory servers rather than flooding provides simplicity and
1146 flexibility. For example, they don't complicate the analysis when we
1147 start experimenting with non-clique network topologies. And because
1148 the directories are signed, they can be cached by other onion routers.
1149 Thus directory servers are not a performance
1150 bottleneck when we have many users, and do not aid traffic analysis by
1151 forcing clients to periodically announce their existence to any
1153 % Mention Hydra as an example of non-clique topologies. -NM, from RD
1156 \Section{Rendezvous points: location privacy
}
1157 \label{sec:rendezvous
}
1159 Rendezvous points are a building block for
\emph{location-hidden
1160 services
} (also known as ``responder anonymity'') in the Tor
1161 network. Location-hidden services allow a server Bob to offer a TCP
1162 service, such as a webserver, without revealing the IP of his service.
1163 Besides allowing Bob to provided services anonymously, location
1164 privacy also seeks to provide some protection against distributed DoS attacks:
1165 attackers are forced to attack the onion routing network as a whole
1166 rather than just Bob's IP.
1168 Our design for location-hidden servers has the following properties.
1169 \textbf{Flood-proof:
} An attacker should not be able to flood Bob
1170 with traffic simply by sending many requests to talk to Bob. Thus,
1171 Bob needs a way to filter incoming requests.
\textbf{Robust:
} Bob
1172 should be able to maintain a long-term pseudonymous identity even
1173 in the presence of router failure. Thus, Bob's service must not be
1174 tied to a single OR, and Bob must be able to tie his service to new
1175 ORs.
\textbf{Smear-resistant:
} An attacker should not be able to use
1176 rendezvous points to smear an OR. That is, if a social attacker tries
1177 to host a location-hidden service that is illegal or disreputable, it
1178 should not appear---even to a casual observer---that the OR is hosting
1179 that service.
\textbf{Application-transparent:
} Although we are willing to
1180 require users to run special software to access location-hidden servers,
1181 we are not willing to require them to modify their applications.
1183 \subsection{Rendezvous design
}
1184 We provide location-hiding for Bob by allowing him to advertise
1185 several onion routers (his
\emph{Introduction Points
}) as his public
1186 location. (He may do this on any robust efficient distributed
1187 key-value lookup system with authenticated updates, such as CFS
1188 \cite{cfs:sosp01
}\footnote{
1189 Each onion router could run a node in this lookup
1190 system; also note that as a stopgap measure, we can start by running a
1191 simple lookup system on the directory servers.
})
1192 Alice, the client, chooses a node for her
1193 \emph{Meeting Point
}. She connects to one of Bob's introduction
1194 points, informs him about her rendezvous point, and then waits for him
1195 to connect to the rendezvous point. This extra level of indirection
1196 helps Bob's introduction points avoid problems associated with serving
1197 unpopular files directly, as could occur, for example, if Bob chooses
1198 an introduction point in Texas to serve anti-ranching propaganda,
1199 or if Bob's service tends to get attacked by network vandals.
1200 The extra level of indirection also allows Bob to respond to some requests
1203 The steps of a rendezvous as follows. These steps are performed on
1204 behalf of Alice and Bob by their local onion proxies, which they both
1205 must run; application integration is described more fully below.
1207 \item Bob chooses some introduction ppoints, and advertises them via
1208 CFS (or some other distributed key-value publication system).
1209 \item Bob establishes a Tor virtual circuit to each of his
1210 Introduction Points, and waits.
1211 \item Alice learns about Bob's service out of band (perhaps Bob told her,
1212 or she found it on a website). She looks up the details of Bob's
1214 \item Alice chooses an OR to serve as a Rendezvous Point (RP) for this
1215 transaction. She establishes a virtual circuit to her RP, and
1216 tells it to wait for connections.
[XXX how?
]
1217 \item Alice opens an anonymous stream to one of Bob's Introduction
1218 Points, and gives it message (encrypted for Bob) which tells him
1219 about herself, her chosen RP, and the first half of an ephemeral
1220 key handshake. The Introduction Point sends the message to Bob.
1221 \item Bob may decide to ignore Alice's request.
[XXX Based on what?
]
1222 Otherwise, he creates a new virtual circuit to Alice's RP, and
1223 authenticates himself.
[XXX how?
]
1224 \item If the authentication is successful, the RP connects Alice's
1225 virtual circuit to Bob's. Note that RP can't recognize Alice,
1226 Bob, or the data they transmit (they share a session key).
1227 \item Alice now sends a Begin cell along the circuit. It arrives at Bob's
1228 onion proxy. Bob's onion proxy connects to Bob's webserver.
1229 \item An anonymous stream has been established, and Alice and Bob
1230 communicate as normal.
1233 [XXX We need to modify the above to refer people down to these next
1236 When establishing an introduction point, Bob provides the onion router
1237 with a public ``introduction'' key. The hash of this public key
1238 identifies a unique service, and (since Bob is required to sign his
1239 messages) prevents anybody else from usurping Bob's introduction point
1240 in the future. Bob uses the same public key when establishing the other
1241 introduction points for that service.
1243 The message that Alice gives the introduction point includes a hash of Bob's
1244 public key to identify the service, an optional initial authentication
1245 token (the introduction point can do prescreening, eg to block replays),
1246 and (encrypted to Bob's public key) the location of the rendezvous point,
1247 a rendezvous cookie Bob should tell RP so he gets connected to
1248 Alice, an optional authentication token so Bob can choose whether to respond,
1249 and the first half of a DH key exchange. When Bob connects to RP
1250 and gets connected to Alice's pipe, his first cell contains the
1251 other half of the DH key exchange.
1253 The authentication tokens can be used to provide selective access to users
1254 proportional to how important it is that they main uninterrupted access
1255 to the service. During normal situations, Bob's service might simply be
1256 offered directly from mirrors; Bob can also give out authentication cookies
1257 to high-priority users. If those mirrors are knocked down by
1258 distributed DoS attacks,
1259 those users can switch to accessing Bob's service via the Tor
1262 \SubSection{Integration with user applications
}
1264 For each service Bob offers, he configures his local onion proxy to know
1265 the local IP and port of the server, a strategy for authorizing Alices,
1266 and a public key. Bob publishes
1267 the public key, an expiration
1268 time (``not valid after''), and the current introduction points for
1270 service into CFS, all indexed by the hash of the public key
1271 Note that Bob's webserver is unmodified, and doesn't even know
1272 that it's hidden behind the Tor network.
1274 Because Alice's applications must work unchanged, her client interface
1275 remains a SOCKS proxy. Thus we must encode all of the necessary
1276 information into the fully qualified domain name Alice uses when
1277 establishing her connections. Location-hidden services use a virtual
1278 top level domain called `.onion': thus hostnames take the form
1279 x.y.onion where x is the authentication cookie, and y encodes the hash
1280 of PK. Alice's onion proxy examines hostnames and recognizes when
1281 they're destined for a hidden server. If so, it decodes the PK and
1282 starts the rendezvous as described in the table above.
1284 \subsection{Previous rendezvous work
}
1286 Ian Goldberg developed a similar notion of rendezvous points for
1287 low-latency anonymity systems
\cite{ian-thesis
}. His ``service tags''
1288 play the same role in his design as the hashes of services' public
1289 keys play in ours. We use public key hashes so that they can be
1290 self-authenticating, and so the client can recognize the same service
1291 with confidence later on. His design also differs from ours in the
1292 following ways: First, Goldberg suggests that the client should
1293 manually hunt down a current location of the service via Gnutella;
1294 whereas our use of CFS makes lookup faster, more robust, and
1295 transparent to the user. Second, in Tor the client and server
1296 negotiate ephemeral keys via Diffie-Hellman, so at no point in the
1297 path is the plaintext exposed. Third, our design tries to minimize the
1298 exposure associated with running the service, so as to make volunteers
1299 more willing to offer introduction and rendezvous point services.
1300 Tor's introduction points do not output any bytes to the clients, and
1301 the rendezvous points don't know the client, the server, or the data
1302 being transmitted. The indirection scheme is also designed to include
1303 authentication/authorization---if the client doesn't include the right
1304 cookie with its request for service, the server need not even
1305 acknowledge its existence.
1308 \label{sec:analysis
}
1310 In this section, we discuss how well Tor meets our stated design goals
1311 and its resistance to attacks.
1313 \SubSection{Meeting Basic Goals
}
1314 % None of these seem to say very much. Should this subsection be removed?
1316 \item [Basic Anonymity:
] Because traffic is encrypted, changing in
1317 appearance, and can flow from anywhere to anywhere within the
1318 network, a simple observer that cannot see both the initiator
1319 activity and the corresponding activity where the responder talks to
1320 the network will not be able to link the initiator and responder.
1321 Nor is it possible to directly correlate any two communication
1322 sessions as coming from a single source without additional
1323 information. Resistance to more sophisticated anonymity threats is
1325 \item[Deployability:
] Tor requires no specialized hardware. Tor
1326 requires no kernel modifications; it runs in user space (currently
1327 on Linux, various BSDs, and Windows). All of these imply a low
1328 technical barrier to running a Tor node. There is an assumption that
1329 Tor nodes have good relatively persistent net connectivity
1330 (currently
T1 or better);
1331 % Is that reasonable to say? We haven't really discussed it -P.S.
1332 % Roger thinks otherwise; he will fix this. -NM
1333 however, there is no padding overhead, and operators can limit
1334 bandwidth on any link. Tor is freely available under the modified
1335 BSD license, and operators are able to choose their own exit
1336 policies, thus reducing legal and social barriers to
1339 \item[Usability:
] As noted, Tor runs in user space. So does the onion
1340 proxy, which is comparatively easy to install and run. SOCKS-aware
1341 applications require nothing more than to be pointed at the onion
1342 proxy; other applications can be redirected to use SOCKS for their
1343 outgoing TCP connections by drop-in libraries such as tsocks.
1345 \item[Flexibility:
] Tor's design and implementation is fairly modular,
1347 for example, a scalable P2P replacement for the directory servers
1348 would not substantially impact other aspects of the system. Tor
1349 runs on top of TCP, so design options that could not easily do so
1350 would be difficult to test on the current network. However, most
1351 low-latency protocols are designed to run over TCP. We are currently
1352 discussing with the designers of MorphMix interoperability of the
1353 two systems, which seems to be relatively straightforward. This will
1354 allow testing and direct comparison of the two rather different
1356 % Do we want to say this? I don't think we should talk about this
1357 % kind of discussion till we have more positive results.
1359 \item[Simple design:
] Tor opts for practicality when there is no
1360 clear resolution of anonymity tradeoffs or practical means to
1361 achieve resolution. Thus, we do not currently pad or mix; although
1362 it would be easy to add either of these. Indeed, our system allows
1363 long-range and variable padding if this should ever be shown to have
1364 a clear advantage. Similarly, we do not currently attempt to
1365 resolve such issues as Sybil attacks to dominate the network except
1366 by such direct means as personal familiarity of director operators
1367 with all node operators.
1370 \SubSection{Attacks and Defenses
}
1373 Below we summarize a variety of attacks, and discuss how well our
1374 design withstands them.
1376 \subsubsection*
{Passive attacks
}
1378 \item \emph{Observing user traffic patterns.
} Observations of connection
1379 between an end user and a first onion router will not reveal to whom
1380 the user is connecting or what information is being sent. It will
1381 reveal patterns of user traffic (both sent and received). Simple
1382 profiling of user connection patterns is not generally possible,
1383 however, because multiple application connections (streams) may be
1384 operating simultaneously or in series over a single circuit. Thus,
1385 further processing is necessary to try to discern even these usage
1388 \item \emph{Observing user content.
} At the user end, content is
1389 encrypted; however, connections from the network to arbitrary
1390 websites may not be. Further, a responding website may itself be
1391 considered an adversary. Filtering content is not a primary goal of
1392 Onion Routing; nonetheless, Tor can directly make use of Privoxy and
1393 related filtering services via SOCKS and thus anonymize their
1394 application data streams.
1396 \item \emph{Option distinguishability.
} Configuration options can be a
1397 source of distinguishable patterns. In general there is economic
1398 incentive to allow preferential services
\cite{econymics
}, and some
1399 degree of configuration choice is a factor in attracting large
1400 numbers of users to provide anonymity. So far, however, we have
1401 not found a compelling use case in Tor for any client-configurable
1402 options. Thus, clients are currently distinguishable only by their
1405 \item \emph{End-to-end Timing correlation.
} Tor only minimally hides
1406 end-to-end timing correlations. If an attacker can watch patterns of
1407 traffic at the initiator end and the responder end, then he will be
1408 able to confirm the correspondence with high probability. The
1409 greatest protection currently against such confirmation is if the
1410 connection between the onion proxy and the first Tor node is hidden,
1411 possibly because it is local or behind a firewall. This approach
1412 requires an observer to separate traffic originating the onion
1413 router from traffic passes through it. We still do not, however,
1414 predict this approach to be a large problem for an attacker who can
1415 observe traffic at both ends of an application connection.
1417 \item \emph{End-to-end Size correlation.
} Simple packet counting
1418 without timing consideration will also be effective in confirming
1419 endpoints of a connection through Onion Routing; although slightly
1420 less so. This is because, even without padding, the leaky pipe
1421 topology means different numbers of packets may enter one end of a
1422 circuit than exit at the other.
1424 \item \emph{Website fingerprinting.
} All the above passive
1425 attacks that are at all effective are traffic confirmation attacks.
1426 This puts them outside our general design goals. There is also
1427 a passive traffic analysis attack that is potentially effective.
1428 Instead of searching exit connections for timing and volume
1429 correlations it is possible to build up a database of
1430 ``fingerprints'' containing file sizes and access patterns for a
1431 large numbers of interesting websites. If one now wants to
1432 monitor the activity of a user, it may be possible to confirm a
1433 connection to a site simply by consulting the database. This attack has
1434 been shown to be effective against SafeWeb
\cite{hintz-pet02
}. Onion
1435 Routing is not as vulnerable as SafeWeb to this attack: There is the
1436 possibility that multiple streams are exiting the circuit at
1437 different places concurrently. Also, fingerprinting will be limited to
1438 the granularity of cells, currently
256 bytes. Larger cell sizes
1439 and/or minimal padding schemes that group websites into large sets
1440 are possible responses. But this remains an open problem. Link
1441 padding or long-range dummies may also make fingerprints harder to
1443 such fingerprinting should not be confused with the latency attacks
1444 of
\cite{back01
}. Those require a fingerprint of the latencies of
1445 all circuits through the network, combined with those from the
1446 network edges to the targeted user and the responder website. While
1447 these are in principal feasible and surprises are always possible,
1448 these constitute a much more complicated attack, and there is no
1449 current evidence of their practicality.)
1451 \item \emph{Content analysis.
} Tor explicitly provides no content
1452 rewriting for any protocol at a higher level than TCP. When
1453 protocol cleaners are available, however (as Privoxy is for HTTP),
1454 Tor can integrate them in order to address these attacks.
1458 \subsubsection*
{Active attacks
}
1460 \item \emph{Key compromise.
} We consider the impact of a compromise
1461 for each type of key in turn, from the shortest- to the
1462 longest-lived. If a circuit session key is compromised, the
1463 attacker can unwrap a single layer of encryption from the relay
1464 cells traveling along that circuit. (Only nodes on the circuit can
1465 see these cells.) If a TLS session key is compromised, an attacker
1466 can view all the cells on TLS connection until the key is
1467 renegotiated. (These cells are themselves encrypted.) If a TLS
1468 private key is compromised, the attacker can fool others into
1469 thinking that he is the affected OR, but still cannot accept any
1470 connections. If an onion private key is compromised, the attacker
1471 can impersonate the OR in circuits, but only if the attacker has
1472 also compromised the OR's TLS private key, or is running the
1473 previous OR in the circuit. (This compromise affects newly created
1474 circuits, but because of perfect forward secrecy, the attacker
1475 cannot hijack old circuits without compromising their session keys.)
1476 In any case, an attacker can only take advantage of a compromise in
1477 these mid-term private keys until they expire. Only by
1478 compromising a node's identity key can an attacker replace that
1479 node indefinitely, by sending new forged mid-term keys to the
1480 directories. Finally, an attacker who can compromise a
1481 \emph{directory's
} identity key can influence every client's view
1482 of the network---but only to the degree made possible by gaining a
1483 vote with the rest of the the directory servers.
1485 \item \emph{Iterated compromise.
} A roving adversary who can
1486 compromise ORs (by system intrusion, legal coersion, or extralegal
1487 coersion) could march down length of a circuit compromising the
1488 nodes until he reaches the end. Unless the adversary can complete
1489 this attack within the lifetime of the circuit, however, the ORs
1490 will have discarded the necessary information before the attack can
1491 be completed. (Thanks to the perfect forward secrecy of session
1492 keys, the attacker cannot cannot force nodes to decrypt recorded
1493 traffic once the circuits have been closed.) Additionally, building
1494 circuits that cross jurisdictions can make legal coercion
1495 harder---this phenomenon is commonly called ``jurisdictional
1496 arbitrage.'' The JAP project recently experienced this issue, when
1497 the German government successfully ordered them to add a backdoor to
1501 \item \emph{Run a recipient.
} By running a Web server, an adversary
1502 trivially learns the timing patterns of those connecting to it, and
1503 can introduce arbitrary patterns in its responses. This can greatly
1504 facilitate end-to-end attacks: If the adversary can induce certain
1505 users to connect to connect to his webserver (perhaps by providing
1506 content targeted at those users), she now holds one end of their
1507 connection. Additonally, here is a danger that the application
1508 protocols and associated programs can be induced to reveal
1509 information about the initiator. This is not directly in Onion
1510 Routing's protection area, so we are dependent on Privoxy and
1511 similar protocol cleaners to solve the problem.
1513 \item \emph{Run an onion proxy.
} It is expected that end users will
1514 nearly always run their own local onion proxy. However, in some
1515 settings, it may be necessary for the proxy to run
1516 remotely---typically, in an institutional setting where it was
1517 necessary to monitor the activity of those connecting to the proxy.
1518 The drawback, of course, is that if the onion proxy is compromised,
1519 then all future connections through it are completely compromised.
1521 \item \emph{DoS non-observed nodes.
} An observer who can observe some
1522 of the Tor network can increase the value of this traffic analysis
1523 if it can attack non-observed nodes to shut them down, reduce
1524 their reliability, or persuade users that they are not trustworthy.
1525 The best defense here is robustness.
1527 \item \emph{Run a hostile node.
} In addition to the abilties of a
1528 local observer, an isolated hostile node can create circuits through
1529 itself, or alter traffic patterns, in order to affect traffic at
1530 other nodes. Its ability to directly DoS a neighbor is now limited
1531 by bandwidth throttling. Nonetheless, in order to compromise the
1532 anonymity of the endpoints of a circuit by its observations, a
1533 hostile node is only significant if it is immediately adjacent to
1536 \item \emph{Run multiple hostile nodes.
} If an adversary is able to
1537 run multiple ORs, and is able to persuade the directory servers
1538 that those ORs are trustworthy and independant, then occasionally
1539 some user will choose one of those ORs for the start and another of
1540 those ORs as the end of a circuit. When this happens, the user's
1541 anonymity is compromised for those circuits. If an adversary can
1542 control $m$ out of $N$ nodes, he should be able to correlate at most
1543 $
\frac{m
}{N
}$ of the traffic in this way---although an adersary
1544 could possibly attract a disproportionately large amount of traffic
1545 by running an exit node with an unusually permisssive exit policy.
1547 \item \emph{Compromise entire path.
} Anyone compromising both
1548 endpoints of a circuit can confirm this with high probability. If
1549 the entire path is compromised, this becomes a certainty; however,
1550 the added benefit to the adversary of such an attack is small in
1551 relation to the difficulty.
1553 \item \emph{Run a hostile directory server.
} Directory servers control
1554 admission to the network. However, because the network directory
1555 must be signed by a majority of servers, the threat of a single
1556 hostile server is minimized.
1558 \item \emph{Selectively DoS a Tor node.
} As noted, neighbors are
1559 bandwidth limited; however, it is possible to open up sufficient
1560 numbers of circuits that converge at a single onion router to
1561 overwhelm its network connection, its ability to process new
1564 %OK so I noticed that twins are completely removed from the paper above,
1565 % but it's after 5 so I'll leave that problem to you guys. -PS
1567 \item \emph{Introduce timing into messages.
} This is simply a stronger
1568 version of passive timing attacks already discussed above.
1570 \item \emph{Tagging attacks.
} A hostile node could try to ``tag'' a
1571 cell by altering it. This would render it unreadable, but if the
1572 connection is, for example, an unencrypted request to a Web site,
1573 the garbled content coming out at the appropriate time could confirm
1574 the association. However, integrity checks on cells prevent
1575 this attack from succeeding.
1577 \item \emph{Replace contents of unauthenticated protocols.
} When a
1578 relaying an unauthenticated protocol like HTTP, a hostile exit node
1579 can impersonate the target server. Thus, whenever possible, clients
1580 should prefer protocols with end-to-end authentication.
1582 \item \emph{Replay attacks.
} Some anonymity protocols are vulnerable
1583 to replay attacks. Tor is not; replaying one side of a handshake
1584 will result in a different negotiated session key, and so the rest
1585 of the recorded session can't be used.
1586 % ``NonSSL Anonymizer''?
1588 \item \emph{Smear attacks.
} An attacker could use the Tor network to
1589 engage in socially dissapproved acts, so as to try to bring the
1590 entire network into disrepute and get its operators to shut it down.
1591 Exit policies can help reduce the possibilities for abuse, but
1592 ultimately, the network will require volunteers who can tolerate
1593 some political heat.
1595 \item \emph{Distribute hostile code.
} An attacker could trick users
1596 into running subverted Tor software that did not, in fact, anonymize
1597 their connections---or worse, trick ORs into running weakened
1598 software that provided users with less anonymity. We address this
1599 problem (but do not solve it completely) by signing all Tor releases
1600 with an official public key, and including an entry the directory
1601 describing which versions are currently believed to be secure. To
1602 prevent an attacker from subverting the official release itself
1603 (through threats, bribery, or insider attacks), we provide all
1604 releases in source code form, encourage source audits, and
1605 frequently warn our users never to trust any software (even from
1606 us!) that comes without source.
1609 \subsubsection*
{Directory attacks
}
1611 \item \emph{Destroy directory servers.
} If a single directory
1612 server drops out of operation, the others still arrive at a final
1613 directory. So long as any directory servers remain in operation,
1614 they will still broadcast their views of the network and generate a
1615 consensus directory. (If more than half are destroyed, this
1616 directory will not, however, have enough signatures for clients to
1617 use it automatically; human intervention will be necessary for
1618 clients to decide whether to trust the resulting directory.)
1620 \item \emph{Subvert a directory server.
} By taking over a directory
1621 server, an attacker can influence (but not control) the final
1622 directory. Since ORs are included or excluded by majority vote,
1623 the corrupt directory can at worst cast a tie-breaking vote to
1624 decide whether to include marginal ORs. How often such marginal
1625 cases will occur in practice, however, remains to be seen.
1627 \item \emph{Subvert a majority of directory servers.
} If the
1628 adversary controls more than half of the directory servers, he can
1629 decide on a final directory, and thus can include as many
1630 compromised ORs in the final directory as he wishes. Other than
1631 trying to ensure that directory server operators are truly
1632 independent and resistant to attack, Tor does not address this
1635 \item \emph{Encourage directory server dissent.
} The directory
1636 agreement protocol requires that directory server operators agree on
1637 the list of directory servers. An adversary who can persuade some
1638 of the directory server operators to distrust one another could
1639 split the quorum into mutually hostile camps, thus partitioning
1640 users based on which directory they used. Tor does not address
1643 \item \emph{Trick the directory servers into listing a hostile OR.
}
1644 Our threat model explicitly assumes directory server operators will
1645 be able to filter out most hostile ORs. If this is not true, an
1646 attacker can flood the directory with compromised servers.
1648 \item \emph{Convince the directories that a malfunctioning OR is
1649 working.
} In the current Tor implementation, directory servers
1650 assume that if they can start a TLS connection to an an OR, that OR
1651 must be running correctly. It would be easy for a hostile OR to
1652 subvert this test by only accepting TLS connections from ORs, and
1653 ignoring all cells. Thus, directory servers must actively test ORs
1654 by building circuits and streams as appropriate. The benefits and
1655 hazards of a similar approach are discussed in
\cite{mix-acc
}.
1659 \subsubsection*
{Attacks against rendezvous points
}
1661 \item \emph{Make many introduction requests.
} An attacker could
1662 attempt to deny Bob service by flooding his Introduction Point with
1663 requests. Because the introduction point can block requests that
1664 lack authentication tokens, however, Bob can restrict the volume of
1665 requests he receives, or require a certain amount of computation for
1666 every request he receives.
1668 \item \emph{Attack an introduction point.
} An attacker could try to
1669 disrupt a location-hidden service by disabling its introduction
1670 point. But because a service's identity is attached to its public
1671 key, not its introduction point, the service can simply re-advertise
1672 itself at a different introduction point.
1674 \item \emph{Compromise an introduction point.
} If an attacker controls
1675 an introduction point for a service, it can flood the service with
1676 introduction requests, or prevent valid introduction requests from
1677 reaching the hidden server. The server will notice a flooding
1678 attempt if it receives many introduction requests. To notice
1679 blocking of valid requests, however, the hidden server should
1680 periodically test the introduction point by sending its introduction
1681 requests, and making sure it receives them.
1683 \item \emph{Compromise a rendezvous point.
} Controlling a rendezvous
1684 point gains an attacker no more than controlling any other OR along
1685 a circuit, since all data passing along the rendezvous is protected
1686 by the session key shared by the client and server.
1691 \Section{Open Questions in Low-latency Anonymity
}
1692 \label{sec:maintaining-anonymity
}
1694 % There must be a better intro than this! -NM
1695 In addition to the open problems discussed in
1696 section~
\ref{subsec:non-goals
}, many other questions remain to be
1697 solved by future research before we can be truly confident that we
1698 have built a secure low-latency anonymity service.
1700 Many of these open issues are questions of balance. For example,
1701 how often should users rotate to fresh circuits? Too-frequent
1702 rotation is inefficient and expensive, but too-infrequent rotation
1703 makes the user's traffic linkable. Instead of opening a fresh
1704 circuit; clients can also limit linkability exit from a middle point
1705 of the circuit, or by truncating and re-extending the circuit, but
1706 more analysis is needed to determine the proper trade-off.
1707 [XXX mention predecessor attacks?
]
1709 A similar question surrounds timing of directory operations:
1710 how often should directories be updated? With too-infrequent
1711 updates clients receive an inaccurate picture of the network; with
1712 too-frequent updates the directory servers are overloaded.
1714 %do different exit policies at different exit nodes trash anonymity sets,
1715 %or not mess with them much?
1717 %% Why would they? By routing traffic to certain nodes preferentially?
1719 [XXX Choosing paths and path lengths: I'm not writing this bit till
1720 Arma's pathselection stuff is in. -NM
]
1722 %%%% Roger said that he'd put a path selection paragraph into section
1723 %%%% 4 that would replace this.
1725 %I probably should have noted that this means loops will be on at least
1726 %five hop routes, which should be rare given the distribution. I'm
1727 %realizing that this is reproducing some of the thought that led to a
1728 %default of five hops in the original onion routing design. There were
1729 %some different assumptions, which I won't spell out now. Note that
1730 %enclave level protections really change these assumptions. If most
1731 %circuits are just two hops, then just a single link observer will be
1732 %able to tell that two enclaves are communicating with high probability.
1733 %So, it would seem that enclaves should have a four node minimum circuit
1734 %to prevent trivial circuit insider identification of the whole circuit,
1735 %and three hop minimum for circuits from an enclave to some nonclave
1736 %responder. But then... we would have to make everyone obey these rules
1737 %or a node that through timing inferred it was on a four hop circuit
1738 %would know that it was probably carrying enclave to enclave traffic.
1739 %Which... if there were even a moderate number of bad nodes in the
1740 %network would make it advantageous to break the connection to conduct
1741 %a reformation intersection attack. Ahhh! I gotta stop thinking
1742 %about this and work on the paper some before the family wakes up.
1743 %On Sat, Oct 25, 2003 at 06:57:12AM -0400, Paul Syverson wrote:
1744 %> Which... if there were even a moderate number of bad nodes in the
1745 %> network would make it advantageous to break the connection to conduct
1746 %> a reformation intersection attack. Ahhh! I gotta stop thinking
1747 %> about this and work on the paper some before the family wakes up.
1748 %This is the sort of issue that should go in the 'maintaining anonymity
1749 %with tor' section towards the end. :)
1750 %Email from between roger and me to beginning of section above. Fix and move.
1752 Throughout this paper, we have assumed that end-to-end traffic
1753 analysis will immediately and automatically defeat a low-latency
1754 anonymity system. Even high-latency anonymity
1755 systems can be vulnerable to end-to-end traffic analysis, if the
1756 traffic volumes are high enough, and if users' habits are sufficiently
1757 distinct
\cite{limits-open,statistical-disclosure
}.
\emph{Can
1758 anything be donw to make low-latency systems resist these attacks as
1759 well as high-latency systems?
}
1760 Tor already makes some effort to conceal the starts and
1761 ends of streams by wrapping all long-range control commands in
1762 identical-looking relay cells, but more analysis is needed. Link
1763 padding could frustrate passive observers who count packets; long-range
1764 padding could work against observers who own the first hop in a
1765 circuit. But more research needs to be done in order to find an
1766 efficient and practical approach. Volunteers prefer not to run
1767 constant-bandwidth padding; but more sophisticated traffic shaping
1768 approaches remain somewhat unanalyzed.
[XXX is this so?
] Recent work
1769 on long-range padding
\cite{defensive-dropping
} shows promise. One
1770 could also try to reduce correlation in packet timing by batching and
1771 re-ordering packets, but it is unclear whether this could improve
1772 anonymity without introducing so much latency as to render the
1775 Even if passive timing attacks were wholly solved, active timing
1776 attacks would remain.
\emph{What can
1777 be done to address attackers who can introduce timing patterns into
1778 a user's traffic?
} [XXX mention likely approaches
]
1780 %%% I think we cover this by framing the problem as ``Can we make
1781 %%% end-to-end characteristics of low-latency systems as good as
1782 %%% those of high-latency systems?'' Eliminating long-term
1783 %%% intersection is a hard problem.
1785 %Even regardless of link padding from Alice to the cloud, there will be
1786 %times when Alice is simply not online. Link padding, at the edges or
1787 %inside the cloud, does not help for this.
1789 In order to scale to large numbers of users, and to prevent an
1790 attacker from observing the whole network at once, it may be necessary
1791 for low-latency anonymity systems to support far more servers than Tor
1792 currently anticipates. This introduces several issues. First, if
1793 approval by a centralized set of directory servers is no longer
1794 feasible, what mechanism should be used to prevent adversaries from
1795 signing up many spurious servers?
1796 Second, if clients can no longer have a complete
1797 picture of the network at all times, how can should they perform
1798 discovery while preventing attackers from manipulating or exploiting
1799 gaps in client knowledge? Third, if there are to many servers
1800 for every server to constantly communicate with every other, what kind
1801 of non-clique topology should the network use? Restricted-route
1802 topologies promise comparable anonymity with better scalability
1803 \cite{danezis-pets03
}, but whatever topology we choose, we need some
1804 way to keep attackers from manipulating their position within it.
1805 Fourth, since no centralized authority is tracking server reliability,
1806 How do we prevent unreliable servers from rendering the network
1807 unusable? Fifth, do clients receive so much anonymity benefit from
1808 running their own servers that we should expect them all to do so, or
1809 do we need to find another incentive structure to motivate them?
1810 (Tarzan and MorphMix present possible solutions.)
1812 [[ XXX how to approve new nodes (advogato, sybil, captcha (RTT));
]
1814 Alternatively, it may be the case that one of these problems proves
1815 intractable, or that the drawbacks to many-server systems prove
1816 greater than the benefits. Nevertheless, we may still do well to
1817 consider non-clique topologies. A cascade topology may provide more
1818 defense against traffic confirmation confirmation.
1819 % Why would it? Cite. -NM
1820 Does the hydra (many inputs, few outputs) topology work
1821 better? Are we going to get a hydra anyway because most nodes will be
1824 %%% Do more with this paragraph once The TCP-over-TCP paragraph is
1825 %%% more integrated into Related works.
1827 As mentioned in section
\ref{where-is-it-now
}, Tor could improve its
1828 robustness against node failure by buffering stream data at the
1829 network's edges, and performing end-to-end acknowledgments. The
1830 efficacy of this approach remains to be tested, however, and there
1831 may be more effective means for ensuring reliable connections in the
1832 presence of unreliable nodes.
1834 %%% Keeping this original paragraph for a little while, since it
1835 %%% is not the same as what's written there now.
1837 %Because Tor depends on TLS and TCP to provide a reliable transport,
1838 %when one of the servers goes down, all the circuits (and thus streams)
1839 %traveling over that server must break. This reduces anonymity because
1840 %everybody needs to reconnect right then (does it? how much?) and
1841 %because exit connections all break at the same time, and it also harms
1842 %usability. It seems the problem is even worse in a peer-to-peer
1843 %environment, because so far such systems don't really provide an
1844 %incentive for nodes to stay connected when they're done browsing, so
1845 %we would expect a much higher churn rate than for onion routing.
1846 %there ways of allowing streams to survive the loss of a node in the
1849 % Roger or Paul suggested that we say something about incentives,
1850 % too, but I think that's a better candidate for our future work
1851 % section. After all, we will doubtlessly learn very much about why
1852 % people do or don't run and use Tor in the near future. -NM
1854 %We should run a squid at each exit node, to provide comparable anonymity
1855 %to private exit nodes for cache hits, to speed everything up, and to
1856 %have a buffer for funny stuff coming out of port 80.
1857 % on the other hand, it hampers PFS, because ORs have pages in the cache.
1858 %I previously elsewhere suggested bulk transfer proxies to carve
1859 %up big things so that they could be downloaded in less noticeable
1860 %pieces over several normal looking connections. We could suggest
1861 %similarly one or a handful of squid nodes that might serve up
1862 %some of the more sensitive but common material, especially if
1863 %the relevant sites didn't want to or couldn't run their own OR.
1864 %This would be better than having everyone run a squid which would
1865 %just help identify after the fact the different history of that
1866 %node's activity. All this kind of speculation needs to move to
1867 %future work section I guess. -PS]
1869 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1873 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1875 \Section{Future Directions
}
1876 \label{sec:conclusion
}
1878 % Mention that we need to do TCP over tor for reliability.
1880 Tor brings together many innovations into
1881 a unified deployable system. But there are still several attacks that
1882 work quite well, as well as a number of sustainability and run-time
1883 issues remaining to be ironed out. In particular:
1885 % Many of these (Scalability, cover traffic) are duplicates from open problems.
1888 \item \emph{Scalability:
} Tor's emphasis on design simplicity and
1889 deployability has led us to adopt a clique topology, a
1890 semi-centralized model for directories and trusts, and a
1891 full-network-visibility model for client knowledge. None of these
1892 properties will scale to more than a few hundred servers, at most.
1893 Promising approaches to better scalability exist (see
1894 section~
\ref{sec:maintaining-anonymity
}), but more deployment
1895 experience would be helpful in learning the relative importance of
1897 \item \emph{Cover traffic:
} Currently we avoid cover traffic because
1898 of its clear costs in performance and bandwidth, and because its
1899 security benefits have not well understood. With more research
1900 \cite{SS03,defensive-dropping
}, the price/value ratio may change,
1901 both for link-level cover traffic and also long-range cover traffic.
1902 \item \emph{Better directory distribution:
} Even with the threshold
1903 directory agreement algorithm described in
\ref{subsec:dirservers
},
1904 the directory servers are still trust bottlenecks. We must find more
1905 decentralized yet practical ways to distribute up-to-date snapshots of
1906 network status without introducing new attacks. Also, directory
1907 retrieval presents a scaling problem, since clients currently
1908 download a description of the entire network state every
15
1909 minutes. As the state grows larger and clients more numerous, we
1910 may need to move to a solution in which clients only receive
1911 incremental updates to directory state, or where directories are
1912 cached at the ORs to avoid high loads on the directory servers.
1913 \item \emph{Implementing location-hidden servers:
} While
1914 Section~
\ref{sec:rendezvous
} describes a design for rendezvous
1915 points and location-hidden servers, these feature has not yet been
1916 implemented. While doing so, will likely encounter additional
1917 issues, both in terms of usability and anonymity, that must be
1919 \item \emph{Further specification review:
} Although we have a public,
1920 byte-level specification for the Tor protocols, this protocol has
1921 not received extensive external review. We hope that as Tor
1922 becomes more widely deployed, more people will become interested in
1923 examining our specification.
1924 \item \emph{Wider-scale deployment:
} The original goal of Tor was to
1925 gain experience in deploying an anonymizing overlay network, and
1926 learn from having actual users. We are now at the point in design
1927 and development where we can start deploying a wider network. Once
1928 we have are ready for actual users, we will doubtlessly be better
1929 able to evaluate some of our design decisions, including our
1930 robustness/latency tradeoffs, our abuse-prevention mechanisms, and
1931 our overall usability.
1932 work with morphmix spec
1933 small cells vs large cells
1936 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1938 %% commented out for anonymous submission
1939 %\Section{Acknowledgments}
1940 % Peter Palfrader, Geoff Goodell, Adam Shostack, Joseph Sokol-Margolis
1941 % for editing and comments
1942 % Bram Cohen for congestion control discussions
1943 % Adam Back for suggesting telescoping circuits
1945 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1947 \bibliographystyle{latex8
}
1948 \bibliography{tor-design
}
1954 % avoid contractions (it's, can't, etc.)
1955 % prefer ``for example'' or ``such as'' to e.g.
1956 % prefer ``that is'' to i.e.
1957 % 'mix', 'mixes' (as noun)
1959 % 'mix', 'mixing' (as verb)
1960 % 'middleman' [Not with a hyphen; the hyphen has been optional
1961 % since Middle English.]
1963 % 'Cypherpunk', 'Cypherpunks', 'Cypherpunk remailer'
1964 % 'Onion Routing design', 'onion router' [note capitalization]
1966 % Try not to use \cite as a noun.
1967 % 'Authorizating' sounds great, but it isn't a word.
1968 % 'First, second, third', not 'Firstly, secondly, thirdly'.
1969 % 'circuit', not 'channel'
1970 % Typography: no space on either side of an em dash---ever.
1971 % Hyphens are for multi-part words; en dashs imply movement or
1972 % opposition (The Alice--Bob connection); and em dashes are
1973 % for punctuation---like that.
1975 % 'Substitute ``Damn'' every time you're inclined to write ``very;'' your
1976 % editor will delete it and the writing will be just as it should be.'