HACKING 24 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534
  1. Guide to Hacking Tor
  2. (As of 8 October 2003, this was all accurate. If you're reading this in
  3. the distant future, stuff may have changed.)
  4. 0. Intro and required reading
  5. Onion Routing is still very much in development stages. This document
  6. aims to get you started in the right direction if you want to understand
  7. the code, add features, fix bugs, etc.
  8. Read the README file first, so you can get familiar with the basics of
  9. installing and running an onion router.
  10. Then, skim some of the introductory materials in tor-design.pdf,
  11. tor-spec.txt, and the Tor FAQ to learn more about how the Tor protocol
  12. is supposed to work. This document will assume you know about Cells,
  13. Circuits, Streams, Connections, Onion Routers, and Onion Proxies.
  14. 1. Code organization
  15. 1.1. The modules
  16. The code is divided into two directories: ./src/common and ./src/or.
  17. The "common" directory contains general purpose utility functions not
  18. specific to onion routing. The "or" directory implements all
  19. onion-routing and onion-proxy specific functionality.
  20. Files in ./src/common:
  21. aes.[ch] -- Implements the AES cipher (with 128-bit keys and blocks),
  22. and a counter-mode stream cipher on top of AES. This code is
  23. taken from the main Rijndael distribution. (We include this
  24. because many people are running older versions of OpenSSL without
  25. AES support.)
  26. crypto.[ch] -- Wrapper functions to present a consistent interface to
  27. public-key and symmetric cryptography operations from OpenSSL.
  28. fakepoll.[ch] -- Used on systems that don't have a poll() system call;
  29. reimplements() poll using the select() system call.
  30. log.[ch] -- Tor's logging subsystem.
  31. test.h -- Macros used by unit tests.
  32. torint.h -- Provides missing [u]int*_t types for environments that
  33. don't have stdint.h.
  34. tortls.[ch] -- Wrapper functions to present a consistent interface to
  35. TLS, SSL, and X.509 functions from OpenSSL.
  36. util.[ch] -- Miscellaneous portability and convenience functions.
  37. Files in ./src/or:
  38. [General-purpose modules]
  39. or.h -- Common header file: include everything, define everything.
  40. buffers.c -- Implements a generic buffer interface. Buffers are
  41. fairly opaque string holders that can read to or flush from:
  42. memory, file descriptors, or TLS connections.
  43. Also implements parsing functions to read HTTP and SOCKS commands
  44. from buffers.
  45. tree.h -- A splay tree implementation by Niels Provos. Used by
  46. dns.c for dns caching at exits, and by connection_edge.c for dns
  47. caching at clients.
  48. config.c -- Code to parse and validate the configuration file.
  49. [Background processing modules]
  50. cpuworker.c -- Implements a farm of 'CPU worker' processes to perform
  51. CPU-intensive tasks in the background, so as not interrupt the
  52. onion router. (OR only)
  53. dns.c -- Implements a farm of 'DNS worker' processes to perform DNS
  54. lookups for onion routers and cache the results. [This needs to
  55. be done in the background because of the lack of a good,
  56. ubiquitous asynchronous DNS implementation.] (OR only)
  57. [Directory-related functionality.]
  58. directory.c -- Code to send and fetch directories and router
  59. descriptors via HTTP. Directories use dirserv.c to generate the
  60. results; clients use routers.c to parse them.
  61. dirserv.c -- Code to manage directory contents and generate
  62. directories. [Directory server only]
  63. routers.c -- Code to parse directories and router descriptors; and to
  64. generate a router descriptor corresponding to this OR's
  65. capabilities. Also presents some high-level interfaces for
  66. managing an OR or OP's view of the directory.
  67. [Circuit-related modules.]
  68. circuit.c -- Code to create circuits, manage circuits, and route
  69. relay cells along circuits.
  70. onion.c -- Code to generate and respond to "onion skins".
  71. [Core protocol implementation.]
  72. connection.c -- Code used in common by all connection types. See
  73. 1.2. below for more general information about connections.
  74. connection_edge.c -- Code used only by edge connections.
  75. command.c -- Code to handle specific cell types.
  76. connection_or.c -- Code to implement cell-speaking connections.
  77. [Toplevel modules.]
  78. main.c -- Toplevel module. Initializes keys, handles signals,
  79. multiplexes between connections, implements main loop, and drives
  80. scheduled events.
  81. tor_main.c -- Stub module containing a main() function. Allows unit
  82. test binary to link against main.c
  83. [Unit tests]
  84. test.c -- Contains unit tests for many pieces of the lower level Tor
  85. modules.
  86. 1.2. All about connections
  87. All sockets in Tor are handled as different types of nonblocking
  88. 'connections'. (What the Tor spec calls a "Connection", the code refers
  89. to as a "Cell-speaking" or "OR" connection.)
  90. Connections are implemented by the connection_t struct, defined in or.h.
  91. Not every kind of connection uses all the fields in connection_t; see
  92. the comments in or.h and the assertions in assert_connection_ok() for
  93. more information.
  94. Every connection has a type and a state. Connections never change their
  95. type, but can go through many state changes in their lifetime.
  96. The connection types break down as follows:
  97. [Cell-speaking connections]
  98. CONN_TYPE_OR -- A bidirectional TLS connection transmitting a
  99. sequence of cells. May be from an OR to an OR, or from an OP to
  100. an OR.
  101. [Edge connections]
  102. CONN_TYPE_EXIT -- A TCP connection from an onion router to a
  103. Stream's destination. [OR only]
  104. CONN_TYPE_AP -- A SOCKS proxy connection from the end user
  105. application to the onion proxy. [OP only]
  106. [Listeners]
  107. CONN_TYPE_OR_LISTENER [OR only]
  108. CONN_TYPE_AP_LISTENER [OP only]
  109. CONN_TYPE_DIR_LISTENER [Directory server only]
  110. -- Bound network sockets, waiting for incoming connections.
  111. [Internal]
  112. CONN_TYPE_DNSWORKER -- Connection from the main process to a DNS
  113. worker process. [OR only]
  114. CONN_TYPE_CPUWORKER -- Connection from the main process to a CPU
  115. worker process. [OR only]
  116. Connection states are documented in or.h.
  117. Every connection has two associated input and output buffers.
  118. Listeners don't use them. For non-listener connections, incoming
  119. data is appended to conn->inbuf, and outgoing data is taken from the
  120. front of conn->outbuf. Connections differ primarily in the functions
  121. called to fill and drain these buffers.
  122. 1.3. All about circuits.
  123. A circuit_t structure fills two roles. First, a circuit_t links two
  124. connections together: either an edge connection and an OR connection,
  125. or two OR connections. (When joined to an OR connection, a circuit_t
  126. affects only cells sent to a particular circID on that connection. When
  127. joined to an edge connection, a circuit_t affects all data.)
  128. Second, a circuit_t holds the cipher keys and state for sending data
  129. along a given circuit. At the OP, it has a sequence of ciphers, each
  130. of which is shared with a single OR along the circuit. Separate
  131. ciphers are used for data going "forward" (away from the OP) and
  132. "backward" (towards the OP). At the OR, a circuit has only two stream
  133. ciphers: one for data going forward, and one for data going backward.
  134. 1.4. Asynchronous IO and the main loop.
  135. Tor uses the poll(2) system call (or it wraps select(2) to act like
  136. poll, if poll is not available) to handle nonblocking (asynchronous)
  137. IO. If you're not familiar with nonblocking IO, check out the links
  138. at the end of this document.
  139. All asynchronous logic is handled in main.c. The functions
  140. 'connection_add', 'connection_set_poll_socket', and 'connection_remove'
  141. manage an array of connection_t*, and keep in synch with the array of
  142. struct pollfd required by poll(2). (This array of connection_t* is
  143. accessible via get_connection_array, but users should generally call
  144. one of the 'connection_get_by_*' functions in connection.c to look up
  145. individual connections.)
  146. To trap read and write events, connections call the functions
  147. 'connection_{is|stop|start}_{reading|writing}'. If you want
  148. to completely reset the events you're watching for, use
  149. 'connection_watch_events'.
  150. Every time poll() finishes, main.c calls conn_read and conn_write on
  151. every connection. These functions dispatch events that have something
  152. to read to connection_handle_read, and events that have something to
  153. write to connection_handle_write, respectively.
  154. When connections need to be closed, they can respond in two ways. Most
  155. simply, they can make connection_handle_* return an error (-1),
  156. which will make conn_{read|write} close them. But if it's not
  157. convenient to return -1 (for example, processing one connection causes
  158. you to realize that a second one should close), then you can also
  159. mark a connection to close by setting conn->marked_for_close. Marked
  160. connections will be closed at the end of the current iteration of
  161. the main loop.
  162. The main loop handles several other operations: First, it checks
  163. whether any signals have been received that require a response (HUP,
  164. KILL, USR1, CHLD). Second, it calls prepare_for_poll to handle recurring
  165. tasks and compute the necessary poll timeout. These recurring tasks
  166. include periodically fetching the directory, timing out unused
  167. circuits, incrementing flow control windows and re-enabling connections
  168. that were blocking for more bandwidth, and maintaining statistics.
  169. A word about TLS: Using TLS on OR connections complicates matters in
  170. two ways.
  171. First, a TLS stream has its own read buffer independent of the
  172. connection's read buffer. (TLS needs to read an entire frame from
  173. the network before it can decrypt any data. Thus, trying to read 1
  174. byte from TLS can require that several KB be read from the network
  175. and decrypted. The extra data is stored in TLS's decrypt buffer.)
  176. Because the data hasn't been read by tor (it's still inside the TLS),
  177. this means that sometimes a connection "has stuff to read" even when
  178. poll() didn't return POLLIN. The tor_tls_get_pending_bytes function is
  179. used in main.c to detect TLS objects with non-empty internal buffers.
  180. Second, the TLS stream's events do not correspond directly to network
  181. events: sometimes, before a TLS stream can read, the network must be
  182. ready to write -- or vice versa.
  183. 1.5. How data flows (An illustration.)
  184. Suppose an OR receives 256 bytes along an OR connection. These 256
  185. bytes turn out to be a data relay cell, which gets decrypted and
  186. delivered to an edge connection. Here we give a possible call sequence
  187. for the delivery of this data.
  188. (This may be outdated quickly.)
  189. do_main_loop -- Calls poll(2), receives a POLLIN event on a struct
  190. pollfd, then calls:
  191. conn_read -- Looks up the corresponding connection_t, and calls:
  192. connection_handle_read -- Calls:
  193. connection_read_to_buf -- Notices that it has an OR connection so:
  194. read_to_buf_tls -- Pulls data from the TLS stream onto conn->inbuf.
  195. connection_process_inbuf -- Notices that it has an OR connection so:
  196. connection_or_process_inbuf -- Checks whether conn is open, and calls:
  197. connection_process_cell_from_inbuf -- Notices it has enough data for
  198. a cell, then calls:
  199. connection_fetch_from_buf -- Pulls the cell from the buffer.
  200. cell_unpack -- Decodes the raw cell into a cell_t
  201. command_process_cell -- Notices it is a relay cell, so calls:
  202. command_process_relay_cell -- Looks up the circuit for the cell,
  203. makes sure the circuit is live, then passes the cell to:
  204. circuit_deliver_relay_cell -- Passes the cell to each of:
  205. relay_crypt -- Strips a layer of encryption from the cell and
  206. notices that the cell is for local delivery.
  207. connection_edge_process_relay_cell -- extracts the cell's
  208. relay command, and makes sure the edge connection is
  209. open. Since it has a DATA cell and an open connection,
  210. calls:
  211. circuit_consider_sending_sendme -- check if the total number
  212. of cells received by all streams on this circuit is
  213. enough that we should send back an acknowledgement
  214. (requesting that more cells be sent to any stream).
  215. connection_write_to_buf -- To place the data on the outgoing
  216. buffer of the correct edge connection, by calling:
  217. connection_start_writing -- To tell the main poll loop about
  218. the pending data.
  219. write_to_buf -- To actually place the outgoing data on the
  220. edge connection.
  221. connection_consider_sending_sendme -- if the outbuf waiting
  222. to flush to the exit connection is not too full, check
  223. if the total number of cells received on this stream
  224. is enough that we should send back an acknowledgement
  225. (requesting that more cells be sent to this stream).
  226. In a subsequent iteration, main notices that the edge connection is
  227. ready for writing:
  228. do_main_loop -- Calls poll(2), receives a POLLOUT event on a struct
  229. pollfd, then calls:
  230. conn_write -- Looks up the corresponding connection_t, and calls:
  231. connection_handle_write -- This isn't a TLS connection, so calls:
  232. flush_buf -- Delivers data from the edge connection's outbuf to the
  233. network.
  234. connection_wants_to_flush -- Reports that all data has been flushed.
  235. connection_finished_flushing -- Notices the connection is an exit,
  236. and calls:
  237. connection_edge_finished_flushing -- The connection is open, so it
  238. calls:
  239. connection_stop_writing -- Tells the main poll loop that this
  240. connection has no more data to write.
  241. connection_consider_sending_sendme -- now that the outbuf
  242. is empty, check again if the total number of cells
  243. received on this stream is enough that we should send
  244. back an acknowledgement (requesting that more cells be
  245. sent to this stream).
  246. 1.6. Routers, descriptors, and directories
  247. All Tor processes need to keep track of a list of onion routers, for
  248. several reasons:
  249. - OPs need to establish connections and circuits to ORs.
  250. - ORs need to establish connections to other ORs.
  251. - OPs and ORs need to fetch directories from a directory server.
  252. - ORs need to upload their descriptors to directory servers.
  253. - Directory servers need to know which ORs are allowed onto the
  254. network, what the descriptors are for those ORs, and which of
  255. those ORs are currently live.
  256. Thus, every Tor process keeps track of a list of all the ORs it knows
  257. in a static variable 'directory' in the routers.c module. This
  258. variable contains a routerinfo_t object for each known OR. On startup,
  259. the directory is initialized to a list of known directory servers (via
  260. router_get_list_from_file()). Later, the directory is updated via
  261. router_get_dir_from_string(). (OPs and ORs retrieve fresh directories
  262. from directory servers; directory servers generate their own.)
  263. Every OR must periodically regenerate a router descriptor for itself.
  264. The descriptor and the corresponding routerinfo_t are stored in the
  265. 'desc_routerinfo' and 'descriptor' static variables in routers.c.
  266. Additionally, a directory server keeps track of a list of the
  267. router descriptors it knows in a separate list in dirserv.c. It
  268. uses this list, checking which OR connections are open, to build
  269. directories.
  270. 1.7. Data model
  271. [XXX]
  272. 1.8. Flow control
  273. [XXX]
  274. 2. Coding conventions
  275. 2.1. Details
  276. Use tor_malloc, tor_strdup, and tor_gettimeofday instead of their
  277. generic equivalents. (They always succeed or exit.)
  278. Use INLINE instead of 'inline', so that we work properly on windows.
  279. 2.2. Calling and naming conventions
  280. Whenever possible, functions should return -1 on error and and 0 on
  281. success.
  282. For multi-word identifiers, use lowercase words combined with
  283. underscores. (e.g., "multi_word_identifier"). Use ALL_CAPS for macros and
  284. constants.
  285. Typenames should end with "_t".
  286. Function names should be prefixed with a module name or object name. (In
  287. general, code to manipulate an object should be a module with the same
  288. name as the object, so it's hard to tell which convention is used.)
  289. Functions that do things should have imperative-verb names
  290. (e.g. buffer_clear, buffer_resize); functions that return booleans should
  291. have predicate names (e.g. buffer_is_empty, buffer_needs_resizing).
  292. 2.3. What To Optimize
  293. Don't optimize anything if it's not in the critical path. Right now,
  294. the critical path seems to be AES, logging, and the network itself.
  295. Feel free to do your own profiling to determine otherwise.
  296. 2.4. Log conventions
  297. Log convention: use only these four log severities.
  298. ERR is if something fatal just happened.
  299. WARN if something bad happened, but we're still running. The
  300. bad thing is either a bug in the code, an attack or buggy
  301. protocol/implementation of the remote peer, etc. The operator should
  302. examine the bad thing and try to correct it.
  303. NOTICE if it's something the operator will want to know about.
  304. (No error or warning messages should be expected during normal OR or OP
  305. operation. I expect most people to run on -l notice eventually. If a
  306. library function is currently called such that failure always means
  307. ERR, then the library function should log WARN and let the caller
  308. log ERR.)
  309. INFO means something happened (maybe bad, maybe ok), but there's nothing
  310. you need to (or can) do about it.
  311. DEBUG is for everything louder than INFO.
  312. [XXX Proposed convention: every messages of severity INFO or higher should
  313. either (A) be intelligible to end-users who don't know the Tor source; or
  314. (B) somehow inform the end-users that they aren't expected to understand
  315. the message (perhaps with a string like "internal error"). Option (A) is
  316. to be preferred to option (B). -NM]
  317. 3. References
  318. About Tor
  319. See http://freehaven.net/tor/
  320. http://freehaven.net/tor/cvs/doc/tor-spec.txt
  321. http://freehaven.net/tor/cvs/doc/tor-design.tex
  322. http://freehaven.net/tor/cvs/doc/FAQ
  323. About anonymity
  324. See http://freehaven.net/anonbib/
  325. About nonblocking IO
  326. [XXX insert references]
  327. # ======================================================================
  328. # Old HACKING document; merge into the above, move into tor-design.tex,
  329. # or delete.
  330. # ======================================================================
  331. The pieces.
  332. Routers. Onion routers, as far as the 'tor' program is concerned,
  333. are a bunch of data items that are loaded into the router_array when
  334. the program starts. Periodically it downloads a new set of routers
  335. from a directory server, and updates the router_array. When a new OR
  336. connection is started (see below), the relevant information is copied
  337. from the router struct to the connection struct.
  338. Connections. A connection is a long-standing tcp socket between
  339. nodes. A connection is named based on what it's connected to -- an "OR
  340. connection" has an onion router on the other end, an "OP connection" has
  341. an onion proxy on the other end, an "exit connection" has a website or
  342. other server on the other end, and an "AP connection" has an application
  343. proxy (and thus a user) on the other end.
  344. Circuits. A circuit is a path over the onion routing
  345. network. Applications can connect to one end of the circuit, and can
  346. create exit connections at the other end of the circuit. AP and exit
  347. connections have only one circuit associated with them (and thus these
  348. connection types are closed when the circuit is closed), whereas OP and
  349. OR connections multiplex many circuits at once, and stay standing even
  350. when there are no circuits running over them.
  351. Streams. Streams are specific conversations between an AP and an exit.
  352. Streams are multiplexed over circuits.
  353. Cells. Some connections, specifically OR and OP connections, speak
  354. "cells". This means that data over that connection is bundled into 256
  355. byte packets (8 bytes of header and 248 bytes of payload). Each cell has
  356. a type, or "command", which indicates what it's for.
  357. Robustness features.
  358. [XXX no longer up to date]
  359. Bandwidth throttling. Each cell-speaking connection has a maximum
  360. bandwidth it can use, as specified in the routers.or file. Bandwidth
  361. throttling can occur on both the sender side and the receiving side. If
  362. the LinkPadding option is on, the sending side sends cells at regularly
  363. spaced intervals (e.g., a connection with a bandwidth of 25600B/s would
  364. queue a cell every 10ms). The receiving side protects against misbehaving
  365. servers that send cells more frequently, by using a simple token bucket:
  366. Each connection has a token bucket with a specified capacity. Tokens are
  367. added to the bucket each second (when the bucket is full, new tokens
  368. are discarded.) Each token represents permission to receive one byte
  369. from the network --- to receive a byte, the connection must remove a
  370. token from the bucket. Thus if the bucket is empty, that connection must
  371. wait until more tokens arrive. The number of tokens we add enforces a
  372. longterm average rate of incoming bytes, yet we still permit short-term
  373. bursts above the allowed bandwidth. Currently bucket sizes are set to
  374. ten seconds worth of traffic.
  375. The bandwidth throttling uses TCP to push back when we stop reading.
  376. We extend it with token buckets to allow more flexibility for traffic
  377. bursts.
  378. Data congestion control. Even with the above bandwidth throttling,
  379. we still need to worry about congestion, either accidental or intentional.
  380. If a lot of people make circuits into same node, and they all come out
  381. through the same connection, then that connection may become saturated
  382. (be unable to send out data cells as quickly as it wants to). An adversary
  383. can make a 'put' request through the onion routing network to a webserver
  384. he owns, and then refuse to read any of the bytes at the webserver end
  385. of the circuit. These bottlenecks can propagate back through the entire
  386. network, mucking up everything.
  387. (See the tor-spec.txt document for details of how congestion control
  388. works.)
  389. In practice, all the nodes in the circuit maintain a receive window
  390. close to maximum except the exit node, which stays around 0, periodically
  391. receiving a sendme and reading more data cells from the webserver.
  392. In this way we can use pretty much all of the available bandwidth for
  393. data, but gracefully back off when faced with multiple circuits (a new
  394. sendme arrives only after some cells have traversed the entire network),
  395. stalled network connections, or attacks.
  396. We don't need to reimplement full tcp windows, with sequence numbers,
  397. the ability to drop cells when we're full etc, because the tcp streams
  398. already guarantee in-order delivery of each cell. Rather than trying
  399. to build some sort of tcp-on-tcp scheme, we implement this minimal data
  400. congestion control; so far it's enough.
  401. Router twins. In many cases when we ask for a router with a given
  402. address and port, we really mean a router who knows a given key. Router
  403. twins are two or more routers that share the same private key. We thus
  404. give routers extra flexibility in choosing the next hop in the circuit: if
  405. some of the twins are down or slow, it can choose the more available ones.
  406. Currently the code tries for the primary router first, and if it's down,
  407. chooses the first available twin.