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