tor-design.html 116 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032203320342035203620372038203920402041204220432044204520462047204820492050205120522053205420552056205720582059206020612062206320642065206620672068206920702071207220732074207520762077207820792080208120822083208420852086208720882089209020912092209320942095209620972098209921002101210221032104210521062107210821092110211121122113211421152116211721182119212021212122212321242125212621272128212921302131213221332134213521362137213821392140214121422143214421452146214721482149215021512152215321542155215621572158215921602161216221632164216521662167216821692170217121722173217421752176217721782179218021812182218321842185218621872188218921902191219221932194219521962197219821992200220122022203220422052206220722082209221022112212221322142215221622172218221922202221222222232224222522262227222822292230223122322233223422352236223722382239224022412242224322442245224622472248224922502251225222532254225522562257225822592260226122622263226422652266226722682269227022712272227322742275227622772278227922802281228222832284228522862287228822892290229122922293229422952296229722982299230023012302230323042305230623072308230923102311231223132314231523162317231823192320232123222323232423252326232723282329233023312332233323342335233623372338233923402341234223432344234523462347234823492350235123522353235423552356235723582359236023612362236323642365236623672368236923702371237223732374237523762377237823792380238123822383238423852386238723882389239023912392239323942395239623972398239924002401240224032404240524062407240824092410241124122413241424152416241724182419242024212422242324242425242624272428242924302431243224332434243524362437243824392440244124422443244424452446244724482449245024512452245324542455245624572458245924602461246224632464246524662467246824692470247124722473247424752476247724782479248024812482248324842485248624872488
  1. <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
  2. "DTD/xhtml1-transitional.dtd">
  3. <html xmlns="http://www.w3.org/1999/xhtml">
  4. <head>
  5. <meta name="GENERATOR" content="TtH 3.59" />
  6. <style type="text/css"> div.p { margin-top: 7pt;}</style>
  7. <style type="text/css"><!--
  8. td div.comp { margin-top: -0.6ex; margin-bottom: -1ex;}
  9. td div.comb { margin-top: -0.6ex; margin-bottom: -.6ex;}
  10. td div.hrcomp { line-height: 0.9; margin-top: -0.8ex; margin-bottom: -1ex;}
  11. td div.norm {line-height:normal;}
  12. span.roman {font-family: serif; font-style: normal; font-weight: normal;}
  13. span.overacc2 {position: relative; left: .8em; top: -1.2ex;}
  14. span.overacc1 {position: relative; left: .6em; top: -1.2ex;} --></style>
  15. <title> Tor: The Second-Generation Onion Router </title>
  16. </head>
  17. <body>
  18. <h1 align="center">Tor: The Second-Generation Onion Router </h1>
  19. <div class="p"><!----></div>
  20. <h3 align="center">
  21. Roger Dingledine, The Free Haven Project, <tt>arma@freehaven.net</tt><br>
  22. Nick Mathewson, The Free Haven Project, <tt>nickm@freehaven.net</tt><br>
  23. Paul Syverson, Naval Research Lab, <tt>syverson@itd.nrl.navy.mil</tt> </h3>
  24. <div class="p"><!----></div>
  25. <div class="p"><!----></div>
  26. <h2> Abstract</h2>
  27. We present Tor, a circuit-based low-latency anonymous communication
  28. service. This second-generation Onion Routing system addresses limitations
  29. in the original design by adding perfect forward secrecy, congestion
  30. control, directory servers, integrity checking, configurable exit policies,
  31. and a practical design for location-hidden services via rendezvous
  32. points. Tor works on the real-world
  33. Internet, requires no special privileges or kernel modifications, requires
  34. little synchronization or coordination between nodes, and provides a
  35. reasonable tradeoff between anonymity, usability, and efficiency.
  36. We briefly describe our experiences with an international network of
  37. more than 30 nodes. We close with a list of open problems in anonymous communication.
  38. <div class="p"><!----></div>
  39. <div class="p"><!----></div>
  40. <div class="p"><!----></div>
  41. <h2><a name="tth_sEc1">
  42. <a name="sec:intro">
  43. 1</a>&nbsp;&nbsp;Overview</h2>
  44. </a>
  45. <div class="p"><!----></div>
  46. Onion Routing is a distributed overlay network designed to anonymize
  47. TCP-based applications like web browsing, secure shell,
  48. and instant messaging. Clients choose a path through the network and
  49. build a <em>circuit</em>, in which each node (or "onion router" or "OR")
  50. in the path knows its predecessor and successor, but no other nodes in
  51. the circuit. Traffic flows down the circuit in fixed-size
  52. <em>cells</em>, which are unwrapped by a symmetric key at each node
  53. (like the layers of an onion) and relayed downstream. The
  54. Onion Routing project published several design and analysis
  55. papers [<a href="#or-ih96" name="CITEor-ih96">27</a>,<a href="#or-jsac98" name="CITEor-jsac98">41</a>,<a href="#or-discex00" name="CITEor-discex00">48</a>,<a href="#or-pet00" name="CITEor-pet00">49</a>]. While a wide area Onion
  56. Routing network was deployed briefly, the only long-running
  57. public implementation was a fragile
  58. proof-of-concept that ran on a single machine. Even this simple deployment
  59. processed connections from over sixty thousand distinct IP addresses from
  60. all over the world at a rate of about fifty thousand per day.
  61. But many critical design and deployment issues were never
  62. resolved, and the design has not been updated in years. Here
  63. we describe Tor, a protocol for asynchronous, loosely federated onion
  64. routers that provides the following improvements over the old Onion
  65. Routing design:
  66. <div class="p"><!----></div>
  67. <b>Perfect forward secrecy:</b> In the original Onion Routing design,
  68. a single hostile node could record traffic and
  69. later compromise successive nodes in the circuit and force them
  70. to decrypt it. Rather than using a single multiply encrypted data
  71. structure (an <em>onion</em>) to lay each circuit,
  72. Tor now uses an incremental or <em>telescoping</em> path-building design,
  73. where the initiator negotiates session keys with each successive hop in
  74. the circuit. Once these keys are deleted, subsequently compromised nodes
  75. cannot decrypt old traffic. As a side benefit, onion replay detection
  76. is no longer necessary, and the process of building circuits is more
  77. reliable, since the initiator knows when a hop fails and can then try
  78. extending to a new node.
  79. <div class="p"><!----></div>
  80. <b>Separation of "protocol cleaning" from anonymity:</b>
  81. Onion Routing originally required a separate "application
  82. proxy" for each supported application protocol &mdash; most of which were
  83. never written, so many applications were never supported. Tor uses the
  84. standard and near-ubiquitous SOCKS&nbsp;[<a href="#socks4" name="CITEsocks4">32</a>] proxy interface, allowing
  85. us to support most TCP-based programs without modification. Tor now
  86. relies on the filtering features of privacy-enhancing
  87. application-level proxies such as Privoxy&nbsp;[<a href="#privoxy" name="CITEprivoxy">39</a>], without trying
  88. to duplicate those features itself.
  89. <div class="p"><!----></div>
  90. <b>No mixing, padding, or traffic shaping (yet):</b> Onion
  91. Routing originally called for batching and reordering cells as they arrived,
  92. assumed padding between ORs, and in
  93. later designs added padding between onion proxies (users) and
  94. ORs&nbsp;[<a href="#or-ih96" name="CITEor-ih96">27</a>,<a href="#or-jsac98" name="CITEor-jsac98">41</a>]. Tradeoffs between padding protection
  95. and cost were discussed, and <em>traffic shaping</em> algorithms were
  96. theorized&nbsp;[<a href="#or-pet00" name="CITEor-pet00">49</a>] to provide good security without expensive
  97. padding, but no concrete padding scheme was suggested.
  98. Recent research&nbsp;[<a href="#econymics" name="CITEeconymics">1</a>]
  99. and deployment experience&nbsp;[<a href="#freedom21-security" name="CITEfreedom21-security">4</a>] suggest that this
  100. level of resource use is not practical or economical; and even full
  101. link padding is still vulnerable&nbsp;[<a href="#defensive-dropping" name="CITEdefensive-dropping">33</a>]. Thus,
  102. until we have a proven and convenient design for traffic shaping or
  103. low-latency mixing that improves anonymity against a realistic
  104. adversary, we leave these strategies out.
  105. <div class="p"><!----></div>
  106. <b>Many TCP streams can share one circuit:</b> Onion Routing originally
  107. built a separate circuit for each
  108. application-level request, but this required
  109. multiple public key operations for every request, and also presented
  110. a threat to anonymity from building so many circuits; see
  111. Section&nbsp;<a href="#sec:maintaining-anonymity">9</a>. Tor multiplexes multiple TCP
  112. streams along each circuit to improve efficiency and anonymity.
  113. <div class="p"><!----></div>
  114. <b>Leaky-pipe circuit topology:</b> Through in-band signaling
  115. within the circuit, Tor initiators can direct traffic to nodes partway
  116. down the circuit. This novel approach
  117. allows traffic to exit the circuit from the middle &mdash; possibly
  118. frustrating traffic shape and volume attacks based on observing the end
  119. of the circuit. (It also allows for long-range padding if
  120. future research shows this to be worthwhile.)
  121. <div class="p"><!----></div>
  122. <b>Congestion control:</b> Earlier anonymity designs do not
  123. address traffic bottlenecks. Unfortunately, typical approaches to
  124. load balancing and flow control in overlay networks involve inter-node
  125. control communication and global views of traffic. Tor's decentralized
  126. congestion control uses end-to-end acks to maintain anonymity
  127. while allowing nodes at the edges of the network to detect congestion
  128. or flooding and send less data until the congestion subsides.
  129. <div class="p"><!----></div>
  130. <b>Directory servers:</b> The earlier Onion Routing design
  131. planned to flood state information through the network &mdash; an approach
  132. that can be unreliable and complex. Tor takes a simplified view toward distributing this
  133. information. Certain more trusted nodes act as <em>directory
  134. servers</em>: they provide signed directories describing known
  135. routers and their current state. Users periodically download them
  136. via HTTP.
  137. <div class="p"><!----></div>
  138. <b>Variable exit policies:</b> Tor provides a consistent mechanism
  139. for each node to advertise a policy describing the hosts
  140. and ports to which it will connect. These exit policies are critical
  141. in a volunteer-based distributed infrastructure, because each operator
  142. is comfortable with allowing different types of traffic to exit
  143. from his node.
  144. <div class="p"><!----></div>
  145. <b>End-to-end integrity checking:</b> The original Onion Routing
  146. design did no integrity checking on data. Any node on the
  147. circuit could change the contents of data cells as they passed by &mdash; for
  148. example, to alter a connection request so it would connect
  149. to a different webserver, or to `tag' encrypted traffic and look for
  150. corresponding corrupted traffic at the network edges&nbsp;[<a href="#minion-design" name="CITEminion-design">15</a>].
  151. Tor hampers these attacks by verifying data integrity before it leaves
  152. the network.
  153. <div class="p"><!----></div>
  154. <div class="p"><!----></div>
  155. <b>Rendezvous points and hidden services:</b>
  156. Tor provides an integrated mechanism for responder anonymity via
  157. location-protected servers. Previous Onion Routing designs included
  158. long-lived "reply onions" that could be used to build circuits
  159. to a hidden server, but these reply onions did not provide forward
  160. security, and became useless if any node in the path went down
  161. or rotated its keys. In Tor, clients negotiate <i>rendezvous points</i>
  162. to connect with hidden servers; reply onions are no longer required.
  163. <div class="p"><!----></div>
  164. Unlike Freedom&nbsp;[<a href="#freedom2-arch" name="CITEfreedom2-arch">8</a>], Tor does not require OS kernel
  165. patches or network stack support. This prevents us from anonymizing
  166. non-TCP protocols, but has greatly helped our portability and
  167. deployability.
  168. <div class="p"><!----></div>
  169. <div class="p"><!----></div>
  170. We have implemented all of the above features, including rendezvous
  171. points. Our source code is
  172. available under a free license, and Tor
  173. is not covered by the patent that affected distribution and use of
  174. earlier versions of Onion Routing.
  175. We have deployed a wide-area alpha network
  176. to test the design, to get more experience with usability
  177. and users, and to provide a research platform for experimentation.
  178. As of this writing, the network stands at 32 nodes spread over two continents.
  179. <div class="p"><!----></div>
  180. We review previous work in Section&nbsp;<a href="#sec:related-work">2</a>, describe
  181. our goals and assumptions in Section&nbsp;<a href="#sec:assumptions">3</a>,
  182. and then address the above list of improvements in
  183. Sections&nbsp;<a href="#sec:design">4</a>,&nbsp;<a href="#sec:rendezvous">5</a>, and&nbsp;<a href="#sec:other-design">6</a>.
  184. We summarize
  185. in Section&nbsp;<a href="#sec:attacks">7</a> how our design stands up to
  186. known attacks, and talk about our early deployment experiences in
  187. Section&nbsp;<a href="#sec:in-the-wild">8</a>. We conclude with a list of open problems in
  188. Section&nbsp;<a href="#sec:maintaining-anonymity">9</a> and future work for the Onion
  189. Routing project in Section&nbsp;<a href="#sec:conclusion">10</a>.
  190. <div class="p"><!----></div>
  191. <div class="p"><!----></div>
  192. <h2><a name="tth_sEc2">
  193. <a name="sec:related-work">
  194. 2</a>&nbsp;&nbsp;Related work</h2>
  195. </a>
  196. <div class="p"><!----></div>
  197. Modern anonymity systems date to Chaum's <b>Mix-Net</b>
  198. design&nbsp;[<a href="#chaum-mix" name="CITEchaum-mix">10</a>]. Chaum
  199. proposed hiding the correspondence between sender and recipient by
  200. wrapping messages in layers of public-key cryptography, and relaying them
  201. through a path composed of "mixes." Each mix in turn
  202. decrypts, delays, and re-orders messages before relaying them
  203. onward.
  204. <div class="p"><!----></div>
  205. Subsequent relay-based anonymity designs have diverged in two
  206. main directions. Systems like <b>Babel</b>&nbsp;[<a href="#babel" name="CITEbabel">28</a>],
  207. <b>Mixmaster</b>&nbsp;[<a href="#mixmaster-spec" name="CITEmixmaster-spec">36</a>],
  208. and <b>Mixminion</b>&nbsp;[<a href="#minion-design" name="CITEminion-design">15</a>] have tried
  209. to maximize anonymity at the cost of introducing comparatively large and
  210. variable latencies. Because of this decision, these <em>high-latency</em>
  211. networks resist strong global adversaries,
  212. but introduce too much lag for interactive tasks like web browsing,
  213. Internet chat, or SSH connections.
  214. <div class="p"><!----></div>
  215. Tor belongs to the second category: <em>low-latency</em> designs that
  216. try to anonymize interactive network traffic. These systems handle
  217. a variety of bidirectional protocols. They also provide more convenient
  218. mail delivery than the high-latency anonymous email
  219. networks, because the remote mail server provides explicit and timely
  220. delivery confirmation. But because these designs typically
  221. involve many packets that must be delivered quickly, it is
  222. difficult for them to prevent an attacker who can eavesdrop both ends of the
  223. communication from correlating the timing and volume
  224. of traffic entering the anonymity network with traffic leaving it&nbsp;[<a href="#SS03" name="CITESS03">45</a>].
  225. These
  226. protocols are similarly vulnerable to an active adversary who introduces
  227. timing patterns into traffic entering the network and looks
  228. for correlated patterns among exiting traffic.
  229. Although some work has been done to frustrate these attacks, most designs
  230. protect primarily against traffic analysis rather than traffic
  231. confirmation (see Section&nbsp;<a href="#subsec:threat-model">3.1</a>).
  232. <div class="p"><!----></div>
  233. The simplest low-latency designs are single-hop proxies such as the
  234. <b>Anonymizer</b>&nbsp;[<a href="#anonymizer" name="CITEanonymizer">3</a>]: a single trusted server strips the
  235. data's origin before relaying it. These designs are easy to
  236. analyze, but users must trust the anonymizing proxy.
  237. Concentrating the traffic to this single point increases the anonymity set
  238. (the people a given user is hiding among), but it is vulnerable if the
  239. adversary can observe all traffic entering and leaving the proxy.
  240. <div class="p"><!----></div>
  241. More complex are distributed-trust, circuit-based anonymizing systems.
  242. In these designs, a user establishes one or more medium-term bidirectional
  243. end-to-end circuits, and tunnels data in fixed-size cells.
  244. Establishing circuits is computationally expensive and typically
  245. requires public-key
  246. cryptography, whereas relaying cells is comparatively inexpensive and
  247. typically requires only symmetric encryption.
  248. Because a circuit crosses several servers, and each server only knows
  249. the adjacent servers in the circuit, no single server can link a
  250. user to her communication partners.
  251. <div class="p"><!----></div>
  252. The <b>Java Anon Proxy</b> (also known as JAP or Web MIXes) uses fixed shared
  253. routes known as <em>cascades</em>. As with a single-hop proxy, this
  254. approach aggregates users into larger anonymity sets, but again an
  255. attacker only needs to observe both ends of the cascade to bridge all
  256. the system's traffic. The Java Anon Proxy's design
  257. calls for padding between end users and the head of the
  258. cascade&nbsp;[<a href="#web-mix" name="CITEweb-mix">7</a>]. However, it is not demonstrated whether the current
  259. implementation's padding policy improves anonymity.
  260. <div class="p"><!----></div>
  261. <b>PipeNet</b>&nbsp;[<a href="#back01" name="CITEback01">5</a>,<a href="#pipenet" name="CITEpipenet">12</a>], another low-latency design proposed
  262. around the same time as Onion Routing, gave
  263. stronger anonymity but allowed a single user to shut
  264. down the network by not sending. Systems like <b>ISDN
  265. mixes</b>&nbsp;[<a href="#isdn-mixes" name="CITEisdn-mixes">38</a>] were designed for other environments with
  266. different assumptions.
  267. <div class="p"><!----></div>
  268. In P2P designs like <b>Tarzan</b>&nbsp;[<a href="#tarzan:ccs02" name="CITEtarzan:ccs02">24</a>] and
  269. <b>MorphMix</b>&nbsp;[<a href="#morphmix:fc04" name="CITEmorphmix:fc04">43</a>], all participants both generate
  270. traffic and relay traffic for others. These systems aim to conceal
  271. whether a given peer originated a request
  272. or just relayed it from another peer. While Tarzan and MorphMix use
  273. layered encryption as above, <b>Crowds</b>&nbsp;[<a href="#crowds-tissec" name="CITEcrowds-tissec">42</a>] simply assumes
  274. an adversary who cannot observe the initiator: it uses no public-key
  275. encryption, so any node on a circuit can read users' traffic.
  276. <div class="p"><!----></div>
  277. <b>Hordes</b>&nbsp;[<a href="#hordes-jcs" name="CITEhordes-jcs">34</a>] is based on Crowds but also uses multicast
  278. responses to hide the initiator. <b>Herbivore</b>&nbsp;[<a href="#herbivore" name="CITEherbivore">25</a>] and
  279. <b>P</b><sup><b>5</b></sup>&nbsp;[<a href="#p5" name="CITEp5">46</a>] go even further, requiring broadcast.
  280. These systems are designed primarily for communication among peers,
  281. although Herbivore users can make external connections by
  282. requesting a peer to serve as a proxy.
  283. <div class="p"><!----></div>
  284. Systems like <b>Freedom</b> and the original Onion Routing build circuits
  285. all at once, using a layered "onion" of public-key encrypted messages,
  286. each layer of which provides session keys and the address of the
  287. next server in the circuit. Tor as described herein, Tarzan, MorphMix,
  288. <b>Cebolla</b>&nbsp;[<a href="#cebolla" name="CITEcebolla">9</a>], and Rennhard's <b>Anonymity Network</b>&nbsp;[<a href="#anonnet" name="CITEanonnet">44</a>]
  289. build circuits
  290. in stages, extending them one hop at a time.
  291. Section&nbsp;<a href="#subsubsec:constructing-a-circuit">4.2</a> describes how this
  292. approach enables perfect forward secrecy.
  293. <div class="p"><!----></div>
  294. Circuit-based designs must choose which protocol layer
  295. to anonymize. They may intercept IP packets directly, and
  296. relay them whole (stripping the source address) along the
  297. circuit&nbsp;[<a href="#freedom2-arch" name="CITEfreedom2-arch">8</a>,<a href="#tarzan:ccs02" name="CITEtarzan:ccs02">24</a>]. Like
  298. Tor, they may accept TCP streams and relay the data in those streams,
  299. ignoring the breakdown of that data into TCP
  300. segments&nbsp;[<a href="#morphmix:fc04" name="CITEmorphmix:fc04">43</a>,<a href="#anonnet" name="CITEanonnet">44</a>]. Finally, like Crowds, they may accept
  301. application-level protocols such as HTTP and relay the application
  302. requests themselves.
  303. Making this protocol-layer decision requires a compromise between flexibility
  304. and anonymity. For example, a system that understands HTTP
  305. can strip
  306. identifying information from requests, can take advantage of caching
  307. to limit the number of requests that leave the network, and can batch
  308. or encode requests to minimize the number of connections.
  309. On the other hand, an IP-level anonymizer can handle nearly any protocol,
  310. even ones unforeseen by its designers (though these systems require
  311. kernel-level modifications to some operating systems, and so are more
  312. complex and less portable). TCP-level anonymity networks like Tor present
  313. a middle approach: they are application neutral (so long as the
  314. application supports, or can be tunneled across, TCP), but by treating
  315. application connections as data streams rather than raw TCP packets,
  316. they avoid the inefficiencies of tunneling TCP over
  317. TCP.
  318. <div class="p"><!----></div>
  319. Distributed-trust anonymizing systems need to prevent attackers from
  320. adding too many servers and thus compromising user paths.
  321. Tor relies on a small set of well-known directory servers, run by
  322. independent parties, to decide which nodes can
  323. join. Tarzan and MorphMix allow unknown users to run servers, and use
  324. a limited resource (like IP addresses) to prevent an attacker from
  325. controlling too much of the network. Crowds suggests requiring
  326. written, notarized requests from potential crowd members.
  327. <div class="p"><!----></div>
  328. Anonymous communication is essential for censorship-resistant
  329. systems like Eternity&nbsp;[<a href="#eternity" name="CITEeternity">2</a>], Free&nbsp;Haven&nbsp;[<a href="#freehaven-berk" name="CITEfreehaven-berk">19</a>],
  330. Publius&nbsp;[<a href="#publius" name="CITEpublius">53</a>], and Tangler&nbsp;[<a href="#tangler" name="CITEtangler">52</a>]. Tor's rendezvous
  331. points enable connections between mutually anonymous entities; they
  332. are a building block for location-hidden servers, which are needed by
  333. Eternity and Free&nbsp;Haven.
  334. <div class="p"><!----></div>
  335. <div class="p"><!----></div>
  336. <h2><a name="tth_sEc3">
  337. <a name="sec:assumptions">
  338. 3</a>&nbsp;&nbsp;Design goals and assumptions</h2>
  339. </a>
  340. <div class="p"><!----></div>
  341. <font size="+1"><b>Goals</b></font><br />
  342. Like other low-latency anonymity designs, Tor seeks to frustrate
  343. attackers from linking communication partners, or from linking
  344. multiple communications to or from a single user. Within this
  345. main goal, however, several considerations have directed
  346. Tor's evolution.
  347. <div class="p"><!----></div>
  348. <b>Deployability:</b> The design must be deployed and used in the
  349. real world. Thus it
  350. must not be expensive to run (for example, by requiring more bandwidth
  351. than volunteers are willing to provide); must not place a heavy
  352. liability burden on operators (for example, by allowing attackers to
  353. implicate onion routers in illegal activities); and must not be
  354. difficult or expensive to implement (for example, by requiring kernel
  355. patches, or separate proxies for every protocol). We also cannot
  356. require non-anonymous parties (such as websites)
  357. to run our software. (Our rendezvous point design does not meet
  358. this goal for non-anonymous users talking to hidden servers,
  359. however; see Section&nbsp;<a href="#sec:rendezvous">5</a>.)
  360. <div class="p"><!----></div>
  361. <b>Usability:</b> A hard-to-use system has fewer users &mdash; and because
  362. anonymity systems hide users among users, a system with fewer users
  363. provides less anonymity. Usability is thus not only a convenience:
  364. it is a security requirement&nbsp;[<a href="#econymics" name="CITEeconymics">1</a>,<a href="#back01" name="CITEback01">5</a>]. Tor should
  365. therefore not
  366. require modifying familiar applications; should not introduce prohibitive
  367. delays;
  368. and should require as few configuration decisions
  369. as possible. Finally, Tor should be easily implementable on all common
  370. platforms; we cannot require users to change their operating system
  371. to be anonymous. (Tor currently runs on Win32, Linux,
  372. Solaris, BSD-style Unix, MacOS X, and probably others.)
  373. <div class="p"><!----></div>
  374. <b>Flexibility:</b> The protocol must be flexible and well-specified,
  375. so Tor can serve as a test-bed for future research.
  376. Many of the open problems in low-latency anonymity
  377. networks, such as generating dummy traffic or preventing Sybil
  378. attacks&nbsp;[<a href="#sybil" name="CITEsybil">22</a>], may be solvable independently from the issues
  379. solved by
  380. Tor. Hopefully future systems will not need to reinvent Tor's design.
  381. <div class="p"><!----></div>
  382. <b>Simple design:</b> The protocol's design and security
  383. parameters must be well-understood. Additional features impose implementation
  384. and complexity costs; adding unproven techniques to the design threatens
  385. deployability, readability, and ease of security analysis. Tor aims to
  386. deploy a simple and stable system that integrates the best accepted
  387. approaches to protecting anonymity.<br />
  388. <div class="p"><!----></div>
  389. <font size="+1"><b>Non-goals</b></font><a name="subsec:non-goals">
  390. </a><br />
  391. In favoring simple, deployable designs, we have explicitly deferred
  392. several possible goals, either because they are solved elsewhere, or because
  393. they are not yet solved.
  394. <div class="p"><!----></div>
  395. <b>Not peer-to-peer:</b> Tarzan and MorphMix aim to scale to completely
  396. decentralized peer-to-peer environments with thousands of short-lived
  397. servers, many of which may be controlled by an adversary. This approach
  398. is appealing, but still has many open
  399. problems&nbsp;[<a href="#tarzan:ccs02" name="CITEtarzan:ccs02">24</a>,<a href="#morphmix:fc04" name="CITEmorphmix:fc04">43</a>].
  400. <div class="p"><!----></div>
  401. <b>Not secure against end-to-end attacks:</b> Tor does not claim
  402. to completely solve end-to-end timing or intersection
  403. attacks. Some approaches, such as having users run their own onion routers,
  404. may help;
  405. see Section&nbsp;<a href="#sec:maintaining-anonymity">9</a> for more discussion.
  406. <div class="p"><!----></div>
  407. <b>No protocol normalization:</b> Tor does not provide <em>protocol
  408. normalization</em> like Privoxy or the Anonymizer. If senders want anonymity from
  409. responders while using complex and variable
  410. protocols like HTTP, Tor must be layered with a filtering proxy such
  411. as Privoxy to hide differences between clients, and expunge protocol
  412. features that leak identity.
  413. Note that by this separation Tor can also provide services that
  414. are anonymous to the network yet authenticated to the responder, like
  415. SSH. Similarly, Tor does not integrate
  416. tunneling for non-stream-based protocols like UDP; this must be
  417. provided by an external service if appropriate.
  418. <div class="p"><!----></div>
  419. <b>Not steganographic:</b> Tor does not try to conceal who is connected
  420. to the network.
  421. <div class="p"><!----></div>
  422. <h3><a name="tth_sEc3.1">
  423. <a name="subsec:threat-model">
  424. 3.1</a>&nbsp;&nbsp;Threat Model</h3>
  425. </a>
  426. <div class="p"><!----></div>
  427. A global passive adversary is the most commonly assumed threat when
  428. analyzing theoretical anonymity designs. But like all practical
  429. low-latency systems, Tor does not protect against such a strong
  430. adversary. Instead, we assume an adversary who can observe some fraction
  431. of network traffic; who can generate, modify, delete, or delay
  432. traffic; who can operate onion routers of his own; and who can
  433. compromise some fraction of the onion routers.
  434. <div class="p"><!----></div>
  435. In low-latency anonymity systems that use layered encryption, the
  436. adversary's typical goal is to observe both the initiator and the
  437. responder. By observing both ends, passive attackers can confirm a
  438. suspicion that Alice is
  439. talking to Bob if the timing and volume patterns of the traffic on the
  440. connection are distinct enough; active attackers can induce timing
  441. signatures on the traffic to force distinct patterns. Rather
  442. than focusing on these <em>traffic confirmation</em> attacks,
  443. we aim to prevent <em>traffic
  444. analysis</em> attacks, where the adversary uses traffic patterns to learn
  445. which points in the network he should attack.
  446. <div class="p"><!----></div>
  447. Our adversary might try to link an initiator Alice with her
  448. communication partners, or try to build a profile of Alice's
  449. behavior. He might mount passive attacks by observing the network edges
  450. and correlating traffic entering and leaving the network &mdash; by
  451. relationships in packet timing, volume, or externally visible
  452. user-selected
  453. options. The adversary can also mount active attacks by compromising
  454. routers or keys; by replaying traffic; by selectively denying service
  455. to trustworthy routers to move users to
  456. compromised routers, or denying service to users to see if traffic
  457. elsewhere in the
  458. network stops; or by introducing patterns into traffic that can later be
  459. detected. The adversary might subvert the directory servers to give users
  460. differing views of network state. Additionally, he can try to decrease
  461. the network's reliability by attacking nodes or by performing antisocial
  462. activities from reliable nodes and trying to get them taken down &mdash; making
  463. the network unreliable flushes users to other less anonymous
  464. systems, where they may be easier to attack. We summarize
  465. in Section&nbsp;<a href="#sec:attacks">7</a> how well the Tor design defends against
  466. each of these attacks.
  467. <div class="p"><!----></div>
  468. <div class="p"><!----></div>
  469. <h2><a name="tth_sEc4">
  470. <a name="sec:design">
  471. 4</a>&nbsp;&nbsp;The Tor Design</h2>
  472. </a>
  473. <div class="p"><!----></div>
  474. The Tor network is an overlay network; each onion router (OR)
  475. runs as a normal
  476. user-level process without any special privileges.
  477. Each onion router maintains a TLS&nbsp;[<a href="#TLS" name="CITETLS">17</a>]
  478. connection to every other onion router.
  479. Each user
  480. runs local software called an onion proxy (OP) to fetch directories,
  481. establish circuits across the network,
  482. and handle connections from user applications. These onion proxies accept
  483. TCP streams and multiplex them across the circuits. The onion
  484. router on the other side
  485. of the circuit connects to the requested destinations
  486. and relays data.
  487. <div class="p"><!----></div>
  488. Each onion router maintains a long-term identity key and a short-term
  489. onion key. The identity
  490. key is used to sign TLS certificates, to sign the OR's <em>router
  491. descriptor</em> (a summary of its keys, address, bandwidth, exit policy,
  492. and so on), and (by directory servers) to sign directories. 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. <div class="p"><!----></div>
  498. Section&nbsp;<a href="#subsec:cells">4.1</a> presents the fixed-size
  499. <em>cells</em> that are the unit of communication in Tor. We describe
  500. in Section&nbsp;<a href="#subsec:circuits">4.2</a> how circuits are
  501. built, extended, truncated, and destroyed. Section&nbsp;<a href="#subsec:tcp">4.3</a>
  502. describes how TCP streams are routed through the network. We address
  503. integrity checking in Section&nbsp;<a href="#subsec:integrity-checking">4.4</a>,
  504. and resource limiting in Section&nbsp;<a href="#subsec:rate-limit">4.5</a>.
  505. Finally,
  506. Section&nbsp;<a href="#subsec:congestion">4.6</a> talks about congestion control and
  507. fairness issues.
  508. <div class="p"><!----></div>
  509. <h3><a name="tth_sEc4.1">
  510. <a name="subsec:cells">
  511. 4.1</a>&nbsp;&nbsp;Cells</h3>
  512. </a>
  513. <div class="p"><!----></div>
  514. Onion routers communicate with one another, and with users' OPs, via
  515. TLS connections with ephemeral keys. Using TLS conceals the data on
  516. the connection with perfect forward secrecy, and prevents an attacker
  517. from modifying data on the wire or impersonating an OR.
  518. <div class="p"><!----></div>
  519. Traffic passes along these connections in fixed-size cells. Each cell
  520. is 512 bytes, and consists of a header and a payload. The header includes a circuit
  521. identifier (circID) that specifies which circuit the cell refers to
  522. (many circuits can be multiplexed over the single TLS connection), and
  523. a command to describe what to do with the cell's payload. (Circuit
  524. identifiers are connection-specific: each circuit has a different
  525. circID on each OP/OR or OR/OR connection it traverses.)
  526. Based on their command, cells are either <em>control</em> cells, which are
  527. always interpreted by the node that receives them, or <em>relay</em> cells,
  528. which carry end-to-end stream data. The control cell commands are:
  529. <em>padding</em> (currently used for keepalive, but also usable for link
  530. padding); <em>create</em> or <em>created</em> (used to set up a new circuit);
  531. and <em>destroy</em> (to tear down a circuit).
  532. <div class="p"><!----></div>
  533. Relay cells have an additional header (the relay header) at the front
  534. of the payload, containing a streamID (stream identifier: many streams can
  535. be multiplexed over a circuit); an end-to-end checksum for integrity
  536. checking; the length of the relay payload; and a relay command.
  537. The entire contents of the relay header and the relay cell payload
  538. are encrypted or decrypted together as the relay cell moves along the
  539. circuit, using the 128-bit AES cipher in counter mode to generate a
  540. cipher stream. The relay commands are: <em>relay
  541. data</em> (for data flowing down the stream), <em>relay begin</em> (to open a
  542. stream), <em>relay end</em> (to close a stream cleanly), <em>relay
  543. teardown</em> (to close a broken stream), <em>relay connected</em>
  544. (to notify the OP that a relay begin has succeeded), <em>relay
  545. extend</em> and <em>relay extended</em> (to extend the circuit by a hop,
  546. and to acknowledge), <em>relay truncate</em> and <em>relay truncated</em>
  547. (to tear down only part of the circuit, and to acknowledge), <em>relay
  548. sendme</em> (used for congestion control), and <em>relay drop</em> (used to
  549. implement long-range dummies).
  550. We give a visual overview of cell structure plus the details of relay
  551. cell structure, and then describe each of these cell types and commands
  552. in more detail below.
  553. <div class="p"><!----></div>
  554. <div class="p"><!----></div>
  555. <div class="p"><!----></div>
  556. <a name="tth_fIg1">
  557. </a> <center><img src="cell-struct.png" alt="cell-struct.png" />
  558. </center>
  559. <div class="p"><!----></div>
  560. <h3><a name="tth_sEc4.2">
  561. <a name="subsec:circuits">
  562. 4.2</a>&nbsp;&nbsp;Circuits and streams</h3>
  563. </a>
  564. <div class="p"><!----></div>
  565. Onion Routing originally built one circuit for each
  566. TCP stream. Because building a circuit can take several tenths of a
  567. second (due to public-key cryptography and network latency),
  568. this design imposed high costs on applications like web browsing that
  569. open many TCP streams.
  570. <div class="p"><!----></div>
  571. In Tor, each circuit can be shared by many TCP streams. To avoid
  572. delays, users construct circuits preemptively. To limit linkability
  573. among their streams, users' OPs build a new circuit
  574. periodically if the previous ones have been used,
  575. and expire old used circuits that no longer have any open streams.
  576. OPs consider rotating to a new circuit once a minute: thus
  577. even heavy users spend negligible time
  578. building circuits, but a limited number of requests can be linked
  579. to each other through a given exit node. Also, because circuits are built
  580. in the background, OPs can recover from failed circuit creation
  581. without harming user experience.<br />
  582. <div class="p"><!----></div>
  583. <div class="p"><!----></div>
  584. <a name="tth_fIg1">
  585. </a> <center><img src="interaction.png" alt="interaction.png" />
  586. <center>Figure 1: Alice builds a two-hop circuit and begins fetching a web page.</center>
  587. <a name="fig:interaction">
  588. </a>
  589. </center>
  590. <div class="p"><!----></div>
  591. <a name="subsubsec:constructing-a-circuit"></a>
  592. <font size="+1"><b>Constructing a circuit</b></font>
  593. <br />
  594. A user's OP constructs circuits incrementally, negotiating a
  595. symmetric key with each OR on the circuit, one hop at a time. To begin
  596. creating a new circuit, the OP (call her Alice) sends a
  597. <em>create</em> cell to the first node in her chosen path (call him Bob).
  598. (She chooses a new
  599. circID C<sub>AB</sub> not currently used on the connection from her to Bob.)
  600. The <em>create</em> cell's
  601. payload contains the first half of the Diffie-Hellman handshake
  602. (g<sup>x</sup>), encrypted to the onion key of Bob. Bob
  603. responds with a <em>created</em> cell containing g<sup>y</sup>
  604. along with a hash of the negotiated key K=g<sup>xy</sup>.
  605. <div class="p"><!----></div>
  606. Once the circuit has been established, Alice and Bob can send one
  607. another relay cells encrypted with the negotiated
  608. key.<a href="#tthFtNtAAB" name="tthFrefAAB"><sup>1</sup></a> More detail is given in
  609. the next section.
  610. <div class="p"><!----></div>
  611. To extend the circuit further, Alice sends a <em>relay extend</em> cell
  612. to Bob, specifying the address of the next OR (call her Carol), and
  613. an encrypted g<sup>x<sub>2</sub></sup> for her. Bob copies the half-handshake into a
  614. <em>create</em> cell, and passes it to Carol to extend the circuit.
  615. (Bob chooses a new circID C<sub>BC</sub> not currently used on the connection
  616. between him and Carol. Alice never needs to know this circID; only Bob
  617. associates C<sub>AB</sub> on his connection with Alice to C<sub>BC</sub> on
  618. his connection with Carol.)
  619. When Carol responds with a <em>created</em> cell, Bob wraps the payload
  620. into a <em>relay extended</em> cell and passes it back to Alice. Now
  621. the circuit is extended to Carol, and Alice and Carol share a common key
  622. K<sub>2</sub> = g<sup>x<sub>2</sub> y<sub>2</sub></sup>.
  623. <div class="p"><!----></div>
  624. To extend the circuit to a third node or beyond, Alice
  625. proceeds as above, always telling the last node in the circuit to
  626. extend one hop further.
  627. <div class="p"><!----></div>
  628. This circuit-level handshake protocol achieves unilateral entity
  629. authentication (Alice knows she's handshaking with the OR, but
  630. the OR doesn't care who is opening the circuit &mdash; Alice uses no public key
  631. and remains anonymous) and unilateral key authentication
  632. (Alice and the OR agree on a key, and Alice knows only the OR learns
  633. it). It also achieves forward
  634. secrecy and key freshness. More formally, the protocol is as follows
  635. (where E<sub>PK<sub>Bob</sub></sub>(&#183;) is encryption with Bob's public key,
  636. H is a secure hash function, and <font face="symbol">|</font
  637. > is concatenation):
  638. <div class="p"><!----></div>
  639. <a name="tth_tAb1">
  640. </a>
  641. <table>
  642. <tr><td align="right">Alice </td><td align="center">-&#62; </td><td align="center">Bob </td><td>: E<sub>PK<sub>Bob</sub></sub>(g<sup>x</sup>) </td></tr>
  643. <tr><td align="right">Bob </td><td align="center">-&#62; </td><td align="center">Alice </td><td>: g<sup>y</sup>, H(K <font face="symbol">|</font
  644. > "<span class="roman">handshake</span>")
  645. </td></tr></table>
  646. <div class="p"><!----></div>
  647. In the second step, Bob proves that it was he who received g<sup>x</sup>,
  648. and who chose y. We use PK encryption in the first step
  649. (rather than, say, using the first two steps of STS, which has a
  650. signature in the second step) because a single cell is too small to
  651. hold both a public key and a signature. Preliminary analysis with the
  652. NRL protocol analyzer&nbsp;[<a href="#meadows96" name="CITEmeadows96">35</a>] shows this protocol to be
  653. secure (including perfect forward secrecy) under the
  654. traditional Dolev-Yao model.<br />
  655. <div class="p"><!----></div>
  656. <font size="+1"><b>Relay cells</b></font><br />
  657. Once Alice has established the circuit (so she shares keys with each
  658. OR on the circuit), she can send relay cells.
  659. Upon receiving a relay
  660. cell, an OR looks up the corresponding circuit, and decrypts the relay
  661. header and payload with the session key for that circuit.
  662. If the cell is headed away from Alice the OR then checks whether the
  663. decrypted cell has a valid digest (as an optimization, the first
  664. two bytes of the integrity check are zero, so in most cases we can avoid
  665. computing the hash).
  666. If valid, it accepts the relay cell and processes it as described
  667. below. Otherwise,
  668. the OR looks up the circID and OR for the
  669. next step in the circuit, replaces the circID as appropriate, and
  670. sends the decrypted relay cell to the next OR. (If the OR at the end
  671. of the circuit receives an unrecognized relay cell, an error has
  672. occurred, and the circuit is torn down.)
  673. <div class="p"><!----></div>
  674. OPs treat incoming relay cells similarly: they iteratively unwrap the
  675. relay header and payload with the session keys shared with each
  676. OR on the circuit, from the closest to farthest.
  677. If at any stage the digest is valid, the cell must have
  678. originated at the OR whose encryption has just been removed.
  679. <div class="p"><!----></div>
  680. To construct a relay cell addressed to a given OR, Alice assigns the
  681. digest, and then iteratively
  682. encrypts the cell payload (that is, the relay header and payload) with
  683. the symmetric key of each hop up to that OR. Because the digest is
  684. encrypted to a different value at each step, only at the targeted OR
  685. will it have a meaningful value.<a href="#tthFtNtAAC" name="tthFrefAAC"><sup>2</sup></a>
  686. This <em>leaky pipe</em> circuit topology
  687. allows Alice's streams to exit at different ORs on a single circuit.
  688. Alice may choose different exit points because of their exit policies,
  689. or to keep the ORs from knowing that two streams
  690. originate from the same person.
  691. <div class="p"><!----></div>
  692. When an OR later replies to Alice with a relay cell, it
  693. encrypts the cell's relay header and payload with the single key it
  694. shares with Alice, and sends the cell back toward Alice along the
  695. circuit. Subsequent ORs add further layers of encryption as they
  696. relay the cell back to Alice.
  697. <div class="p"><!----></div>
  698. To tear down a circuit, Alice sends a <em>destroy</em> control
  699. cell. Each OR in the circuit receives the <em>destroy</em> cell, closes
  700. all streams on that circuit, and passes a new <em>destroy</em> cell
  701. forward. But just as circuits are built incrementally, they can also
  702. be torn down incrementally: Alice can send a <em>relay
  703. truncate</em> cell to a single OR on a circuit. That OR then sends a
  704. <em>destroy</em> cell forward, and acknowledges with a
  705. <em>relay truncated</em> cell. Alice can then extend the circuit to
  706. different nodes, without signaling to the intermediate nodes (or
  707. a limited observer) that she has changed her circuit.
  708. Similarly, if a node on the circuit goes down, the adjacent
  709. node can send a <em>relay truncated</em> cell back to Alice. Thus the
  710. "break a node and see which circuits go down"
  711. attack&nbsp;[<a href="#freedom21-security" name="CITEfreedom21-security">4</a>] is weakened.
  712. <div class="p"><!----></div>
  713. <h3><a name="tth_sEc4.3">
  714. <a name="subsec:tcp">
  715. 4.3</a>&nbsp;&nbsp;Opening and closing streams</h3>
  716. </a>
  717. <div class="p"><!----></div>
  718. When Alice's application wants a TCP connection to a given
  719. address and port, it asks the OP (via SOCKS) to make the
  720. connection. The OP chooses the newest open circuit (or creates one if
  721. needed), and chooses a suitable OR on that circuit to be the
  722. exit node (usually the last node, but maybe others due to exit policy
  723. conflicts; see Section&nbsp;<a href="#subsec:exitpolicies">6.2</a>.) The OP then opens
  724. the stream by sending a <em>relay begin</em> cell to the exit node,
  725. using a new random streamID. Once the
  726. exit node connects to the remote host, it responds
  727. with a <em>relay connected</em> cell. Upon receipt, the OP sends a
  728. SOCKS reply to notify the application of its success. The OP
  729. now accepts data from the application's TCP stream, packaging it into
  730. <em>relay data</em> cells and sending those cells along the circuit to
  731. the chosen OR.
  732. <div class="p"><!----></div>
  733. There's a catch to using SOCKS, however &mdash; some applications pass the
  734. alphanumeric hostname to the Tor client, while others resolve it into
  735. an IP address first and then pass the IP address to the Tor client. If
  736. the application does DNS resolution first, Alice thereby reveals her
  737. destination to the remote DNS server, rather than sending the hostname
  738. through the Tor network to be resolved at the far end. Common applications
  739. like Mozilla and SSH have this flaw.
  740. <div class="p"><!----></div>
  741. With Mozilla, the flaw is easy to address: the filtering HTTP
  742. proxy called Privoxy gives a hostname to the Tor client, so Alice's
  743. computer never does DNS resolution.
  744. But a portable general solution, such as is needed for
  745. SSH, is
  746. an open problem. Modifying or replacing the local nameserver
  747. can be invasive, brittle, and unportable. Forcing the resolver
  748. library to prefer TCP rather than UDP is hard, and also has
  749. portability problems. Dynamically intercepting system calls to the
  750. resolver library seems a promising direction. We could also provide
  751. a tool similar to <em>dig</em> to perform a private lookup through the
  752. Tor network. Currently, we encourage the use of privacy-aware proxies
  753. like Privoxy wherever possible.
  754. <div class="p"><!----></div>
  755. Closing a Tor stream is analogous to closing a TCP stream: it uses a
  756. two-step handshake for normal operation, or a one-step handshake for
  757. errors. If the stream closes abnormally, the adjacent node simply sends a
  758. <em>relay teardown</em> cell. If the stream closes normally, the node sends
  759. a <em>relay end</em> cell down the circuit, and the other side responds with
  760. its own <em>relay end</em> cell. Because
  761. all relay cells use layered encryption, only the destination OR knows
  762. that a given relay cell is a request to close a stream. This two-step
  763. handshake allows Tor to support TCP-based applications that use half-closed
  764. connections.
  765. <div class="p"><!----></div>
  766. <h3><a name="tth_sEc4.4">
  767. <a name="subsec:integrity-checking">
  768. 4.4</a>&nbsp;&nbsp;Integrity checking on streams</h3>
  769. </a>
  770. <div class="p"><!----></div>
  771. Because the old Onion Routing design used a stream cipher without integrity
  772. checking, traffic was
  773. vulnerable to a malleability attack: though the attacker could not
  774. decrypt cells, any changes to encrypted data
  775. would create corresponding changes to the data leaving the network.
  776. This weakness allowed an adversary who could guess the encrypted content
  777. to change a padding cell to a destroy
  778. cell; change the destination address in a <em>relay begin</em> cell to the
  779. adversary's webserver; or change an FTP command from
  780. <tt>dir</tt> to <tt>rm&nbsp;*</tt>. (Even an external
  781. adversary could do this, because the link encryption similarly used a
  782. stream cipher.)
  783. <div class="p"><!----></div>
  784. Because Tor uses TLS on its links, external adversaries cannot modify
  785. data. Addressing the insider malleability attack, however, is
  786. more complex.
  787. <div class="p"><!----></div>
  788. We could do integrity checking of the relay cells at each hop, either
  789. by including hashes or by using an authenticating cipher mode like
  790. EAX&nbsp;[<a href="#eax" name="CITEeax">6</a>], but there are some problems. First, these approaches
  791. impose a message-expansion overhead at each hop, and so we would have to
  792. either leak the path length or waste bytes by padding to a maximum
  793. path length. Second, these solutions can only verify traffic coming
  794. from Alice: ORs would not be able to produce suitable hashes for
  795. the intermediate hops, since the ORs on a circuit do not know the
  796. other ORs' session keys. Third, we have already accepted that our design
  797. is vulnerable to end-to-end timing attacks; so tagging attacks performed
  798. within the circuit provide no additional information to the attacker.
  799. <div class="p"><!----></div>
  800. Thus, we check integrity only at the edges of each stream. (Remember that
  801. in our leaky-pipe circuit topology, a stream's edge could be any hop
  802. in the circuit.) When Alice
  803. negotiates a key with a new hop, they each initialize a SHA-1
  804. digest with a derivative of that key,
  805. thus beginning with randomness that only the two of them know.
  806. Then they each incrementally add to the SHA-1 digest the contents of
  807. all relay cells they create, and include with each relay cell the
  808. first four bytes of the current digest. Each also keeps a SHA-1
  809. digest of data received, to verify that the received hashes are correct.
  810. <div class="p"><!----></div>
  811. To be sure of removing or modifying a cell, the attacker must be able
  812. to deduce the current digest state (which depends on all
  813. traffic between Alice and Bob, starting with their negotiated key).
  814. Attacks on SHA-1 where the adversary can incrementally add to a hash
  815. to produce a new valid hash don't work, because all hashes are
  816. end-to-end encrypted across the circuit. The computational overhead
  817. of computing the digests is minimal compared to doing the AES
  818. encryption performed at each hop of the circuit. We use only four
  819. bytes per cell to minimize overhead; the chance that an adversary will
  820. correctly guess a valid hash
  821. is
  822. acceptably low, given that the OP or OR tear down the circuit if they
  823. receive a bad hash.
  824. <div class="p"><!----></div>
  825. <h3><a name="tth_sEc4.5">
  826. <a name="subsec:rate-limit">
  827. 4.5</a>&nbsp;&nbsp;Rate limiting and fairness</h3>
  828. </a>
  829. <div class="p"><!----></div>
  830. Volunteers are more willing to run services that can limit
  831. their bandwidth usage. To accommodate them, Tor servers use a
  832. token bucket approach&nbsp;[<a href="#tannenbaum96" name="CITEtannenbaum96">50</a>] to
  833. enforce a long-term average rate of incoming bytes, while still
  834. permitting short-term bursts above the allowed bandwidth.
  835. <div class="p"><!----></div>
  836. <div class="p"><!----></div>
  837. Because the Tor protocol outputs about the same number of bytes as it
  838. takes in, it is sufficient in practice to limit only incoming bytes.
  839. With TCP streams, however, the correspondence is not one-to-one:
  840. relaying a single incoming byte can require an entire 512-byte cell.
  841. (We can't just wait for more bytes, because the local application may
  842. be awaiting a reply.) Therefore, we treat this case as if the entire
  843. cell size had been read, regardless of the cell's fullness.
  844. <div class="p"><!----></div>
  845. Further, inspired by Rennhard et al's design in&nbsp;[<a href="#anonnet" name="CITEanonnet">44</a>], a
  846. circuit's edges can heuristically distinguish interactive streams from bulk
  847. streams by comparing the frequency with which they supply cells. We can
  848. provide good latency for interactive streams by giving them preferential
  849. service, while still giving good overall throughput to the bulk
  850. streams. Such preferential treatment presents a possible end-to-end
  851. attack, but an adversary observing both
  852. ends of the stream can already learn this information through timing
  853. attacks.
  854. <div class="p"><!----></div>
  855. <h3><a name="tth_sEc4.6">
  856. <a name="subsec:congestion">
  857. 4.6</a>&nbsp;&nbsp;Congestion control</h3>
  858. </a>
  859. <div class="p"><!----></div>
  860. Even with bandwidth rate limiting, we still need to worry about
  861. congestion, either accidental or intentional. If enough users choose the
  862. same OR-to-OR connection for their circuits, that connection can become
  863. saturated. For example, an attacker could send a large file
  864. through the Tor network to a webserver he runs, and then
  865. refuse to read any of the bytes at the webserver end of the
  866. circuit. Without some congestion control mechanism, these bottlenecks
  867. can propagate back through the entire network. We don't need to
  868. reimplement full TCP windows (with sequence numbers,
  869. the ability to drop cells when we're full and retransmit later, and so
  870. on),
  871. because TCP already guarantees in-order delivery of each
  872. cell.
  873. We describe our response below.
  874. <div class="p"><!----></div>
  875. <b>Circuit-level throttling:</b>
  876. To control a circuit's bandwidth usage, each OR keeps track of two
  877. windows. The <em>packaging window</em> tracks how many relay data cells the OR is
  878. allowed to package (from incoming TCP streams) for transmission back to the OP,
  879. and the <em>delivery window</em> tracks how many relay data cells it is willing
  880. to deliver to TCP streams outside the network. Each window is initialized
  881. (say, to 1000 data cells). When a data cell is packaged or delivered,
  882. the appropriate window is decremented. When an OR has received enough
  883. data cells (currently 100), it sends a <em>relay sendme</em> cell towards the OP,
  884. with streamID zero. When an OR receives a <em>relay sendme</em> cell with
  885. streamID zero, it increments its packaging window. Either of these cells
  886. increments the corresponding window by 100. If the packaging window
  887. reaches 0, the OR stops reading from TCP connections for all streams
  888. on the corresponding circuit, and sends no more relay data cells until
  889. receiving a <em>relay sendme</em> cell.
  890. <div class="p"><!----></div>
  891. The OP behaves identically, except that it must track a packaging window
  892. and a delivery window for every OR in the circuit. If a packaging window
  893. reaches 0, it stops reading from streams destined for that OR.
  894. <div class="p"><!----></div>
  895. <b>Stream-level throttling</b>:
  896. The stream-level congestion control mechanism is similar to the
  897. circuit-level mechanism. ORs and OPs use <em>relay sendme</em> cells
  898. to implement end-to-end flow control for individual streams across
  899. circuits. Each stream begins with a packaging window (currently 500 cells),
  900. and increments the window by a fixed value (50) upon receiving a <em>relay
  901. sendme</em> cell. Rather than always returning a <em>relay sendme</em> cell as soon
  902. as enough cells have arrived, the stream-level congestion control also
  903. has to check whether data has been successfully flushed onto the TCP
  904. stream; it sends the <em>relay sendme</em> cell only when the number of bytes pending
  905. to be flushed is under some threshold (currently 10 cells' worth).
  906. <div class="p"><!----></div>
  907. <div class="p"><!----></div>
  908. These arbitrarily chosen parameters seem to give tolerable throughput
  909. and delay; see Section&nbsp;<a href="#sec:in-the-wild">8</a>.
  910. <div class="p"><!----></div>
  911. <h2><a name="tth_sEc5">
  912. <a name="sec:rendezvous">
  913. 5</a>&nbsp;&nbsp;Rendezvous Points and hidden services</h2>
  914. </a>
  915. <div class="p"><!----></div>
  916. Rendezvous points are a building block for <em>location-hidden
  917. services</em> (also known as <em>responder anonymity</em>) in the Tor
  918. network. Location-hidden services allow Bob to offer a TCP
  919. service, such as a webserver, without revealing his IP address.
  920. This type of anonymity protects against distributed DoS attacks:
  921. attackers are forced to attack the onion routing network
  922. because they do not know Bob's IP address.
  923. <div class="p"><!----></div>
  924. Our design for location-hidden servers has the following goals.
  925. <b>Access-control:</b> Bob needs a way to filter incoming requests,
  926. so an attacker cannot flood Bob simply by making many connections to him.
  927. <b>Robustness:</b> Bob should be able to maintain a long-term pseudonymous
  928. identity even in the presence of router failure. Bob's service must
  929. not be tied to a single OR, and Bob must be able to migrate his service
  930. across ORs. <b>Smear-resistance:</b>
  931. A social attacker
  932. should not be able to "frame" a rendezvous router by
  933. offering an illegal or disreputable location-hidden service and
  934. making observers believe the router created that service.
  935. <b>Application-transparency:</b> Although we require users
  936. to run special software to access location-hidden servers, we must not
  937. require them to modify their applications.
  938. <div class="p"><!----></div>
  939. We provide location-hiding for Bob by allowing him to advertise
  940. several onion routers (his <em>introduction points</em>) as contact
  941. points. He may do this on any robust efficient
  942. key-value lookup system with authenticated updates, such as a
  943. distributed hash table (DHT) like CFS&nbsp;[<a href="#cfs:sosp01" name="CITEcfs:sosp01">11</a>].<a href="#tthFtNtAAD" name="tthFrefAAD"><sup>3</sup></a> Alice, the client, chooses an OR as her
  944. <em>rendezvous point</em>. She connects to one of Bob's introduction
  945. points, informs him of her rendezvous point, and then waits for him
  946. to connect to the rendezvous point. This extra level of indirection
  947. helps Bob's introduction points avoid problems associated with serving
  948. unpopular files directly (for example, if Bob serves
  949. material that the introduction point's community finds objectionable,
  950. or if Bob's service tends to get attacked by network vandals).
  951. The extra level of indirection also allows Bob to respond to some requests
  952. and ignore others.
  953. <div class="p"><!----></div>
  954. <h3><a name="tth_sEc5.1">
  955. 5.1</a>&nbsp;&nbsp;Rendezvous points in Tor</h3>
  956. <div class="p"><!----></div>
  957. The following steps are
  958. performed on behalf of Alice and Bob by their local OPs;
  959. application integration is described more fully below.
  960. <div class="p"><!----></div>
  961. <dl compact="compact">
  962. <dt><b></b></dt>
  963. <dd><li>Bob generates a long-term public key pair to identify his service.</dd>
  964. <dt><b></b></dt>
  965. <dd><li>Bob chooses some introduction points, and advertises them on
  966. the lookup service, signing the advertisement with his public key. He
  967. can add more later.</dd>
  968. <dt><b></b></dt>
  969. <dd><li>Bob builds a circuit to each of his introduction points, and tells
  970. them to wait for requests.</dd>
  971. <dt><b></b></dt>
  972. <dd><li>Alice learns about Bob's service out of band (perhaps Bob told her,
  973. or she found it on a website). She retrieves the details of Bob's
  974. service from the lookup service. If Alice wants to access Bob's
  975. service anonymously, she must connect to the lookup service via Tor.</dd>
  976. <dt><b></b></dt>
  977. <dd><li>Alice chooses an OR as the rendezvous point (RP) for her connection to
  978. Bob's service. She builds a circuit to the RP, and gives it a
  979. randomly chosen "rendezvous cookie" to recognize Bob.</dd>
  980. <dt><b></b></dt>
  981. <dd><li>Alice opens an anonymous stream to one of Bob's introduction
  982. points, and gives it a message (encrypted with Bob's public key)
  983. telling it about herself,
  984. her RP and rendezvous cookie, and the
  985. start of a DH
  986. handshake. The introduction point sends the message to Bob.</dd>
  987. <dt><b></b></dt>
  988. <dd><li>If Bob wants to talk to Alice, he builds a circuit to Alice's
  989. RP and sends the rendezvous cookie, the second half of the DH
  990. handshake, and a hash of the session
  991. key they now share. By the same argument as in
  992. Section&nbsp;<a href="#subsubsec:constructing-a-circuit">4.2</a>, Alice knows she
  993. shares the key only with Bob.</dd>
  994. <dt><b></b></dt>
  995. <dd><li>The RP connects Alice's circuit to Bob's. Note that RP can't
  996. recognize Alice, Bob, or the data they transmit.</dd>
  997. <dt><b></b></dt>
  998. <dd><li>Alice sends a <em>relay begin</em> cell along the circuit. It
  999. arrives at Bob's OP, which connects to Bob's
  1000. webserver.</dd>
  1001. <dt><b></b></dt>
  1002. <dd><li>An anonymous stream has been established, and Alice and Bob
  1003. communicate as normal.
  1004. </dd>
  1005. </dl>
  1006. <div class="p"><!----></div>
  1007. When establishing an introduction point, Bob provides the onion router
  1008. with the public key identifying his service. Bob signs his
  1009. messages, so others cannot usurp his introduction point
  1010. in the future. He uses the same public key to establish the other
  1011. introduction points for his service, and periodically refreshes his
  1012. entry in the lookup service.
  1013. <div class="p"><!----></div>
  1014. The message that Alice gives
  1015. the introduction point includes a hash of Bob's public key and an optional initial authorization token (the
  1016. introduction point can do prescreening, for example to block replays). Her
  1017. message to Bob may include an end-to-end authorization token so Bob
  1018. can choose whether to respond.
  1019. The authorization tokens can be used to provide selective access:
  1020. important users can get uninterrupted access.
  1021. During normal situations, Bob's service might simply be offered
  1022. directly from mirrors, while Bob gives out tokens to high-priority users. If
  1023. the mirrors are knocked down,
  1024. those users can switch to accessing Bob's service via
  1025. the Tor rendezvous system.
  1026. <div class="p"><!----></div>
  1027. Bob's introduction points are themselves subject to DoS &mdash; he must
  1028. open many introduction points or risk such an attack.
  1029. He can provide selected users with a current list or future schedule of
  1030. unadvertised introduction points;
  1031. this is most practical
  1032. if there is a stable and large group of introduction points
  1033. available. Bob could also give secret public keys
  1034. for consulting the lookup service. All of these approaches
  1035. limit exposure even when
  1036. some selected users collude in the DoS.
  1037. <div class="p"><!----></div>
  1038. <h3><a name="tth_sEc5.2">
  1039. 5.2</a>&nbsp;&nbsp;Integration with user applications</h3>
  1040. <div class="p"><!----></div>
  1041. Bob configures his onion proxy to know the local IP address and port of his
  1042. service, a strategy for authorizing clients, and his public key. The onion
  1043. proxy anonymously publishes a signed statement of Bob's
  1044. public key, an expiration time, and
  1045. the current introduction points for his service onto the lookup service,
  1046. indexed
  1047. by the hash of his public key. Bob's webserver is unmodified,
  1048. and doesn't even know that it's hidden behind the Tor network.
  1049. <div class="p"><!----></div>
  1050. Alice's applications also work unchanged &mdash; her client interface
  1051. remains a SOCKS proxy. We encode all of the necessary information
  1052. into the fully qualified domain name (FQDN) Alice uses when establishing her
  1053. connection. Location-hidden services use a virtual top level domain
  1054. called <tt>.onion</tt>: thus hostnames take the form <tt>x.y.onion</tt> where
  1055. <tt>x</tt> is the authorization cookie and <tt>y</tt> encodes the hash of
  1056. the public key. Alice's onion proxy
  1057. examines addresses; if they're destined for a hidden server, it decodes
  1058. the key and starts the rendezvous as described above.
  1059. <div class="p"><!----></div>
  1060. <h3><a name="tth_sEc5.3">
  1061. 5.3</a>&nbsp;&nbsp;Previous rendezvous work</h3>
  1062. <div class="p"><!----></div>
  1063. Rendezvous points in low-latency anonymity systems were first
  1064. described for use in ISDN telephony&nbsp;[<a href="#jerichow-jsac98" name="CITEjerichow-jsac98">30</a>,<a href="#isdn-mixes" name="CITEisdn-mixes">38</a>].
  1065. Later low-latency designs used rendezvous points for hiding location
  1066. of mobile phones and low-power location
  1067. trackers&nbsp;[<a href="#federrath-ih96" name="CITEfederrath-ih96">23</a>,<a href="#reed-protocols97" name="CITEreed-protocols97">40</a>]. Rendezvous for
  1068. anonymizing low-latency
  1069. Internet connections was suggested in early Onion Routing
  1070. work&nbsp;[<a href="#or-ih96" name="CITEor-ih96">27</a>], but the first published design was by Ian
  1071. Goldberg&nbsp;[<a href="#ian-thesis" name="CITEian-thesis">26</a>]. His design differs from
  1072. ours in three ways. First, Goldberg suggests that Alice should manually
  1073. hunt down a current location of the service via Gnutella; our approach
  1074. makes lookup transparent to the user, as well as faster and more robust.
  1075. Second, in Tor the client and server negotiate session keys
  1076. with Diffie-Hellman, so plaintext is not exposed even at the rendezvous
  1077. point. Third,
  1078. our design minimizes the exposure from running the
  1079. service, to encourage volunteers to offer introduction and rendezvous
  1080. services. Tor's introduction points do not output any bytes to the
  1081. clients; the rendezvous points don't know the client or the server,
  1082. and can't read the data being transmitted. The indirection scheme is
  1083. also designed to include authentication/authorization &mdash; if Alice doesn't
  1084. include the right cookie with her request for service, Bob need not even
  1085. acknowledge his existence.
  1086. <div class="p"><!----></div>
  1087. <h2><a name="tth_sEc6">
  1088. <a name="sec:other-design">
  1089. 6</a>&nbsp;&nbsp;Other design decisions</h2>
  1090. </a>
  1091. <div class="p"><!----></div>
  1092. <h3><a name="tth_sEc6.1">
  1093. <a name="subsec:dos">
  1094. 6.1</a>&nbsp;&nbsp;Denial of service</h3>
  1095. </a>
  1096. <div class="p"><!----></div>
  1097. Providing Tor as a public service creates many opportunities for
  1098. denial-of-service attacks against the network. While
  1099. flow control and rate limiting (discussed in
  1100. Section&nbsp;<a href="#subsec:congestion">4.6</a>) prevent users from consuming more
  1101. bandwidth than routers are willing to provide, opportunities remain for
  1102. users to
  1103. consume more network resources than their fair share, or to render the
  1104. network unusable for others.
  1105. <div class="p"><!----></div>
  1106. First of all, there are several CPU-consuming denial-of-service
  1107. attacks wherein an attacker can force an OR to perform expensive
  1108. cryptographic operations. For example, an attacker can
  1109. fake the start of a TLS handshake, forcing the OR to carry out its
  1110. (comparatively expensive) half of the handshake at no real computational
  1111. cost to the attacker.
  1112. <div class="p"><!----></div>
  1113. We have not yet implemented any defenses for these attacks, but several
  1114. approaches are possible. First, ORs can
  1115. require clients to solve a puzzle&nbsp;[<a href="#puzzles-tls" name="CITEpuzzles-tls">16</a>] while beginning new
  1116. TLS handshakes or accepting <em>create</em> cells. So long as these
  1117. tokens are easy to verify and computationally expensive to produce, this
  1118. approach limits the attack multiplier. Additionally, ORs can limit
  1119. the rate at which they accept <em>create</em> cells and TLS connections,
  1120. so that
  1121. the computational work of processing them does not drown out the
  1122. symmetric cryptography operations that keep cells
  1123. flowing. This rate limiting could, however, allow an attacker
  1124. to slow down other users when they build new circuits.
  1125. <div class="p"><!----></div>
  1126. <div class="p"><!----></div>
  1127. Adversaries can also attack the Tor network's hosts and network
  1128. links. Disrupting a single circuit or link breaks all streams passing
  1129. along that part of the circuit. Users similarly lose service
  1130. when a router crashes or its operator restarts it. The current
  1131. Tor design treats such attacks as intermittent network failures, and
  1132. depends on users and applications to respond or recover as appropriate. A
  1133. future design could use an end-to-end TCP-like acknowledgment protocol,
  1134. so no streams are lost unless the entry or exit point is
  1135. disrupted. This solution would require more buffering at the network
  1136. edges, however, and the performance and anonymity implications from this
  1137. extra complexity still require investigation.
  1138. <div class="p"><!----></div>
  1139. <h3><a name="tth_sEc6.2">
  1140. <a name="subsec:exitpolicies">
  1141. 6.2</a>&nbsp;&nbsp;Exit policies and abuse</h3>
  1142. </a>
  1143. <div class="p"><!----></div>
  1144. <div class="p"><!----></div>
  1145. Exit abuse is a serious barrier to wide-scale Tor deployment. Anonymity
  1146. presents would-be vandals and abusers with an opportunity to hide
  1147. the origins of their activities. Attackers can harm the Tor network by
  1148. implicating exit servers for their abuse. Also, applications that commonly
  1149. use IP-based authentication (such as institutional mail or webservers)
  1150. can be fooled by the fact that anonymous connections appear to originate
  1151. at the exit OR.
  1152. <div class="p"><!----></div>
  1153. We stress that Tor does not enable any new class of abuse. Spammers
  1154. and other attackers already have access to thousands of misconfigured
  1155. systems worldwide, and the Tor network is far from the easiest way
  1156. to launch attacks.
  1157. But because the
  1158. onion routers can be mistaken for the originators of the abuse,
  1159. and the volunteers who run them may not want to deal with the hassle of
  1160. explaining anonymity networks to irate administrators, we must block or limit
  1161. abuse through the Tor network.
  1162. <div class="p"><!----></div>
  1163. To mitigate abuse issues, each onion router's <em>exit policy</em>
  1164. describes to which external addresses and ports the router will
  1165. connect. On one end of the spectrum are <em>open exit</em>
  1166. nodes that will connect anywhere. On the other end are <em>middleman</em>
  1167. nodes that only relay traffic to other Tor nodes, and <em>private exit</em>
  1168. nodes that only connect to a local host or network. A private
  1169. exit can allow a client to connect to a given host or
  1170. network more securely &mdash; an external adversary cannot eavesdrop traffic
  1171. between the private exit and the final destination, and so is less sure of
  1172. Alice's destination and activities. Most onion routers in the current
  1173. network function as
  1174. <em>restricted exits</em> that permit connections to the world at large,
  1175. but prevent access to certain abuse-prone addresses and services such
  1176. as SMTP.
  1177. The OR might also be able to authenticate clients to
  1178. prevent exit abuse without harming anonymity&nbsp;[<a href="#or-discex00" name="CITEor-discex00">48</a>].
  1179. <div class="p"><!----></div>
  1180. <div class="p"><!----></div>
  1181. Many administrators use port restrictions to support only a
  1182. limited set of services, such as HTTP, SSH, or AIM.
  1183. This is not a complete solution, of course, since abuse opportunities for these
  1184. protocols are still well known.
  1185. <div class="p"><!----></div>
  1186. We have not yet encountered any abuse in the deployed network, but if
  1187. we do we should consider using proxies to clean traffic for certain
  1188. protocols as it leaves the network. For example, much abusive HTTP
  1189. behavior (such as exploiting buffer overflows or well-known script
  1190. vulnerabilities) can be detected in a straightforward manner.
  1191. Similarly, one could run automatic spam filtering software (such as
  1192. SpamAssassin) on email exiting the OR network.
  1193. <div class="p"><!----></div>
  1194. ORs may also rewrite exiting traffic to append
  1195. headers or other information indicating that the traffic has passed
  1196. through an anonymity service. This approach is commonly used
  1197. by email-only anonymity systems. ORs can also
  1198. run on servers with hostnames like <tt>anonymous</tt> to further
  1199. alert abuse targets to the nature of the anonymous traffic.
  1200. <div class="p"><!----></div>
  1201. A mixture of open and restricted exit nodes allows the most
  1202. flexibility for volunteers running servers. But while having many
  1203. middleman nodes provides a large and robust network,
  1204. having only a few exit nodes reduces the number of points
  1205. an adversary needs to monitor for traffic analysis, and places a
  1206. greater burden on the exit nodes. This tension can be seen in the
  1207. Java Anon Proxy
  1208. cascade model, wherein only one node in each cascade needs to handle
  1209. abuse complaints &mdash; but an adversary only needs to observe the entry
  1210. and exit of a cascade to perform traffic analysis on all that
  1211. cascade's users. The hydra model (many entries, few exits) presents a
  1212. different compromise: only a few exit nodes are needed, but an
  1213. adversary needs to work harder to watch all the clients; see
  1214. Section&nbsp;<a href="#sec:conclusion">10</a>.
  1215. <div class="p"><!----></div>
  1216. Finally, we note that exit abuse must not be dismissed as a peripheral
  1217. issue: when a system's public image suffers, it can reduce the number
  1218. and diversity of that system's users, and thereby reduce the anonymity
  1219. of the system itself. Like usability, public perception is a
  1220. security parameter. Sadly, preventing abuse of open exit nodes is an
  1221. unsolved problem, and will probably remain an arms race for the
  1222. foreseeable future. The abuse problems faced by Princeton's CoDeeN
  1223. project&nbsp;[<a href="#darkside" name="CITEdarkside">37</a>] give us a glimpse of likely issues.
  1224. <div class="p"><!----></div>
  1225. <h3><a name="tth_sEc6.3">
  1226. <a name="subsec:dirservers">
  1227. 6.3</a>&nbsp;&nbsp;Directory Servers</h3>
  1228. </a>
  1229. <div class="p"><!----></div>
  1230. First-generation Onion Routing designs&nbsp;[<a href="#freedom2-arch" name="CITEfreedom2-arch">8</a>,<a href="#or-jsac98" name="CITEor-jsac98">41</a>] used
  1231. in-band network status updates: each router flooded a signed statement
  1232. to its neighbors, which propagated it onward. But anonymizing networks
  1233. have different security goals than typical link-state routing protocols.
  1234. For example, delays (accidental or intentional)
  1235. that can cause different parts of the network to have different views
  1236. of link-state and topology are not only inconvenient: they give
  1237. attackers an opportunity to exploit differences in client knowledge.
  1238. We also worry about attacks to deceive a
  1239. client about the router membership list, topology, or current network
  1240. state. Such <em>partitioning attacks</em> on client knowledge help an
  1241. adversary to efficiently deploy resources
  1242. against a target&nbsp;[<a href="#minion-design" name="CITEminion-design">15</a>].
  1243. <div class="p"><!----></div>
  1244. Tor uses a small group of redundant, well-known onion routers to
  1245. track changes in network topology and node state, including keys and
  1246. exit policies. Each such <em>directory server</em> acts as an HTTP
  1247. server, so clients can fetch current network state
  1248. and router lists, and so other ORs can upload
  1249. state information. Onion routers periodically publish signed
  1250. statements of their state to each directory server. The directory servers
  1251. combine this information with their own views of network liveness,
  1252. and generate a signed description (a <em>directory</em>) of the entire
  1253. network state. Client software is
  1254. pre-loaded with a list of the directory servers and their keys,
  1255. to bootstrap each client's view of the network.
  1256. <div class="p"><!----></div>
  1257. When a directory server receives a signed statement for an OR, it
  1258. checks whether the OR's identity key is recognized. Directory
  1259. servers do not advertise unrecognized ORs &mdash; if they did,
  1260. an adversary could take over the network by creating many
  1261. servers&nbsp;[<a href="#sybil" name="CITEsybil">22</a>]. Instead, new nodes must be approved by the
  1262. directory
  1263. server administrator before they are included. Mechanisms for automated
  1264. node approval are an area of active research, and are discussed more
  1265. in Section&nbsp;<a href="#sec:maintaining-anonymity">9</a>.
  1266. <div class="p"><!----></div>
  1267. Of course, a variety of attacks remain. An adversary who controls
  1268. a directory server can track clients by providing them different
  1269. information &mdash; perhaps by listing only nodes under its control, or by
  1270. informing only certain clients about a given node. Even an external
  1271. adversary can exploit differences in client knowledge: clients who use
  1272. a node listed on one directory server but not the others are vulnerable.
  1273. <div class="p"><!----></div>
  1274. Thus these directory servers must be synchronized and redundant, so
  1275. that they can agree on a common directory. Clients should only trust
  1276. this directory if it is signed by a threshold of the directory
  1277. servers.
  1278. <div class="p"><!----></div>
  1279. The directory servers in Tor are modeled after those in
  1280. Mixminion&nbsp;[<a href="#minion-design" name="CITEminion-design">15</a>], but our situation is easier. First,
  1281. we make the
  1282. simplifying assumption that all participants agree on the set of
  1283. directory servers. Second, while Mixminion needs to predict node
  1284. behavior, Tor only needs a threshold consensus of the current
  1285. state of the network. Third, we assume that we can fall back to the
  1286. human administrators to discover and resolve problems when a consensus
  1287. directory cannot be reached. Since there are relatively few directory
  1288. servers (currently 3, but we expect as many as 9 as the network scales),
  1289. we can afford operations like broadcast to simplify the consensus-building
  1290. protocol.
  1291. <div class="p"><!----></div>
  1292. To avoid attacks where a router connects to all the directory servers
  1293. but refuses to relay traffic from other routers, the directory servers
  1294. must also build circuits and use them to anonymously test router
  1295. reliability&nbsp;[<a href="#mix-acc" name="CITEmix-acc">18</a>]. Unfortunately, this defense is not yet
  1296. designed or
  1297. implemented.
  1298. <div class="p"><!----></div>
  1299. Using directory servers is simpler and more flexible than flooding.
  1300. Flooding is expensive, and complicates the analysis when we
  1301. start experimenting with non-clique network topologies. Signed
  1302. directories can be cached by other
  1303. onion routers,
  1304. so directory servers are not a performance
  1305. bottleneck when we have many users, and do not aid traffic analysis by
  1306. forcing clients to announce their existence to any
  1307. central point.
  1308. <div class="p"><!----></div>
  1309. <h2><a name="tth_sEc7">
  1310. <a name="sec:attacks">
  1311. 7</a>&nbsp;&nbsp;Attacks and Defenses</h2>
  1312. </a>
  1313. <div class="p"><!----></div>
  1314. Below we summarize a variety of attacks, and discuss how well our
  1315. design withstands them.<br />
  1316. <div class="p"><!----></div>
  1317. <font size="+1"><b>Passive attacks</b></font><br />
  1318. <em>Observing user traffic patterns.</em> Observing a user's connection
  1319. will not reveal her destination or data, but it will
  1320. reveal traffic patterns (both sent and received). Profiling via user
  1321. connection patterns requires further processing, because multiple
  1322. application streams may be operating simultaneously or in series over
  1323. a single circuit.
  1324. <div class="p"><!----></div>
  1325. <em>Observing user content.</em> While content at the user end is encrypted,
  1326. connections to responders may not be (indeed, the responding website
  1327. itself may be hostile). While filtering content is not a primary goal
  1328. of Onion Routing, Tor can directly use Privoxy and related
  1329. filtering services to anonymize application data streams.
  1330. <div class="p"><!----></div>
  1331. <em>Option distinguishability.</em> We allow clients to choose
  1332. configuration options. For example, clients concerned about request
  1333. linkability should rotate circuits more often than those concerned
  1334. about traceability. Allowing choice may attract users with different
  1335. needs; but clients who are
  1336. in the minority may lose more anonymity by appearing distinct than they
  1337. gain by optimizing their behavior&nbsp;[<a href="#econymics" name="CITEeconymics">1</a>].
  1338. <div class="p"><!----></div>
  1339. <em>End-to-end timing correlation.</em> Tor only minimally hides
  1340. such correlations. An attacker watching patterns of
  1341. traffic at the initiator and the responder will be
  1342. able to confirm the correspondence with high probability. The
  1343. greatest protection currently available against such confirmation is to hide
  1344. the connection between the onion proxy and the first Tor node,
  1345. by running the OP on the Tor node or behind a firewall. This approach
  1346. requires an observer to separate traffic originating at the onion
  1347. router from traffic passing through it: a global observer can do this,
  1348. but it might be beyond a limited observer's capabilities.
  1349. <div class="p"><!----></div>
  1350. <em>End-to-end size correlation.</em> Simple packet counting
  1351. will also be effective in confirming
  1352. endpoints of a stream. However, even without padding, we may have some
  1353. limited protection: the leaky pipe topology means different numbers
  1354. of packets may enter one end of a circuit than exit at the other.
  1355. <div class="p"><!----></div>
  1356. <em>Website fingerprinting.</em> All the effective passive
  1357. attacks above are traffic confirmation attacks,
  1358. which puts them outside our design goals. There is also
  1359. a passive traffic analysis attack that is potentially effective.
  1360. Rather than searching exit connections for timing and volume
  1361. correlations, the adversary may build up a database of
  1362. "fingerprints" containing file sizes and access patterns for
  1363. targeted websites. He can later confirm a user's connection to a given
  1364. site simply by consulting the database. This attack has
  1365. been shown to be effective against SafeWeb&nbsp;[<a href="#hintz-pet02" name="CITEhintz-pet02">29</a>].
  1366. It may be less effective against Tor, since
  1367. streams are multiplexed within the same circuit, and
  1368. fingerprinting will be limited to
  1369. the granularity of cells (currently 512 bytes). Additional
  1370. defenses could include
  1371. larger cell sizes, padding schemes to group websites
  1372. into large sets, and link
  1373. padding or long-range dummies.<a href="#tthFtNtAAE" name="tthFrefAAE"><sup>4</sup></a><br />
  1374. <div class="p"><!----></div>
  1375. <font size="+1"><b>Active attacks</b></font><br />
  1376. <em>Compromise keys.</em> An attacker who learns the TLS session key can
  1377. see control cells and encrypted relay cells on every circuit on that
  1378. connection; learning a circuit
  1379. session key lets him unwrap one layer of the encryption. An attacker
  1380. who learns an OR's TLS private key can impersonate that OR for the TLS
  1381. key's lifetime, but he must
  1382. also learn the onion key to decrypt <em>create</em> cells (and because of
  1383. perfect forward secrecy, he cannot hijack already established circuits
  1384. without also compromising their session keys). Periodic key rotation
  1385. limits the window of opportunity for these attacks. On the other hand,
  1386. an attacker who learns a node's identity key can replace that node
  1387. indefinitely by sending new forged descriptors to the directory servers.
  1388. <div class="p"><!----></div>
  1389. <em>Iterated compromise.</em> A roving adversary who can
  1390. compromise ORs (by system intrusion, legal coercion, or extralegal
  1391. coercion) could march down the circuit compromising the
  1392. nodes until he reaches the end. Unless the adversary can complete
  1393. this attack within the lifetime of the circuit, however, the ORs
  1394. will have discarded the necessary information before the attack can
  1395. be completed. (Thanks to the perfect forward secrecy of session
  1396. keys, the attacker cannot force nodes to decrypt recorded
  1397. traffic once the circuits have been closed.) Additionally, building
  1398. circuits that cross jurisdictions can make legal coercion
  1399. harder &mdash; this phenomenon is commonly called "jurisdictional
  1400. arbitrage." The Java Anon Proxy project recently experienced the
  1401. need for this approach, when
  1402. a German court forced them to add a backdoor to
  1403. their nodes&nbsp;[<a href="#jap-backdoor" name="CITEjap-backdoor">51</a>].
  1404. <div class="p"><!----></div>
  1405. <em>Run a recipient.</em> An adversary running a webserver
  1406. trivially learns the timing patterns of users connecting to it, and
  1407. can introduce arbitrary patterns in its responses.
  1408. End-to-end attacks become easier: if the adversary can induce
  1409. users to connect to his webserver (perhaps by advertising
  1410. content targeted to those users), he now holds one end of their
  1411. connection. There is also a danger that application
  1412. protocols and associated programs can be induced to reveal information
  1413. about the initiator. Tor depends on Privoxy and similar protocol cleaners
  1414. to solve this latter problem.
  1415. <div class="p"><!----></div>
  1416. <em>Run an onion proxy.</em> It is expected that end users will
  1417. nearly always run their own local onion proxy. However, in some
  1418. settings, it may be necessary for the proxy to run
  1419. remotely &mdash; typically, in institutions that want
  1420. to monitor the activity of those connecting to the proxy.
  1421. Compromising an onion proxy compromises all future connections
  1422. through it.
  1423. <div class="p"><!----></div>
  1424. <em>DoS non-observed nodes.</em> An observer who can only watch some
  1425. of the Tor network can increase the value of this traffic
  1426. by attacking non-observed nodes to shut them down, reduce
  1427. their reliability, or persuade users that they are not trustworthy.
  1428. The best defense here is robustness.
  1429. <div class="p"><!----></div>
  1430. <em>Run a hostile OR.</em> In addition to being a local observer,
  1431. an isolated hostile node can create circuits through itself, or alter
  1432. traffic patterns to affect traffic at other nodes. Nonetheless, a hostile
  1433. node must be immediately adjacent to both endpoints to compromise the
  1434. anonymity of a circuit. If an adversary can
  1435. run multiple ORs, and can persuade the directory servers
  1436. that those ORs are trustworthy and independent, then occasionally
  1437. some user will choose one of those ORs for the start and another
  1438. as the end of a circuit. If an adversary
  1439. controls m &gt; 1 of N nodes, he can correlate at most
  1440. ([m/N])<sup>2</sup> of the traffic &mdash; although an
  1441. adversary
  1442. could still attract a disproportionately large amount of traffic
  1443. by running an OR with a permissive exit policy, or by
  1444. degrading the reliability of other routers.
  1445. <div class="p"><!----></div>
  1446. <em>Introduce timing into messages.</em> This is simply a stronger
  1447. version of passive timing attacks already discussed earlier.
  1448. <div class="p"><!----></div>
  1449. <em>Tagging attacks.</em> A hostile node could "tag" a
  1450. cell by altering it. If the
  1451. stream were, for example, an unencrypted request to a Web site,
  1452. the garbled content coming out at the appropriate time would confirm
  1453. the association. However, integrity checks on cells prevent
  1454. this attack.
  1455. <div class="p"><!----></div>
  1456. <em>Replace contents of unauthenticated protocols.</em> When
  1457. relaying an unauthenticated protocol like HTTP, a hostile exit node
  1458. can impersonate the target server. Clients
  1459. should prefer protocols with end-to-end authentication.
  1460. <div class="p"><!----></div>
  1461. <em>Replay attacks.</em> Some anonymity protocols are vulnerable
  1462. to replay attacks. Tor is not; replaying one side of a handshake
  1463. will result in a different negotiated session key, and so the rest
  1464. of the recorded session can't be used.
  1465. <div class="p"><!----></div>
  1466. <em>Smear attacks.</em> An attacker could use the Tor network for
  1467. socially disapproved acts, to bring the
  1468. network into disrepute and get its operators to shut it down.
  1469. Exit policies reduce the possibilities for abuse, but
  1470. ultimately the network requires volunteers who can tolerate
  1471. some political heat.
  1472. <div class="p"><!----></div>
  1473. <em>Distribute hostile code.</em> An attacker could trick users
  1474. into running subverted Tor software that did not, in fact, anonymize
  1475. their connections &mdash; or worse, could trick ORs into running weakened
  1476. software that provided users with less anonymity. We address this
  1477. problem (but do not solve it completely) by signing all Tor releases
  1478. with an official public key, and including an entry in the directory
  1479. that lists which versions are currently believed to be secure. To
  1480. prevent an attacker from subverting the official release itself
  1481. (through threats, bribery, or insider attacks), we provide all
  1482. releases in source code form, encourage source audits, and
  1483. frequently warn our users never to trust any software (even from
  1484. us) that comes without source.<br />
  1485. <div class="p"><!----></div>
  1486. <font size="+1"><b>Directory attacks</b></font><br />
  1487. <em>Destroy directory servers.</em> If a few directory
  1488. servers disappear, the others still decide on a valid
  1489. directory. So long as any directory servers remain in operation,
  1490. they will still broadcast their views of the network and generate a
  1491. consensus directory. (If more than half are destroyed, this
  1492. directory will not, however, have enough signatures for clients to
  1493. use it automatically; human intervention will be necessary for
  1494. clients to decide whether to trust the resulting directory.)
  1495. <div class="p"><!----></div>
  1496. <em>Subvert a directory server.</em> By taking over a directory server,
  1497. an attacker can partially influence the final directory. Since ORs
  1498. are included or excluded by majority vote, the corrupt directory can
  1499. at worst cast a tie-breaking vote to decide whether to include
  1500. marginal ORs. It remains to be seen how often such marginal cases
  1501. occur in practice.
  1502. <div class="p"><!----></div>
  1503. <em>Subvert a majority of directory servers.</em> An adversary who controls
  1504. more than half the directory servers can include as many compromised
  1505. ORs in the final directory as he wishes. We must ensure that directory
  1506. server operators are independent and attack-resistant.
  1507. <div class="p"><!----></div>
  1508. <em>Encourage directory server dissent.</em> The directory
  1509. agreement protocol assumes that directory server operators agree on
  1510. the set of directory servers. An adversary who can persuade some
  1511. of the directory server operators to distrust one another could
  1512. split the quorum into mutually hostile camps, thus partitioning
  1513. users based on which directory they use. Tor does not address
  1514. this attack.
  1515. <div class="p"><!----></div>
  1516. <em>Trick the directory servers into listing a hostile OR.</em>
  1517. Our threat model explicitly assumes directory server operators will
  1518. be able to filter out most hostile ORs.
  1519. <div class="p"><!----></div>
  1520. <em>Convince the directories that a malfunctioning OR is
  1521. working.</em> In the current Tor implementation, directory servers
  1522. assume that an OR is running correctly if they can start a TLS
  1523. connection to it. A hostile OR could easily subvert this test by
  1524. accepting TLS connections from ORs but ignoring all cells. Directory
  1525. servers must actively test ORs by building circuits and streams as
  1526. appropriate. The tradeoffs of a similar approach are discussed
  1527. in&nbsp;[<a href="#mix-acc" name="CITEmix-acc">18</a>].<br />
  1528. <div class="p"><!----></div>
  1529. <font size="+1"><b>Attacks against rendezvous points</b></font><br />
  1530. <em>Make many introduction requests.</em> An attacker could
  1531. try to deny Bob service by flooding his introduction points with
  1532. requests. Because the introduction points can block requests that
  1533. lack authorization tokens, however, Bob can restrict the volume of
  1534. requests he receives, or require a certain amount of computation for
  1535. every request he receives.
  1536. <div class="p"><!----></div>
  1537. <em>Attack an introduction point.</em> An attacker could
  1538. disrupt a location-hidden service by disabling its introduction
  1539. points. But because a service's identity is attached to its public
  1540. key, the service can simply re-advertise
  1541. itself at a different introduction point. Advertisements can also be
  1542. done secretly so that only high-priority clients know the address of
  1543. Bob's introduction points or so that different clients know of different
  1544. introduction points. This forces the attacker to disable all possible
  1545. introduction points.
  1546. <div class="p"><!----></div>
  1547. <em>Compromise an introduction point.</em> An attacker who controls
  1548. Bob's introduction point can flood Bob with
  1549. introduction requests, or prevent valid introduction requests from
  1550. reaching him. Bob can notice a flood, and close the circuit. To notice
  1551. blocking of valid requests, however, he should periodically test the
  1552. introduction point by sending rendezvous requests and making
  1553. sure he receives them.
  1554. <div class="p"><!----></div>
  1555. <em>Compromise a rendezvous point.</em> A rendezvous
  1556. point is no more sensitive than any other OR on
  1557. a circuit, since all data passing through the rendezvous is encrypted
  1558. with a session key shared by Alice and Bob.
  1559. <div class="p"><!----></div>
  1560. <h2><a name="tth_sEc8">
  1561. <a name="sec:in-the-wild">
  1562. 8</a>&nbsp;&nbsp;Early experiences: Tor in the Wild</h2>
  1563. </a>
  1564. <div class="p"><!----></div>
  1565. As of mid-May 2004, the Tor network consists of 32 nodes
  1566. (24 in the US, 8 in Europe), and more are joining each week as the code
  1567. matures. (For comparison, the current remailer network
  1568. has about 40 nodes.) Each node has at least a 768Kb/768Kb connection, and
  1569. many have 10Mb. The number of users varies (and of course, it's hard to
  1570. tell for sure), but we sometimes have several hundred users &mdash; administrators at
  1571. several companies have begun sending their entire departments' web
  1572. traffic through Tor, to block other divisions of
  1573. their company from reading their traffic. Tor users have reported using
  1574. the network for web browsing, FTP, IRC, AIM, Kazaa, SSH, and
  1575. recipient-anonymous email via rendezvous points. One user has anonymously
  1576. set up a Wiki as a hidden service, where other users anonymously publish
  1577. the addresses of their hidden services.
  1578. <div class="p"><!----></div>
  1579. Each Tor node currently processes roughly 800,000 relay
  1580. cells (a bit under half a gigabyte) per week. On average, about 80%
  1581. of each 498-byte payload is full for cells going back to the client,
  1582. whereas about 40% is full for cells coming from the client. (The difference
  1583. arises because most of the network's traffic is web browsing.) Interactive
  1584. traffic like SSH brings down the average a lot &mdash; once we have more
  1585. experience, and assuming we can resolve the anonymity issues, we may
  1586. partition traffic into two relay cell sizes: one to handle
  1587. bulk traffic and one for interactive traffic.
  1588. <div class="p"><!----></div>
  1589. Based in part on our restrictive default exit policy (we
  1590. reject SMTP requests) and our low profile, we have had no abuse
  1591. issues since the network was deployed in October
  1592. 2003. Our slow growth rate gives us time to add features,
  1593. resolve bugs, and get a feel for what users actually want from an
  1594. anonymity system. Even though having more users would bolster our
  1595. anonymity sets, we are not eager to attract the Kazaa or warez
  1596. communities &mdash; we feel that we must build a reputation for privacy, human
  1597. rights, research, and other socially laudable activities.
  1598. <div class="p"><!----></div>
  1599. As for performance, profiling shows that Tor spends almost
  1600. all its CPU time in AES, which is fast. Current latency is attributable
  1601. to two factors. First, network latency is critical: we are
  1602. intentionally bouncing traffic around the world several times. Second,
  1603. our end-to-end congestion control algorithm focuses on protecting
  1604. volunteer servers from accidental DoS rather than on optimizing
  1605. performance. To quantify these effects, we did some informal tests using a network of 4
  1606. nodes on the same machine (a heavily loaded 1GHz Athlon). We downloaded a 60
  1607. megabyte file from <tt>debian.org</tt> every 30 minutes for 54 hours (108 sample
  1608. points). It arrived in about 300 seconds on average, compared to 210s for a
  1609. direct download. We ran a similar test on the production Tor network,
  1610. fetching the front page of <tt>cnn.com</tt> (55 kilobytes):
  1611. while a direct
  1612. download consistently took about 0.3s, the performance through Tor varied.
  1613. Some downloads were as fast as 0.4s, with a median at 2.8s, and
  1614. 90% finishing within 5.3s. It seems that as the network expands, the chance
  1615. of building a slow circuit (one that includes a slow or heavily loaded node
  1616. or link) is increasing. On the other hand, as our users remain satisfied
  1617. with this increased latency, we can address our performance incrementally as we
  1618. proceed with development.
  1619. <div class="p"><!----></div>
  1620. <div class="p"><!----></div>
  1621. <div class="p"><!----></div>
  1622. Although Tor's clique topology and full-visibility directories present
  1623. scaling problems, we still expect the network to support a few hundred
  1624. nodes and maybe 10,000 users before we're forced to become
  1625. more distributed. With luck, the experience we gain running the current
  1626. topology will help us choose among alternatives when the time comes.
  1627. <div class="p"><!----></div>
  1628. <h2><a name="tth_sEc9">
  1629. <a name="sec:maintaining-anonymity">
  1630. 9</a>&nbsp;&nbsp;Open Questions in Low-latency Anonymity</h2>
  1631. </a>
  1632. <div class="p"><!----></div>
  1633. In addition to the non-goals in
  1634. Section&nbsp;<a href="#subsec:non-goals">3</a>, many questions must be solved
  1635. before we can be confident of Tor's security.
  1636. <div class="p"><!----></div>
  1637. Many of these open issues are questions of balance. For example,
  1638. how often should users rotate to fresh circuits? Frequent rotation
  1639. is inefficient, expensive, and may lead to intersection attacks and
  1640. predecessor attacks&nbsp;[<a href="#wright03" name="CITEwright03">54</a>], but infrequent rotation makes the
  1641. user's traffic linkable. Besides opening fresh circuits, clients can
  1642. also exit from the middle of the circuit,
  1643. or truncate and re-extend the circuit. More analysis is
  1644. needed to determine the proper tradeoff.
  1645. <div class="p"><!----></div>
  1646. <div class="p"><!----></div>
  1647. How should we choose path lengths? If Alice always uses two hops,
  1648. then both ORs can be certain that by colluding they will learn about
  1649. Alice and Bob. In our current approach, Alice always chooses at least
  1650. three nodes unrelated to herself and her destination.
  1651. Should Alice choose a random path length (e.g.&nbsp;from a geometric
  1652. distribution) to foil an attacker who
  1653. uses timing to learn that he is the fifth hop and thus concludes that
  1654. both Alice and the responder are running ORs?
  1655. <div class="p"><!----></div>
  1656. Throughout this paper, we have assumed that end-to-end traffic
  1657. confirmation will immediately and automatically defeat a low-latency
  1658. anonymity system. Even high-latency anonymity systems can be
  1659. vulnerable to end-to-end traffic confirmation, if the traffic volumes
  1660. are high enough, and if users' habits are sufficiently
  1661. distinct&nbsp;[<a href="#statistical-disclosure" name="CITEstatistical-disclosure">14</a>,<a href="#limits-open" name="CITElimits-open">31</a>]. Can anything be
  1662. done to
  1663. make low-latency systems resist these attacks as well as high-latency
  1664. systems? Tor already makes some effort to conceal the starts and ends of
  1665. streams by wrapping long-range control commands in identical-looking
  1666. relay cells. Link padding could frustrate passive observers who count
  1667. packets; long-range padding could work against observers who own the
  1668. first hop in a circuit. But more research remains to find an efficient
  1669. and practical approach. Volunteers prefer not to run constant-bandwidth
  1670. padding; but no convincing traffic shaping approach has been
  1671. specified. Recent work on long-range padding&nbsp;[<a href="#defensive-dropping" name="CITEdefensive-dropping">33</a>]
  1672. shows promise. One could also try to reduce correlation in packet timing
  1673. by batching and re-ordering packets, but it is unclear whether this could
  1674. improve anonymity without introducing so much latency as to render the
  1675. network unusable.
  1676. <div class="p"><!----></div>
  1677. A cascade topology may better defend against traffic confirmation by
  1678. aggregating users, and making padding and
  1679. mixing more affordable. Does the hydra topology (many input nodes,
  1680. few output nodes) work better against some adversaries? Are we going
  1681. to get a hydra anyway because most nodes will be middleman nodes?
  1682. <div class="p"><!----></div>
  1683. Common wisdom suggests that Alice should run her own OR for best
  1684. anonymity, because traffic coming from her node could plausibly have
  1685. come from elsewhere. How much mixing does this approach need? Is it
  1686. immediately beneficial because of real-world adversaries that can't
  1687. observe Alice's router, but can run routers of their own?
  1688. <div class="p"><!----></div>
  1689. To scale to many users, and to prevent an attacker from observing the
  1690. whole network, it may be necessary
  1691. to support far more servers than Tor currently anticipates.
  1692. This introduces several issues. First, if approval by a central set
  1693. of directory servers is no longer feasible, what mechanism should be used
  1694. to prevent adversaries from signing up many colluding servers? Second,
  1695. if clients can no longer have a complete picture of the network,
  1696. how can they perform discovery while preventing attackers from
  1697. manipulating or exploiting gaps in their knowledge? Third, if there
  1698. are too many servers for every server to constantly communicate with
  1699. every other, which non-clique topology should the network use?
  1700. (Restricted-route topologies promise comparable anonymity with better
  1701. scalability&nbsp;[<a href="#danezis-pets03" name="CITEdanezis-pets03">13</a>], but whatever topology we choose, we
  1702. need some way to keep attackers from manipulating their position within
  1703. it&nbsp;[<a href="#casc-rep" name="CITEcasc-rep">21</a>].) Fourth, if no central authority is tracking
  1704. server reliability, how do we stop unreliable servers from making
  1705. the network unusable? Fifth, do clients receive so much anonymity
  1706. from running their own ORs that we should expect them all to do
  1707. so&nbsp;[<a href="#econymics" name="CITEeconymics">1</a>], or do we need another incentive structure to
  1708. motivate them? Tarzan and MorphMix present possible solutions.
  1709. <div class="p"><!----></div>
  1710. <div class="p"><!----></div>
  1711. When a Tor node goes down, all its circuits (and thus streams) must break.
  1712. Will users abandon the system because of this brittleness? How well
  1713. does the method in Section&nbsp;<a href="#subsec:dos">6.1</a> allow streams to survive
  1714. node failure? If affected users rebuild circuits immediately, how much
  1715. anonymity is lost? It seems the problem is even worse in a peer-to-peer
  1716. environment &mdash; such systems don't yet provide an incentive for peers to
  1717. stay connected when they're done retrieving content, so we would expect
  1718. a higher churn rate.
  1719. <div class="p"><!----></div>
  1720. <div class="p"><!----></div>
  1721. <h2><a name="tth_sEc10">
  1722. <a name="sec:conclusion">
  1723. 10</a>&nbsp;&nbsp;Future Directions</h2>
  1724. </a>
  1725. <div class="p"><!----></div>
  1726. Tor brings together many innovations into a unified deployable system. The
  1727. next immediate steps include:
  1728. <div class="p"><!----></div>
  1729. <em>Scalability:</em> Tor's emphasis on deployability and design simplicity
  1730. has led us to adopt a clique topology, semi-centralized
  1731. directories, and a full-network-visibility model for client
  1732. knowledge. These properties will not scale past a few hundred servers.
  1733. Section&nbsp;<a href="#sec:maintaining-anonymity">9</a> describes some promising
  1734. approaches, but more deployment experience will be helpful in learning
  1735. the relative importance of these bottlenecks.
  1736. <div class="p"><!----></div>
  1737. <em>Bandwidth classes:</em> This paper assumes that all ORs have
  1738. good bandwidth and latency. We should instead adopt the MorphMix model,
  1739. where nodes advertise their bandwidth level (DSL, T1, T3), and
  1740. Alice avoids bottlenecks by choosing nodes that match or
  1741. exceed her bandwidth. In this way DSL users can usefully join the Tor
  1742. network.
  1743. <div class="p"><!----></div>
  1744. <em>Incentives:</em> Volunteers who run nodes are rewarded with publicity
  1745. and possibly better anonymity&nbsp;[<a href="#econymics" name="CITEeconymics">1</a>]. More nodes means increased
  1746. scalability, and more users can mean more anonymity. We need to continue
  1747. examining the incentive structures for participating in Tor. Further,
  1748. we need to explore more approaches to limiting abuse, and understand
  1749. why most people don't bother using privacy systems.
  1750. <div class="p"><!----></div>
  1751. <em>Cover traffic:</em> Currently Tor omits cover traffic &mdash; its costs
  1752. in performance and bandwidth are clear but its security benefits are
  1753. not well understood. We must pursue more research on link-level cover
  1754. traffic and long-range cover traffic to determine whether some simple padding
  1755. method offers provable protection against our chosen adversary.
  1756. <div class="p"><!----></div>
  1757. <div class="p"><!----></div>
  1758. <em>Caching at exit nodes:</em> Perhaps each exit node should run a
  1759. caching web proxy&nbsp;[<a href="#shsm03" name="CITEshsm03">47</a>], to improve anonymity for cached pages
  1760. (Alice's request never
  1761. leaves the Tor network), to improve speed, and to reduce bandwidth cost.
  1762. On the other hand, forward security is weakened because caches
  1763. constitute a record of retrieved files. We must find the right
  1764. balance between usability and security.
  1765. <div class="p"><!----></div>
  1766. <em>Better directory distribution:</em>
  1767. Clients currently download a description of
  1768. the entire network every 15 minutes. As the state grows larger
  1769. and clients more numerous, we may need a solution in which
  1770. clients receive incremental updates to directory state.
  1771. More generally, we must find more
  1772. scalable yet practical ways to distribute up-to-date snapshots of
  1773. network status without introducing new attacks.
  1774. <div class="p"><!----></div>
  1775. <em>Further specification review:</em> Our public
  1776. byte-level specification&nbsp;[<a href="#tor-spec" name="CITEtor-spec">20</a>] needs
  1777. external review. We hope that as Tor
  1778. is deployed, more people will examine its
  1779. specification.
  1780. <div class="p"><!----></div>
  1781. <em>Multisystem interoperability:</em> We are currently working with the
  1782. designer of MorphMix to unify the specification and implementation of
  1783. the common elements of our two systems. So far, this seems
  1784. to be relatively straightforward. Interoperability will allow testing
  1785. and direct comparison of the two designs for trust and scalability.
  1786. <div class="p"><!----></div>
  1787. <em>Wider-scale deployment:</em> The original goal of Tor was to
  1788. gain experience in deploying an anonymizing overlay network, and
  1789. learn from having actual users. We are now at a point in design
  1790. and development where we can start deploying a wider network. Once
  1791. we have many actual users, we will doubtlessly be better
  1792. able to evaluate some of our design decisions, including our
  1793. robustness/latency tradeoffs, our performance tradeoffs (including
  1794. cell size), our abuse-prevention mechanisms, and
  1795. our overall usability.
  1796. <div class="p"><!----></div>
  1797. <div class="p"><!----></div>
  1798. <h2>Acknowledgments</h2>
  1799. We thank Peter Palfrader, Geoff Goodell, Adam Shostack, Joseph Sokol-Margolis,
  1800. John Bashinski, and Zack Brown
  1801. for editing and comments;
  1802. Matej Pfajfar, Andrei Serjantov, Marc Rennhard for design discussions;
  1803. Bram Cohen for congestion control discussions;
  1804. Adam Back for suggesting telescoping circuits; and
  1805. Cathy Meadows for formal analysis of the <em>extend</em> protocol.
  1806. This work has been supported by ONR and DARPA.
  1807. <div class="p"><!----></div>
  1808. <div class="p"><!----></div>
  1809. <div class="p"><!----></div>
  1810. <h2>References</h2>
  1811. <dl compact="compact">
  1812. <font size="-1"></font> <dt><a href="#CITEeconymics" name="econymics">[1]</a></dt><dd>
  1813. A.&nbsp;Acquisti, R.&nbsp;Dingledine, and P.&nbsp;Syverson.
  1814. On the economics of anonymity.
  1815. In R.&nbsp;N. Wright, editor, <em>Financial Cryptography</em>.
  1816. Springer-Verlag, LNCS 2742, 2003.
  1817. <div class="p"><!----></div>
  1818. </dd>
  1819. <dt><a href="#CITEeternity" name="eternity">[2]</a></dt><dd>
  1820. R.&nbsp;Anderson.
  1821. The eternity service.
  1822. In <em>Pragocrypt '96</em>, 1996.
  1823. <div class="p"><!----></div>
  1824. </dd>
  1825. <dt><a href="#CITEanonymizer" name="anonymizer">[3]</a></dt><dd>
  1826. The Anonymizer.
  1827. <tt>&lt;http://anonymizer.com/&#62;.
  1828. <div class="p"><!----></div>
  1829. </tt></dd>
  1830. <dt><a href="#CITEfreedom21-security" name="freedom21-security">[4]</a></dt><dd>
  1831. A.&nbsp;Back, I.&nbsp;Goldberg, and A.&nbsp;Shostack.
  1832. Freedom systems 2.1 security issues and analysis.
  1833. White paper, Zero Knowledge Systems, Inc., May 2001.
  1834. <div class="p"><!----></div>
  1835. </dd>
  1836. <dt><a href="#CITEback01" name="back01">[5]</a></dt><dd>
  1837. A.&nbsp;Back, U.&nbsp;M&#246;ller, and A.&nbsp;Stiglic.
  1838. Traffic analysis attacks and trade-offs in anonymity providing
  1839. systems.
  1840. In I.&nbsp;S. Moskowitz, editor, <em>Information Hiding (IH 2001)</em>, pages
  1841. 245-257. Springer-Verlag, LNCS 2137, 2001.
  1842. <div class="p"><!----></div>
  1843. </dd>
  1844. <dt><a href="#CITEeax" name="eax">[6]</a></dt><dd>
  1845. M.&nbsp;Bellare, P.&nbsp;Rogaway, and D.&nbsp;Wagner.
  1846. The EAX mode of operation: A two-pass authenticated-encryption
  1847. scheme optimized for simplicity and efficiency.
  1848. In <em>Fast Software Encryption 2004</em>, February 2004.
  1849. <div class="p"><!----></div>
  1850. </dd>
  1851. <dt><a href="#CITEweb-mix" name="web-mix">[7]</a></dt><dd>
  1852. O.&nbsp;Berthold, H.&nbsp;Federrath, and S.&nbsp;K&#246;psell.
  1853. Web MIXes: A system for anonymous and unobservable Internet
  1854. access.
  1855. In H.&nbsp;Federrath, editor, <em>Designing Privacy Enhancing
  1856. Technologies: Workshop on Design Issue in Anonymity and Unobservability</em>.
  1857. Springer-Verlag, LNCS 2009, 2000.
  1858. <div class="p"><!----></div>
  1859. </dd>
  1860. <dt><a href="#CITEfreedom2-arch" name="freedom2-arch">[8]</a></dt><dd>
  1861. P.&nbsp;Boucher, A.&nbsp;Shostack, and I.&nbsp;Goldberg.
  1862. Freedom systems 2.0 architecture.
  1863. White paper, Zero Knowledge Systems, Inc., December 2000.
  1864. <div class="p"><!----></div>
  1865. </dd>
  1866. <dt><a href="#CITEcebolla" name="cebolla">[9]</a></dt><dd>
  1867. Z.&nbsp;Brown.
  1868. Cebolla: Pragmatic IP Anonymity.
  1869. In <em>Ottawa Linux Symposium</em>, June 2002.
  1870. <div class="p"><!----></div>
  1871. </dd>
  1872. <dt><a href="#CITEchaum-mix" name="chaum-mix">[10]</a></dt><dd>
  1873. D.&nbsp;Chaum.
  1874. Untraceable electronic mail, return addresses, and digital
  1875. pseudo-nyms.
  1876. <em>Communications of the ACM</em>, 4(2), February 1981.
  1877. <div class="p"><!----></div>
  1878. </dd>
  1879. <dt><a href="#CITEcfs:sosp01" name="cfs:sosp01">[11]</a></dt><dd>
  1880. F.&nbsp;Dabek, M.&nbsp;F. Kaashoek, D.&nbsp;Karger, R.&nbsp;Morris, and I.&nbsp;Stoica.
  1881. Wide-area cooperative storage with CFS.
  1882. In <em>18th ACM Symposium on Operating Systems Principles
  1883. (SOSP '01)</em>, Chateau Lake Louise, Banff, Canada, October 2001.
  1884. <div class="p"><!----></div>
  1885. </dd>
  1886. <dt><a href="#CITEpipenet" name="pipenet">[12]</a></dt><dd>
  1887. W.&nbsp;Dai.
  1888. Pipenet 1.1.
  1889. Usenet post, August 1996.
  1890. <tt>&lt;http://www.eskimo.com/&nbsp;weidai/pipenet.txt&#62; First mentioned in a
  1891. post to the cypherpunks list, Feb.&nbsp;1995.
  1892. <div class="p"><!----></div>
  1893. </tt></dd>
  1894. <dt><a href="#CITEdanezis-pets03" name="danezis-pets03">[13]</a></dt><dd>
  1895. G.&nbsp;Danezis.
  1896. Mix-networks with restricted routes.
  1897. In R.&nbsp;Dingledine, editor, <em>Privacy Enhancing Technologies (PET
  1898. 2003)</em>. Springer-Verlag LNCS 2760, 2003.
  1899. <div class="p"><!----></div>
  1900. </dd>
  1901. <dt><a href="#CITEstatistical-disclosure" name="statistical-disclosure">[14]</a></dt><dd>
  1902. G.&nbsp;Danezis.
  1903. Statistical disclosure attacks.
  1904. In <em>Security and Privacy in the Age of Uncertainty (SEC2003)</em>,
  1905. pages 421-426, Athens, May 2003. IFIP TC11, Kluwer.
  1906. <div class="p"><!----></div>
  1907. </dd>
  1908. <dt><a href="#CITEminion-design" name="minion-design">[15]</a></dt><dd>
  1909. G.&nbsp;Danezis, R.&nbsp;Dingledine, and N.&nbsp;Mathewson.
  1910. Mixminion: Design of a type III anonymous remailer protocol.
  1911. In <em>2003 IEEE Symposium on Security and Privacy</em>, pages 2-15.
  1912. IEEE CS, May 2003.
  1913. <div class="p"><!----></div>
  1914. </dd>
  1915. <dt><a href="#CITEpuzzles-tls" name="puzzles-tls">[16]</a></dt><dd>
  1916. D.&nbsp;Dean and A.&nbsp;Stubblefield.
  1917. Using Client Puzzles to Protect TLS.
  1918. In <em>Proceedings of the 10th USENIX Security Symposium</em>. USENIX,
  1919. Aug. 2001.
  1920. <div class="p"><!----></div>
  1921. </dd>
  1922. <dt><a href="#CITETLS" name="TLS">[17]</a></dt><dd>
  1923. T.&nbsp;Dierks and C.&nbsp;Allen.
  1924. The TLS Protocol - Version 1.0.
  1925. IETF RFC 2246, January 1999.
  1926. <div class="p"><!----></div>
  1927. </dd>
  1928. <dt><a href="#CITEmix-acc" name="mix-acc">[18]</a></dt><dd>
  1929. R.&nbsp;Dingledine, M.&nbsp;J. Freedman, D.&nbsp;Hopwood, and D.&nbsp;Molnar.
  1930. A Reputation System to Increase MIX-net Reliability.
  1931. In I.&nbsp;S. Moskowitz, editor, <em>Information Hiding (IH 2001)</em>, pages
  1932. 126-141. Springer-Verlag, LNCS 2137, 2001.
  1933. <div class="p"><!----></div>
  1934. </dd>
  1935. <dt><a href="#CITEfreehaven-berk" name="freehaven-berk">[19]</a></dt><dd>
  1936. R.&nbsp;Dingledine, M.&nbsp;J. Freedman, and D.&nbsp;Molnar.
  1937. The free haven project: Distributed anonymous storage service.
  1938. In H.&nbsp;Federrath, editor, <em>Designing Privacy Enhancing
  1939. Technologies: Workshop on Design Issue in Anonymity and Unobservability</em>.
  1940. Springer-Verlag, LNCS 2009, July 2000.
  1941. <div class="p"><!----></div>
  1942. </dd>
  1943. <dt><a href="#CITEtor-spec" name="tor-spec">[20]</a></dt><dd>
  1944. R.&nbsp;Dingledine and N.&nbsp;Mathewson.
  1945. Tor protocol specifications.
  1946. <tt>&lt;http://freehaven.net/tor/tor-spec.txt&#62;.
  1947. <div class="p"><!----></div>
  1948. </tt></dd>
  1949. <dt><a href="#CITEcasc-rep" name="casc-rep">[21]</a></dt><dd>
  1950. R.&nbsp;Dingledine and P.&nbsp;Syverson.
  1951. Reliable MIX Cascade Networks through Reputation.
  1952. In M.&nbsp;Blaze, editor, <em>Financial Cryptography</em>. Springer-Verlag,
  1953. LNCS 2357, 2002.
  1954. <div class="p"><!----></div>
  1955. </dd>
  1956. <dt><a href="#CITEsybil" name="sybil">[22]</a></dt><dd>
  1957. J.&nbsp;Douceur.
  1958. The Sybil Attack.
  1959. In <em>Proceedings of the 1st International Peer To Peer Systems
  1960. Workshop (IPTPS)</em>, Mar. 2002.
  1961. <div class="p"><!----></div>
  1962. </dd>
  1963. <dt><a href="#CITEfederrath-ih96" name="federrath-ih96">[23]</a></dt><dd>
  1964. H.&nbsp;Federrath, A.&nbsp;Jerichow, and A.&nbsp;Pfitzmann.
  1965. MIXes in mobile communication systems: Location management with
  1966. privacy.
  1967. In R.&nbsp;Anderson, editor, <em>Information Hiding, First International
  1968. Workshop</em>, pages 121-135. Springer-Verlag, LNCS 1174, May 1996.
  1969. <div class="p"><!----></div>
  1970. </dd>
  1971. <dt><a href="#CITEtarzan:ccs02" name="tarzan:ccs02">[24]</a></dt><dd>
  1972. M.&nbsp;J. Freedman and R.&nbsp;Morris.
  1973. Tarzan: A peer-to-peer anonymizing network layer.
  1974. In <em>9th ACM Conference on Computer and Communications
  1975. Security (CCS 2002)</em>, Washington, DC, November 2002.
  1976. <div class="p"><!----></div>
  1977. </dd>
  1978. <dt><a href="#CITEherbivore" name="herbivore">[25]</a></dt><dd>
  1979. S.&nbsp;Goel, M.&nbsp;Robson, M.&nbsp;Polte, and E.&nbsp;G. Sirer.
  1980. Herbivore: A scalable and efficient protocol for anonymous
  1981. communication.
  1982. Technical Report TR2003-1890, Cornell University Computing and
  1983. Information Science, February 2003.
  1984. <div class="p"><!----></div>
  1985. </dd>
  1986. <dt><a href="#CITEian-thesis" name="ian-thesis">[26]</a></dt><dd>
  1987. I.&nbsp;Goldberg.
  1988. <em>A Pseudonymous Communications Infrastructure for the Internet</em>.
  1989. PhD thesis, UC Berkeley, Dec 2000.
  1990. <div class="p"><!----></div>
  1991. </dd>
  1992. <dt><a href="#CITEor-ih96" name="or-ih96">[27]</a></dt><dd>
  1993. D.&nbsp;M. Goldschlag, M.&nbsp;G. Reed, and P.&nbsp;F. Syverson.
  1994. Hiding routing information.
  1995. In R.&nbsp;Anderson, editor, <em>Information Hiding, First International
  1996. Workshop</em>, pages 137-150. Springer-Verlag, LNCS 1174, May 1996.
  1997. <div class="p"><!----></div>
  1998. </dd>
  1999. <dt><a href="#CITEbabel" name="babel">[28]</a></dt><dd>
  2000. C.&nbsp;G&#252;lc&#252; and G.&nbsp;Tsudik.
  2001. Mixing E-mail with Babel.
  2002. In <em>Network and Distributed Security Symposium (NDSS 96)</em>,
  2003. pages 2-16. IEEE, February 1996.
  2004. <div class="p"><!----></div>
  2005. </dd>
  2006. <dt><a href="#CITEhintz-pet02" name="hintz-pet02">[29]</a></dt><dd>
  2007. A.&nbsp;Hintz.
  2008. Fingerprinting websites using traffic analysis.
  2009. In R.&nbsp;Dingledine and P.&nbsp;Syverson, editors, <em>Privacy Enhancing
  2010. Technologies (PET 2002)</em>, pages 171-178. Springer-Verlag, LNCS 2482, 2002.
  2011. <div class="p"><!----></div>
  2012. </dd>
  2013. <dt><a href="#CITEjerichow-jsac98" name="jerichow-jsac98">[30]</a></dt><dd>
  2014. A.&nbsp;Jerichow, J.&nbsp;M&#252;ller, A.&nbsp;Pfitzmann, B.&nbsp;Pfitzmann, and M.&nbsp;Waidner.
  2015. Real-time mixes: A bandwidth-efficient anonymity protocol.
  2016. <em>IEEE Journal on Selected Areas in Communications</em>,
  2017. 16(4):495-509, May 1998.
  2018. <div class="p"><!----></div>
  2019. </dd>
  2020. <dt><a href="#CITElimits-open" name="limits-open">[31]</a></dt><dd>
  2021. D.&nbsp;Kesdogan, D.&nbsp;Agrawal, and S.&nbsp;Penz.
  2022. Limits of anonymity in open environments.
  2023. In F.&nbsp;Petitcolas, editor, <em>Information Hiding Workshop (IH
  2024. 2002)</em>. Springer-Verlag, LNCS 2578, October 2002.
  2025. <div class="p"><!----></div>
  2026. </dd>
  2027. <dt><a href="#CITEsocks4" name="socks4">[32]</a></dt><dd>
  2028. D.&nbsp;Koblas and M.&nbsp;R. Koblas.
  2029. SOCKS.
  2030. In <em>UNIX Security III Symposium (1992 USENIX Security
  2031. Symposium)</em>, pages 77-83. USENIX, 1992.
  2032. <div class="p"><!----></div>
  2033. </dd>
  2034. <dt><a href="#CITEdefensive-dropping" name="defensive-dropping">[33]</a></dt><dd>
  2035. B.&nbsp;N. Levine, M.&nbsp;K. Reiter, C.&nbsp;Wang, and M.&nbsp;Wright.
  2036. Timing analysis in low-latency mix-based systems.
  2037. In A.&nbsp;Juels, editor, <em>Financial Cryptography</em>. Springer-Verlag,
  2038. LNCS (forthcoming), 2004.
  2039. <div class="p"><!----></div>
  2040. </dd>
  2041. <dt><a href="#CITEhordes-jcs" name="hordes-jcs">[34]</a></dt><dd>
  2042. B.&nbsp;N. Levine and C.&nbsp;Shields.
  2043. Hordes: A multicast-based protocol for anonymity.
  2044. <em>Journal of Computer Security</em>, 10(3):213-240, 2002.
  2045. <div class="p"><!----></div>
  2046. </dd>
  2047. <dt><a href="#CITEmeadows96" name="meadows96">[35]</a></dt><dd>
  2048. C.&nbsp;Meadows.
  2049. The NRL protocol analyzer: An overview.
  2050. <em>Journal of Logic Programming</em>, 26(2):113-131, 1996.
  2051. <div class="p"><!----></div>
  2052. </dd>
  2053. <dt><a href="#CITEmixmaster-spec" name="mixmaster-spec">[36]</a></dt><dd>
  2054. U.&nbsp;M&#246;ller, L.&nbsp;Cottrell, P.&nbsp;Palfrader, and L.&nbsp;Sassaman.
  2055. Mixmaster Protocol - Version 2.
  2056. Draft, July 2003.
  2057. <tt>&lt;http://www.abditum.com/mixmaster-spec.txt&#62;.
  2058. <div class="p"><!----></div>
  2059. </tt></dd>
  2060. <dt><a href="#CITEdarkside" name="darkside">[37]</a></dt><dd>
  2061. V.&nbsp;S. Pai, L.&nbsp;Wang, K.&nbsp;Park, R.&nbsp;Pang, and L.&nbsp;Peterson.
  2062. The Dark Side of the Web: An Open Proxy's View.
  2063. <tt>&lt;http://codeen.cs.princeton.edu/&#62;.
  2064. <div class="p"><!----></div>
  2065. </tt></dd>
  2066. <dt><a href="#CITEisdn-mixes" name="isdn-mixes">[38]</a></dt><dd>
  2067. A.&nbsp;Pfitzmann, B.&nbsp;Pfitzmann, and M.&nbsp;Waidner.
  2068. ISDN-mixes: Untraceable communication with very small bandwidth
  2069. overhead.
  2070. In <em>GI/ITG Conference on Communication in Distributed Systems</em>,
  2071. pages 451-463, February 1991.
  2072. <div class="p"><!----></div>
  2073. </dd>
  2074. <dt><a href="#CITEprivoxy" name="privoxy">[39]</a></dt><dd>
  2075. Privoxy.
  2076. <tt>&lt;http://www.privoxy.org/&#62;.
  2077. <div class="p"><!----></div>
  2078. </tt></dd>
  2079. <dt><a href="#CITEreed-protocols97" name="reed-protocols97">[40]</a></dt><dd>
  2080. M.&nbsp;G. Reed, P.&nbsp;F. Syverson, and D.&nbsp;M. Goldschlag.
  2081. Protocols using anonymous connections: Mobile applications.
  2082. In B.&nbsp;Christianson, B.&nbsp;Crispo, M.&nbsp;Lomas, and M.&nbsp;Roe, editors, <em>
  2083. Security Protocols: 5th International Workshop</em>, pages 13-23.
  2084. Springer-Verlag, LNCS 1361, April 1997.
  2085. <div class="p"><!----></div>
  2086. </dd>
  2087. <dt><a href="#CITEor-jsac98" name="or-jsac98">[41]</a></dt><dd>
  2088. M.&nbsp;G. Reed, P.&nbsp;F. Syverson, and D.&nbsp;M. Goldschlag.
  2089. Anonymous connections and onion routing.
  2090. <em>IEEE Journal on Selected Areas in Communications</em>,
  2091. 16(4):482-494, May 1998.
  2092. <div class="p"><!----></div>
  2093. </dd>
  2094. <dt><a href="#CITEcrowds-tissec" name="crowds-tissec">[42]</a></dt><dd>
  2095. M.&nbsp;K. Reiter and A.&nbsp;D. Rubin.
  2096. Crowds: Anonymity for web transactions.
  2097. <em>ACM TISSEC</em>, 1(1):66-92, June 1998.
  2098. <div class="p"><!----></div>
  2099. </dd>
  2100. <dt><a href="#CITEmorphmix:fc04" name="morphmix:fc04">[43]</a></dt><dd>
  2101. M.&nbsp;Rennhard and B.&nbsp;Plattner.
  2102. Practical anonymity for the masses with morphmix.
  2103. In A.&nbsp;Juels, editor, <em>Financial Cryptography</em>. Springer-Verlag,
  2104. LNCS (forthcoming), 2004.
  2105. <div class="p"><!----></div>
  2106. </dd>
  2107. <dt><a href="#CITEanonnet" name="anonnet">[44]</a></dt><dd>
  2108. M.&nbsp;Rennhard, S.&nbsp;Rafaeli, L.&nbsp;Mathy, B.&nbsp;Plattner, and D.&nbsp;Hutchison.
  2109. Analysis of an Anonymity Network for Web Browsing.
  2110. In <em>IEEE 7th Intl. Workshop on Enterprise Security (WET ICE
  2111. 2002)</em>, Pittsburgh, USA, June 2002.
  2112. <div class="p"><!----></div>
  2113. </dd>
  2114. <dt><a href="#CITESS03" name="SS03">[45]</a></dt><dd>
  2115. A.&nbsp;Serjantov and P.&nbsp;Sewell.
  2116. Passive attack analysis for connection-based anonymity systems.
  2117. In <em>Computer Security - ESORICS 2003</em>. Springer-Verlag, LNCS
  2118. 2808, October 2003.
  2119. <div class="p"><!----></div>
  2120. </dd>
  2121. <dt><a href="#CITEp5" name="p5">[46]</a></dt><dd>
  2122. R.&nbsp;Sherwood, B.&nbsp;Bhattacharjee, and A.&nbsp;Srinivasan.
  2123. p<sup>5</sup>: A protocol for scalable anonymous communication.
  2124. In <em>IEEE Symposium on Security and Privacy</em>, pages 58-70. IEEE
  2125. CS, 2002.
  2126. <div class="p"><!----></div>
  2127. </dd>
  2128. <dt><a href="#CITEshsm03" name="shsm03">[47]</a></dt><dd>
  2129. A.&nbsp;Shubina and S.&nbsp;Smith.
  2130. Using caching for browsing anonymity.
  2131. <em>ACM SIGEcom Exchanges</em>, 4(2), Sept 2003.
  2132. <div class="p"><!----></div>
  2133. </dd>
  2134. <dt><a href="#CITEor-discex00" name="or-discex00">[48]</a></dt><dd>
  2135. P.&nbsp;Syverson, M.&nbsp;Reed, and D.&nbsp;Goldschlag.
  2136. Onion Routing access configurations.
  2137. In <em>DARPA Information Survivability Conference and Exposition
  2138. (DISCEX 2000)</em>, volume&nbsp;1, pages 34-40. IEEE CS Press, 2000.
  2139. <div class="p"><!----></div>
  2140. </dd>
  2141. <dt><a href="#CITEor-pet00" name="or-pet00">[49]</a></dt><dd>
  2142. P.&nbsp;Syverson, G.&nbsp;Tsudik, M.&nbsp;Reed, and C.&nbsp;Landwehr.
  2143. Towards an Analysis of Onion Routing Security.
  2144. In H.&nbsp;Federrath, editor, <em>Designing Privacy Enhancing
  2145. Technologies: Workshop on Design Issue in Anonymity and Unobservability</em>,
  2146. pages 96-114. Springer-Verlag, LNCS 2009, July 2000.
  2147. <div class="p"><!----></div>
  2148. </dd>
  2149. <dt><a href="#CITEtannenbaum96" name="tannenbaum96">[50]</a></dt><dd>
  2150. A.&nbsp;Tannenbaum.
  2151. Computer networks, 1996.
  2152. <div class="p"><!----></div>
  2153. </dd>
  2154. <dt><a href="#CITEjap-backdoor" name="jap-backdoor">[51]</a></dt><dd>
  2155. The AN.ON Project.
  2156. German police proceeds against anonymity service.
  2157. Press release, September 2003.
  2158. <tt>&lt;http://www.datenschutzzentrum.de/material/themen/presse/anon-bka_e.htm&#62;.
  2159. <div class="p"><!----></div>
  2160. </tt></dd>
  2161. <dt><a href="#CITEtangler" name="tangler">[52]</a></dt><dd>
  2162. M.&nbsp;Waldman and D.&nbsp;Mazi&#232;res.
  2163. Tangler: A censorship-resistant publishing system based on document
  2164. entanglements.
  2165. In <em>8<sup>th</sup> ACM Conference on Computer and Communications
  2166. Security (CCS-8)</em>, pages 86-135. ACM Press, 2001.
  2167. <div class="p"><!----></div>
  2168. </dd>
  2169. <dt><a href="#CITEpublius" name="publius">[53]</a></dt><dd>
  2170. M.&nbsp;Waldman, A.&nbsp;Rubin, and L.&nbsp;Cranor.
  2171. Publius: A robust, tamper-evident, censorship-resistant and
  2172. source-anonymous web publishing system.
  2173. In <em>Proc. 9th USENIX Security Symposium</em>, pages 59-72, August
  2174. 2000.
  2175. <div class="p"><!----></div>
  2176. </dd>
  2177. <dt><a href="#CITEwright03" name="wright03">[54]</a></dt><dd>
  2178. M.&nbsp;Wright, M.&nbsp;Adler, B.&nbsp;N. Levine, and C.&nbsp;Shields.
  2179. Defending anonymous communication against passive logging attacks.
  2180. In <em>IEEE Symposium on Security and Privacy</em>, pages 28-41. IEEE
  2181. CS, May 2003.</dd>
  2182. </dl>
  2183. <div class="p"><!----></div>
  2184. <hr /><h3>Footnotes:</h3>
  2185. <div class="p"><!----></div>
  2186. <a name="tthFtNtAAB"></a><a href="#tthFrefAAB"><sup>1</sup></a>Actually, the negotiated key is used to derive two
  2187. symmetric keys: one for each direction.
  2188. <div class="p"><!----></div>
  2189. <a name="tthFtNtAAC"></a><a href="#tthFrefAAC"><sup>2</sup></a>
  2190. With 48 bits of digest per cell, the probability of an accidental
  2191. collision is far lower than the chance of hardware failure.
  2192. <div class="p"><!----></div>
  2193. <a name="tthFtNtAAD"></a><a href="#tthFrefAAD"><sup>3</sup></a>
  2194. Rather than rely on an external infrastructure, the Onion Routing network
  2195. can run the lookup service itself. Our current implementation provides a
  2196. simple lookup system on the
  2197. directory servers.
  2198. <div class="p"><!----></div>
  2199. <a name="tthFtNtAAE"></a><a href="#tthFrefAAE"><sup>4</sup></a>Note that this fingerprinting
  2200. attack should not be confused with the much more complicated latency
  2201. attacks of&nbsp;[<a href="#back01" name="CITEback01">5</a>], which require a fingerprint of the latencies
  2202. of all circuits through the network, combined with those from the
  2203. network edges to the target user and the responder website.
  2204. <br /><br /><hr /><small>File translated from
  2205. T<sub><font size="-1">E</font></sub>X
  2206. by <a href="http://hutchinson.belmont.ma.us/tth/">
  2207. T<sub><font size="-1">T</font></sub>H</a>,
  2208. version 3.59.<br />On 18 May 2004, 10:45.</small>
  2209. </body></html>