# Compulsion Resistant Anonymous Communications

###### tags: `Tag(HashCloak - Validator Privacy)`
Author(s):George Danezis and Jolyon Clulow

Paper: https://www.freehaven.net/anonbib/cache/ih05-danezisclulow.pdf
(If there are issues, try with incognito mode)

### Table of Contents
[toc]

:::info
>Abstract: We study the effect compulsion attacks, through which an adversary can request a decryption or key from an honest node, have on the security of mix based anonymous communication systems. Some specific countermeasures are proposed that increase the cost of compulsion attacks, detect that tracing is taking place and ultimately allow for some anonymity to be preserved even when all nodes are under compulsion. Going beyond the case when a single message is traced, we also analyze the effect of multiple messages being traced and devise some techniques that could retain some anonymity. Our analysis highlights that we can reason about plausible deniability in terms of the information theoretic anonymity metrics.
:::

## 1 Introduction
Research on anonymous communication and mix networks has in the past concentrated on protecting users’ anonymity against an eavesdropping adversary.
* Assuming a partial eavesdropping adversary, controlling only a small subset of network nodes one can show that very little information is leaked about the correspondence between actual senders and receivers of messages.
* We will study the impact on anonymity if an adversary is able to ask for honest nodes’ private keys or the decryption of arbitrary material.
* In this work we introduce techniques to make compulsion attacks both more expensive, more visible and reduce the information they provide.
* The cost of compulsion attacks is raised by introducing some uncertainty, though multicasting steps, in the routing.
* Often it is assumed than an adversary is *shy* and would prefer the attack not to be known, particularly to the ultimate target.
* We describe techniques that make it difficult to hide the fact that a packet is being traced, through using compulsion traps, loops in the routing that are designed to give advance warning of a successful attack.
* Finally we make the results of an attack much less certain, by allowing both intermediate nodes to plausibly lie, and the final node to pretend to be merely an intermediary.
* An adversary is in these cases not able to find any bit string that would contradict these claims.
* This allows mix systems to provide initiator/receiver anonymity properties, and retain some anonymity, even if all nodes are under compulsion.

## 2 The Compulsion Threat Model
The traditional anonymous communication threat model assumes an adversary that can eavesdrop or even modify traffic on a proportion of the network links. Furthermore it assumes that some proportion of the system nodes are subverted and directly controlled by the adversary.
* This threat model has been used in the context of cryptological research for some time, and can indeed express a wide spectrum of threats.
* On the other hand it suffers some biases from its military origins, that do not allow it to define some very important threats to anonymous communication systems.

Anonymous communication systems are often deployed in environments with a very strong imbalance of power. That makes each of the participants in a network, user or intermediary, individually vulnerable to *compulsion* attacks:
These compulsion attacks are usually expensive for all parties and cannot be too wide or too numerous.

Note that compulsion and coercion cannot be appropriately modeled using the concept of subverted nodes from the traditional threat model.
* The party under compulsion is fundamentally honest but forced to perform certain operations that have an effect which the adversary can observe either directly or by requesting the information from the node under compulsion.
* The information or actions that are collected or performed under coercion are not as trustworthy, from the point of view of an adversary, as those performed by a subverted node since the coerced party can lie and deceive in an attempt not to comply.
* At the same time system designers should not assume that honest parties will always lie when under compulsion simply because they can – it is more prudent to assume that only nodes benefiting from deceiving the adversary are required to lie.
* Good compulsion-resistant designs will maintain their security properties even when all other, non-interested nodes, are cooperating with the adversary

Election protocols are specifically designed to allow voters to freely lie about how they voted, and *receipt-freeness* guarantees that there is no evidence to contradict them.

Other protocols and systems attempt to provide *plausible deniability*, the ability to deceive the coercer and reveal partial or wrong information.
* Forward secure communications: Guarantee the privacy of past conversations, by updating and deleting old keys.
* Forward secure signature schemes: Make sure that signature keys leaked cannot be used to sign valid documents in past epochs.
* The steganographic file system: Allows users to deny the existence of some stored files, while chaffinch allows users to deny the existence of some communication stream.

## 3 Introduction to mix systems
A mix, as introduced by David Chaum, is a network node that hides the correspondence between its inputs and outputs. It does that by receiving encoded inputs that it decodes using a private key, to outputs that are bitwise unlinkable with the inputs.
* Furthermore in order to disrupt the timing characteristics of traffic, several messages are batched together before being decoded and sent out in a random order.

In order to prevent a single corrupt mix compromising the anonymity of all messages traveling though it, a chain of mixes can be used. As long as one of them is honest, the message will be provided with some anonymity. The way one can select the series of mixes is called the topology of the network.
* If only one sequence is possible, we call such a network a cascade.
* And conversely if all possible sequences are permitted we call the network free route.

**Figure 1** illustrates the routing of normal sender anonymous messages, as well as anonymous replies.
* The notation $[x]y$ means that message $x$ is encoded under key $y$.
* The keys with capital letters subscripts $(K_A, . . . , K_F)$ are the public keys of the corresponding nodes.
* While keys with lowercase subscripts $(K_a, . . . , K_f)$ are symmetric session keys.
* The reply block, that the anonymous sender has constructed and included in the message $M$ is the string: $F, [E, K_f , [D, K_e, [K_d, R']_{K_D}]_{K_E}]_{K_F}.$


The figure abstracts away quite a few crucial details, such as the exact encoding scheme, the padding added to keep messages constant length, the duplicate detection mechanisms that discard already seen messages

## 4 Using compulsion to attack mix systems
The security of mix systems relies on the correspondence between inputs and outputs of some mix on the message path to remain hidden. There is no cryptographic way of ensuring this (since it is impossible to prove that information was not leaked), and therefore some degree of trust is placed on the mixes.

Note that there is little value in intercepting messages in the middle of the network since they have already been stripped of information that could lead to their sender.
* Therefore an eavesdropper will try to intercept messages as close to their senders as possible, and then sequentially compel intermediate mixes to decode them.
* After a number of compelled mixes equal to the path length, an adversary will be able to link the targeted sender with the receiver of their messages.

Roger Dingledine, was first to point out that this mechanisms makes reply blocks more vulnerable to attack, than normal messages.
* The attacker has no need to eavesdrop on the network to get a first packet since the reply block is readily available and encodes all information needed to trace its creator.
* Therefore given a single use reply block and a number of compelled nodes equal to the path length, the identity of the user that has sent the message containing the reply block is revealed

Since this is the simplest and most devastating compulsion attack we will concentrate on making it more difficult.

## 5 Protecting mix systems
In this section we present the technical details of the constructions we devised in order to strengthen mixed communications against compulsion attacks and in particular reply blocks, since they are the most vulnerable to this attack. We will make some assumptions about the nature of the mix network, but present our solutions in the context of the abstract mix architecture of **figure 1**.
* The main difference from traditional, client-server, mix networks is the need to distribute the full list of all participating nodes and their keys at all times.
* A failure to distribute the whole list might result in attacks.
* Furthermore this has to be done in a way that is not manipulable by an adversary that tries to flood the network with corrupt nodes.

### 5.1 Multicast steps
First we note the asymmetry between the cost of relaying a message and the cost of compelling a node to reveal secrets.
* Relaying consumes a bit of bandwidth and computation time. On the other hand compelling a node can only happen after a prolonged conflict, legal or physical, with a very high cost for all parties.
* We shall use this asymmetry to protect against compulsion.

A standard message travels through a mix network using a sequence of intermediate mix nodes. The routing information is encrypted to intermediary nodes, and they have to use their secrets in order to decrypt it.
* A way of pushing up the cost of compulsion would be to include some multicast steps into the routing, where the message is sent to a set of nodes at once.
* Only one of these nodes has the necessary secret to correctly decode the message, and continue routing it.
* Therefore the adversary will have to try them one by one until a correct decryption is provided to trace that step.


In the case of Mixminion the nodes receiving a message that cannot be decrypted using their secrets will discard it immediately. As a result an adversary compelling them can be sure that they are not the nodes expected to route the message, since he can ask for all secrets and check for a well formed message.
* For each multicast step, multicasting the message to $K$ nodes, the cost to the mix network during normal operation is $O(K)$.
* On the other hand the adversary will have to query the multicast nodes one by one until one of them decodes the message correctly.
* This requires the adversary to query on average about $K \over 2$ nodes per multicast step until a correct decryption is provided.

If Minx is used to implement *multicast steps*, neither the nodes nor an adversary that compels them can tell if the message was intended for them. They will simply decode it and pass it along.
* This results in an exponential growth of the effort required to process the message, that makes this scheme impractical in the case of Minx.
* At the same time it also means that the adversary has to compel an enormous number of nodes, hoping that one of them will be the final node relaying the message.

### 5.2 Compulsion traps
Some adversaries would prefer to trace messages using compulsion, without the ultimate recipient of the message knowing. We shall therefore assume that our adversary is shy and forces mix nodes not to hide whether they are under compulsion.


We modify the path selection procedure, that we use to select intermediary nodes in the mix network, to provide some advance warning of an attack. The sender of the message or reply block includes itself on the path that their own message is routed through – we call this a *compulsion trap*.
* As a result a reply block that is being traced back would require the attacker to compel the target to decode the message.
* The target can do this and provide a valid message, that still has to get routed to reach its ultimate destination.
* The adversary has no way of knowing which node on the path (aside from when it reaches the last) is the target, while the target gets some advance notice that tracing is taking place.

if an adversary is tracing the message, the target node will provide a decryption, and force the adversary to compel more nodes, until he is eventually led back to the target. This means that more compulsion operations have to be performed by the adversary, than hops when honest nodes relay the message. During normal operation the message is not relayed for more hops than a message that is not using this scheme, and therefore the latency of messages is also not affected by this scheme.

### 5.3 Plausibly deniable routing
As we have seen the normal operation of the mix network does not require the reply message to travel through all nodes specified, but only until the first occurrence of the recipient node. The question then arises: why including the same node again further down in the path? There is no reason, and one can include a random selection of other nodes instead.

The resulting construction, of including in the routing information a tail of random nodes, provides *plausible deniability*. That means that the adversary cannot determine with certainty that a particular node in the path was the intended recipient of the message.

The plausible deniability property proposed can be analyzed as an anonymity property.
* We can at each stage of the compulsion attack assign a probability to each actor in the network of being the receiver.
* Then we use the established measure of anonymity, which is the entropy of this probability distribution, to assess how much plausible deniability is provided

We shall compute the anonymity of the proposed scheme as a function of the compulsion effort of the adversary.
* We denote the number of hosts under compulsion as $k$.
* We assume there are N participants, in a peer-to-peer mix network.
* To simplify things we also assume that the total route length is of a fixed size $l$.
* The real recipient of the message was an equal probability of being at any position, while the other relays are chosen at random.

After $k$ mixes have been forced to decode the reply block, and provide the adversary with the next recipient, the adversary knows $k$ candidates that are equally likely to be the receiver.
* All other $N − k$ nodes also have an equal probability of being the receivers in case he is not in the set of nodes under compulsion.
* This is the case with probability $l−k \over l$, namely the probability the target has chosen a position on the route further away from the part that has been traced back.
* The probability distribution that describes how likely each node is to be the receiver is the following (after $k$ nodes under compulsion):


We can easily calculate the entropy $(\mathcal{H})$ of this distribution $(U(x)$ denotes the uniform distribution over $x$ elements).


This formula is in line with our intuitions.
* When there is no compulsion $(\mathcal{H}$(Pr$[i|0]))$ then the effective anonymity set size is equal to log $N$, since all the network participants are equally likely to have been the receiver.
* The adversary is missing log $N$ bits of information to uniquely identify the receiver.
* When all nodes in the route have been compelled we have $\mathcal{H}$(Pr$[i|l])$ = log $l$, since only the compelled nodes are equally likely to be the ultimate receivers of the message.
* Note that even when all participants are under compulsion, there is still some anonymity left.

## 6 From single message tracing to traffic analysis
Since mixing is taking place, one could try to skew the probability distribution describing the placement of the receiver on the path to gain some security against this attack. This would not add any security against compulsion attacks (beyond making compulsion slower to the same degree as the latency increases), and therefore we shall not discuss this countermeasure any further. Instead we will analyze the security of the base scheme and present in section 6.1 an alternative solution that relies on routing amongst a fixed set of ‘friends’.
* We shall use the setup of **figure 3**, to illustrate how an adversary should decide between tracing one reply block until the end, or tracing two in parallel, when compulsion traps are used.
* We will assume that all reply blocks have a total path length of $l$, and the compulsion trap, the position in the route where the receiver node insert itself, is $k ∈ [1, l −1]$,
* Note that in **figure 3** the last node is always the receiver)
* and it follows a uniform distribution over all positions $k ∼ U(1, l −1)$ and therefore Pr$[k] = 1 \over l−1$.
* On average the compulsion trap point $k$, where the receiver has included himself in the path, will be at:


An attacker tracing two reply blocks in parallel will expect to have to compel $K_1 + K_2$ nodes, where both are independent random variables that follow the uniform distribution above, until it reaches the same recipient node, in both paths.

Since $E[K1 +K2] = 2E[k] = l −1$, a attacker will do marginally better by tracing two reply blocks in parallel.
* Tracing a single reply blocks is guaranteed to pay off after $l$ compulsion steps
* This probability, in our example, equals:
> (from section 2.1.5 of [20], that uses the notation $m(n) = m(m − 1). . .(m − n + 1))$

> Note how the probability of false positives goes quickly towards zero as $N$ grows.

The method we presented that provides *plausible deniability* guarantees some anonymity even when all nodes on the path of one reply have been compelled.
* When two reply blocks to the same receivers are available an adversary reduces greatly the anonymity of the receiver.
* A second couple of nodes, one in each path, that are the same is extremely unlikely as $N$ grows:


We should conclude that given the above models a mix system, even if it implements our countermeasures, can be subject to traffic analysis attacks to uncover the ultimate receiver of reply blocks.
* Therefore we must modify the way nodes are selected on the path to recover some plausible deniability and some anonymity even when faced with overwhelming compulsion.

There are two ways in which one can select nodes to include in the path to enhance anonymity:
1. The first is to route amongst a smaller group of friends.
2. The second is to setup stings, that look to an attacker performing traffic analysis like the final receiver

### 6.1 Routing amongst friends
As the network of mix participants (and therefore nodes) grows, traffic analysis attacks become more certain. The probability a random node is on the path of a reply block twice, becomes smaller, and as a result the probability of the attacker observing a false positive decreases quickly to zero. In order to strengthen the network against such attacks it might be worthwhile to form routes in a non random manner.
* Note that a particular node choosing routes that always include a fixed set of nodes foils the traffic analysis attacks. These set nodes can be arranged in a cascade but this is not necessary: they simply need to be present at some point, before or after the receiver, on the path.

A mixed approach, where a set of fixed nodes is used in conjunction with random nodes seems preferable. The reply block paths are constructed in such a way that between each node from the fixed ‘friends’ set there is a randomly chosen node. This prevents an observer or a corrupt node from trivially inferring the membership of the fixed set.

Using a fixed set of nodes of size $F$, guarantees that under any circumstances, including the tracing of multiply reply blocks, the effective anonymity set size will be at least − log$(F +1)$.
* The additional security provided does not come for free: all $F$ nodes must be on the path, along with another $F$ random nodes.
* Therefore the latency will be on average proportional to the minimum degree of anonymity required.

### 6.2 Setting someone else up
An attacker that naively relies on compulsion in order to infer the final recipient of a reply block must be very cautious. In the case of *compulsion traps* construction, where the final receiver is meant to be twice on the path of the message, it is easy to incriminate another node.

A user can create a path that contains a loop at a different position than itself. For example the path [A, B, C, D, Receiver, E, F, D], contains a loop, that might look to the adversary as a compulsion trap when actually node D is unaware that the message is traveling twice through it (since it does not know all the keys that are necessary to decode the reply block and recognize it at each phase).

## 7 Conclusions
We have presented the effects that compulsion powers might have in undermining the security of a mix network. Our analysis is based on an abstract model of how a mix network works and should be applicable to a large variety of architectures.

Three concrete techniques were presented to make such attacks more expensive for the adversary, tracing the especially vulnerable anonymous reply blocks:
1. Introducing *multicast steps* in the routing increases the number of nodes that have to be compelled to trace, but also makes normal routing more expensive.
2. *Compulsion traps* allow a user to get advance warning of a reply block being traced, and might allow them to eliminate evidence or make tracing more difficult by deleting key material necessary for further tracing [10].
3. Finally *plausibly deniable routing* provides some anonymity even though all nodes on the path of the reply block have been compelled.