path-spec.txt 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306
  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. I'm just copying in relevant info so
  12. far. -NM
  13. X. Guard nodes
  14. (From some emails by arma)
  15. Hi folks,
  16. I've gotten the codebase to the point that I'm going to start trying
  17. to make helper nodes work well. With luck they will be on by default in
  18. the final 0.1.1.x release.
  19. For background on helper nodes, read
  20. http://wiki.noreply.org/noreply/TheOnionRouter/TorFAQ#RestrictedEntry
  21. First order of business: the phrase "helper node" sucks. We always have
  22. to define it after we say it to somebody. Nick likes the phrase "contact
  23. node", because they are your point-of-contact into the network. That is
  24. better than phrases like "bridge node". The phrase "fixed entry node"
  25. doesn't seem to work with non-math people, because they wonder what was
  26. broken about it. I'm sort of partial to the phrase "entry node" or maybe
  27. "restricted entry node". In any case, if you have ideas on names, please
  28. mail me off-list and I'll collate them.
  29. Right now the code exists to pick helper nodes, store our choices to
  30. disk, and use them for our entry nodes. But there are three topics
  31. to tackle before I'm comfortable turning them on by default. First,
  32. how to handle churn: since Tor nodes are not always up, and sometimes
  33. disappear forever, we need a plan for replacing missing helpers in a
  34. safe way. Second, we need a way to distinguish "the network is down"
  35. from "all my helpers are down", also in a safe way. Lastly, we need to
  36. examine the situation where a client picks three crummy helper nodes
  37. and is forever doomed to a lousy Tor experience. Here's my plan:
  38. How to handle churn.
  39. - Keep track of whether you have ever actually established a
  40. connection to each helper. Any helper node in your list that you've
  41. never used is ok to drop immediately. Also, we don't save that
  42. one to disk.
  43. - If all our helpers are down, we need more helper nodes: add a new
  44. one to the *end*of our list. Only remove dead ones when they have
  45. been gone for a very long time (months).
  46. - Pick from the first n (by default 3) helper nodes in your list
  47. that are up (according to the network-statuses) and reachable
  48. (according to your local firewall config).
  49. - This means that order matters when writing/reading them to disk.
  50. How to deal with network down.
  51. - While all helpers are down/unreachable and there are no established
  52. or on-the-way testing circuits, launch a testing circuit. (Do this
  53. periodically in the same way we try to establish normal circuits
  54. when things are working normally.)
  55. (Testing circuits are a special type of circuit, that streams won't
  56. attach to by accident.)
  57. - When a testing circuit succeeds, mark all helpers up and hold
  58. the testing circuit open.
  59. - If a connection to a helper succeeds, close all testing circuits.
  60. Else mark that helper down and try another.
  61. - If the last helper is marked down and we already have a testing
  62. circuit established, then add the first hop of that testing circuit
  63. to the end of our helper node list, close that testing circuit,
  64. and go back to square one. (Actually, rather than closing the
  65. testing circuit, can we get away with converting it to a normal
  66. circuit and beginning to use it immediately?)
  67. How to pick non-sucky helpers.
  68. - When we're picking a new helper nodes, don't use ones which aren't
  69. reachable according to our local ReachableAddresses configuration.
  70. (There's an attack here: if I pick my helper nodes in a very
  71. restrictive environment, say "ReachableAddresses 18.0.0.0/255.0.0.0:*",
  72. then somebody watching me use the network from another location will
  73. guess where I first joined the network. But let's ignore it for now.)
  74. - Right now we choose new helpers just like we'd choose any entry
  75. node: they must be "stable" (claim >1day uptime) and "fast" (advertise
  76. >10kB capacity). In 0.1.1.11-alpha, clients let dirservers define
  77. "stable" and "fast" however they like, and they just believe them.
  78. So the next step is to make them a function of the current network:
  79. e.g. line up all the 'up' nodes in order and declare the top
  80. three-quarter to be stable, fast, etc, as long as they meet some
  81. minimum too.
  82. - If that's not sufficient (it won't be), dirservers should introduce
  83. a new status flag: in additional to "stable" and "fast", we should
  84. also describe certain nodes as "entry", meaning they are suitable
  85. to be chosen as a helper. The first difference would be that we'd
  86. demand the top half rather than the top three-quarters. Another
  87. requirement would be to look at "mean time between returning" to
  88. ensure that these nodes spend most of their time available. (Up for
  89. two days straight, once a month, is not good enough.)
  90. - Lastly, we need a function, given our current set of helpers and a
  91. directory of the rest of the network, that decides when our helper
  92. set has become "too crummy" and we need to add more. For example,
  93. this could be based on currently advertised capacity of each of
  94. our helpers, and it would also be based on the user's preferences
  95. of speed vs. security.
  96. ***
  97. Lasse wrote:
  98. > I am a bit concerned with performance if we are to have e.g. two out of
  99. > three helper nodes down or unreachable. How often should Tor check if
  100. > they are back up and running?
  101. Right now Tor believes a threshold of directory servers when deciding
  102. whether each server is up. When Tor observes a server to be down
  103. (connection failed or building the first hop of the circuit failed),
  104. it marks it as down and doesn't try it again, until it gets a new
  105. network-status from somebody, at which point it takes a new concensus
  106. and marks the appropriate servers as up.
  107. According to sec 5.1 of dir-spec.txt, the client will try to fetch a new
  108. network-status at least every 30 minutes, and more often in certain cases.
  109. With the proposed scheme, we'll also mark all our helpers as up shortly
  110. after the last one is marked down.
  111. > When should there be
  112. > added an extra node to the helper node list? This is kind of an
  113. > important threshold?
  114. I agree, this is an important question. I don't have a good answer yet. Is
  115. it terrible, anonymity-wise, to add a new helper every time only one of
  116. your helpers is up? Notice that I say add rather than replace -- so you'd
  117. only use this fourth helper when one of your main three helpers is down,
  118. and if three of your four are down, you'd add a fifth, but only use it
  119. when two of the first four are down, etc.
  120. In fact, this may be smarter than just picking a random node for your
  121. testing circuit, because if your network goes up and down a lot, then
  122. eventually you have a chance of using any entry node in the network for
  123. your testing circuit.
  124. We have a design choice here. Do we only try to use helpers for the
  125. connections that will have streams on them (revealing our communication
  126. partners), or do we also want to restrict the overall set of nodes that
  127. we'll connect to, to discourage people from enumerating all Tor clients?
  128. I'm increasingly of the belief that we want to hide our presence too,
  129. based on the fact that Steven and George and others keep coming up with
  130. attacks that start with "Assuming we know the set of users".
  131. If so, then here's a revised "How to deal with network down" section:
  132. 1) When a helper is marked down or the helper list shrinks, and as
  133. a result the total number of helpers that are either (up and
  134. reachable) or (reachable but never connected to) is <= 1, then pick
  135. a new helper and add it to the end of the list.
  136. [We count nodes that have never been connected to, since otherwise
  137. we might keep on adding new nodes before trying any of them. By
  138. "reachable" I mean "is allowed by ReachableAddresses".]
  139. 2) When you fail to connect to a helper that has never been connected
  140. to, you remove him from the list right then (and the above rule
  141. might kick in).
  142. 3) When you succeed at connecting to a helper that you've never
  143. connected to before, mark all reachable helpers earlier in the list
  144. as up, and close that circuit.
  145. [We close the circuit, since if the other helpers are now up, we
  146. prefer to use them for circuits that will reveal communication
  147. partners.]
  148. This certainly seems simpler. Are there holes that I'm missing?
  149. > If running from a laptop you will meet different firewall settings, so
  150. > how should Helper Nodes settings keep up with moving from an open
  151. > ReachableAddresses to a FascistFirewall setting after the helper nodes
  152. > have been selected?
  153. I added the word "reachable" to three places in the above list, and I
  154. believe that totally solves this question.
  155. And as a bonus, it leads to an answer to Nick's attack ("If I pick
  156. my helper nodes all on 18.0.0.0:*, then I move, you'll know where I
  157. bootstrapped") -- the answer is to pick your original three helper nodes
  158. without regard for reachability. Then the above algorithm will add some
  159. more that are reachable for you, and if you move somewhere, it's more
  160. likely (though not certain) that some of the originals will become useful.
  161. Is that smart or just complex?
  162. > What happens if(when?) performance of the third node is bad?
  163. My above solution solves this a little bit, in that we always try to
  164. have two nodes available. But what if they are both up but bad? I'm not
  165. sure. As my previous mail said, we need some function, given our list
  166. of helpers and the network directory, that will tell us when we're in a
  167. bad situation. I can imagine some simple versions of this function --
  168. for example, when both our working helpers are in the bottom half of
  169. the nodes, ranked by capacity.
  170. But the hard part: what's the remedy when we decide there's something
  171. to fix? Do we add a third, and now we have two crummy ones and a new
  172. one? Or do we drop one or both of the bad ones?
  173. Perhaps we believe the latest claim from the network-status concensus,
  174. and we count a helper the dirservers believe is crummy as "not worth
  175. trying" (equivalent to "not reachable under our current ReachableAddresses
  176. config") -- and then the above algorithm would end up adding good ones,
  177. but we'd go back to the originals if they resume being acceptable? That's
  178. an appealing design. I wonder if it will cause the typical Tor user to
  179. have a helper node list that comprises most of the network, though. I'm
  180. ok with this.
  181. > Another point you might want to keep in mind, is the possibility to
  182. > reuse the code in order to add a second layer helper node (meaning node
  183. > number two) to "protect" the first layer (node number one) helper nodes.
  184. > These nodes should be tied to each of the first layer nodes. E.g. there
  185. > is one helper node list, as described in your mail, for each of the
  186. > first layer nodes, following their create/destroy.
  187. True. Does that require us to add a fourth hop to our path length,
  188. since the first hop is from a limited set, the second hop is from a
  189. limited set, and the third hop might also be constrained because, say,
  190. we're asking for an unusual exit port?
  191. > Another of the things might worth adding to the to do list is
  192. > localization of server (helper) nodes. Making it possible to pick
  193. > countries/regions where you do (not) want your helper nodes located. (As
  194. > in "HelperNodesLocated us,!eu" etc.) I know this requires the use of
  195. > external data and may not be worth it, but it _could_ be integrated at
  196. > the directory servers only -- adding a list of node IP's and e.g. a
  197. > country/region code to the directory and thus reduce the overhead. (?)
  198. > Maybe extending the Family-term?
  199. I think we are heading towards doing path selection based on geography,
  200. but I don't have a good sense yet of how that will actually turn out --
  201. that is, with what mechanism Tor clients will learn the information they
  202. need. But this seems to be something that is orthogonal to the rest of
  203. this discussion, so I look forward to having somebody else solve it for
  204. us, and fitting it in when it's ready. :)
  205. > And I would like to keep an option to pick the first X helper nodes
  206. > myself and then let Tor extend this list if these nodes are down (like
  207. > EntryNodes in current code). Even if this opens up for some new types of
  208. > "relationship" attacks.
  209. Good idea. Here's how I'd like to name these:
  210. The "EntryNodes" config option is a list of seed helper nodes. When we
  211. read EntryNodes, any node listed in entrynodes but not in the current
  212. helper node list gets *pre*pended to the helper node list.
  213. The "NumEntryNodes" config option (currently called NumHelperNodes)
  214. specifies the number of up, reachable, good-enough helper nodes that
  215. will make up the pool of possible choices for first hop, counted from
  216. the front of the helper node list until we have enough.
  217. The "UseEntryNodes" config option (currently called UseHelperNodes)
  218. tells us to turn on all this helper node behavior. If you set EntryNodes,
  219. then this option is implied.
  220. The "StrictEntryNodes" config option, provided for backward compatibility
  221. and for debugging, means a) we replace the helper node list with the
  222. current EntryNodes list, and b) whenever we would do an operation that
  223. alters the helper node list, we don't. (Yes, this means that if all the
  224. helper nodes are down, we lose until we mark them up again. But this is
  225. how it behaves now.)
  226. > I am sure my next point has been asked before, but what about testing
  227. > the current speed of the connections when looking for new helper nodes,
  228. > not only testing the connectivity? I know this might contribute to a lot
  229. > of overhead in the network, but if this only occur e.g. when using
  230. > helper nodes as a Hidden Service it might not have that large an impact,
  231. > but could help availability for the services?
  232. If we're just going to be testing them when we're first picking them,
  233. then it seems we can do the same thing by letting the directory servers
  234. test them. This has the added benefit that all the (behaving) clients
  235. use the same data, so they don't end up partitioned by a node that
  236. (for example) performs selectively for his victims.
  237. Another idea would be to periodically keep track of what speeds you get
  238. through your helpers, and make decisions from this. The reason we haven't
  239. done this yet is because there are a lot of variables -- perhaps the
  240. web site is slow, perhaps some other node in the path is slow, perhaps
  241. your local network is slow briefly, perhaps you got unlucky, etc. I
  242. believe that over time (assuming the user has roughly the same browsing
  243. habits) all of these would average out and you'd get a usable answer,
  244. but I don't have a good sense of how long it would take to converge,
  245. so I don't know whether this would be worthwhile.
  246. > BTW. I feel confortable with all the terms helper/entry/contact nodes,
  247. > but I think you (the developers) should just pick one and stay with it
  248. > to avoid confusion.
  249. I think I'm going to try to co-opt the term 'Entry' node for this
  250. purpose. We're going to have to keep referring to helper nodes for the
  251. research community for a while though, so they realize that Tor does
  252. more than just let users ask for certain entry nodes.