diff options
Diffstat (limited to 'attic/text_formats/path-spec.txt')
| -rw-r--r-- | attic/text_formats/path-spec.txt | 1051 |
1 files changed, 1051 insertions, 0 deletions
diff --git a/attic/text_formats/path-spec.txt b/attic/text_formats/path-spec.txt new file mode 100644 index 0000000..33d50e5 --- /dev/null +++ b/attic/text_formats/path-spec.txt @@ -0,0 +1,1051 @@ + + Tor Path Specification + + Roger Dingledine + Nick Mathewson + +Note: This is an attempt to specify Tor as currently implemented. Future +versions of Tor will implement improved algorithms. + +This document tries to cover how Tor chooses to build circuits and assign +streams to circuits. Other implementations MAY take other approaches, but +implementors should be aware of the anonymity and load-balancing implications +of their choices. + + THIS SPEC ISN'T DONE YET. + + The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL + NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and + "OPTIONAL" in this document are to be interpreted as described in + RFC 2119. + +Tables of Contents + + 1. General operation + 1.1. Terminology + 1.2. A relay's bandwidth + 2. Building circuits + 2.1. When we build + 2.1.0. We don't build circuits until we have enough directory info + 2.1.1. Clients build circuits preemptively + 2.1.2. Clients build circuits on demand + 2.1.3. Relays build circuits for testing reachability and bandwidth + 2.1.4. Hidden-service circuits + 2.1.5. Rate limiting of failed circuits + 2.1.6. When to tear down circuits + 2.2. Path selection and constraints + 2.2.1. Choosing an exit + 2.2.2. User configuration + 2.3. Cannibalizing circuits + 2.4. Learning when to give up ("timeout") on circuit construction + 2.4.1 Distribution choice and parameter estimation + 2.4.2. How much data to record + 2.4.3. How to record timeouts + 2.4.4. Detecting Changing Network Conditions + 2.4.5. Consensus parameters governing behavior + 2.4.6. Consensus parameters governing behavior + 2.5. Handling failure + 3. Attaching streams to circuits + 4. Hidden-service related circuits + 5. Guard nodes + 5.1. How consensus bandwidth weights factor into entry guard selection + 6. Server descriptor purposes + 7. Detecting route manipulation by Guard nodes (Path Bias) + 7.1. Measuring path construction success rates + 7.2. Measuring path usage success rates + 7.3. Scaling success counts + 7.4. Parametrization + 7.5. Known barriers to enforcement + X. Old notes + X.1. Do we actually do this? + X.2. A thing we could do to deal with reachability. + X.3. Some stuff that worries me about entry guards. 2006 Jun, Nickm. + +1. General operation + + Tor begins building circuits as soon as it has enough directory + information to do so (see section 5 of dir-spec.txt). Some circuits are + built preemptively because we expect to need them later (for user + traffic), and some are built because of immediate need (for user traffic + that no current circuit can handle, for testing the network or our + reachability, and so on). + + [Newer versions of Tor (0.2.6.2-alpha and later): + If the consensus contains Exits (the typical case), Tor will build both + exit and internal circuits. When bootstrap completes, Tor will be ready + to handle an application requesting an exit circuit to services like the + World Wide Web. + + If the consensus does not contain Exits, Tor will only build internal + circuits. In this case, earlier statuses will have included "internal" + as indicated above. When bootstrap completes, Tor will be ready to handle + an application requesting an internal circuit to hidden services at + ".onion" addresses. + + If a future consensus contains Exits, exit circuits may become available.] + + When a client application creates a new stream (by opening a SOCKS + connection or launching a resolve request), we attach it to an appropriate + open circuit if one exists, or wait if an appropriate circuit is + in-progress. We launch a new circuit only + if no current circuit can handle the request. We rotate circuits over + time to avoid some profiling attacks. + + To build a circuit, we choose all the nodes we want to use, and then + construct the circuit. Sometimes, when we want a circuit that ends at a + given hop, and we have an appropriate unused circuit, we "cannibalize" the + existing circuit and extend it to the new terminus. + + These processes are described in more detail below. + + This document describes Tor's automatic path selection logic only; path + selection can be overridden by a controller (with the EXTENDCIRCUIT and + ATTACHSTREAM commands). Paths constructed through these means may + violate some constraints given below. + +1.1. Terminology + + A "path" is an ordered sequence of nodes, not yet built as a circuit. + + A "clean" circuit is one that has not yet been used for any traffic. + + A "fast" or "stable" or "valid" node is one that has the 'Fast' or + 'Stable' or 'Valid' flag + set respectively, based on our current directory information. A "fast" + or "stable" circuit is one consisting only of "fast" or "stable" nodes. + + In an "exit" circuit, the final node is chosen based on waiting stream + requests if any, and in any case it avoids nodes with exit policy of + "reject *:*". An "internal" circuit, on the other hand, is one where + the final node is chosen just like a middle node (ignoring its exit + policy). + + A "request" is a client-side stream or DNS resolve that needs to be + served by a circuit. + + A "pending" circuit is one that we have started to build, but which has + not yet completed. + + A circuit or path "supports" a request if it is okay to use the + circuit/path to fulfill the request, according to the rules given below. + A circuit or path "might support" a request if some aspect of the request + is unknown (usually its target IP), but we believe the path probably + supports the request according to the rules given below. + +1.2. A relay's bandwidth + + Old versions of Tor did not report bandwidths in network status + documents, so clients had to learn them from the routers' advertised + relay descriptors. + + For versions of Tor prior to 0.2.1.17-rc, everywhere below where we + refer to a relay's "bandwidth", we mean its clipped advertised + bandwidth, computed by taking the smaller of the 'rate' and + 'observed' arguments to the "bandwidth" element in the relay's + descriptor. If a router's advertised bandwidth is greater than + MAX_BELIEVABLE_BANDWIDTH (currently 10 MB/s), we clipped to that + value. + + For more recent versions of Tor, we take the bandwidth value declared + in the consensus, and fall back to the clipped advertised bandwidth + only if the consensus does not have bandwidths listed. + +2. Building circuits + +2.1. When we build + +2.1.0. We don't build circuits until we have enough directory info + + There's a class of possible attacks where our directory servers + only give us information about the relays that they would like us + to use. To prevent this attack, we don't build multi-hop + circuits for real traffic (like those in 2.1.1, 2.1.2, 2.1.4 + below) until we have enough directory information to be + reasonably confident this attack isn't being done to us. + + Here, "enough" directory information is defined as: + + * Having a consensus that's been valid at some point in the + last REASONABLY_LIVE_TIME interval (24 hours). + + * Having enough descriptors that we could build at least some + fraction F of all bandwidth-weighted paths, without taking + ExitNodes/EntryNodes/etc into account. + + (F is set by the PathsNeededToBuildCircuits option, + defaulting to the 'min_paths_for_circs_pct' consensus + parameter, with a final default value of 60%.) + + * Having enough descriptors that we could build at least some + fraction F of all bandwidth-weighted paths, _while_ taking + ExitNodes/EntryNodes/etc into account. + + (F is as above.) + + * Having a descriptor for every one of the first + NUM_USABLE_PRIMARY_GUARDS guards among our primary guards. (see + guard-spec.txt) + + We define the "fraction of bandwidth-weighted paths" as the product of + these three fractions. + + * The fraction of descriptors that we have for nodes with the Guard + flag, weighted by their bandwidth for the guard position. + * The fraction of descriptors that we have for all nodes, + weighted by their bandwidth for the middle position. + * The fraction of descriptors that we have for nodes with the Exit + flag, weighted by their bandwidth for the exit position. + + If the consensus has zero weighted bandwidth for a given kind of + relay (Guard, Middle, or Exit), Tor instead uses the fraction of relays + for which it has the descriptor (not weighted by bandwidth at all). + + If the consensus lists zero exit-flagged relays, Tor instead uses the + fraction of middle relays. + + +2.1.1. Clients build circuits preemptively + + When running as a client, Tor tries to maintain at least a certain + number of clean circuits, so that new streams can be handled + quickly. To increase the likelihood of success, Tor tries to + predict what circuits will be useful by choosing from among nodes + that support the ports we have used in the recent past (by default + one hour). Specifically, on startup Tor tries to maintain one clean + fast exit circuit that allows connections to port 80, and at least + two fast clean stable internal circuits in case we get a resolve + request or hidden service request (at least three if we _run_ a + hidden service). + + After that, Tor will adapt the circuits that it preemptively builds + based on the requests it sees from the user: it tries to have two fast + clean exit circuits available for every port seen within the past hour + (each circuit can be adequate for many predicted ports -- it doesn't + need two separate circuits for each port), and it tries to have the + above internal circuits available if we've seen resolves or hidden + service activity within the past hour. If there are 12 or more clean + circuits open, it doesn't open more even if it has more predictions. + + Only stable circuits can "cover" a port that is listed in the + LongLivedPorts config option. Similarly, hidden service requests + to ports listed in LongLivedPorts make us create stable internal + circuits. + + Note that if there are no requests from the user for an hour, Tor + will predict no use and build no preemptive circuits. + + The Tor client SHOULD NOT store its list of predicted requests to a + persistent medium. + +2.1.2. Clients build circuits on demand + + Additionally, when a client request exists that no circuit (built or + pending) might support, we create a new circuit to support the request. + For exit connections, we pick an exit node that will handle the + most pending requests (choosing arbitrarily among ties), launch a + circuit to end there, and repeat until every unattached request + might be supported by a pending or built circuit. For internal + circuits, we pick an arbitrary acceptable path, repeating as needed. + + Clients consider a circuit to become "dirty" as soon as a stream is + attached to it, or some other request is performed over the circuit. + If a circuit has been "dirty" for at least MaxCircuitDirtiness seconds, + new circuits may not be attached to it. + + In some cases we can reuse an already established circuit if it's + clean; see Section 2.3 (cannibalizing circuits) for details. + +2.1.3. Relays build circuits for testing reachability and bandwidth + + Tor relays test reachability of their ORPort once they have + successfully built a circuit (on startup and whenever their IP address + changes). They build an ordinary fast internal circuit with themselves + as the last hop. As soon as any testing circuit succeeds, the Tor + relay decides it's reachable and is willing to publish a descriptor. + + We launch multiple testing circuits (one at a time), until we + have NUM_PARALLEL_TESTING_CIRC (4) such circuits open. Then we + do a "bandwidth test" by sending a certain number of relay drop + cells down each circuit: BandwidthRate * 10 / CELL_NETWORK_SIZE + total cells divided across the four circuits, but never more than + CIRCWINDOW_START (1000) cells total. This exercises both outgoing and + incoming bandwidth, and helps to jumpstart the observed bandwidth + (see dir-spec.txt). + + Tor relays also test reachability of their DirPort once they have + established a circuit, but they use an ordinary exit circuit for + this purpose. + +2.1.4. Hidden-service circuits + + See section 4 below. + +2.1.5. Rate limiting of failed circuits + + If we fail to build a circuit N times in a X second period (see Section + 2.3 for how this works), we stop building circuits until the X seconds + have elapsed. + XXXX + +2.1.6. When to tear down circuits + + Clients should tear down circuits (in general) only when those circuits + have no streams on them. Additionally, clients should tear-down + stream-less circuits only under one of the following conditions: + + - The circuit has never had a stream attached, and it was created too + long in the past (based on CircuitsAvailableTimeout or + cbtlearntimeout, depending on timeout estimate status). + + - The circuit is dirty (has had a stream attached), and it has been + dirty for at least MaxCircuitDirtiness. + +2.2. Path selection and constraints + + We choose the path for each new circuit before we build it. We choose the + exit node first, followed by the other nodes in the circuit, front to + back. (In other words, for a 3-hop circuit, we first pick hop 3, + then hop 1, then hop 2.) All paths we generate obey the following + constraints: + + - We do not choose the same router twice for the same path. + - We do not choose any router in the same family as another in the same + path. (Two routers are in the same family if each one lists the other + in the "family" entries of its descriptor.) + - We do not choose more than one router in a given /16 subnet + (unless EnforceDistinctSubnets is 0). + - We don't choose any non-running or non-valid router unless we have + been configured to do so. By default, we are configured to allow + non-valid routers in "middle" and "rendezvous" positions. + - If we're using Guard nodes, the first node must be a Guard (see 5 + below) + - XXXX Choosing the length + + For "fast" circuits, we only choose nodes with the Fast flag. For + non-"fast" circuits, all nodes are eligible. + + For all circuits, we weight node selection according to router bandwidth. + + We also weight the bandwidth of Exit and Guard flagged nodes depending on + the fraction of total bandwidth that they make up and depending upon the + position they are being selected for. + + These weights are published in the consensus, and are computed as described + in Section "Computing Bandwidth Weights" of dir-spec.txt. They are: + + Wgg - Weight for Guard-flagged nodes in the guard position + Wgm - Weight for non-flagged nodes in the guard Position + Wgd - Weight for Guard+Exit-flagged nodes in the guard Position + + Wmg - Weight for Guard-flagged nodes in the middle Position + Wmm - Weight for non-flagged nodes in the middle Position + Wme - Weight for Exit-flagged nodes in the middle Position + Wmd - Weight for Guard+Exit flagged nodes in the middle Position + + Weg - Weight for Guard flagged nodes in the exit Position + Wem - Weight for non-flagged nodes in the exit Position + Wee - Weight for Exit-flagged nodes in the exit Position + Wed - Weight for Guard+Exit-flagged nodes in the exit Position + + Wgb - Weight for BEGIN_DIR-supporting Guard-flagged nodes + Wmb - Weight for BEGIN_DIR-supporting non-flagged nodes + Web - Weight for BEGIN_DIR-supporting Exit-flagged nodes + Wdb - Weight for BEGIN_DIR-supporting Guard+Exit-flagged nodes + + Wbg - Weight for Guard+Exit-flagged nodes for BEGIN_DIR requests + Wbm - Weight for Guard+Exit-flagged nodes for BEGIN_DIR requests + Wbe - Weight for Guard+Exit-flagged nodes for BEGIN_DIR requests + Wbd - Weight for Guard+Exit-flagged nodes for BEGIN_DIR requests + + If any of those weights is malformed or not present in a consensus, + clients proceed with the regular path selection algorithm setting + the weights to the default value of 10000. + + Additionally, we may be building circuits with one or more requests in + mind. Each kind of request puts certain constraints on paths: + + - All service-side introduction circuits and all rendezvous paths + should be Stable. + - All connection requests for connections that we think will need to + stay open a long time require Stable circuits. Currently, Tor decides + this by examining the request's target port, and comparing it to a + list of "long-lived" ports. (Default: 21, 22, 706, 1863, 5050, + 5190, 5222, 5223, 6667, 6697, 8300.) + - DNS resolves require an exit node whose exit policy is not equivalent + to "reject *:*". + - Reverse DNS resolves require a version of Tor with advertised eventdns + support (available in Tor 0.1.2.1-alpha-dev and later). + - All connection requests require an exit node whose exit policy + supports their target address and port (if known), or which "might + support it" (if the address isn't known). See 2.2.1. + - Rules for Fast? XXXXX + +2.2.1. Choosing an exit + + If we know what IP address we want to connect to or resolve, we can + trivially tell whether a given router will support it by simulating + its declared exit policy. + + Because we often connect to addresses of the form hostname:port, we do not + always know the target IP address when we select an exit node. In these + cases, we need to pick an exit node that "might support" connections to a + given address port with an unknown address. An exit node "might support" + such a connection if any clause that accepts any connections to that port + precedes all clauses (if any) that reject all connections to that port. + + Unless requested to do so by the user, we never choose an exit node + flagged as "BadExit" by more than half of the authorities who advertise + themselves as listing bad exits. + +2.2.2. User configuration + + Users can alter the default behavior for path selection with configuration + options. + + - If "ExitNodes" is provided, then every request requires an exit node on + the ExitNodes list. (If a request is supported by no nodes on that list, + and StrictExitNodes is false, then Tor treats that request as if + ExitNodes were not provided.) + + - "EntryNodes" and "StrictEntryNodes" behave analogously. + + - If a user tries to connect to or resolve a hostname of the form + <target>.<servername>.exit, the request is rewritten to a request for + <target>, and the request is only supported by the exit whose nickname + or fingerprint is <servername>. + + - When set, "HSLayer2Nodes" and "HSLayer3Nodes" relax Tor's path + restrictions to allow nodes in the same /16 and node family to reappear + in the path. They also allow the guard node to be chosen as the RP, IP, + and HSDIR, and as the hop before those positions. + +2.3. Cannibalizing circuits + + If we need a circuit and have a clean one already established, in + some cases we can adapt the clean circuit for our new + purpose. Specifically, + + For hidden service interactions, we can "cannibalize" a clean internal + circuit if one is available, so we don't need to build those circuits + from scratch on demand. + + We can also cannibalize clean circuits when the client asks to exit + at a given node -- either via the ".exit" notation or because the + destination is running at the same location as an exit node. + +2.4. Learning when to give up ("timeout") on circuit construction + + Since version 0.2.2.8-alpha, Tor clients attempt to learn when to give + up on circuits based on network conditions. + +2.4.1. Distribution choice + + Based on studies of build times, we found that the distribution of + circuit build times appears to be a Frechet distribution (and a multi-modal + Frechet distribution, if more than one guard or bridge is used). However, + estimators and quantile functions of the Frechet distribution are difficult + to work with and slow to converge. So instead, since we are only interested + in the accuracy of the tail, clients approximate the tail of the multi-modal + distribution with a single Pareto curve. + +2.4.2. How much data to record + + From our observations, the minimum number of circuit build times for a + reasonable fit appears to be on the order of 100. However, to keep a + good fit over the long term, clients store 1000 most recent circuit build + times in a circular array. + + These build times only include the times required to build three-hop + circuits, and the times required to build the first three hops of circuits + with more than three hops. Circuits of fewer than three hops are not + recorded, and hops past the third are not recorded. + + The Tor client should build test circuits at a rate of one every 'cbttestfreq' + (10 seconds) until 'cbtmincircs' (100 circuits) are built, with a maximum of + 'cbtmaxopencircs' (default: 10) circuits open at once. This allows a fresh + Tor to have a CircuitBuildTimeout estimated within 30 minutes after install + or network change (see section 2.4.5 below). + + Timeouts are stored on disk in a histogram of 10ms bin width, the same + width used to calculate the Xm value above. The timeouts recorded in the + histogram must be shuffled after being read from disk, to preserve a + proper expiration of old values after restart. + + Thus, some build time resolution is lost during restart. Implementations may + choose a different persistence mechanism than this histogram, but be aware + that build time binning is still needed for parameter estimation. + +2.4.3. Parameter estimation + + Once 'cbtmincircs' build times are recorded, Tor clients update the + distribution parameters and recompute the timeout every circuit completion + (though see section 2.4.5 for when to pause and reset timeout due to + too many circuits timing out). + + Tor clients calculate the parameters for a Pareto distribution fitting the + data using the maximum likelihood estimator. For derivation, see: + https://en.wikipedia.org/wiki/Pareto_distribution#Estimation_of_parameters + + Because build times are not a true Pareto distribution, we alter how Xm is + computed. In a max likelihood estimator, the mode of the distribution is + used directly as Xm. + + Instead of using the mode of discrete build times directly, Tor clients + compute the Xm parameter using the weighted average of the midpoints + of the 'cbtnummodes' (10) most frequently occurring 10ms histogram bins. + Ties are broken in favor of earlier bins (that is, in favor of bins + corresponding to shorter build times). + + (The use of 10 modes was found to minimize error from the selected + cbtquantile, with 10ms bins for quantiles 60-80, compared to many other + heuristics). + + To avoid ln(1.0+epsilon) precision issues, use log laws to rewrite the + estimator for 'alpha' as the sum of logs followed by subtraction, rather + than multiplication and division: + + alpha = n/(Sum_n{ln(MAX(Xm, x_i))} - n*ln(Xm)) + + In this, n is the total number of build times that have completed, x_i is + the ith recorded build time, and Xm is the modes of x_i as above. + + All times below Xm are counted as having the Xm value via the MAX(), + because in Pareto estimators, Xm is supposed to be the lowest value. + However, since clients use mode averaging to estimate Xm, there can be + values below our Xm. Effectively, the Pareto estimator then treats that + everything smaller than Xm happened at Xm. One can also see that if + clients did not do this, alpha could underflow to become negative, which + results in an exponential curve, not a Pareto probability distribution. + + The timeout itself is calculated by using the Pareto Quantile function (the + inverted CDF) to give us the value on the CDF such that 80% of the mass + of the distribution is below the timeout value (parameter 'cbtquantile'). + + The Pareto Quantile Function (inverse CDF) is: + + F(q) = Xm/((1.0-q)^(1.0/alpha)) + + Thus, clients obtain the circuit build timeout for 3-hop circuits by + computing: + + timeout_ms = F(0.8) # 'cbtquantile' == 0.8 + + With this, we expect that the Tor client will accept the fastest 80% of the + total number of paths on the network. + + Clients obtain the circuit close time to completely abandon circuits as: + + close_ms = F(0.99) # 'cbtclosequantile' == 0.99 + + To avoid waiting an unreasonably long period of time for circuits that + simply have relays that are down, Tor clients cap timeout_ms at the max + build time actually observed so far, and cap close_ms at twice this max, + but at least 60 seconds: + + timeout_ms = MIN(timeout_ms, max_observed_timeout) + close_ms = MAX(MIN(close_ms, 2*max_observed_timeout), 'cbtinitialtimeout') + +2.4.3. Calculating timeouts thresholds for circuits of different lengths + + The timeout_ms and close_ms estimates above are good only for 3-hop + circuits, since only 3-hop circuits are recorded in the list of build + times. + + To calculate the appropriate timeouts and close timeouts for circuits of + other lengths, the client multiples the timeout_ms and close_ms values + by a scaling factor determined by the number of communication hops + needed to build their circuits: + + timeout_ms[hops=n] = timeout_ms * Actions(N) / Actions(3) + + close_ms[hops=n] = close_ms * Actions(N) / Actions(3) + + where Actions(N) = N * (N + 1) / 2. + + To calculate timeouts for operations other than circuit building, + the client should add X to Actions(N) for every round-trip communication + required with the Xth hop. + +2.4.4. How to record timeouts + + Pareto estimators begin to lose their accuracy if the tail is omitted. + Hence, Tor clients actually calculate two timeouts: a usage timeout, and a + close timeout. + + Circuits that pass the usage timeout are marked as measurement circuits, + and are allowed to continue to build until the close timeout corresponding + to the point 'cbtclosequantile' (default 99) on the Pareto curve, or 60 + seconds, whichever is greater. + + The actual completion times for these measurement circuits should be + recorded. + + Implementations should completely abandon a circuit and ignore the circuit + if the total build time exceeds the close threshold. Such closed circuits + should be ignored, as this typically means one of the relays in the path is + offline. + +2.4.5. Detecting Changing Network Conditions + + Tor clients attempt to detect both network connectivity loss and drastic + changes in the timeout characteristics. + + To detect changing network conditions, clients keep a history of + the timeout or non-timeout status of the past 'cbtrecentcount' circuits + (20 circuits) that successfully completed at least one hop. If more than + 90% of these circuits timeout, the client discards all buildtimes history, + resets the timeout to 'cbtinitialtimeout' (60 seconds), and then begins + recomputing the timeout. + + If the timeout was already at least `cbtinitialtimeout`, + the client doubles the timeout. + + The records here (of how many circuits succeeded or failed among the most + recent 'cbrrecentcount') are not stored as persistent state. On reload, + we start with a new, empty state. + +2.4.6. Consensus parameters governing behavior + + Clients that implement circuit build timeout learning should obey the + following consensus parameters that govern behavior, in order to allow + us to handle bugs or other emergent behaviors due to client circuit + construction. If these parameters are not present in the consensus, + the listed default values should be used instead. + + cbtdisabled + Default: 0 + Min: 0 + Max: 1 + Effect: If 1, all CircuitBuildTime learning code should be + disabled and history should be discarded. For use in + emergency situations only. + + cbtnummodes + Default: 10 + Min: 1 + Max: 20 + Effect: This value governs how many modes to use in the weighted + average calculation of Pareto parameter Xm. Selecting Xm as the + average of multiple modes improves accuracy of the Pareto tail + for quantile cutoffs from 60-80% (see cbtquantile). + + cbtrecentcount + Default: 20 + Min: 3 + Max: 1000 + Effect: This is the number of circuit build outcomes (success vs + timeout) to keep track of for the following option. + + cbtmaxtimeouts + Default: 18 + Min: 3 + Max: 10000 + Effect: When this many timeouts happen in the last 'cbtrecentcount' + circuit attempts, the client should discard all of its + history and begin learning a fresh timeout value. + + Note that if this parameter's value is greater than the value + of 'cbtrecentcount', then the history will never be + discarded because of this feature. + + cbtmincircs + Default: 100 + Min: 1 + Max: 10000 + Effect: This is the minimum number of circuits to build before + computing a timeout. + + Note that if this parameter's value is higher than 1000 (the + number of time observations that a client keeps in its + circular buffer), circuit build timeout calculation is + effectively disabled, and the default timeouts are used + indefinitely. + + cbtquantile + Default: 80 + Min: 10 + Max: 99 + Effect: This is the position on the quantile curve to use to set the + timeout value. It is a percent (10-99). + + cbtclosequantile + Default: 99 + Min: Value of cbtquantile parameter + Max: 99 + Effect: This is the position on the quantile curve to use to set the + timeout value to use to actually close circuits. It is a + percent (0-99). + + cbttestfreq + Default: 10 + Min: 1 + Max: 2147483647 (INT32_MAX) + Effect: Describes how often in seconds to build a test circuit to + gather timeout values. Only applies if less than 'cbtmincircs' + have been recorded. + + cbtmintimeout + Default: 10 + Min: 10 + Max: 2147483647 (INT32_MAX) + Effect: This is the minimum allowed timeout value in milliseconds. + + cbtinitialtimeout + Default: 60000 + Min: Value of cbtmintimeout + Max: 2147483647 (INT32_MAX) + Effect: This is the timeout value to use before we have enough data + to compute a timeout, in milliseconds. If we do not have + enough data to compute a timeout estimate (see cbtmincircs), + then we use this interval both for the close timeout and the + abandon timeout. + + cbtlearntimeout + Default: 180 + Min: 10 + Max: 60000 + Effect: This is how long idle circuits will be kept open while cbt is + learning a new timeout value. + + cbtmaxopencircs + Default: 10 + Min: 0 + Max: 14 + Effect: This is the maximum number of circuits that can be open at + at the same time during the circuit build time learning phase. + +2.5. Handling failure + + If an attempt to extend a circuit fails (either because the first create + failed or a subsequent extend failed) then the circuit is torn down and is + no longer pending. (XXXX really?) Requests that might have been + supported by the pending circuit thus become unsupported, and a new + circuit needs to be constructed. + + If a stream "begin" attempt fails with an EXITPOLICY error, we + decide that the exit node's exit policy is not correctly advertised, + so we treat the exit node as if it were a non-exit until we retrieve + a fresh descriptor for it. + + Excessive amounts of either type of failure can indicate an + attack on anonymity. See section 7 for how excessive failure is handled. + +3. Attaching streams to circuits + + When a circuit that might support a request is built, Tor tries to attach + the request's stream to the circuit and sends a BEGIN, BEGIN_DIR, + or RESOLVE relay + cell as appropriate. If the request completes unsuccessfully, Tor + considers the reason given in the CLOSE relay cell. [XXX yes, and?] + + + After a request has remained unattached for SocksTimeout (2 minutes + by default), Tor abandons the attempt and signals an error to the + client as appropriate (e.g., by closing the SOCKS connection). + + XXX Timeouts and when Tor auto-retries. + + * What stream-end-reasons are appropriate for retrying. + + If no reply to BEGIN/RESOLVE, then the stream will timeout and fail. + +4. Hidden-service related circuits + + XXX Tracking expected hidden service use (client-side and hidserv-side) + +5. Guard nodes + + We use Guard nodes (also called "helper nodes" in the research + literature) to prevent certain profiling attacks. For an overview of + our Guard selection algorithm -- which has grown rather complex -- see + guard-spec.txt. + +5.1. How consensus bandwidth weights factor into entry guard selection + + When weighting a list of routers for choosing an entry guard, the following + consensus parameters (from the "bandwidth-weights" line) apply: + + Wgg - Weight for Guard-flagged nodes in the guard position + Wgm - Weight for non-flagged nodes in the guard Position + Wgd - Weight for Guard+Exit-flagged nodes in the guard Position + Wgb - Weight for BEGIN_DIR-supporting Guard-flagged nodes + Wmb - Weight for BEGIN_DIR-supporting non-flagged nodes + Web - Weight for BEGIN_DIR-supporting Exit-flagged nodes + Wdb - Weight for BEGIN_DIR-supporting Guard+Exit-flagged nodes + + Please see "bandwidth-weights" in ยง3.4.1 of dir-spec.txt for more in depth + descriptions of these parameters. + + If a router has been marked as both an entry guard and an exit, then we + prefer to use it more, with our preference for doing so (roughly) linearly + increasing w.r.t. the router's non-guard bandwidth and bandwidth weight + (calculated without taking the guard flag into account). From proposal + #236: + + | + | Let Wpf denote the weight from the 'bandwidth-weights' line a + | client would apply to N for position p if it had the guard + | flag, Wpn the weight if it did not have the guard flag, and B the + | measured bandwidth of N in the consensus. Then instead of choosing + | N for position p proportionally to Wpf*B or Wpn*B, clients should + | choose N proportionally to F*Wpf*B + (1-F)*Wpn*B. + + where F is the weight as calculated using the above parameters. + +6. Server descriptor purposes + + There are currently three "purposes" supported for server descriptors: + general, controller, and bridge. Most descriptors are of type general + -- these are the ones listed in the consensus, and the ones fetched + and used in normal cases. + + Controller-purpose descriptors are those delivered by the controller + and labelled as such: they will be kept around (and expire like + normal descriptors), and they can be used by the controller in its + CIRCUITEXTEND commands. Otherwise they are ignored by Tor when it + chooses paths. + + Bridge-purpose descriptors are for routers that are used as bridges. See + doc/design-paper/blocking.pdf for more design explanation, or proposal + 125 for specific details. Currently bridge descriptors are used in place + of normal entry guards, for Tor clients that have UseBridges enabled. + +7. Detecting route manipulation by Guard nodes (Path Bias) + + The Path Bias defense is designed to defend against a type of route + capture where malicious Guard nodes deliberately fail or choke circuits + that extend to non-colluding Exit nodes to maximize their network + utilization in favor of carrying only compromised traffic. + + In the extreme, the attack allows an adversary that carries c/n + of the network capacity to deanonymize c/n of the network + connections, breaking the O((c/n)^2) property of Tor's original + threat model. It also allows targeted attacks aimed at monitoring + the activity of specific users, bridges, or Guard nodes. + + There are two points where path selection can be manipulated: + during construction, and during usage. Circuit construction + can be manipulated by inducing circuit failures during circuit + extend steps, which causes the Tor client to transparently retry + the circuit construction with a new path. Circuit usage can be + manipulated by abusing the stream retry features of Tor (for + example by withholding stream attempt responses from the client + until the stream timeout has expired), at which point the tor client + will also transparently retry the stream on a new path. + + The defense as deployed therefore makes two independent sets of + measurements of successful path use: one during circuit construction, + and one during circuit usage. + + The intended behavior is for clients to ultimately disable the use + of Guards responsible for excessive circuit failure of either type + (see section 7.4); however known issues with the Tor network currently + restrict the defense to being informational only at this stage (see + section 7.5). + +7.1. Measuring path construction success rates + + Clients maintain two counts for each of their guards: a count of the + number of times a circuit was extended to at least two hops through that + guard, and a count of the number of circuits that successfully complete + through that guard. The ratio of these two numbers is used to determine + a circuit success rate for that Guard. + + Circuit build timeouts are counted as construction failures if the + circuit fails to complete before the 95% "right-censored" timeout + interval, not the 80% timeout condition (see section 2.4). + + If a circuit closes prematurely after construction but before being + requested to close by the client, this is counted as a failure. + +7.2. Measuring path usage success rates + + Clients maintain two usage counts for each of their guards: a count + of the number of usage attempts, and a count of the number of + successful usages. + + A usage attempt means any attempt to attach a stream to a circuit. + + Usage success status is temporarily recorded by state flags on circuits. + Guard usage success counts are not incremented until circuit close. A + circuit is marked as successfully used if we receive a properly + recognized RELAY cell on that circuit that was expected for the current + circuit purpose. + + If subsequent stream attachments fail or time out, the successfully used + state of the circuit is cleared, causing it once again to be regarded + as a usage attempt only. + + Upon close by the client, all circuits that are still marked as usage + attempts are probed using a RELAY_BEGIN cell constructed with a + destination of the form 0.a.b.c:25, where a.b.c is a 24 bit random + nonce. If we get a RELAY_COMMAND_END in response matching our nonce, + the circuit is counted as successfully used. + + If any unrecognized RELAY cells arrive after the probe has been sent, + the circuit is counted as a usage failure. + + If the stream failure reason codes DESTROY, TORPROTOCOL, or INTERNAL + are received in response to any stream attempt, such circuits are not + probed and are declared usage failures. + + Prematurely closed circuits are not probed, and are counted as usage + failures. + +7.3. Scaling success counts + + To provide a moving average of recent Guard activity while + still preserving the ability to verify correctness, we periodically + "scale" the success counts by multiplying them by a scale factor + between 0 and 1.0. + + Scaling is performed when either usage or construction attempt counts + exceed a parametrized value. + + To avoid error due to scaling during circuit construction and use, + currently open circuits are subtracted from the usage counts before + scaling, and added back after scaling. + +7.4. Parametrization + + The following consensus parameters tune various aspects of the + defense. + + pb_mincircs + Default: 150 + Min: 5 + Effect: This is the minimum number of circuits that must complete + at least 2 hops before we begin evaluating construction rates. + + + pb_noticepct + Default: 70 + Min: 0 + Max: 100 + Effect: If the circuit success rate falls below this percentage, + we emit a notice log message. + + pb_warnpct + Default: 50 + Min: 0 + Max: 100 + Effect: If the circuit success rate falls below this percentage, + we emit a warn log message. + + pb_extremepct + Default: 30 + Min: 0 + Max: 100 + Effect: If the circuit success rate falls below this percentage, + we emit a more alarmist warning log message. If + pb_dropguard is set to 1, we also disable the use of the + guard. + + pb_dropguards + Default: 0 + Min: 0 + Max: 1 + Effect: If the circuit success rate falls below pb_extremepct, + when pb_dropguard is set to 1, we disable use of that + guard. + + pb_scalecircs + Default: 300 + Min: 10 + Effect: After this many circuits have completed at least two hops, + Tor performs the scaling described in Section 7.3. + + pb_multfactor and pb_scalefactor + Default: 1/2 + Min: 0.0 + Max: 1.0 + Effect: The double-precision result obtained from + pb_multfactor/pb_scalefactor is multiplied by our current + counts to scale them. + + pb_minuse + Default: 20 + Min: 3 + Effect: This is the minimum number of circuits that we must attempt to + use before we begin evaluating construction rates. + + pb_noticeusepct + Default: 80 + Min: 3 + Effect: If the circuit usage success rate falls below this percentage, + we emit a notice log message. + + pb_extremeusepct + Default: 60 + Min: 3 + Effect: If the circuit usage success rate falls below this percentage, + we emit a warning log message. We also disable the use of the + guard if pb_dropguards is set. + + pb_scaleuse + Default: 100 + Min: 10 + Effect: After we have attempted to use this many circuits, + Tor performs the scaling described in Section 7.3. + +7.5. Known barriers to enforcement + + Due to intermittent CPU overload at relays, the normal rate of + successful circuit completion is highly variable. The Guard-dropping + version of the defense is unlikely to be deployed until the ntor + circuit handshake is enabled, or the nature of CPU overload induced + failure is better understood. + + + +X. Old notes + +X.1. Do we actually do this? + +How to deal with network down. + - While all helpers are down/unreachable and there are no established + or on-the-way testing circuits, launch a testing circuit. (Do this + periodically in the same way we try to establish normal circuits + when things are working normally.) + (Testing circuits are a special type of circuit, that streams won't + attach to by accident.) + - When a testing circuit succeeds, mark all helpers up and hold + the testing circuit open. + - If a connection to a helper succeeds, close all testing circuits. + Else mark that helper down and try another. + - If the last helper is marked down and we already have a testing + circuit established, then add the first hop of that testing circuit + to the end of our helper node list, close that testing circuit, + and go back to square one. (Actually, rather than closing the + testing circuit, can we get away with converting it to a normal + circuit and beginning to use it immediately?) + + [Do we actually do any of the above? If so, let's spec it. If not, let's + remove it. -NM] + +X.2. A thing we could do to deal with reachability. + +And as a bonus, it leads to an answer to Nick's attack ("If I pick +my helper nodes all on 18.0.0.0:*, then I move, you'll know where I +bootstrapped") -- the answer is to pick your original three helper nodes +without regard for reachability. Then the above algorithm will add some +more that are reachable for you, and if you move somewhere, it's more +likely (though not certain) that some of the originals will become useful. +Is that smart or just complex? + +X.3. Some stuff that worries me about entry guards. 2006 Jun, Nickm. + + It is unlikely for two users to have the same set of entry guards. + Observing a user is sufficient to learn its entry guards. So, as we move + around, entry guards make us linkable. If we want to change guards when + our location (IP? subnet?) changes, we have two bad options. We could + + - Drop the old guards. But if we go back to our old location, + we'll not use our old guards. For a laptop that sometimes gets used + from work and sometimes from home, this is pretty fatal. + - Remember the old guards as associated with the old location, and use + them again if we ever go back to the old location. This would be + nasty, since it would force us to record where we've been. + + [Do we do any of this now? If not, this should move into 099-misc or + 098-todo. -NM] |