- tor-dev - lists.torproject.org

CAPTCHA Monitoring Project's Dashboard
by Barkin Simsek 11 Aug '20

11 Aug '20

Hi everyone, I created a wiki page [1] for "describing" the graphs that will be used to visualize the CAPTCHA Monitor dataset [2]. There are already a few graphs on the dashboard [3] and they will be replaced with the new ones described on the wiki page. I'm interested in hearing your feedback on the graph descriptions [1] and suggestions for adding new graphs. I want to understand if the graphs I proposed make sense and useful for anyone. The descriptions have a similar style to the one used in the metrics website's "Reproducible Metrics" page [4]. Thank you in advance! Best, Barkin (woswos) [1] https://gitlab.torproject.org/woswos/CAPTCHA-Monitor/-/wikis/Dashboard-Grap… [2] https://gitlab.torproject.org/woswos/CAPTCHA-Monitor/-/wikis/home [3] https://dashboard.captcha.wtf [4] https://metrics.torproject.org/reproducible-metrics.html

2 1

CentOS 8 TOR Repo
by Ladar Levison 07 Aug '20

07 Aug '20

It appears that installing TOR via the CentOS 8 DNF repo isn't working. The pre-flight configuration check fails because the repo package was built using zstd 1.4.4, and CentOS 8 is currently providing zstd 1.4.2. For any that cares to try, the repo is at: https://rpm.torproject.org/centos/8/ L~

2 2

Connection padding set to 1 vs auto
by procmem＠riseup.net 06 Aug '20

06 Aug '20

Hi. I was wondering if setting the connection padding setting in torrc to 1 instead of auto has any benefit in protecting against a passive adversary outside the Tor network.

1 0

CAPTCHA Monitoring Project Updates #3
by Barkin Simsek 25 Jul '20

25 Jul '20

Hi everyone, I have a few more updates since my last email (you might want to check the project's wiki page [0] first if you didn't see my previous emails): -- I have the onion service [1] of the dashboard [2] up and running. -- I was using an SQLite database and migrated it to PostgreSQL. This migration was needed to scale up the whole system. At the moment, there are 50000+ measurements in the database, and access time was very long with SQLite. -- Now there is a properly documented API [3] available for everyone's use. You can perform queries through the API if you prefer to access the raw data, instead of the visualizations on the dashboard. -- The Dockerfile [4] is updated and working again. -- I decided to give priority to the API and Dockerfile for the "reproducibility" of the results and graphs in the dashboard. Before the API, the graphs were using hardcoded SQL queries, which required people to dig in the source code to find out possible mistakes. It was also impossible for people to execute these SQL queries and see the results themselves. API allows me to put a link to the exact API calls to anything I place on the dashboard so that people can double-check with the raw data if they want. -- I'm working on adding Brave Browser's "Private Window with Tor" to the CAPTCHA Monitor. I'm very close to finishing it and should be ready at the end of this weekend. I expect to see a high amount of CAPTCHA since it is using Tor without Tor Browser's user-agent (and thus fingerprint). -- I discussed a possible integration with the metrics website on the metrics team meeting. I initially thought about placing CAPTCHA rate graphs under each relay in the "Relay Search" section. If you have any suggestions, you are welcomed to mention them in ticket tpo/metrics/website/40002 [5]. -- Finally, you can take a look at my blog posts on DIAL's blog [6] to see more detailed explanations, but I already summarized the blog posts in this email. Best, Barkin (woswos) [0] https://gitlab.torproject.org/woswos/CAPTCHA-Monitor/-/wikis/home [1] http://captchaufjq5m2i73up537pldaxnbp6rzcbdrzc7y5rlwtx3mwigznad.onion/ [2] https://dashboard.captcha.wtf/ [3] https://api.captcha.wtf/ [4] https://gitlab.torproject.org/woswos/CAPTCHA-Monitor/-/tree/master/docker [5] https://gitlab.torproject.org/tpo/metrics/website/-/issues/40002 [6] https://hub.osc.dial.community/t/tor-project-cloudflare-captcha-monitoring/…

1 0

Distributing Tor developer keys via Fedora packages
by Andrew Clausen 20 Jul '20

20 Jul '20

Hi everyone, I propose distributing the Tor developer keys inside the Fedora package distribution-gpg-keys.[1] This would give most Linux users a trustworthy chain of signatures from their own distributor (e.g. CentOS or Fedora) to Tor project downloads. I am happy to take care of this, although I am also happy if somebody who is more involved with Tor than me takes this on. I wrote a shell script (attached) to acquire and organise the keys based on https://2019.www.torproject.org/include/keys.txt. My script would install the following keys under /usr/share/distribution-gpg-keys/tor: Arm_releases/Damian_Johnson.gpg Tails_live_system_releases/The_Tails_team.gpg TorBirdy_releases/Sukhbir_Singh.gpg Tor_Browser_releases/Arthur_Edelstein.gpg Tor_Browser_releases/Georg_Koppen.gpg Tor_Browser_releases/Mike_Perry.gpg Tor_Browser_releases/Nicolas_Vigier.gpg Tor_Browser_releases/The_Tor_Browser_Developers.gpg Tor_source_tarballs/Nick_Mathewson.gpg Tor_source_tarballs/Roger_Dingledine.gpg Torsocks_releases/David_Goulet.gpg deb.torproject.org_repositories_and_archives/Tor_Project_Archive.gpg older_Tor_tarballs/Nick_Mathewson.gpg other/Peter_Palfrader.gpg Unless someone else volunteers (please do!), I will set up a weekly job to run the script and alert me to any changes. Can anyone see any potential problems with this plan? The most obvious question is: how do I know that I am distributing unadulterated keys? I think the answer is that I don't! But any attack would have to affect a large group of people, and would be detected quickly as long as many people are looking at the distribution-gpg-keys package. If this solution is unsatisfactory, then perhaps someone who is more involved with the Tor developers -- and hence able to directly check the keys -- ought to take this on. [1] See https://github.com/xsuchy/distribution-gpg-keys and https://rpmfind.net/linux/RPM/fedora/updates/32/x86_64/Packages/d/distribut…

2 2

Proposal 325: Packed relay cells: saving space on small commands
by Nick Mathewson 10 Jul '20

10 Jul '20

``` Filename: 325-packed-relay-cells.md Title: Packed relay cells: saving space on small commands Author: Nick Mathewson Created: 10 July 2020 Status: Draft ``` # Introduction In proposal 319 I suggested a way to fragment long commands across multiple RELAY cells. In this proposal, I suggest a new format for RELAY cells that can be used to pack multiple relay commands into a single cell. Why would we want to do this? As we move towards improved congestion-control and flow-control algorithms, we might not want to use an entire 498-byte relay payload just to send a one-byte flow-control message. We already have some cases where we'd benefit from this feature. For example, when we send SENDME messages, END cells, or BEGIN_DIR cells, most of the cell body is wasted with padding. As a side benefit, packing cells in this way may make the job of the traffic analyst a little more tricky, as cell contents become less predictable. # The basic design Let's use the term "Relay Message" to mean the kind of thing that a relay cell used to hold. Thus, this proposal is about packing multiple "Relay Messages" in to a cell. I'll use "Packed relay cell" to mean a relay cell in this new format, that supports multiple messages. I'll use "client" to mean the initiator of a circuit, and "relay" to refer to the parties through who a circuit is created. Note that each "relay" (as used here) may be the "client" on circuits of its own. When a relay supports relay message packing, it advertises the fact using a new Relay protocol version. Clients must opt-in to using this protocol version (see XXX below) before they can send any packed relay cells, and before the relay will send them any packed relay cells. When packed cells are in use, multiple cell messages can be concatenated in a single relay cell. Only some relay commands are supported for relay cell packing, listed here: - SENDME - DROP - DATA - BEGIN - BEGIN_DIR - END - CONNECTED - PADDING_NEGOTIATE - PADDING_NEGOTIATED If any relay message with a relay command _not_ listed above appears in a packed relay cell with another relay message, then the receiving party MUST tear down the circuit. (Note that relay cell fragments (proposal 319) are not supported for packing.) The command byte "0" is now used to explicitly indicate "end of cell". If the byte "0" appears after a relay message, the rest of the cell MUST be ignored. When generating RELAY cells, implementations SHOULD (as they do today) fill in the unused bytes with four 0-valued bytes, followed by a sequence of random bytes up to the end of the cell. If there are fewer than 4 unused bytes at the end of the cell, those unused bytes should all be filled with 0-valued bytes. # Negotiation and migration After receiving a packed relay cell, the relay know that the client supports this proposal: Relays SHOULD send packed relay cells on any circuit on which they have received a packed relay cell. Relays MUST NOT send packed relay cells otherwise. Clients, in turn, MAY send packed relay cells to any relay whose "Relay" subprotocol version indicates that it supports this protocol. To avoid fingerprinting, this client behavior should controlled with a tristate (1/0/auto) torrc configuration value, with the default set to use a consensus parameter. The parameter is: "relay-cell-packing" Boolean: if 1, clients should send packed relay cells. (Min: 0, Max 1, Default: 0) To handle migration, first the parameter should be set to 0 and the configuration setting should be "auto". To test the feature, individual clients can set the tristate to "1". Once enough clients have support for the parameter, the parameter can be set to 1. # A new relay message format (This section is optional and should be considered separately; we may decide it is too complex.) Currently, every relay message uses 5 bytes of header to hold a relay command, a length field, and a stream ID. This is wasteful: the stream ID is often redundant, and the top 7 bits of the length field are always zero. I propose a new relay message format, described here (with `ux` denoting an x-bit bitfield). This format is 2 bytes or 4 bytes, depending on its first bit. struct relay_header { u1 stream_id_included; // Is the stream_id included? u6 relay_command; // as before u9 relay_data_len; // as before u8 optional_stream_id[]; // 0 bytes or two bytes. } Alternatively, you can view the first three fields as a 16-bit value, computed as: (stream_id_included<<15) | (relay_command << 9) | (relay_data_len). If the optional_stream_id field is not present, then the default value for the stream_id is computed as follows. We use stream_id 0 for any command that doesn't take a stream ID. For commands that _do_ take a steam_id, we use whichever nonzero stream_id appeared last in this cell. This format limits the space of possible relay commands. That's probably okay: after 20 years of Tor development, we have defined 25 relay command values. But in case 2^6==64 commands will not be enough, we reserve command values 48 through 63 for future formats that need more command bits.

3 2

CAPTCHA Monitoring Project Updates & Findings
by Barkin Simsek 09 Jul '20

09 Jul '20

Hi everyone, I made progress on the Cloudflare CAPTCHA Monitoring project since my last email, and I wanted to share some of the updates & findings. This year Tor Project is participating in GSoC under the DIAL umbrella, and I have already been posting updates to the DIAL blog [1] weekly. I started mirroring these updates [2] to my project's wiki page, and I will be posting more frequent updates here. a) Updates: Firstly, I moved the wiki page that explains the project, the code base, and the issue tracker to Tor Project's GitLab. They are all in the same GitLab project. You can find detailed information about the project on the wiki page [3] and leave comments & suggestions within that repository by creating issues. Secondly, I got a fully functioning system up and running. The system fetches various URLs with Tor Browser & Firefox over Tor and checks for CAPTCHAs. The system also checks if any third-party code was injected by comparing the hash of the received page with an expected hash value. It repeats these experiments using different exit relays and records results. You can view the results on the dashboard [4] I created. I'm looking for more URLs to track for CAPTCHAs. Feel free to share the websites you frequently visit and get CAPTCHAs, so that I can track these websites with this tool as well. I want to experiment with all types of CAPTCHAs, and these URLs don't have to be fronted by Cloudflare. b) Findings: So far, I have observed that using the Tor Browser Bundle out of the box without changing its configurations doesn't lead to a high CAPTCHA rate on Cloudflare fronted websites (assuming the website owners don't explicitly block exit relays [5]). That said, modifying the user-agent or any other modifications that deviate your browser's fingerprint from a typical Tor Browser user, significantly increases the chance of getting CAPTCHAs. For example, using the regular Firefox over Tor resulted in getting CAPTCHAs in ~90% of the measurements. I believe Cloudflare is very aggressive against the "Firefox over Tor" users because many people, unfortunately, use Chromium/Firefox + Selenium + Tor to scrape web pages and bypass IP-based rate limits. That's why I'm interested in hearing about your specific browser/Tor configurations to test them with the CAPTCHA Monitor. Not everyone is affected in the same way because of these differences in the way we use Tor, but we can understand which differences affect the CAPTCHA rate more than others by experimenting. Additionally, I observed that the TLS fingerprint has a significant role in whether someone gets a CAPTCHA or not. As a part of the project, I decided to capture the HTTP headers during measurements to understand how they affect the CAPTCHA rates. Initially, I was using a Python library called seleniumwire to capture the HTTP headers by intercepting the traffic between the Tor Browser and Tor. By doing this, I got a very high CAPTCHA rate, like 98% of the time. seleniumwire forwards the traffic transparently, but it has a different TLS fingerprint than Tor Browser. I figured out that the difference in the TLS fingerprints was triggering the MITM detection on the Cloudflare side, thus, resulting in very high CAPTCHA rates. Interestingly, I tried using the exact same Tor Browser & seleniumwire setup, but without Tor and, practically, I didn't get any CAPTCHAs. I believe the MITM detection is more aggressive if the traffic is coming through an exit relay. So, I stopped using seleniumwire to capture headers because it didn't reflect what a real human Tor Browser user is usually experiencing. Please feel free to use the sample code [6] that I used to combine seleniumwire and Tor, if you are interested in doing further experimenting on this. c) Next: I will work on collecting more metrics by testing more configurations and websites. I will create a "Relay Search" section on the dashboard, where CAPTCHA statistics for the relays (exit relays for now) will be available. I will also work on using the collected data to predict the probability of getting CAPTCHAs with a given exit relay and configuration/setup. Best, Barkin [1] https://hub.osc.dial.community/t/tor-project-cloudflare-captcha-monitoring/… [2] https://gitlab.torproject.org/woswos/CAPTCHA-Monitor/-/wikis/Updates [3] https://gitlab.torproject.org/woswos/CAPTCHA-Monitor/-/wikis/home [4] https://dashboard.captcha.wtf/ [5] Cloudflare has a setting to block all traffic originating from the Tor network, but that setting is not "turned on" by default [6] https://gist.github.com/woswos/38b921f0b82de009c12c6494db3f50c5

1 0

Gitolite to Gitlab Sync Change
by Alexander Færøy 09 Jul '20

09 Jul '20

Hello folks! In an attempt to solve Gitlab#41[1] the hooks that is executed when you push to git.torproject.org to synchronize to Gitlab was modified to avoid pruning references in Gitlab that was missing in the Gitolite repository. This /should/ have the following implications: - We no longer delete the "refs/merge-requests/*" namespace each time someone pushes to your repository on git.torproject.org. This should allow people to use the `git mr` alias that can be found online which should make local code-reviews easier and also allow you to handle manual CLI merging more easily. - We no longer delete branches automatically on Gitlab: if a branch is deleted on git.torproject.org. This have to be deleted manually now on Gitlab. Please report any issues you that you might discover on the ticket. Thanks to Hiro for getting this running! All the best, Alex. [1]: https://gitlab.torproject.org/tpo/tpa/gitlab/-/issues/41 -- Alexander Færøy

1 0

Gitlab CI runners available for experimentation on gitlab.torproject.org
by Alexander Færøy 09 Jul '20

09 Jul '20

Hello folks! Hans from The Guardian Project added his CI runners to our Gitlab instance. It looks like some pretty fast machines that allows each team to experiment with Gitlab CI on our Gitlab instance. Hans says that the runners have no uptime promises or anything like that, so if they are down they are down :-) Here's some documentation for getting started: https://docs.gitlab.com/ee/ci/ Thanks to Hans for this! All the best, Alex. -- Alexander Færøy

2 1

Proposal: RTT-based Congestion Control for Tor
by Mike Perry 02 Jul '20

02 Jul '20

https://github.com/mikeperry-tor/torspec/blob/rtt-congestion-control/propos… https://github.com/torproject/torspec/pull/125 ================================ Filename: 324-rtt-congestion-control.txt Title: RTT-based Congestion Control for Tor Author: Mike Perry Created: 02 July 2020 Status: Open 0. Motivation [MOTIVATION] This proposal specifies how to incrementally deploy RTT-based congestion control and improved queue management in Tor. It is written to allow us to first deploy the system only at Exit relays, and then incrementally improve the system by upgrading intermediate relays. Lack of congestion control is the reason why Tor has an inherent speed limit of about 500KB/sec for downloads and uploads via Exits, and even slower for onion services. Because our stream SENDME windows are fixed at 500 cells per stream, and only ~500 bytes can be sent in one cell, the max speed of a single Tor stream is 500*500/circuit_latency. This works out to about 500KB/sec max sustained throughput for a single download, even if circuit latency is as low as 500ms. Because onion services paths are more than twice the length of Exit paths (and thus more than twice the circuit latency), onion service throughput will always have less than half the throughput of Exit throughput, until we deploy proper congestion control with dynamic windows. Proper congestion control will remove this speed limit for both Exits and onion services, as well as reduce memory requirements for fast Tor relays, by reducing queue lengths. The high-level plan is to use Round Trip Time (RTT) as a primary congestion signal, and compare the performance of two different congestion window update algorithms that both use RTT as a congestion signal. The combination of RTT-based congestion signaling, a congestion window update algorithm, and Circuit-EWMA will get us the most if not all of the benefits we seek, and only requires clients and Exits to upgrade to use it. Once this is deployed, circuit bandwidth caps will no longer be capped at ~500kb/sec by the fixed window sizes of SENDME; queue latency will fall significantly; memory requirements at relays should plummet; and transient bottlenecks in the network should dissipate. Extended background information on the choices made in this proposal can be found at: https://lists.torproject.org/pipermail/tor-dev/2020-June/014343.html https://lists.torproject.org/pipermail/tor-dev/2020-January/014140.html An exhaustive list of citations for further reading is in Section [CITATIONS]. 1. Overview [OVERVIEW] This proposal has five main sections, after this overview. These sections are referenced [IN_ALL_CAPS] rather than by number, for easy searching. Section [CONGESTION_SIGNALS] specifies how to use Tor's SENDME flow control cells to measure circuit RTT, for use as an implicit congestion signal. It also specifies an explicit congestion signal, which can be used as a future optimization once all relays upgrade. Section [CONTROL_ALGORITHMS] specifies two candidate congestion window upgrade mechanisms, which will be compared for performance in simulation in Shadow, as well as evaluated on the live network, and tuned via consensus parameters listed in [CONSENSUS_PARAMETERS]. Section [FLOW_CONTROL] specifies how to handle back-pressure when one of the endpoints stops reading data, but data is still arriving. In particular, it specifies what to do with streams that are not being read by an application, but still have data arriving on them. Section [SYSTEM_INTERACTIONS] describes how congestion control will interact with onion services, circuit padding, and conflux-style traffic splitting. Section [EVALUATION] describes how we will evaluate and tune our options for control algorithms and their parameters. Section [PROTOCOL_SPEC] describes the specific cell formats and descriptor changes needed by this proposal. Section [SECURITY_ANALYSIS] provides information about the DoS and traffic analysis properties of congestion control. 2. Congestion Signals [CONGESTION_SIGNALS] In order to detect congestion at relays on a circuit, Tor will use circuit Round Trip Time (RTT) measurement. This signal will be used in slightly different ways in our various [CONTROL_ALGORITHMS], which will be compared against each other for optimum performance in Shadow and on the live network. To facilitate this, we will also change SENDME accounting logic slightly. These changes only require clients, exits, and dirauths to update. As a future optimization, we also specify an explicit congestion signal. This signal *will* require all relays on a circuit to upgrade to support it, but it will reduce congestion by making the first congestion event on a circuit much faster to detect. 2.1 RTT measurement Recall that Tor clients, exits, and onion services send RELAY_COMMAND_SENDME relay cells every CIRCWINDOW_INCREMENT (100) cells of received RELAY_COMMAND_DATA. This allows those endpoints to measure the current circuit RTT, by measuring the amount of time between sending of every 100th data cell and the arrival of the SENDME command that the other endpoint immediately sends to ack that 100th cell. Circuits will record the current RTT measurement as a field in their circuit_t data structure. They will also record the minimum and maximum RTT seen so far. Algorithms that make use of this RTT measurement for congestion window update are specified in [CONTROL_ALGORITHMS]. 2.2. SENDME behavior changes We will make four major changes to SENDME behavior to aid in computing and using RTT as a congestion signal. First, we will need to establish a ProtoVer of "CCtrl=1" to signal support by Exits for the new SENDME format and congestion control algorithm mechanisms. We will need a similar announcement in the onion service descriptors of services that support congestion control. Second, we will turn CIRCWINDOW_INCREMENT into a consensus parameter 'circwindow_inc', instead of using a hardcoded value of 100 cells. It is likely that more frequent SENDME cells will provide quicker reaction to congestion, since the RTT will be measured more often. If experimentation in Shadow shows that more frequent SENDMEs reduce congestion and improve performance but add significant overhead, we can reduce SENDME overhead by allowing SENDME cells to carry stream data, as well. TODO: If two endpoints view different consensus parameters for 'circwindow_inc', we will have complications measuring RTT, as well as complications for authenticated SENDME hash accounting. We need a way for endpoints to negotiate SENDME pacing with eachother, perhaps during circuit setup. This will require changes to the Onionskin/CREATE cell format (and RELAY_COMMAND_EXTEND), as mentioned in Section [PROTOCOL_SPEC]. Second, all end-to-end relay cells except RELAY_COMMAND_DROP and RELAY_COMMAND_INTRODUCE1 will count towards SENDME cell counts. The details behind how these cells are handled is addressed in section [SYSTEM_INTERACTIONS]. TODO: List any other exceptions. There probably are some more. Third, authenticated SENDMEs can remain as-is in terms of protocol behavior, but will require some implementation updates to account for variable window sizes and variable SENDME pacing. In particular, the sendme_last_digests list for auth sendmes needs updated checks for larger windows and CIRCWINDOW_INCREMENT changes. Other functions to examine include: - circuit_sendme_cell_is_next() - sendme_record_cell_digest_on_circ() - sendme_record_received_cell_digest() - sendme_record_sending_cell_digest() - send_randomness_after_n_cells Fourth, stream level SENDMEs will be eliminated. Details on handling streams and backpressure is covered in [FLOW_CONTROL]. 2.3. Backward ECN signaling [BACKWARD_ECN] As an optimization after the RTT deployment, we will deploy an explicit congestion control signal by allowing relays to modify the cell_t.command field when they detect congestion, on circuits for which all relays have support for this signal (as mediated by Tor protocol version handshake via the client). This is taken from the Options mail[1], section BACKWARD_ECN_TOR. To detect congestion in order to deliver this signal, we will deploy a simplified version of the already-simple CoDel algorithm on each outbound TLS connection at relays. https://queue.acm.org/detail.cfm?id=2209336 https://tools.ietf.org/html/rfc8289 Each cell will get a timestamp upon arrival at a relay that will allow us to measure how long it spends in queues, all the way to hitting a TLS outbuf. The duration of total circuitmux queue time for each cell will be compared a consensus parameter 'min_queue_target', which is set to 5% of min network RTT. (This mirrors the CoDel parameter of the same name). As soon as a cell of a circuit spends more than this time in queues, a per-circuit flag 'ecn_exit_slow_start' will be set to 1. As soon as a cell is available in the opposite direction on that circuit, the relay will flip the cell_t.command of from CELL_COMMAND_RELAY to CELL_COMMAND_RELAY_CONGESTION. (We must wait for a cell in the opposite direction because that is the sender that caused the congestion). This enhancement will allow endpoints to very quickly exit from [CONTROL_ALGORITHM] "slow start" phase (during which, the congestion window increases exponentially). The ability to more quickly exit the exponential slow start phase during congestion will help reduce queue sizes at relays. To avoid side channels, this cell must only be flipped on CELL_COMMAND_RELAY, and not CELL_COMMAND_RELAY_EARLY. Additionally, all relays MUST enforce that only *one* such cell command is flipped, per direction, per circuit. Any additional CELL_COMMAND_RELAY_CONGESTION cells seen by any relay or client MUST cause those circuit participants to immediately close the circuit. As a further optimization, if no relay cells are pending in the opposite direction as congestion is happening, we can send a zero-filled cell instead. In the forward direction of the circuit, we can send this cell without any crypto layers, so long as further relays enforce that the contents are zero-filled, to avoid side channels. 3. Congestion Window Update Algorithms [CONTROL_ALGORITHMS] We specify two candidate window update algorithms. The specification describes the update algorithms for the slow start phase and the steady state phase separately, with some explanation. Then the combined algorithm is given. Note that these algorithms differ slightly from the background tor-dev mails[1,2], due to corrections and improvements. Hence they have been given different names than in those two mails. These algorithms will be evaluated by running Shadow simulations, to help determine parameter ranges, but experimentation on the live network will be required to determine which of these algorithms performs best when in competition with our current SENDME behavior, as used by real network traffic. This experimentation and tuning is detailed in section [EVALUATION]. All of these algorithms have rules to update 'cwnd' - the current congestion window. In the C Tor reference implementation, 'cwnd' is called the circuit 'package_window'. C Tor also maintains a 'deliver_window', which it uses to track how many cells it has received, in order to send the appropriate number of SENDME acks. TODO: This 'deliver_window' count can be updated by the other endpoint using the congestion control rules to watch for cheating. Alternatively, it can be simplified just to count the number of cells we get until we send a SENDME. Implementation of different algorithms should be very simple - each algorithm should have a different set of package_window update functions depending on the selected algorithm, as specified by consensus parameter 'cc_alg'. For C Tor's current flow control, these functions are defined in sendme.c, and are called by relay.c: - sendme_note_circuit_data_packaged() - sendme_circuit_data_received() - sendme_circuit_consider_sending() - sendme_process_circuit_level() Despite the complexity of the following algorithms in their TCP implementations, their Tor equivalents are extremely simple, each being just a handful of lines of C. This simplicity is possible because Tor does not have to deal with out-of-order delivery, packet drops, duplicate packets, and other network issues at the circuit layer, due to the fact that Tor circuits already have reliability and in-order delivery at that layer. We are also removing the aspects of TCP that cause the congestion algorithm to reset into slow start after being idle for too long, or after too many congestion signals. These are deliberate choices that simplify the algorithms and also should provide better performance for Tor workloads. TODO: We may want to experiment with adding revert-to-slow-start back in, but slow start is very expensive in a lot of ways, so let's see if we can avoid falling back into it, if at all possible. 3.1. Tor Westwood: TCP Westwood using RTT signaling [TOR_WESTWOOD] http://intronetworks.cs.luc.edu/1/html/newtcps.html#tcp-westwood http://nrlweb.cs.ucla.edu/nrlweb/publication/download/99/2001-mobicom-0.pdf http://cpham.perso.univ-pau.fr/TCP/ccr_v31.pdf https://c3lab.poliba.it/images/d/d7/Westwood_linux.pdf Recall that TCP Westwood is basically TCP Reno, but it uses RTT to help estimate the bandwidth-delay-product (BDP) of the link, and use that for "Fast recovery" after a congestion signal arrives. We will also be using the RTT congestion signal as per BOOTLEG_RTT_TOR here, from the Options mail[1] and Defenestrator paper[3]. Recall that BOOTLEG_RTT_TOR emits a congestion signal when the current RTT falls below some fractional threshold ('rtt_thresh') fraction between RTT_min and RTT_max: RTT_current < (1−rtt_thresh)*RTT_min + rtt_thresh*RTT_max We can also optionally use the ECN signal described in [BACKWARD_ECN] above, to exit Slow Start. Tor Westwood will require each circuit endpoint to maintain a Bandwidth-Delay-Product (BDP) and Bandwidth Estimate (BWE) variable. The bandwidth estimate is the current congestion window size divided by the RTT estimate: BWE = cwnd / RTT_current The BDP estimate is computed by multiplying the Bandwidth estimate by the circuit latency: BDP = BWE * RTT_min TODO: Different papers on TCP Westwood and TCP Vegas recommend different methods for calculating BWE. See citations for details, but common options are 'packets_in_flight/RTT_current' or 'circwindow_inc*sendme_arrival_rate'. They also recommend averaging and filtering of the BWE, due to ack compression in inbound queues. We will need to experiment to determine how to best compute the BWE for Tor circuits. 3.1.1. Tor Westwood: Slow Start Prior to the first congestion signal, Tor Westwood will update its congestion window exponentially, as per Slow Start. Recall that this first congestion signal can be either BOOTLEG_RTT_TOR's RTT threshold signal, or BACKWARD_ECN's cell command signal. For simplicity, we will just write the BOOTLEG_RTT_TOR check, which compares the current RTT measurement to the observed min and max RTT, using the consensus parameter 'rtt_thresh'. This section of the update algorithm is: cwnd = cwnd + circwindow_inc # For acked cells # BOOTLEG_RTT_TOR threshold check: if RTT_current < (1−rtt_thresh)*RTT_min + rtt_thresh*RTT_max: cwnd = cwnd + circwindow_inc # Exponential window growth else: BDP = BWE*RTT_min cwnd = max(cwnd * cwnd_recovery_m, BDP) in_slow_start = 0 Increasing the congestion window by 100 *more* cells every SENDME allows the sender to send 100 *more* cells every 100 cells. Thus, this is an exponential function that causes cwnd to double every cwnd cells. Once a congestion signal is experienced, Slow Start is exited, and the Additive-Increase-Multiplicative-Decrease (AIMD) steady-state phase begins. 3.1.2. Tor Westwood: Steady State AIMD After slow start exits, in steady-state, after every SENDME response without a congestion signal, the window is updated as: cwnd = cwnd + circwindow_inc # For acked cells cwnd = cwnd + circwindow_inc/cwnd # Linear window growth This comes out to increasing cwnd by 1, every time cwnd cells are successfully sent without a congestion signal occurring. Thus this is additive linear growth, not exponential growth. If there is a congestion signal, cwnd is updated as: cwnd = cwnd + circwindow_inc # For acked cells cwnd = max(cwnd * cwnd_recovery_m, BDP) # For window shrink This is called "Fast Recovery". If you dig into the citations, actual TCP Westwood has some additional details for responding to multiple packet losses that in some cases can fall back into slow-start, as well as some smoothing of the BDP to make up for dropped acks. Tor does not need either of these aspects of complexity. 3.1.3. Tor Westwood: Complete SENDME Update Algorithm Here is the complete congestion window algorithm for Tor Westwood, using only RTT signaling. This will run each time we get a SENDME (aka sendme_process_circuit_level()): in_slow_start = 1 # Per-circuit indicator Every received SENDME ack, do: cwnd = cwnd + circwindow_inc # Update acked cells # BOOTLEG_RTT_TOR threshold; can also be BACKWARD_ECN check: if RTT_current < (1−rtt_thresh)*RTT_min + rtt_thresh*RTT_max: if in_slow_start: cwnd = cwnd + circwindow_inc # Exponential growth else: cwnd = cwnd + circwindow_inc/cwnd # Linear growth else: BDP = BWE*RTT_min cwnd = max(cwnd * cwnd_recovery_m, BDP) # Window shrink in_slow_start = 0 3.2. Tor Vegas: TCP Vegas with Aggressive Slow Start [TOR_VEGAS] http://intronetworks.cs.luc.edu/1/html/newtcps.html#tcp-vegas http://pages.cs.wisc.edu/~akella/CS740/F08/740-Papers/BOP94.pdf ftp://ftp.cs.princeton.edu/techreports/2000/628.pdf TCP Vegas control algorithm makes use of two RTT measurements: RTT_current and RTT_min. Like TCP Westwood, it also maintains a bandwidth estimate and a BDP estimate, but those can be simplified away with algebra. The bandwidth estimate is the current congestion window size divided by the RTT estimate: BWE = cwnd/RTT_current The extra queue use along a path can thus be estimated by first estimating the path's bandwidth-delay product: BDP = BWE*RTT_min TCP Vegas then estimates the queue use caused by congestion as: queue_use = cwnd - BDP = cwnd - cwnd*RTT_min/RTT_current = cwnd * (1 - RTT_min/RTT_current) So only RTT_min and RTT_current need to be recorded to provide this queue_use estimate. TODO: This simplification might not hold for some versions of BWE and BDP estimation. See also the [TOR_WESTWOOD] section's TODO and paper citations for both TCP Westwood and TCP Vegas. 3.2.1. Tor Vegas Slow Start During slow start, we will increase our window exponentially, so long as this queue_use estimate is below the 'vegas_gamma' consensus parameter. We also re-use the Tor Westwood backoff, upon exit from Slow Start. Note though that the exit from Slow Start for here does *not* use the BOOTLEG_RTT_TOR style RTT threshold, and instead relies on the queue_use calculation directly. Tor Vegas slow start can also be exited due to [BACKWARD_ECN] cell signal, which is omitted for brevity and clarity. cwnd = cwnd + circwindow_inc # Ack cells if queue_use < vegas_gamma: # Vegas RTT check cwnd = cwnd + circwindow_inc # Exponential growth else: cwnd = max(cwnd * cwnd_recovery_m, BDP) # Westwood backoff in_slow_start = 0 3.2.2. Tor Vegas: Steady State Queue Tracking Recall that TCP Vegas does not use AIMD in the steady state. Because TCP Vegas is actually trying to directly control the queue use on the path, its updates are additive and subtractive only. If queue_use drops below a threshold alpha (typically 2-3 packets for TCP Vegas, but perhaps double or triple that for our smaller cells), then the congestion window is increased. If queue_use exceeds a threshold beta (typically 4-6 packets, but again we should probably double or triple this), then the congestion window is decreased. cwnd = cwnd + circwindow_inc # Ack cells if queue_use < vegas_alpha: cwnd = cwnd + circwindow_inc/cwnd # linear growth elif queue_use > vegas_beta: cwnd = cwnd - circwindow_inc/cwnd # linear backoff TODO: Why not reduce the window by the number of packets that queue_use is over or under the target value by, rather than just 1 cell per cwnd? Need to ask some TCP folks, or experiment. 3.2.3. Tor Vegas: Complete SENDME Update Algorithm in_slow_start = 1 # Per-circuit indicator Every received SENDME ack: cwnd = cwnd + circwindow_inc # Update acked cells queue_use = cwnd * (1 - RTT_min/RTT_current) if in_slow_start: if queue_use < vegas_gamma: cwnd = cwnd + circwindow_inc # Exponential growth else: cwnd = max(cwnd * cwnd_recovery_m, BDP) # Westwood backoff in_slow_start = 0 else: if queue_use < vegas_alpha: cwnd = cwnd + circwindow_inc/cwnd # linear growth elif queue_use > vegas_beta: cwnd = cwnd - circwindow_inc/cwnd # linear backoff 4. Flow Control [FLOW_CONTROL] Flow control provides what is known as "pushback" -- the property that if one endpoint stops reading data, the other endpoint stops sending data. This prevents data from accumulating at points in the network, if it is not being read fast enough by an application. Because Tor must multiplex many streams onto one circuit, and each stream is mapped to another TCP socket, Tor's current pushback is rather complicated and under-specified. In C Tor, it is implemented in the following functions: - circuit_consider_stop_edge_reading() - connection_edge_package_raw_inbuf() - circuit_resume_edge_reading() Tor currently maintains separate windows for each stream on a circuit, to provide individual stream flow control. Circuit windows are SENDME acked as soon as a relay data cell is decrypted and recognized. Stream windows are only SENDME acked if the data can be delivered to an active edge connection. This allows the circuit to continue to operate if an endpoint refuses to read data off of one of the streams on the circuit. Because Tor streams can connect to many different applications and endpoints per circuit, it is important to preserve the property that if only one endpoint edge connection is inactive, it does not stall the whole circuit, in case one of those endpoints is malfunctioning or malicious. However, window-based stream flow control also imposes a speed limit on individual streams. If the stream window size is below the circuit congestion window size, then it becomes the speed limit of a download, as we saw in the [MOTIVATION] section of this proposal. So for performance, it is optimal that each stream window is the same size as the circuit's congestion window. However, large stream windows are a vector for OOM attacks, because malicious clients can force Exits to buffer a full stream window for each stream while connecting to a malicious site and uploading data that the site does not read from its socket. This attack is significantly easier to perform at the stream level than on the circuit level, because of the multiplier effects of only needing to establish a single fast circuit to perform the attack on a very large number of streams. This catch22 means that if we use windows for stream flow control, we either have to commit to allocating a full congestion window worth memory for each stream, or impose a speed limit on our streams. Hence, we will discard stream windows entirely, and instead use a simpler buffer-based design that uses XON/XOFF as a backstop. This will allow us to make full use of the circuit congestion window for every stream in combination, while still avoiding buffer buildup inside the network. 4.1. Stream Flow Control Without Windows [WINDOWLESS_FLOW] Each endpoint (client, Exit, or onion service) should send circuit-level SENDME acks for all circuit cells as soon as they are decrypted and recognized, but *before* delivery to their edge connections. If the edge connection is blocked because an application is not reading, data will build up in a queue at that endpoint. Three consensus parameters will govern the max length of this queue: xoff_client, xoff_exit, and xoff_mobile. These will be used for Tor clients, exits, and mobile devices, respectively. These cuttofs will be a percentage of current 'cwnd' rather than number of cells. Something like 5% of 'cwnd' should be plenty, since these edge connections should normally drain *much* faster than Tor itself. If the length of an application stream queue exceeds the size provided in the appropriate consensus parameter, a RELAY_COMMAND_STREAM_XOFF will be sent, which instructs the other endpoint to stop sending from that edge connection. This XOFF cell can optionally contain any available stream data, as well. As soon as the queue begins to drain, a RELAY_COMMAND_STREAM_XON will sent, which allows the other end to resume reading on that edge connection. Because application streams should drain quickly once they are active, we will send the XON command as soon as they start draining. If the queues fill again, another XOFF will be sent. If this results in excessive XOFF/XON flapping and chatter, we will also use consensus parameters xon_client, xon_exit, and xon_mobile to optionally specify when to send an XON. These parameters will be defined in terms of cells below the xoff_* levels, rather than percentage. The XON cells can also contain stream data, if any is available. Tor's OOM killer will be invoked to close any streams whose application buffer grows too large, due to memory shortage, or malicious endpoints. Note that no stream buffer should ever grow larger than the xoff level plus 'cwnd', unless an endpoint is ignoring XOFF. So, 'xoff_{client,exit,mobile} + cwnd' should be the hard-close stream cutoff, regardless of OOM killer status. 5. System Interactions [SYSTEM_INTERACTIONS] Tor's circuit-level SENDME system currently has special cases in the following situations: Intropoints, HSDirs, onion services, and circuit padding. Additionally, proper congestion control will allow us to very easily implement conflux (circuit traffic splitting). This section details those special cases and interactions of congestion control with other components of Tor. 5.1. HSDirs Because HSDirs use the tunneled dirconn mechanism and thus also use RELAY_COMMAND_DATA, they are already subject to Tor's flow control. We may want to make sure our initial circuit window for HSDir circuits is set custom for those circuit types, so a SENDME is not required to fetch long descriptors. This will ensure HSDir descriptors can be fetched in one RTT. 5.2. Introduction Points Introduction Points are not currently subject to any flow control. Because Intropoints accept INTRODUCE1 cells from many client circuits and then relay them down a single circuit to the service as INTRODUCE2 cells, we cannot provide end-to-end congestion control all the way from client to service for these cells. We can run congestion control from the service to the Intropoint, however, and if that congestion window reaches zero (because the service is overwhelmed), then we start sending NACKS back to the clients (or begin requiring proof-of-work), rather than just let clients wait for timeout. 5.3. Rendezvous Points Rendezvous points are already subject to end-to-end SENDME control, because all relay cells are sent end-to-end via the rendezvous circuit splice in circuit_receive_relay_cell(). This means that rendezvous circuits will use end-to-end congestion control, as soon as individual onion clients and onion services upgrade to support it. There is no need for intermediate relays to upgrade at all. 5.4. Circuit Padding Recall that circuit padding is negotiated between a client and a middle relay, with one or more state machines running on circuits at the middle relay that decide when to add padding. https://github.com/torproject/tor/blob/master/doc/HACKING/CircuitPaddingDev… This means that the middle relay can send padding traffic towards the client that contributes to congestion, and the client may also send padding towards the middle relay, that also creates congestion. For low-traffic padding machines, such as the currently deployed circuit setup obfuscation, this padding is inconsequential. However, higher traffic circuit padding machines that are designed to defend against website traffic fingerprinting will need additional care to avoid inducing additional congestion, especially after the client or the exit experiences a congestion signal. The current overhead percentage rate limiting features of the circuit padding system should handle this in some cases, but in other cases, an XON/XOFF circuit padding flow control command may be required, so that clients may signal to the machine that congestion is occurring. 5.5. Conflux Conflux (aka multi-circuit traffic splitting) becomes significantly easier to implement once we have congestion control. However, much like congestion control, it will require experimentation to tune properly. Recall that Conflux uses a 256-bit UUID to bind two circuits together at the Exit or onion service. The original Conflux paper specified an equation based on RTT to choose which circuit to send cells on. https://www.cypherpunks.ca/~iang/pubs/conflux-pets.pdf However, with congestion control, we will already know which circuit has the larger congestion window, and thus has the most available cells in its current congestion window. This will also be the faster circuit. Thus, the decision of which circuit to send a cell on only requires comparing congestion windows (and choosing the circuit with more packets remaining in its window). Conflux will require sequence numbers on data cells, to ensure that the two circuits' data is properly re-assembled. The resulting out-of-order buffer can potentially be as large as an entire congestion window, if the circuits are very desynced (or one of them closes). It will be very expensive for Exits to maintain this much memory, and exposes them to OOM attacks. This is not as much of a concern in the client download direction, since clients will typically only have a small number of these out-of-order buffers to keep around. But for the upload direction, Exits will need to send some form of early XOFF on the faster circuit if this out-of-order buffer begins to grow too large, since simply halting the delivery of SENDMEs will still allow a full congestion window full of data to arrive. This will also require tuning and experimentation, and optimum results will vary between simulator and live network. TODO: Can we use explicit SENDME sequence number acking to make a connection-resumption conflux, to recover from circuit collapse or client migration? I am having trouble coming up with a design that does not require Exits to maintain a full congestion window full of data as a retransmit buffer in the event of circuit close. Such reconnect activity might require assistance from Guard relays so that they can help clients discover which cells were sent vs lost. 6. Performance Evaluation [EVALUATION] Congestion control for Tor will be easy to implement, but difficult to tune to ensure optimal behavior. 6.1. Congestion Signal Experiments Our first experiments will be to conduct client-side experiments to determine how stable the RTT measurements of circuits are across the live Tor network, to determine if we need more frequent SENDMEs, and/or need to use any RTT smoothing or averaging. Once we have a reliable way to measure RTT, we will need to test the reliability and accuracy of the Bandwidth Estimation (BWE) and Bandwidth-Delay-Product (BDP) measurements that are required for [TOR_WESTWOOD] and [TOR_VEGAS]. These experiments can be conducted in Shadow, with precise network topologies for which actual bandwidth and latency (and thus BWE and BDP) are known parameters. We should use the most accurate form of these estimators from Shadow experimentation to run some client tests with custom Exits on the live network, to check for high variability in these estimates, discrepancy with client application throughput and application latency, and other surprises. Care will need to be taken to increase or alter Tor's circwindow during these experiments in Shadow and on the custom Exits, so that the default of 1000 does not impose an artificial ceiling on circuit bandwidth. 6.2. Congestion Algorithm Experiments In order to evaluate performance of congestion control algorithms, we will need to implement [TOR_WESTWOOD], [TOR_VEGAS], and also variants of those without the Westwood BDP fast recovery backoff. We will need to simulate their use in the Shadow Tor network simulator. Simulation runs will need to evaluate performance on networks that use only one algorithm, as well as on networks that run a combinations of algorithms - particularly each type of congestion control in combination with Tor's current flow control. If Tor's current flow control is too aggressive, we can experiment with kneecapping these legacy flow control Tor clients by setting a low 'circwindow' consensus parameter for them. Because custom congestion control can be deployed by any Exit or onion service that desires better service, we will need to be particularly careful about how congestion control algorithms interact with rogue implementations that more aggressively increase their window sizes. During these adversarial-style experiments, we must verify that cheaters do not get better service, and that Tor's circuit OOM killer properly closes circuits that seriously abuse the congestion control algorithm, as per [SECURITY_ANALYSIS]. Finally, we should determine if the [BACKWARD_ECN] cell_t.command congestion signal is enough of an optimization to be worth the complexity, especially if it is only used once, to exit slow start. This can be determined in Shadow. 6.3. Flow Control Algorithm Experiments We will need to tune the xoff_* consensus parameters to minimize the amount of edge connection buffering as well as XON/XOFF chatter for Exits. This can be done in simulation, but will require fine-tuning on the live network. Relays will need to report these statistics in extra-info descriptor, to help with monitoring the live network conditions. 6.4. Performance Metrics [EVALUATION_METRICS] Because congestion control will affect so many aspects of performance, from throughput to RTT, to load balancing, queue length, overload, and other failure conditions, the full set of performance metrics will be required: https://trac.torproject.org/projects/tor/wiki/org/roadmaps/CoreTor/Performa… We will also need to monitor network health for relay queue lengths, relay overload, and other signs of network stress (and particularly the alleviation of network stress). 6.5. Consensus Parameter Tuning [CONSENSUS_PARAMETERS] During Shadow simulation, we will determine reasonable default parameters for our consensus parameters for each algorithm. We will then re-run these tuning experiments on the live Tor network, as described in: https://trac.torproject.org/projects/tor/wiki/org/roadmaps/CoreTor/Performa… The following list is the complete set of network consensus parameters referenced in this proposal, sorted roughly in order of importance (most important to tune first): cc_alg: - Description: Specifies which congestion control algorithm clients should use, as an integer. - Range: [0,2] (0=fixed, 1=Westwood, 2=Vegas) - Default: 2 cwnd_recovery_m: - Description: Specifies how much to reduce the congestion window after a congestion signal, as a fraction of 100. - Range: [0, 100] - Default: 70 circwindow: - Description: Initial congestion window for legacy Tor clients - Range: [1, 1000] - Default: 1000 (reduced if legacy Tor clients compete unfairly) circwindow_cc: - Description: Initial congestion window for new congestion control Tor clients. - Range: [1, 1000] - Default: 10-100 rtt_thresh: - Description: Specifies the cutoff for BOOTLEG_RTT_TOR to deliver congestion signal, as fixed point representation divided by 1000. - Range: [1, 1000] - Default: 230 vegas_alpha vegas_beta vegas_gamma - Description: These parameters govern the number of cells that [TOR_VEGAS] can detect in queue before reacting. - Range: [1, 1000] - Defaults: 6,12,12 circwindow_inc: - Description: Specifies how many cells a SENDME acks - Range: [1, 5000] - Default: 100 min_queue_target: - Description: How long in milliseconds can a cell spend in a relay's queues before we declare its circuit congested? - Range: [1, 10000] - Default: 10 xoff_client xoff_mobile xoff_exit - Description: Specifies the stream queue size as a percentage of 'cwnd' at an endpoint before an XOFF is sent. - Range: [1, 100] - Default: 5 xon_client xon_mobile xon_exit - Description: Specifies the how many cells below xoff_* before an XON is sent from an endpoint. - Range: [1, 10000000] - Default: 10000 7. Protocol format specifications [PROTOCOL_SPEC] TODO: This section needs details once we close out other TODOs above. 7.1. Circuit window handshake format TODO: We need to specify a way to communicate the currently seen circwindow_inc consensus parameter to the other endpoint, due to consensus sync delay. Probably during the CREATE onionskin (and RELAY_COMMAND_EXTEND). TODO: We probably want stricter rules on the range of values for the per-circuit negotiation - something like it has to be between [circwindow_inc/2, 2*circwindow_inc]. That way, we can limit weird per-circuit values, but still allow us to change the consensus value in increments. 7.2. XON/XOFF relay cell formats TODO: We need to specify XON/XOFF for flow control. This should be simple. TODO: We should also allow it to carry stream data. 7.3. Onion Service formats TODO: We need to specify how to signal support for congestion control in an onion service, to both the intropoint and to clients. 7.4. Protocol Version format TODO: We need to pick a protover to signal Exit and Intropoint congestion control support. 7.5. SENDME relay cell format TODO: We need to specify how to add stream data to a SENDME as an optimization. 7.6. BACKWARD_ECN signal format TODO: We need to specify exactly which byte to flip in cells to signal congestion on a circuit. TODO: Black magic will allow us to send zero-filled BACKWARD_ECN cells in the *wrong* direction in a circuit, towards the Exit - ie with no crypto layers at all. If we enforce strict format and zero-filling of these cells at intermediate relays, we can avoid side channels there, too. (Such a hack allows us to send BACKWARD_ECN without any wait, if there are no relay cells that are available heading in the backward direction, towards the endpoint that caused congestion). 7.7. Extrainfo descriptor formats TODO: We will want to gather information on circuitmux and other relay queues, as well as XON/XOFF rates, and edge connection queue lengths at exits. 8. Security Analysis [SECURITY_ANALYSIS] The security risks of congestion control come in three forms: DoS attacks, fairness abuse, and side channel risk. 8.1. DoS Attacks (aka Adversarial Buffer Bloat) The most serious risk of eliminating our current window cap is that endpoints can abuse this situation to create huge queues and thus DoS Tor relays. This form of attack was already studied against the Tor network in the Sniper attack: https://www.freehaven.net/anonbib/cache/sniper14.pdf We had two fixes for this. First, we implemented a circuit-level OOM killer that closed circuits whose queues became too big, before the relay OOMed and crashed. Second, we implemented authenticated SENDMEs, so clients could not artificially increase their window sizes with honest exits: https://gitweb.torproject.org/torspec.git/tree/proposals/289-authenticated-… We can continue this kind of enforcement by having Exit relays ensure that clients are not transmitting SENDMEs too often, and do not appear to be inflating their send windows beyond what the Exit expects by calculating a similar receive window. Unfortunately, authenticated SENDMEs do *not* prevent the same attack from being done by rogue exits, or rogue onion services. For that, we rely solely on the circuit OOM killer. During our experimentation, we must ensure that the circuit OOM killer works properly to close circuits in these scenarios. But in any case, it is important to note that we are not any worse off with congestion control than we were before, with respect to these kinds of DoS attacks. In fact, the deployment of congestion control by honest clients should reduce queue use and overall memory use in relays, allowing them to be more resilient to OOM attacks than before. 8.2. Congestion Control Fairness Abuse (aka Cheating) On the Internet, significant research and engineering effort has been devoted to ensuring that congestion control algorithms are "fair" in that each connection receives equal throughput. This fairness is provided both via the congestion control algorithm, as well as via queue management algorithms at Internet routers. One of the most unfortunate early results was that TCP Vegas, despite being near-optimal at minimizing queue lengths at routers, was easily out-performed by more aggressive algorithms that tolerated larger queue delay (such as TCP Reno). Note that because the most common direction of traffic for Tor is from Exit to client, unless Exits are malicious, we do not need to worry about rogue algorithms as much, but we should still examine them in our experiments because of the possibility of malicious Exits, as well as malicious onion services. Queue management can help further mitigate this risk, too. When RTT is used as a congestion signal, our current Circuit-EWMA queue management algorithm is likely sufficient for this. Because Circuit-EWMA will add additional delay to loud circuits, "cheaters" who use alternate congestion control algorithms to inflate their congestion windows should end up with more RTT congestion signals than those who do not, and the Circuit-EWMA scheduler will also relay fewer of their cells per time interval. In this sense, we do not need to worry about fairness and cheating as a security property, but a lack of fairness in the congestion control algorithm *will* increase memory use in relays to queue these unfair/loud circuits, perhaps enough to trigger the OOM killer. So we should still be mindful of these properties in selecting our congestion control algorithm, to minimize relay memory use, if nothing else. These two properties (honest Exits and Circuit-EWMA) may even be enough to make it possible to use [TOR_VEGAS] even in the presence of other algorithms, which would be a huge win in terms of memory savings as well as vastly reduced queue delay. We must verify this experimentally, though. 8.3. Side Channel Risks Vastly reduced queue delay and predictable amounts of congestion on the Tor network may make certain forms of traffic analysis easier. Additionally, the ability to measure RTT and have it be stable due to minimal network congestion may make geographical inference attacks easier: https://www.freehaven.net/anonbib/cache/ccs07-latency-leak.pdf https://www.robgjansen.com/publications/howlow-pets2013.pdf It is an open question as to if these risks are serious enough to warrant eliminating the ability to measure RTT at the protocol level and abandoning it as a congestion signal, in favor of other approaches (which have their own side channel risks). It will be difficult to comprehensively eliminate RTT measurements, too. On the plus side, Conflux traffic splitting (which is made easy once congestion control is implemented) does show promise as providing defense against traffic analysis: https://www.comsys.rwth-aachen.de/fileadmin/papers/2019/2019-delacadena-spl… There is also literature on shaping circuit bandwidth to create a side channel. This can be done regardless of the use of congestion control, and is not an argument against using congestion control. In fact, the Backlit defense may be an argument in favor of endpoints monitoring circuit bandwidth and latency more closely, as a defense: https://www.freehaven.net/anonbib/cache/ndss09-rainbow.pdf https://www.freehaven.net/anonbib/cache/ndss11-swirl.pdf https://www.freehaven.net/anonbib/cache/acsac11-backlit.pdf Finally, recall that we are considering BACKWARD_ECN to use a circuit-level cell_t.command to signal congestion. This allows all relays in the path to signal congestion in under RTT/2 in either direction, and it can be flipped on existing relay cells already in transit, without introducing any overhead. However, because cell_t.command is visible and malleable to all relays, it can also be used as a side channel. So we must limit its use to a couple of cells per circuit, at most. https://blog.torproject.org/tor-security-advisory-relay-early-traffic-confi… 9. [CITATIONS] 1. Options for Congestion Control in Tor-Like Networks. https://lists.torproject.org/pipermail/tor-dev/2020-January/014140.html 2. Towards Congestion Control Deployment in Tor-like Networks. https://lists.torproject.org/pipermail/tor-dev/2020-June/014343.html 3. DefenestraTor: Throwing out Windows in Tor. https://www.cypherpunks.ca/~iang/pubs/defenestrator.pdf 4. TCP Westwood: Bandwidth Estimation for Enhanced Transport over Wireless Links http://nrlweb.cs.ucla.edu/nrlweb/publication/download/99/2001-mobicom-0.pdf 5. Performance Evaluation and Comparison of Westwood+, New Reno, and Vegas TCP Congestion Control http://cpham.perso.univ-pau.fr/TCP/ccr_v31.pdf 6. Linux 2.4 Implementation of Westwood+ TCP with rate-halving https://c3lab.poliba.it/images/d/d7/Westwood_linux.pdf 7. TCP Westwood http://intronetworks.cs.luc.edu/1/html/newtcps.html#tcp-westwood 8. TCP Vegas: New Techniques for Congestion Detection and Avoidance http://pages.cs.wisc.edu/~akella/CS740/F08/740-Papers/BOP94.pdf 9. Understanding TCP Vegas: A Duality Model ftp://ftp.cs.princeton.edu/techreports/2000/628.pdf 10. TCP Vegas http://intronetworks.cs.luc.edu/1/html/newtcps.html#tcp-vegas 11. Controlling Queue Delay https://queue.acm.org/detail.cfm?id=2209336 12. Controlled Delay Active Queue Management https://tools.ietf.org/html/rfc8289 13. How Much Anonymity does Network Latency Leak? https://www.freehaven.net/anonbib/cache/ccs07-latency-leak.pdf 14. How Low Can You Go: Balancing Performance with Anonymity in Tor https://www.robgjansen.com/publications/howlow-pets2013.pdf 15. POSTER: Traffic Splitting to Counter Website Fingerprinting https://www.comsys.rwth-aachen.de/fileadmin/papers/2019/2019-delacadena-spl… 16. RAINBOW: A Robust And Invisible Non-Blind Watermark for Network Flows https://www.freehaven.net/anonbib/cache/ndss09-rainbow.pdf 17. SWIRL: A Scalable Watermark to Detect Correlated Network Flows https://www.freehaven.net/anonbib/cache/ndss11-swirl.pdf 18. Exposing Invisible Timing-based Traffic Watermarks with BACKLIT https://www.freehaven.net/anonbib/cache/acsac11-backlit.pdf 19. The Sniper Attack: Anonymously Deanonymizing and Disabling the Tor Network https://www.freehaven.net/anonbib/cache/sniper14.pdf 20. Authenticating sendme cells to mitigate bandwidth attacks https://gitweb.torproject.org/torspec.git/tree/proposals/289-authenticated-… 21. Tor security advisory: "relay early" traffic confirmation attack https://blog.torproject.org/tor-security-advisory-relay-early-traffic-confi… 22. The Path Less Travelled: Overcoming Tor’s Bottlenecks with Traffic Splitting https://www.cypherpunks.ca/~iang/pubs/conflux-pets.pdf 23. Circuit Padding Developer Documentation https://github.com/torproject/tor/blob/master/doc/HACKING/CircuitPaddingDev… 24. Plans for Tor Live Network Performance Experiments https://trac.torproject.org/projects/tor/wiki/org/roadmaps/CoreTor/Performa… 25. Tor Performance Metrics for Live Network Tuning https://trac.torproject.org/projects/tor/wiki/org/roadmaps/CoreTor/Performa…

1 0