# Towards Side Channel Analysis of Datagram Tor vs Current Tor

Version 0.6, 27 Nov 2018

by Nick Mathewson and Mike Perry

## Disclaimers

This whitepaper assumes that you know how Tor works.

There are probably some very good references here that we didn't remember to cite.

## Introduction

Tor's current design requires that its data cells be transmitted from one end of a circuit to the other using a reliable, in-order delivery mechanism. To meet this requirement, Tor relays need to buffer cells--spending resources, hurting performance, and risking susceptibility to out-of-memory attacks.

In order to improve Tor's performance and resilience, researchers have made several proposals for ways to relax the requirement for reliable in-order delivery. In general, these "datagram-based" proposals would allow relays to drop or reorder cells as needed, and move the responsibility for providing a reliable stream protocol to the endpoints (the client and the exit relays).

But by increasing flexibility for the relays, and by increasing the complexity of the endpoints, these datagram proposals also create some new attack vectors. Before we can deploy any of these designs, we need to consider whether these attacks weaken Tor's security, or whether they are irrelevant given other, stronger attacks against Onion Routing.

This whitepaper tries to list these attacks, and to provide a framework for thinking about them as we move forward with our design analysis.

We hope that this whitepaper will help researchers and others in the Tor community to understand these issues, so that we can work together to find new ideas to analyze and mitigate the attacks described here, and to help deploy a faster and more reliable network while still maintaining our current (or better) security guarantees. We hope that our description of the problem space will inspire, not discourage, future experiments in this area, and help with a holistic understanding of the risks, rewards, and future areas of work.

### A toy system

We will be analyzing a system that differs from Tor in the following ways.

* The link between a client and its guard, and between each pair of relays uses DTLS over UDP: packets can be dropped or re-ordered by an attacker on the link, but not modified, read, or forged. Each DTLS packet contains an integer number of cells.

* Each circuit between a client and an exit traverse several relays, as before. The cells on a circuit are no longer guaranteed to arrive reliably, but can be dropped or re-ordered on the wire, or by a relay.

* To provide reliable service end-to-end, the client and the exit each use a TCP-like protocol to track which application bytes have been sent and received. Received data is acknowledged; dropped data is retransmitted.

* The cryptography to be used for circuit encryption is not specified here.

* A reliable signaling mechanism between relays (to create, destroy, and maintain circuits) is not specified here.

(It is likely that many readers will be able to design a system that resists the attacks below better than the design above. But please remember as you do, that a design which improves a system in one way may constrain it in others, or may offer insufficient benefits to be clearly superior to Tor as it is today. Before we can deploy, we will need not just defenses, but also a systemic way to compare the effect of these defenses, used together, to the Tor status quo.)

## Some preexisting attacks to consider

To put the datagram-based attacks into context, we'll start out by listing some attacks against the current non-datagram Tor design (and proposed defenses for those, where they exist).

We assume, as usual, an adversary who controls some but not all relays, and some but not all ISPs.

A note on attack power: the accuracy of many of these attacks, particularly the passive ones, depends on the type of traffic being sent, the quantity of similar traffic elsewhere on the Tor network, the quantity of concurrent activity by the same client, the adversary's observation position and data retention resolution, the quantity of padding, and the tendency of the network to preserve or alter packet timing information in transit.

In many cases, we don't have good metrics or evaluation methodology to determine how much harder or easier one attack is than another.

### End-to-end passive traffic correlation attacks.

Here's the gold-standard base-line attack: an attacker who can watch any two points on the same circuit is assumed to be able to realize, without having observed very much traffic at all, that the two points are indeed on the same circuit by correlating the timing and volume of data sent at those two points.

When one of these points is also linked to the client, and one is linked to the client's activity, this attack deanonymizes the client.

Tor's current design focuses on minimizing this probability, and also shifting its characteristics, through things like network diversity and long-term entry points. The attack may also become harder (and/or slower) when there is a lot of similar concurrent traffic on the Tor network, which means that adding users who use Tor for many things is in itself a form of mitigation.

Proposed defenses in this area include deliberate obfuscation of message volume through padding, and of message timing through random delays, as well as things like traffic splitting and more complex traffic scheduling for loud flows. While we have completed some work on link padding, and are progressing on a deployment for circuit padding, it is not yet clear if we can use these defenses in an affordable way against a correlation attack, and it is hard to measure their effectiveness on a realistic Tor-sized network.

### Data tagging side-channels by relays

If two relays are on the same circuit, they can surreptitiously communicate with one another transforming the data in the RELAY cells, and un-transforming the data before passing it on. Since Tor's current encryption protocol is malleable, this allows them to send a large number of bits per cell.

This attack can also be used when two relays do not know if they are on the same circuit. One relay modifies a cell, and the other one looks for such modifications. If the data is processed by an honest relay, it will destroy the circuit, but the client may or may not notice that the circuit has destroyed. (And the dishonest relay may delay informing the client!)

To defend against this, we plan to replace our encryption with a non-malleable algorithm. See for example proposals 202, 261, and 295.

### Destructive side-channels (internal)

Even if we remove the malleability in Tor's encryption, a smaller side-channel remains: A dishonest relay can destroy a circuit at any time, either by corrupting the circuit or simply sending a DESTROY cell along it. A third party can destroy a large number of circuits at once by remotely attacking a client or relay -- either disabling that relay, or making it close circuits because of the OOM handler. (See the Sniper Attack paper.)

If a circuit is corrupted (as would happen if a relay attempted data tagging against one of the non-malleable cryptographic algorithms mentioned above), other points on the circuit can tell which cell is the first corrupted cell. If a circuit is destroyed at one point, other points on the circuit can tell how many cells were sent before the destruction.

It is likely that based on data or traffic patterns, most parties on a circuit will be able to distinguish a prematurely destroyed circuit from one that was shut down normally.

In each case, this attack can be used to send (log n) bits of information per circuit, at the cost of destroying the circuit, where n is the number of cells that might be sent over the circuit in total. Some noise will exist, since we expect some circuits to be prematurely closed on their own. We don't know how much noise.

We also have various heuristics that can attempt to detect if this happens too often; however at best they likely reduce the rate that information that can be sent in this way rather than eliminate it. We also lack methodology to measure the rate of information in this case, to help determine if we can successfully reduce it further.

### Destructive network probes (external)

Though TLS is resilient against many forms of active attacks, it can't resist an attacker who focuses against the underlying TCP layer. Such an attacker can, by forging TCP resets, cause all the entire TLS connection to be dropped, thereby closing all the circuits on it. This kind of attack can be observed at other points on the network in a way similar to the destructive side-channels noted above.

This class of attack seems to be easier against Tor's current design than it would be against (some) datagram-based designs, since datagram-based designs are resilient to more kinds of traffic interference.

### Timing-based watermarking attacks

Hostile relays can also introduce a side channels to a circuit by introducing patterned delays into the cells. For example, a relay could buffer a large number of cells, then transmit a "1" bit by sending a cell in a given time period, or a "0" by not sending cells in that time period.

An attacker can also mount this attack without controlling relays: if the attacker performs a DoS attack against a relay or its traffic, it can observe changes in the traffic volume elsewhere on the network.

[See https://www.freehaven.net/anonbib/cache/ccs07-latency-leak.pdf and http://cybercentre.cs.ttu.ee/wp/wp-content/uploads/2017/01/crw2017_final.pdf ]

The bandwidth of this side-channel will be limited, since other relays on the network will naturally buffer and delay traffic, obscuring the pattern some. There are also limits to how long packets can be delayed before the relay is no longer usable.

[See: - Rainbow: https://www.freehaven.net/anonbib/cache/ndss09-rainbow.pdf - Swirl: https://www.freehaven.net/anonbib/cache/ndss11-swirl.pdf - Backlit (detection): https://www.freehaven.net/anonbib/cache/acsac11-backlit.pdf ]

Proposals for resisting this type of watermarking attack are mostly of the same type that would be needed for resisting end-to-end correlation. An adversary that can perform active attacks to introduce their own unique traffic patterns intuitively seems much stronger than one that must passively use potentially common patterns. We lack a unified framework to tell us how much stronger this adversary is than the passive one, especially against various defenses.

### Traffic injection attacks

Related to the active timing attack, in some positions (like exit and RP) relays can inject cells that are ignored by the other endpoint. These injected patterns will not impact the user's experience, but will allow unique traffic patterns to be sent and detected by the adversary at crucial times.

[See https://petsymposium.org/2018/files/papers/issue2/popets-2018-0011.pdf]

These injection attacks arise from former adherence to Postel's Maxim. Tor has since departed from this maxim, and instead opted for stricter forward compatibility through feature versioning, but removing instances in the codebase where injected cells can be permitted has proven challenging.

## Attacks unique to datagram designs

Here are some attacks that are enabled by (or at any rate behave differently under) datagram-based designs.

### Traffic-stream tagging (by relays and internet links)

Because the new system permits a number of transformations on traffic that were not previously allowed, we need to look at how those transformations can be used to attack users.

As a trivial example, any router can relay an arbitrary subset of the cells that it receives on a circuit, in an arbitrary order, due to the exact properties the reliable transport aims to provide. The pattern induced in this way will be detectable by the exit relay when it attempts to reconstruct the stream. Because we explicitly allow this kind of transformation, the circuit will not be killed after a single dropped cell, but rather will continue working silently.

Moreover, any ISP can mount the same attack by dropping and/or re-ordering DTLS calls.

A remote attacker may also be able to mount this attack by flooding any router between a client and its guard, thereby causing some of the DTLS messages to get dropped.

If we are using TCP between client and exit, the acknowledgments sent by each endpoint will provide confirmation about which data it received and which it did not. If instead of TCP, we use some other protocol where the end-points communicate even more information about which packets they did and did not receive, this can provide an even higher-bandwidth side-channel.

The bandwidth of this side-channel is fairly high, since it allows the attacker to send over a bit per cell. But it will be somewhat noisy, since some cells will dropped and reordered naturally.

Padding, traffic splitting, and concurrent activity will increase the noise of this attack; we lack metrics to tell us how much, and we have no framework as of yet to measure the throughput of the resulting side channel in these conditions.

### Traffic Fingerprinting of TCP-like systems

Today, because Tor terminates TCP at the guard node, there is limited ability for the exit node to fingerprint client TCP behavior (aside from perhaps measuring some effects on traffic volume, but those are not likely preserved across the Tor network).

However, when using a TCP-like system for end-to-end congestion control, flow control, and reliability, the exit relay will be able to make inferences about client implementation and conditions based on its behavior.

Different implementations of TCP-like systems behave differently. Either party on a stream can observe the packets as they arrive to notice cells from an unusual implementation. They can probe the other side of the stream, nmap-style, to see how it responds to various inputs.

If two TCP-like implementations differ in their retransmit or timeout behavior, an attacker can use this to distinguish them by carefully chosen patterns of dropped traffic. Such an attacker does not even need to be a relay, if it can cause DTLS packets between relays to be dropped or reordered.

This class of attacks is solvable, especially if the exact same TCP-like implementation is used by all clients, but it also requires careful consideration and additional constraints to be placed on the TCP stack(s) in use that are not usually considered by TCP implementations -- particularly to ensure that they do not depend on OS-specific features or try to learn things about their environment over time, across different connections.

### Retransmit-based watermarking

Even if all TCP-like implementations are identical, they will retransmit with different timing and volume based on which cells have been acked or not acked. These differences may be observable from many points on the circuit, or from outside the network. Such retransmissions can be induced from outside the network, by hostile relays, or even by a hostile endpoint that pretends not to have received some of the packets.

We again lack metrics to indicate that it is substantially worse (or not worse) than other similar attacks. Intuitively, the key difference in degree would come from how much easier it is to perform this attack than the delay based watermarking attacks on traditional Tor above.

### Congestion and flow control interference

To the extent that the TCP-like stack uses information learned from one stream to alter its behavior on another stream, an attacker can exploit this interference between streams make all of the streams from a given party more linkable.

All implementations will have some amount of interference, to the extent that their bandwidth is limited. But some may have more than necessary.

### Non-malleable encryption designs only currently exist for in-order transports (or the return of data tagging attacks)

Our proposed defenses against data tagging require us to move to non-malleable encryption, with each cell's encryption tweaked by a function of all previous cells, so that if even a single cell is modified, not only is that cell corrupted, but no subsequent cell can be decrypted.

It seems nontrivial to achieve this property with datagram based designs, since we require that cells on a circuit can be decrypted even when previous cells have not arrived. We can achieve data-based non-malleability by using a per-hop MAC for each cell -- but we would no longer be able to get the property that a since altered cell would make the whole circuit unrecoverable. This would enable a one-bit-per-cell side-channel, similar but possibly more powerful than the packet dropping side-channel above. (Because the congestion window is essentially a bit vector of received cells, the adversary in this scenario gets to corrupt cells in carefully chosen ways instead of merely dropping them.)

Perhaps other cryptographic schemes could be found to resist data-tagging in a datagram-based environment or limit its impact, but we'll need to figure out what the requirements and models are.

As a proof-by-example of a mitigating system: Proposal 253 describes a way to send a rolling MAC out of band, to ensure integrity of packets between those cells. But can we do better? Can middle nodes enforce integrity in some other way?

### The risks of success: lower latency strengthens timing attacks?

There are two factors that make timing-correlation and timing-watermark attacks more difficult in practice: similarity between different users' traffic, and distortion in timing patterns caused by variance in cell latency on the network. To whatever extent we successfully reduce this distortion by lowering latency, it seems that we'll make these attacks more powerful.

In particular, geolocation attacks based on observed circuit setup times may get worse [See again https://www.freehaven.net/anonbib/cache/ccs07-latency-leak.pdf].

We're already making improvements to Tor that may make these attacks worse -- Tor latency has dropped and will continue to drop due to improvements like KIST, more relays, and better load balancing. Further incremental improvements like explicit congestion control on the existing Tor network will reduce latency even further.

It may be that a more performant Tor becomes less safe than a slower, less usable Tor. On the other hand, a more usable Tor will likely be used by more people, which we know makes many forms of traffic analysis harder (slower?) in general. However, we have no way to measure this tradeoff on many different attack types.

Delay and latency can also be added back in, and this has been a common defense against both active adversaries and timing attacks in the anonymity literature, but such delays have user-facing consequences, unless they are carefully restricted to the cases where the adversary can directly measure RTT and can be amortized away by things like pre-emptive circuit building. In this and other cases, it is also not clear to what degree adding delay is more useful than adding more padding.

## Towards comparing attacks

A high-bandwidth attack is worse than a low-bandwidth attack. One bit is enough to send "is this the targeted user?", but 32 bits is enough to send a whole IP address.

The impact of these attacks become worse if they can be repeated over time.

An attack that can be performed by an ISP relaying traffic is worse than one that can be performed by a relay. An attack that can be performed remotely against either of these is worse still.

We need some kind of methodology to help us compare the new side channels that datagram transports may enable to the existing side channels in Tor, particularly delay-based and congestion-based side channels. Ideally, these metrics or evaluation methodology would also allow us to compare these side channels under various forms of defense, such as padding.

At the very least, we need some way to compare the side channels in datagram transports to those that already exist.

We also likely need a common reference research prototype and/or platform to experiment with and study, so that attacks and defenses are reproducibly comparable. Reproducibility in attack and defense literature is often not reliable, due to differing implementations, in addition to differing methodology and evaluation frameworks.

## Open Questions

Why permit reordering? There are schemes (like order-preserving encryption) that we could deploy on middle nodes to prevent reordering, without allowing earlier nodes to differentiate padding from non-padding. Do we derive any benefit by allowing a relay to send cells on a single circuit in a different order than the order in which it receives those cells on that circuit? This may be an answered question in congestion control research, but we lack the domain expertise to know what this tradeoff is.

Related: what cryptography to use? Our current stateful encryption schemes benefit from having access to "all previous cells" when encrypting or decrypting each following cell. If we allow a cell to be {de,en}crypted before previous cells are received, we'll need a new model for onion-routing cryptography -- possibly one with significantly bigger headers.

## Future work

We hope to investigate these issues with researchers and others in the Tor community as we work towards solutions to help scale and strengthen the Tor network. Understanding the risks and rewards that datagram-based transports introduce to Tor is important to help us select designs that both help improve performance but also guarantee safety for Tor users. We hope that by cataloging these risks, future conversations about improved network designs can bring answers and broader improvements. We look forward to working with others interested in helping solve these problems to design a better Tor.

## Acknowledgments

Our thanks to Chelsea Komlo for many helpful suggestions and comments on earlier drafts of this whitepaper, and for writing the request for future work.

## Further reading

Steven Murdoch, "Comparison of Tor Datagram Designs", 2011. https://murdoch.is/papers/tor11datagramcomparison.pdf

Mashael AlSabah and Ian Goldberg. "PCTCP: per-circuit TCP-over-IPsec transport for anonymous communication overlay networks", 2013. http://cacr.uwaterloo.ca/techreports/2013/cacr2013-09.pdf

Michael F. Nowlan, David Wolinsky, and Bryan Ford. "Reducing Latency in Tor Circuits with Unordered Delivery", 2013. https://www.usenix.org/system/files/conference/foci13/foci13-nowlan.pdf

Rob Jansen, Florian Tschorsch, Aaron Johnson, and Björn Scheuermann The Sniper attack: Anonymously Deanonymizing and Disabling the Tor Network", 2013 https://www.nrl.navy.mil/itd/chacs/sites/edit-www.nrl.navy.mil.itd.chacs/fil...