tor-design.tex 100 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021
  1. \documentclass[times,10pt,twocolumn]{article}
  2. \usepackage{latex8}
  3. \usepackage{times}
  4. \usepackage{url}
  5. \usepackage{graphics}
  6. \usepackage{amsmath}
  7. \usepackage{epsfig}
  8. \pagestyle{plain}
  9. \renewcommand\url{\begingroup \def\UrlLeft{<}\def\UrlRight{>}\urlstyle{tt}\Url}
  10. \newcommand\emailaddr{\begingroup \def\UrlLeft{<}\def\UrlRight{>}\urlstyle{tt}\Url}
  11. \newcommand{\workingnote}[1]{} % The version that hides the note.
  12. %\newcommand{\workingnote}[1]{(**#1)} % The version that makes the note visible.
  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
  16. %\newif\ifpdf
  17. %\ifx\pdfoutput\undefined
  18. % \pdffalse
  19. %\else
  20. % \pdfoutput=1
  21. % \pdftrue
  22. %\fi
  23. \newenvironment{tightlist}{\begin{list}{$\bullet$}{
  24. \setlength{\itemsep}{0mm}
  25. \setlength{\parsep}{0mm}
  26. % \setlength{\labelsep}{0mm}
  27. % \setlength{\labelwidth}{0mm}
  28. % \setlength{\topsep}{0mm}
  29. }}{\end{list}}
  30. % Cut down on whitespace above and below figures displayed at head/foot of
  31. % page.
  32. \setlength{\textfloatsep}{3mm}
  33. % Cut down on whitespace above and below figures displayed in middle of page
  34. \setlength{\intextsep}{3mm}
  35. \begin{document}
  36. %% Use dvipdfm instead. --DH
  37. %\ifpdf
  38. % \pdfcompresslevel=9
  39. % \pdfpagewidth=\the\paperwidth
  40. % \pdfpageheight=\the\paperheight
  41. %\fi
  42. \title{Tor: The Second-Generation Onion Router} %\\DRAFT VERSION}
  43. % Putting the 'Private' back in 'Virtual Private Network'
  44. \author{Roger Dingledine \\ The Free Haven Project \\ arma@freehaven.net \and
  45. Nick Mathewson \\ The Free Haven Project \\ nickm@freehaven.net \and
  46. Paul Syverson \\ Naval Research Lab \\ syverson@itd.nrl.navy.mil}
  47. \maketitle
  48. \thispagestyle{empty}
  49. \begin{abstract}
  50. We present Tor, a circuit-based low-latency anonymous communication
  51. service. This second-generation Onion Routing system addresses limitations
  52. in the original design. Tor adds perfect forward secrecy, congestion
  53. control, directory servers, integrity checking, configurable exit policies,
  54. and a practical design for rendezvous points. Tor works on the real-world
  55. Internet, requires no special privileges or kernel modifications, requires
  56. little synchronization or coordination between nodes, and provides a
  57. reasonable tradeoff between anonymity, usability, and efficiency.
  58. We briefly describe our experiences with an international network of
  59. more than a dozen hosts. % that has been running for several months.
  60. We close with a list of open problems in anonymous communication.
  61. \end{abstract}
  62. %\begin{center}
  63. %\textbf{Keywords:} anonymity, peer-to-peer, remailer, nymserver, reply block
  64. %\end{center}
  65. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  66. \Section{Overview}
  67. \label{sec:intro}
  68. Onion Routing is a distributed overlay network designed to anonymize
  69. TCP-based applications like web browsing, secure shell,
  70. and instant messaging. Clients choose a path through the network and
  71. build a \emph{circuit}, in which each node (or ``onion router'' or ``OR'')
  72. in the path knows its predecessor and successor, but no other nodes in
  73. the circuit. Traffic flows down the circuit in fixed-size
  74. \emph{cells}, which are unwrapped by a symmetric key at each node
  75. (like the layers of an onion) and relayed downstream. The
  76. Onion Routing project published several design and analysis
  77. papers \cite{or-ih96,or-jsac98,or-discex00,or-pet00}. While a wide area Onion
  78. Routing network was deployed briefly, the only long-running
  79. public implementation was a fragile
  80. proof-of-concept that ran on a single machine. Even this simple deployment
  81. processed connections from over sixty thousand distinct IP addresses from
  82. all over the world at a rate of about fifty thousand per day.
  83. But many critical design and deployment issues were never
  84. resolved, and the design has not been updated in several years. Here
  85. we describe Tor, a protocol for asynchronous, loosely federated onion
  86. routers that provides the following improvements over the old Onion
  87. Routing design:
  88. \textbf{Perfect forward secrecy:} Onion Routing
  89. was originally vulnerable to a single hostile node recording traffic and
  90. later compromising successive nodes in the circuit and forcing them
  91. to decrypt it. Rather than using a single multiply encrypted data
  92. structure (an \emph{onion}) to lay each circuit,
  93. Tor now uses an incremental or \emph{telescoping} path-building design,
  94. where the initiator negotiates session keys with each successive hop in
  95. the circuit. Once these keys are deleted, subsequently compromised nodes
  96. cannot decrypt old traffic. As a side benefit, onion replay detection
  97. is no longer necessary, and the process of building circuits is more
  98. reliable, since the initiator knows when a hop fails and can then try
  99. extending to a new node.
  100. \textbf{Separation of ``protocol cleaning'' from anonymity:}
  101. Onion Routing originally required a separate ``application
  102. proxy'' for each supported application protocol---most of which were
  103. never written, so many applications were never supported. Tor uses the
  104. standard and near-ubiquitous SOCKS~\cite{socks4} proxy interface, allowing
  105. us to support most TCP-based programs without modification. Tor now
  106. relies on the filtering features of privacy-enhancing
  107. application-level proxies such as Privoxy~\cite{privoxy}, without trying
  108. to duplicate those features itself.
  109. \textbf{No mixing, padding, or traffic shaping (yet):} Onion
  110. Routing originally called for batching and reordering cells as they arrived,
  111. assumed padding between ORs, and in
  112. later designs added padding between onion proxies (users) and
  113. ORs~\cite{or-ih96,or-jsac98}. Tradeoffs between padding protection
  114. and cost were discussed, and \emph{traffic shaping} algorithms were
  115. theorized~\cite{or-pet00} to provide good security without expensive
  116. padding, but no concrete padding scheme was suggested.
  117. Recent research~\cite{econymics}
  118. and deployment experience~\cite{freedom21-security} suggest that this
  119. level of resource use is not practical or economical; and even full
  120. link padding is still vulnerable~\cite{defensive-dropping}. Thus,
  121. until we have a proven and convenient design for traffic shaping or
  122. low-latency mixing that improves anonymity against a realistic
  123. adversary, we leave these strategies out.
  124. \textbf{Many TCP streams can share one circuit:} Onion Routing originally
  125. built a separate circuit for each
  126. application-level request, but this required
  127. multiple public key operations for every request, and also presented
  128. a threat to anonymity from building so many circuits; see
  129. Section~\ref{sec:maintaining-anonymity}. Tor multiplexes multiple TCP
  130. streams along each circuit to improve efficiency and anonymity.
  131. \textbf{Leaky-pipe circuit topology:} Through in-band signaling
  132. within the circuit, Tor initiators can direct traffic to nodes partway
  133. down the circuit. This novel approach
  134. allows traffic to exit the circuit from the middle---possibly
  135. frustrating traffic shape and volume attacks based on observing the end
  136. of the circuit. (It also allows for long-range padding if
  137. future research shows this to be worthwhile.)
  138. \textbf{Congestion control:} Earlier anonymity designs do not
  139. address traffic bottlenecks. Unfortunately, typical approaches to
  140. load balancing and flow control in overlay networks involve inter-node
  141. control communication and global views of traffic. Tor's decentralized
  142. congestion control uses end-to-end acks to maintain anonymity
  143. while allowing nodes at the edges of the network to detect congestion
  144. or flooding and send less data until the congestion subsides.
  145. \textbf{Directory servers:} The earlier Onion Routing design
  146. planned to flood state information through the network---an approach
  147. that can be unreliable and complex. % open to partitioning attacks.
  148. Tor takes a simplified view toward distributing this
  149. information. Certain more trusted nodes act as \emph{directory
  150. servers}: they provide signed directories describing known
  151. routers and their current state. Users periodically download them
  152. via HTTP.
  153. \textbf{Variable exit policies:} Tor provides a consistent mechanism
  154. for each node to advertise a policy describing the hosts
  155. and ports to which it will connect. These exit policies are critical
  156. in a volunteer-based distributed infrastructure, because each operator
  157. is comfortable with allowing different types of traffic to exit the Tor
  158. network from his node.
  159. \textbf{End-to-end integrity checking:} The original Onion Routing
  160. design did no integrity checking on data. Any node on the
  161. circuit could change the contents of data cells as they passed by---for
  162. example, to alter a connection request so it would connect
  163. to a different webserver, or to `tag' encrypted traffic and look for
  164. corresponding corrupted traffic at the network edges~\cite{minion-design}.
  165. Tor hampers these attacks by verifying data integrity before it leaves
  166. the network.
  167. %\textbf{Improved robustness to failed nodes:} A failed node
  168. %in the old design meant that circuit building failed, but thanks to
  169. %Tor's step-by-step circuit building, users notice failed nodes
  170. %while building circuits and route around them. Additionally, liveness
  171. %information from directories allows users to avoid unreliable nodes in
  172. %the first place.
  173. %% Can't really claim this, now that we've found so many variants of
  174. %% attack on partial-circuit-building. -RD
  175. \textbf{Rendezvous points and hidden services:}
  176. Tor provides an integrated mechanism for responder anonymity via
  177. location-protected servers. Previous Onion Routing designs included
  178. long-lived ``reply onions'' that could be used to build circuits
  179. to a hidden server, but these reply onions did not provide forward
  180. security, and became useless if any node in the path went down
  181. or rotated its keys. In Tor, clients negotiate {\it rendezvous points}
  182. to connect with hidden servers; reply onions are no longer required.
  183. Unlike Freedom~\cite{freedom2-arch}, Tor does not require OS kernel
  184. patches or network stack support. This prevents us from anonymizing
  185. non-TCP protocols, but has greatly helped our portability and
  186. deployability.
  187. %Unlike Freedom~\cite{freedom2-arch}, Tor only anonymizes
  188. %TCP-based protocols---not requiring patches (or built-in support) in an
  189. %operating system's network stack has been valuable to Tor's
  190. %portability and deployability.
  191. We have implemented all of the above features except rendezvous
  192. points. Our source code is
  193. available under a free license, and Tor
  194. %, as far as we know, is unencumbered by patents.
  195. is not covered by the patent that affected distribution and use of
  196. earlier versions of Onion Routing.
  197. We have deployed a wide-area alpha network
  198. to test the design, to get more experience with usability
  199. and users, and to provide a research platform for experimentation.
  200. As of this writing, the network stands at eighteen nodes in thirteen
  201. distinct administrative domains on two continents.
  202. We review previous work in Section~\ref{sec:related-work}, describe
  203. our goals and assumptions in Section~\ref{sec:assumptions},
  204. and then address the above list of improvements in
  205. Sections~\ref{sec:design} and~\ref{sec:other-design}. We summarize
  206. in Section~\ref{sec:attacks} how our design stands up to
  207. known attacks, and talk about our early deployment experiences in
  208. Section~\ref{sec:in-the-wild}. We conclude with a list of open problems in
  209. Section~\ref{sec:maintaining-anonymity} and future work for the Onion
  210. Routing project in Section~\ref{sec:conclusion}.
  211. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  212. \Section{Related work}
  213. \label{sec:related-work}
  214. Modern anonymity systems date to Chaum's {\bf Mix-Net}
  215. design~\cite{chaum-mix}. Chaum
  216. proposed hiding the correspondence between sender and recipient by
  217. wrapping messages in layers of public-key cryptography, and relaying them
  218. through a path composed of ``mixes.'' Each mix in turn
  219. decrypts, delays, and re-orders messages, before relaying them
  220. onward.
  221. %toward their destinations.
  222. Subsequent relay-based anonymity designs have diverged in two
  223. main directions. Systems like {\bf Babel}~\cite{babel},
  224. {\bf Mixmaster}~\cite{mixmaster-spec},
  225. and {\bf Mixminion}~\cite{minion-design} have tried
  226. to maximize anonymity at the cost of introducing comparatively large and
  227. variable latencies. Because of this decision, these \emph{high-latency}
  228. networks resist strong global adversaries,
  229. but introduce too much lag for interactive tasks like web browsing,
  230. Internet chat, or SSH connections.
  231. Tor belongs to the second category: \emph{low-latency} designs that
  232. try to anonymize interactive network traffic. These systems handle
  233. a variety of bidirectional protocols. They also provide more convenient
  234. mail delivery than the high-latency anonymous email
  235. networks, because the remote mail server provides explicit and timely
  236. delivery confirmation. But because these designs typically
  237. involve many packets that must be delivered quickly, it is
  238. difficult for them to prevent an attacker who can eavesdrop both ends of the
  239. communication from correlating the timing and volume
  240. of traffic entering the anonymity network with traffic leaving it \cite{SS03}.
  241. These
  242. protocols are similarly vulnerable to an active adversary who introduces
  243. timing patterns into traffic entering the network and looks
  244. for correlated patterns among exiting traffic.
  245. Although some work has been done to frustrate
  246. these attacks, %\footnote{
  247. % The most common approach is to pad and limit communication to a constant
  248. % rate, or to limit
  249. % the variation in traffic shape. Doing so can have prohibitive bandwidth
  250. % costs and/or performance limitations.
  251. %}
  252. % Point in the footnote is covered above, yes? -PS
  253. most designs protect primarily against traffic analysis rather than traffic
  254. confirmation (see Section~\ref{subsec:threat-model}).
  255. The simplest low-latency designs are single-hop proxies such as the
  256. {\bf Anonymizer}~\cite{anonymizer}: a single trusted server strips the
  257. data's origin before relaying it. These designs are easy to
  258. analyze, but users must trust the anonymizing proxy.
  259. Concentrating the traffic to this single point increases the anonymity set
  260. (the people a given user is hiding among), but it is vulnerable if the
  261. adversary can observe all traffic going into and out of the proxy.
  262. More complex are distributed-trust, circuit-based anonymizing systems.
  263. In these designs, a user establishes one or more medium-term bidirectional
  264. end-to-end circuits, and tunnels data in fixed-size cells.
  265. Establishing circuits is computationally expensive and typically
  266. requires public-key
  267. cryptography, whereas relaying cells is comparatively inexpensive and
  268. typically requires only symmetric encryption.
  269. Because a circuit crosses several servers, and each server only knows
  270. the adjacent servers in the circuit, no single server can link a
  271. user to her communication partners.
  272. The {\bf Java Anon Proxy} (also known as JAP or Web MIXes) uses fixed shared
  273. routes known as \emph{cascades}. As with a single-hop proxy, this
  274. approach aggregates users into larger anonymity sets, but again an
  275. attacker only needs to observe both ends of the cascade to bridge all
  276. the system's traffic. The Java Anon Proxy's design
  277. calls for padding between end users and the head of the
  278. cascade~\cite{web-mix}. However, it is not demonstrated whether the current
  279. implementation's padding policy improves anonymity.
  280. {\bf PipeNet}~\cite{back01, pipenet}, another low-latency design proposed
  281. around the same time as Onion Routing, gave
  282. stronger anonymity but allowed a single user to shut
  283. down the network by not sending. Systems like {\bf ISDN
  284. mixes}~\cite{isdn-mixes} were designed for other environments with
  285. different assumptions.
  286. %XXX please can we fix this sentence to something less demeaning
  287. In P2P designs like {\bf Tarzan}~\cite{tarzan:ccs02} and
  288. {\bf MorphMix}~\cite{morphmix:fc04}, all participants both generate
  289. traffic and relay traffic for others. These systems aim to conceal
  290. whether a given peer originated a request
  291. or just relayed it from another peer. While Tarzan and MorphMix use
  292. layered encryption as above, {\bf Crowds}~\cite{crowds-tissec} simply assumes
  293. an adversary who cannot observe the initiator: it uses no public-key
  294. encryption, so any node on a circuit can read the circuit's traffic.
  295. {\bf Hordes}~\cite{hordes-jcs} is based on Crowds but also uses multicast
  296. responses to hide the initiator. {\bf Herbivore}~\cite{herbivore} and
  297. $\mbox{\bf P}^{\mathbf 5}$~\cite{p5} go even further, requiring broadcast.
  298. These systems are designed primarily for communication between peers,
  299. although Herbivore users can make external connections by
  300. requesting a peer to serve as a proxy.
  301. Systems like {\bf Freedom} and the original Onion Routing build circuits
  302. all at once, using a layered ``onion'' of public-key encrypted messages,
  303. each layer of which provides session keys and the address of the
  304. next server in the circuit. Tor as described herein, Tarzan, MorphMix,
  305. {\bf Cebolla}~\cite{cebolla}, and Rennhard's {\bf Anonymity Network}~\cite{anonnet}
  306. build circuits
  307. in stages, extending them one hop at a time.
  308. Section~\ref{subsubsec:constructing-a-circuit} describes how this
  309. approach enables perfect forward secrecy.
  310. Circuit-based anonymity designs must choose which protocol layer
  311. to anonymize. They may choose to intercept IP packets directly, and
  312. relay them whole (stripping the source address) along the
  313. circuit~\cite{freedom2-arch,tarzan:ccs02}. Alternatively, like
  314. Tor, they may accept TCP streams and relay the data in those streams
  315. along the circuit, ignoring the breakdown of that data into TCP
  316. segments~\cite{morphmix:fc04,anonnet}. Finally, they may accept
  317. application-level protocols (such as HTTP) and relay the application
  318. requests themselves along the circuit.
  319. Making this protocol-layer decision requires a compromise between flexibility
  320. and anonymity. For example, a system that understands HTTP, such as Crowds,
  321. can strip
  322. identifying information from those requests, can take advantage of caching
  323. to limit the number of requests that leave the network, and can batch
  324. or encode those requests to minimize the number of connections.
  325. On the other hand, an IP-level anonymizer can handle nearly any protocol,
  326. even ones unforeseen by its designers (though these systems require
  327. kernel-level modifications to some operating systems, and so are more
  328. complex and less portable). TCP-level anonymity networks like Tor present
  329. a middle approach: they are fairly application neutral (so long as the
  330. application supports, or can be tunneled across, TCP), but by treating
  331. application connections as data streams rather than raw TCP packets,
  332. they avoid the well-known inefficiencies of tunneling TCP over
  333. TCP~\cite{tcp-over-tcp-is-bad}.
  334. Distributed-trust anonymizing systems need to prevent attackers from
  335. adding too many servers and thus compromising user paths.
  336. Tor relies on a small set of well-known directory servers, run by
  337. independent parties, to decide which nodes can
  338. join. Tarzan and MorphMix allow unknown users to run servers, and use
  339. a limited resource (like IP addresses) to prevent an attacker from
  340. controlling too much of the network. Crowds suggests requiring
  341. written, notarized requests from potential crowd members.
  342. Anonymous communication is essential for censorship-resistant
  343. systems like Eternity~\cite{eternity}, Free~Haven~\cite{freehaven-berk},
  344. Publius~\cite{publius}, and Tangler~\cite{tangler}. Tor's rendezvous
  345. points enable connections between mutually anonymous entities; they
  346. are a building block for location-hidden servers, which are needed by
  347. Eternity and Free~Haven.
  348. % didn't include rewebbers. No clear place to put them, so I'll leave
  349. % them out for now. -RD
  350. \Section{Design goals and assumptions}
  351. \label{sec:assumptions}
  352. \noindent{\large\bf Goals}\\
  353. Like other low-latency anonymity designs, Tor seeks to frustrate
  354. attackers from linking communication partners, or from linking
  355. multiple communications to or from a single user. Within this
  356. main goal, however, several considerations have directed
  357. Tor's evolution.
  358. \textbf{Deployability:} The design must be deployed and used in the
  359. real world. Thus it
  360. must not be expensive to run (for example, by requiring more bandwidth
  361. than volunteers are willing to provide); must not place a heavy
  362. liability burden on operators (for example, by allowing attackers to
  363. implicate onion routers in illegal activities); and must not be
  364. difficult or expensive to implement (for example, by requiring kernel
  365. patches, or separate proxies for every protocol). We also cannot
  366. require non-anonymous parties (such as websites)
  367. to run our software. (Our rendezvous point design does not meet
  368. this goal for non-anonymous users talking to hidden servers,
  369. however; see Section~\ref{subsec:rendezvous}.)
  370. \textbf{Usability:} A hard-to-use system has fewer users---and because
  371. anonymity systems hide users among users, a system with fewer users
  372. provides less anonymity. Usability is thus not only a convenience:
  373. it is a security requirement~\cite{econymics,back01}. Tor should
  374. therefore not
  375. require modifying applications; should not introduce prohibitive delays;
  376. and should require users to make as few configuration decisions
  377. as possible. Finally, Tor should be easily implemented on all common
  378. platforms; we cannot require users to change their operating system
  379. to be anonymous. (The current Tor implementation runs on Windows and
  380. assorted Unix clones including Linux, FreeBSD, and MacOS X.)
  381. \textbf{Flexibility:} The protocol must be flexible and well-specified,
  382. so Tor can serve as a test-bed for future research.
  383. Many of the open problems in low-latency anonymity
  384. networks, such as generating dummy traffic or preventing Sybil
  385. attacks~\cite{sybil}, may be solvable independently from the issues
  386. solved by
  387. Tor. Hopefully future systems will not need to reinvent Tor's design.
  388. %(But note that while a flexible design benefits researchers,
  389. %there is a danger that differing choices of extensions will make users
  390. %distinguishable. Experiments should be run on a separate network.)
  391. \textbf{Simple design:} The protocol's design and security
  392. parameters must be well-understood. Additional features impose implementation
  393. and complexity costs; adding unproven techniques to the design threatens
  394. deployability, readability, and ease of security analysis. Tor aims to
  395. deploy a simple and stable system that integrates the best accepted
  396. approaches to protecting anonymity.\\
  397. \noindent{\large\bf Non-goals}\label{subsec:non-goals}\\
  398. In favoring simple, deployable designs, we have explicitly deferred
  399. several possible goals, either because they are solved elsewhere, or because
  400. they are not yet solved.
  401. \textbf{Not peer-to-peer:} Tarzan and MorphMix aim to scale to completely
  402. decentralized peer-to-peer environments with thousands of short-lived
  403. servers, many of which may be controlled by an adversary. This approach
  404. is appealing, but still has many open
  405. problems~\cite{tarzan:ccs02,morphmix:fc04}.
  406. \textbf{Not secure against end-to-end attacks:} Tor does not claim
  407. to provide a definitive solution to end-to-end timing or intersection
  408. attacks. Some approaches, such as having users run their own onion routers,
  409. may help;
  410. see Section~\ref{sec:maintaining-anonymity} for more discussion.
  411. \textbf{No protocol normalization:} Tor does not provide \emph{protocol
  412. normalization} like Privoxy or the Anonymizer. If senders want anonymity from
  413. responders while using complex and variable
  414. protocols like HTTP, Tor must be layered with a filtering proxy such
  415. as Privoxy to hide differences between clients, and expunge protocol
  416. features that leak identity.
  417. Note that by this separation Tor can also provide services that
  418. are anonymous to the network yet authenticated to the responder, like
  419. SSH. Similarly, Tor does not integrate
  420. tunneling for non-stream-based protocols like UDP; this must be
  421. provided by an external service if appropriate.
  422. \textbf{Not steganographic:} Tor does not try to conceal who is connected
  423. to the network.
  424. \SubSection{Threat Model}
  425. \label{subsec:threat-model}
  426. A global passive adversary is the most commonly assumed threat when
  427. analyzing theoretical anonymity designs. But like all practical
  428. low-latency systems, Tor does not protect against such a strong
  429. adversary. Instead, we assume an adversary who can observe some fraction
  430. of network traffic; who can generate, modify, delete, or delay
  431. traffic; who can operate onion routers of his own; and who can
  432. compromise some fraction of the onion routers.
  433. In low-latency anonymity systems that use layered encryption, the
  434. adversary's typical goal is to observe both the initiator and the
  435. responder. By observing both ends, passive attackers can confirm a
  436. suspicion that Alice is
  437. talking to Bob if the timing and volume patterns of the traffic on the
  438. connection are distinct enough; active attackers can induce timing
  439. signatures on the traffic to force distinct patterns. Rather
  440. than focusing on these \emph{traffic confirmation} attacks,
  441. we aim to prevent \emph{traffic
  442. analysis} attacks, where the adversary uses traffic patterns to learn
  443. which points in the network he should attack.
  444. Our adversary might try to link an initiator Alice with her
  445. communication partners, or try to build a profile of Alice's
  446. behavior. He might mount passive attacks by observing the network edges
  447. and correlating traffic entering and leaving the network---by
  448. relationships in packet timing, volume, or externally visible
  449. user-selected
  450. options. The adversary can also mount active attacks by compromising
  451. routers or keys; by replaying traffic; by selectively denying service
  452. to trustworthy routers to move users to
  453. compromised routers, or denying service to users to see if traffic
  454. elsewhere in the
  455. network stops; or by introducing patterns into traffic that can later be
  456. detected. The adversary might subvert the directory servers to give users
  457. differing views of network state. Additionally, he can try to decrease
  458. the network's reliability by attacking nodes or by performing antisocial
  459. activities from reliable nodes and trying to get them taken down---making
  460. the network unreliable flushes users to other less anonymous
  461. systems, where they may be easier to attack. We summarize
  462. in Section~\ref{sec:attacks} how well the Tor design defends against
  463. each of these attacks.
  464. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  465. \Section{The Tor Design}
  466. \label{sec:design}
  467. The Tor network is an overlay network; each onion router (OR)
  468. runs as a normal
  469. user-level process without any special privileges.
  470. Each onion router maintains a TLS~\cite{TLS}
  471. connection to every other onion router.
  472. %(We discuss alternatives to this clique-topology assumption in
  473. %Section~\ref{sec:maintaining-anonymity}.)
  474. % A subset of the ORs also act as
  475. %directory servers, tracking which routers are in the network;
  476. %see Section~\ref{subsec:dirservers} for directory server details.
  477. Each user
  478. runs local software called an onion proxy (OP) to fetch directories,
  479. establish circuits across the network,
  480. and handle connections from user applications. These onion proxies accept
  481. TCP streams and multiplex them across the circuits. The onion
  482. router on the other side
  483. of the circuit connects to the destinations of
  484. the TCP streams and relays data.
  485. Each onion router maintains a long-term identity key and a short-term
  486. onion key. The identity
  487. key is used to sign TLS certificates, to sign the OR's \emph{router
  488. descriptor} (a summary of its keys, address, bandwidth, exit policy,
  489. and so on), and (by directory servers) to sign directories. %Changing
  490. %the identity key of a router is considered equivalent to creating a
  491. %new router.
  492. The onion key is used to decrypt requests
  493. from users to set up a circuit and negotiate ephemeral keys.
  494. The TLS protocol also establishes a short-term link key when communicating
  495. between ORs. Short-term keys are rotated periodically and
  496. independently, to limit the impact of key compromise.
  497. Section~\ref{subsec:cells} presents the fixed-size
  498. \emph{cells} that are the unit of communication in Tor. We describe
  499. in Section~\ref{subsec:circuits} how circuits are
  500. built, extended, truncated, and destroyed. Section~\ref{subsec:tcp}
  501. describes how TCP streams are routed through the network. We address
  502. integrity checking in Section~\ref{subsec:integrity-checking},
  503. and resource limiting in Section~\ref{subsec:rate-limit}.
  504. Finally,
  505. Section~\ref{subsec:congestion} talks about congestion control and
  506. fairness issues.
  507. \SubSection{Cells}
  508. \label{subsec:cells}
  509. Onion routers communicate with one another, and with users' OPs, via
  510. TLS connections with ephemeral keys. Using TLS conceals the data on
  511. the connection with perfect forward secrecy, and prevents an attacker
  512. from modifying data on the wire or impersonating an OR.
  513. Traffic passes along these connections in fixed-size cells. Each cell
  514. is 512 bytes, %(but see Section~\ref{sec:conclusion} for a discussion of
  515. %allowing large cells and small cells on the same network),
  516. and consists of a header and a payload. The header includes a circuit
  517. identifier (circID) that specifies which circuit the cell refers to
  518. (many circuits can be multiplexed over the single TLS connection), and
  519. a command to describe what to do with the cell's payload. (Circuit
  520. identifiers are connection-specific: each single circuit has a different
  521. circID on each OP/OR or OR/OR connection it traverses.)
  522. Based on their command, cells are either \emph{control} cells, which are
  523. always interpreted by the node that receives them, or \emph{relay} cells,
  524. which carry end-to-end stream data. The control cell commands are:
  525. \emph{padding} (currently used for keepalive, but also usable for link
  526. padding); \emph{create} or \emph{created} (used to set up a new circuit);
  527. and \emph{destroy} (to tear down a circuit).
  528. Relay cells have an additional header (the relay header) after the
  529. cell header, containing a streamID (stream identifier: many streams can
  530. be multiplexed over a circuit); an end-to-end checksum for integrity
  531. checking; the length of the relay payload; and a relay command.
  532. The entire contents of the relay header and the relay cell payload
  533. are encrypted or decrypted together as the relay cell moves along the
  534. circuit, using the 128-bit AES cipher in counter mode to generate a
  535. cipher stream. The relay commands are: \emph{relay
  536. data} (for data flowing down the stream), \emph{relay begin} (to open a
  537. stream), \emph{relay end} (to close a stream cleanly), \emph{relay
  538. teardown} (to close a broken stream), \emph{relay connected}
  539. (to notify the OP that a relay begin has succeeded), \emph{relay
  540. extend} and \emph{relay extended} (to extend the circuit by a hop,
  541. and to acknowledge), \emph{relay truncate} and \emph{relay truncated}
  542. (to tear down only part of the circuit, and to acknowledge), \emph{relay
  543. sendme} (used for congestion control), and \emph{relay drop} (used to
  544. implement long-range dummies).
  545. We give a visual overview of cell structure plus the details of relay
  546. cell structure, and then describe each of these cell types and commands
  547. in more detail below.
  548. \begin{figure}[h]
  549. \unitlength=1cm
  550. \centering
  551. \begin{picture}(8.0,1.5)
  552. \put(4,.5){\makebox(0,0)[c]{\epsfig{file=cell-struct,width=7cm}}}
  553. \end{picture}
  554. \end{figure}
  555. \SubSection{Circuits and streams}
  556. \label{subsec:circuits}
  557. Onion Routing originally built one circuit for each
  558. TCP stream. Because building a circuit can take several tenths of a
  559. second (due to public-key cryptography and network latency),
  560. this design imposed high costs on applications like web browsing that
  561. open many TCP streams.
  562. In Tor, each circuit can be shared by many TCP streams. To avoid
  563. delays, users construct circuits preemptively. To limit linkability
  564. among their streams, users' OPs build a new circuit
  565. periodically if the previous one has been used,
  566. and expire old used circuits that no longer have any open streams.
  567. OPs consider making a new circuit once a minute: thus
  568. even heavy users spend negligible time
  569. building circuits, but a limited number of requests can be linked
  570. to each other through a given exit node. Also, because circuits are built
  571. in the background, OPs can recover from failed circuit creation
  572. without delaying streams and thereby harming user experience.\\
  573. \begin{figure}[h]
  574. \centering
  575. \mbox{\epsfig{figure=interaction,width=8.75cm}}
  576. \caption{Alice builds a two-hop circuit and begins fetching a web page.}
  577. \label{fig:interaction}
  578. \end{figure}
  579. \noindent{\large\bf Constructing a circuit}\label{subsubsec:constructing-a-circuit}\\
  580. %\subsubsection{Constructing a circuit}
  581. A user's OP constructs circuits incrementally, negotiating a
  582. symmetric key with each OR on the circuit, one hop at a time. To begin
  583. creating a new circuit, the OP (call her Alice) sends a
  584. \emph{create} cell to the first node in her chosen path (call him Bob).
  585. (She chooses a new
  586. circID $C_{AB}$ not currently used on the connection from her to Bob.)
  587. The \emph{create} cell's
  588. payload contains the first half of the Diffie-Hellman handshake
  589. ($g^x$), encrypted to the onion key of the OR (call him Bob). Bob
  590. responds with a \emph{created} cell containing the second half of the
  591. DH handshake, along with a hash of the negotiated key $K=g^{xy}$.
  592. Once the circuit has been established, Alice and Bob can send one
  593. another relay cells encrypted with the negotiated
  594. key.\footnote{Actually, the negotiated key is used to derive two
  595. symmetric keys: one for each direction.} More detail is given in
  596. the next section.
  597. To extend the circuit further, Alice sends a \emph{relay extend} cell
  598. to Bob, specifying the address of the next OR (call her Carol), and
  599. an encrypted $g^{x_2}$ for her. Bob copies the half-handshake into a
  600. \emph{create} cell, and passes it to Carol to extend the circuit.
  601. (Bob chooses a new circID $C_{BC}$ not currently used on the connection
  602. between him and Carol. Alice never needs to know this circID; only Bob
  603. associates $C_{AB}$ on his connection with Alice to $C_{BC}$ on
  604. his connection with Carol.)
  605. When Carol responds with a \emph{created} cell, Bob wraps the payload
  606. into a \emph{relay extended} cell and passes it back to Alice. Now
  607. the circuit is extended to Carol, and Alice and Carol share a common key
  608. $K_2 = g^{x_2 y_2}$.
  609. To extend the circuit to a third node or beyond, Alice
  610. proceeds as above, always telling the last node in the circuit to
  611. extend one hop further.
  612. This circuit-level handshake protocol achieves unilateral entity
  613. authentication (Alice knows she's handshaking with the OR, but
  614. the OR doesn't care who is opening the circuit---Alice uses no public key
  615. and is trying to remain anonymous) and unilateral key authentication
  616. (Alice and the OR agree on a key, and Alice knows only the OR learns
  617. it). It also achieves forward
  618. secrecy and key freshness. More formally, the protocol is as follows
  619. (where $E_{PK_{Bob}}(\cdot)$ is encryption with Bob's public key,
  620. $H$ is a secure hash function, and $|$ is concatenation):
  621. \begin{equation*}
  622. \begin{aligned}
  623. \mathrm{Alice} \rightarrow \mathrm{Bob}&: E_{PK_{Bob}}(g^x) \\
  624. \mathrm{Bob} \rightarrow \mathrm{Alice}&: g^y, H(K | \mathrm{``handshake"}) \\
  625. \end{aligned}
  626. \end{equation*}
  627. \noindent In the second step, Bob proves that it was he who received $g^x$,
  628. and who chose $y$. We use PK encryption in the first step
  629. (rather than, say, using the first two steps of STS, which has a
  630. signature in the second step) because a single cell is too small to
  631. hold both a public key and a signature. Preliminary analysis with the
  632. NRL protocol analyzer~\cite{meadows96} shows this protocol to be
  633. secure (including perfect forward secrecy) under the
  634. traditional Dolev-Yao model.\\
  635. \noindent{\large\bf Relay cells}\\
  636. %\subsubsection{Relay cells}
  637. %
  638. Once Alice has established the circuit (so she shares keys with each
  639. OR on the circuit), she can send relay cells. Recall that every relay
  640. cell has a streamID that indicates to which
  641. stream the cell belongs. %This streamID allows a relay cell to be
  642. %addressed to any OR on the circuit.
  643. Upon receiving a relay
  644. cell, an OR looks up the corresponding circuit, and decrypts the relay
  645. header and payload with the session key for that circuit.
  646. If the cell is headed away from Alice the OR then checks
  647. whether the decrypted streamID is recognized---either because it
  648. corresponds to an open stream at this OR for the given circuit, or because
  649. it is the control streamID (zero). If the OR recognizes the
  650. streamID, it accepts the relay cell and processes it as described
  651. below. Otherwise,
  652. the OR looks up the circID and OR for the
  653. next step in the circuit, replaces the circID as appropriate, and
  654. sends the decrypted relay cell to the next OR. (If the OR at the end
  655. of the circuit receives an unrecognized relay cell, an error has
  656. occurred, and the cell is discarded.)
  657. OPs treat incoming relay cells similarly: they iteratively unwrap the
  658. relay header and payload with the session keys shared with each
  659. OR on the circuit, from the closest to farthest. % (Because we use a
  660. %stream cipher, encryption operations may be inverted in any order.)
  661. If at any stage the OP recognizes the streamID, the cell must have
  662. originated at the OR whose encryption has just been removed.
  663. To construct a relay cell addressed to a given OR, Alice iteratively
  664. encrypts the cell payload (that is, the relay header and payload) with
  665. the symmetric key of each hop up to that OR. Because the streamID is
  666. encrypted to a different value at each step, only at the targeted OR
  667. will it have a meaningful value.\footnote{
  668. % Should we just say that 2^56 is itself negligible?
  669. % Assuming 4-hop circuits with 10 streams per hop, there are 33
  670. % possible bad streamIDs before the last circuit. This still
  671. % gives an error only once every 2 million terabytes (approx).
  672. With 48 bits of streamID per cell, the probability of an accidental
  673. collision is far lower than the chance of hardware failure.}
  674. This \emph{leaky pipe} circuit topology
  675. allows Alice's streams to exit at different ORs on a single circuit.
  676. Alice may choose different exit points because of their exit policies,
  677. or to keep the ORs from knowing that two streams
  678. originate from the same person.
  679. When an OR later replies to Alice with a relay cell, it
  680. encrypts the cell's relay header and payload with the single key it
  681. shares with Alice, and sends the cell back toward Alice along the
  682. circuit. Subsequent ORs add further layers of encryption as they
  683. relay the cell back to Alice.
  684. To tear down a circuit, Alice sends a \emph{destroy} control
  685. cell. Each OR in the circuit receives the \emph{destroy} cell, closes
  686. all streams on that circuit, and passes a new \emph{destroy} cell
  687. forward. But just as circuits are built incrementally, they can also
  688. be torn down incrementally: Alice can send a \emph{relay
  689. truncate} cell to a single OR on a circuit. That OR then sends a
  690. \emph{destroy} cell forward, and acknowledges with a
  691. \emph{relay truncated} cell. Alice can then extend the circuit to
  692. different nodes, without signaling to the intermediate nodes (or
  693. a limited observer) that she has changed her circuit.
  694. Similarly, if a node on the circuit goes down, the adjacent
  695. node can send a \emph{relay truncated} cell back to Alice. Thus the
  696. ``break a node and see which circuits go down''
  697. attack~\cite{freedom21-security} is weakened.
  698. \SubSection{Opening and closing streams}
  699. \label{subsec:tcp}
  700. When Alice's application wants a TCP connection to a given
  701. address and port, it asks the OP (via SOCKS) to make the
  702. connection. The OP chooses the newest open circuit (or creates one if
  703. none is available), and chooses a suitable OR on that circuit to be the
  704. exit node (usually the last node, but maybe others due to exit policy
  705. conflicts; see Section~\ref{subsec:exitpolicies}.) The OP then opens
  706. the stream by sending a \emph{relay begin} cell to the exit node,
  707. using a streamID of zero (so the OR will recognize it), containing as
  708. its relay payload a new random streamID, the destination
  709. address, and the destination port. Once the
  710. exit node connects to the remote host, it responds
  711. with a \emph{relay connected} cell. Upon receipt, the OP sends a
  712. SOCKS reply to notify the application of its success. The OP
  713. now accepts data from the application's TCP stream, packaging it into
  714. \emph{relay data} cells and sending those cells along the circuit to
  715. the chosen OR.
  716. There's a catch to using SOCKS, however---some applications pass the
  717. alphanumeric hostname to the Tor client, while others resolve it into
  718. an IP address first and then pass the IP address to the Tor client. If
  719. the application does DNS resolution first, Alice thereby reveals her
  720. destination to the remote DNS server, rather than sending the hostname
  721. through the Tor network to be resolved at the far end. Common applications
  722. like Mozilla and SSH have this flaw.
  723. With Mozilla, the flaw is easy to address: the filtering HTTP
  724. proxy called Privoxy gives a hostname to the Tor client, so Alice's
  725. computer never does DNS resolution.
  726. But a portable general solution, such as is needed for
  727. SSH, is
  728. an open problem. Modifying or replacing the local nameserver
  729. can be invasive, brittle, and unportable. Forcing the resolver
  730. library to do resolution via TCP rather than UDP is
  731. hard, and also has portability problems. We could also provide a
  732. tool similar to \emph{dig} to perform a private lookup through the
  733. Tor network. Currently, we encourage the use of
  734. privacy-aware proxies like Privoxy wherever possible.
  735. Closing a Tor stream is analogous to closing a TCP stream: it uses a
  736. two-step handshake for normal operation, or a one-step handshake for
  737. errors. If the stream closes abnormally, the adjacent node simply sends a
  738. \emph{relay teardown} cell. If the stream closes normally, the node sends
  739. a \emph{relay end} cell down the circuit. When the other side has sent
  740. back its own \emph{relay end} cell, the stream can be torn down. Because
  741. all relay cells use layered encryption, only the destination OR knows
  742. that a given relay cell is a request to close a stream. This two-step
  743. handshake allows Tor to support TCP-based applications that use half-closed
  744. connections.
  745. % such as broken HTTP clients that close their side of the
  746. %stream after writing but are still willing to read.
  747. \SubSection{Integrity checking on streams}
  748. \label{subsec:integrity-checking}
  749. Because the old Onion Routing design used a stream cipher without integrity
  750. checking, traffic was
  751. vulnerable to a malleability attack: though the attacker could not
  752. decrypt cells, any changes to encrypted data
  753. would create corresponding changes to the data leaving the network.
  754. This weakness allowed an adversary to change a padding cell to a destroy
  755. cell; change the destination address in a \emph{relay begin} cell to the
  756. adversary's webserver; or change an FTP command from
  757. {\tt dir} to {\tt rm~*}. Any adversary who could guess the encrypted
  758. content could introduce such corruption in a stream. (Even an external
  759. adversary could do this, because the link encryption similarly used a
  760. stream cipher.)
  761. Tor uses TLS on its links---its integrity checking
  762. protects data from modification by external adversaries.
  763. Addressing the insider malleability attack, however, is
  764. more complex.
  765. We could do integrity checking of the relay cells at each hop, either
  766. by including hashes or by using an authenticating cipher mode like
  767. EAX~\cite{eax}, but there are some problems. First, these approaches
  768. impose a message-expansion overhead at each hop, and so we would have to
  769. either leak the path length or waste bytes by padding to a maximum
  770. path length. Second, these solutions can only verify traffic coming
  771. from Alice: ORs would not be able to produce suitable hashes for
  772. the intermediate hops, since the ORs on a circuit do not know the
  773. other ORs' session keys. Third, we have already accepted that our design
  774. is vulnerable to end-to-end timing attacks; tagging attacks performed
  775. within the circuit provide no additional information to the attacker.
  776. Thus, we check integrity only at the edges of each stream. When Alice
  777. negotiates a key with a new hop, they each initialize a SHA-1
  778. digest with a derivative of that key,
  779. thus beginning with randomness that only the two of them know. From
  780. then on they each incrementally add to the SHA-1 digest the contents of
  781. all relay cells they create, and include with each relay cell the
  782. first four bytes of the current digest. Each also keeps a SHA-1
  783. digest of data received, to verify that the received hashes are correct.
  784. To be sure of removing or modifying a cell, the attacker must be able
  785. to deduce the current digest state (which depends on all
  786. traffic between Alice and Bob, starting with their negotiated key).
  787. Attacks on SHA-1 where the adversary can incrementally add to a hash
  788. to produce a new valid hash don't work, because all hashes are
  789. end-to-end encrypted across the circuit. The computational overhead
  790. of computing the digests is minimal compared to doing the AES
  791. encryption performed at each hop of the circuit. We use only four
  792. bytes per cell to minimize overhead; the chance that an adversary will
  793. correctly guess a valid hash
  794. %, plus the payload the current cell,
  795. is
  796. acceptably low, given that Alice or Bob tear down the circuit if they
  797. receive a bad hash.
  798. \SubSection{Rate limiting and fairness}
  799. \label{subsec:rate-limit}
  800. Volunteers are more willing to run services that can limit
  801. their bandwidth usage. To accommodate them, Tor servers use a
  802. token bucket approach~\cite{tannenbaum96} to
  803. enforce a long-term average rate of incoming bytes, while still
  804. permitting short-term bursts above the allowed bandwidth.
  805. % Current bucket sizes are set to ten seconds' worth of traffic.
  806. %Further, we want to avoid starving any Tor streams. Entire circuits
  807. %could starve if we read greedily from connections and one connection
  808. %uses all the remaining bandwidth. We solve this by dividing the number
  809. %of tokens in the bucket by the number of connections that want to read,
  810. %and reading at most that number of bytes from each connection. We iterate
  811. %this procedure until the number of tokens in the bucket is under some
  812. %threshold (currently 10KB), at which point we greedily read from connections.
  813. Because the Tor protocol generates roughly the same number of outgoing
  814. bytes as incoming bytes, it is sufficient in practice to limit only
  815. incoming bytes.
  816. With TCP streams, however, the correspondence is not one-to-one:
  817. relaying a single incoming byte can require an entire 512-byte cell.
  818. (We can't just wait for more bytes, because the local application may
  819. be waiting for a reply.) Therefore, we treat this case as if the entire
  820. cell size had been read, regardless of the fullness of the cell.
  821. Further, inspired by Rennhard et al's design in~\cite{anonnet}, a
  822. circuit's edges can heuristically distinguish interactive streams from bulk
  823. streams by comparing the frequency with which they supply cells. We can
  824. provide good latency for interactive streams by giving them preferential
  825. service, while still giving good overall throughput to the bulk
  826. streams. Such preferential treatment presents a possible end-to-end
  827. attack, but an adversary observing both
  828. ends of the stream can already learn this information through timing
  829. attacks.
  830. \SubSection{Congestion control}
  831. \label{subsec:congestion}
  832. Even with bandwidth rate limiting, we still need to worry about
  833. congestion, either accidental or intentional. If enough users choose the
  834. same OR-to-OR connection for their circuits, that connection can become
  835. saturated. For example, an attacker could send a large file
  836. through the Tor network to a webserver he runs, and then
  837. refuse to read any of the bytes at the webserver end of the
  838. circuit. Without some congestion control mechanism, these bottlenecks
  839. can propagate back through the entire network. We don't need to
  840. reimplement full TCP windows (with sequence numbers,
  841. the ability to drop cells when we're full and retransmit later, and so
  842. on),
  843. because TCP already guarantees in-order delivery of each
  844. cell.
  845. %But we need to investigate further the effects of the current
  846. %parameters on throughput and latency, while also keeping privacy in mind;
  847. %see Section~\ref{sec:maintaining-anonymity} for more discussion.
  848. We describe our response below.
  849. \textbf{Circuit-level throttling:}
  850. To control a circuit's bandwidth usage, each OR keeps track of two
  851. windows. The \emph{packaging window} tracks how many relay data cells the OR is
  852. allowed to package (from incoming TCP streams) for transmission back to the OP,
  853. and the \emph{delivery window} tracks how many relay data cells it is willing
  854. to deliver to TCP streams outside the network. Each window is initialized
  855. (say, to 1000 data cells). When a data cell is packaged or delivered,
  856. the appropriate window is decremented. When an OR has received enough
  857. data cells (currently 100), it sends a \emph{relay sendme} cell towards the OP,
  858. with streamID zero. When an OR receives a \emph{relay sendme} cell with
  859. streamID zero, it increments its packaging window. Either of these cells
  860. increments the corresponding window by 100. If the packaging window
  861. reaches 0, the OR stops reading from TCP connections for all streams
  862. on the corresponding circuit, and sends no more relay data cells until
  863. receiving a \emph{relay sendme} cell.
  864. The OP behaves identically, except that it must track a packaging window
  865. and a delivery window for every OR in the circuit. If a packaging window
  866. reaches 0, it stops reading from streams destined for that OR.
  867. \textbf{Stream-level throttling}:
  868. The stream-level congestion control mechanism is similar to the
  869. circuit-level mechanism. ORs and OPs use \emph{relay sendme} cells
  870. to implement end-to-end flow control for individual streams across
  871. circuits. Each stream begins with a packaging window (currently 500 cells),
  872. and increments the window by a fixed value (50) upon receiving a \emph{relay
  873. sendme} cell. Rather than always returning a \emph{relay sendme} cell as soon
  874. as enough cells have arrived, the stream-level congestion control also
  875. has to check whether data has been successfully flushed onto the TCP
  876. stream; it sends the \emph{relay sendme} cell only when the number of bytes pending
  877. to be flushed is under some threshold (currently 10 cells' worth).
  878. %% Maybe omit this next paragraph. -NM
  879. %Currently, non-data relay cells do not affect the windows. Thus we
  880. %avoid potential deadlock issues, for example, arising because a stream
  881. %can't send a \emph{relay sendme} cell when its packaging window is empty.
  882. These arbitrarily chosen parameters seem to give tolerable throughput
  883. and delay; see Section~\ref{sec:in-the-wild}.
  884. \SubSection{Rendezvous Points and hidden services}
  885. \label{subsec:rendezvous}
  886. Rendezvous points are a building block for \emph{location-hidden
  887. services} (also known as \emph{responder anonymity}) in the Tor
  888. network. Location-hidden services allow Bob to offer a TCP
  889. service, such as a webserver, without revealing his IP address.
  890. This type of anonymity protects against distributed DoS attacks:
  891. attackers are forced to attack the onion routing network
  892. because they do not know Bob's IP address.
  893. Our design for location-hidden servers has the following goals.
  894. \textbf{Access-controlled:} Bob needs a way to filter incoming requests,
  895. so an attacker cannot flood Bob simply by making many connections to him.
  896. \textbf{Robust:} Bob should be able to maintain a long-term pseudonymous
  897. identity even in the presence of router failure. Bob's service must
  898. not be tied to a single OR, and Bob must be able to tie his service
  899. to new ORs. \textbf{Smear-resistant:}
  900. A social attacker who offers an illegal or disreputable location-hidden
  901. service should not be able to ``frame'' a rendezvous router by
  902. making observers believe the router created that service.
  903. \textbf{Application-transparent:} Although we require users
  904. to run special software to access location-hidden servers, we must not
  905. require them to modify their applications.
  906. We provide location-hiding for Bob by allowing him to advertise
  907. several onion routers (his \emph{introduction points}) as contact
  908. points. He may do this on any robust efficient
  909. key-value lookup system with authenticated updates, such as a
  910. distributed hash table (DHT) like CFS~\cite{cfs:sosp01}\footnote{
  911. Rather than rely on an external infrastructure, the Onion Routing network
  912. can run the DHT itself. At first, we can run a simple lookup
  913. system on the
  914. directory servers.} Alice, the client, chooses an OR as her
  915. \emph{rendezvous point}. She connects to one of Bob's introduction
  916. points, informs him of her rendezvous point, and then waits for him
  917. to connect to the rendezvous point. This extra level of indirection
  918. helps Bob's introduction points avoid problems associated with serving
  919. unpopular files directly (for example, if Bob serves
  920. material that the introduction point's community finds objectionable,
  921. or if Bob's service tends to get attacked by network vandals).
  922. The extra level of indirection also allows Bob to respond to some requests
  923. and ignore others.
  924. In Appendix~\ref{sec:rendezvous-specifics} we provide a more detailed
  925. description of the rendezvous protocol, integration issues, attacks,
  926. and related rendezvous work.
  927. \Section{Other design decisions}
  928. \label{sec:other-design}
  929. \SubSection{Resource management and denial-of-service}
  930. \label{subsec:dos}
  931. Providing Tor as a public service creates many opportunities for
  932. denial-of-service attacks against the network. While
  933. flow control and rate limiting (discussed in
  934. Section~\ref{subsec:congestion}) prevent users from consuming more
  935. bandwidth than routers are willing to provide, opportunities remain for
  936. users to
  937. consume more network resources than their fair share, or to render the
  938. network unusable for others.
  939. First of all, there are several CPU-consuming denial-of-service
  940. attacks wherein an attacker can force an OR to perform expensive
  941. cryptographic operations. For example, an attacker who sends a
  942. \emph{create} cell full of junk bytes can force an OR to perform an RSA
  943. decrypt. Similarly, an attacker can
  944. fake the start of a TLS handshake, forcing the OR to carry out its
  945. (comparatively expensive) half of the handshake at no real computational
  946. cost to the attacker.
  947. We have not yet implemented any defenses for these attacks, but several
  948. approaches are possible. First, ORs can
  949. require clients to solve a puzzle~\cite{puzzles-tls} while beginning new
  950. TLS handshakes or accepting \emph{create} cells. So long as these
  951. tokens are easy to verify and computationally expensive to produce, this
  952. approach limits the attack multiplier. Additionally, ORs can limit
  953. the rate at which they accept \emph{create} cells and TLS connections,
  954. so that
  955. the computational work of processing them does not drown out the
  956. symmetric cryptography operations that keep cells
  957. flowing. This rate limiting could, however, allow an attacker
  958. to slow down other users when they build new circuits.
  959. % What about link-to-link rate limiting?
  960. Adversaries can also attack the Tor network's hosts and network
  961. links. Disrupting a single circuit or link breaks all streams passing
  962. along that part of the circuit. Users similarly lose service
  963. when a router crashes or its operator restarts it. The current
  964. Tor design treats such attacks as intermittent network failures, and
  965. depends on users and applications to respond or recover as appropriate. A
  966. future design could use an end-to-end TCP-like acknowledgment protocol,
  967. so that no streams are lost unless the entry or exit point itself is
  968. disrupted. This solution would require more buffering at the network
  969. edges, however, and the performance and anonymity implications from this
  970. extra complexity still require investigation.
  971. \SubSection{Exit policies and abuse}
  972. \label{subsec:exitpolicies}
  973. % originally, we planned to put the "users only know the hostname,
  974. % not the IP, but exit policies are by IP" problem here too. Not
  975. % worth putting in the submission, but worth thinking about putting
  976. % in sometime somehow. -RD
  977. Exit abuse is a serious barrier to wide-scale Tor deployment. Anonymity
  978. presents would-be vandals and abusers with an opportunity to hide
  979. the origins of their activities. Attackers can harm the Tor network by
  980. implicating exit servers for their abuse. Also, applications that commonly
  981. use IP-based authentication (such as institutional mail or webservers)
  982. can be fooled by the fact that anonymous connections appear to originate
  983. at the exit OR.
  984. We stress that Tor does not enable any new class of abuse. Spammers
  985. and other attackers already have access to thousands of misconfigured
  986. systems worldwide, and the Tor network is far from the easiest way
  987. to launch attacks.
  988. %Indeed, because of its limited
  989. %anonymity, Tor is probably not a good way to commit crimes.
  990. But because the
  991. onion routers can be mistaken for the originators of the abuse,
  992. and the volunteers who run them may not want to deal with the hassle of
  993. explaining anonymity networks to irate administrators, we must block or limit
  994. the abuse that travels through the Tor network.
  995. To mitigate abuse issues, in Tor, each onion router's \emph{exit policy}
  996. describes to which external addresses and ports the router will
  997. connect. On one end of the spectrum are \emph{open exit}
  998. nodes that will connect anywhere. On the other end are \emph{middleman}
  999. nodes that only relay traffic to other Tor nodes, and \emph{private exit}
  1000. nodes that only connect to a local host or network. Using a private
  1001. exit (if one exists) is a more secure way for a client to connect to a
  1002. given host or network---an external adversary cannot eavesdrop traffic
  1003. between the private exit and the final destination, and so is less sure of
  1004. Alice's destination and activities. Most onion routers in the current
  1005. network function as
  1006. \emph{restricted exits} that permit connections to the world at large,
  1007. but prevent access to certain abuse-prone addresses and services such
  1008. as SMTP.
  1009. Additionally, in some cases the OR can authenticate clients to
  1010. prevent exit abuse without harming anonymity~\cite{or-discex00}.
  1011. %The abuse issues on closed (e.g. military) networks are different
  1012. %from the abuse on open networks like the Internet. While these IP-based
  1013. %access controls are still commonplace on the Internet, on closed networks,
  1014. %nearly all participants will be honest, and end-to-end authentication
  1015. %can be assumed for important traffic.
  1016. Many administrators use port restrictions to support only a
  1017. limited set of services, such as HTTP, SSH, or AIM.
  1018. This is not a complete solution, of course, since abuse opportunities for these
  1019. protocols are still well known.
  1020. We have not yet encountered any abuse in the deployed network, but if
  1021. we do we should consider using proxies to clean traffic for certain
  1022. protocols as it leaves the network. For example, much abusive HTTP
  1023. behavior (such as exploiting buffer overflows or well-known script
  1024. vulnerabilities) can be detected in a straightforward manner.
  1025. Similarly, one could run automatic spam filtering software (such as
  1026. SpamAssassin) on email exiting the OR network.
  1027. ORs may also rewrite exiting traffic to append
  1028. headers or other information indicating that the traffic has passed
  1029. through an anonymity service. This approach is commonly used
  1030. by email-only anonymity systems. ORs can also
  1031. run on servers with hostnames like {\tt anonymous} to further
  1032. alert abuse targets to the nature of the anonymous traffic.
  1033. A mixture of open and restricted exit nodes allows the most
  1034. flexibility for volunteers running servers. But while having many
  1035. middleman nodes provides a large and robust network,
  1036. having only a few exit nodes reduces the number of points
  1037. an adversary needs to monitor for traffic analysis, and places a
  1038. greater burden on the exit nodes. This tension can be seen in the
  1039. Java Anon Proxy
  1040. cascade model, wherein only one node in each cascade needs to handle
  1041. abuse complaints---but an adversary only needs to observe the entry
  1042. and exit of a cascade to perform traffic analysis on all that
  1043. cascade's users. The hydra model (many entries, few exits) presents a
  1044. different compromise: only a few exit nodes are needed, but an
  1045. adversary needs to work harder to watch all the clients; see
  1046. Section~\ref{sec:conclusion}.
  1047. Finally, we note that exit abuse must not be dismissed as a peripheral
  1048. issue: when a system's public image suffers, it can reduce the number
  1049. and diversity of that system's users, and thereby reduce the anonymity
  1050. of the system itself. Like usability, public perception is a
  1051. security parameter. Sadly, preventing abuse of open exit nodes is an
  1052. unsolved problem, and will probably remain an arms race for the
  1053. foreseeable future. The abuse problems faced by Princeton's CoDeeN
  1054. project~\cite{darkside} give us a glimpse of likely issues.
  1055. \SubSection{Directory Servers}
  1056. \label{subsec:dirservers}
  1057. First-generation Onion Routing designs~\cite{freedom2-arch,or-jsac98} used
  1058. in-band network status updates: each router flooded a signed statement
  1059. to its neighbors, which propagated it onward. But anonymizing networks
  1060. have different security goals than typical link-state routing protocols.
  1061. For example, delays (accidental or intentional)
  1062. that can cause different parts of the network to have different views
  1063. of link-state and topology are not only inconvenient: they give
  1064. attackers an opportunity to exploit differences in client knowledge.
  1065. We also worry about attacks to deceive a
  1066. client about the router membership list, topology, or current network
  1067. state. Such \emph{partitioning attacks} on client knowledge help an
  1068. adversary to efficiently deploy resources
  1069. against a target~\cite{minion-design}.
  1070. Tor uses a small group of redundant, well-known onion routers to
  1071. track changes in network topology and node state, including keys and
  1072. exit policies. Each such \emph{directory server} acts as an HTTP
  1073. server, so clients can fetch current network state
  1074. and router lists, and so other ORs can upload
  1075. state information. Onion routers periodically publish signed
  1076. statements of their state to each directory server. The directory servers
  1077. combine this information with their own views of network liveness,
  1078. and generate a signed description (a \emph{directory}) of the entire
  1079. network state. Client software is
  1080. pre-loaded with a list of the directory servers and their keys,
  1081. to bootstrap each client's view of the network.
  1082. % XXX this means that clients will be forced to upgrade as the
  1083. % XXX dirservers change or get compromised. argue that this is ok.
  1084. When a directory server receives a signed statement for an OR, it
  1085. checks whether the OR's identity key is recognized. Directory
  1086. servers do not automatically advertise unrecognized ORs. (If they did,
  1087. an adversary could take over the network by creating many
  1088. servers~\cite{sybil}.) Instead, new nodes must be approved by the
  1089. directory
  1090. server administrator before they are included. Mechanisms for automated
  1091. node approval are an area of active research, and are discussed more
  1092. in Section~\ref{sec:maintaining-anonymity}.
  1093. Of course, a variety of attacks remain. An adversary who controls
  1094. a directory server can track clients by providing them different
  1095. information---perhaps by listing only nodes under its control, or by
  1096. informing only certain clients about a given node. Even an external
  1097. adversary can exploit differences in client knowledge: clients who use
  1098. a node listed on one directory server but not the others are vulnerable.
  1099. Thus these directory servers must be synchronized and redundant, so
  1100. that they can agree on a common directory. Clients should only trust
  1101. this directory if it is signed by a threshold of the directory
  1102. servers.
  1103. The directory servers in Tor are modeled after those in
  1104. Mixminion~\cite{minion-design}, but our situation is easier. First,
  1105. we make the
  1106. simplifying assumption that all participants agree on the set of
  1107. directory servers. Second, while Mixminion needs to predict node
  1108. behavior, Tor only needs a threshold consensus of the current
  1109. state of the network.
  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. Such a 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
  1120. (described below)
  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.
  1126. The rebroadcast steps ensure that a directory server is heard by
  1127. either all of the other servers or none of them, even when some links
  1128. are down (assuming that any two directory servers can talk directly or
  1129. via a third). Broadcasts are feasible because there are relatively few
  1130. directory servers (currently 3, but we expect as many as 9 as the network
  1131. scales). Computing the shared directory locally is a straightforward
  1132. threshold voting process: we include an OR if a majority of directory
  1133. servers believe it to be good.
  1134. To avoid attacks where a router connects to all the directory servers
  1135. but refuses to relay traffic from other routers, the directory servers
  1136. must build circuits and use them to anonymously test router
  1137. reliability~\cite{mix-acc}. Unfortunately, this defense is not yet
  1138. designed or
  1139. implemented.
  1140. Using directory servers is simpler and more flexible than flooding.
  1141. Flooding is expensive, and complicates the analysis when we
  1142. start experimenting with non-clique network topologies. Signed
  1143. directories can be cached by other
  1144. onion routers,
  1145. so directory servers are not a performance
  1146. bottleneck when we have many users, and do not aid traffic analysis by
  1147. forcing clients to periodically announce their existence to any
  1148. central point.
  1149. \Section{Attacks and Defenses}
  1150. \label{sec:attacks}
  1151. Below we summarize a variety of attacks, and discuss how well our
  1152. design withstands them.\\
  1153. \noindent{\large\bf Passive attacks}\\
  1154. \emph{Observing user traffic patterns.} Observing a user's connection
  1155. will not reveal her destination or data, but it will
  1156. reveal traffic patterns (both sent and received). Profiling via user
  1157. connection patterns requires further processing, because multiple
  1158. application streams may be operating simultaneously or in series over
  1159. a single circuit.
  1160. \emph{Observing user content.} While content at the user end is encrypted,
  1161. connections to responders may not be (indeed, the responding website
  1162. itself may be hostile). While filtering content is not a primary goal
  1163. of Onion Routing, Tor can directly use Privoxy and related
  1164. filtering services to anonymize application data streams.
  1165. \emph{Option distinguishability.} We allow clients to choose
  1166. configuration options. For example, clients concerned about request
  1167. linkability should rotate circuits more often than those concerned
  1168. about traceability. Allowing choice may attract users with different
  1169. %There is economic incentive to attract users by
  1170. %allowing this choice;
  1171. needs; but clients who are
  1172. in the minority may lose more anonymity by appearing distinct than they
  1173. gain by optimizing their behavior~\cite{econymics}.
  1174. \emph{End-to-end timing correlation.} Tor only minimally hides
  1175. such correlations. An attacker watching patterns of
  1176. traffic at the initiator and the responder will be
  1177. able to confirm the correspondence with high probability. The
  1178. greatest protection currently available against such confirmation is to hide
  1179. the connection between the onion proxy and the first Tor node,
  1180. by running the OP on the Tor node or behind a firewall. This approach
  1181. requires an observer to separate traffic originating at the onion
  1182. router from traffic passing through it: a global observer can do this,
  1183. but it might be beyond a limited observer's capabilities.
  1184. \emph{End-to-end size correlation.} Simple packet counting
  1185. will also be effective in confirming
  1186. endpoints of a stream. However, even without padding, we have some
  1187. limited protection: the leaky pipe topology means different numbers
  1188. of packets may enter one end of a circuit than exit at the other.
  1189. \emph{Website fingerprinting.} All the effective passive
  1190. attacks above are traffic confirmation attacks,
  1191. which puts them outside our design goals. There is also
  1192. a passive traffic analysis attack that is potentially effective.
  1193. Rather than searching exit connections for timing and volume
  1194. correlations, the adversary may build up a database of
  1195. ``fingerprints'' containing file sizes and access patterns for
  1196. targeted websites. He can later confirm a user's connection to a given
  1197. site simply by consulting the database. This attack has
  1198. been shown to be effective against SafeWeb~\cite{hintz-pet02}.
  1199. It may be less effective against Tor, since
  1200. streams are multiplexed within the same circuit, and
  1201. fingerprinting will be limited to
  1202. the granularity of cells (currently 512 bytes). Additional
  1203. defenses could include
  1204. larger cell sizes, padding schemes to group websites
  1205. into large sets, and link
  1206. padding or long-range dummies.\footnote{Note that this fingerprinting
  1207. attack should not be confused with the much more complicated latency
  1208. attacks of~\cite{back01}, which require a fingerprint of the latencies
  1209. of all circuits through the network, combined with those from the
  1210. network edges to the target user and the responder website.}\\
  1211. \noindent{\large\bf Active attacks}\\
  1212. \emph{Compromise keys.} An attacker who learns the TLS session key can
  1213. see control cells and encrypted relay cells on every circuit on that
  1214. connection; learning a circuit
  1215. session key lets him unwrap one layer of the encryption. An attacker
  1216. who learns an OR's TLS private key can impersonate that OR for the TLS
  1217. key's lifetime, but he must
  1218. also learn the onion key to decrypt \emph{create} cells (and because of
  1219. perfect forward secrecy, he cannot hijack already established circuits
  1220. without also compromising their session keys). Periodic key rotation
  1221. limits the window of opportunity for these attacks. On the other hand,
  1222. an attacker who learns a node's identity key can replace that node
  1223. indefinitely by sending new forged descriptors to the directory servers.
  1224. \emph{Iterated compromise.} A roving adversary who can
  1225. compromise ORs (by system intrusion, legal coercion, or extralegal
  1226. coercion) could march down the circuit compromising the
  1227. nodes until he reaches the end. Unless the adversary can complete
  1228. this attack within the lifetime of the circuit, however, the ORs
  1229. will have discarded the necessary information before the attack can
  1230. be completed. (Thanks to the perfect forward secrecy of session
  1231. keys, the attacker cannot force nodes to decrypt recorded
  1232. traffic once the circuits have been closed.) Additionally, building
  1233. circuits that cross jurisdictions can make legal coercion
  1234. harder---this phenomenon is commonly called ``jurisdictional
  1235. arbitrage.'' The Java Anon Proxy project recently experienced the
  1236. need for this approach, when
  1237. a German court forced them to add a backdoor to
  1238. all of their nodes~\cite{jap-backdoor}.
  1239. \emph{Run a recipient.} An adversary running a webserver
  1240. trivially learns the timing patterns of users connecting to it, and
  1241. can introduce arbitrary patterns in its responses.
  1242. End-to-end attacks become easier: if the adversary can induce
  1243. users to connect to his webserver (perhaps by advertising
  1244. content targeted to those users), she now holds one end of their
  1245. connection. There is also a danger that application
  1246. protocols and associated programs can be induced to reveal information
  1247. about the initiator. Tor depends on Privoxy and similar protocol cleaners
  1248. to solve this latter problem.
  1249. \emph{Run an onion proxy.} It is expected that end users will
  1250. nearly always run their own local onion proxy. However, in some
  1251. settings, it may be necessary for the proxy to run
  1252. remotely---typically, in institutions that want
  1253. to monitor the activity of those connecting to the proxy.
  1254. Compromising an onion proxy compromises all future connections
  1255. through it.
  1256. \emph{DoS non-observed nodes.} An observer who can only watch some
  1257. of the Tor network can increase the value of this traffic
  1258. by attacking non-observed nodes to shut them down, reduce
  1259. their reliability, or persuade users that they are not trustworthy.
  1260. The best defense here is robustness.
  1261. \emph{Run a hostile OR.} In addition to being a local observer,
  1262. an isolated hostile node can create circuits through itself, or alter
  1263. traffic patterns to affect traffic at other nodes. Nonetheless, a hostile
  1264. node must be immediately adjacent to both endpoints to compromise the
  1265. anonymity of a circuit. If an adversary can
  1266. run multiple ORs, and can persuade the directory servers
  1267. that those ORs are trustworthy and independent, then occasionally
  1268. some user will choose one of those ORs for the start and another
  1269. as the end of a circuit. If an adversary
  1270. controls $m>1$ out of $N$ nodes, he can to correlate at most
  1271. $\left(\frac{m}{N}\right)^2$ of the traffic in this way---although an
  1272. adversary
  1273. could possibly attract a disproportionately large amount of traffic
  1274. by running an OR with a permissive exit policy, or by
  1275. degrading the reliability of other routers.
  1276. \emph{Introduce timing into messages.} This is simply a stronger
  1277. version of passive timing attacks already discussed earlier.
  1278. \emph{Tagging attacks.} A hostile node could ``tag'' a
  1279. cell by altering it. If the
  1280. stream were, for example, an unencrypted request to a Web site,
  1281. the garbled content coming out at the appropriate time would confirm
  1282. the association. However, integrity checks on cells prevent
  1283. this attack.
  1284. \emph{Replace contents of unauthenticated protocols.} When
  1285. relaying an unauthenticated protocol like HTTP, a hostile exit node
  1286. can impersonate the target server. Clients
  1287. should prefer protocols with end-to-end authentication.
  1288. \emph{Replay attacks.} Some anonymity protocols are vulnerable
  1289. to replay attacks. Tor is not; replaying one side of a handshake
  1290. will result in a different negotiated session key, and so the rest
  1291. of the recorded session can't be used.
  1292. \emph{Smear attacks.} An attacker could use the Tor network for
  1293. socially disapproved acts, to bring the
  1294. network into disrepute and get its operators to shut it down.
  1295. Exit policies reduce the possibilities for abuse, but
  1296. ultimately the network requires volunteers who can tolerate
  1297. some political heat.
  1298. \emph{Distribute hostile code.} An attacker could trick users
  1299. into running subverted Tor software that did not, in fact, anonymize
  1300. their connections---or worse, could trick ORs into running weakened
  1301. software that provided users with less anonymity. We address this
  1302. problem (but do not solve it completely) by signing all Tor releases
  1303. with an official public key, and including an entry in the directory
  1304. that lists which versions are currently believed to be secure. To
  1305. prevent an attacker from subverting the official release itself
  1306. (through threats, bribery, or insider attacks), we provide all
  1307. releases in source code form, encourage source audits, and
  1308. frequently warn our users never to trust any software (even from
  1309. us) that comes without source.\\
  1310. \noindent{\large\bf Directory attacks}\\
  1311. \emph{Destroy directory servers.} If a few directory
  1312. servers disappear, the others still decide on a valid
  1313. directory. So long as any directory servers remain in operation,
  1314. they will still broadcast their views of the network and generate a
  1315. consensus directory. (If more than half are destroyed, this
  1316. directory will not, however, have enough signatures for clients to
  1317. use it automatically; human intervention will be necessary for
  1318. clients to decide whether to trust the resulting directory.)
  1319. \emph{Subvert a directory server.} By taking over a directory server,
  1320. an attacker can partially influence the final directory. Since ORs
  1321. are included or excluded by majority vote, the corrupt directory can
  1322. at worst cast a tie-breaking vote to decide whether to include
  1323. marginal ORs. It remains to be seen how often such marginal cases
  1324. occur in practice.
  1325. \emph{Subvert a majority of directory servers.} An adversary who controls
  1326. more than half the directory servers can include as many compromised
  1327. ORs in the final directory as he wishes. We must ensure that directory
  1328. server operators are independent and attack-resistant.
  1329. \emph{Encourage directory server dissent.} The directory
  1330. agreement protocol assumes that directory server operators agree on
  1331. the set of directory servers. An adversary who can persuade some
  1332. of the directory server operators to distrust one another could
  1333. split the quorum into mutually hostile camps, thus partitioning
  1334. users based on which directory they use. Tor does not address
  1335. this attack.
  1336. \emph{Trick the directory servers into listing a hostile OR.}
  1337. Our threat model explicitly assumes directory server operators will
  1338. be able to filter out most hostile ORs.
  1339. % If this is not true, an
  1340. % attacker can flood the directory with compromised servers.
  1341. \emph{Convince the directories that a malfunctioning OR is
  1342. working.} In the current Tor implementation, directory servers
  1343. assume that an OR is running correctly if they can start a TLS
  1344. connection to it. A hostile OR could easily subvert this test by
  1345. accepting TLS connections from ORs but ignoring all cells. Directory
  1346. servers must actively test ORs by building circuits and streams as
  1347. appropriate. The tradeoffs of a similar approach are discussed
  1348. in~\cite{mix-acc}.\\
  1349. \Section{Early experiences: Tor in the Wild}
  1350. \label{sec:in-the-wild}
  1351. As of mid-January 2004, the Tor network consists of 18 nodes
  1352. (16 in the US, 2 in Europe), and more are joining each week as the code
  1353. matures.\footnote{For comparison, the current remailer network
  1354. has about 30 reliable nodes. We haven't asked PlanetLab to provide
  1355. Tor nodes, since their AUP wouldn't allow exit nodes (see
  1356. also~\cite{darkside}) and because we aim to build a long-term community of
  1357. node operators and developers.} Each node has at least a 768Kb/768Kb
  1358. connection, and
  1359. many have 10Mb. The number of users varies (and of course, it's hard to
  1360. tell for sure), but we sometimes have several hundred users---administrators at
  1361. several companies have begun sending their entire departments' web
  1362. traffic through Tor, to block other divisions of
  1363. their company from reading their traffic. Tor users have reported using
  1364. the network for web browsing, FTP, IRC, AIM, Kazaa, and SSH.
  1365. Each Tor node currently processes roughly 800,000 relay
  1366. cells (a bit under half a gigabyte) per week. On average, about 80\%
  1367. of each 500-byte payload is full for cells going back to the client,
  1368. whereas about 40\% is full for cells coming from the client. (The difference
  1369. arises because most of the network's traffic is web browsing.) Interactive
  1370. traffic like SSH brings down the average a lot---once we have more
  1371. experience, and assuming we can resolve the anonymity issues, we may
  1372. partition traffic into two relay cell sizes: one to handle
  1373. bulk traffic and one for interactive traffic.
  1374. Based in part on our restrictive default exit policy (we
  1375. reject SMTP requests) and our low profile, we have had no abuse
  1376. issues since the network was deployed in October
  1377. 2003. Our slow growth rate gives us time to add features,
  1378. resolve bugs, and get a feel for what users actually want from an
  1379. anonymity system. Even though having more users would bolster our
  1380. anonymity sets, we are not eager to attract the Kazaa or warez
  1381. communities---we feel that we must build a reputation for privacy, human
  1382. rights, research, and other socially laudable activities.
  1383. As for performance, profiling shows that Tor spends almost
  1384. all its CPU time in AES, which is fast. Current latency is attributable
  1385. to two factors. First, network latency is critical: we are
  1386. intentionally bouncing traffic around the world several times. Second,
  1387. our end-to-end congestion control algorithm focuses on protecting
  1388. volunteer servers from accidental DoS rather than on optimizing
  1389. performance. % Right now the first $500 \times 500\mbox{B}=250\mbox{KB}$
  1390. %of the stream arrives
  1391. %quickly, and after that throughput depends on the rate that \emph{relay
  1392. %sendme} acknowledgments arrive.
  1393. To quantify these effects, we did some informal tests using a network of 4
  1394. nodes on the same machine (a heavily loaded 1GHz Athlon). We downloaded a 60
  1395. megabyte file from {\tt debian.org} every 30 minutes for 54 hours (108 sample
  1396. points). It arrived in about 300 seconds on average, compared to 210s for a
  1397. direct download. We ran a similar test on the production Tor network,
  1398. fetching the front page of {\tt cnn.com} (55 kilobytes): %every 10 minutes for
  1399. %26 hours (156 sample points):
  1400. while a direct
  1401. download consistently took about 0.3s, the performance through Tor was highly
  1402. variable. Some downloads were as fast as 0.6s, with a median at 2.7s, and
  1403. 80\% finishing within 5.7s. It seems that as the network expands, the chance
  1404. of building a slow circuit (one that includes a slow or heavily loaded node
  1405. or link) is increasing. On the other hand, as our users remain satisfied
  1406. with this increased latency, we can address our performance incrementally as we
  1407. proceed with development.\footnote{For example, we have just begun pushing
  1408. a pipelining patch to the production network that seems to decrease
  1409. latency for medium-to-large files; we will present revised benchmarks
  1410. as they become available.}
  1411. %With the current network's topology and load, users can typically get 1-2
  1412. %megabits sustained transfer rate, which is good enough for now.
  1413. Indeed, the Tor
  1414. design aims foremost to provide a security research platform; performance
  1415. only needs to be sufficient to retain users~\cite{econymics,back01}.
  1416. We can tweak the congestion control
  1417. parameters to provide faster throughput at the cost of
  1418. larger buffers at each node; adding the heuristics mentioned in
  1419. Section~\ref{subsec:rate-limit} to favor low-volume
  1420. streams may also help. More research remains to find the
  1421. right balance.
  1422. % We should say _HOW MUCH_ latency there is in these cases. -NM
  1423. %performs badly on lossy networks. may need airhook or something else as
  1424. %transport alternative?
  1425. Although Tor's clique topology and full-visibility directories present
  1426. scaling problems, we still expect the network to support a few hundred
  1427. nodes and maybe 10,000 users before we're forced to become
  1428. more distributed. With luck, the experience we gain running the current
  1429. topology will help us choose among alternatives when the time comes.
  1430. \Section{Open Questions in Low-latency Anonymity}
  1431. \label{sec:maintaining-anonymity}
  1432. In addition to the non-goals in
  1433. Section~\ref{subsec:non-goals}, many other questions must be solved
  1434. before we can be confident of Tor's security.
  1435. Many of these open issues are questions of balance. For example,
  1436. how often should users rotate to fresh circuits? Frequent rotation
  1437. is inefficient, expensive, and may lead to intersection attacks and
  1438. predecessor attacks~\cite{wright03}, but infrequent rotation makes the
  1439. user's traffic linkable. Besides opening fresh circuits, clients can
  1440. also exit from the middle of the circuit,
  1441. or truncate and re-extend the circuit. More analysis is
  1442. needed to determine the proper tradeoff.
  1443. %% Duplicated by 'Better directory distribution' in section 9.
  1444. %
  1445. %A similar question surrounds timing of directory operations: how often
  1446. %should directories be updated? Clients that update infrequently receive
  1447. %an inaccurate picture of the network, but frequent updates can overload
  1448. %the directory servers. More generally, we must find more
  1449. %decentralized yet practical ways to distribute up-to-date snapshots of
  1450. %network status without introducing new attacks.
  1451. How should we choose path lengths? If Alice only ever uses two hops,
  1452. then both ORs can be certain that by colluding they will learn about
  1453. Alice and Bob. In our current approach, Alice always chooses at least
  1454. three nodes unrelated to herself and her destination.
  1455. %% This point is subtle, but not IMO necessary. Anybody who thinks
  1456. %% about it will see that it's implied by the above sentence; anybody
  1457. %% who doesn't think about it is safe in his ignorance.
  1458. %
  1459. %Thus normally she chooses
  1460. %three nodes, but if she is running an OR and her destination is on an OR,
  1461. %she uses five.
  1462. Should Alice choose a random path length (say,
  1463. increasing it from a geometric distribution) to foil an attacker who
  1464. uses timing to learn that he is the fifth hop and thus concludes that
  1465. both Alice and the responder are on ORs?
  1466. Throughout this paper, we have assumed that end-to-end traffic
  1467. confirmation will immediately and automatically defeat a low-latency
  1468. anonymity system. Even high-latency anonymity systems can be
  1469. vulnerable to end-to-end traffic confirmation, if the traffic volumes
  1470. are high enough, and if users' habits are sufficiently
  1471. distinct~\cite{statistical-disclosure,limits-open}. Can anything be
  1472. done to
  1473. make low-latency systems resist these attacks as well as high-latency
  1474. systems? Tor already makes some effort to conceal the starts and ends of
  1475. streams by wrapping long-range control commands in identical-looking
  1476. relay cells. Link padding could frustrate passive observers who count
  1477. packets; long-range padding could work against observers who own the
  1478. first hop in a circuit. But more research remains to find an efficient
  1479. and practical approach. Volunteers prefer not to run constant-bandwidth
  1480. padding; but no convincing traffic shaping approach has been
  1481. specified. Recent work on long-range padding~\cite{defensive-dropping}
  1482. shows promise. One could also try to reduce correlation in packet timing
  1483. by batching and re-ordering packets, but it is unclear whether this could
  1484. improve anonymity without introducing so much latency as to render the
  1485. network unusable.
  1486. A cascade topology may better defend against traffic confirmation by
  1487. aggregating users, and making padding and
  1488. mixing more affordable. Does the hydra topology (many input nodes,
  1489. few output nodes) work better against some adversaries? Are we going
  1490. to get a hydra anyway because most nodes will be middleman nodes?
  1491. Common wisdom suggests that Alice should run her own OR for best
  1492. anonymity, because traffic coming from her node could plausibly have
  1493. come from elsewhere. How much mixing does this approach need? Is it
  1494. immediately beneficial because of real-world adversaries that can't
  1495. observe Alice's router, but can run routers of their own?
  1496. To scale to many users, and to prevent an attacker from observing the
  1497. whole network, it may be necessary
  1498. to support far more servers than Tor currently anticipates.
  1499. This introduces several issues. First, if approval by a central set
  1500. of directory servers is no longer feasible, what mechanism should be used
  1501. to prevent adversaries from signing up many colluding servers? Second,
  1502. if clients can no longer have a complete picture of the network,
  1503. how can they perform discovery while preventing attackers from
  1504. manipulating or exploiting gaps in their knowledge? Third, if there
  1505. are too many servers for every server to constantly communicate with
  1506. every other, which non-clique topology should the network use?
  1507. (Restricted-route topologies promise comparable anonymity with better
  1508. scalability~\cite{danezis-pets03}, but whatever topology we choose, we
  1509. need some way to keep attackers from manipulating their position within
  1510. it~\cite{casc-rep}.) Fourth, if no central authority is tracking
  1511. server reliability, how do we stop unreliable servers from making
  1512. the network unusable? Fifth, do clients receive so much anonymity
  1513. from running their own ORs that we should expect them all to do
  1514. so~\cite{econymics}, or do we need another incentive structure to
  1515. motivate them? Tarzan and MorphMix present possible solutions.
  1516. % advogato, captcha
  1517. When a Tor node goes down, all its circuits (and thus streams) must break.
  1518. Will users abandon the system because of this brittleness? How well
  1519. does the method in Section~\ref{subsec:dos} allow streams to survive
  1520. node failure? If affected users rebuild circuits immediately, how much
  1521. anonymity is lost? It seems the problem is even worse in a peer-to-peer
  1522. environment---such systems don't yet provide an incentive for peers to
  1523. stay connected when they're done retrieving content, so we would expect
  1524. a higher churn rate.
  1525. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1526. \Section{Future Directions}
  1527. \label{sec:conclusion}
  1528. Tor brings together many innovations into a unified deployable system. The
  1529. next immediate steps include:
  1530. \emph{Scalability:} Tor's emphasis on deployability and design simplicity
  1531. has led us to adopt a clique topology, semi-centralized
  1532. directories, and a full-network-visibility model for client
  1533. knowledge. These properties will not scale past a few hundred servers.
  1534. Section~\ref{sec:maintaining-anonymity} describes some promising
  1535. approaches, but more deployment experience will be helpful in learning
  1536. the relative importance of these bottlenecks.
  1537. \emph{Bandwidth classes:} This paper assumes that all ORs have
  1538. good bandwidth and latency. We should instead adopt the MorphMix model,
  1539. where nodes advertise their bandwidth level (DSL, T1, T3), and
  1540. Alice avoids bottlenecks by choosing nodes that match or
  1541. exceed her bandwidth. In this way DSL users can usefully join the Tor
  1542. network.
  1543. \emph{Incentives:} Volunteers who run nodes are rewarded with publicity
  1544. and possibly better anonymity~\cite{econymics}. More nodes means increased
  1545. scalability, and more users can mean more anonymity. We need to continue
  1546. examining the incentive structures for participating in Tor. Further,
  1547. we need to explore more approaches to limiting abuse, and understand
  1548. why most people don't bother using privacy systems.
  1549. \emph{Cover traffic:} Currently Tor omits cover traffic---its costs
  1550. in performance and bandwidth are clear but its security benefits are
  1551. not well understood. We must pursue more research on link-level cover
  1552. traffic and long-range cover traffic to determine whether some simple padding
  1553. method offers provable protection against our chosen adversary.
  1554. %%\emph{Offer two relay cell sizes:} Traffic on the Internet tends to be
  1555. %%large for bulk transfers and small for interactive traffic. One cell
  1556. %%size cannot be optimal for both types of traffic.
  1557. % This should go in the spec and todo, but not the paper yet. -RD
  1558. \emph{Caching at exit nodes:} Perhaps each exit node should run a
  1559. caching web proxy~\cite{shsm03}, to improve anonymity for cached pages
  1560. (Alice's request never
  1561. leaves the Tor network), to improve speed, and to reduce bandwidth cost.
  1562. On the other hand, forward security is weakened because caches
  1563. constitute a record of retrieved files. We must find the right
  1564. balance between usability and security.
  1565. \emph{Better directory distribution:}
  1566. Clients currently download a description of
  1567. the entire network every 15 minutes. As the state grows larger
  1568. and clients more numerous, we may need a solution in which
  1569. clients receive incremental updates to directory state.
  1570. More generally, we must find more
  1571. scalable yet practical ways to distribute up-to-date snapshots of
  1572. network status without introducing new attacks.
  1573. \emph{Implement location-hidden services:} The design in
  1574. Appendix~\ref{sec:rendezvous-specifics} has not yet been implemented.
  1575. While doing
  1576. so we are likely to encounter additional issues that must be resolved,
  1577. both in terms of usability and anonymity.
  1578. \emph{Further specification review:} Our public
  1579. byte-level specification~\cite{tor-spec} needs
  1580. external review. We hope that as Tor
  1581. is deployed, more people will examine its
  1582. specification.
  1583. \emph{Multisystem interoperability:} We are currently working with the
  1584. designer of MorphMix to unify the specification and implementation of
  1585. the common elements of our two systems. So far, this seems
  1586. to be relatively straightforward. Interoperability will allow testing
  1587. and direct comparison of the two designs for trust and scalability.
  1588. \emph{Wider-scale deployment:} The original goal of Tor was to
  1589. gain experience in deploying an anonymizing overlay network, and
  1590. learn from having actual users. We are now at a point in design
  1591. and development where we can start deploying a wider network. Once
  1592. we have many actual users, we will doubtlessly be better
  1593. able to evaluate some of our design decisions, including our
  1594. robustness/latency tradeoffs, our performance tradeoffs (including
  1595. cell size), our abuse-prevention mechanisms, and
  1596. our overall usability.
  1597. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1598. %% commented out for anonymous submission
  1599. \section*{Acknowledgments}
  1600. We thank Peter Palfrader, Geoff Goodell, Adam Shostack, Joseph Sokol-Margolis,
  1601. John Bashinski, and Zack Brown
  1602. for editing and comments;
  1603. Matej Pfajfar, Andrei Serjantov, Marc Rennhard for design discussions;
  1604. Bram Cohen for congestion control discussions;
  1605. Adam Back for suggesting telescoping circuits; and
  1606. Cathy Meadows for formal analysis of the \emph{extend} protocol.
  1607. This work has been supported by ONR and DARPA.
  1608. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1609. \bibliographystyle{latex8}
  1610. \bibliography{tor-design}
  1611. \newpage
  1612. \appendix
  1613. \Section{Rendezvous points and hidden services}
  1614. \label{sec:rendezvous-specifics}
  1615. In this appendix we provide specifics about the rendezvous points
  1616. of Section~\ref{subsec:rendezvous}. % We also describe integration
  1617. %issues and related work.
  1618. %, and how well the rendezvous point design
  1619. %withstands various attacks.
  1620. % (Not any more; it's currently commented out. -NM)
  1621. %
  1622. %\SubSection{Rendezvous protocol overview}
  1623. %
  1624. The following steps are
  1625. %We give an overview of the steps of a rendezvous. These are
  1626. performed on behalf of Alice and Bob by their local OPs;
  1627. application integration is described more fully below.
  1628. \begin{tightlist}
  1629. \item Bob chooses some introduction points, and advertises them on
  1630. the DHT. He can add more later.
  1631. \item Bob builds a circuit to each of his introduction points,
  1632. and waits for requests.
  1633. \item Alice learns about Bob's service out of band (perhaps Bob told her,
  1634. or she found it on a website). She retrieves the details of Bob's
  1635. service from the DHT.
  1636. \item Alice chooses an OR as the rendezvous point (RP) for this
  1637. transaction. She builds a circuit to the RP, and gives it a
  1638. rendezvous cookie to recognize Bob.
  1639. \item Alice opens an anonymous stream to one of Bob's introduction
  1640. points, and gives it a message (encrypted to Bob's public key)
  1641. telling it about herself,
  1642. her RP and rendezvous cookie, and the
  1643. start of a DH
  1644. handshake. The introduction point sends the message to Bob.
  1645. \item If Bob wants to talk to Alice, he builds a circuit to Alice's
  1646. RP and sends the rendezvous cookie, the second half of the DH
  1647. handshake, and a hash of the session
  1648. key they now share. By the same argument as in
  1649. Section~\ref{subsubsec:constructing-a-circuit}, Alice knows she
  1650. shares the key only with Bob.
  1651. \item The RP connects Alice's circuit to Bob's. Note that RP can't
  1652. recognize Alice, Bob, or the data they transmit.
  1653. \item Alice sends a \emph{relay begin} cell along the circuit. It
  1654. arrives at Bob's OP, which connects to Bob's
  1655. webserver.
  1656. \item An anonymous stream has been established, and Alice and Bob
  1657. communicate as normal.
  1658. \end{tightlist}
  1659. When establishing an introduction point, Bob provides the onion router
  1660. with a public ``introduction'' key. The hash of this public key
  1661. identifies a unique service, and (since Bob signs his
  1662. messages) prevents anybody else from usurping Bob's introduction point
  1663. in the future. Bob uses the same public key to establish the other
  1664. introduction points for his service, and periodically refreshes his
  1665. entry in the DHT.
  1666. The message that Alice gives
  1667. the introduction point includes a hash of Bob's public key % to identify
  1668. %the service, along with
  1669. and an optional initial authorization token (the
  1670. introduction point can do prescreening, for example to block replays). Her
  1671. message to Bob may include an end-to-end authorization token so Bob
  1672. can choose whether to respond.
  1673. The authorization tokens can be used to provide selective access:
  1674. important users can get uninterrupted access.
  1675. %important users get tokens to ensure uninterrupted access. %to the
  1676. %service.
  1677. During normal situations, Bob's service might simply be offered
  1678. directly from mirrors, while Bob gives out tokens to high-priority users. If
  1679. the mirrors are knocked down,
  1680. %by distributed DoS attacks or even
  1681. %physical attack,
  1682. those users can switch to accessing Bob's service via
  1683. the Tor rendezvous system.
  1684. Bob's introduction points are themselves subject to DoS---he must
  1685. open many introduction points or risk such an attack.
  1686. He can provide selected users with a current list or future schedule of
  1687. unadvertised introduction points;
  1688. this is most practical
  1689. if there is a stable and large group of introduction points
  1690. available. Bob could also give secret public keys
  1691. for consulting the DHT\@. All of these approaches
  1692. limit exposure even when
  1693. some selected users collude in the DoS\@.
  1694. \SubSection{Integration with user applications}
  1695. Bob configures his onion proxy to know the local IP address and port of his
  1696. service, a strategy for authorizing clients, and a public key. Bob
  1697. publishes the public key, an expiration time, and
  1698. the current introduction points for his service into the DHT, indexed
  1699. by the hash of the public key. Bob's webserver is unmodified,
  1700. and doesn't even know that it's hidden behind the Tor network.
  1701. Alice's applications also work unchanged---her client interface
  1702. remains a SOCKS proxy. We encode all of the necessary information
  1703. into the fully qualified domain name Alice uses when establishing her
  1704. connection. Location-hidden services use a virtual top level domain
  1705. called {\tt .onion}: thus hostnames take the form {\tt x.y.onion} where
  1706. {\tt x} is the authorization cookie and {\tt y} encodes the hash of
  1707. the public key. Alice's onion proxy
  1708. examines addresses; if they're destined for a hidden server, it decodes
  1709. the key and starts the rendezvous as described above.
  1710. \subsection{Previous rendezvous work}
  1711. Rendezvous points in low-latency anonymity systems were first
  1712. described for use in ISDN telephony~\cite{jerichow-jsac98,isdn-mixes}.
  1713. Later low-latency designs used rendezvous points for hiding location
  1714. of mobile phones and low-power location
  1715. trackers~\cite{federrath-ih96,reed-protocols97}. Rendezvous for
  1716. low-latency
  1717. Internet connections was suggested in early Onion Routing
  1718. work~\cite{or-ih96}, but the first published design was by Ian
  1719. Goldberg~\cite{ian-thesis}. His design differs from
  1720. ours in three ways. First, Goldberg suggests that Alice should manually
  1721. hunt down a current location of the service via Gnutella; our approach
  1722. makes lookup transparent to the user, as well as faster and more robust.
  1723. Second, in Tor the client and server negotiate session keys
  1724. via Diffie-Hellman, so plaintext is not exposed even at the rendezvous point. Third,
  1725. our design minimizes the exposure from running the
  1726. service, to encourage volunteers to offer introduction and rendezvous
  1727. services. Tor's introduction points do not output any bytes to the
  1728. clients; the rendezvous points don't know the client or the server,
  1729. and can't read the data being transmitted. The indirection scheme is
  1730. also designed to include authentication/authorization---if Alice doesn't
  1731. include the right cookie with her request for service, Bob need not even
  1732. acknowledge his existence.
  1733. %\SubSection{Attacks against rendezvous points}
  1734. %
  1735. %We describe here attacks against rendezvous points and how well
  1736. %the system protects against them.
  1737. %
  1738. %\emph{Make many introduction requests.} An attacker could
  1739. %try to deny Bob service by flooding his introduction points with
  1740. %requests. Because the introduction points can block requests that
  1741. %lack authorization tokens, however, Bob can restrict the volume of
  1742. %requests he receives, or require a certain amount of computation for
  1743. %every request he receives.
  1744. %
  1745. %\emph{Attack an introduction point.} An attacker could
  1746. %disrupt a location-hidden service by disabling its introduction
  1747. %points. But because a service's identity is attached to its public
  1748. %key, the service can simply re-advertise
  1749. %itself at a different introduction point. Advertisements can also be
  1750. %done secretly so that only high-priority clients know the address of
  1751. %Bob's introduction points or so that different clients know of different
  1752. %introduction points. This forces the attacker to disable all possible
  1753. %introduction points.
  1754. %
  1755. %\emph{Compromise an introduction point.} An attacker who controls
  1756. %Bob's introduction point can flood Bob with
  1757. %introduction requests, or prevent valid introduction requests from
  1758. %reaching him. Bob can notice a flood, and close the circuit. To notice
  1759. %blocking of valid requests, however, he should periodically test the
  1760. %introduction point by sending rendezvous requests and making
  1761. %sure he receives them.
  1762. %
  1763. %\emph{Compromise a rendezvous point.} A rendezvous
  1764. %point is no more sensitive than any other OR on
  1765. %a circuit, since all data passing through the rendezvous is encrypted
  1766. %with a session key shared by Alice and Bob.
  1767. \end{document}
  1768. % Style guide:
  1769. % U.S. spelling
  1770. % avoid contractions (it's, can't, etc.)
  1771. % prefer ``for example'' or ``such as'' to e.g.
  1772. % prefer ``that is'' to i.e.
  1773. % 'mix', 'mixes' (as noun)
  1774. % 'mix-net'
  1775. % 'mix', 'mixing' (as verb)
  1776. % 'middleman' [Not with a hyphen; the hyphen has been optional
  1777. % since Middle English.]
  1778. % 'nymserver'
  1779. % 'Cypherpunk', 'Cypherpunks', 'Cypherpunk remailer'
  1780. % 'Onion Routing design', 'onion router' [note capitalization]
  1781. % 'SOCKS'
  1782. % Try not to use \cite as a noun.
  1783. % 'Authorizating' sounds great, but it isn't a word.
  1784. % 'First, second, third', not 'Firstly, secondly, thirdly'.
  1785. % 'circuit', not 'channel'
  1786. % Typography: no space on either side of an em dash---ever.
  1787. % Hyphens are for multi-part words; en dashs imply movement or
  1788. % opposition (The Alice--Bob connection); and em dashes are
  1789. % for punctuation---like that.
  1790. % A relay cell; a control cell; a \emph{create} cell; a
  1791. % \emph{relay truncated} cell. Never ``a \emph{relay truncated}.''
  1792. %
  1793. % 'Substitute ``Damn'' every time you're inclined to write ``very;'' your
  1794. % editor will delete it and the writing will be just as it should be.'
  1795. % -- Mark Twain