tor-design.tex 91 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808
  1. \documentclass[times,10pt,twocolumn]{article}
  2. \usepackage{latex8}
  3. \usepackage{times}
  4. \usepackage{url}
  5. \usepackage{graphics}
  6. \usepackage{amsmath}
  7. \pagestyle{empty}
  8. \renewcommand\url{\begingroup \def\UrlLeft{<}\def\UrlRight{>}\urlstyle{tt}\Url}
  9. \newcommand\emailaddr{\begingroup \def\UrlLeft{<}\def\UrlRight{>}\urlstyle{tt}\Url}
  10. % If an URL ends up with '%'s in it, that's because the line *in the .bib/.tex
  11. % file* is too long, so break it there (it doesn't matter if the next line is
  12. % indented with spaces). -DH
  13. %\newif\ifpdf
  14. %\ifx\pdfoutput\undefined
  15. % \pdffalse
  16. %\else
  17. % \pdfoutput=1
  18. % \pdftrue
  19. %\fi
  20. \newenvironment{tightlist}{\begin{list}{$\bullet$}{
  21. \setlength{\itemsep}{0mm}
  22. \setlength{\parsep}{0mm}
  23. % \setlength{\labelsep}{0mm}
  24. % \setlength{\labelwidth}{0mm}
  25. % \setlength{\topsep}{0mm}
  26. }}{\end{list}}
  27. \begin{document}
  28. %% Use dvipdfm instead. --DH
  29. %\ifpdf
  30. % \pdfcompresslevel=9
  31. % \pdfpagewidth=\the\paperwidth
  32. % \pdfpageheight=\the\paperheight
  33. %\fi
  34. \title{Tor: Design of a Second-Generation Onion Router}
  35. %\author{Roger Dingledine \\ The Free Haven Project \\ arma@freehaven.net \and
  36. %Nick Mathewson \\ The Free Haven Project \\ nickm@freehaven.net \and
  37. %Paul Syverson \\ Naval Research Lab \\ syverson@itd.nrl.navy.mil}
  38. \maketitle
  39. \thispagestyle{empty}
  40. \begin{abstract}
  41. We present Tor, a circuit-based low-latency anonymous communication
  42. system. Tor is the successor to Onion Routing
  43. and addresses many limitations in the original Onion Routing design.
  44. Tor works in a real-world Internet environment,
  45. % it's user-space too
  46. requires little synchronization or coordination between nodes, and
  47. provides a reasonable tradeoff between anonymity and usability/efficiency
  48. %protects against known anonymity-breaking attacks as well
  49. %as or better than other systems with similar design parameters.
  50. % and we present a big list of open problems at the end
  51. % and we present a new practical design for rendezvous points
  52. \end{abstract}
  53. %\begin{center}
  54. %\textbf{Keywords:} anonymity, peer-to-peer, remailer, nymserver, reply block
  55. %\end{center}
  56. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  57. \Section{Overview}
  58. \label{sec:intro}
  59. Onion Routing is a distributed overlay network designed to anonymize
  60. low-latency TCP-based applications such as web browsing, secure shell,
  61. and instant messaging. Clients choose a path through the network and
  62. build a \emph{virtual circuit}, in which each node (or ``onion router'')
  63. in the path knows its
  64. predecessor and successor, but no others. Traffic flowing down the circuit
  65. is sent in fixed-size \emph{cells}, which are unwrapped by a symmetric key
  66. at each node (like the layers of an onion) and relayed downstream. The
  67. original Onion Routing project published several design and analysis
  68. papers
  69. \cite{or-ih96,or-jsac98,or-discex00,or-pet00}. While
  70. a wide area Onion Routing network was deployed for several weeks,
  71. the only long-running and publicly accessible
  72. implementation was a fragile proof-of-concept that ran on a single
  73. machine.
  74. % (which nonetheless processed several tens of thousands of connections
  75. %daily from thousands of global users).
  76. %%Do we really want to say this? It softens our motivation for the paper. -RD
  77. Many critical design and deployment issues were never resolved,
  78. and the design has not been updated in several years.
  79. Here we describe Tor, a protocol for asynchronous, loosely
  80. federated onion routers that provides the following improvements over
  81. the old Onion Routing design:
  82. \begin{tightlist}
  83. \item \textbf{Perfect forward secrecy:} The original Onion Routing
  84. design was vulnerable to a single hostile node recording traffic and later
  85. compromising successive nodes in the circuit and forcing them to
  86. decrypt it.
  87. Rather than using a single onion to lay each circuit,
  88. Tor now uses an incremental or \emph{telescoping}
  89. path-building design, where the initiator negotiates session keys with
  90. each successive hop in the circuit. Once these keys are deleted,
  91. subsequently compromised nodes cannot decrypt old traffic.
  92. As a side benefit, onion replay detection is no longer
  93. necessary, and the process of building circuits is more reliable, since
  94. the initiator knows when a hop fails and can then try extending to a new node.
  95. % Perhaps mention that not all of these are things that we invented. -NM
  96. \item \textbf{Separation of protocol cleaning from anonymity:}
  97. The original Onion Routing design required a separate ``application
  98. proxy'' for each
  99. supported application protocol---most
  100. of which were never written, so many applications were never supported.
  101. Tor uses the standard and near-ubiquitous SOCKS
  102. \cite{socks4,socks5} proxy interface, allowing us to support most TCP-based
  103. programs without modification. This design change allows Tor to
  104. use the filtering features of privacy-enhancing
  105. application-level proxies such as Privoxy \cite{privoxy} without having to
  106. incorporate those features itself.
  107. \item \textbf{Many TCP streams can share one circuit:} The original
  108. Onion Routing design built a separate circuit for each application-level
  109. request.
  110. This hurt performance by requiring multiple public key operations for
  111. every request, and also presented
  112. a threat to anonymity from building so many different circuits; see
  113. Section~\ref{sec:maintaining-anonymity}.
  114. Tor multiplexes multiple TCP streams along each virtual
  115. circuit, to improve efficiency and anonymity.
  116. \item \textbf{No mixing, padding, or traffic shaping:} The original
  117. Onion Routing design called for batching and reordering the cells arriving
  118. from each circuit,
  119. plus full link padding between onion routers and between onion
  120. proxies (that is, users) and onion routers \cite{or-jsac98}. The
  121. later analysis paper \cite{or-pet00} theorized \emph{traffic shaping}
  122. that provides similar protection but use less bandwidth, but did not
  123. provide details. However, recent research \cite{econymics} and deployment
  124. experience \cite{freedom21-security} suggest that this level of resource
  125. use is not practical or economical; and even full link padding is still
  126. vulnerable \cite{defensive-dropping}. Thus, until we have a proven and
  127. convenient design for traffic shaping or low-latency mixing that
  128. will improve anonymity against a realistic adversary, we leave these
  129. strategies out.
  130. \item \textbf{Leaky-pipe circuit topology:} Through in-band
  131. signalling within the
  132. circuit, Tor initiators can direct traffic to nodes partway down the
  133. circuit. This allows for long-range padding to frustrate traffic
  134. shape and volume attacks at the initiator \cite{defensive-dropping}.
  135. Because circuits are used by more than one application, it also
  136. allows traffic to exit the circuit from the middle---thus
  137. frustrating traffic shape and volume attacks based on observing the
  138. end of the circuit.
  139. \item \textbf{Congestion control:} Earlier anonymity designs do not
  140. address traffic bottlenecks. Unfortunately, typical approaches to load
  141. balancing and flow control in overlay networks involve inter-node control
  142. communication and global views of traffic. Tor's decentralized congestion
  143. control uses end-to-end acks to maintain reasonable anonymity while
  144. allowing nodes
  145. at the edges of the network to detect congestion or flooding attacks
  146. and send less data until the congestion subsides.
  147. \item \textbf{Directory servers:} The original Onion Routing design
  148. planned to flood link-state information through the network---an
  149. approach which can be unreliable and
  150. open to partitioning attacks or outright deception. Tor takes a simplified
  151. view towards distributing link-state information. Certain more trusted
  152. onion routers also act as directory servers: they provide signed
  153. \emph{directories} which describe the routers they know about and mark
  154. those that
  155. are currently up. Users periodically download these directories via HTTP.
  156. \item \textbf{End-to-end integrity checking:} The original Onion Routing
  157. design did no integrity checking on data. Any onion router on the circuit
  158. could change the contents of cells as they pass by---for example, to
  159. redirect a
  160. connection on the fly so it connects to a different webserver, or to
  161. tag encrypted traffic and look for the tagged traffic at the network
  162. edges \cite{minion-design}. Tor hampers these attacks by checking data
  163. integrity before it leaves the network.
  164. \item \textbf{Robustness to failed nodes:} A failed node in the old design
  165. meant that circuit-building failed, but thanks to Tor's step-by-step
  166. circuit building, users can notice failed
  167. nodes while building circuits and route around them. Additionally,
  168. liveness information from directories allows users to avoid
  169. unreliable nodes in the first place.
  170. %We further provide a
  171. %simple mechanism that allows connections to be established despite recent
  172. %node failure or slightly dated information from a directory server. Tor
  173. %permits onion routers to have \emph{router twins} --- nodes that share
  174. %the same private decryption key. Note that because connections now have
  175. %perfect forward secrecy, an onion router still cannot read the traffic
  176. %on a connection established through its twin even while that connection
  177. %is active. Also, which nodes are twins can change dynamically depending
  178. %on current circumstances, and twins may or may not be under the same
  179. %administrative authority.
  180. %
  181. %[Commented out; Router twins provide no real increase in robustness
  182. %to failed nodes. If a non-twinned node goes down, the
  183. %circuit-builder notices this and routes around it. Circuit-building
  184. %is offline, so there shouldn't even be a latency hit. -NM]
  185. \item \textbf{Variable exit policies:} Tor provides a consistent
  186. mechanism for
  187. each node to specify and advertise a policy describing the hosts and
  188. ports to which it will connect. These exit policies
  189. are critical in a volunteer-based distributed infrastructure, because
  190. each operator is comfortable with allowing different types of traffic
  191. to exit the Tor network from his node.
  192. \item \textbf{Implementable in user-space:} Unlike other anonymity systems
  193. like Freedom \cite{freedom2-arch}, Tor only attempts to anonymize TCP
  194. streams. Thus it does not require patches to an operating system's network
  195. stack (or built-in support) to operate. Although this approach is less
  196. flexible, it has proven valuable to Tor's portability and deployability.
  197. \item \textbf{Rendezvous points and location-protected servers:}
  198. Tor provides an integrated mechanism for responder anonymity via
  199. location-protected servers. Previous Onion Routing designs included
  200. long-lived ``reply onions'' which could be used to build virtual circuits
  201. to a hidden server, but a reply onion becomes useless if any node in
  202. the path goes down or rotates its keys, and it also does not provide
  203. forward security. In Tor's current design, clients negotiate {\it
  204. rendezvous points} to connect with hidden servers; reply onions are no
  205. longer required.
  206. \end{tightlist}
  207. We have implemented most of the above features. Our source code is
  208. available under a free license, and is not encumbered by patents. We have
  209. recently begun deploying a widespread alpha network to see how well the
  210. design works in practice, to get more experience with usability and users,
  211. and to provide a research platform for experimenting with new ideas.
  212. We review previous work in Section~\ref{sec:related-work}, describe
  213. our goals and assumptions in Section~\ref{sec:assumptions},
  214. and then address the above list of improvements in
  215. Sections~\ref{sec:design}-\ref{sec:rendezvous}. We
  216. summarize in Section \ref{sec:analysis}
  217. how our design stands up to known attacks, and conclude with a list of
  218. open problems.
  219. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  220. \Section{Related work}
  221. \label{sec:related-work}
  222. Modern anonymity designs date to Chaum's Mix-Net\cite{chaum-mix} design of
  223. 1981. Chaum proposed hiding sender-recipient linkability by wrapping
  224. messages in layers of public key cryptography, and relaying them
  225. through a path composed of ``Mixes.'' These mixes in turn decrypt, delay,
  226. and re-order messages, before relaying them along the sender-selected
  227. path towards their destinations.
  228. Subsequent relay-based anonymity designs have diverged in two
  229. principal directions. Some have attempted to maximize anonymity at
  230. the cost of introducing comparatively large and variable latencies,
  231. for example, Babel\cite{babel}, Mixmaster\cite{mixmaster-spec}, and
  232. Mixminion\cite{minion-design}. Because of this
  233. trade-off, these \emph{high-latency} networks are well-suited for anonymous
  234. email, but introduce too much lag for interactive tasks such as web browsing,
  235. internet chat, or SSH connections.
  236. Tor belongs to the second category: \emph{low-latency} designs that attempt
  237. to anonymize interactive network traffic. Because these protocols typically
  238. involve a large number of packets that must be delivered quickly, it is
  239. difficult for them to prevent an attacker who can eavesdrop both ends of the
  240. communication from correlating the timing and volume
  241. of traffic entering the anonymity network with traffic leaving it. These
  242. protocols are also vulnerable against active attacks in which an
  243. adversary introduces timing patterns into traffic entering the network, and
  244. looks
  245. for correlated patterns among exiting traffic.
  246. Although some work has been done to frustrate
  247. these attacks,\footnote{
  248. The most common approach is to pad and limit communication to a constant
  249. rate, or to limit
  250. the variation in traffic shape. Doing so can have prohibitive bandwidth
  251. costs and/or performance limitations.
  252. %One can also use a cascade (fixed
  253. %shared route) with a relatively fixed set of users. This assumes a
  254. %significant degree of agreement and provides an easier target for an active
  255. %attacker since the endpoints are generally known.
  256. } most designs protect primarily against traffic analysis rather than traffic
  257. confirmation \cite{or-jsac98}---that is, they assume that the attacker is
  258. attempting to learn who is talking to whom, not to confirm a prior suspicion
  259. about who is talking to whom.
  260. The simplest low-latency designs are single-hop proxies such as the
  261. Anonymizer \cite{anonymizer}, wherein a single trusted server strips the
  262. data's origin before relaying it. These designs are easy to
  263. analyze, but require end-users to trust the anonymizing proxy.
  264. Concentrating the traffic to a single point increases the anonymity set
  265. (the set of people a given user is hiding among), but it can make traffic
  266. analysis easier: an adversary need only eavesdrop on the proxy to observe
  267. the entire system.
  268. More complex are distributed-trust, circuit-based anonymizing systems. In
  269. these designs, a user establishes one or more medium-term bidirectional
  270. end-to-end tunnels to exit servers, and uses those tunnels to deliver
  271. low-latency packets to and from one or more destinations per
  272. tunnel. %XXX reword
  273. Establishing tunnels is expensive and typically
  274. requires public-key cryptography, whereas relaying packets along a tunnel is
  275. comparatively inexpensive. Because a tunnel crosses several servers, no
  276. single server can link a user to her communication partners.
  277. In some distributed-trust systems, such as the Java Anon Proxy (also known
  278. as JAP or Web MIXes), users build their tunnels along a fixed shared route
  279. or \emph{cascade}. As with a single-hop proxy, this approach aggregates
  280. users into larger anonymity sets, but again an attacker only needs to
  281. observe both ends of the cascade to bridge all the system's traffic.
  282. The Java Anon Proxy's design seeks to prevent this by padding
  283. between end users and the head of the cascade \cite{web-mix}. However, the
  284. current implementation does no padding and thus remains vulnerable
  285. to both active and passive bridging.
  286. %XXX fix, yes it does, sort of.
  287. %XXX do a paragraph on p2p vs client-server
  288. \cite{tarzan:ccs02}
  289. \cite{morphmix:fc04}
  290. Systems such as Freedom and the original Onion Routing
  291. build the anonymous channel all at once, using a layered ``onion'' of
  292. public-key encrypted messages, each layer of which provides a set of session
  293. keys and the address of the next server in the channel. Tor as described
  294. herein, Tarzan, Morphmix, Cebolla \cite{cebolla}, and AnonNet
  295. \cite{anonnet} build the
  296. channel in stages, extending it one hop at a time. This approach
  297. makes perfect forward secrecy feasible.
  298. Distributed-trust anonymizing systems differ in how they prevent attackers
  299. from controlling too many servers and thus compromising too many user paths.
  300. Some protocols rely on a centrally maintained set of well-known anonymizing
  301. servers. The current Tor design falls into this category.
  302. Others (such as Tarzan and MorphMix) allow unknown users to run
  303. servers, while using a limited resource (DHT space for Tarzan; IP space for
  304. MorphMix) to prevent an attacker from owning too much of the network.
  305. Crowds uses a centralized ``blender'' to enforce Crowd membership
  306. policy. For small crowds it is suggested that familiarity with all
  307. members is adequate. For large diverse crowds, limiting accounts in
  308. control of any one party is more complex:
  309. ``(e.g., the blender administrator sets up an account for a user only
  310. after receiving a written, notarized request from that user) and each
  311. account to one jondo, and by monitoring and limiting the number of
  312. jondos on any one net- work (using IP address), the attacker would be
  313. forced to launch jondos using many different identities and on many
  314. different networks to succeed'' \cite{crowds-tissec}.
  315. PipeNet \cite{back01, pipenet}, another low-latency design proposed at
  316. about the same time as the original Onion Routing design, provided
  317. stronger anonymity at the cost of allowing a single user to shut
  318. down the network simply by not sending. Low-latency anonymous
  319. communication has also been designed for other environments, including
  320. ISDN \cite{isdn-mixes}
  321. % and mobile applications such as telephones and
  322. %active badging systems \cite{federrath-ih96,reed-protocols97}.
  323. Some systems, such as Crowds \cite{crowds-tissec}, do not rely on changing the
  324. appearance of packets to hide the path; rather they try to prevent an
  325. intermediary from knowing whether it is talking to an initiator
  326. or just another intermediary. Crowds uses no public-key
  327. encryption, but the responder and all data are visible to all
  328. nodes on the path; so anonymity of the connection initiator depends on
  329. filtering all identifying information from the data stream. Crowds only
  330. supports HTTP traffic.
  331. Hordes \cite{hordes-jcs} is based on Crowds but also uses multicast
  332. responses to hide the initiator. Herbivore \cite{herbivore} and
  333. P5 \cite{p5} go even further, requiring broadcast.
  334. Each uses broadcast in different ways, and trade-offs are made to
  335. make broadcast more practical. Both Herbivore and P5 are designed primarily
  336. for communication between communicating peers, although Herbivore
  337. permits external connections by requesting a peer to serve as a proxy.
  338. Allowing easy connections to nonparticipating responders or recipients
  339. is a practical requirement for many users, e.g., to visit
  340. nonparticipating Web sites or to exchange mail with nonparticipating
  341. recipients.
  342. Tor is not primarily designed for censorship resistance but rather
  343. for anonymous communication. However, Tor's rendezvous points, which
  344. enable connections between mutually anonymous entities, also
  345. facilitate connections to hidden servers. These building blocks to
  346. censorship resistance and other capabilities are described in
  347. Section~\ref{sec:rendezvous}. Location-hidden servers are an
  348. essential component for the anonymous publishing systems such as
  349. Eternity\cite{eternity}, Publius\cite{publius},
  350. Free Haven\cite{freehaven-berk}, and Tangler\cite{tangler}.
  351. STILL NOT MENTIONED:
  352. real-time mixes\\
  353. rewebbers\\
  354. cebolla\\
  355. [XXX Close by mentioning where Tor fits.]
  356. \Section{Design goals and assumptions}
  357. \label{sec:assumptions}
  358. \SubSection{Goals}
  359. Like other low-latency anonymity designs, Tor seeks to frustrate
  360. attackers from linking communication partners, or from linking
  361. multiple communications to or from a single point. Within this
  362. main goal, however, several design considerations have directed
  363. Tor's evolution.
  364. \begin{description}
  365. \item[Deployability:] The design must be one which can be implemented,
  366. deployed, and used in the real world. This requirement precludes designs
  367. that are expensive to run (for example, by requiring more bandwidth than
  368. volunteers are willing to provide); designs that place a heavy liability
  369. burden on operators (for example, by allowing attackers to implicate onion
  370. routers in illegal activities); and designs that are difficult or expensive
  371. to implement (for example, by requiring kernel patches, or separate proxies
  372. for every protocol). This requirement also precludes systems in which
  373. users who do not benefit from anonymity are required to run special
  374. software in order to communicate with anonymous parties.
  375. % Our rendezvous points require clients to use our software to get to
  376. % the location-hidden servers.
  377. % Or at least, they require somebody near the client-side running our
  378. % software. We haven't worked out the details of keeping it transparent
  379. % for Alice if she's using some other http proxy somewhere. I guess the
  380. % external http proxy should route through a Tor client, which automatically
  381. % translates the foo.onion address? -RD
  382. %
  383. % 1. Such clients do benefit from anonymity: they can reach the server.
  384. % Recall that our goal for location hidden servers is to continue to
  385. % provide service to priviliged clients when a DoS is happening or
  386. % to provide access to a location sensitive service. I see no contradiction.
  387. % 2. A good idiot check is whether what we require people to download
  388. % and use is more extreme than downloading the anonymizer toolbar or
  389. % privacy manager. I don't think so, though I'm not claiming we've already
  390. % got the installation and running of a client down to that simplicity
  391. % at this time. -PS
  392. \item[Usability:] A hard-to-use system has fewer users---and because
  393. anonymity systems hide users among users, a system with fewer users
  394. provides less anonymity. Usability is not only a convenience for Tor:
  395. it is a security requirement \cite{econymics,back01}. Tor
  396. should work with most of a user's unmodified applications; shouldn't
  397. introduce prohibitive delays; and should require the user to make as few
  398. configuration decisions as possible.
  399. \item[Flexibility:] The protocol must be flexible and
  400. well-specified, so that it can serve as a test-bed for future research in
  401. low-latency anonymity systems. Many of the open problems in low-latency
  402. anonymity networks (such as generating dummy traffic, or preventing
  403. pseudospoofing attacks) may be solvable independently from the issues
  404. solved by Tor; it would be beneficial if future systems were not forced to
  405. reinvent Tor's design decisions. (But note that while a flexible design
  406. benefits researchers, there is a danger that differing choices of
  407. extensions will render users distinguishable. Thus, experiments
  408. on extensions should be limited and should not significantly affect
  409. the distinguishability of ordinary users.
  410. % To run an experiment researchers must file an
  411. % anonymity impact statement -PS
  412. of implementations should
  413. not permit different protocol extensions to coexist in a single deployed
  414. network.)
  415. \item[Conservative design:] The protocol's design and security parameters
  416. must be conservative. Because additional features impose implementation
  417. and complexity costs, Tor should include as few speculative features as
  418. possible. (We do not oppose speculative designs in general; however, it is
  419. our goal with Tor to embody a solution to the problems in low-latency
  420. anonymity that we can solve today before we plunge into the problems of
  421. tomorrow.)
  422. % This last bit sounds completely cheesy. Somebody should tone it down. -NM
  423. \end{description}
  424. \SubSection{Non-goals}
  425. In favoring conservative, deployable designs, we have explicitly deferred
  426. a number of goals. Many of these goals are desirable in anonymity systems,
  427. but we choose to defer them either because they are solved elsewhere,
  428. or because they present an area of active research lacking a generally
  429. accepted solution.
  430. \begin{description}
  431. \item[Not Peer-to-peer:] Tarzan and Morphmix aim to
  432. scale to completely decentralized peer-to-peer environments with thousands
  433. of short-lived servers, many of which may be controlled by an adversary.
  434. Because of the many open problems in this approach, Tor uses a more
  435. conservative design.
  436. \item[Not secure against end-to-end attacks:] Tor does not claim to provide a
  437. definitive solution to end-to-end timing or intersection attacks. Some
  438. approaches, such as running an onion router, may help; see
  439. Section~\ref{sec:analysis} for more discussion.
  440. \item[No protocol normalization:] Tor does not provide \emph{protocol
  441. normalization} like Privoxy or the Anonymizer. In order to make clients
  442. indistinguishable when they use complex and variable protocols such as HTTP,
  443. Tor must be layered with a filtering proxy such as Privoxy to hide
  444. differences between clients, expunge protocol features that leak identity,
  445. and so on. Similarly, Tor does not currently integrate tunneling for
  446. non-stream-based protocols like UDP; this too must be provided by
  447. an external service.
  448. % Actually, tunneling udp over tcp is probably horrible for some apps.
  449. % Should this get its own non-goal bulletpoint? The motivation for
  450. % non-goal-ness would be burden on clients / portability.
  451. \item[Not steganographic:] Tor does not try to conceal which users are
  452. sending or receiving communications; it only tries to conceal whom they are
  453. communicating with.
  454. \end{description}
  455. \SubSection{Threat Model}
  456. \label{subsec:threat-model}
  457. A global passive adversary is the most commonly assumed threat when
  458. analyzing theoretical anonymity designs. But like all practical low-latency
  459. systems, Tor is not secure against this adversary. Instead, we assume an
  460. adversary that is weaker than global with respect to distribution, but that
  461. is not merely passive. Our threat model expands on that from
  462. \cite{or-pet00}.
  463. %%%% This is really keen analytical stuff, but it isn't our threat model:
  464. %%%% we just go ahead and assume a fraction of hostile nodes for
  465. %%%% convenience. -NM
  466. %
  467. %% The basic adversary components we consider are:
  468. %% \begin{description}
  469. %% \item[Observer:] can observe a connection (e.g., a sniffer on an
  470. %% Internet router), but cannot initiate connections. Observations may
  471. %% include timing and/or volume of packets as well as appearance of
  472. %% individual packets (including headers and content).
  473. %% \item[Disrupter:] can delay (indefinitely) or corrupt traffic on a
  474. %% link. Can change all those things that an observer can observe up to
  475. %% the limits of computational ability (e.g., cannot forge signatures
  476. %% unless a key is compromised).
  477. %% \item[Hostile initiator:] can initiate (or destroy) connections with
  478. %% specific routes as well as vary the timing and content of traffic
  479. %% on the connections it creates. A special case of the disrupter with
  480. %% additional abilities appropriate to its role in forming connections.
  481. %% \item[Hostile responder:] can vary the traffic on the connections made
  482. %% to it including refusing them entirely, intentionally modifying what
  483. %% it sends and at what rate, and selectively closing them. Also a
  484. %% special case of the disrupter.
  485. %% \item[Key breaker:] can break the key used to encrypt connection
  486. %% initiation requests sent to a Tor-node.
  487. %% % Er, there are no long-term private decryption keys. They have
  488. %% % long-term private signing keys, and medium-term onion (decryption)
  489. %% % keys. Plus short-term link keys. Should we lump them together or
  490. %% % separate them out? -RD
  491. %% %
  492. %% % Hmmm, I was talking about the keys used to encrypt the onion skin
  493. %% % that contains the public DH key from the initiator. Is that what you
  494. %% % mean by medium-term onion key? (``Onion key'' used to mean the
  495. %% % session keys distributed in the onion, back when there were onions.)
  496. %% % Also, why are link keys short-term? By link keys I assume you mean
  497. %% % keys that neighbor nodes use to superencrypt all the stuff they send
  498. %% % to each other on a link. Did you mean the session keys? I had been
  499. %% % calling session keys short-term and everything else long-term. I
  500. %% % know I was being sloppy. (I _have_ written papers formalizing
  501. %% % concepts of relative freshness.) But, there's some questions lurking
  502. %% % here. First up, I don't see why the onion-skin encryption key should
  503. %% % be any shorter term than the signature key in terms of threat
  504. %% % resistance. I understand that how we update onion-skin encryption
  505. %% % keys makes them depend on the signature keys. But, this is not the
  506. %% % basis on which we should be deciding about key rotation. Another
  507. %% % question is whether we want to bother with someone who breaks a
  508. %% % signature key as a particular adversary. He should be able to do
  509. %% % nearly the same as a compromised tor-node, although they're not the
  510. %% % same. I reworded above, I'm thinking we should leave other concerns
  511. %% % for later. -PS
  512. %% \item[Hostile Tor node:] can arbitrarily manipulate the
  513. %% connections under its control, as well as creating new connections
  514. %% (that pass through itself).
  515. %% \end{description}
  516. %
  517. %% All feasible adversaries can be composed out of these basic
  518. %% adversaries. This includes combinations such as one or more
  519. %% compromised Tor-nodes cooperating with disrupters of links on which
  520. %% those nodes are not adjacent, or such as combinations of hostile
  521. %% outsiders and link observers (who watch links between adjacent
  522. %% Tor-nodes). Note that one type of observer might be a Tor-node. This
  523. %% is sometimes called an honest-but-curious adversary. While an observer
  524. %% Tor-node will perform only correct protocol interactions, it might
  525. %% share information about connections and cannot be assumed to destroy
  526. %% session keys at end of a session. Note that a compromised Tor-node is
  527. %% stronger than any other adversary component in the sense that
  528. %% replacing a component of any adversary with a compromised Tor-node
  529. %% results in a stronger overall adversary (assuming that the compromised
  530. %% Tor-node retains the same signature keys and other private
  531. %% state-information as the component it replaces).
  532. First, we assume that a threshold of directory servers are honest,
  533. reliable, accurate, and trustworthy.
  534. %% the rest of this isn't needed, if dirservers do threshold concensus dirs
  535. % To augment this, users can periodically cross-check
  536. %directories from each directory server (trust, but verify).
  537. %, and that they always have access to at least one directory server that they trust.
  538. Second, we assume that somewhere between ten percent and twenty
  539. percent\footnote{In some circumstances---for example, if the Tor network is
  540. running on a hardened network where all operators have had background
  541. checks---the number of compromised nodes could be much lower.}
  542. of the Tor nodes accepted by the directory servers are compromised, hostile,
  543. and collaborating in an off-line clique. These compromised nodes can
  544. arbitrarily manipulate the connections that pass through them, as well as
  545. creating new connections that pass through themselves. They can observe
  546. traffic, and record it for later analysis. Honest participants do not know
  547. which servers these are.
  548. (In reality, many realistic adversaries might have `bad' servers that are not
  549. fully compromised but simply under observation, or that have had their keys
  550. compromised. But for the sake of analysis, we ignore, this possibility,
  551. since the threat model we assume is strictly stronger.)
  552. % This next paragraph is also more about analysis than it is about our
  553. % threat model. Perhaps we can say, ``users can connect to the network and
  554. % use it in any way; we consider abusive attacks separately.'' ? -NM
  555. Third, we constrain the impact of hostile users. Users are assumed to vary
  556. widely in both the duration and number of times they are connected to the Tor
  557. network. They can also be assumed to vary widely in the volume and shape of
  558. the traffic they send and receive. Hostile users are, by definition, limited
  559. to creating and varying their own connections into or through a Tor
  560. network. They may attack their own connections to try to gain identity
  561. information of the responder in a rendezvous connection. They can also try to
  562. attack sites through the Onion Routing network; however we will consider this
  563. abuse rather than an attack per se (see
  564. Section~\ref{subsec:exitpolicies}). Other than abuse, a hostile user's
  565. motivation to attack his own connections is limited to the network effects of
  566. such actions, such as denial of service (DoS) attacks. Thus, in this case,
  567. we can view user as simply an extreme case of the ordinary user; although
  568. ordinary users are not likely to engage in, e.g., IP spoofing, to gain their
  569. objectives.
  570. In general, we are more focused on traffic analysis attacks than
  571. traffic confirmation attacks.
  572. %A user who runs a Tor proxy on his own
  573. %machine, connects to some remote Tor-node and makes a connection to an
  574. %open Internet site, such as a public web server, is vulnerable to
  575. %traffic confirmation.
  576. That is, an active attacker who suspects that
  577. a particular client is communicating with a particular server can
  578. confirm this if she can modify and observe both the
  579. connection between the Tor network and the client and that between the
  580. Tor network and the server. Even a purely passive attacker can
  581. confirm traffic if the timing and volume properties of the traffic on
  582. the connection are unique enough. (This is not to say that Tor offers
  583. no resistance to traffic confirmation; it does. We defer discussion
  584. of this point and of particular attacks until Section~\ref{sec:attacks},
  585. after we have described Tor in more detail.)
  586. % XXX We need to say what traffic analysis is: How about...
  587. On the other hand, we {\it do} try to prevent an attacker from
  588. performing traffic analysis: that is, attempting to learn the communication
  589. partners of an arbitrary user.
  590. % XXX If that's not right, what is? It would be silly to have a
  591. % threat model section without saying what we want to prevent the
  592. % attacker from doing. -NM
  593. % XXX Also, do we want to mention linkability or building profiles? -NM
  594. Our assumptions about our adversary's capabilities imply a number of
  595. possible attacks against users' anonymity. Our adversary might try to
  596. mount passive attacks by observing the edges of the network and
  597. correlating traffic entering and leaving the network: either because
  598. of relationships in packet timing; relationships in the volume of data
  599. sent; [XXX simple observation??]; or relationships in any externally
  600. visible user-selected options. The adversary can also mount active
  601. attacks by trying to compromise all the servers' keys in a
  602. path---either through illegitimate means or through legal coercion in
  603. unfriendly jurisdiction; by selectively DoSing trustworthy servers; by
  604. introducing patterns into entering traffic that can later be detected;
  605. or by modifying data entering the network and hoping that trashed data
  606. comes out the other end. The attacker can additionally try to
  607. decrease the network's reliability by performing antisocial activities
  608. from reliable servers and trying to get them taken down.
  609. % XXX Should there be more or less? Should we turn this into a
  610. % bulleted list? Should we cut it entirely?
  611. We consider these attacks and more, and describe our defenses against them
  612. in Section~\ref{sec:attacks}.
  613. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  614. \Section{The Tor Design}
  615. \label{sec:design}
  616. The Tor network is an overlay network; each node is called an onion router
  617. (OR). Onion routers run as normal user-level processes without needing
  618. any special
  619. privileges. Currently, each OR maintains a long-term TLS connection
  620. to every other
  621. OR. (We examine some ways to relax this clique-topology assumption in
  622. Section~\ref{subsec:restricted-routes}.) A subset of the ORs also act as
  623. directory servers, tracking which routers are currently in the network;
  624. see Section~\ref{subsec:dirservers} for directory server details. Users
  625. run local software called an onion proxy (OP) to fetch directories,
  626. establish paths (called \emph{virtual circuits}) across the network,
  627. and handle connections from user applications. Onion proxies accept
  628. TCP streams and multiplex them across the virtual circuit. The onion
  629. router on the other side
  630. % I don't mean other side, I mean wherever it is on the circuit. But
  631. % don't want to introduce complexity this early? Hm. -RD
  632. of the circuit connects to the destinations of
  633. the TCP streams and relays data.
  634. Each onion router uses three public keys: a long-term identity key, a
  635. short-term onion key, and a short-term link key. The identity
  636. (signing) key is used to sign TLS certificates, to sign its router
  637. descriptor (a summary of its keys, address, bandwidth, exit policy,
  638. etc), and to sign directories if it is a directory server. Changing
  639. the identity key of a router is considered equivalent to creating a
  640. new router. The onion (decryption) key is used for decrypting requests
  641. from users to set up a circuit and negotiate ephemeral keys. Finally,
  642. link keys are used by the TLS protocol when communicating between
  643. onion routers. We discuss rotating these keys in
  644. Section~\ref{subsec:rotating-keys}.
  645. Section~\ref{subsec:cells} discusses the structure of the fixed-size
  646. \emph{cells} that are the unit of communication in Tor. We describe
  647. in Section~\ref{subsec:circuits} how virtual circuits are
  648. built, extended, truncated, and destroyed. Section~\ref{subsec:tcp}
  649. describes how TCP streams are routed through the network, and finally
  650. Section~\ref{subsec:congestion} talks about congestion control and
  651. fairness issues.
  652. \SubSection{Cells}
  653. \label{subsec:cells}
  654. % I think we should describe connections before cells. -NM
  655. Traffic passes from one OR to another, or between a user's OP and an OR,
  656. in fixed-size cells. Each cell is 256
  657. bytes, and consists of a header and a payload. The header includes an
  658. anonymous circuit identifier (ACI) that specifies which circuit the
  659. % Should we replace ACI with circID ? What is this 'anonymous circuit'
  660. % thing anyway? -RD
  661. cell refers to
  662. (many circuits can be multiplexed over the single TCP connection between
  663. ORs or between an OP and an OR), and a command to describe what to do
  664. with the cell's payload. Cells are either \emph{control} cells, which are
  665. interpreted by the node that receives them, or \emph{relay} cells,
  666. which carry end-to-end stream data. Controls cells can be one of:
  667. \emph{padding} (currently used for keepalive, but also usable for link
  668. padding); \emph{create} or \emph{created} (used to set up a new circuit);
  669. or \emph{destroy} (to tear down a circuit).
  670. % We need to say that ACIs are connection-specific: each circuit has
  671. % a different ACI along each connection. -NM
  672. % agreed -RD
  673. Relay cells have an additional header (the relay header) after the
  674. cell header, containing the stream identifier (many streams can
  675. be multiplexed over a circuit); an end-to-end checksum for integrity
  676. checking; the length of the relay payload; and a relay command. Relay
  677. commands can be one of: \emph{relay
  678. data} (for data flowing down the stream), \emph{relay begin} (to open a
  679. stream), \emph{relay end} (to close a stream), \emph{relay connected}
  680. (to notify the OP that a relay begin has succeeded), \emph{relay
  681. extend} and \emph{relay extended} (to extend the circuit by a hop,
  682. and to acknowledge), \emph{relay truncate} and \emph{relay truncated}
  683. (to tear down only part of the circuit, and to acknowledge), \emph{relay
  684. sendme} (used for congestion control), and \emph{relay drop} (used to
  685. implement long-range dummies).
  686. We describe each of these cell types in more detail below.
  687. % Nick: should there have been a table here? -RD
  688. % Maybe. -NM
  689. \SubSection{Circuits and streams}
  690. \label{subsec:circuits}
  691. % I think when we say ``the user,'' maybe we should say ``the user's OP.''
  692. The original Onion Routing design built one circuit for each
  693. TCP stream. Because building a circuit can take several tenths of a
  694. second (due to public-key cryptography delays and network latency),
  695. this design imposed high costs on applications like web browsing that
  696. open many TCP streams.
  697. In Tor, each circuit can be shared by many TCP streams. To avoid
  698. delays, users construct circuits preemptively. To limit linkability
  699. among the streams, users rotate connections by building a new circuit
  700. periodically (currently every minute) if the previous one has been
  701. used, and expire old used circuits that are no longer in use. Thus
  702. even very active users spend a negligible amount of time and CPU in
  703. building circuits, but only a limited number of requests can be linked
  704. to each other by a given exit node. Also, because circuits are built
  705. in the background, failed routers do not affects user experience.
  706. \subsubsection{Constructing a circuit}
  707. Users construct each incrementally, negotiating a symmetric key with
  708. each hop one at a time. To begin creating a new circuit, the user
  709. (call her Alice) sends a \emph{create} cell to the first node in her
  710. chosen path. The cell's payload is the first half of the
  711. Diffie-Hellman handshake, encrypted to the onion key of the OR (call
  712. him Bob). Bob responds with a \emph{created} cell containg the second
  713. half of the DH handshake, along with a hash of the negotiated key
  714. $K=g^{xy}$. This protocol tries to achieve unilateral entity
  715. authentication (Alice knows she's handshaking with Bob, Bob doesn't
  716. care who is opening the circuit---Alice has no key and is trying to
  717. remain anonymous); unilateral key authentication (Alice and Bob
  718. agree on a key, and Alice knows Bob is the only other person who could
  719. know it). We also want perfect forward
  720. secrecy, key freshness, etc.
  721. \begin{equation}
  722. \begin{aligned}
  723. \mathrm{Alice} \rightarrow \mathrm{Bob}&: E_{PK_{Bob}}(g^x) \\
  724. \mathrm{Bob} \rightarrow \mathrm{Alice}&: g^y, H(K | \mathrm{``handshake"}) \\
  725. \end{aligned}
  726. \end{equation}
  727. The second step shows both that it was Bob
  728. who received $g^x$, and that it was Bob who came up with $y$. We use
  729. PK encryption in the first step (rather than, e.g., using the first two
  730. steps of STS, which has a signature in the second step) because we
  731. don't have enough room in a single cell for a public key and also a
  732. signature. Preliminary analysis with the NRL protocol analyzer shows
  733. the above protocol to be secure (including providing PFS) under the
  734. traditional Dolev-Yao model.
  735. % cite Cathy? -RD
  736. % did I use the buzzwords correctly? -RD
  737. % Hm. I think that this paragraph could go earlier in expository
  738. % order: we describe how to build whole circuit, then explain the
  739. % protocol in more detail. -NM
  740. To extend a circuit past the first hop, Alice sends a \emph{relay extend}
  741. cell to the last node in the circuit, specifying the address of the new
  742. OR and an encrypted $g^x$ for it. That node copies the half-handshake
  743. into a \emph{create} cell, and passes it to the new OR to extend the
  744. circuit. When it responds with a \emph{created} cell, the penultimate OR
  745. copies the payload into a \emph{relay extended} cell and passes it back.
  746. % Nick: please fix my "that OR" pronouns -RD
  747. \subsubsection{Relay cells}
  748. Once Alice has established the circuit (so she shares a key with each
  749. OR on the circuit), she can send relay cells.
  750. The stream ID in the relay header indicates to which stream the cell belongs.
  751. A relay cell can be addressed to any of the ORs on the circuit. To
  752. construct a relay cell addressed to a given OR, Alice iteratively
  753. encrypts the cell payload (that is, the relay header and payload)
  754. with the symmetric key of each hop up to that OR. Then, at each hop
  755. down the circuit, the OR decrypts the cell payload and checks whether
  756. it recognizes the stream ID. A stream ID is recognized either if it
  757. is an already open stream at that OR, or if it is equal to zero. The
  758. zero stream ID is treated specially, and is used for control messages,
  759. e.g. starting a new stream. If the stream ID is unrecognized, the OR
  760. passes the relay cell downstream. This \emph{leaky pipe} circuit topology
  761. allows Alice's streams to exit at different ORs on a single circuit.
  762. Alice may choose different exit points because of their exit policies,
  763. or to keep the ORs from knowing that two streams
  764. originate at the same person.
  765. To tear down a circuit, Alice sends a destroy control cell. Each OR
  766. in the circuit receives the destroy cell, closes all open streams on
  767. that circuit, and passes a new destroy cell forward. But since circuits
  768. can be built incrementally, they can also be torn down incrementally:
  769. Alice can instead send a relay truncate cell to a node along the circuit. That
  770. node will send a destroy cell forward, and reply with an acknowledgment
  771. (relay truncated). Alice might truncate her circuit so she can extend it
  772. to different nodes without signaling to the first few nodes (or somebody
  773. observing them) that she is changing her circuit. That is, nodes in the
  774. middle are not even aware that the circuit was truncated, because the
  775. relay cells are encrypted. Similarly, if a node on the circuit goes down,
  776. the adjacent node can send a relay truncated back to Alice. Thus the
  777. ``break a node and see which circuits go down'' attack is weakened.
  778. \SubSection{Opening and closing streams}
  779. \label{subsec:tcp}
  780. When Alice's application wants to open a TCP connection to a given
  781. address and port, it asks the OP (via SOCKS) to make the connection. The
  782. OP chooses the newest open circuit (or creates one if none is available),
  783. chooses a suitable OR on that circuit to be the exit node (usually the
  784. last node, but maybe others due to exit policy conflicts; see
  785. Section~\ref{sec:exit-policies}), chooses a new random stream ID for
  786. this stream,
  787. and delivers a relay begin cell to that exit node. It uses a stream ID
  788. of zero for the begin cell (so the OR will recognize it), and the relay
  789. payload lists the new stream ID and the destination address and port.
  790. Once the exit node completes the connection to the remote host, it
  791. responds with a relay connected cell through the circuit. Upon receipt,
  792. the OP notifies the application that it can begin talking.
  793. There's a catch to using SOCKS, though -- some applications hand the
  794. alphanumeric address to the proxy, while others resolve it into an IP
  795. address first and then hand the IP to the proxy. When the application
  796. does the DNS resolution first, Alice broadcasts her destination. Common
  797. applications like Mozilla and ssh have this flaw.
  798. In the case of Mozilla, we're fine: the filtering web proxy called Privoxy
  799. does the SOCKS call safely, and Mozilla talks to Privoxy safely. But a
  800. portable general solution, such as for ssh, is an open problem. We could
  801. modify the local nameserver, but this approach is invasive, brittle, and
  802. not portable. We could encourage the resolver library to do resolution
  803. via TCP rather than UDP, but this approach is hard to do right, and also
  804. has portability problems. Our current answer is to encourage the use of
  805. privacy-aware proxies like Privoxy wherever possible, and also provide
  806. a tool similar to \emph{dig} that can do a private lookup through the
  807. Tor network.
  808. Ending a Tor stream is analogous to ending a TCP stream: it uses a
  809. two-step handshake for normal operation, or a one-step handshake for
  810. errors. If one side of the stream closes abnormally, that node simply
  811. sends a relay teardown cell, and tears down the stream. If one side
  812. % Nick: mention relay teardown in 'cell' subsec? good enough name? -RD
  813. of the stream closes the connection normally, that node sends a relay
  814. end cell down the circuit. When the other side has sent back its own
  815. relay end, the stream can be torn down. This two-step handshake allows
  816. for TCP-based applications that, for example, close a socket for writing
  817. but are still willing to read.
  818. \SubSection{Integrity checking on streams}
  819. In the old Onion Routing design, traffic was vulnerable to a
  820. malleability attack: an attacker could make changes to an encrypted
  821. cell to create corresponding changes to the data leaving the network.
  822. (Even an external adversary could do this, despite link encryption!)
  823. This weakness allowed an adversary to change a create cell to a destroy
  824. cell; change the destination address in a relay begin cell to the
  825. adversary's webserver; or change a user on an ftp connection from
  826. typing ``dir'' to typing ``delete *''. Any node or observer along the
  827. path could introduce such corruption in a stream.
  828. Tor prevents external adversaries by mounting this attack simply by
  829. using TLS. Addressing the insider malleability attack, however, is
  830. more complex.
  831. Rather than doing integrity checking of the relay cells at each hop,
  832. which would increase packet size
  833. by a function of path length\footnote{This is also the argument against
  834. using recent cipher modes like EAX \cite{eax} --- we don't want the added
  835. message-expansion overhead at each hop, and we don't want to leak the path
  836. length (or pad to some max path length).}, we choose to
  837. % accept passive timing attacks,
  838. % (How? I don't get it. Do we mean end-to-end traffic
  839. % confirmation attacks? -NM)
  840. and perform integrity
  841. checking only at the edges of the circuit. When Alice negotiates a key
  842. with the exit hop, they both start a SHA-1 with some derivative of that key,
  843. thus starting out with randomness that only the two of them know. From
  844. then on they each incrementally add all the data bytes flowing across
  845. the stream to the SHA-1, and each relay cell includes the first 4 bytes
  846. of the current value of the hash.
  847. The attacker must be able to guess all previous bytes between Alice
  848. and Bob on that circuit (including the pseudorandomness from the key
  849. negotiation), plus the bytes in the current cell, to remove or modify the
  850. cell. Attacks on SHA-1 where the adversary can incrementally add to a
  851. hash to produce a new valid hash \cite{practical-crypto} don't work,
  852. % XXX Do we want to cite practical crypto here, or is there a better
  853. % place to cite, or is this well-known enough to leave out a cite? -RD
  854. because all hashes are end-to-end encrypted across the circuit.
  855. The computational overhead isn't so bad, compared to doing an AES
  856. % XXX We never say we use AES. Say it somewhere above? -RD
  857. crypt at each hop in the circuit. We use only four bytes per cell to
  858. minimize overhead; the chance that an adversary will correctly guess a
  859. valid hash, plus the payload the current cell, is acceptly low, given
  860. that Alice or Bob tear down the circuit if they receive a bad hash.
  861. \SubSection{Rate limiting and fairness}
  862. Volunteers are generally more willing to run services that can limit
  863. their bandwidth usage. To accomodate them, Tor servers use a token
  864. bucket approach \cite{foo} to limit the number of bytes they
  865. receive. Tokens are added to the bucket each second (when the bucket is
  866. full, new tokens are discarded.) Each token represents permission to
  867. receive one byte from the network --- to receive a byte, the connection
  868. must remove a token from the bucket. Thus if the bucket is empty, that
  869. connection must wait until more tokens arrive. The number of tokens we
  870. add enforces a long-term average rate of incoming bytes, while still
  871. permitting short-term bursts above the allowed bandwidth. Current bucket
  872. sizes are set to ten seconds worth of traffic.
  873. Further, we want to avoid starving any Tor streams. Entire circuits
  874. could starve if we read greedily from connections and one connection
  875. uses all the remaining bandwidth. We solve this by dividing the number
  876. of tokens in the bucket by the number of connections that want to read,
  877. and reading at most that number of bytes from each connection. We iterate
  878. this procedure until the number of tokens in the bucket is under some
  879. threshold (eg 10KB), at which point we greedily read from connections.
  880. Because the Tor protocol generates roughly the same number of outgoing
  881. bytes as incoming bytes, it is sufficient in practice to rate-limit
  882. incoming bytes.
  883. % Is it? Fun attack: I send you lots of 1-byte-at-a-time TCP frames.
  884. % In response, you send lots of 256 byte cells. Can I use this to
  885. % make you exceed your outgoing bandwidth limit by a factor of 256?
  886. Further, inspired by Rennhard et al's design in \cite{anonnet}, a
  887. circuit's edges heuristically distinguish interactive streams from bulk
  888. streams by comparing the frequency with which they supply cells. We can
  889. provide good latency for interactive streams by giving them preferential
  890. service, while still getting good overall throughput to the bulk
  891. streams. Such preferential treatment presents a possible end-to-end
  892. attack, but an adversary who can observe both
  893. ends of the stream can already learn this information through timing
  894. attacks.
  895. \SubSection{Congestion control}
  896. \label{subsec:congestion}
  897. Even with bandwidth rate limiting, we still need to worry about
  898. congestion, either accidental or intentional. If enough users choose the
  899. same OR-to-OR connection for their circuits, that connection can become
  900. saturated. For example, an adversary could make a large HTTP PUT request
  901. through the onion routing network to a webserver he runs, and then
  902. refuse to read any of the bytes at the webserver end of the
  903. circuit. Without some congestion control mechanism, these bottlenecks
  904. can propagate back through the entire network. We describe our
  905. responses below.
  906. \subsubsection{Circuit-level}
  907. To control a circuit's bandwidth usage, each OR keeps track of two
  908. windows. The \emph{package window} tracks how many relay data cells the OR is
  909. allowed to package (from outside streams) for transmission back to the OP,
  910. and the \emph{deliver window} tracks how many relay data cells it is willing
  911. to deliver to streams outside the network. Each window is initialized
  912. (say, to 1000 data cells). When a data cell is packaged or delivered,
  913. the appropriate window is decremented. When an OR has received enough
  914. data cells (currently 100), it sends a relay sendme cell towards the OP,
  915. with stream ID zero. When an OR receives a relay sendme cell with stream
  916. ID zero, it increments its packaging window. Either of these cells
  917. increments the corresponding window by 100. If the packaging window
  918. reaches 0, the OR stops reading from TCP connections for all streams
  919. on the corresponding circuit, and sends no more relay data cells until
  920. receiving a relay sendme cell.
  921. The OP behaves identically, except that it must track a packaging window
  922. and a delivery window for every OR in the circuit. If a packaging window
  923. reaches 0, it stops reading from streams destined for that OR.
  924. \subsubsection{Stream-level}
  925. The stream-level congestion control mechanism is similar to the
  926. circuit-level mechanism above. ORs and OPs use relay sendme cells
  927. to implement end-to-end flow control for individual streams across
  928. circuits. Each stream begins with a package window (e.g. 500 cells),
  929. and increments the window by a fixed value (50) upon receiving a relay
  930. sendme cell. Rather than always returning a relay sendme cell as soon
  931. as enough cells have arrived, the stream-level congestion control also
  932. has to check whether data has been successfully flushed onto the TCP
  933. stream; it sends a relay sendme only when the number of bytes pending
  934. to be flushed is under some threshold (currently 10 cells worth).
  935. Currently, non-data relay cells do not affect the windows. Thus we
  936. avoid potential deadlock issues, e.g. because a stream can't send a
  937. relay sendme cell because its packaging window is empty.
  938. \subsubsection{Needs more research}
  939. We don't need to reimplement full TCP windows (with sequence numbers,
  940. the ability to drop cells when we're full and retransmit later, etc),
  941. because the TCP streams already guarantee in-order delivery of each
  942. cell. But we need to investigate further the effects of the current
  943. parameters on throughput and latency, while also keeping privacy in mind;
  944. see Section~\ref{sec:maintaining-anonymity} for more discussion.
  945. \Section{Other design decisions}
  946. \SubSection{Resource management and DoS prevention}
  947. \label{subsec:dos}
  948. Providing Tor as a public service provides many opportunities for an
  949. attacker to mount denial-of-service attacks against the network. While
  950. flow control and rate limiting (discussed in
  951. section~\ref{subsec:congestion}) prevents users from consuming more
  952. bandwidth than nodes are willing to provide, opportunities remain for
  953. consume more network resources than their fair share, or to render the
  954. network unusable for other users.
  955. First of all, there are a number of CPU-consuming denial-of-service
  956. attacks wherein an attacker can force an OR to perform expensive
  957. cryptographic operations. For example, an attacker who sends a
  958. \emph{create} cell full of junk bytes can force an OR to perform an RSA
  959. decrypt its half of the Diffie-Helman handshake. Similarly, an attacker
  960. fake the start of a TLS handshake, forcing the OR to carry out its
  961. (comparatively expensive) half of the handshake at no real computational
  962. cost to the attacker.
  963. To address these attacks, several approaches exist. First, ORs may
  964. demand proof-of-computation tokens \cite{hashcash} before beginning new
  965. TLS handshakes or accepting \emph{create} cells. So long as these
  966. tokens are easy to verify and computationally expensive to produce, this
  967. approach limits the DoS attack multiplier. Additionally, ORs may limit
  968. the rate at which they accept create cells and TLS connections, so that
  969. the computational work of doing so does not drown out the (comparatively
  970. inexpensive) work of symmetric cryptography needed to keep users'
  971. packets flowing. This rate limiting could, however, allows an attacker
  972. to slow down other users as they build new circuits.
  973. % What about link-to-link rate limiting?
  974. % This paragraph needs more references.
  975. More worrisome are distributed denial of service attacks wherein an
  976. attacker uses a large number of compromised hosts throughout the network
  977. to consume the Tor network's resources. Although these attacks are not
  978. new to the networking literature, some proposed approaches are a poor
  979. fit to anonymous networks. For example, solutions based on backtracking
  980. harmful traffic present a significant risk that an anonymity-breaking
  981. adversary could exploit the backtracking mechanism to compromise users'
  982. anonymity. [XXX So, what should we say here? -NM]
  983. % Now would be a good point to talk about twins. What the do, what
  984. % they can't.
  985. Attackers also have an opportunity to attack the Tor network by mounting
  986. attacks on the hosts and network links running it. If an attacker can
  987. successfully disrupt a single circuit or link along a virtual circuit,
  988. all currently open streams passing along that part of the circuit
  989. become unrecoverable, and are closed. The current Tor design treats
  990. such attacks as intermittent network failures, and depends on users and
  991. applications to respond or recover as appropriate. A possible future
  992. design could use an end-to-end based TCP-like acknowledgment protocol,
  993. so that no streams are lost unless the entry or exit point themselves
  994. are disrupted. This solution would require more buffering at exits,
  995. however, and its network properties still need to be investigated. [XXX
  996. That sounds really evasive. We should say more.]
  997. %[XXX Mention that OR-to-OR connections should be highly reliable
  998. % (whatever that means). If they aren't, everything can stall.]
  999. %=====================
  1000. % This stuff should go elsewhere. Probably section 2.
  1001. Channel-based anonymity designs must choose which protocol layer to
  1002. anonymize. They may choose to intercept IP packets directly, and relay
  1003. them whole (stripping the source address) as the contents of their
  1004. anonymous channels [XXX cite an example]. Alternatively, they may
  1005. accept TCP streams and relay the data in those streams along the
  1006. channel, ignoring the breakdown of that data into TCP frames. (Tor takes
  1007. this approach, as does [XXX].) Finally, they may accept
  1008. application-level protocols (such as HTTP) and relay the application
  1009. requests themselves along their anonymous channels.
  1010. This protocol-layer decision represents a compromise between flexibility
  1011. and anonymity. For example, a system that understands HTTP can strip
  1012. identifying information from those requests; can take advantage of
  1013. caching to limit the number of requests that leave the network; and can
  1014. batch or encode those requests in order to minimize the number of
  1015. connections. On the other hand, an IP-level anonymizer can handle
  1016. nearly any protocol, even ones unforeseen by their designers. TCP-level
  1017. anonymity networks like Tor present a middle approach: they are fairly
  1018. application neutral (so long as the application supports, or can be
  1019. tunneled across, TCP), but by treating application connections as data
  1020. streams rather than raw TCP packets, they avoid the well-known
  1021. inefficiencies of tunneling TCP over TCP \cite{tcp-over-tcp-is-bad}.
  1022. % Is there a better tcp-over-tcp-is-bad reference?
  1023. %Also mention that weirdo IP trickery requires kernel patches to most
  1024. %operating systems? -NM
  1025. \SubSection{Exit policies and abuse}
  1026. \label{subsec:exitpolicies}
  1027. Exit abuse is a serious barrier to wide-scale Tor deployment --- we
  1028. must block or limit attacks and other abuse that users can do through
  1029. the Tor network.
  1030. Each onion router's \emph{exit policy} describes to which external
  1031. addresses and ports the router will permit stream connections. On one end
  1032. of the spectrum are \emph{open exit} nodes that will connect anywhere;
  1033. on the other end are \emph{middleman} nodes that only relay traffic to
  1034. other Tor nodes, and \emph{private exit} nodes that only connect locally
  1035. or to addresses internal to that node's organization.
  1036. This private exit
  1037. node configuration is more secure for clients --- the adversary cannot
  1038. see plaintext traffic leaving the network (e.g. to a webserver), so he
  1039. is less sure of Alice's destination. More generally, nodes can require
  1040. a variety of forms of traffic authentication \cite{or-discex00}.
  1041. Most onnion routers will function as \emph{limited exits} that permit
  1042. connections to the world at large, but restrict access to certain abuse-prone
  1043. addresses and services.
  1044. Tor offers more reliability than the high-latency fire-and-forget
  1045. anonymous email networks, because the sender opens a TCP stream
  1046. with the remote mail server and receives an explicit confirmation of
  1047. acceptance. But ironically, the private exit node model works poorly for
  1048. email, when Tor nodes are run on volunteer machines that also do other
  1049. things, because it's quite hard to configure mail transport agents so
  1050. normal users can send mail normally, but the Tor process can only deliver
  1051. mail locally. Further, most organizations have specific hosts that will
  1052. deliver mail on behalf of certain IP ranges; Tor operators must be aware
  1053. of these hosts and consider putting them in the Tor exit policy.
  1054. The abuse issues on closed (e.g. military) networks are different
  1055. from the abuse on open networks like the Internet. While these IP-based
  1056. access controls are still commonplace on the Internet, on closed networks,
  1057. nearly all participants will be honest, and end-to-end authentication
  1058. can be assumed for anything important.
  1059. Tor is harder than minion because tcp doesn't include an abuse
  1060. address. you could reach inside the http stream and change the agent
  1061. or something, but that's a specific case and probably won't help
  1062. much anyway.
  1063. And volunteer nodes don't resolve to anonymizer.mit.edu so it never
  1064. even occurs to people that it wasn't you.
  1065. Preventing abuse of open exit nodes is an unsolved problem. Princeton's
  1066. CoDeeN project \cite{darkside} gives us a glimpse of what we're in for.
  1067. % This is more speculative than a description of our design.
  1068. but their solutions, which mainly involve rate limiting and blacklisting
  1069. nodes which do bad things, don't translate directly to Tor. Rate limiting
  1070. still works great, but Tor intentionally separates sender from recipient,
  1071. so it's hard to know which sender was the one who did the bad thing,
  1072. without just making the whole network wide open.
  1073. even limiting most nodes to allow http, ssh, and aim to exit and reject
  1074. all other stuff is sketchy, because plenty of abuse can happen over
  1075. port 80. but it's a surprisingly good start, because it blocks most things,
  1076. and because people are more used to the concept of port 80 abuse not
  1077. coming from the machine's owner.
  1078. we could also run intrusion detection system (IDS) modules at each tor
  1079. node, to dynamically monitor traffic streams for attack signatures. it
  1080. can even react when it sees a signature by closing the stream. but IDS's
  1081. don't actually work most of the time, and besides, how do you write a
  1082. signature for "is sending a mean mail"?
  1083. we should run a squid at each exit node, to provide comparable anonymity
  1084. to private exit nodes for cache hits, to speed everything up, and to
  1085. have a buffer for funny stuff coming out of port 80. we could similarly
  1086. have other exit proxies for other protocols, like mail, to check
  1087. delivered mail for being spam.
  1088. [XXX Um, I'm uncomfortable with this for several reasons.
  1089. It's not good for keeping honest nodes honest about discarding
  1090. state after it's no longer needed. Granted it keeps an external
  1091. observer from noticing how often sites are visited, but it also
  1092. allows fishing expeditions. ``We noticed you went to this prohibited
  1093. site an hour ago. Kindly turn over your caches to the authorities.''
  1094. I previously elsewhere suggested bulk transfer proxies to carve
  1095. up big things so that they could be downloaded in less noticeable
  1096. pieces over several normal looking connections. We could suggest
  1097. similarly one or a handful of squid nodes that might serve up
  1098. some of the more sensitive but common material, especially if
  1099. the relevant sites didn't want to or couldn't run their own OR.
  1100. This would be better than having everyone run a squid which would
  1101. just help identify after the fact the different history of that
  1102. node's activity. All this kind of speculation needs to move to
  1103. future work section I guess. -PS]
  1104. A mixture of open and restricted exit nodes will allow the most
  1105. flexibility for volunteers running servers. But while a large number
  1106. of middleman nodes is useful to provide a large and robust network,
  1107. a small number of exit nodes still simplifies traffic analysis because
  1108. there are fewer nodes the adversary needs to monitor, and also puts a
  1109. greater burden on the exit nodes.
  1110. The JAP cascade model is really nice because they only need one node to
  1111. take the heat per cascade. On the other hand, a hydra scheme could work
  1112. better (it's still hard to watch all the clients).
  1113. Discuss importance of public perception, and how abuse affects it.
  1114. ``Usability is a security parameter''. ``Public Perception is also a
  1115. security parameter.''
  1116. Discuss smear attacks.
  1117. \SubSection{Directory Servers}
  1118. \label{subsec:dirservers}
  1119. First-generation Onion Routing designs \cite{or-jsac98,freedom2-arch} did
  1120. % is or-jsac98 the right cite here? what's our stock OR cite? -RD
  1121. in-band network status updates: each router flooded a signed statement
  1122. to its neighbors, which propagated it onward. But anonymizing networks
  1123. have different security goals than typical link-state routing protocols.
  1124. For example, we worry more about delays (accidental or intentional)
  1125. that can cause different parts of the network to have different pictures
  1126. of link-state and topology. We also worry about attacks to deceive a
  1127. client about the router membership list, topology, or current network
  1128. state. Such \emph{partitioning attacks} on client knowledge help an
  1129. adversary with limited resources to efficiently deploy those resources
  1130. when attacking a target.
  1131. Instead, Tor uses a small group of redundant directory servers to
  1132. track network topology and node state such as current keys and exit
  1133. policies. The directory servers are normal onion routers, but there are
  1134. only a few of them and they are more trusted. They listen on a separate
  1135. port as an HTTP server, both so participants can fetch current network
  1136. state and router lists (a \emph{directory}), and so other onion routers
  1137. can upload their router descriptors.
  1138. [[mention that descriptors are signed with long-term keys; ORs publish
  1139. regularly to dirservers; policies for generating directories; key
  1140. rotation (link, onion, identity); Everybody already know directory
  1141. keys; how to approve new nodes (advogato, sybil, captcha (RTT));
  1142. policy for handling connections with unknown ORs; diff-based
  1143. retrieval; diff-based consensus; separate liveness from descriptor
  1144. list]]
  1145. Of course, a variety of attacks remain. An adversary who controls a
  1146. directory server can track certain clients by providing different
  1147. information --- perhaps by listing only nodes under its control
  1148. as working, or by informing only certain clients about a given
  1149. node. Moreover, an adversary without control of a directory server can
  1150. still exploit differences among client knowledge. If Eve knows that
  1151. node $M$ is listed on server $D_1$ but not on $D_2$, she can use this
  1152. knowledge to link traffic through $M$ to clients who have queried $D_1$.
  1153. Thus these directory servers must be synchronized and redundant. The
  1154. software is distributed with the signature public key of each directory
  1155. server, and directories must be signed by a threshold of these keys.
  1156. The directory servers in Tor are modeled after those in Mixminion
  1157. \cite{minion-design}, but our situation is easier. Firstly, we make the
  1158. simplifying assumption that all participants agree on who the directory
  1159. servers are. Secondly, Mixminion needs to predict node behavior ---
  1160. that is, build a reputation system for guessing future performance of
  1161. nodes based on past performance, and then figure out a way to build
  1162. a threshold consensus of these predictions. Tor just needs to get a
  1163. threshold consensus of the current state of the network.
  1164. The threshold consensus can be reached with standard Byzantine agreement
  1165. techniques \cite{castro-liskov}.
  1166. % Should I just stop the section here? Is the rest crap? -RD
  1167. But this library, while more efficient than previous Byzantine agreement
  1168. systems, is still complex and heavyweight for our purposes: we only need
  1169. to compute a single algorithm, and we do not require strict in-order
  1170. computation steps. Indeed, the complexity of Byzantine agreement protocols
  1171. threatens our security, because users cannot easily understand it and
  1172. thus have less trust in the directory servers. The Tor directory servers
  1173. build a consensus directory
  1174. through a simple four-round broadcast protocol. First, each server signs
  1175. and broadcasts its current opinion to the other directory servers; each
  1176. server then rebroadcasts all the signed opinions it has received. At this
  1177. point all directory servers check to see if anybody's cheating. If so,
  1178. directory service stops, the humans are notified, and that directory
  1179. server is permanently removed from the network. Assuming no cheating,
  1180. each directory server then computes a local algorithm on the set of
  1181. opinions, resulting in a uniform shared directory. Then the servers sign
  1182. this directory and broadcast it; and finally all servers rebroadcast
  1183. the directory and all the signatures.
  1184. The rebroadcast steps ensure that a directory server is heard by either
  1185. all of the other servers or none of them (some of the links between
  1186. directory servers may be down). Broadcasts are feasible because there
  1187. are so few directory servers (currently 3, but we expect to use as many
  1188. as 9 as the network scales). The actual local algorithm for computing
  1189. the shared directory is straightforward, and is described in the Tor
  1190. specification \cite{tor-spec}.
  1191. % we should, uh, add this to the spec. oh, and write it. -RD
  1192. Using directory servers rather than flooding approaches provides
  1193. simplicity and flexibility. For example, they don't complicate
  1194. the analysis when we start experimenting with non-clique network
  1195. topologies. And because the directories are signed, they can be cached at
  1196. all the other onion routers (or even elsewhere). Thus directory servers
  1197. are not a performance bottleneck when we have many users, and also they
  1198. won't aid traffic analysis by forcing clients to periodically announce
  1199. their existence to any central point.
  1200. % Mention Hydra as an example of non-clique topologies. -NM, from RD
  1201. % also find some place to integrate that dirservers have to actually
  1202. % lay test circuits and use them, otherwise routers could connect to
  1203. % the dirservers but discard all other traffic.
  1204. % in some sense they're like reputation servers in \cite{mix-acc} -RD
  1205. \Section{Rendezvous points: location privacy}
  1206. \label{sec:rendezvous}
  1207. Rendezvous points are a building block for \emph{location-hidden services}
  1208. (aka responder anonymity) in the Tor network. Location-hidden services
  1209. means Bob can offer a TCP service, such as a webserver, without revealing
  1210. the IP of that service. One motivation for location privacy is to provide
  1211. protection against DDoS attacks: attackers are forced to attack the
  1212. onion routing network as a whole rather than just Bob's IP.
  1213. We provide this censorship resistance for Bob by allowing him to
  1214. advertise several onion routers (his \emph{Introduction Points}) as his
  1215. public location. Alice, the client, chooses a node for her \emph{Meeting
  1216. Point}. She connects to one of Bob's introduction points, informs him
  1217. about her rendezvous point, and then waits for him to connect to the
  1218. rendezvous
  1219. point. This extra level of indirection means Bob's introduction points
  1220. don't open themselves up to abuse by serving files directly, eg if Bob
  1221. chooses a node in France to serve material distateful to the French,
  1222. %
  1223. % We need a more legitimate-sounding reason here.
  1224. %
  1225. or if Bob's service tends to get DDoS'ed by script kiddies.
  1226. The extra level of indirection also allows Bob to respond to some requests
  1227. and ignore others.
  1228. We provide the necessary glue so that Alice can view webpages from Bob's
  1229. location-hidden webserver with minimal invasive changes. Both Alice and
  1230. Bob must run local onion proxies.
  1231. The steps of a rendezvous:
  1232. \begin{tightlist}
  1233. \item Bob chooses some Introduction Points, and advertises them on a
  1234. Distributed Hash Table (DHT).
  1235. \item Bob establishes onion routing connections to each of his
  1236. Introduction Points, and waits.
  1237. \item Alice learns about Bob's service out of band (perhaps Bob told her,
  1238. or she found it on a website). She looks up the details of Bob's
  1239. service from the DHT.
  1240. \item Alice chooses and establishes a Rendezvous Point (RP) for this
  1241. transaction.
  1242. \item Alice goes to one of Bob's Introduction Points, and gives it a blob
  1243. (encrypted for Bob) which tells him about herself, the RP
  1244. she chose, and the first half of an ephemeral key handshake. The
  1245. Introduction Point sends the blob to Bob.
  1246. \item Bob chooses whether to ignore the blob, or to onion route to RP.
  1247. Let's assume the latter.
  1248. \item RP plugs together Alice and Bob. Note that RP can't recognize Alice,
  1249. Bob, or the data they transmit (they share a session key).
  1250. \item Alice sends a Begin cell along the circuit. It arrives at Bob's
  1251. onion proxy. Bob's onion proxy connects to Bob's webserver.
  1252. \item Data goes back and forth as usual.
  1253. \end{tightlist}
  1254. When establishing an introduction point, Bob provides the onion router
  1255. with a public ``introduction'' key. The hash of this public key
  1256. identifies a unique service, and (since Bob is required to sign his
  1257. messages) prevents anybody else from usurping Bob's introduction point
  1258. in the future. Bob uses the same public key when establishing the other
  1259. introduction points for that service.
  1260. The blob that Alice gives the introduction point includes a hash of Bob's
  1261. public key to identify the service, an optional initial authentication
  1262. token (the introduction point can do prescreening, eg to block replays),
  1263. and (encrypted to Bob's public key) the location of the rendezvous point,
  1264. a rendezvous cookie Bob should tell RP so he gets connected to
  1265. Alice, an optional authentication token so Bob can choose whether to respond,
  1266. and the first half of a DH key exchange. When Bob connects to RP
  1267. and gets connected to Alice's pipe, his first cell contains the
  1268. other half of the DH key exchange.
  1269. The authentication tokens can be used to provide selective access to users
  1270. proportional to how important it is that they main uninterrupted access
  1271. to the service. During normal situations, Bob's service might simply be
  1272. offered directly from mirrors; Bob also gives out authentication cookies
  1273. to special users. When those mirrors are knocked down by DDoS attacks,
  1274. those special users can switch to accessing Bob's service via the Tor
  1275. rendezvous system.
  1276. \SubSection{Integration with user applications}
  1277. For each service Bob offers, he configures his local onion proxy to know
  1278. the local IP and port of the server, a strategy for authorizating Alices,
  1279. and a public key. We assume the existence of a robust decentralized
  1280. efficient lookup system which allows authenticated updates, eg
  1281. \cite{cfs:sosp01}. (Each onion router could run a node in this lookup
  1282. system; also note that as a stopgap measure, we can just run a simple
  1283. lookup system on the directory servers.) Bob publishes into the DHT
  1284. (indexed by the hash of the public key) the public key, an expiration
  1285. time (``not valid after''), and the current introduction points for that
  1286. service. Note that Bob's webserver is unmodified, and doesn't even know
  1287. that it's hidden behind the Tor network.
  1288. As far as Alice's experience goes, we require that her client interface
  1289. remain a SOCKS proxy, and we require that she shouldn't have to modify
  1290. her applications. Thus we encode all of the necessary information into
  1291. the hostname (more correctly, fully qualified domain name) that Alice
  1292. uses, eg when clicking on a url in her browser. Location-hidden services
  1293. use the special top level domain called `.onion': thus hostnames take the
  1294. form x.y.onion where x encodes the hash of PK, and y is the authentication
  1295. cookie. Alice's onion proxy examines hostnames and recognizes when they're
  1296. destined for a hidden server. If so, it decodes the PK and starts the
  1297. rendezvous as described in the table above.
  1298. \subsection{Previous rendezvous work}
  1299. Ian Goldberg developed a similar notion of rendezvous points for
  1300. low-latency anonymity systems \cite{ian-thesis}. His ``service tag''
  1301. is the same concept as our ``hash of service's public key''. We make it
  1302. a hash of the public key so it can be self-authenticating, and so the
  1303. client can recognize the same service with confidence later on. His
  1304. design differs from ours in the following ways though. Firstly, Ian
  1305. suggests that the client should manually hunt down a current location of
  1306. the service via Gnutella; whereas our use of the DHT makes lookup faster,
  1307. more robust, and transparent to the user. Secondly, in Tor the client
  1308. and server can share ephemeral DH keys, so at no point in the path is
  1309. the plaintext
  1310. exposed. Thirdly, our design is much more practical for deployment in a
  1311. volunteer network, in terms of getting volunteers to offer introduction
  1312. and rendezvous point services. The introduction points do not output any
  1313. bytes to the clients, and the rendezvous points don't know the client,
  1314. the server, or the stuff being transmitted. The indirection scheme
  1315. is also designed with authentication/authorization in mind -- if the
  1316. client doesn't include the right cookie with its request for service,
  1317. the server doesn't even acknowledge its existence.
  1318. \Section{Analysis}
  1319. \label{sec:analysis}
  1320. In this section, we discuss how well Tor meets our stated design goals
  1321. and its resistance to attacks.
  1322. Goals:
  1323. \begin{description}
  1324. \item [Basic Anonymity:] Because traffic is encrypted, changing in
  1325. appearance, and can flow from anywhere to anywhere within the
  1326. network, a simple observer that cannot see both the initiator
  1327. activity and the corresponding activity where the responder talks to
  1328. the network will not be able to link the initiator and responder.
  1329. Nor is it possible to directly correlate any two communication
  1330. sessions as coming from a single source without additional
  1331. information. Resistance to specific anonymity threats will be discussed
  1332. below.
  1333. \item[Deployability:]
  1334. \item[Usability:]
  1335. \item[Flexibility:]
  1336. \item[Conservative design:]
  1337. \end{description}
  1338. Basic
  1339. How well do we resist chosen adversary?
  1340. How well do we meet stated goals?
  1341. Mention jurisdictional arbitrage.
  1342. Pull attacks and defenses into analysis as a subsection
  1343. \Section{Maintaining anonymity in Tor}
  1344. \label{sec:maintaining-anonymity}
  1345. \footnote{The first Onion Routing design \cite{or-ih96} protected against
  1346. this threat to some
  1347. extent by requiring users to hide network access behind an onion
  1348. router/firewall that was also forwarding traffic from other nodes.
  1349. However, it is desirable for users to
  1350. benefit from Onion Routing even when they can't run their own
  1351. onion routers.
  1352. %Such users, especially if they engage in certain unusual
  1353. %communication behaviors, may be identifiable \cite{wright03}.
  1354. %To
  1355. %complicate the possibility of such attacks Tor multiplexes many
  1356. %stream down each circuit, but still rotates the circuit
  1357. %periodically to avoid too much linkability from requests on a single
  1358. %circuit.
  1359. }
  1360. I probably should have noted that this means loops will be on at least
  1361. five hop routes, which should be rare given the distribution. I'm
  1362. realizing that this is reproducing some of the thought that led to a
  1363. default of five hops in the original onion routing design. There were
  1364. some different assumptions, which I won't spell out now. Note that
  1365. enclave level protections really change these assumptions. If most
  1366. circuits are just two hops, then just a single link observer will be
  1367. able to tell that two enclaves are communicating with high probability.
  1368. So, it would seem that enclaves should have a four node minimum circuit
  1369. to prevent trivial circuit insider identification of the whole circuit,
  1370. and three hop minimum for circuits from an enclave to some nonclave
  1371. responder. But then... we would have to make everyone obey these rules
  1372. or a node that through timing inferred it was on a four hop circuit
  1373. would know that it was probably carrying enclave to enclave traffic.
  1374. Which... if there were even a moderate number of bad nodes in the
  1375. network would make it advantageous to break the connection to conduct
  1376. a reformation intersection attack. Ahhh! I gotta stop thinking
  1377. about this and work on the paper some before the family wakes up.
  1378. On Sat, Oct 25, 2003 at 06:57:12AM -0400, Paul Syverson wrote:
  1379. > Which... if there were even a moderate number of bad nodes in the
  1380. > network would make it advantageous to break the connection to conduct > a reformation intersection attack. Ahhh! I gotta stop thinking > about this and work on the paper some before the family wakes up.
  1381. This is the sort of issue that should go in the 'maintaining anonymity
  1382. with tor' section towards the end. :)
  1383. Email from between roger and me to beginning of section above. Fix and move.
  1384. [Put as much of this as a part of open issues as is possible.]
  1385. [what's an anonymity set?]
  1386. packet counting attacks work great against initiators. need to do some
  1387. level of obfuscation for that. standard link padding for passive link
  1388. observers. long-range padding for people who own the first hop. are
  1389. we just screwed against people who insert timing signatures into your
  1390. traffic?
  1391. Even regardless of link padding from Alice to the cloud, there will be
  1392. times when Alice is simply not online. Link padding, at the edges or
  1393. inside the cloud, does not help for this.
  1394. how often should we pull down directories? how often send updated
  1395. server descs?
  1396. when we start up the client, should we build a circuit immediately,
  1397. or should the default be to build a circuit only on demand? should we
  1398. fetch a directory immediately?
  1399. would we benefit from greater synchronization, to blend with the other
  1400. users? would the reduced speed hurt us more?
  1401. does the "you can't see when i'm starting or ending a stream because
  1402. you can't tell what sort of relay cell it is" idea work, or is just
  1403. a distraction?
  1404. does running a server actually get you better protection, because traffic
  1405. coming from your node could plausibly have come from elsewhere? how
  1406. much mixing do you need before this is actually plausible, or is it
  1407. immediately beneficial because many adversary can't see your node?
  1408. do different exit policies at different exit nodes trash anonymity sets,
  1409. or not mess with them much?
  1410. do we get better protection against a realistic adversary by having as
  1411. many nodes as possible, so he probably can't see the whole network,
  1412. or by having a small number of nodes that mix traffic well? is a
  1413. cascade topology a more realistic way to get defenses against traffic
  1414. confirmation? does the hydra (many inputs, few outputs) topology work
  1415. better? are we going to get a hydra anyway because most nodes will be
  1416. middleman nodes?
  1417. using a circuit many times is good because it's less cpu work.
  1418. good because of predecessor attacks with path rebuilding.
  1419. bad because predecessor attacks can be more likely to link you with a
  1420. previous circuit since you're so verbose.
  1421. bad because each thing you do on that circuit is linked to the other
  1422. things you do on that circuit.
  1423. how often to rotate?
  1424. how to decide when to exit from middle?
  1425. when to truncate and re-extend versus when to start new circuit?
  1426. Because Tor runs over TCP, when one of the servers goes down it seems
  1427. that all the circuits (and thus streams) going over that server must
  1428. break. This reduces anonymity because everybody needs to reconnect
  1429. right then (does it? how much?) and because exit connections all break
  1430. at the same time, and it also reduces usability. It seems the problem
  1431. is even worse in a p2p environment, because so far such systems don't
  1432. really provide an incentive for nodes to stay connected when they're
  1433. done browsing, so we would expect a much higher churn rate than for
  1434. onion routing. Are there ways of allowing streams to survive the loss
  1435. of a node in the path?
  1436. discuss topologies. Cite George's non-freeroutes paper. Maybe this
  1437. graf goes elsewhere.
  1438. discuss attracting users; incentives; usability.
  1439. Choosing paths and path lengths.
  1440. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1441. \Section{Attacks and Defenses}
  1442. \label{sec:attacks}
  1443. Below we summarize a variety of attacks and how well our design withstands
  1444. them.
  1445. \begin{enumerate}
  1446. \item \textbf{Passive attacks}
  1447. \begin{itemize}
  1448. \item \emph{Observing user behavior.}
  1449. \item \emph{End-to-end Timing correlation.}
  1450. \item \emph{End-to-end Size correlation.}
  1451. \item \emph{Website fingerprinting attacks} old onion routing is
  1452. vulnerable to website fingerprinting attacks like david martin's
  1453. from usenix sec and drew's from pet2002. so is tor. we need to send
  1454. some padding or something, including long-range padding (to foil the
  1455. first hop), to solve this. let's hope somebody writes a followup to
  1456. \cite{defensive-dropping} that tells us what, exactly, to do, and why,
  1457. exactly, it helps. but website fingerprinting intersection attacks
  1458. \cite{dogan:pet2002} still seem an open problem.
  1459. \item \emph{Option distinguishability.} User configuration options.
  1460. A: We standardize on how clients behave. cite econymics.
  1461. \item sub of the above on exit policy\\
  1462. Partitioning based on exit policy.
  1463. Run a rare exit server/something other people won't allow.
  1464. DOS three of the 4 who would allow a certain exit.
  1465. \item Content analysis. Not our main thing, but, Privoxy to
  1466. anonymization of data stream.
  1467. \end{itemize}
  1468. \item \textbf{Active attacks}
  1469. \begin{itemize}
  1470. \item \emph{Key compromise.} Talk about all three keys. 3 bullets
  1471. \item \emph{Iterated subpoena.} Legal roving adversary. Works bad against
  1472. this because of ephemeral keys. Criticize pets paper in section 2 for
  1473. failing to consider this when describing roving adversary.
  1474. \item \emph{Run recipient.} Be the Web server.
  1475. \item \emph{Run a hostile node.}
  1476. \item \emph{Compromise entire path.} Directory servers controlling admission
  1477. to network. But if you do compromise it, we're toast.
  1478. \item \emph{Selectively DoS OR.} Flood the pipe. We're toast. Rate limiting.
  1479. We can't stop flooding creates through all your neighbors. Router twins
  1480. is a useful fallback, makes you hit all the twins.
  1481. \item \emph{Introduce timing into messages.}
  1482. \item \emph{Tagging attacks.}
  1483. Integrity checking stops this.
  1484. Subcase of running a hostile node:
  1485. the exit node can change the content you're getting to try to
  1486. trick you. similarly, when it rejects you due to exit policy,
  1487. it could give you a bad IP that sends you somewhere else.
  1488. \end{itemize}
  1489. \item \emph{replaying traffic} Can't in Tor. NonSSL anonymizer.
  1490. \item Do bad things with the Tor network, so we are hated and
  1491. get shut down. Now the user you want to watch has to use anonymizer.
  1492. Exit policy's are a start.
  1493. \item Send spam through the network. Exit policy (no open relay) and
  1494. rate limiting. We won't send to more than 8 people at a time. See
  1495. section 5.1.
  1496. we rely on DNS being globally consistent. if people in africa resolve
  1497. IPs differently, then asking to extend a circuit to a certain IP can
  1498. give away your origin.
  1499. \item \textbf{Directory attacks}
  1500. \begin{itemize}
  1501. \item knock out a dirserver
  1502. \item knock out half the dirservers
  1503. \item trick user into using different software (with different dirserver
  1504. keys)
  1505. \item OR connects to the dirservers but nowhere else
  1506. \item foo
  1507. \end{itemize}
  1508. \item \textbf{Attacks against rendezvous points}
  1509. \begin{itemize}
  1510. \item foo
  1511. \end{itemize}
  1512. \end{enumerate}
  1513. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1514. \Section{Future Directions and Open Problems}
  1515. \label{sec:conclusion}
  1516. % Mention that we need to do TCP over tor for reliability.
  1517. Tor brings together many innovations into
  1518. a unified deployable system. But there are still several attacks that
  1519. work quite well, as well as a number of sustainability and run-time
  1520. issues remaining to be ironed out. In particular:
  1521. \begin{itemize}
  1522. \item \emph{Scalability:} Since Tor's emphasis currently is on simplicity
  1523. of design and deployment, the current design won't easily handle more
  1524. than a few hundred servers, because of its clique topology. Restricted
  1525. route topologies \cite{danezis-pets03} promise comparable anonymity
  1526. with much better scaling properties, but we must solve problems like
  1527. how to randomly form the network without introducing net attacks.
  1528. % [cascades are a restricted route topology too. we must mention
  1529. % earlier why we're not satisfied with the cascade approach.]-RD
  1530. % [We do. At least
  1531. \item \emph{Cover traffic:} Currently we avoid cover traffic because
  1532. it introduces clear performance and bandwidth costs, but and its
  1533. security properties are not well understood. With more research
  1534. \cite{SS03,defensive-dropping}, the price/value ratio may change, both for
  1535. link-level cover traffic and also long-range cover traffic. In particular,
  1536. we expect restricted route topologies to reduce the cost of cover traffic
  1537. because there are fewer links to cover.
  1538. \item \emph{Better directory distribution:} Even with the threshold
  1539. directory agreement algorithm described in \ref{subsec:dirservers},
  1540. the directory servers are still trust bottlenecks. We must find more
  1541. decentralized yet practical ways to distribute up-to-date snapshots of
  1542. network status without introducing new attacks.
  1543. \item \emph{Implementing location-hidden servers:} While
  1544. Section~\ref{sec:rendezvous} provides a design for rendezvous points and
  1545. location-hidden servers, this feature has not yet been implemented.
  1546. We will likely encounter additional issues, both in terms of usability
  1547. and anonymity, that must be resolved.
  1548. \item \emph{Wider-scale deployment:} The original goal of Tor was to
  1549. gain experience in deploying an anonymizing overlay network, and learn
  1550. from having actual users. We are now at the point where we can start
  1551. deploying a wider network. We will see what happens!
  1552. % ok, so that's hokey. fix it. -RD
  1553. \item \emph{Further specification review:} Foo.
  1554. \end{itemize}
  1555. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1556. %% commented out for anonymous submission
  1557. %\Section{Acknowledgments}
  1558. % Peter Palfrader for editing
  1559. % Bram Cohen for congestion control discussions
  1560. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1561. \bibliographystyle{latex8}
  1562. \bibliography{tor-design}
  1563. \end{document}
  1564. % Style guide:
  1565. % U.S. spelling
  1566. % avoid contractions (it's, can't, etc.)
  1567. % 'mix', 'mixes' (as noun)
  1568. % 'mix-net'
  1569. % 'mix', 'mixing' (as verb)
  1570. % 'middleman' [Not with a hyphen; the hyphen has been optional
  1571. % since Middle English.]
  1572. % 'nymserver'
  1573. % 'Cypherpunk', 'Cypherpunks', 'Cypherpunk remailer'
  1574. % 'Onion Routing design', 'onion router' [note capitalization]
  1575. % 'SOCKS'
  1576. %
  1577. %
  1578. % 'Substitute ``Damn'' every time you're inclined to write ``very;'' your
  1579. % editor will delete it and the writing will be just as it should be.'
  1580. % -- Mark Twain