September 2015 - tor-dev - lists.torproject.org

What happens to my hidden service?
by Liste 29 Dec '25

29 Dec '25

Hidden service is unavailable, but tor is running. Tor's log: Dec 12 18:10:27.000 [notice] Your Guard SECxFreeBSD64 ($D7DB8E82604F806766FC3F80213CF719A0481D0B) is failing more circuits than usual. Most likely this means the Tor network is overloaded. Success counts are 199/285. Use counts are 101/101. 253 circuits completed, 0 were unusable, 54 collapsed, and 15 timed out. For reference, your timeout cutoff is 60 seconds. is failing a very large amount of circuits. Most likely this means the Tor network is overloaded, but it could also mean an attack against you or potentially the guard itself. Dec 12 18:15:53.000 [warn] Giving up launching first hop of circuit to rendezvous point [scrubbed] for service xxxxxxxxxxxxxxx. Dec 11 13:08:59.000 [notice] We'd like to launch a circuit to handle a connection, but we already have 32 general-purpose client circuits pending. Waiting until some finish. [268 similar message(s) suppressed in last 600 seconds] Dec 11 13:43:12.000 [warn] onion_skin_client_handshake failed. Dec 11 13:43:12.000 [warn] circuit_finish_handshake failed. Dec 11 13:43:12.000 [warn] connection_edge_process_relay_cell (at origin) failed. Dec 11 00:34:57.000 [warn] Giving up launching first hop of circuit to rendezvous point [scrubbed] for service .... Dec 10 10:09:01.000 [warn] rend_service_introduce(): Bug: Internal error: Got an INTRODUCE2 cell on an intro circ (for service "...") with no corresponding rend_intro_point_t. Dec 10 10:09:03.000 [warn] rend_service_introduce(): Bug: Internal error: Got an INTRODUCE2 cell on an intro circ (for service "...") with no corresponding rend_intro_point_t. Dec 10 10:09:04.000 [warn] rend_service_introduce(): Bug: Internal error: Got an INTRODUCE2 cell on an intro circ (for service "...") with no corresponding rend_intro_point_t. Dec 10 12:42:19.000 [warn] rend_service_introduce(): Bug: Internal error: Got an INTRODUCE2 cell on an intro circ (for service "...") with no corresponding rend_intro_point_t.

3 2

Proposal 247 (Hidden Service Vanguards) Overhaul
by Mike Perry 09 Jun '17

09 Jun '17

I spent some time trying to clean up proposal 247 based on everyone's comments, as well as based on my own thoughts. Please have a look if you commented on the original proposal, and complain if I've not taken your thoughts into account. (Aaron: In particular, I made several tradeoffs in favor of performance and DoS resistance that may be at odds with some of your suggestions, but I think the end result is still OK after looking into the Sybil rates and thinking about the adversary model in more detail. You may disagree). I've attached my updated version of the proposal inline in this mail, but the canonical updated proposal is in my remote at: https://gitweb.torproject.org/user/mikeperry/torspec.git/tree/proposals/247… Here's a summary of the changes (which are also listed in Git): * Try to make a coherent threat model and specify its assumptions * Fold in my comments about using disjoint sets ("buckets") for the third level guard. * Make the parameter discussion subsection its own section, and include tables with far more detail for the Sybil success rates. * Put the rotation period in a separate subsection from the number of guards * Switch to using min(X,X) and max(X,X) for the distribution for the second and third layer guard lifespans, respectively. Add a subsection describing this distribution (3.2.3) * Changed the default parameters based on these tables, and based on my own intuition about Tor's performance properties. * Move the load balancing, torrc, and other performance considerations to their own section (Section 5). * Move "3.2. Distinguishing new HS circuits from normal HS circuits" to section 4.1. * Fold in some of "3.3. Circuit nodes can now be linked to specific hidden services" into 4.1. Some of it I just removed, though, because I did not find it credible. * Added Roger's concerns about guard linkability to Section 4.2. * Added a denial of service subsection to Section 4.3. ================================ Filename: 247-hs-guard-discovery.txt Title: Defending Against Guard Discovery Attacks using Vanguards Author: George Kadianakis Created: 2015-07-10 Status: Draft 0. Motivation A guard discovery attack allow attackers to determine the guard node of a Tor client. The hidden service rendezvous protocol provides an attack vector for a guard discovery attack since anyone can force an HS to construct a 3-hop circuit to a relay (#9001). Following the guard discovery attack with a compromise and/or coercion of the guard node can lead to the deanonymization of a hidden service. 1. Overview This document tries to make the above guard discovery + compromise attack harder to launch. It introduces an optional configuration option which makes the hidden service also pin the second and third hops of its circuits for a longer duration. With this new path selection, we force the adversary to perform a Sybil attack and two compromise attacks before succeeding. This is an improvement over the current state where the Sybil attack is trivial to pull off, and only a single compromise attack is required. With this new path selection, an attacker is forced to do a one or more node compromise attacks before learning the guard node of a hidden service. This increases the uncertainty of the attacker, since compromise attacks are costly and potentially detectable, so an attacker will have to think twice before beginning a chain of node compromise attacks that he might not be able to complete. 1.1. Visuals Here is how a hidden service rendezvous circuit currently looks like: -> middle_1 -> middle_A -> middle_2 -> middle_B -> middle_3 -> middle_C -> middle_4 -> middle_D HS -> guard -> middle_5 -> middle_E -> Rendezvous Point -> middle_6 -> middle_F -> middle_7 -> middle_G -> middle_8 -> middle_H -> ... -> ... -> middle_n -> middle_n this proposal pins the two middles nodes to a much more restricted set, as follows: -> guard_3A_A -> guard_2_A -> guard_3A_B -> guard_3A_C -> Rendezvous Point HS -> guard_1 -> guard_3B_D -> guard_2_B -> guard_3B_E -> guard_3B_F -> Rendezvous Point Note that the third level guards are partitioned into buckets such that they are only used with one specific second-level guard. In this way, we ensure that even if an adversary is able to execute a Sybil attack against the third layer, they only get to learn one of the second-layer Guards, and not all of them. This prevents the adversary from gaining the ability to take their pick of the weakest of the second-level guards for further attack. 2. Design This feature requires the HiddenServiceGuardDiscovery torrc option to be enabled. When a hidden service picks its guard nodes, it also picks two additional sets of middle nodes `second_guard_set` and `third_guard_set` of size NUM_SECOND_GUARDS and NUM_THIRD_GUARDS respectively for each hidden service. These sets are unique to each hidden service created by a single Tor client, and must be kept separate and distinct. When a hidden service needs to establish a circuit to an HSDir, introduction point or a rendezvous point, it uses nodes from `second_guard_set` as the second hop of the circuit and nodes from that second hop's corresponding `third_guard_set` as third hops of the circuit. A hidden service rotates nodes from the 'second_guard_set' at a random time between MIN_SECOND_GUARD_LIFETIME hours and MAX_SECOND_GUARD_LIFETIME hours. A hidden service rotates nodes from the 'third_guard_set' at a random time between MIN_THIRD_GUARD_LIFETIME and MAX_THIRD_GUARD_LIFETIME hours. These extra guard nodes should be picked with the same path selection procedure that is used for regular middle nodes (though see Section 5.1 for performance reasons to restrict this slightly). Each node's rotation time is tracked independently, to avoid disclosing the rotation times of the primary and second-level guards. XXX how should proposal 241 ("Resisting guard-turnover attacks") be applied here? 2.1. Security parameters We set NUM_SECOND_GUARDS to 4 nodes and NUM_THIRD_GUARDS to 16 nodes (ie four sets of four). XXX: 3 and 12 might be another option here, in which case our rotation period for the second guard position can be reduced to 15 days. We set MIN_SECOND_GUARD_LIFETIME to 1 day, and MAX_SECOND_GUARD_LIFETIME to 33 days, for an average rotation rate of ~11 days, using the min(X,X) distribution specified in Section 3.2.2. We set MIN_THIRD_GUARD_LIFETIME to 1 hour, and MAX_THIRD_GUARD_LIFETIME to 18 hours, for an average rotation rate of ~12 hours, using the max(X,X) distribution specified in Section 3.2.2. XXX make all the above consensus parameters? Yes. Very yes, especially if we decide to change the primary guard lifespan. See Section 3 for more analysis on these constants. 3. Rationale and Security Parameter Selection 3.1. Threat model, Assumptions, and Goals Consider an adversary with the following powers: - Can launch a Sybil guard discovery attack against any node of a rendezvous circuit. The slower the rotation period of the node, the longer the attack takes. Similarly, the higher the percentage of the network is compromised, the faster the attack runs. - Can compromise any node on the network, but this compromise takes time and potentially even coercive action, and also carries risk of discovery. We also make the following assumptions about the types of attacks: 1. A Sybil attack is noisy. It will require either large amounts of traffic, multiple test circuits, or both. 2. A Sybil attack against the second or first layer Guards will be more noisy than a Sybil attack against the third layer guard, since the second and first layer Sybil attack requires a timing side channel in order to determine success, where as the Sybil success is almost immediately obvious to third layer guard, since it will now be returned as a rend point for circuits for the hidden service in question. 3. As soon as the adversary is confident they have won the Sybil attack, an even more aggressive circuit building attack will allow them to determine the next node very fast (an hour or less). 4. The adversary is strongly disincentivized from compromising nodes that may prove useless, as node compromise is even more risky for the adversary than a Sybil attack in terms of being noticed. Given this threat model, our security parameters were selected so that the first two layers of guards should be hard to attack using a Sybil guard discovery attack and hence require a node compromise attack. Ideally, we want the node compromise attacks to carry a non-negligible probability of being useless to the adversary by the time they complete. On the other hand, the outermost layer of guards should rotate fast enough to _require_ a Sybil attack. 3.2. Parameter Tuning 3.2.1. Sybil rotation counts for a given number of Guards The probability of Sybil success for Guard discovery can be modeled as the probability of choosing 1 or more malicious middle nodes for a sensitive circuit over some period of time. P(At least 1 bad middle) = 1 - P(All Good Middles) = 1 - P(One Good middle)^(num_middles) = 1 - (1 - c/n)^(num_middles) c/n is the adversary compromise percentage In the case of Vanguards, num_middles is the number of Guards you rotate through in a given time period. This is a function of the number of vanguards in that position (v), as well as the number of rotations (r). P(At least one bad middle) = 1 - (1 - c/n)^(v*r) Here's detailed tables in terms of the number of rotations required for a given Sybil success rate for certain number of guards. 1.0% Network Compromise: Sybil Success One Two Three Four Five Six Eight Nine Ten Twelve Sixteen 10% 11 6 4 3 3 2 2 2 2 1 1 15% 17 9 6 5 4 3 3 2 2 2 2 25% 29 15 10 8 6 5 4 4 3 3 2 50% 69 35 23 18 14 12 9 8 7 6 5 60% 92 46 31 23 19 16 12 11 10 8 6 75% 138 69 46 35 28 23 18 16 14 12 9 85% 189 95 63 48 38 32 24 21 19 16 12 90% 230 115 77 58 46 39 29 26 23 20 15 95% 299 150 100 75 60 50 38 34 30 25 19 99% 459 230 153 115 92 77 58 51 46 39 29 5.0% Network Compromise: Sybil Success One Two Three Four Five Six Eight Nine Ten Twelve Sixteen 10% 3 2 1 1 1 1 1 1 1 1 1 15% 4 2 2 1 1 1 1 1 1 1 1 25% 6 3 2 2 2 1 1 1 1 1 1 50% 14 7 5 4 3 3 2 2 2 2 1 60% 18 9 6 5 4 3 3 2 2 2 2 75% 28 14 10 7 6 5 4 4 3 3 2 85% 37 19 13 10 8 7 5 5 4 4 3 90% 45 23 15 12 9 8 6 5 5 4 3 95% 59 30 20 15 12 10 8 7 6 5 4 99% 90 45 30 23 18 15 12 10 9 8 6 10.0% Network Compromise: Sybil Success One Two Three Four Five Six Eight Nine Ten Twelve Sixteen 10% 2 1 1 1 1 1 1 1 1 1 1 15% 2 1 1 1 1 1 1 1 1 1 1 25% 3 2 1 1 1 1 1 1 1 1 1 50% 7 4 3 2 2 2 1 1 1 1 1 60% 9 5 3 3 2 2 2 1 1 1 1 75% 14 7 5 4 3 3 2 2 2 2 1 85% 19 10 7 5 4 4 3 3 2 2 2 90% 22 11 8 6 5 4 3 3 3 2 2 95% 29 15 10 8 6 5 4 4 3 3 2 99% 44 22 15 11 9 8 6 5 5 4 3 The rotation counts in these tables were generated with: def count_rotations(c, v, success): r = 0 while 1-math.pow((1-c), v*r) < success: r += 1 return r 3.2.2. Rotation Period As specified in Section 3.1, the primary driving force for the third layer selection was to ensure that these nodes rotate fast enough that it is not worth trying to compromise them, because it is unlikely for compromise to succeed and yield useful information before the nodes stop being used. For this reason we chose 1 to 18 hours, with a weighted distribution (Section 3.2.3) causing the expected average to be 12 hours. From the table in Section 3.2.1, it can be seen that this means that the Sybil attack will complete with near-certainty (99%) in 29*12 hours (14.5 days) for the 1% adversary, 3 days for the 5% adversary, and 1.5 days for the 10% adversary. Since rotation of each node happens independently, the distribution of when the adversary expects to win this Sybil attack in order to discover the next node up is uniform. This means that on average, the adversary should expect that half of the rotation period of the next node is already over by the time that they win the Sybil. With this fact, we choose our range and distribution for the second layer rotation to be short enough to cause the adversary to risk compromising nodes that are useless, yet long enough to require a Sybil attack to be noticeable in terms of client activity. For this reason, we choose a minimum second-layer guard lifetime of 1 day, since this gives the adversary a minimum expected value of 12 hours for during which they can compromise a guard before it might be rotated. If the total expected rotation rate is 11 days, then the adversary can expect overall to have 5.5 days remaining after completing their Sybil attack before a second-layer guard rotates away. 3.2.3. Rotation distribution In order to skew the distribution of the third layer guard towards higher values, we use max(X,X) for the distribution, where X is a random variable that takes on values from the uniform distribution. In order to skew the distribution of the second layer guard towards low values (to increase the risk of compromising useless nodes) we skew the distribution towards lower values, using min(X,X). Here's a table of expectation (arithmetic means) for relevant ranges of X (sampled from 0..N). The current choice for second-layer guards is noted with **, and the current choice for third-layer guards is noted with ***. Range Min(X,X) Max(X,X) 10 2.85 6.15 11 3.18 6.82 12 3.51 7.49 13 3.85 8.15 14 4.18 8.82 15 4.51 9.49 16 4.84 10.16 17 5.18 10.82*** 18 5.51 11.49 19 5.84 12.16 20 6.18 12.82 21 6.51 13.49 22 6.84 14.16 23 7.17 14.83 24 7.51 15.49 25 7.84 16.16 26 8.17 16.83 27 8.51 17.49 28 8.84 18.16 29 9.17 18.83 30 9.51 19.49 31 9.84 20.16 32 10.17** 20.83 33 10.51 21.49 34 10.84 22.16 35 11.17 22.83 36 11.50 23.50 37 11.84 24.16 38 12.17 24.83 39 12.50 25.50 4. Security concerns and mitigations 4.1. Mitigating fingerprinting of new HS circuits By pinning the middle nodes of rendezvous circuits, we make it easier for all hops of the circuit to detect that they are part of a special hidden service circuit with varying degrees of certainty. The Guard node is able to recognize a Vanguard client with a high degree of certainty because it will observe a client IP creating the overwhelming majority of its circuits to just a few middle nodes in any given 10-18 day time period. The middle nodes will be able to tell with a variable certainty that depends on both its traffic volume and upon the popularity of the service, because they will see a large number of circuits that tend to pick the same Guard and Exit. The final nodes will be able to tell with a similar level certainty that depends on their capacity and the service popularity, because they will see a lot of rend handshakes that all tend to have the same second hop. The most serious of these is the Guard fingerprinting issue. When proposal xxx-padding-negotiation is implemented, services that enable this feature should use those padding primitives to create fake circuits to random middle nodes that are not their guards, in an attempt to look more like a client. Additionally, if Tor Browser implements "virtual circuits" based on SOCKS username+password isolation in order to enforce the re-use of paths when SOCKS username+passwords are re-used, then the number of middle nodes in use during a typical user's browsing session will be proportional to the number of sites they are viewing at any one time. This is likely to be much lower than one new middle node every ten minutes, and for some users, may be close to the number of Vanguards we're considering. This same reasoning is also an argument for increasing the number of second-level guards beyond just two, as it will spread the hidden service's traffic over a wider set of middle nodes, making it both easier to cover, and behave closer to a client using SOCKS virtual circuit isolation. 4.2. Hidden service linkability Multiple hidden services on the same Tor instance should use separate second and third level guard sets, otherwise an adversary is trivially able to determine that the two hidden services are co-located by inspecting their current chosen rend point nodes. Unfortunately, if the adversary is still able to determine that two or more hidden services are run on the same Tor instance through some other means, then they are able to take advantage of this fact to execute a Sybil attack more effectively, since there will now be an extra set of guard nodes for each hidden service in use. For this reason, if Vanguards are enabled, and more than one hidden service is configured, the user should be advised to ensure that they do not accidentally leak that the two hidden services are from the same Tor instance. 4.3. Denial of service Since it will be fairly trivial for the adversary to enumerate the current set of rend nodes for a hidden service, denial of service becomes a serious risk for Vanguard users. For this reason, it is important to support a large number of third-level guards, to increase the amount of resources required to bring a hidden service offline by DoSing just a few Tor nodes. 5. Performance considerations The switch to a restricted set of nodes will very likely cause significant performance issues, especially for high-traffic hidden services. If any of the nodes they select happen to be temporarily overloaded, performance will suffer dramatically until the next rotation period. 5.1. Load Balancing Since the second and third level "guards" are chosen from the set of all nodes eligible for use in the "middle" hop (as per hidden services today), this proposal should not significantly affect the long-term load on various classes of the Tor network, and should not require any changes to either the node weight equations, or the bandwidth authorities. Unfortunately, transient load is another matter, as mentioned previously. It is very likely that this scheme will increase instances of transient overload at nodes selected by high-traffic hidden services. One option to reduce the impact of this transient overload is to restrict the set of middle nodes that we chose from to some percentage of the fastest middle-capable relays in the network. This may have some impact on load balancing, but since the total volume of hidden service traffic is low, it may be unlikely to matter. 5.2. Circuit build timeout The adaptive circuit build timeout mechanism in Tor is what corrects for instances of transient node overload right now. The timeout will naturally tend to select the current fastest and least-loaded paths even through this set of restricted routes, but it may fail to behave correctly if there are a very small set of nodes in each guard set, as it is based upon assumptions about the current path selection algorithm, and it may need to be tuned specifically for Vanguards, especially if the set of possible routes is small. 5.3. OnionBalance At first glance, it seems that this scheme makes multi-homed hidden services such as OnionBalance[1] even more important for high-traffic hidden services. Unfortunately, if it is equally damaging to the user for any of their multi-homed hidden service locations to be discovered, then OnionBalance is strictly equivalent to simply increasing the number of second-level guard nodes in use, because an active adversary can perform simultaneous Sybil attacks against all of the rend points offered by the multi-homed OnionBalance introduction points. 5.4. Default vs optional behavior We suggest this torrc option to be optional because it changes path selection in a way that may seriously impact hidden service performance, especially for high traffic services that happen to pick slow guard nodes. However, by having this setting be disabled by default, we make hidden services who use it stand out a lot. For this reason, we should in fact enable this feature globally, but only after we verify its viability for high-traffic hidden services, and ensure that it is free of second-order load balancing effects. Even after that point, until Single Onion Services are implemented, there will likely still be classes of very high traffic hidden services for whom some degree of location anonymity is desired, but for which performance is much more important than the benefit of Vanguards, so there should always remain a way to turn this option off. 6. Future directions Here are some more ideas for improvements that should be done sooner or later: - Maybe we should make the size and rotation period of secondary/third guard sets to be configurable by the user. - To make it harder for an adversary, a hidden service MAY extend the path length of its circuits by an additional static hop. This forces the adversary to use another coercion attack to walk the chain up to the hidden service. 7. Acknowledgments Thanks to Aaron Johnson, John Brooks, Mike Perry and everyone else who helped with this idea. 1. https://onionbalance.readthedocs.org/en/latest/design.html#overview -- Mike Perry

7 14

Relay Database: Existing Schemas?
by nusenu 27 Feb '16

27 Feb '16

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA512 Hi, I'm planing to store relay data in a database for analysis. I assume others have done so as well, so before going ahead and designing a db schema I'd like to make sure I didn't miss pre-existing db schemas one could build on. Data to be stored: - - (most) descriptor fields - - everything that onionoo provides in a details record (geoip, asn, rdns, tordnsel, cw, ...) - - historic records I didn't find something matching so far, so I'll go ahead, but if you know of other existing relay db schemas I'd like to hear about it. thanks, nusenu "GSoC2013: Searchable Tor descriptor archive" (Kostas Jakeliunas) https://www.google-melange.com/gsoc/project/details/google/gsoc2013/wfn/ 5866452879933440 https://lists.torproject.org/pipermail/tor-dev/2013-May/004923.html https://lists.torproject.org/pipermail/tor-dev/2013-September/005357.htm l https://github.com/wfn/torsearch (btw, someone knows the license of this?) > This is true: the summary/details documents (just like in Onionoo > proper) deal with the *last* known info about relays. ernie https://gitweb.torproject.org/metrics-db.git/plain/doc/manual.pdf (didn't find db/tordir.sql mentioned in the pdf) "Instructions for setting up relay descriptor database" https://lists.torproject.org/pipermail/tor-dev/2010-March/001783.html "Set up descriptor database for other researchers" https://trac.torproject.org/projects/tor/ticket/1643 -----BEGIN PGP SIGNATURE----- iQIcBAEBCgAGBQJVLrmVAAoJEFv7XvVCELh0+ycP/0VkRWMGAhx7YwWhixtOPB0q ouitosse3SdLCMd1W7cps7nnQhcGv8E1xeUPYeizNQ+RIK9ldvnwgxhVt9ETOI3e oL6bcx3B/NSbTcGfZhIU6XCCX7+39CXz3/+/gXg4c1a5Cd9rYKuwTn7ZApPUNAK2 9yfckCwHaqh67ZDHB1A7nrHX1BJAjwhri5JRGomHSUXPwNZOyMzpgPkB+I92esqc Z4ajQo2D+Vyk42qF7apqp5ApVBLdt5ycUtW1j4s4KvyJH2BjeP4tCXvvYLKv9IvN TGHMJ111NQXbuk6H1OdaDmMZhhW6utPk8YAbNc7RZHqCdH7No40zFVlikLDrV2Xl uLt8FMlck7hGQv/4udA59Dw3PGHfrSiCbvJXb0S2jarnWOH2O+zSSuMs8jQM/x7k 6tIOlwtRDVGw3VuvNbb4MJnLzdHRxq3qy6ueDYuhmhHslxjD1Cbr3eE1RA7Da9aX kNDgjfXtdah52HWUZbIIxHQYzyCg5G3M5yy51GhUlA2Fe1sbPpNcEBeyEDK/jH3Y +7G+tgR+CdMvSFraCiYKHa1drVPJHeqNvZAqPNHKxpKwOwOoJEYrsW4wb/mJ7ybe o8xNYK691hcaMvHqwI47tw4hZfrI0f0+gQKKzENQQk8/8yUZ/0jgMRlW/Cz0yYIa FZEg+OJ/yEs8vKfYerIN =Rfn4 -----END PGP SIGNATURE-----

3 2

Proposal: Load-balancing hidden services by splitting introduction from rendezvous
by Tom van der Woerdt 12 Feb '16

12 Feb '16

Hey all, I'd like your thoughts and comments on this proposal. Tom PS: If you want to deliver them in person, I'm in Berlin. Filename: xxx-intro-rendezvous-controlsocket.txt Title: Load-balancing hidden services by splitting introduction from rendezvous Author: Tom van der Woerdt Created: 2015-09-30 Status: draft 1. Overview and motivation To address scaling concerns with the onion web, we want to be able to spread the load of hidden services across multiple machines. OnionBalance is a great stab at this, and it can currently give us 60x the capacity by publishing 6 separate descriptors, each with 10 introduction points, but more is better. This proposal aims to address hidden service scaling up to a point where we can handle millions of concurrent connections. The basic idea involves splitting the 'introduce' from the 'rendezvous', in the tor implementation, and adding new events and commands to the control specification to allow intercepting introductions and transmitting them to different nodes, which will then take care of the actual rendezvous. External controller code could relay the data to another node or a pool of nodes, all which are run by the hidden service operator, effectively distributing the load of hidden services over multiple processes. By cleverly utilizing the current descriptor methods, we could publish up to sixty unique introduction points, which could translate to many thousands of parallel tor workers. This should allow hidden services to go multi-threaded, with a few small changes. 2. Specification We propose two additions to the control specification, of which one is an event and the other is a new command. We also introduce a new configuration option. 2.1. DisableAutomaticRendezvous configuration option The syntax is: "DisableAutomaticRendezvous" SP [1|0] CRLF This configuration option is defined to be a boolean toggle which, if set, stops the tor implementation from automatically doing a rendezvous when an INTRODUCE2 cell is received. Instead, an event will be sent to the controllers. If no controllers are present, the introduction cell should be dropped, as acting on it instead of dropping it could open a window for a DoS. For security reasons, the configuration should be made available only in the configuration files, and not as an option settable by the controller. 2.2. The "INTRODUCE" event The syntax is: "650" SP "INTRODUCE" SP RendezvousData CRLF RendezvousData = implementation-specific, but must not contain whitespace, must only contain human-readable characters, and should be no longer than 512 bytes The INTRODUCE event should contain sufficient data to allow continuing the rendezvous from another Tor instance. The exact format is left unspecified and left up to the implementation. From this follows that only matching versions can be used safely to coordinate the rendezvous of hidden service connections. 2.3. "PERFORM-RENDEZVOUS" command The syntax is: "PERFORM-RENDEZVOUS" SP RendezvousData CRLF This command allows a controller to perform a rendezvous using data received through an INTRODUCE event. The format of RendezvousData is not specified other than that it must not contain whitespace, and should be no longer than 512 bytes. 3. Compatibility and security The implementation of these methods should, ideally, not change anything in the network, and all control changes are opt-in, so this proposal is fully backwards compatible. Controllers handling this data must be careful to not leak rendezvous data to untrusted parties, as it could be used to intercept and manipulate hidden services traffic. 4. Example Let's take an example where a client (Alice) tries to contact Bob's hidden service. To do this, Bob follows the normal hidden service specification, except he sets up ten servers to do this. One of these publishes the descriptor, the others have this desabled. When the INTRODUCE2 cell arrives at the node which published the descriptor, it does not immediately try to perform the rendezvous, but instead outputs this to the controller. Through an out-of-band process this message is relayed to a controller of another node of Bob's, and this transmits the "PERFORM-RENDEZVOUS" command to that node. This node finally performs the rendezvous, and will continue to serve data to Alice, whose client will now not have to talk to the introduction point anymore. 5. Other considerations We have left the actual format of the rendezvous data in the control protocol unspecified, so that controllers do not need to worry about the various types of hidden service connections, most notably proposal 224. The decision to not implement the actual cell relaying in the tor implementation itself was taken to allow more advanced configurations, and to leave the actual load-balancing algorithm to the implementor of the controller. The developer of the tor implementation should not have to choose between a round-robin algorithm and something that could pull CPU load averages from a centralized monitoring system.

5 9

Re: [tor-dev] . tor-roster's geo diversity badge and self-ref relays
by Sean Saito 15 Nov '15

15 Nov '15

Hi nusenu, >Do you consider in-family diversity so important - even though all of >them are run by a single entity anyway? > How about having a badge for tor network wide diversity? > I'd consider the tor network's overall diversity far more important than > in-family diversity because clients won't use more than one relay of a > given family anyway. Entire-network diversity is obviously more important than within-operator diversity---no doubt about that. We are doing within-operator diversity simply because the it's easier to measure/understand. I agree that measuring a family's relay diversity with respect to the entire Tor network is would be supplementary, maybe even strictly better. I am already logging relevant data, namely the number of relays per country and total CW per country (as you suggested previously). The former stastic could be used for badges like "First relay in country X." >More than 4/5 of the family's CW is located in countries with a cw lower >than 2%* (currently means non-top 7 country) and ASes lower than 1.5%* >(currently means non-top 8 AS)? > >That implies some degree of in-family diversity since a big family would >have to spread across multiple countries/ASes Although there have been some interesting discussions about which ASes to prioritize in putting new relays, an actual concrete numerical measure is thus far an unsolved problem. Virgil and I have talked about using a new tool (http://labs.apnic.net/vizas/) to observe which ASes have more interconnections and award bonus points to new relays on them. When these measures become better established definitely in favor of making badges for them (perhaps even replacing the within-operator diversity badges?). >"No Self-Referencing Relays" >I'm not sure what exactly you mean by that but I assume it is a MyFamily >config where a relay includes his own fingerprint. Why does that hurt? >The unnecessary descriptor space/bw? This is something Virgil wanted because he thought self-connections were ugly. If the penalizing of self-connections is found to be uglier than the self-connections themselves, we're both fine with removing it. Hope this answers your questions. Thanks for the feedback! Best, Sean

7 6

Proposal: Adding x-namespace to relay descriptor for key:value pairs
by Virgil Griffith 09 Nov '15

09 Nov '15

Filename: ExtraRelayDescriptorFields.txt Title: Adding x-namespace to relay descriptor for key:value pairs Author: Virgil Griffith Created: 2015-09-30 Status: Open 1. Motivation We wish to allow developers to build new applications atop relays. Towards this end, we wish to add the ability for users to specify arbitrary new key-value entries under the "X-" namespace to the router descriptor [1]. The canonical applications for this are adding a bitcoin donation address and networking of tor2web nodes. 2. Proposal Allow optional key-value lines in the relay's torrc file. These lines will be mirrored in the relay's descriptor which is then published in the directory consensus. The following would be added to section 2.1.2 of the dir-spec (Extra-info document format): ======================================================== "X-" CustomKey SP CustomValue NL CustomKeyChar = "a"-"z" / "0" - "9" / "-" / "_" CustomKey = 1*32 CustomKeyChar CustomValueChar = atext / specials CustomValue = 1*1024 CustomValueChar Custom fields can appear multiple times, for example... X-bitcoin 19mP9FKrXqL46Si58pHdhGKow88SUPy1V8 X-gravatar https://s.gravatar.com/avatar/d27fce46c9ac41a41bb52455ae75701d X-favoritequote Be excellent to each other. Party on dudes! X-foo bar If the same CustomKey appearing more than once is disallowed. Possible values for CustomValueChar as specified per RFC 2822. The sum size accounting for all such custom fields is truncated to 5 kilobytes. ======================================================== To mitigate the chance of a malformed torrc file, I additionally propose that the relay descriptor be scanned and if it does not match the specification, that it exit with error telling her torrc file is a likely culprit. -V

3 5

Bridge Guards (prop#188) & Bridge ORPort Reachability Tests
by isis 30 Oct '15

30 Oct '15

Hey all, I have a working implementation of proposal #188, [0] which specifies a mechanism by which tor's (rather accidental) loose-source routing feature is utilised by Bridges in order to transparently inject a Bridge Guard into all client circuits. (See #7144. [1]) Currently, I am updating the text in proposal #188 to match my implementation, and I am trying to decide what to do about the two types of Bridge ORPort reachability testing. Here's the text I've written so far to explain the issues: (In the following, "Alice" is an OP, "Bob" is a Bridge, "Guillaume" is Bob's chosen Entry Guard, and "Charlie" is a random Middle node.) > 4.4. Bridge Reachability Testing > > Currently, a Bridge's reachability is tested both by the Bridge > itself (called "self-testing") and by the BridgeAuthority. > > 4.4.1. Bridge Reachability Self-Testing > > Before a Bridge uploads its descriptors to the BridgeAuthority, it > creates a special type of testing circuit which ends at itself: > > Bob -> Guillaume -> Charlie -> Bob > > Thus, going to all this trouble to later use loose-source routing in > order to relay Alice's traffic through Guillaume (rather than > connecting directly to Charlie, as Alice intended) is diminished by > the fact that Charlie can still passively enumerate Bridges by > waiting to be asked to connect to a node which is not > contained within the consensus. > > We could get around this option by disabling self-testing for bridges > entirely, by automatically setting "AssumeReachable 1" for all Bridge > relays… although I am not sure if this is wise. > > 4.4.2. Bridge Reachability Testing by the BridgeAuthority > > After receiving Bob's descriptors, the BridgeAuthority attempts to > connect to Bob's ORPort by making a direct TLS connection to the > Bridge's advertised ORPort. > > Should we change this behaviour? One the one hand, at least this > does not enable any random OR in the entire network to enumerate > Bridges. On the other hand, any adversary who can observe packets > from the BridgeAuthority is capable of enumeration. So, my current questions are: 1. Bridges only do reachability self-testing in order to warn their operators that the Bridge (or firewall or whatever) might be misconfigured, correct? Is there any other reason (or future reason) why self-testing is important/useful? 2. How should the self-testing be changed? 2.a. First, if there aren't any other reasons for self-testing: Is Bridge reachability self-testing actually helpful to Bridge operators in practice? Don't most Bridge operators just try to connect, as a client, to their own Bridge to see if it's working correctly? (This is what I usually do, at least…) If it's not useful to most Bridge operators, can we just disable self-testing for all Bridges? (And, should we disable it only for Bridges who are using Bridge Guards, or all of Bridges regardless?) 2.b. If it is useful to people, then the best way I can think of so far to keep it, but refactor it to be safer, would be to create a circuit like: Bridge → Guard → Middle → OtherMiddle → Guard → Bridge Clearly, that circuit is just a little bit insane… but we can't do: Bridge → Guard → Middle → Guard → Bridge because the Middle would refuse to extend back to the previous node (all ORs follow this rule). Similarly, it would be stupid to do: Bridge → Guard → Middle → OtherMiddle → Bridge because, obviously, that merely shifts the problem and accomplishes nothing. But is there something smarter I could do? 3. Should we change how the BridgeAuthority tests Bridge ORPort reachability? If so, how? 4. If I'm going to refactor all of this, are there other (future) things I should take into account? For example, if self-testing is disabled for Bridges, and, due to #7349, [2] the BridgeAuthority isn't testing reachability either, then how will the BridgeAuthority know if (any of) the Bridge's PTs are reachable? (One solution might be to, in that case, have the BridgeAuthority lie and tell BridgeDB that such Bridges were reachable, letting BridgeDB do the PT reachability testing.) Please help me brainstorm a way out of this mess! [0]: https://gitweb.torproject.org/torspec.git/tree/proposals/188-bridge-guards.… [1]: https://bugs.torproject.org/7144 [2]: https://bugs.torproject.org/7349 Best Regards, -- ♥Ⓐ isis agora lovecruft _________________________________________________________ OpenPGP: 4096R/0A6A58A14B5946ABDE18E207A3ADB67A2CDB8B35 Current Keys: https://blog.patternsinthevoid.net/isis.txt

4 8

Onion Services and NAT Punching
by Tim Wilson-Brown - teor 26 Oct '15

26 Oct '15

Hi All, Do you know a use case which needs Single Onion Services and NAT punching? We’re wondering if there are mobile or desktop applications / services that would use a single onion service for the performance benefits, but still need NAT punching. (And don’t need the anonymity of a hidden service.) Single Onion Services: * can’t do NAT punching, (they need an ORPort on a publicly accessible IP address), * locations are easier to discover, and * have lower latency. Hidden Services: * can do NAT punching, * locations are hard to discover, and * have higher latency. Are there any use cases that: * need NAT punching, * don’t need service location anonymity, and * would benefit from lower latency? Thanks Tim Tim Wilson-Brown (teor) teor2345 at gmail dot com PGP 968F094B teor at blah dot im OTR CAD08081 9755866D 89E2A06F E3558B7F B5A9D14F

6 6

txtorcon 0.14.0
by meejah 26 Oct '15

26 Oct '15

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 I'm happy to announce txtorcon 0.14.0. Changes: * IStreamAttacher handling was missing None and DO_NOT_ATTACH cases if a Deferred was returned. * add .is_built Deferred to txtorcon.Circuit that gets callback()'d when the circuit becomes BUILT * David Stainton ported his "tor:" endpoint parser so now both client and server endpoints are supported. This means **any** Twisted program using endpoints can use Tor as a client. For example, to connect to txtorcon's Web site: ep = clientFromString("tor:timaq4ygg2iegci7.onion:80"). (In the future, I'd like to automatically launch Tor if required, too). * Python3 fixes from Isis Lovecruft (note: needs Twisted 15.4.0+) You can download the release from PyPI or GitHub (or of course "pip install txtorcon"): https://pypi.python.org/pypi/txtorcon/0.14.0 https://github.com/meejah/txtorcon/releases/tag/v0.14.0 Releases are also available from the hidden service: http://timaq4ygg2iegci7.onion/txtorcon-0.14.0.tar.gz http://timaq4ygg2iegci7.onion/txtorcon-0.14.0.tar.gz.asc http://timaq4ygg2iegci7.onion/txtorcon-0.14.0-py2-none-any.whl http://timaq4ygg2iegci7.onion/txtorcon-0.14.0-py2-none-any.whl.asc You can verify the sha256sum of both by running the following 4 lines in a shell wherever you have the files downloaded: cat <<EOF | sha256sum --check d44be978dd9521f22333edea49789fe7e19c4bea9a02d63e6ec826d08fb571d1 dist/txtorcon-0.14.0-py2-none-any.whl a2d0fae65da015840bb392ffc4fd63918168edb6b634941f6b8aa843b338edbf dist/txtorcon-0.14.0.tar.gz EOF thanks, meejah -----BEGIN PGP SIGNATURE----- iQEcBAEBAgAGBQJWB3FqAAoJEMJgKAMSgGmn1fsIAOcqJdIFIO5cIvj7TRv9rxFP aEW/Vb0UGN2/A2skWxajzYJLeZ0geZaOmYGFyscs+fguIzRaGRX4G8+7xRuIzzim GqjPd+my2+h79hDpH/RntwQvNmW9K50UCKOH5TiW5fGnjbO0ZkqoK8ln+aGz7WCC HjRmNTJb7iI/vVs6h66evBHjkgib4lBpZSEnJR6H+c1ZC5hJ0uYt1SFch5IF/UsA QeISGyc2SE5wuwjLuiHDyPoFC/Q5IEhDWABFgs3Z6LB/2yfnUFEjrtEla1Uq454H YJ5mWsgxx/apGDXbACQ3p8N5ISA/WDOWHm2Rg+XgZo758KyMyOQIfSy1RrGBld4= =Wffv -----END PGP SIGNATURE-----

1 1

Proposal: Padding Negotiation
by Mike Perry 15 Oct '15

15 Oct '15

Here's a proposal describing some padding negotiation cell primitives that should be useful to defend against website traffic fingerprinting, hidden service circuit fingerprinting, and probably just about any other traffic analysis attack under the sun. The proposal is in my git remote at: https://gitweb.torproject.org/user/mikeperry/torspec.git/tree/proposals/xxx… ============================== Filename: xxx-padding-negotiation.txt Title: Padding Negotiation Authors: Mike Perry Created: 01 September 2015 Status: Draft 0. Overview This proposal aims to describe mechanisms for requesting various types of padding from relays. These padding primitives are general enough to use to defend against both website traffic fingerprinting as well as hidden service circuit setup fingerprinting. 1. Motivation Tor already supports both link-level padding via (CELL_PADDING cell types), as well as circuit-level padding (via RELAY_COMMAND_DROP relay cells). Unfortunately, there is no way for clients to request padding from relays, or request that relays not send them padding to conserve bandwidth. This proposal aims to create a mechanism for clients to do both of these. It also establishes consensus parameters to limit the amount of padding that relays will send, to prevent custom wingnut clients from requesting too much. 2. Link-level padding Padding is most useful if it can defend against a malicious or compromised guard node. However, link-level padding is still useful to defend against an adversary that can merely observe a Guard node externally, such as for low-resolution netflow-based attacks (see Proposal 251[1]). In that scenario, the primary negotiation mechanism we need is a way for mobile clients to tell their Guards to stop padding, or to pad less often. The following Trunnel payloads should cover the needed parameters: const CELL_PADDING_COMMAND_STOP = 1; const CELL_PADDING_COMMAND_START = 2; /* This command tells the relay to stop sending any periodic CELL_PADDING cells. */ struct cell_padding_stop { u8 command IN [CELL_PADDING_COMMAND_STOP]; }; /* This command tells the relay to alter its min and max netflow timeout range values, and send padding at that rate (resuming if stopped). */ struct cell_padding_start { u8 command IN [CELL_PADDING_COMMAND_START]; /* Min must not be lower than the current consensus parameter nf_ito_low. */ u16 ito_low_ms; /* Max must not be lower than ito_low_ms */ u16 ito_high_ms; }; More complicated forms of link-level padding can still be specified using the primitives in Section 3, by using "leaky pipe" topology to send the RELAY commands to the Guard node instead of to later nodes in the circuit. 3. End-to-end circuit padding For circuit-level padding, we need two types of additional features: the ability to schedule additional incoming cells at one or more fixed points in the future, and the ability to schedule a statistical distribution of arbitrary padding to overlay on top of non-padding traffic (aka "Adaptive Padding"). In both cases, these messages will be sent from clients to middle nodes using the "leaky pipe" property of the 'recognized' field of RELAY cells, allowing padding to originate from middle nodes on a circuit in a way that is not detectable from the Guard node. This same mechanism can also be used to request padding from the Guard node itself, to achieve link-level padding without the additional overhead requirements on middle nodes. 3.1. Fixed-schedule padding message (RELAY_COMMAND_PADDING_SCHEDULE) The fixed schedule padding will be encoded in a RELAY_COMMAND_PADDING_SCHEDULE cell. It specifies a set of up to 80 fixed time points in the future to send cells. XXX: 80 timers is a lot to allow every client to create. We may want to have something that checks this structure to ensure it actually schedules no more than N in practice, until we figure out how to optimize either libevent or timer scheduling/packet delivery. See also Section 4.3. The RELAY_COMMAND_PADDING_SCHEDULE body is specified in Trunnel as follows: struct relay_padding_schedule { /* Number of microseconds before sending cells (cumulative) */ u32 when_send[80]; /* Number of cells to send at time point sum(when_send[0..i]) */ u16 num_cells[80]; /* Adaptivity: If 1, and server-originating cells arrive before the next when_send time, then decrement the next non-zero when_send index, so we don't send a padding cell then, too */ u8 adaptive IN [0,1]; }; To allow both high-resolution time values, and the ability to specify timeout values far in the future, the time values are cumulative. In other words, sending a cell with when_send = [MAX_INT, MAX_INT, MAX_INT, 0...] and num_cells = [0, 0, 100, 0...] would cause the relay to reply with 100 cells in 3*MAX_INT microseconds from the receipt of this cell. 3.2. Adaptive Padding message (RELAY_COMMAND_PADDING_ADAPTIVE) The following message is a generalization of the Adaptive Padding defense specified in "Timing Attacks and Defenses"[2]. The message encodes either one or two state machines, each of which can contain one or two histograms ("Burst" and "Gap") governing their behavior. The "Burst" histogram specifies the delay probabilities for sending a padding packet after the arrival of a non-padding data packet. The "Gap" histogram specifies the delay probabilities for sending another padding packet after a padding packet was just sent from this node. This self-triggering property of the "Gap" histogram allows the construction of multi-packet padding trains using a simple statistical distribution. Both "Gap" and "Burst" histograms each have a special "Infinity" bin, which means "We have decided not to send a packet". Each histogram is combined with state transition information, which allows a client to specify the types of incoming packets that cause the state machine to decide to schedule padding cells (and/or when to cease scheduling them). The client also maintains its own local histogram state machine(s), for reacting to traffic on its end. Note that our generalization of the Adaptive Padding state machine also gives clients full control over the state transition events, even allowing them to specify a single-state Burst-only state machine if desired. See Sections 3.2.1 and 3.2.2 for details. The histograms and the associated state machine packet layout is specified in Trunnel as follows: /* These constants form a bitfield to specify the types of events * that can cause transitions between state machine states. * * Note that SENT and RECV are relative to this endpoint. For * relays, SENT means packets destined towards the client and * RECV means packets destined towards the relay. On the client, * SENT means packets destined towards the relay, where as RECV * means packets destined towards the client. */ const RELAY_PADDING_TRANSITION_EVENT_NONPADDING_RECV = 1; const RELAY_PADDING_TRANSITION_EVENT_NONPADDING_SENT = 2; const RELAY_PADDING_TRANSITION_EVENT_PADDING_SENT = 4; const RELAY_PADDING_TRANSITION_EVENT_PADDING_RECV = 8; /* This payload encodes a histogram delay distribution representing * the probability of sending a single RELAY_DROP cell after a * given delay in response to a non-padding cell. */ struct burst_state { u8 histogram_len IN [2..51]; u16 histogram[histogram_len]; u32 start_usec; u16 max_sec; /* This is a bitfield that specifies which direction and types * of traffic that cause us to abort our scheduled packet and * return to waiting for another event from transition_burst_events. */ u8 transition_start_events; /* This is a bitfield that specifies which direction and types * of traffic that cause us to remain in the burst state: Cancel the * pending padding packet (if any), and schedule another padding * packet from our histogram. */ u8 transition_reschedule_events; /* This is a bitfield that specifies which direction and types * of traffic that cause us to transition to the Gap state. */ u8 transition_gap_events; /* If true, remove tokens from the histogram upon padding and * non-padding activity. */ u8 remove_toks IN [0,1]; }; /* This histogram encodes a delay distribution representing the * probability of sending a single additional padding packet after * sending a padding packet that originated at this hop. */ struct gap_state { u8 histogram_len IN [2..51]; u16 histogram[histogram_len]; u32 start_usec; u16 max_sec; /* This is a bitfield which specifies which direction and types * of traffic should cause us to transition back to the start * state (ie: abort scheduling packets completely). */ u8 transition_start_events; /* This is a bitfield which specifies which direction and types * of traffic should cause us to transition back to the burst * state (and schedule a packet from the burst histogram). */ u8 transition_burst_events; /* This is a bitfield that specifies which direction and types * of traffic that cause us to remain in the gap state: Cancel the * pending padding packet (if any), and schedule another padding * packet from our histogram. */ u8 transition_reschedule_events; /* If true, remove tokens from the histogram upon padding and non-padding activity. */ u8 remove_toks IN [0,1]; }; struct adaptive_padding_machine { /* This is a bitfield which specifies which direction and types * of traffic should cause us to transition to the burst * state (and schedule a packet from the burst histogram). */ u8 transition_burst_events; struct burst_state burst; struct gap_state gap; }; /* This is the full payload of a RELAY_COMMAND_PADDING_ADAPTIVE * cell. */ struct relay_command_padding_adaptive { u8 num_machines IN [1,2]; struct adaptive_padding_machine machines[num_machines]; }; 3.2.1. Histogram state machine operation Each of pair of histograms ("Burst" and "Gap") together form a state machine whose transitions are governed by incoming traffic and/or locally generated padding traffic. Each state machine has a Start state S, a Burst state B, and a Gap state G. The state machine starts idle (state S) until it receives a packet of a type that matches the bitmask in machines[i].transition_burst_events. This causes it to enter burst mode (state B), in which a delay t is sampled from the Burst histogram, and a timer is scheduled to count down until either another matching packet arrives, or t expires. If the "Infinity" time is sampled from this histogram, the machine returns to the Start state. If a packet that matches machines[i].burst.transition_start_events arrives before t expires, the machine transitions back to the Start state. If a packet that matches machines[i].burst.transition_reschedule_events arrives before t expires, a new delay is sampled and the process is repeated again, i.e. it remains in burst mode. Otherwise, if t expires, a padding message is sent to the other end. If a packet that matches machines[i].burst.transition_gap_events arrives (or is sent), the machine transitions to the Gap state G. In state G, the machine samples from the Gap histogram and sends padding messages when the time it samples expires. If an infinite delay is sampled while being in state G we jump back to state B. If a packet arrives that matches gap.transition_start_events, the machine transitions back to the Start state. If a packet arrives that matches gap.transition_burst_events, the machine transitions back to the Burst state. If a packet arrives that matches machines[i].gap.transition_reschedule_events, the machine remains in G but schedules a new padding time from its Gap histogram. In the event that a malicious or buggy client specifies conflicting state transition rules with the same bits in multiple transition bitmasks, the transition rules of a state that specify transition to earlier states take priority. So burst.transition_start_events takes priority over burst.transition_reschedule_events, and both of these take priority over burst.transition_gap_events. Similarly, gap.transition_start_events takes priority over gap.transition_burst_events, and gap.transition_burst_events takes priority over gap.transition_reschedule_events. In our generalization of Adaptive Padding, either histogram may actually be self-scheduling (by setting the bit RELAY_PADDING_TRANSITION_EVENT_PADDING_SENT in their transition_reschedule_events). This allows the client to create a single-state machine if desired. Clients are expected to maintain their own local version of the state machines, for reacting to their own locally generated traffic, in addition to sending one or more state machines to the middle relay. The histograms that the client uses locally will differ from the ones it sends to the upstream relay. On the client, the "SENT" direction means packets destined towards the upstream, where as "RECV" means packets destined towards the client. However, on the relay, the "SENT" direction means packets destined towards the client, where as "RECV" means packets destined towards the relay. 3.2.2. The original Adaptive Padding algorithm As we have noted, the state machines above represent a generalization of the original Adaptive Padding algorithm. To implement the original behavior, the following flags should be set in both the client and the relay state machines: num_machines = 1; machines[0].transition_burst_events = RELAY_PADDING_TRANSITION_EVENT_NONPADDING_SENT; machines[0].burst.transition_reschedule_events = RELAY_PADDING_TRANSITION_EVENT_NONPADDING_SENT; machines[0].burst.transition_gap_events = RELAY_PADDING_TRANSITION_EVENT_PADDING_SENT; machines[0].gap.transition_reschedule_events = RELAY_PADDING_TRANSITION_EVENT_PADDING_SENT; machines[0].gap.transition_burst_events = RELAY_PADDING_TRANSITION_EVENT_NONPADDING_SENT; The rest of the transition fields would be 0. Adding additional transition flags will either increase or decrease the amount of padding sent, depending on their placement. The second machine slot is provided in the event that it proves useful to have separate state machines reacting to both sent and received traffic. 3.2.3. Histogram decoding/representation Each of the histograms' fields represent a probability distribution that is expanded into bins representing time periods a[i]..b[i] as follows: start_usec,max_sec,histogram_len initialized from appropriate histogram body. n = histogram_len-1 INFINITY_BIN = n a[0] = start_usec; b[0] = start_usec + max_sec*USEC_PER_SEC/2^(n); for(i=1; i < n; i++) { a[i] = start_usec + max_sec*USEC_PER_SEC/2^(n-i) b[i] = start_usec + max_sec*USEC_PER_SEC/2^(n-i-1) } To sample the delay time to send a padding packet, perform the following: i = 0; curr_weight = histogram[0]; tot_weight = sum(histogram); bin_choice = crypto_rand_int(tot_weight); while (curr_weight < bin_choice) { curr_weight += histogram[i]; i++; } if (i == INFINITY_BIN) return; // Don't send a padding packet // Sample uniformly between a[i] and b[i] send_padding_packet_at = a[i] + crypto_rand_int(b[i] - a[i]); In this way, the bin widths are exponentially increasing in width, where the width is set at max_sec/2^(n-i) seconds. This exponentially increasing bin width allows the histograms to most accurately represent small interpacket delay (where accuracy is needed), and devote less accuracy to larger timescales (where accuracy is not as important). 3.2.4. Token removal and refill If the remove_tok field is set to true for a given state's histogram, then whenever a padding packet is sent, the corresponding histogram bin's token count is decremented by one. If a packet matching the current state's transition_reschedule_events bitmask arrives from the server before the chosen padding timer expires, then a token is removed from the nearest non-empty bin corresponding to the delay since the last packet was sent, and the padding packet timer is re-sampled from the histogram. If the entire histogram becomes empty, it is then refilled to the original values. 3.2.5. Constructing the histograms Care must be taken when constructing the histograms themselves, since their non-uniform widths means that the actual underlying probability distribution needs to be both normalized for total number of tokens, as well as the non-uniform histogram bin widths. Care should also be taken with interaction with the token removal rules from Section 3.2.4. Obviously using a large number of tokens will cause token removal to have much less of an impact upon the adaptive nature of the padding in the face of existing traffic. Actual optimal histogram and state transition construction for different traffic types is expected to be a topic for further research. Intuitively, the burst state is used to detect when the line is idle (and should therefore have few or no tokens in low histogram bins). The lack of tokens in the low histogram bins causes the system to remain in the burst state until the actual application traffic either slows, stalls, or has a gap. The gap state is used to fill in otherwise idle periods with artificial payloads from the server (and should have many tokens in low bins, and possibly some also at higher bins). It should be noted that due to our generalization of these states and their transition possibilities, more complicated interactions are also possible. 4. Security considerations and mitigations The risks from this proposal are primarily DoS/resource exhaustion, and side channels. 4.1. Rate limiting Fully client-requested padding introduces a vector for resource amplification attacks and general network overload due to overly-aggressive client implementations requesting too much padding. Current research indicates that this form of statistical padding should be effective at overhead rates of 50-60%. This suggests that clients that use more padding than this are likely to be overly aggressive in their behavior. We recommend that three consensus parameters be used in the event that the network is being overloaded from padding to such a degree that padding requests should be ignored: * CircuitPaddingMaxRatio - The maximum ratio of padding traffic to non-padding traffic (expressed as a percent) to allow on a circuit before ceasing to pad. Ex: 75 means 75 padding packets for every 100 non-padding packets. - Default: 100 * CircuitPaddingLimitCount - The number of padding cells that must be transmitted before the ratio limit is applied. - Default: 500 * CircuitPaddingLimitTime - The time period in seconds over which to count padding cells for application of the ratio limit. - Default: 60 XXX: Should we cap padding at these rates, or fully disable it once they're crossed? Proposal 251 introduced extra-info accounting at relays to enable us to measure the total overhead of both link and circuit-level padding at various relays. 4.2. Malicious state machines The state machine capabilities of RELAY_COMMAND_PADDING_ADAPTIVE are very flexible, and as a result may specify conflicting or non-deterministic state transitions. We believe that the rules in Section 3.2.1 for prioritizing transitions towards lower states remove any possibility of non-deterministic transitions. However, because of self-triggering property that allows the state machines to schedule more padding packets after sending their own locally generated padding packets, care must be taken with the interaction with the rate limiting rules in Section 4.1. If the limits in section 4.1 are exceeded, the state machines should stop, rather than continually poll themselves trying to transmit packets and being blocked by the rate limiter at another layer. 4.3. Libevent timer exhaustion As mentioned in section 3.1, scheduled padding may create an excessive number of libevent timers. Care should be taken in the implementation to devise a way to prevent clients from sending padding requests specifically designed to impact the ability of relays to function by causing too many timers to be scheduled at once. XXX: Can we suggest any specifics here? I can imagine a few ways of lazily scheduling timers only when they are close to their expiry time, and other ways of minimizing the number of pending timer callbacks at a given time, but I am not sure which would be best for libevent. 4.4. Side channels In order to prevent relays from introducing side channels by requesting padding from clients, all of these commands should only be valid in the outgoing (from the client/OP) direction. Clients should perform accounting on the amount of padding that they receive, and if it exceeds the amount that they have requested, they alert the user of a potentially misbehaving node, and/or close the circuit. Similarly, if RELAY_DROP cells arrive from the last hop of a circuit, rather than from the expected interior node, clients should alert the user of the possibility of that circuit endpoint introducing a side-channel attack, and/or close the circuit. ------------------- 1. https://gitweb.torproject.org/torspec.git/tree/proposals/251-netflow-paddin… 2. http://freehaven.net/anonbib/cache/ShWa-Timing06.pdf -- Mike Perry

3 3