path-spec.txt 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374
  1. $Id$
  2. Tor Path Specification
  3. Roger Dingledine
  4. Nick Mathewson
  5. Note: This is an attempt to specify Tor as currently implemented. Future
  6. versions of Tor will implement improved algorithms.
  7. This document tries to cover how Tor chooses to build circuits and assign
  8. streams to circuits. Other implementations MAY take other approaches, but
  9. implementors should be aware of the anonymity and load-balancing implications
  10. of their choices.
  11. THIS SPEC ISN'T DONE OR CORRECT YET.
  12. 1. General operation
  13. Tor begins building circuits as soon as it has enough directory
  14. information to do so (see section 5.1 of dir-spec.txt). Some circuits are
  15. built preemptively because we expect to need them later (for user
  16. traffic), and some are built because of immediate need (for user traffic
  17. that no current circuit can handle, for testing the network or our
  18. reachability, and so on).
  19. When a client application creates a new stream (by opening a SOCKS
  20. connection or launching a resolve request), we attach it to an appropriate
  21. open circuit if one exists, or wait if an appropriate circuit is
  22. in-progress. We launch a new circuit only
  23. if no current circuit can handle the request. We rotate circuits over
  24. time to avoid some profiling attacks.
  25. To build a circuit, we choose all the nodes we want to use, and then
  26. construct the circuit. Sometimes, when we want a circuit that ends at a
  27. given hop, and we have an appropriate unused circuit, we "cannibalize" the
  28. existing circuit and extend it to the new terminus.
  29. These processes are described in more detail below.
  30. This document describes Tor's automatic path selection logic only; path
  31. selection can be overridden by a controller (with the EXTENDCIRCUIT and
  32. ATTACHSTREAM commands). Paths constructed through these means may
  33. violate some constraints given below.
  34. 1b. Terminology
  35. A "path" is an ordered sequence of nodes, not yet built as a circuit.
  36. A "clean" circuit is one that has not yet been used for any traffic.
  37. A "fast" or "stable" or "valid" node is one that has the 'Fast' or
  38. 'Stable' or 'Valid' flag
  39. set respectively, based on our current directory information. A "fast"
  40. or "stable" circuit is one consisting only of "fast" or "stable" nodes.
  41. In an "exit" circuit, the final node is chosen based on waiting stream
  42. requests if any, and in any case it avoids nodes with exit policy of
  43. "reject *:*". An "internal" circuit, on the other hand, is one where
  44. the final node is chosen just like a middle node (ignoring its exit
  45. policy).
  46. A "request" is a client-side stream or DNS resolve that needs to be
  47. served by a circuit.
  48. A "pending" circuit is one that we have started to build, but which has
  49. not yet completed.
  50. A circuit or path "supports" a request if it is okay to use the
  51. circuit/path to fulfill the request, according to the rules given below.
  52. A circuit or path "might support" a request if some aspect of the request
  53. is unknown (usually its target IP), but we believe the path probably
  54. supports the request according to the rules given below.
  55. 2. Building circuits
  56. 2.1. When we build.
  57. 2.1.1. Clients build circuits preemptively
  58. When running as a client, Tor tries to maintain at least a certain
  59. number of clean circuits, so that new streams can be handled
  60. quickly. To increase the likelihood of success, Tor tries to
  61. predict what circuits will be useful by choosing from among nodes
  62. that support the ports we have used in the recent past (by default
  63. one hour). Specifically, on startup Tor tries to maintain one clean
  64. fast exit circuit that allows connections to port 80, and at least
  65. two internal circuits in case we get a resolve request or hidden
  66. service request (at least three internal circuits if we _run_ a
  67. hidden service).
  68. After that, Tor will adapt the circuits that it preemptively builds
  69. based on the requests it sees from the user: it tries to have a clean
  70. fast exit circuit available for every port seen recently (one circuit
  71. is adequate for many predicted ports -- it doesn't keep a separate
  72. circuit for each port), and it tries to have the above internal
  73. circuits available if we've seen resolves or hidden service activity
  74. recently. If there are 12 clean circuits open, it doesn't open more
  75. even if it has more predictions. Lastly, note that if there are no
  76. requests from the user for an hour, Tor will predict no use and build
  77. no preemptive circuits.
  78. The Tor client SHOULD NOT store its list of predicted requests to a
  79. persistent medium.
  80. 2.1.2. Clients build circuits on demand
  81. Additionally, when a client request exists that no circuit (built or
  82. pending) might support, we create a new circuit to support the request.
  83. We do so by picking a request arbitrarily, launching a circuit to
  84. support it, and repeating until every unattached request might be
  85. supported by a pending or built circuit.
  86. For hidden service interations, we can "cannibalize" a clean internal
  87. circuit if one is available, so we don't need to build those circuits
  88. from scratch on demand.
  89. We can also cannibalize clean circuits when the client asks to exit
  90. at a given node -- either via mapaddress or the ".exit" notation,
  91. or because the destination is running at the same location as an
  92. exit node.
  93. 2.1.3. Servers build circuits for testing reachability
  94. Tor servers test reachability of their ORPort on start and whenever
  95. their IP address changes.
  96. XXXX
  97. 2.1.4. Hidden-service circuits
  98. See section 4 below.
  99. 2.1.5. Rate limiting of failed circuits
  100. If we fail to build a circuit N times in a X second period (see Section
  101. 2.3 for how this works), we stop building circuits until the X seconds
  102. have elapsed.
  103. XXXX
  104. 2.1.6. When to tear down circuits
  105. XXXX
  106. 2.2. Path selection and constraints
  107. We choose the path for each new circuit before we build it. We choose the
  108. exit node first, followed by the other nodes in the circuit. All paths
  109. we generate obey the following constraints:
  110. - We do not choose the same router twice for the same path.
  111. - We do not choose any router in the same family as another in the same
  112. path.
  113. - We do not choose more than one router in a given /16 subnet
  114. (unless EnforceDistinctSubnets is 0).
  115. - We don't choose any non-running or non-valid router unless we have
  116. been configured to do so. By default, we are configured to allow
  117. non-valid routers in "middle" and "rendezvous" positions.
  118. - If we're using Guard nodes, the first node must be a Guard (see 5
  119. below)
  120. - XXXX Choosing the length
  121. For circuits that do not need to be not "fast", when choosing among
  122. multiple candidates for a path element, we choose randomly.
  123. For "fast" circuits, we pick a given router as an exit with probability
  124. proportional to its advertised bandwidth [the smaller of the 'rate' and
  125. 'observed' arguments to the "bandwidth" element in its descriptor]. If a
  126. router's advertised bandwidth is greater than MAX_BELIEVABLE_BANDWIDTH
  127. (1.5 MB/s), we clip to that value.
  128. For non-exit positions on "fast" circuits, we pick routers as above, but
  129. we weight the clipped advertised bandwidth of Exit-flagged nodes depending
  130. on the fraction of bandwidth available from non-Exit nodes. Call the
  131. total clipped advertised bandwidth for Exit nodes under consideration E,
  132. and the total clipped advertised bandwidth for non-Exit nodes under
  133. consideration N. If E<N/2, we do not consider Exit-flagged nodes.
  134. Otherwise, we weight their bandwidth with the factor (E-N/2)/(N+E-N/2) ==
  135. (2E - N)/(2E + N). This ensures that bandwidth is evenly distributed over
  136. nodes in 3-hop paths.
  137. Additionally, we may be building circuits with one or more requests in
  138. mind. Each kind of request puts certain constraints on paths:
  139. - All service-side introduction circuits and all rendezvous paths
  140. should be Stable.
  141. - All connection requests for connections that we think will need to
  142. stay open a long time require Stable circuits. Currently, Tor decides
  143. this by examining the request's target port, and comparing it to a
  144. list of "long-lived" ports. (Default: 21, 22, 706, 1863, 5050,
  145. 5190, 5222, 5223, 6667, 6697, 8300.)
  146. - DNS resolves require an exit node whose exit policy is not equivalent
  147. to "reject *:*".
  148. - Reverse DNS resolves require a version of Tor with advertised eventdns
  149. support (available in Tor 0.1.2.1-alpha-dev and later).
  150. - All connection requests require an exit node whose exit policy
  151. supports their target address and port (if known), or which "might
  152. support it" (if the address isn't known). See 2.2.1.
  153. - Rules for Fast? XXXXX
  154. 2.2.1. Choosing an exit
  155. If we know what IP address we want to resolve, we can trivially tell
  156. whether a given router will support it by simulating its declared
  157. exit policy.
  158. Because we often connect to addresses of the form hostname:port, we do not
  159. always know the target IP address when we select an exit node. In these
  160. cases, we need to pick an exit node that "might support" connections to a
  161. given address port with an unknown address. An exit node "might support"
  162. such a connection if any clause that accepts any connections to that port
  163. precedes all clauses (if any) that reject all connections to that port.
  164. Unless requested to do so by the user, we never choose an exit server
  165. flagged as "BadExit" by more than half of the authorities who advertise
  166. themselves as listing bad exits.
  167. 2.2.2. User configuration
  168. Users can alter the default behavior for path selection with configuration
  169. options.
  170. - If "ExitNodes" is provided, then every request requires an exit node on
  171. the ExitNodes list. (If a request is supported by no nodes on that list,
  172. and StrictExitNodes is false, then Tor treats that request as if
  173. ExitNodes were not provided.)
  174. - "EntryNodes" and "StrictEntryNodes" behave analogously.
  175. - If a user tries to connect to or resolve a hostname of the form
  176. <target>.<servername>.exit, the request is rewritten to a request for
  177. <target>, and the request is only supported by the exit whose nickname
  178. or fingerprint is <servername>.
  179. 2.3. Handling failure
  180. If an attempt to extend a circuit fails (either because the first create
  181. failed or a subsequent extend failed) then the circuit is torn down and is
  182. no longer pending. (XXXX really?) Requests that might have been
  183. supported by the pending circuit thus become unsupported, and a new
  184. circuit needs to be constructed.
  185. If a stream "begin" attempt fails with an EXITPOLICY error, we
  186. decide that the exit node's exit policy is not correctly advertised,
  187. so we treat the exit node as if it were a non-exit until we retrieve
  188. a fresh descriptor for it.
  189. XXXX
  190. 3. Attaching streams to circuits
  191. When a circuit that might support a request is built, Tor tries to attach
  192. the request's stream to the circuit and sends a BEGIN or RESOLVE relay
  193. cell as appropriate. If the request completes unsuccessfully, Tor
  194. considers the reason given in the CLOSE relay cell. [XXX yes, and?]
  195. After a request has remained unattached for [XXXX interval?], Tor
  196. abandons the attempt and signals an error to the client as appropriate
  197. (e.g., by closing the SOCKS connection).
  198. XXX Timeouts and when Tor auto-retries.
  199. * What stream-end-reasons are appropriate for retrying.
  200. If no reply to BEGIN/RESOLVE, then the stream will timeout and fail.
  201. 4. Hidden-service related circuits
  202. XXX Tracking expected hidden service use (client-side and hidserv-side)
  203. 5. Guard nodes
  204. We use Guard nodes (also called "helper nodes" in the literature) to
  205. prevent certain profiling attacks. Here's the risk: if we choose entry and
  206. exit nodes at random, and an attacker controls C out of N servers
  207. (ignoring advertised bandwidth), then the
  208. attacker will control the entry and exit node of any given circuit with
  209. probability (C/N)^2. But as we make many different circuits over time,
  210. then the probability that the attacker will see a sample of about (C/N)^2
  211. of our traffic goes to 1. Since statistical sampling works, the attacker
  212. can be sure of learning a profile of our behavior.
  213. If, on the other hand, we picked an entry node and held it fixed, we would
  214. have probability C/N of choosing a bad entry and being profiled, and
  215. probability (N-C)/N of choosing a good entry and not being profiled.
  216. When guard nodes are enabled, Tor maintains an ordered list of entry nodes
  217. as our chosen guards, and store this list persistently to disk. If a Guard
  218. node becomes unusable, rather than replacing it, Tor adds new guards to the
  219. end of the list. When it comes time to choose an entry, Tor chooses at
  220. random from among the first NumEntryGuards (default 3) usable guards on the
  221. list. If there are not at least 2 usable guards on the list, Tor adds
  222. routers until there are, or until there are no more usable routers to add.
  223. A guard is unusable if any of the following hold:
  224. - it is not marked as a Guard by the networkstatuses,
  225. - it is not marked Valid (and the user hasn't set AllowInvalid entry)
  226. - it is not marked Running
  227. - Tor couldn't reach it the last time it tried to connect
  228. A guard is unusable for a particular circuit if any of the rules for path
  229. selection in 2.2 are not met. In particular, if the circuit is "fast"
  230. and the guard is not Fast, or if the circuit is "stable" and the guard is
  231. not Stable, or if the guard has already been chosen as the exit node in
  232. that circuit, Tor can't use it as a guard node for that circuit.
  233. If the guard is excluded because of its status in the networkstatuses for
  234. over 30 days, Tor removes it from the list entirely, preserving order.
  235. If Tor fails to connect to an otherwise usable guard, it retries
  236. periodically: every hour for six hours, every 4 hours for 3 days, every
  237. 18 hours for a week, and every 36 hours thereafter. Additionally, Tor
  238. retries unreachable guards the first time it adds a new guard to the list,
  239. since it is possible that the old guards were only marked as unreachable
  240. because the network was unreachable or down.
  241. Tor does not add a guard persistently to the list until the first time we
  242. have connected to it successfully.
  243. 6. Testing circuits
  244. XXXX
  245. X. Old notes
  246. X.1. Do we actually do this?
  247. How to deal with network down.
  248. - While all helpers are down/unreachable and there are no established
  249. or on-the-way testing circuits, launch a testing circuit. (Do this
  250. periodically in the same way we try to establish normal circuits
  251. when things are working normally.)
  252. (Testing circuits are a special type of circuit, that streams won't
  253. attach to by accident.)
  254. - When a testing circuit succeeds, mark all helpers up and hold
  255. the testing circuit open.
  256. - If a connection to a helper succeeds, close all testing circuits.
  257. Else mark that helper down and try another.
  258. - If the last helper is marked down and we already have a testing
  259. circuit established, then add the first hop of that testing circuit
  260. to the end of our helper node list, close that testing circuit,
  261. and go back to square one. (Actually, rather than closing the
  262. testing circuit, can we get away with converting it to a normal
  263. circuit and beginning to use it immediately?)
  264. [Do we actually do any of the above? If so, let's spec it. If not, let's
  265. remove it. -NM]
  266. X.2. A thing we could do to deal with reachability.
  267. And as a bonus, it leads to an answer to Nick's attack ("If I pick
  268. my helper nodes all on 18.0.0.0:*, then I move, you'll know where I
  269. bootstrapped") -- the answer is to pick your original three helper nodes
  270. without regard for reachability. Then the above algorithm will add some
  271. more that are reachable for you, and if you move somewhere, it's more
  272. likely (though not certain) that some of the originals will become useful.
  273. Is that smart or just complex?
  274. X.3. Some stuff that worries me about entry guards. 2006 Jun, Nickm.
  275. It is unlikely for two users to have the same set of entry guards.
  276. Observing a user is sufficient to learn its entry guards. So, as we move
  277. around, entry guards make us linkable. If we want to change guards when
  278. our location (IP? subnet?) changes, we have two bad options. We could
  279. - Drop the old guards. But if we go back to our old location,
  280. we'll not use our old guards. For a laptop that sometimes gets used
  281. from work and sometimes from home, this is pretty fatal.
  282. - Remember the old guards as associated with the old location, and use
  283. them again if we ever go back to the old location. This would be
  284. nasty, since it would force us to record where we've been.
  285. [Do we do any of this now? If not, this should move into 099-misc or
  286. 098-todo. -NM]