commit 9f39565e61b65bb5f65d37ed779d17fe1c596179 Author: David Goulet dgoulet@torproject.org Date: Wed Feb 6 17:24:01 2019 -0500
Proposal 329: Conflux traffic splitting --- proposals/329-traffic-splitting.txt | 843 ++++++++++++++++++++++++++++++++++++ 1 file changed, 843 insertions(+)
diff --git a/proposals/329-traffic-splitting.txt b/proposals/329-traffic-splitting.txt new file mode 100644 index 0000000..746c6c4 --- /dev/null +++ b/proposals/329-traffic-splitting.txt @@ -0,0 +1,843 @@ +Filename: 329-traffic-splitting.txt +Title: Overcoming Tor's Bottlenecks with Traffic Splitting +Author: David Goulet, Mike Perry +Created: 2020-11-25 +Status: Draft + +0. Status + + This proposal describes the Conflux [CONFLUX] system developed by Mashael + AlSabah, Kevin Bauer, Tariq Elahi, and Ian Goldberg. It aims at improving + Tor client network performance by dynamically splitting traffic between two + circuits. + + +1. Overview + +1.1. Multipath TCP Design Space + + In order to understand our improvements to Conflux, it is important to + properly conceptualize what is involved in the design of multipath + algorithms in general. + + The design space is broken into two orthogonal parts: congestion + control algorithms that apply to each path, and traffic scheduling + algorithms that decide when to send packets to send on each path. + + MPTCP specifies 'coupled' congestion control (see [COUPLED]). Coupled + congestion control updates single-path congestion control algorithms to + account for shared bottlenecks between the paths, so that the combined + congestion control algorithms do not overwhelm any bottlenecks that + happen to be shared between the multiple paths. Various ways of + accomplishing this have been proposed and implemented in the Linux kernel. + + Because Tor's congestion control only concerns itself with bottnecks in Tor + relay queues, and not with any other bottlenecks (such as intermediate + Internet routers), we can avoid this complexity merely by specifying that + any paths that are constructed should not share any relays. In this way, we + can proceed to use the exact same congestion control as specified in Proposal + 324, for each path. + + For this reason, this proposal will focus on the traffic scheduling + algorithms, rather than coupling. We propose three candidate algorithms + that have been studied in the literature, and will compare their + performance using simulation and consensus parameters. + +1.2. Divergence from the initial Conflux design + + The initial [CONFLUX] paper doesn't provide any indications on how to handle + the size of out-of-order cell queue, which we consider a potential dangerous + memory DoS vector (see [MEMORY_DOS]). It also used RTT as the sole heuristic + for selecting which circuit to send on, which may vary depending on the + geographical locations of the participant relays, without considering their + actual available circuit capacity (which will be available to us via Proposal + 324). Additionally, since the publication of [CONFLUX], more modern + packet scheduling algorithms have been developed, which aim to reduce + out-of-order queue size. + + We propose mitigations for these issues using modern scheduling algorithms, + as well as implementations options for avoiding the out-of-order queue at + Exit relays. Additionally, we consider resumption, side channel, and traffic + analysis risks and benefits in [RESUMPTION], [SIDE_CHANNELS] and + [TRAFFIC_ANALYSIS]. + + +2. Design + + The following section describes the Conflux design. Each sub-section is a + building block to the multipath design that Conflux proposes. + + The circuit construction is as follow: + + Primary Circuit (lower RTT) + +-------+ +--------+ + |Guard 1|----->|Middle 1|----------+ + +---^---+ +--------+ | + +-----+ | +--v---+ + | OP +------+ | Exit |--> ... + +-----+ | +--^---+ + +---v---+ +--------+ | + |Guard 2|----->|Middle 2|----------+ + +-------+ +--------+ + Secondary Circuit (higher RTT) + + Both circuits are built using current Tor path selection, however they + SHOULD NOT share the same Guard relay, or middle relay. By avoiding + using the same relays in these positions in the path, we ensure + additional path capacity, and eliminate the need to use more complicated + 'coupled' congestion control algorithms from the MPTCP literature[COUPLED]. + This both simplifies design, and improves performance. + + Then, the OP needs to link the two circuits together, as described in + [LINKING_CIRCUITS], [LINKING_EXIT], and [LINKING_SERVICE]. + + For ease of explanation, the primary circuit is the circuit with lower RTT, + and the secondary circuit is the circuit with higher RTT. Initial RTT + is measured during circuit linking, as described in [LINKING_CIRCUITS]. + RTT is continually measured using SENDME timing, as in Proposal 324. + This means that during use, the primary circuit and secondary circuit may + switch roles, depending on unrelated network congestion caused by other + Tor clients. + + We also support linking onion service circuits together. In this case, + only two rendezvous circuits are linked. Each of these RP circuits will be + constructed separately, and then linked. However, the same path constraints + apply to each half of the circuits (no shared relays between the legs). + Should, by chance, the service and the client sides end up sharing some + relays, this is not catastrophic. Multipath TCP researchers we have + consulted believe Tor's congestion control from Proposal 324 to be + sufficient in this rare case. + + Only two circuits SHOULD be linked together. However, implementations + SHOULD make it easy for researchers to *test* more than two paths, as this + has been shown to assist in traffic analysis resistance[WTF_SPLIT]. At + minimum, this means not hardcoding only two circuits in the implementation. + + If the number of circuits exceeds the current number of guard relays, + guard relays MAY be re-used, but implementations SHOULD use the same + number of Guards as paths. + + Linked circuits MUST NOT be extended further once linked (ie: + 'cannibalization' is not supported). + +2.1. Advertising support for conflux + + We propose a new protocol version in order to advertise support for + circuit linking on the relay side: + + "Relay=4" -- Relay supports an 2 byte sequence number in a RELAY cell + header used for multipath circuit which are linked with the + new RELAY_CIRCUIT_LINK relay cell command. + + XXX: Advertise this in onion service descriptor. + XXX: Onion service descriptor can advertise more than two circuits? + + The next section describes how the circuits are linked together. + +2.2. Linking circuits [LINKING_CIRCUITS] + + To link circuits, we propose new relay commands that are sent on both + circuits, as well as a response to confirm the join, and an ack of this + response. These commands create a 3way handshake, which allows each + endpoint to measure the initial RTT of each leg upon link, without + needing to wait for any data. + + All three stages of this handshake are sent on *each* circuit leg to be + linked. + + To save round trips, these cells SHOULD be combined with the initial + RELAY_BEGIN cell on the faster circuit leg, using Proposal 325. See + [LINKING_EXIT] and [LINKING_SERVICE] for more details on setup in each case. + + There are other ways to do this linking that we have considered, but they + seem not to be significantly better than this method, especially since we + can use Proposal 325 to eliminate the RTT cost of this setup before sending + data. For those other ideas, see [ALTERNATIVE_LINKING] and + [ALTERNATIVE_RTT], in the appendix. + + The first two parts of the handshake establish the link, and enable + resumption: + + 16 -- RELAY_CIRCUIT_LINK + + Sent from the OP to the exit/service in order to link + circuits together at the end point. + + 17 -- RELAY_CIRCUIT_LINKED + + Sent from the exit/service to the OP, to confirm the circuits + were linked. + + These cells have the following contents: + + VERSION [1 byte] + PAYLOAD [variable, up to end of relay payload] + + The VERSION tells us which circuit linking mechanism to use. At this point + in time, only 0x01 is recognized and is the one described by the Conflux + design. + + For version 0x01, the PAYLOAD contains: + + NONCE [32 bytes] + LAST_SEQNO_SENT [8 bytes] + LAST_SEQNO_RECV [8 bytes] + + XXX: Should we let endpoints specify their preferred [SCHEDULING] alg + here, to override consensus params? This has benefits: eg low-memory + mobile clients can ask for an alg that is better for their reorder + queues. But it also has complexity risk, if the other endpoint does + not want to support it, because of its own memory issues. + + The NONCE contains a random 256-bit secret, used to associate the two + circuits together. The nonce must not be shared outside of the circuit + transmission, or data may be injected into TCP streams. This means it + MUST NOT be logged to disk. + + The two sequence number fields are 0 upon initial link, but non-zero in the + case of a resumption attempt (See [RESUMPTION]). + + If either circuit does not receive a RELAY_CIRCUIT_LINKED response, both + circuits MUST be closed. + + The third stage of the handshake exists to help the exit/service measure + initial RTT, for use in [SCHEDULING]: + + 18 -- RELAY_CIRCUIT_LINKED_RTT_ACK + + Sent from the OP to the exit/service, to provide initial RTT + measurement for the exit/service. + + For timeout of the handshake, clients should use the normal SOCKS/stream + timeout already in use for RELAY_BEGIN. + + These three relay commands (RELAY_CIRCUIT_LINK, RELAY_CIRCUIT_LINKED, + and RELAY_CIRCUIT_LINKED_ACK) are send on *each* leg, to allow each + endpoint to measure the initial RTT of each leg. + +2.2. Linking Circuits from OP to Exit [LINKING_EXIT] + + To link exit circuits, two circuits to the same exit are built. The + client records the circuit build time of each. + + If the circuits are being built on-demand, for immediate use, the + circuit with the lower build time SHOULD use Proposal 325 to append its + first RELAY cell to the RELAY_COMMAND_LINK, on the circuit with the + lower circuit build time. The exit MUST respond on this same leg. + After that, actual RTT measurements MUST be used to determine + future transmissions, as specified in [SCHEDULING]. + + The RTT times between RELAY_COMMAND_LINK and RELAY_COMMAND_LINKED are + measured by the client, to determine each circuit RTT to determine + primary vs secondary circuit use, and for packet scheduling. Similarly, + the exit measures the RTT times between RELAY_COMMAND_LINKED and + RELAY_COMMAND_LINKED_ACK, for the same purpose. + +2.3. Linking circuits to an onion service [LINKING_SERVICE] + + For onion services, we will only concern ourselves with linking + rendezvous circuits. + + To join rendezvous circuits, clients make two introduce requests to a + service's intropoint, causing it to create two rendezvous circuits, to + meet the client at two separate rendezvous points. These introduce + requests MUST be sent to the same intropoint (due to potential use of + onionbalance), and SHOULD be sent back-to-back on the same intro + circuit. They MAY be combined with Proposal 325. + + The first rendezvous circuit to get joined SHOULD use Proposal 325 + to append the RELAY_BEGIN command, and the service MUST answer + on this circuit, until RTT can be measured. + + Once both circuits are linked and RTT is measured, packet scheduling + should be used, as per [SCHEDULING]. + +2.4. Congestion Control Application [CONGESTION_CONTROL] + + The SENDMEs for congestion control are performed per-leg. As data arrives, + regardless of its ordering, it is counted towards SENDME delivery. In this + way, 'cwnd - package_window' of each leg always reflects the available + data to send on each leg. This is important for [SCHEDULING]. + + The Congestion control Stream XON/XOFF can be sent on either leg, and + applies to the stream's transmission on both legs. + +2.5. Sequencing [SEQUENCING] + + With multiple paths for data, the problem of data re-ordering appears. In + other words, cells can arrive out of order from the two circuits where cell + N + 1 arrives before the cell N. + + Handling this reordering operates after congestion control for each circuit + leg, but before relay cell command processing or stream data delivery. + + For the receiver to be able to reorder the receiving cells, a sequencing + scheme needs to be implemented. However, because Tor does not drop or + reorder packets inside of a circuit, this sequence number can be very + small. It only has to signal that a cell comes after those arriving + on another circuit. + + To achieve this, we add a small sequence number to the common relay + header for all relay cells on linked circuits. This sequence number + is meant to signal the number of cells sent on the *other* leg, so + that each endpoint knows how many cells are still in-flight on + another leg. It is different from the absolute sequence number used + in [LINKING_CIRCUITS] and [RESUMPTION], but can be derived from that + number, using relative arithmetic. + + Relay command [1 byte] + Recognized [2 bytes] + StreamID [2 bytes] + Digest [4 bytes] + Length [2 bytes] + > LongSeq [1 bit] # If this bit is set, use 31 bits for Seq + > Sequencing [7 or 31 bits] + Data [Remainder] + + The sequence number is only set for the first cell after the endpoint + switches legs. In this case, LongSeq is set to 1, and the Sequencing + field is 31 more bits. Otherwise it is a 1 byte 0 value. + + These fields MUST be present on ALL end-to-end relay cells on each leg + that come from the endpoint, following a RELAY_CIRCUIT_LINK command. + + They are absent on 'leaky pipe' RELAY_COMMAND_DROP and + RELAY_COMMAND_PADDING_NEGOTIATED cells that come from middle relays, + as opposed to the endpoint, to support padding. + + When an endpoint switches legs, on the first cell in a new leg, + LongSeq is set to 1, and the following 31 bits represent the *total* + number of cells sent on the *other* leg, before the switch. The receiver + must wait for that number of cells to arrive from the previous leg + before delivering that cell. + + XXX: In the rare event that we send more than 2^31 cells (~1TB) on a + single leg, do we force a switch of legs, or expand the field further? + + An alternative method of sequencing, that assumes that the endpoint + knows when it is going to switch, the cell before it switches, is + specified in [ALTERNATIVE_SEQUENCING]. Note that that method requires + only 1 byte for sequence number and switch signaling, but requires that + the sender know that it is planning to switch, the cell before it switches. + (This is possible with [BLEST_TOR], but [LOWRTT_TOR] can switch based on + RTT change, so it may be one cell late in that case). + +2.6. Resumption [RESUMPTION] + + In the event that a circuit leg is destroyed, they MAY be resumed. + + Resumption is achieved by re-using the NONCE and method to the same endpoint + (either [LINKING_EXIT] or [LINKING_SERVICE]). The resumed path need not + use the same middle and guard relays, but should not share any relays + with any existing legs(s). + + To provide resumption, endpoints store an absolute 64bit cell counter of + the last cell they have sent on a conflux pair (their LAST_SEQNO_SENT), + as well the last sequence number they have delivered in-order to edge + connections corresponding to a conflux pair (their LAST_SEQNO_RECV). + Additionally, endpoints MAY store the entire contents of unacked + inflight cells (ie the 'package_window' from proposal 324), for each + leg, along with information corresponding to those cells' absolute + sequence numbers. + + These 64 bit absolute counters can wrap without issue, as congestion + windows will never grow to 2^64 cells until well past the Singularity. + However, it is possible that extremely long, bulk circuits could + exceed 2^64 total sent or received cells, so endpoints SHOULD handle + wrapped sequence numbers for purposes of computing retransmit + information. (But even this case is unlikely to happen within the next + decade or so). + + Upon resumption, the LAST_SEQNO_SENT and LAST_SEQNO_RECV fields are used to + convey the sequence numbers of the last cell the relay sent and received on + that leg. The other endpoint can use these sequence numbers to determine if + it received the in-flight data or not, or sent more data since that point, + up to and including this absolute sequence number. If LAST_SEQNO_SENT + has not been received, the endpoint MAY transmit the missing data, if it + still has it buffered. + + Because both endpoints get information about the other side's absolute + SENT sequence number, they will know exactly how many re-transmitted + packets to expect, should the circuit stay open. Re-transmitters + should not re-increment their absolute sent fields while re-transmitting. + + If it does not have this missing data due to memory pressure, that endpoint + should destroy *both* legs, as this represents unrecoverable data loss. + + Otherwise, the new circuit can be re-joined, and its RTT can be compared + to the remaining circuit to determine if the new leg is primary or + secondary. + + It is even possible to resume conflux circuits where both legs have + been collapsed using this scheme, if endpoints continue to buffer their + unacked package_window data for some time after this close. However, + see [TRAFFIC_ANALYSIS] for more details on the full scope of this + issue. + + If endpoints are buffering package_window data, such data should be + given priority to be freed in any oomkiller invocation. See + [MEMORY_DOS] for more oomkiller information. + + +3. Traffic Scheduling [SCHEDULING] + + In order to load balance the traffic between the two circuits, the original + conflux paper used only RTT. However, with Proposal 324, we will have + accurate information on the instantaneous available bandwidth of each + circuit leg, as 'cwnd - package_window' (see Section 3 of Proposal 324). + + Some additional RTT optimizations are also useful, to improve + responsiveness and minimize out-of-order queue sizes. + + We specify two traffic schedulers from the multipath literature and adapt + them to Tor: [LOWRTT_TOR] and [BLEST_TOR]. [LOWRTT_TOR] also has three + variants, with different trade offs. + + However, see the [TRAFFIC_ANALYSIS] sections of this proposal for important + details on how this selection can be changed, to reduce website traffic + fingerprinting. + +3.1. LowRTT Scheduling [LOWRTT_TOR] + + This scheduling algorithm is based on the original [CONFLUX] paper, with + ideas from [MPTCP]'s minRTT/LowRTT scheduler. + + In this algorithm, endpoints send cells on the circuit with lower RTT + (primary circuit). This continues while the congestion window on the + circuit has available room: ie whenever cwnd - package_window > 0. + + Whenever the primary circuit's congestion window becomes full, the + secondary circuit is used. We stop reading on the send window source + (edge connection) when both congestion windows become full. + + In this way, unlike original conflux, we switch to the secondary circuit + without causing congestion on the primary circuit. This improves both + load times, and overall throughput. + + This behavior matches minRTT from [MPTCP], sometimes called LowRTT. + + It may be better to stop reading on the edge connection when the primary + congestion window becomes full, rather than switch to the secondary + circuit as soon as the primary congestion window becomes full. (Ie: only + switch if the RTTs themselves change which circuit is primary). This is + what was done in the original Conflux paper. This behavior effectively + causes us to optimize for responsiveness and congestion avoidance, rather + than throughput. For evaluation, we should control this switching behavior + with a consensus parameter (see [CONSENSUS_PARAMETERS]). + + Because of potential side channel risk (see [SIDE_CHANNELS]), a third + variant of this algorithm, where the primary circuit is chosen during the + [LINKING_CIRCUITS] handshake and never changed, should also be possible + to control via consensus parameter. + +3.2. BLEST Scheduling [BLEST_TOR] + + [BLEST] attempts to predict the availability of the primary circuit, and + use this information to reorder transmitted data, to minimize head-of-line + blocking in the recipient (and thus minimize out-of-order queues there). + + BLEST_TOR uses the primary circuit until the congestion window is full. + Then, it uses the relative RTT times of the two circuits to calculate + how much data can be sent on the secondary circuit faster than if we + just waited for the primary circuit to become available. + + This is achieved by computing two variables at the sender: + + rtts = secondary.currRTT / primary.currRTT + primary_limit = primary.cwnd + (rtts-1)/2)*rtts + + Note: This (rtts-1)/2 factor represents anticipated congestion window + growth over this period.. it may be different for Tor, depending on CC alg. + + If primary_limit < secondary.cwnd - (secondary.package_window + 1), then + there is enough space on the secondary circuit to send data faster than we + could than waiting for the primary circuit. + + XXX: Note that BLEST uses total_send_window where we use secondary.cwnd in + this check. total_send_window is min(recv_win, CWND). But since Tor does + not use receive windows and intead uses stream XON/XOFF, we only use CWND. There + is some concern this may alter BLEST's buffer minimization properties, + but since receive window should only matter if the application is slower + than Tor, and XON/XOFF should cover that case, hopefully this is fine. + + Otherwise, if the primary_limit condition is not hit, cease reading + on source edge connections until SENDME acks come back. + + Here is the pseudocode for this: + + while source.has_data_to_send(): + if primary.cwnd > primary.package_window: + primary.send(source.get_packet()) + continue + + rtts = secondary.currRTT / primary.currRTT + primary_limit = (primary.cwnd + (rtts-1)/2)*rtts + + if primary_limit < secondary.cwnd - (secondary.package_window+1): + secondary.send(source.get_packet()) + else: + break # done for now, wait for an ACK to free up CWND space and restart + + Note that BLEST also has a parameter lambda that is updated whenever HoL + blocking occurs. Because it is expensive and takes significant time to + signal this over Tor, we omit this. + XXX: See [REORDER_SIGNALING] section if we want this lambda feedback. + +3.3. Reorder queue signaling [REORDER_SIGNALING] + + Reordering should be fairly simple task. By following using the sequence + number field in [SEQUENCING], endpoints can know how many cells are still + in flight on the other leg. + + To reorder them properly, a buffer of out of order cells needs to be kept. + On the Exit side, this can quickly become overwhelming considering ten of + thousands of possible circuits can be held open leading to gigabytes of + memory being used. There is a clear potential memory DoS vector which means + that a tor implementation should be able to limit the size of those queues. + + Luckily, [BLEST_TOR] and the form of [LOWRTT_TOR] that only uses the + primary circuit will minimize or eliminate this out-of-order buffer. + + XXX: The remainder of this section may be over-complicating things... We + only need these concepts if we want to use BLEST's lambda feedback. + + The default for this queue size is governed by the 'cflx_reorder_client' + and 'cflx_reorder_srv' consensus parameters (see [CONSENSUS_PARAMS]). + 'cflx_reorder_srv' applies to Exits and onion services. Both parameters + can be overridden by Torrc, to larger or smaller than the consensus + parameter. (Low memory clients may want to lower it; SecureDrop onion + services or other high-upload services may want to raise it). + + When the reorder queue hits this size, a RELAY_CONFLUX_XOFF is sent down + the circuit leg that has data waiting in the queue and use of that leg must + cease, until it drains to half of this value, at which point an + RELAY_CONFLUX_XON is sent. Note that this is different than the stream + XON/XOFF from Proposal 324. + + XXX: [BLEST] actually does not cease use of a path in this case, but + instead uses this signal to adjust the lambda parameter, which biases + traffic away from that leg. + + +4. Security Considerations + +4.1. Memory Denial of Service [MEMORY_DOS] + + Both reorder queues and retransmit buffers inherently represent a memory + denial of service condition. + + For [RESUMPTION] retransmit buffers, endpoints that support this + feature SHOULD free retransmit information as soon as they get close + to memory pressure. This prevents resumption while data is in flight, + but will not otherwise harm operation. + + For reorder buffers, adversaries can potentially impact this at any + point, but most obviously and most severely from the client position. + + In particular, clients can lie about sequence numbers, sending cells + with sequence numbers such that the next expected sequence number + is never sent. They can do this repeatedly on many circuits, to exhaust + memory at exits. + + One option is to only allow actual traffic splitting in the downstream + direction, towards clients, and always use the primary circuit for + everything in the upstream direction. However, the ability to support + conflux from the client to the exit shows promise against traffic + analysis (see [WTF_SPLIT]). + + The other option is to use [BLEST_TOR] from clients to exits, as it has + predictable interleaved cell scheduling, and minimizes reorder queues + at exits. If the ratios prescribed by that algorithm are not followed + within some bounds, the other endpoint can close both circuits, and + free the queue memory. + + This still leaves the possibility that intermediate relays may block + a leg, allowing cells to traverse only one leg, thus still accumulating + at the reorder queue. Clients can also spoof sequence numbers similarly, + to make it appear that they are following [BLEST_TOR], without + actually sending any data on one of the legs. + + To handle either of these cases, when a relay is under memory pressure, + the circuit OOM killer SHOULD free and close circuits with the oldest + reorder queue data, first. This heuristic was shown to be best during + the [SNIPER] attack OOM killer iteration cycle. + +4.2. Side Channels [SIDE_CHANNELS] + + Two potential side channels may be introduced by the use of Conflux: + 1. RTT leg-use bias by altering SENDME latency + 2. Location info leaks through the use of both leg's latencies + + For RTT and leg-use bias, Guard relays could delay legs to introduce + a pattern into the delivery of cells at the exit relay, by varying the + latency of SENDME cells (every 100th cell) to change the distribution + of traffic to send information. This attack could be performed in either + direction of traffic, to bias traffic load off of a particular Guard. + If an adversary controls both Guards, it could in theory send a binary + signal more easily, by alternating delays on each. + + However, this risk weighs against the potential benefits against traffic + fingerprinting, as per [WTF_SPLIT]. Additionally, even ignoring + cryptographic tagging attacks, this side channel provides significantly + lower information over time than inter-packet-delay based side channels + that are already available to Guards and routers along the path to the + Guard. + + Tor currently provides no defenses against already existing + single-circuit delay-based side channels, though both circuit padding + and [BACKLIT] are potential options it could conceivably deploy. The + [BACKLIT] paper also has an excellent review of the various methods + that have been studied for such single circuit side channels, and + the [BACKLIT] style RTT monitoring could be used to protect against + these conflux side channels as well. Circuit padding can also help + to obscure which cells are SENDMEs, since circuit padding is not + counted towards SENDME totals. + + The second class of side channel is where the Exit relay may be able + to use the two legs to further infer more information about client + location. See [LATENCY_LEAK] for more details. It is unclear at + this time how much more severe this is for two paths than just one. + + We should preserve the ability to disable conflux to and from Exit + relays, should these side channels prove more severe, or should + it prove possible to mitigate single-circuit side channels, but + not conflux side channels. + + In all cases, all of these side channels appear less severe for onion + service traffic, due to the higher path variability due to relay + selection, as well as the end-to-end nature of conflux in that case. + This indicates that our ability to enable/disable conflux for services + should be separate from Exits. + +4.3. Traffic analysis [TRAFFIC_ANALYSIS] + + Even though conflux shows benefits against traffic analysis in [WTF_SPLIT], + these gains may be moot if the adversary is able to perform packet counting + and timing analysis at guards to guess which specific circuits are linked. + In particular, the 3 way handshake in [LINKING_CIRCUITS] may be quite + noticeable. + + As one countermeasure, it may be possible to eliminate the third leg + (RELAY_CIRCUIT_LINKED_ACK) by computing the exit/service RTT via measuring + the time between CREATED/REND_JOINED and RELAY_CIRCUIT_LINK, but this + will introduce cross-component complexity into Tor's protocol that + could quickly become unwieldy and fragile. + + Additionally, the conflux handshake may make onion services stand out + more, regardless of the number of stages in the handshake. For this + reason, it may be more wise to simply address these issues with circuit + padding machines during circuit setup (see padding-spec.txt). + + Additional traffic analysis considerations arise when combining conflux + with padding, for purposes of mitigating traffic fingerprinting. For this, + it seems wise to treat the packet schedulers as another piece of a combined + optimization problem in tandem with optimizing padding machines, perhaps + introducing randomness or fudge factors their scheduling, as a parameterized + distribution. For details, see + https://github.com/torproject/tor/blob/master/doc/HACKING/CircuitPaddingDeve... + + Finally, conflux may exacerbate forms of confirmation-based traffic + analysis that close circuits to determine concretely if they were in use, + since closing either leg might cause resumption to fail. TCP RST + injection can perform this attack on the side, without surveillance + capability. [RESUMPTION] with buffering of the inflight unacked + package_window data, for retransmit, is a partial mitigation, if + endpoints buffer this data for retransmission for a brief time even + if both legs close. This seems more feasible for onion services, + which are more vulnerable to this attack. However, if the adversary + controls the client, they will notice the resumption re-link, and + still obtain confirmation that way. + + It seems the only way to fully mitigate these kinds of attacks is with + the Snowflake pluggable transport, which provides its own resumption + and retransmit behavior. Additionally, Snowflake's use of UDP DTLS also + protects against TCP RST injection, which we suspect to be the main + vector for such attacks. + + In the future, a DTLS or QUIC transport for Tor such as masque could + provide similar RST injection resistance, and resumption at + Guard/Bridge nodes, as well. + + +5. System Interactions + + - congestion control + - EWMA and KIST + - CBT and number of guards + - Onion service circ obfuscation + - Future UDP (it may increase the need for UDP to buffer before dropping) + - Padding (no sequence numbers on padding cells, as per [SEQUENCING]) + - Also, any padding machines may need re-tuning + - No 'cannibalization' of linked circuits + + +6. Consensus and Torrc Parameters [CONSENSUS] + + - conflux_circs + - Number of conflux circuits + + - conflux_sched_exits, conflux_sched_clients, conflux_sched_service + - Three forms of LOWRTT_TOR, and BLEST_TOR + + - ConfluxOnionService + - ConfluxOnionCircs + + +7. Tuning Experiments [EXPERIMENTS] + + - conflux_sched & conflux_exits + - Exit reorder queue size + - Responsiveness vs throughput tradeoff? + - Congestion control + - EWMA and KIST + - num guards & conflux_circs + + +Appended A [ALTERNATIVES] + +A.1 BEGIN/END sequencing [ALTERNATIVE_SEQUENCING] + + In this method of signaling, we increment the sequence number by 1 + only when we switch legs, and use BEGIN/END "bookends" to know that + all data on a leg has been received. + + To achieve this, we add a small sequence number to the common relay + header for all relay cells on linked circuits, as well as a field to + signal the beginning of a sequence, intermediate data, and the end + of a sequence. + + Relay command [1 byte] + Recognized [2 bytes] + StreamID [2 bytes] + Digest [4 bytes] + Length [2 bytes] + > Switching [2 bits] # 01 = BEGIN, 00 = CONTINUE, 10 = END + > Sequencing [6 bits] + Data [PAYLOAD_LEN - 12 - Length bytes] + + These fields MUST be present on ALL end-to-end relay cells on each leg + that come from the endpoint, following a RELAY_CIRCUIT_LINK command. + + They are absent on 'leaky pipe' RELAY_COMMAND_DROP and + RELAY_COMMAND_PADDING_NEGOTIATED cells that come from middle relays, + as opposed to the endpoint, to support padding. + + Sequence numbers are incremented by one when an endpoint switches legs + to transmit a cell. This number will wrap; implementations should treat + 0 as the next sequence after 2^6-1. Because we do not expect to support + significantly more than 2 legs, and much fewer than 63, this is not an + issue. + + The first cell on a new circuit MUST use the BEGIN code for switching. + Cells are delivered from that circuit until an END switching signal is + received, even if cells arrive first on another circuit with the next + sequence number before and END switching field. Recipients MUST only + deliver cells with a BEGIN, if their Sequencing number is one more than + the last END. + +A.2 Alternative Link Handshake [ALTERNATIVE_LINKING] + + The circuit linking in [LINKING_CIRCUITS] could be done as encrypted + ntor onionskin extension fields, similar to those used by v3 onions. + + This approach has at least four problems: + i). For onion services, since the onionskins traverse the intro circuit + and then return on the rend circuit, this handshake cannot measure + RTT there. + ii). Since these onionskins are larger, and have no PFS, an adversary + at the middle relay knows that the onionskin is for linking, and + can potentially try to obtain the onionskin key for attacks on + the link. + iii). It makes linking circuits more fragile, since they could timeout + due to CBT, or other issues during construction. + iv). The overhead in processing this onionskin through onionskin queues + adds additional time for linking, even in the Exit case, making + that RTT potentially noisy. + + Additionally, it is not clear that this approach actually saves us + anything in terms of setup time, because we can optimize away the + linking phase using Proposal 325, to combine initial RELAY_BEGIN cells + with RELAY_CIRCUIT_LINK. + +A.3. Alternative RTT measurement [ALTERNATIVE_RTT] + + Instead of measuring RTTs during [LINKING_CIRCUITS], we could create + PING/PONG cells, whose sole purpose is to allow endpoints to measure + RTT. + + This was rejected for several reasons. First, during circuit use, we + already have SENDMEs to measure RTT. Every 100 cells (or + 'circwindow_inc' from Proposal 324), we are able to re-measure RTT based + on the time between that Nth cell and the SENDME ack. So we only need + PING/PONG to measure initial circuit RTT. + + If we were able to use onionskins, as per [ALTERNATIVE_LINKING] above, + we might be able to specify a PING/PONG/PING handshake solely for + measuring initial RTT, especially for onion service circuits. + + The reason for not making a dedicated PING/PONG for this purpose is that + it is context-free. Even if we were able to use onionskins for linking + and resumption, to avoid additional data in handshake that just measures + RTT, we would have to enforce that this PING/PONG/PING only follows the + exact form needed by this proposal, at the expected time, and at no + other points. + + If we do not enforce this specific use of PING/PONG/PING, it becomes + another potential side channel, for use in attacks such as [DROPMARK]. + + In general, Tor is planning to remove current forms of context-free and + semantic-free cells from its protocol: + https://gitlab.torproject.org/tpo/core/torspec/-/issues/39 + + We should not add more. + + +Appendix B: Acknowledgments + + Thanks to Per Hurtig for helping us with the framing of the MPTCP + problem space. + + Thanks to Simone Ferlin for clarifications on the [BLEST] + paper, and for pointing us at the Linux kernel implementation. + + Extreme thanks goes again to Toke Høiland-Jørgensen, who helped + immensely towards our understanding of how the BLEST condition relates + to edge connection pushback, and for clearing up many other + misconceptions we had. + + Finally, thanks to Mashael AlSabah, Kevin Bauer, Tariq Elahi, and Ian + Goldberg, for the original [CONFLUX] paper! + + +References: + +[CONFLUX] + https://freehaven.net/anonbib/papers/pets2013/paper_65.pdf + +[BLEST] + https://olivier.mehani.name/publications/2016ferlin_blest_blocking_estimatio... + https://opus.lib.uts.edu.au/bitstream/10453/140571/2/08636963.pdf + https://github.com/multipath-tcp/mptcp/blob/mptcp_v0.95/net/mptcp/mptcp_bles... + +[WTF_SPLIT] + https://www.comsys.rwth-aachen.de/fileadmin/papers/2020/2020-delacadena-traf... + +[COUPLED] + https://datatracker.ietf.org/doc/html/rfc6356 + https://www.researchgate.net/profile/Xiaoming_Fu2/publication/230888515_Dela... + http://staff.ustc.edu.cn/~kpxue/paper/ToN-wwj-2020.04.pdf + https://www.thinkmind.org/articles/icn_2019_2_10_30024.pdf + https://arxiv.org/pdf/1308.3119.pdf + +[BACKLIT] + https://www.freehaven.net/anonbib/cache/acsac11-backlit.pdf + +[LATENCY_LEAK] + https://www.freehaven.net/anonbib/cache/ccs07-latency-leak.pdf + https://www.robgjansen.com/publications/howlow-pets2013.pdf + +[SNIPER] + https://www.freehaven.net/anonbib/cache/sniper14.pdf + +[DROPMARK] + https://www.freehaven.net/anonbib/cache/sniper14.pdf