# "Design Principles for Low Latency Anonymous Network Systems Secure against Timing Attacks"

###### tags: `Tag(HashCloak - Validator Privacy)`
Author(s): Rungrat Wiangsripanawan, Willy Susilo and Rei Safavi-Naini

Paper: https://dl.acm.org/doi/pdf/10.5555/1274531.1274553?download=true

### Table of Contents
[toc]

:::info
>Abstract: Low latency anonymous network systems, such as Tor, were considered secure against timing attacks when the threat model does not include a global adversary. In this threat model the adversary can only see part of the links in the system. In a recent paper entitled Low-cost traffic analysis of Tor, it was shown that a variant of timing attack that does not require a global adversary can be applied to Tor. More importantly, authors claimed that their attack would work on any low latency anonymous network systems. The implication of the attack is that all low latency anonymous networks will be vulnerable to this attack even if there is no global adversary.
>
> In this paper, we investigate this claim against other low latency anonymous networks, including Tarzan and Morphmix. Our results show that in contrast to the claim of the aforementioned paper, the attack may not be applicable in all cases. Based on our analysis, we draw design principles for secure low latency anonymous network system (also secure against the above attack).
:::

## 1 Introduction
Recently, Murdoch and Danezis have shown a low cost attack that can successfully “break” low latency systems, and does not use a global adversary (Murdoch & Danezis 2005). Their attack is based on a traffic analysis attack proposed by Danezis (Danezis 2004). In their attack, Tor’s provided anonymity can be broken by an attacker that only has a partial view of the network or is one of the Tor nodes. The attack works because Tor removes the mixing operation that has been used in its earlier version, and instead processes its input queues in a round robin fashion.
* The Tor node is responsible for receiving and forwarding each stream’s packets.
* A corrupted Tor node can create connections to other Tor nodes and so indirectly estimate other nodes’ traffic volumes at each time.
* These estimates use the difference in the latency of streams that are sent and received back using those connections.
* As the traffic volume or traffic load on each Tor node is a result of the traffic load of all relayed connections on that Tor node, the technique in (Danezis 2004) can be used to estimate the traffic pattern of each node and utlimately a good estimate of the route.
* Authors noted that their scheme can be applied to any anonymous low latency systems.

This significantly invalidates the threat model used in many low latency anonymous systems.

**Our COntributions**
Our analysis has two directions.
1. We focus on the *latency* of the system, to verify whether it can be used to represent the traffic load of each node.
2. We look at the effectiveness of the attack on different architectures and mechanisms.

We will use our analysis to provide design principles for building secure low latency anonymity systems that do not suffer from these types of attacks.

## 2 Related Works
In this section, we will briefly review the three existing anonymous network systems, namely Tor, Tarzan amd Morphmix.

### 2.1 Tor
Tor, the second-generation Onion Routing, is a circuit-based low-latency anonymous communication service (Dingledine et al. 2004).

**Tor Threats Model**
An adversary’s goal is to observe both the initiator and the recipient. Like all other practical low latency anonymous systems, Tor does not provide any mechanisms to protect against a global passive adversary. However, it is designed to prevent the system against an adversary that has the following capacities:
* the adversary who can observe some fraction of network traffic.
* The adversary who can generate, modify, delete or delay traffic.
* The adversary who can operate onion routers of his own.
* The adversary who can compromise some fractions of onion routers.


Attacks using the network traffic can be classified into two main categories:
1. Traffic confirmation attacks.
2. Traffic analysis attacks.
* Each category consists of both passive and active attacks.
* Traffic confirmation attacks are attacks where the adversary uses a traffic pattern to confirm his guess.
* Traffic analysis attacks are attacks that the adversary learns which points in the network he should attack by using traffic patterns.

### 2.2 Tarzan
Tarzan is another low latency anonymous system, which is also based on the Chaum’s mix concept. Similar to other low latency anonymous systems, it is aimed to provide anonymity for applications such as web-application or instant messenger. Unlike Tor, Tarzan is based on peer-to-peer architecture.
* Each Tarzan node can be both a Tarzan client (the sender) or a Tarzan relay.
* This is done to avoid end-to-end timing analysis of an entry and exit nodes.
* That is, any one can join and leave the network and all nodes can be potential initiators.

Tarzan provides peer discovery by using a protocol based on the gossip-based mechanism similar to the one in (Harchol-Balter, Leighton & Lewin 1999).
* Due to the peer-to-peer characteristic, an adversary can imitate himself as many Tarzan nodes as he wishes.
* Therefore, Tarzan is equipped with a mechanism to store peers in a way that reduces a chance that a malicious node is selected.
* This is done by hashing the node’s IP address according to its subnet and categorizing its result into levels.

Tarzan claims that it is resistant to the global adversary’s attack, that is achieved via its cover traffic mechanism, known as mimic traffic. To prevent an overwhelming network consumption, Tarzan limits the mimic traffic of each Tarzan node to merely with some of its peers.

To illustrate this, when joining the network, after discovering all other peers, the Tarzan node selects a number of nodes as its mimics. Then, when an anonymous connection is required, the next relay node must be chosen from the node’s mimic list.

When a Tarzan node a wants to have an anonymous connection with its recipient such as a web server $svr$, assuming that the anonymous tunnel has $l + 1$ length where $l$ is a number of the nodes in the tunnel, $a$ selects its first hop from its mimic list, say $n1$.
* Then, $a$ asks $n1$ for $n1$’s mimic list $(l_{n1})$.
* $a$ chooses the 2$^{nd}$ hop, from $(l_{n1})$.
* Then, $a$ repeats this process until $l$ hops.
* Finally, $a$ chooses the last node randomly from $a$’s peer database.
* This last node acts as an exit node in Tor but Tarzan names it PNAT.
* Therefore, the connections has the following path:
* $a → n_1 → n_2 → ... → n_l → PNAT → svr$.
* It is important to note that PNAT is selected randomly from all peers in the database not from $n_l$’s mimic list, otherwise numbers of available paths are limited.


**Figure 2** illustrates Tarzan network’s architecture and its tunnel connections. In this example, each Tarzan node has approximately 6 mimics.

### 2.3 MorphMix
MorphMix (Rennhard & Plattner 2002, Rennhard & Plattner 2004) is another low latency anonymous system. Its main objective is to provide a practical anonymous communication to the masses. It is based on a peer-to-peer architecture. Similar to Tor, MorphMix is a circuit-based mix system that makes use of fix-length cells and layered encryption to establish a circuit through other nodes.
* Cover traffic is removed unless really required.
* The circuit, the first node, the last node and the nodes in between are called the anonymous tunnel, the initiator, the final node and the intermediate nodes, respectively.
* Unlike Tor or Tarzan, the intermediate nodes in MorphMix are not entirely chosen by the initiator.
* Rather, MorphMix allows each intermediate node to select its successor.
* When an initiator node a wants to establish an anonymous tunnel, it selects the first intermediate nodes $b$ from its current neighbor list.
* Then, it establishes a symmetric key between them.
* The shared key is used for layered encryption.
* To extend the tunnel, $a$ asks $b$ for a selection of nodes that should be used as its next hop.
* $b$ sends a a set of its recommended nodes chosen from $b$’s neighbors.
* $a$ then chooses one of them, for example, node $c$.
* $a$ appends $c$ to $b$ in the tunnel.
* A symmetric key between a and $c$ is created and then, sends to $c$ through $b$.

To prevent $b$ from being man-in-the-middle attacked, MorphMix introduces a witness. The witness’s duty is to act as a third party during the next hop selection process. It allows the initiator $a$ to establish a shared key with the appended node $c$ through $b$, without revealing $c$’s key information to $b$ or without $b$ being a malicious node.


**Figure 3** is cited from (Rennhard & Plattner 2002). It shows how MorphMix selects the next hop with the witness’s help.

Assuming that the connection between the initiator a and b has already been established. The complete procedure is illustrated as follows:


Unlike any other systems, MorphMix does not require that any MorphMix node must have knowledge of all other nodes. Rather, MorphMix pays more attention to collusion’s detection of malicious nodes.

## 3 A Low Cost Attack in Low Latency Anonymous System
In this section, we review a low cost attack on Tor as described in (Murdoch & Danezis 2005). The term *low cost* comes from the fact that the adversary requires only a partial view of the network, i.e. being one of the Tor nodes, to attack the Tor network. The attack shows that the Tor system is vulnerable to a variant of timing analysis attack, even though this attack was claimed to be *prevented* in the original Tor threats model.

The attack, conceptually, takes advantage of a seemingly unavoidable limitation of the low latency anonymous system; that is *time*. The goal of the attack is to infer which nodes are being used to relay streams in the Tor circuit. This greatly decreases the anonymity properties of Tor system.

**The Idea of The Attack**
The idea comes from the known fact that delay cannot be induced much in the low latency systems. Hence, the timing pattern of packets should persist throughout a circuit.

The traffic loads of the other Tor nodes are changed as well. Therefore, they can conclude that the change of the traffic load on one Tor node affects other Tor nodes that have connections to it. Hence, for nodes that are on the same circuit, their traffic loads should result in the same pattern of effects.

**Entities Involved**
The adversary merely requires to be a member of the Tor’s system. That is, being one of the Tor clients. This node is called a *corrupt node* or a *probe node*.


**Attack Model**
Conceptually, the attack works as follows:
* A corrupt Tor node establishes connections to other Tor nodes in order to measure these connections’ latencies.
* The corrupt Tor node keeps monitoring latencies of all these connections during a reasonable time period.
* The latencies values are used to estimate traffic loads of the Tor nodes’ that the corrupt node makes connection with.
* Traffic patterns are derived from the traffic loads.
* When the adversary has the traffic pattern of all nodes, it can further mount an attack similar to ones in (Danezis 2004, Levine et al. 2004).

## 4 Analysis of the Low Cost Timing Attack against Tarzan and Morphmix
To perform this attack with other systems, we employ the same model as the one used by Tor. The adversary requires at least two entities: a corrupt node and a corrupt server.
* A corrupt node is changed to a sender node in each particular system.
* That is, a Tarzan client in Tarzan, and an initiator node in MorphMix.
* Next, a corrupt node needs to acquire a list of all other nodes in the system.
* Then, it establishes connections to these nodes so that it can monitor their connections’ latencies.
* Connections are monitored for a period of time.
* During that time, the corrupt server keeps sending its traffic into the system.
* When the monitoring period finishes, latency of each connection is used to estimate the traffic load of that particular node.
* Then, the traffic load is compared with the server traffic.
* If it results in similarity, the node is concluded as one of the intermediate nodes in the path.
* When traffic of all nodes are compared, the possible path(s) is/are derived.

Thus, the attack would be successful under the following three conditions:
1. Latencies received at the corrupt node indeed represent traffic loads of the target nodes.
2. The corrupt node must be able to know other participants in the network.
3. The corrupt node must be able to establish a *direct* connection to *all* nodes it wants to monitor

The attack is successful in Tor because the Tor architecture satisfies these conditions.
1. Firstly, due to the fact that Tor removes mixing operations and cover traffic, its timing characteristic is retained.
* This is supported by the experiment result in (Murdoch & Danezis 2005).
2. Secondly, Tor provides a directory service that a Tor client can acquire a list of all other Tor servers.
3. Third, there is no restriction to prohibit the Tor client not to establish a connection to all Tor servers.


### 4.1 Low Cost Attack in Tarzan
To investigate if the attack is applicable with Tarzan, we will analyze what influences each condition has provided to the system.

**Latency**
There are two differences between Tarzan and Tor that should affect the latency.
1. The first one is Tor operates its queue in a round-robin fashion.
2. Secondly, Tor does not include mixing operations and cover traffic.

Tarzan provides a mimic mechanism. That is, even though Tarzan does not mention how each Tarzan node manages its incoming queues, Tarzan controls the rate of output links according to the average rates of its input links.
* When each link does not reach the rate it requires, Tarzan inserts dummy data.
* Also, prior to sending out its streams to output links, the Tarzan node does some mixing and batching within each link’s outgoing queue.

**Node discovering ability**
A Tarzan node discovers other peers through a mechanism based on a gossip-protocol. Thus, each Tarzan node can gather all information about all peers. What seems to be a problem is Tarzan is based on peer-to-peer architecture so that the number of nodes should be huge and the network should be dynamic. Then, whether it is possible that the corrupt node can monitor all others’ node latency is dubious. However, since we are merely concerned with the ability to know other peers in the network, Tarzan is still considered to satisfy this condition.

**Connection Establishment ability**
After recognizing all other nodes in the network, if the corrupt node is able to establish a direct connection with all nodes through an anonymous tunnel in Tarzan network, then this will satisfy the third requirement. Unlike Tor, Tarzan restricts its traffic through merely its mimics. Therefore, when target nodes are not mimics of a corrupt node, the corrupt Tarzan node may not be able to make a one-hop connection to each target node.

Up to this point, it seems that the low latency attack may not work in Tarzan. Nevertheless, the adversary is fortunate. Tarzan employs PNAT, which is the last node in the tunnel prior to the recipient.
* Unlike other intermediate nodes in the tunnel that their successors and their predecessors are restricted to their mimics, the PNAT can be any node in Tarzan network.
* Therefore, to measure latency of other node in the network with a single hop connection, the corrupt node can treat each target node as the PNAT of that connection.
* Then, there will be no problem with the mimic traffic.

In summary, the low cost attacks should be applicable with the Tarzan architecture, unless Tarzan’s mimic traffic can destroy timing characteristic of the streams or the PNAT mechanism is modified to require the exit node to be part of the mimics.

### 4.2 Low Cost Attack in MorphMix
The major differences between MorphMix and Tor seems to be the architectures of the systems and the method to select tunnels’ members and the exit node. MorphMix works in a peer-to-peer environment where Tor has dedicate servers acting as Mix nodes. In Tor, a Tor client is the one who selects all participants in its anonymous tunnel by itself.

**Latency**
MorphMix nodes appear to work in the similar fashion as Tor nodes, after tunnels are established. That is, no cover traffic mechanism is included. Thus, in this aspect, the attack should be applicable to MorphMix.

**Node discovering ability**
There is no requirement in MorphMix that each MorphMix node must have knowledge of all other MorphMix nodes in the system. Simply, each node requires a handful of other nodes obtained locally such as from its neighbors.

The implication is as follows. When the low cost attack is employed, the corrupt MorphMix node has a problem with acquiring a complete list of all running MorphMix nodes. That is, it must discover all nodes first. This is not a trivial exercise, in particular, when the discovery can only be done through MorphMix tunnel establishment mechanism. Therefore, an effective searching algorithm is required. Nevertheless, this involves a lots of work. Hence, the so-called “low” cost attack will now become “costly”.

**Connection Establishment ability**
There is no restriction in MorphMix connection. Hence, each MorphMix node can have a one-hop connection to other MorphMix node directly.

In short, the current attack is not applicable to the MorphMix architecture because the corrupt node is lacking the knowledge of a complete list of all MorphMix nodes.

## 5 Design Requirements for Secure Low Latency Networks
There are two essential conditions required in mounting the low-cost attack. Firstly, the knowledge of all other nodes in the system by a corrupt node is essential. Without this knowledge, this type of attacks cannot be performed. Secondly, the latency being probed must genuinely represent the traffic load.

Based on these observations, we derive the following conclusions. There are two alternative approaches that can be taken to prevent the low cost traffic analysis attacks.
1. Preventing all nodes from gathering information of the whole network , i.e. a list of all nodes. This implies that we only need to provide adequate information so that an anonymous tunnel can be created.
2. Inserting cover traffic into streams in the network in a way such that the network cannot find the streams’ signature.

Based on either of these two possible approaches, we can build a secure low latency network that will not be susceptible against the low cost attacks.

> It is important to note that all strategies suggested by (Murdoch & Danezis 2005) fall into the second approach. However, as they introduce more latency to each connection and involve a covert channel, there remains an open problem in what degree that cover traffic should be employed. Hence, the first alternative sheds a new light in preventing this attack.

## 6 Conclusion
In this paper, we investigated one of the attacks in low latency anonymous network systems, namely the low cost traffic analysis attack. This attack is an important one, since it has proven to be successful in attacking a system like Tor, which was believed to be secure under the *weaker* threat model. Moreover, these types of attacks are claimed to work with *any* low latency anonymous systems. We presented a case where this attack is not applicable. We also investigate some important properties that need to be ensured whilst building low latency network systems, so that they will not be susceptible against these types of attacks. Hence, we provided some necessary conditions that are important and need to be adhered when designing the low latency anonymous networks. We note that cautions must be exercised upon building this type of networks.