path-spec.txt 37 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881
  1. Tor Path Specification
  2. Roger Dingledine
  3. Nick Mathewson
  4. Note: This is an attempt to specify Tor as currently implemented. Future
  5. versions of Tor will implement improved algorithms.
  6. This document tries to cover how Tor chooses to build circuits and assign
  7. streams to circuits. Other implementations MAY take other approaches, but
  8. implementors should be aware of the anonymity and load-balancing implications
  9. of their choices.
  10. THIS SPEC ISN'T DONE YET.
  11. The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL
  12. NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and
  13. "OPTIONAL" in this document are to be interpreted as described in
  14. RFC 2119.
  15. 1. General operation
  16. Tor begins building circuits as soon as it has enough directory
  17. information to do so (see section 5 of dir-spec.txt). Some circuits are
  18. built preemptively because we expect to need them later (for user
  19. traffic), and some are built because of immediate need (for user traffic
  20. that no current circuit can handle, for testing the network or our
  21. reachability, and so on).
  22. [Newer versions of Tor (0.2.6.2-alpha and later):
  23. If the consensus contains Exits (the typical case), Tor will build both
  24. exit and internal circuits. When bootstrap completes, Tor will be ready
  25. to handle an application requesting an exit circuit to services like the
  26. World Wide Web.
  27. If the consensus does not contain Exits, Tor will only build internal
  28. circuits. In this case, earlier statuses will have included "internal"
  29. as indicated above. When bootstrap completes, Tor will be ready to handle
  30. an application requesting an internal circuit to hidden services at
  31. ".onion" addresses.
  32. If a future consensus contains Exits, exit circuits may become available.]
  33. When a client application creates a new stream (by opening a SOCKS
  34. connection or launching a resolve request), we attach it to an appropriate
  35. open circuit if one exists, or wait if an appropriate circuit is
  36. in-progress. We launch a new circuit only
  37. if no current circuit can handle the request. We rotate circuits over
  38. time to avoid some profiling attacks.
  39. To build a circuit, we choose all the nodes we want to use, and then
  40. construct the circuit. Sometimes, when we want a circuit that ends at a
  41. given hop, and we have an appropriate unused circuit, we "cannibalize" the
  42. existing circuit and extend it to the new terminus.
  43. These processes are described in more detail below.
  44. This document describes Tor's automatic path selection logic only; path
  45. selection can be overridden by a controller (with the EXTENDCIRCUIT and
  46. ATTACHSTREAM commands). Paths constructed through these means may
  47. violate some constraints given below.
  48. 1.1. Terminology
  49. A "path" is an ordered sequence of nodes, not yet built as a circuit.
  50. A "clean" circuit is one that has not yet been used for any traffic.
  51. A "fast" or "stable" or "valid" node is one that has the 'Fast' or
  52. 'Stable' or 'Valid' flag
  53. set respectively, based on our current directory information. A "fast"
  54. or "stable" circuit is one consisting only of "fast" or "stable" nodes.
  55. In an "exit" circuit, the final node is chosen based on waiting stream
  56. requests if any, and in any case it avoids nodes with exit policy of
  57. "reject *:*". An "internal" circuit, on the other hand, is one where
  58. the final node is chosen just like a middle node (ignoring its exit
  59. policy).
  60. A "request" is a client-side stream or DNS resolve that needs to be
  61. served by a circuit.
  62. A "pending" circuit is one that we have started to build, but which has
  63. not yet completed.
  64. A circuit or path "supports" a request if it is okay to use the
  65. circuit/path to fulfill the request, according to the rules given below.
  66. A circuit or path "might support" a request if some aspect of the request
  67. is unknown (usually its target IP), but we believe the path probably
  68. supports the request according to the rules given below.
  69. 1.1. A relay's bandwidth
  70. Old versions of Tor did not report bandwidths in network status
  71. documents, so clients had to learn them from the routers' advertised
  72. relay descriptors.
  73. For versions of Tor prior to 0.2.1.17-rc, everywhere below where we
  74. refer to a relay's "bandwidth", we mean its clipped advertised
  75. bandwidth, computed by taking the smaller of the 'rate' and
  76. 'observed' arguments to the "bandwidth" element in the relay's
  77. descriptor. If a router's advertised bandwidth is greater than
  78. MAX_BELIEVABLE_BANDWIDTH (currently 10 MB/s), we clipped to that
  79. value.
  80. For more recent versions of Tor, we take the bandwidth value declared
  81. in the consensus, and fall back to the clipped advertised bandwidth
  82. only if the consensus does not have bandwidths listed.
  83. 2. Building circuits
  84. 2.1. When we build
  85. 2.1.0. We don't build circuits until we have enough directory info
  86. There's a class of possible attacks where our directory servers
  87. only give us information about the relays that they would like us
  88. to use. To prevent this attack, we don't build multi-hop
  89. circuits for real traffic (like those in 2.1.1, 2.1.2, 2.1.4
  90. below) until we have enough directory information to be
  91. reasonably confident this attack isn't being done to us.
  92. Here, "enough" directory information is defined as:
  93. * Having a consensus that's been valid at some point in the
  94. last REASONABLY_LIVE_TIME interval (24 hourts).
  95. * Having enough descriptors that we could build at least some
  96. fraction F of all bandwidth-weighted paths, without taking
  97. ExitNodes/EntryNodes/etc into account.
  98. (F is set by the PathsNeededToBuildCircuits option,
  99. defaulting to the 'min_paths_for_circs_pct' consensus
  100. parameter, with a final default value of 60%.)
  101. * Having enough descriptors that we could build at least some
  102. fraction F of all bandwidth-weighted paths, _while_ taking
  103. ExitNodes/EntryNodes/etc into account.
  104. (F is as above.)
  105. * Having a descriptor for every one of the first
  106. NUM_GUARDS_TO_USE guards among our primary guards. (see
  107. guard-spec.txt)
  108. 2.1.1. Clients build circuits preemptively
  109. When running as a client, Tor tries to maintain at least a certain
  110. number of clean circuits, so that new streams can be handled
  111. quickly. To increase the likelihood of success, Tor tries to
  112. predict what circuits will be useful by choosing from among nodes
  113. that support the ports we have used in the recent past (by default
  114. one hour). Specifically, on startup Tor tries to maintain one clean
  115. fast exit circuit that allows connections to port 80, and at least
  116. two fast clean stable internal circuits in case we get a resolve
  117. request or hidden service request (at least three if we _run_ a
  118. hidden service).
  119. After that, Tor will adapt the circuits that it preemptively builds
  120. based on the requests it sees from the user: it tries to have two fast
  121. clean exit circuits available for every port seen within the past hour
  122. (each circuit can be adequate for many predicted ports -- it doesn't
  123. need two separate circuits for each port), and it tries to have the
  124. above internal circuits available if we've seen resolves or hidden
  125. service activity within the past hour. If there are 12 or more clean
  126. circuits open, it doesn't open more even if it has more predictions.
  127. Only stable circuits can "cover" a port that is listed in the
  128. LongLivedPorts config option. Similarly, hidden service requests
  129. to ports listed in LongLivedPorts make us create stable internal
  130. circuits.
  131. Note that if there are no requests from the user for an hour, Tor
  132. will predict no use and build no preemptive circuits.
  133. The Tor client SHOULD NOT store its list of predicted requests to a
  134. persistent medium.
  135. 2.1.2. Clients build circuits on demand
  136. Additionally, when a client request exists that no circuit (built or
  137. pending) might support, we create a new circuit to support the request.
  138. For exit connections, we pick an exit node that will handle the
  139. most pending requests (choosing arbitrarily among ties), launch a
  140. circuit to end there, and repeat until every unattached request
  141. might be supported by a pending or built circuit. For internal
  142. circuits, we pick an arbitrary acceptable path, repeating as needed.
  143. In some cases we can reuse an already established circuit if it's
  144. clean; see Section 2.3 (cannibalizing circuits) for details.
  145. 2.1.3. Relays build circuits for testing reachability and bandwidth
  146. Tor relays test reachability of their ORPort once they have
  147. successfully built a circuit (on startup and whenever their IP address
  148. changes). They build an ordinary fast internal circuit with themselves
  149. as the last hop. As soon as any testing circuit succeeds, the Tor
  150. relay decides it's reachable and is willing to publish a descriptor.
  151. We launch multiple testing circuits (one at a time), until we
  152. have NUM_PARALLEL_TESTING_CIRC (4) such circuits open. Then we
  153. do a "bandwidth test" by sending a certain number of relay drop
  154. cells down each circuit: BandwidthRate * 10 / CELL_NETWORK_SIZE
  155. total cells divided across the four circuits, but never more than
  156. CIRCWINDOW_START (1000) cells total. This exercises both outgoing and
  157. incoming bandwidth, and helps to jumpstart the observed bandwidth
  158. (see dir-spec.txt).
  159. Tor relays also test reachability of their DirPort once they have
  160. established a circuit, but they use an ordinary exit circuit for
  161. this purpose.
  162. 2.1.4. Hidden-service circuits
  163. See section 4 below.
  164. 2.1.5. Rate limiting of failed circuits
  165. If we fail to build a circuit N times in a X second period (see Section
  166. 2.3 for how this works), we stop building circuits until the X seconds
  167. have elapsed.
  168. XXXX
  169. 2.1.6. When to tear down circuits
  170. XXXX
  171. 2.2. Path selection and constraints
  172. We choose the path for each new circuit before we build it. We choose the
  173. exit node first, followed by the other nodes in the circuit. All paths
  174. we generate obey the following constraints:
  175. - We do not choose the same router twice for the same path.
  176. - We do not choose any router in the same family as another in the same
  177. path. (Two routers are in the same family if each one lists the other
  178. in the "family" entries of its descriptor.)
  179. - We do not choose more than one router in a given /16 subnet
  180. (unless EnforceDistinctSubnets is 0).
  181. - We don't choose any non-running or non-valid router unless we have
  182. been configured to do so. By default, we are configured to allow
  183. non-valid routers in "middle" and "rendezvous" positions.
  184. - If we're using Guard nodes, the first node must be a Guard (see 5
  185. below)
  186. - XXXX Choosing the length
  187. For "fast" circuits, we only choose nodes with the Fast flag. For
  188. non-"fast" circuits, all nodes are eligible.
  189. For all circuits, we weight node selection according to router bandwidth.
  190. We also weight the bandwidth of Exit and Guard flagged nodes depending on
  191. the fraction of total bandwidth that they make up and depending upon the
  192. position they are being selected for.
  193. These weights are published in the consensus, and are computed as described
  194. in Section "Computing Bandwidth Weights" of dir-spec.txt. They are:
  195. Wgg - Weight for Guard-flagged nodes in the guard position
  196. Wgm - Weight for non-flagged nodes in the guard Position
  197. Wgd - Weight for Guard+Exit-flagged nodes in the guard Position
  198. Wmg - Weight for Guard-flagged nodes in the middle Position
  199. Wmm - Weight for non-flagged nodes in the middle Position
  200. Wme - Weight for Exit-flagged nodes in the middle Position
  201. Wmd - Weight for Guard+Exit flagged nodes in the middle Position
  202. Weg - Weight for Guard flagged nodes in the exit Position
  203. Wem - Weight for non-flagged nodes in the exit Position
  204. Wee - Weight for Exit-flagged nodes in the exit Position
  205. Wed - Weight for Guard+Exit-flagged nodes in the exit Position
  206. Wgb - Weight for BEGIN_DIR-supporting Guard-flagged nodes
  207. Wmb - Weight for BEGIN_DIR-supporting non-flagged nodes
  208. Web - Weight for BEGIN_DIR-supporting Exit-flagged nodes
  209. Wdb - Weight for BEGIN_DIR-supporting Guard+Exit-flagged nodes
  210. Wbg - Weight for Guard+Exit-flagged nodes for BEGIN_DIR requests
  211. Wbm - Weight for Guard+Exit-flagged nodes for BEGIN_DIR requests
  212. Wbe - Weight for Guard+Exit-flagged nodes for BEGIN_DIR requests
  213. Wbd - Weight for Guard+Exit-flagged nodes for BEGIN_DIR requests
  214. If any of those weights is malformed or not present in a consensus,
  215. clients proceed with the regular path selection algorithm setting
  216. the weights to the default value of 10000.
  217. Additionally, we may be building circuits with one or more requests in
  218. mind. Each kind of request puts certain constraints on paths:
  219. - All service-side introduction circuits and all rendezvous paths
  220. should be Stable.
  221. - All connection requests for connections that we think will need to
  222. stay open a long time require Stable circuits. Currently, Tor decides
  223. this by examining the request's target port, and comparing it to a
  224. list of "long-lived" ports. (Default: 21, 22, 706, 1863, 5050,
  225. 5190, 5222, 5223, 6667, 6697, 8300.)
  226. - DNS resolves require an exit node whose exit policy is not equivalent
  227. to "reject *:*".
  228. - Reverse DNS resolves require a version of Tor with advertised eventdns
  229. support (available in Tor 0.1.2.1-alpha-dev and later).
  230. - All connection requests require an exit node whose exit policy
  231. supports their target address and port (if known), or which "might
  232. support it" (if the address isn't known). See 2.2.1.
  233. - Rules for Fast? XXXXX
  234. 2.2.1. Choosing an exit
  235. If we know what IP address we want to connect to or resolve, we can
  236. trivially tell whether a given router will support it by simulating
  237. its declared exit policy.
  238. Because we often connect to addresses of the form hostname:port, we do not
  239. always know the target IP address when we select an exit node. In these
  240. cases, we need to pick an exit node that "might support" connections to a
  241. given address port with an unknown address. An exit node "might support"
  242. such a connection if any clause that accepts any connections to that port
  243. precedes all clauses (if any) that reject all connections to that port.
  244. Unless requested to do so by the user, we never choose an exit node
  245. flagged as "BadExit" by more than half of the authorities who advertise
  246. themselves as listing bad exits.
  247. 2.2.2. User configuration
  248. Users can alter the default behavior for path selection with configuration
  249. options.
  250. - If "ExitNodes" is provided, then every request requires an exit node on
  251. the ExitNodes list. (If a request is supported by no nodes on that list,
  252. and StrictExitNodes is false, then Tor treats that request as if
  253. ExitNodes were not provided.)
  254. - "EntryNodes" and "StrictEntryNodes" behave analogously.
  255. - If a user tries to connect to or resolve a hostname of the form
  256. <target>.<servername>.exit, the request is rewritten to a request for
  257. <target>, and the request is only supported by the exit whose nickname
  258. or fingerprint is <servername>.
  259. 2.3. Cannibalizing circuits
  260. If we need a circuit and have a clean one already established, in
  261. some cases we can adapt the clean circuit for our new
  262. purpose. Specifically,
  263. For hidden service interactions, we can "cannibalize" a clean internal
  264. circuit if one is available, so we don't need to build those circuits
  265. from scratch on demand.
  266. We can also cannibalize clean circuits when the client asks to exit
  267. at a given node -- either via the ".exit" notation or because the
  268. destination is running at the same location as an exit node.
  269. 2.4. Learning when to give up ("timeout") on circuit construction
  270. Since version 0.2.2.8-alpha, Tor attempts to learn when to give up on
  271. circuits based on network conditions.
  272. 2.4.1 Distribution choice and parameter estimation
  273. Based on studies of build times, we found that the distribution of
  274. circuit build times appears to be a Frechet distribution. However,
  275. estimators and quantile functions of the Frechet distribution are
  276. difficult to work with and slow to converge. So instead, since we
  277. are only interested in the accuracy of the tail, we approximate
  278. the tail of the distribution with a Pareto curve.
  279. We calculate the parameters for a Pareto distribution fitting the data
  280. using the estimators in equation 4 from:
  281. http://portal.acm.org/citation.cfm?id=1647962.1648139
  282. This is:
  283. alpha_m = s/(ln(U(X)/Xm^n))
  284. where s is the total number of completed circuits we have seen, and
  285. U(X) = x_max^u * Prod_s{x_i}
  286. with x_i as our i-th completed circuit time, x_max as the longest
  287. completed circuit build time we have yet observed, u as the
  288. number of unobserved timeouts that have no exact value recorded,
  289. and n as u+s, the total number of circuits that either timeout or
  290. complete.
  291. Using log laws, we compute this as the sum of logs to avoid
  292. overflow and ln(1.0+epsilon) precision issues:
  293. alpha_m = s/(u*ln(x_max) + Sum_s{ln(x_i)} - n*ln(Xm))
  294. This estimator is closely related to the parameters present in:
  295. http://en.wikipedia.org/wiki/Pareto_distribution#Parameter_estimation
  296. except they are adjusted to handle the fact that our samples are
  297. right-censored at the timeout cutoff.
  298. Additionally, because this is not a true Pareto distribution, we alter
  299. how Xm is computed. The Xm parameter is computed as the midpoint of the most
  300. frequently occurring 50ms histogram bin, until the point where 1000
  301. circuits are recorded. After this point, the weighted average of the top
  302. 'cbtnummodes' (default: 3) midpoint modes is used as Xm. All times below
  303. this value are counted as having the midpoint value of this weighted average
  304. bin.
  305. The timeout itself is calculated by using the Pareto Quantile function (the
  306. inverted CDF) to give us the value on the CDF such that 80% of the mass
  307. of the distribution is below the timeout value.
  308. Thus, we expect that the Tor client will accept the fastest 80% of
  309. the total number of paths on the network.
  310. 2.4.2. How much data to record
  311. From our observations, the minimum number of circuit build times for a
  312. reasonable fit appears to be on the order of 100. However, to keep a
  313. good fit over the long term, we store 1000 most recent circuit build times
  314. in a circular array.
  315. The Tor client should build test circuits at a rate of one per
  316. minute up until 100 circuits are built. This allows a fresh Tor to have
  317. a CircuitBuildTimeout estimated within 1.5 hours after install,
  318. upgrade, or network change (see below).
  319. Timeouts are stored on disk in a histogram of 50ms bin width, the same
  320. width used to calculate the Xm value above. This histogram must be shuffled
  321. after being read from disk, to preserve a proper expiration of old values
  322. after restart.
  323. 2.4.3. How to record timeouts
  324. Circuits that pass the timeout threshold should be allowed to continue
  325. building until a time corresponding to the point 'cbtclosequantile'
  326. (default 95) on the Pareto curve, or 60 seconds, whichever is greater.
  327. The actual completion times for these circuits should be recorded.
  328. Implementations should completely abandon a circuit and record a value
  329. as an 'unknown' timeout if the total build time exceeds this threshold.
  330. The reason for this is that right-censored pareto estimators begin to lose
  331. their accuracy if more than approximately 5% of the values are censored.
  332. Since we wish to set the cutoff at 20%, we must allow circuits to continue
  333. building past this cutoff point up to the 95th percentile.
  334. 2.4.4. Detecting Changing Network Conditions
  335. We attempt to detect both network connectivity loss and drastic
  336. changes in the timeout characteristics.
  337. We assume that we've had network connectivity loss if a circuit
  338. times out and we've received no cells or TLS handshakes since that
  339. circuit began. We then temporarily stop counting timeouts until
  340. network activity resumes.
  341. To detect changing network conditions, we keep a history of
  342. the timeout or non-timeout status of the past 20 circuits that
  343. successfully completed at least one hop. If more than 90% of
  344. these circuits timeout, we discard all buildtimes history, reset
  345. the timeout to 60, and then begin recomputing the timeout.
  346. If the timeout was already 60 or higher, we double the timeout.
  347. 2.4.5. Consensus parameters governing behavior
  348. Clients that implement circuit build timeout learning should obey the
  349. following consensus parameters that govern behavior, in order to allow
  350. us to handle bugs or other emergent behaviors due to client circuit
  351. construction. If these parameters are not present in the consensus,
  352. the listed default values should be used instead.
  353. cbtdisabled
  354. Default: 0
  355. Min: 0
  356. Max: 1
  357. Effect: If 1, all CircuitBuildTime learning code should be
  358. disabled and history should be discarded. For use in
  359. emergency situations only.
  360. cbtnummodes
  361. Default: 3
  362. Min: 1
  363. Max: 20
  364. Effect: This value governs how many modes to use in the weighted
  365. average calculation of Pareto parameter Xm. A value of 3 introduces
  366. some bias (2-5% of CDF) under ideal conditions, but allows for better
  367. performance in the event that a client chooses guard nodes of radically
  368. different performance characteristics.
  369. cbtrecentcount
  370. Default: 20
  371. Min: 3
  372. Max: 1000
  373. Effect: This is the number of circuit build times to keep track of
  374. for the following option.
  375. cbtmaxtimeouts
  376. Default: 18
  377. Min: 3
  378. Max: 10000
  379. Effect: When this many timeouts happen in the last 'cbtrecentcount'
  380. circuit attempts, the client should discard all of its
  381. history and begin learning a fresh timeout value.
  382. cbtmincircs
  383. Default: 100
  384. Min: 1
  385. Max: 10000
  386. Effect: This is the minimum number of circuits to build before
  387. computing a timeout.
  388. cbtquantile
  389. Default: 80
  390. Min: 10
  391. Max: 99
  392. Effect: This is the position on the quantile curve to use to set the
  393. timeout value. It is a percent (10-99).
  394. cbtclosequantile
  395. Default: 95
  396. Min: Value of cbtquantile parameter
  397. Max: 99
  398. Effect: This is the position on the quantile curve to use to set the
  399. timeout value to use to actually close circuits. It is a
  400. percent (0-99).
  401. cbttestfreq
  402. Default: 60
  403. Min: 1
  404. Max: 2147483647 (INT32_MAX)
  405. Effect: Describes how often in seconds to build a test circuit to
  406. gather timeout values. Only applies if less than 'cbtmincircs'
  407. have been recorded.
  408. cbtmintimeout
  409. Default: 2000
  410. Min: 500
  411. Max: 2147483647 (INT32_MAX)
  412. Effect: This is the minimum allowed timeout value in milliseconds.
  413. The minimum is to prevent rounding to 0 (we only check once
  414. per second).
  415. cbtinitialtimeout
  416. Default: 60000
  417. Min: Value of cbtmintimeout
  418. Max: 2147483647 (INT32_MAX)
  419. Effect: This is the timeout value to use before computing a timeout,
  420. in milliseconds.
  421. 2.5. Handling failure
  422. If an attempt to extend a circuit fails (either because the first create
  423. failed or a subsequent extend failed) then the circuit is torn down and is
  424. no longer pending. (XXXX really?) Requests that might have been
  425. supported by the pending circuit thus become unsupported, and a new
  426. circuit needs to be constructed.
  427. If a stream "begin" attempt fails with an EXITPOLICY error, we
  428. decide that the exit node's exit policy is not correctly advertised,
  429. so we treat the exit node as if it were a non-exit until we retrieve
  430. a fresh descriptor for it.
  431. Excessive amounts of either type of failure can indicate an
  432. attack on anonymity. See section 7 for how excessive failure is handled.
  433. 3. Attaching streams to circuits
  434. When a circuit that might support a request is built, Tor tries to attach
  435. the request's stream to the circuit and sends a BEGIN, BEGIN_DIR,
  436. or RESOLVE relay
  437. cell as appropriate. If the request completes unsuccessfully, Tor
  438. considers the reason given in the CLOSE relay cell. [XXX yes, and?]
  439. After a request has remained unattached for SocksTimeout (2 minutes
  440. by default), Tor abandons the attempt and signals an error to the
  441. client as appropriate (e.g., by closing the SOCKS connection).
  442. XXX Timeouts and when Tor auto-retries.
  443. * What stream-end-reasons are appropriate for retrying.
  444. If no reply to BEGIN/RESOLVE, then the stream will timeout and fail.
  445. 4. Hidden-service related circuits
  446. XXX Tracking expected hidden service use (client-side and hidserv-side)
  447. 5. Guard nodes
  448. We use Guard nodes (also called "helper nodes" in the research
  449. literature) to prevent certain profiling attacks. For an overview of
  450. our Guard selection algorithm -- which has grown rather complex -- see
  451. guard-spec.txt.
  452. 5.1. How consensus bandwidth weights factor into entry guard selection
  453. When weighting a list of routers for choosing an entry guard, the following
  454. consensus parameters (from the "bandwidth-weights" line) apply:
  455. Wgg - Weight for Guard-flagged nodes in the guard position
  456. Wgm - Weight for non-flagged nodes in the guard Position
  457. Wgd - Weight for Guard+Exit-flagged nodes in the guard Position
  458. Wgb - Weight for BEGIN_DIR-supporting Guard-flagged nodes
  459. Wmb - Weight for BEGIN_DIR-supporting non-flagged nodes
  460. Web - Weight for BEGIN_DIR-supporting Exit-flagged nodes
  461. Wdb - Weight for BEGIN_DIR-supporting Guard+Exit-flagged nodes
  462. Please see "bandwidth-weights" in §3.4.1 of dir-spec.txt for more in depth
  463. descriptions of these parameters.
  464. If a router has been marked as both an entry guard and an exit, then we
  465. prefer to use it more, with our preference for doing so (roughly) linearly
  466. increasing w.r.t. the router's non-guard bandwidth and bandwidth weight
  467. (calculated without taking the guard flag into account). From proposal
  468. #236:
  469. |
  470. | Let Wpf denote the weight from the 'bandwidth-weights' line a
  471. | client would apply to N for position p if it had the guard
  472. | flag, Wpn the weight if it did not have the guard flag, and B the
  473. | measured bandwidth of N in the consensus. Then instead of choosing
  474. | N for position p proportionally to Wpf*B or Wpn*B, clients should
  475. | choose N proportionally to F*Wpf*B + (1-F)*Wpn*B.
  476. where F is the weight as calculated using the above parameters.
  477. 6. Server descriptor purposes
  478. There are currently three "purposes" supported for server descriptors:
  479. general, controller, and bridge. Most descriptors are of type general
  480. -- these are the ones listed in the consensus, and the ones fetched
  481. and used in normal cases.
  482. Controller-purpose descriptors are those delivered by the controller
  483. and labelled as such: they will be kept around (and expire like
  484. normal descriptors), and they can be used by the controller in its
  485. CIRCUITEXTEND commands. Otherwise they are ignored by Tor when it
  486. chooses paths.
  487. Bridge-purpose descriptors are for routers that are used as bridges. See
  488. doc/design-paper/blocking.pdf for more design explanation, or proposal
  489. 125 for specific details. Currently bridge descriptors are used in place
  490. of normal entry guards, for Tor clients that have UseBridges enabled.
  491. 7. Detecting route manipulation by Guard nodes (Path Bias)
  492. The Path Bias defense is designed to defend against a type of route
  493. capture where malicious Guard nodes deliberately fail or choke circuits
  494. that extend to non-colluding Exit nodes to maximize their network
  495. utilization in favor of carrying only compromised traffic.
  496. In the extreme, the attack allows an adversary that carries c/n
  497. of the network capacity to deanonymize c/n of the network
  498. connections, breaking the O((c/n)^2) property of Tor's original
  499. threat model. It also allows targeted attacks aimed at monitoring
  500. the activity of specific users, bridges, or Guard nodes.
  501. There are two points where path selection can be manipulated:
  502. during construction, and during usage. Circuit construction
  503. can be manipulated by inducing circuit failures during circuit
  504. extend steps, which causes the Tor client to transparently retry
  505. the circuit construction with a new path. Circuit usage can be
  506. manipulated by abusing the stream retry features of Tor (for
  507. example by withholding stream attempt responses from the client
  508. until the stream timeout has expired), at which point the tor client
  509. will also transparently retry the stream on a new path.
  510. The defense as deployed therefore makes two independent sets of
  511. measurements of successful path use: one during circuit construction,
  512. and one during circuit usage.
  513. The intended behavior is for clients to ultimately disable the use
  514. of Guards responsible for excessive circuit failure of either type
  515. (see section 7.4); however known issues with the Tor network currently
  516. restrict the defense to being informational only at this stage (see
  517. section 7.5).
  518. 7.1. Measuring path construction success rates
  519. Clients maintain two counts for each of their guards: a count of the
  520. number of times a circuit was extended to at least two hops through that
  521. guard, and a count of the number of circuits that successfully complete
  522. through that guard. The ratio of these two numbers is used to determine
  523. a circuit success rate for that Guard.
  524. Circuit build timeouts are counted as construction failures if the
  525. circuit fails to complete before the 95% "right-censored" timeout
  526. interval, not the 80% timeout condition (see section 2.4).
  527. If a circuit closes prematurely after construction but before being
  528. requested to close by the client, this is counted as a failure.
  529. 7.2. Measuring path usage success rates
  530. Clients maintain two usage counts for each of their guards: a count
  531. of the number of usage attempts, and a count of the number of
  532. successful usages.
  533. A usage attempt means any attempt to attach a stream to a circuit.
  534. Usage success status is temporarily recorded by state flags on circuits.
  535. Guard usage success counts are not incremented until circuit close. A
  536. circuit is marked as successfully used if we receive a properly
  537. recognized RELAY cell on that circuit that was expected for the current
  538. circuit purpose.
  539. If subsequent stream attachments fail or time out, the successfully used
  540. state of the circuit is cleared, causing it once again to be regarded
  541. as a usage attempt only.
  542. Upon close by the client, all circuits that are still marked as usage
  543. attempts are probed using a RELAY_BEGIN cell constructed with a
  544. destination of the form 0.a.b.c:25, where a.b.c is a 24 bit random
  545. nonce. If we get a RELAY_COMMAND_END in response matching our nonce,
  546. the circuit is counted as successfully used.
  547. If any unrecognized RELAY cells arrive after the probe has been sent,
  548. the circuit is counted as a usage failure.
  549. If the stream failure reason codes DESTROY, TORPROTOCOL, or INTERNAL
  550. are received in response to any stream attempt, such circuits are not
  551. probed and are declared usage failures.
  552. Prematurely closed circuits are not probed, and are counted as usage
  553. failures.
  554. 7.3. Scaling success counts
  555. To provide a moving average of recent Guard activity while
  556. still preserving the ability to verify correctness, we periodically
  557. "scale" the success counts by multiplying them by a scale factor
  558. between 0 and 1.0.
  559. Scaling is performed when either usage or construction attempt counts
  560. exceed a parametrized value.
  561. To avoid error due to scaling during circuit construction and use,
  562. currently open circuits are subtracted from the usage counts before
  563. scaling, and added back after scaling.
  564. 7.4. Parametrization
  565. The following consensus parameters tune various aspects of the
  566. defense.
  567. pb_mincircs
  568. Default: 150
  569. Min: 5
  570. Effect: This is the minimum number of circuits that must complete
  571. at least 2 hops before we begin evaluating construction rates.
  572. pb_noticepct
  573. Default: 70
  574. Min: 0
  575. Max: 100
  576. Effect: If the circuit success rate falls below this percentage,
  577. we emit a notice log message.
  578. pb_warnpct
  579. Default: 50
  580. Min: 0
  581. Max: 100
  582. Effect: If the circuit success rate falls below this percentage,
  583. we emit a warn log message.
  584. pb_extremepct
  585. Default: 30
  586. Min: 0
  587. Max: 100
  588. Effect: If the circuit success rate falls below this percentage,
  589. we emit a more alarmist warning log message. If
  590. pb_dropguard is set to 1, we also disable the use of the
  591. guard.
  592. pb_dropguards
  593. Default: 0
  594. Min: 0
  595. Max: 1
  596. Effect: If the circuit success rate falls below pb_extremepct,
  597. when pb_dropguard is set to 1, we disable use of that
  598. guard.
  599. pb_scalecircs
  600. Default: 300
  601. Min: 10
  602. Effect: After this many circuits have completed at least two hops,
  603. Tor performs the scaling described in Section 7.3.
  604. pb_multfactor and pb_scalefactor
  605. Default: 1/2
  606. Min: 0.0
  607. Max: 1.0
  608. Effect: The double-precision result obtained from
  609. pb_multfactor/pb_scalefactor is multiplied by our current
  610. counts to scale them.
  611. pb_minuse
  612. Default: 20
  613. Min: 3
  614. Effect: This is the minimum number of circuits that we must attempt to
  615. use before we begin evaluating construction rates.
  616. pb_noticeusepct
  617. Default: 80
  618. Min: 3
  619. Effect: If the circuit usage success rate falls below this percentage,
  620. we emit a notice log message.
  621. pb_extremeusepct
  622. Default: 60
  623. Min: 3
  624. Effect: If the circuit usage success rate falls below this percentage,
  625. we emit a warning log message. We also disable the use of the
  626. guard if pb_dropguards is set.
  627. pb_scaleuse
  628. Default: 100
  629. Min: 10
  630. Effect: After we have attempted to use this many circuits,
  631. Tor performs the scaling described in Section 7.3.
  632. 7.5. Known barriers to enforcement
  633. Due to intermittent CPU overload at relays, the normal rate of
  634. successful circuit completion is highly variable. The Guard-dropping
  635. version of the defense is unlikely to be deployed until the ntor
  636. circuit handshake is enabled, or the nature of CPU overload induced
  637. failure is better understood.
  638. X. Old notes
  639. X.1. Do we actually do this?
  640. How to deal with network down.
  641. - While all helpers are down/unreachable and there are no established
  642. or on-the-way testing circuits, launch a testing circuit. (Do this
  643. periodically in the same way we try to establish normal circuits
  644. when things are working normally.)
  645. (Testing circuits are a special type of circuit, that streams won't
  646. attach to by accident.)
  647. - When a testing circuit succeeds, mark all helpers up and hold
  648. the testing circuit open.
  649. - If a connection to a helper succeeds, close all testing circuits.
  650. Else mark that helper down and try another.
  651. - If the last helper is marked down and we already have a testing
  652. circuit established, then add the first hop of that testing circuit
  653. to the end of our helper node list, close that testing circuit,
  654. and go back to square one. (Actually, rather than closing the
  655. testing circuit, can we get away with converting it to a normal
  656. circuit and beginning to use it immediately?)
  657. [Do we actually do any of the above? If so, let's spec it. If not, let's
  658. remove it. -NM]
  659. X.2. A thing we could do to deal with reachability.
  660. And as a bonus, it leads to an answer to Nick's attack ("If I pick
  661. my helper nodes all on 18.0.0.0:*, then I move, you'll know where I
  662. bootstrapped") -- the answer is to pick your original three helper nodes
  663. without regard for reachability. Then the above algorithm will add some
  664. more that are reachable for you, and if you move somewhere, it's more
  665. likely (though not certain) that some of the originals will become useful.
  666. Is that smart or just complex?
  667. X.3. Some stuff that worries me about entry guards. 2006 Jun, Nickm.
  668. It is unlikely for two users to have the same set of entry guards.
  669. Observing a user is sufficient to learn its entry guards. So, as we move
  670. around, entry guards make us linkable. If we want to change guards when
  671. our location (IP? subnet?) changes, we have two bad options. We could
  672. - Drop the old guards. But if we go back to our old location,
  673. we'll not use our old guards. For a laptop that sometimes gets used
  674. from work and sometimes from home, this is pretty fatal.
  675. - Remember the old guards as associated with the old location, and use
  676. them again if we ever go back to the old location. This would be
  677. nasty, since it would force us to record where we've been.
  678. [Do we do any of this now? If not, this should move into 099-misc or
  679. 098-todo. -NM]