# BYZANTINE ATTACKS ON ANONYMITY SYSTEMS - 2005

###### tags: `Tag(HashCloak - Validator Privacy)`

Authors: PARISA M. TABRIZ

Paper: http://asirap.net/work/msthesis.pdf

Definitions:

### Table of Contents
[toc]

:::info
>Abstract: Anonymous communications systems are analyzed against a range of attacker models
to measure the level of privacy they provide users.
:::

### Introduction
> If an adversary controls enough
of the relay path, he is able to trace messages through the network and deanonymize the connection. We present two specific instances of this attack and evaluate their impact on existing systems.

1. The first attack is on MorphMix, a peer-to-peer anonymous networking system for lowlatency communications.
2. The second attack we contribute is a selective Denial-of-Service (DOS) attack against all anonymous systems that are designed using the Mix-Net architecture.

### Ch 2: Background
Tor and systems like it are insecure against many traffic analysis attacks. The current deployment of the Tor network has been pushing the limits of the fixed size network somewhat, with several hundred mix servers in operation, but the network cannot grow much larger without major changes to its design and implementation.

MorphMix represents an alternative, peer-to-peer design for anonymous networks. Each MorphMix user runs a node that both generates anonymous traffic of its own and acts as a mix server, forwarding anonymous traffic for others.

### Ch 3: The Byzantine Participant
> In this Chapter, we review the various threat models used in system analysis and explain why we focus on the Byzantine participant. We also define the path compromise attack and a specific path compromise strategy.

#### Privacy as Unlinkability
> The level of privacy in anonymous communications is often measured by evaluating how well the system performs in the presence of an adversary trying to disrupt security.

If only one user is active at a certain period of time and only one service is producing activity, the observer can link a connection between a user and the service even if all of the data on the connection is encrypted.

#### Common Threat Models
Due to traffic analysis attacks, all practical low-latency systems are insecure against the global passive adversary, and thus assume a weaker than global attacker with respect to network coverage, but one that is not merely passive.

The active adversaries can additionally disrupt the system by inserting or delaying messages on any communication link under their control.

Additionally, an active adversary can mark messages as they go through a relay in an anonymous network and try to locate the tagged message later to trace the connection.

* Mixmaster and Babel are both vulnerable to this form of tagging.
* Mixminion, however, specifically addresses this threat by using hashes to verify the integrity of message headers at every relay.

#### A Participating Attacker
> It is both to the benefit and detriment of the system that the resource costs to join are so small, as it encourages all types of users to contribute to the network.

The participating adversary is one that has either compromised or is independently running mixes in a system:

1. The first is an “honest, but curious” (HBC) participant that behaves according to the anonymity protocols of the system, but tries to learn as much as he can about the source and destination of all messages he observes.
> This threat is the underlying reason we use mix chaining instead of just a single mix for anonymous communication. The rationale is that as long as there is one honest mix selected as part of a relay path, the initiator and recipient will remain unlinkable.

2. The second classification is a participating adversary that both behaves and misbehaves according to the system protocols, depending on his current strategy.
> We can model this adversary’s arbitrary behavior as a Byzantine adversary.

**The Byzantine failure model** has been increasingly used to evaluate the security of distributed systems. This is because in the worst case, an adversary that exhibits random behavior can be considered as acting malicious, and therefore if a system tolerates Byzantine faults, it can also be regarded as secure from malicious adversaries.

Due to the loose organization of membership in anonymous communication systems and low resource cost to participate, we consider the participating adversary an especially realistic threat.

Additionally, since the participating adversary is directly controlling mixes, the resources required to act as a Byzantine participant are no more than those needed to act as an HBC participant, so we focus our attention on this more dangerous case of a Byzantine attacker.

#### Path Compromise Attacks
> A path compromise attack is any strategy that takes advantage of a relay path formation protocol to degrade the security of an anonymous communication system.

While mix cascades are less flexible, they are resilient to some message blocking attacks and global traffic analysis that deployed Mix-Nets are unprotected against.

Alternatively, it has been shown that freely constructed relay paths can provide better anonymity and message reliability when using synchronous message batching designs.

Instead of exploiting information gathered from the protocol itself, an adversary can simply try to influence how the relay path that a user sends its messages over is built.

### Ch 4: Attacking the Collusion Detection Mechanism of MorphMix
> by allowing unknown peers to aid in tunnel construction, MorphMix is vulnerable to colluding attackers that only offer other attacking nodes in their recommendations. To avoid building corrupt tunnels, MorphMix employs a collusion detection mechanism to identify this type of misbehavior.

#### MorphMix
>MorphMix is a circuit-based mix network consisting of many MorphMix clients, or nodes, that act as both connection initiators and routers for the network.

**MorphMix and Anonymous Tunnels**
One unique feature of MorphMix is that the route a node uses for its connection, an anonymous tunnel, is constructed iteratively by other participating nodes in the system.

By using the last hop to discover options for the next hop, MorphMix nodes only need to maintain state information about their local neighbors. This allows MorphMix to scale independently of the number of nodes in the system. However, an immediate threat is introduced when a malicious node is appended because it helps determine the next hop in the tunnel. To prevent a malicious node from offering selections biased with other malicious nodes, MorphMix employs a collusion detection mechanism (CDM) to identify this behavior and prohibit this form of attack.

> MorphMix assumes that a tunnel is compromised, or malicious, if the first intermediate and final node are both controlled by an attacker. Otherwise, it considers the tunnel fair.

#### Collusion Detection Mechanism
> MorphMix detects this behavior by performing collusion detection on each offered selection.

If attackers own a whole range of IP addresses, it would be easy for them to operate many MorphMix nodes. To limit this threat, MorphMix distinguishes individual nodes from each other by their 16-bit IP address prefix.

It is much more costly and difficult for attackers to own nodes in many unique /16 subnets than it is for them to own many nodes in one or more /16 subnets.

There are two important assumptions to highlight from the collusion detection mechanism that form the intuition behind our attack:

1. An extended selection from a colluding node will overlap with many other colluding entries stored in the LES, resulting in a large c.
2. The c of a malicious extended selection will, in general, be higher than the correlation limit determined for that node.

> By limiting the number of selections that overlap in a victim’s LES, a colluding adversary can keep c low such that it frequently falls beneath the correlation limit and is not detected during tunnel construction.

#### Attacking the Collusion Detection Mechanism
> In this section, we define the adversary necessary to perform this attack, describe the attacker’s goal, and present a general description of the attack.

* Attacker Model: Because attackers can so easily join, contribute, and exit the system, we assume an active, internal adversary.
* Attacker Goal: We assume that the goal of attackers is to link a connection initiator with some outgoing stream.
> Our attackers, however, accomplish linkability by owning every node in the tunnel.
* Attack Description: Our attack is based on this simple intuition
> Because each node’s CDM is based on only the local knowledge stored in its LES, attackers can model and manipulate the LES to avoid being detected.

#### Simulation

* MorphMix Settings: we simulate many tunnel constructions using the CDM from the MorphMix client prototype [28] and investigate the effects of the attack on one node, the victim node.
* Attacker Settings: To minimize the effect these misdirected selections have on the collusion detection mechanism, the attackers should use a different random permutation of nc when constructing Sv for each different victim v.
* Attack Execution: We execute the attack during 5000 tunnel construction attempts by a single victim node and calculate how many successful tunnels are constructed.
> creating 5000 tunnels is roughly equivalent to one week of constant MorphMix usage
> If colluding adversaries control nodes in more than 15% of the represented subnets in MorphMix, they are able to compromise at least that percentage of tunnels constructed by victims.
> Attacking levels above 30% result in the majority of all constructed tunnels being compromised by an attacker.
* Optimized Execution for Smaller Adversaries: If attackers owning nodes in less than 15% of the unique subnets in MorphMix attack uninterrupted, they will eventually saturate the victim’s LES and be detected with high probability once they starts repeating selections.
> In this case, they can optimize their attack by using intelligent selections to build tunnels until they runs out of unique selections and then behave normally until the victim’s LES has cleared. Because nodes evict the oldest entries from their LES, attackers can estimate how long it will take for the victim’s LES to be cleared based on how often and at what rate the victim creates tunnels.
> If they attack until they run out of unique selections and then wait until the node’s LES has cleared, they can compromise almost five times as many tunnels and can continue to attack the victim in this manner indefinitely.

In theory, there is an improved strategy that a limited attacker can use when behaving honestly. Attackers should provide selections that consist of very few malicious nodes and many other unique honest nodes during this honest behavior period. This way, the victim’s LES becomes filled with selections that will overlap with future attacking selections, yet make a large contribution to u in the correlation algorithm. This will, in turn, lower the correlation and decrease the chance of future detection
* Attack Countermeasures: An immediate countermeasure to this attack might be to increase the number of nodes in the tunnel and increase the number of entries in the LES. Increasing the number of nodes in the tunnel would force the attackers to use more selections for each tunnel. Increasing the number of entries in the LES has a similar consequence because it allows each node to store more attacker selections at one time.

New users to MorphMix are especially vulnerable to the intelligent selection attack. Since new users enter the system with an empty LES, attackers are guaranteed to successfully compromise a significant portion of a new user’s initial tunnels, regardless of the LES size. This type of initial behavior in MorphMix will presumably limit its adoption.

Also, because nodes evict the oldest entries from their LES, attackers can estimate when a victim’s LES will be cleared of attacking selections and then once again begin the attack. These two factors make it easy for attackers to not only model and manipulate what a node has stored in its LES, but improve their attack strategy based on this information.

Although the CDM may be adjusted to capture some possible attack strategies, attackers can stay one step ahead by modeling the state and algorithms of the CDM at each node and crafting the best possible response, consisting of both honest and colluding selections.

> An effective collusion detection mechanism for MorphMix requires a more global perspective of the network. One instance of this might be to enforce a double check on any offered selection during tunnel construction.

### Ch 5: Selective Denial of Service Attacks
> In this Chapter, we consider the effect attackers that disrupt anonymous communications have on the security of traditional mix systems, as well as on the Hydra-Onion and Cashmere systems that aim to offer reliable mixing.

#### Denial of Service against Conventional Anonymity Systems

**Tor**
> Tor is a widely used system for low-latency anonymous Internet communication.

Background:

* As of November 2006, Tor is composed of approximately 800 active routers supporting hundreds of thousands of users.
* The tunnels are constructed in a telescoping manner and are protected by layered encryption, so that each router only knows the previous and next routers forwarding the tunnel.
* In Tor, the low-latency nature of the communication allows the first and last router in a tunnel to collude and easily discover that they are forwarding the same data stream by matching packet timings.
* under conventional analysis, if t! is the fraction of all Tor routers that are compromised, then t2! is the probability that any individual tunnel will be compromised.

Reliability Analysis:

The reliability of Tor tunnels is straightforward to determine:

A Tor tunnel that goes through l routers (l is typically 3) will fail if any of the routers fail. Therefore, if f is the probability of a router being reliable, R = f^l is the probability of the entire tunnel being reliable.

Next, we analyze the effect of a selective denial of service on Tor.

1. We assume that dishonest routers will perform DoS on any tunnel they cannot compromise.
2. If the adversary acts as a first or last router on a tunnel, the tunnel is observed for a brief period of time and matched against all other tunnels where a colluding router is the last or first router, respectively
3. If there is a match, the tunnel is compromised; otherwise, the adversary kills the tunnel by no longer forwarding traffic on it.
4. The adversary also kills all tunnels where it is the middle node, unless both the previous and the next hop are also colluding.

>Under this attack, a tunnel is reliable only if the first and last nodes are compromised, or if it is composed of only reliable honest nodes.

Of course, one hopes that fewer than 50% of Tor routers are dishonest — it would seem difficult for an adversary to compromise 400 out of 800 routers.
> Personal Note: Would this be as large of an issue in blockchains where there is something at stake? Private chains where membership is exclusive? If selected validators ran an onion/tor like network, general validators could be private. This system should definitely ADD to the cost of attacking general validators' privacy although would add another attack vector (specialized routing validators).

**Vanilla Mix Networks**

Background:

* These systems can be classified as high-latency Mix-Nets since they introduce large and variable latencies during batching.
* Because of this, however, high-latency MixNets are much more robust to timing attacks than systems such as Tor.
* Only when the adversary controls every mix in the forwarding path will the anonymity of a message be compromised.

Reliability:

* As mix-based systems were developed and deployed, the issue of reliability became apparent as volunteer-run nodes were often unavailable or offline.
* Pingers attempt to relay traffic through all mixes and keep track of the messages that are eventually delivered.
* To avoid malicious nodes manipulating the rankings, the pinging traffic is forwarded through the anonymous network itself.
* Such a strategy, however, biases the nodes used, may be manipulable by the adversary, and could reduce the anonymity of messages.
* An alternative strategy to ensure reliability, used by Mixminion and Mixmaster, is to send copies of the messages, or fragments thereof, through independent paths.

Conventional Analysis:
> We first analyze the security and reliability of Vanilla mixes under the simple attacker strategy of forwarding all messages.

**Theorem 1 (Security of Vanilla Mixes)**
For the message to be compromised, at least one full route should be composed of dishonest mixes.

**Theorem 2 (Reliability of Vanilla Mixes)**
For the messages to be delivered there should be at least one full route composed of bad or reliable honest mixes.

Selective DoS Attack:
* Instead of relaying all messages, bad mixes only relay those messages that they can trace from the beginning to end.
* The mixes decrypt as much of the message as they can using the keys of all the colluding mixes and determine whether there is an honest mix somewhere in the chain.
* Messages that cannot be compromised in this way are either dropped or modified in a subtle way so that they are unrecoverable by the recipient.
* The sender then has to send more copies of the message to increase its chances of arriving, which in turn increases the chances that the adversary captures the message.

**Theorem 3 (Reliability of Vanilla Mixes against DoS).**
For the message to be delivered a path has to be either fully compromised or fully honest and reliable.

The DoS strategy does not affect the probability the message is secure; the results are the same as in Theorem 1.

To achieve the same level of reliability, a sender must send the messages more times, which in turn provides more opportunities for the adversary to capture the message.

#### Denial of Service against Systems Featuring Reliability

**Cashmere**
> Cashmere is an anonymous routing layer that uses relay groups instead of single-node mixes to provide increased connection reliability.

Background:
* Each relay group is composed of a set of nodes that share a common public/private key pair.
* This gives any member of the group the ability to decrypt a layer of the message and forward it to the next relay group.
* Each node in Cashmere is assigned a unique nodeID and each relay group a unique groupID such that a node is a member of a relay group if the groupID is a prefix of its nodeID.
* Cashmere is implemented on top of the Pastry structured overlay and makes use of its anycast mechanism to route a message toward any node with the correct groupID prefix.
* A node will be found as long as at least one member of the relay group is reliable.
* The root decrypts the message, broadcasts the payload to all members of his relay group, and then sends the message to the next relay group in the forwarding path.
* Since the payload of the message is encrypted with the destination’s public key, independent of the forwarding path, a destination can receive the message before it reaches the end of the relay path.

Security and Reliability of Cashmere:
* In the presence of a passive adversary, honest and reliable, as well as dishonest nodes will forward traffic appropriately.
* Since any of the nodes in a relay group can decrypt the current layer of the forwarding path, connections may be insecure whenever there is at least one dishonest mix present in every relay group leading up to the destination.
* We also require the destination to be dishonest to consider a message compromised.

**Theorem 4 (Reliability of Cashmere)**
To ensure message reliability, each relay group before the one that contains the destination must be reliable, and the destination must itself be reliable.

**Theorem 5 (Security of Cashmere)**
For message anonymity to be compromised, each relay group leading up the destination, plus the destination itself must be compromised.

Cashmere under a DoS adversary:
> Cashmere routing is affected by DoS attacks when any of the relay group roots are dishonest. Unless the adversary has compromised the entire forwarding path, he will drop any connection that goes through a relay root he controls and the connection will have to be rebuilt.

**Theorem 6 (Reliability of Cashmere under DoS)**
The probability that a message is delivered reliably is the probability that every relay group until the destination delivers the message reliably. This means that either every relay root and the destination are reliable and honest, or the entire path is compromised and thus remains reliable.
> These results highlight that under the DoS strategy, both the reliability and security of Cashmere are strictly worse than for Vanilla mixes with equivalent w (group size).
> Cashmere is useful when there are few compromised nodes and very frequent failures.

#### Hydra-Onions
> The Hydra-Onion system was designed to resist active adversaries dropping onions during transmission.

Background:
* Just as in vanilla mixes, w copies4 of a Hydra-Onion are sent in a cascade.
* However, at each step, a mix will forward two copies of the Hydra-Onion to two different mix servers at the next step.

Security and Reliability of Hydra-Onions:
> Since any of the mixes at step i can decrypt the Hydra-Onion Oi , a Hydra-Onion is insecure whenever there is at least one dishonest mix at each step.

**Theorem 7 (Security of Hydra-Onions)**
The reliability of Hydra-Onions is somewhat harder to ascertain, due to the randomized forwarding nature of the mixes.

To simulate the reliability given the DoS attacker strategy, we first determine whether there is at least one dishonest mix at each step. In this case, the onion is compromised and the dishonest nodes are reliable and forward all messages. Otherwise, the dishonest nodes perform a denial of service and drop all traffic sent to them.

**Analysis**
* As designed, Hydra-Onions are effective at providing reliability in the face of denialof-service.
* However, this is done at the expense of security: increasing values of w very quickly decrease the security of Hydra Onions, as a single compromised mix at each step suffices to compromise the entire onion.
* When 15% of nodes are malicious, 5% of all onions are compromised, and when the fraction of malicious nodes rises to 30%, over half of all paths are compromised.
* Hydra-Onions are not a good tool when a significant number of mixes are compromised.
* They are also inefficient when nearly all nodes are honest.
* The main advantage of Hydra-Onions seems to be when most nodes are honest, but not reliable.

> A simpler variant of Hydra-Onions proposed by the same authors, called DUO-Onions, may be more appropriate for this case. DUO-Onions are designed to handle fail-stop failures, such as unreliable nodes or DoS, by iteratively picking the next mix in a list whenever the first choice is unreachable. DUO-Onions have the advantage of using dramatically less bandwidth in the case that nodes are reliable, and only sending extra onions as necessitated by failures. They are unable to address Byzantine faults of the forwarding mixes, but as our analysis shows, neither are Hydra-Onions.

#### Attacks
> In robust mix systems the anonymity of messages may be greatly reduced even if the full path of a message is not controlled by malicious nodes.

**Replay attacks against Hydra-Onions and Cashmere**
The mechanisms by which replay prevention is achieved are security critical, and are the only ones in a mix that requires keeping state. To minimize the space required to keep this state, a mixture of hashing to compress signatures, timestamps to make messages expire, and key rotation to prevent valid decryption are used.

Neither the Hydra-Onion scheme, nor Cashmere, consider the problem of replay prevention, which becomes much more difficult when distributing mixes across multiple nodes.

Both schemes describe a hybrid packet format, with symmetric keys Ki, being encrypted using the public asymmetric key of each mix in Hydra-Onions, or the public key of the whole group in Cashmere. Sadly, this approach is open to attacks.

These two attacks illustrate that the naive local storage of messages processed by each mix does not provide a similar degree of replay prevention as traditional mixes.

A robust replay prevention scheme would need to determine some sort of consensus about whether an onion has already been forwarded among all other mixes who may have seen it, yet such consensus is both difficult to achieve without sacrificing reliability and in the presence of malicious nodes.

**Bridging Honest Hydra-Onion Groups**
The attack relies on an honest group, composed only of honest nodes, being preceded and succeeded by dishonest groups, containing at least one dishonest node. The aim of the adversary in this case is to trace the message being relayed through the honest group, and link it to the corresponding output message.

**Reducing the Anonymity Sets in Cashmere**
Each Pastry node keeps a record of some other nodes distributed in a particular way around the network, and routes messages based on a longest common prefix strategy. Eventually messages should converge toward a node with the appropriate prefix.

A key weakness of Pastry routing, when it comes to overlaying an anonymity system
on it, is that the node receiving the message routed using anycast, is not random.

An adversary can use the above property to degrade the quality of the anonymity provided by the system.

The reduction in anonymity sets can only be used in conjunction with other attacks, since by itself, a sparse mix network is still secure even for small path lengths.

### Ch 6: Defenses
> How reputation management and Byzantine fault tolerance algorithms can be applied to anonymous communication systems to defend against path compromise strategies.

#### Path Compromise and Reputation
A reliable reputation mechanism would be an effective counter to the adversary trying to make itself look more attractive to be selected as a relay mix.

Such a mechanism would allow us to:
* maintain history on node behavior to identify dishonest activity.
* Distribute this information to other mixes in the system.

MorphMix attempted to use local view information to address the shortcomings of using a small set of trusted authorities. However, attackers may be able to model a victim’s local knowledge and manipulate its content to prevent detection.

An important aspect of reputation management is verifying mix capabilities. During path construction, many system protocols have been designed to take into account the bandwidth capacity and current mix load before selecting mixes to use in the relay path.

Malicious nodes are able to make themselves look more attractive by providing specially crafted “honest-looking” selections that not only fool a victim into thinking they are honest, but additionally lower the collusion threshold such that honest nodes are falsely detected as being dishonest.

** Path Compromise Detection and Prevention**
We need a mechanism to detect such types of dishonest behavior and a protocol to disseminate this information reliably to the rest of the mixes in the network.

If each relay group required acknowledgments from multiple mixes in the subsequent relay group, it could be assured that the message was broadcast to at least some set of mixes in the next group. Otherwise it could rebroadcast the message until it has either received a sufficient number of acknowledgments or has reason to believe there is suspicious behavior taking place.

Using a group of trusted servers to monitor statistics of failed connections may shed light on repeated misbehaviors and allow for protocols based on reliable mix reputations.

> It is uncertain if reputation management schemes can be applied to anonymous systems without disrupting mix anonymity and user unlinkability within the system.

#### BFT and Anonymous Communications
> It has been shown that more than 2/3 of the participants in a system must be non-faulty for BFT techniques to hold.

Unfortunately, there are two major limitations of BFT algorithms that complicate their application to anonymous communication systems:

1. First, BFT techniques require replicated state between servers, however, this reduces the privacy of mixes.
2. Second, most BFT techniques assume closed group membership of BFT groups, but anonymous communication systems typically have dynamic structures.

If a system was able to initially form a secure BFT group among participants, they could determine the security protocols necessary to maintain fault tolerance, but how does one initially form a BFT group without first knowing these protocols.

### Ch 7: Conclusion
> Due to the nature of current anonymous network designs, the resources needed for participation are low, so this adversary is a significant threat. Additionally, an attacker that controls mixes in the network can both behave honestly and dishonestly according to the system protocols, making him hard to detect and defend against.