Traffic Analysis by Adversaries with Partial Visibility

Abstract

Mixnets are a fundamental privacy enhancing technology in the context of anonymous communication that have been extensively studied in terms of a Global passive Adversary (GPA). However a more realistic adversary that captures only a portion of the network have not yet been studied. We call these adversaries “Adversaries with Partial Visibility (APV)" In this paper we provide a framework that models the mixnet-based system and captures different types of Adversaries with Partial Visibility. Each adversary is modeled based on their goals, prior knowledge, and capabilities. We then use this model to perform traffic analysis using the Metropolis-Hastings algorithm in conjunction with a Bayesian inference engine. To the best of our knowledge this is the first time such an adversary is explicitly defined and studied, despite this adversary model being championed as more realistic than global passive adversaries in prior work. We highlight that our framework is flexible and able to encompass a broad range of different adversaries. Naturally, our model also captures the classical global passive adversary (GPA) as a special case.

Appendices

A System Model: Topology

1.1 A.1 Topology

Fig. 6.

Mixnet-based system Model

B Probability of a Trace: Mixes Are Not Chosen Uniformly

Depending in the systems requirements, mixes can be chosen according to a certain weights assigned to them. We now consider the case of mixes not chosen uniformly, but according to an assigned weight. Mix weights can reflect geographic approximation, bandwidth, trust etc. Let’s denote by $w(\mu _{j,l_i})$ the probability of the mix $\mu _{j,l_i}$ being chosen among the set of mixes in layer $l_i$. The probability of each path becomes (Fig. 6):

$$\begin{aligned} \begin{aligned} Pr[P_i] = \left[ \prod _{i =1}^{l} w(\mu _{j_{i},i})\right] Pr[r_i] \end{aligned} \end{aligned}$$

(10)

We can also model the case when each sender $s_i$ only knows a subset of the mixes in each layer $l_j$ ($\mathcal {S}(s_i, l_j)$).

$$\begin{aligned} \begin{aligned} Pr[P_{i} | \mathcal {S}(s_i, l_j)]= \left[ \prod _{j =1}^{l} Pr[\mu _{j,l_j} | \mathcal {S}(s_i, l_j))] \right] Pr[r_i] \end{aligned} \end{aligned}$$

(11)

To compute $\texttt {Pr}[\mu _{j_{i},i}|\mathcal {S}(s_i, l_j)]$, we need to divide the weight of mix $\mu _{j_{i},i}$ by the sum of the weights of the all the mixes in layer $l_i$ that sender $s_i$ knows.

$$\begin{aligned} \begin{aligned} Pr[\mu _{j,l_j} | \mathcal {S}(s_i, l_j)] &= \frac{w(\mu _{j_{i},i})}{w(\mathcal {S}(s_i, l_i))} \\ \end{aligned} \end{aligned}$$

(12)

Therefore:

$$\begin{aligned} \begin{aligned} Pr[P_{i} | \mathcal {S}(s_i, l_j)]= \left[ \prod _{j =1}^{l} \frac{w(\mu _{j_{i},i})}{w(\mathcal {S}(s_i, l_i))} \right] Pr[r_i] \end{aligned} \end{aligned}$$

(13)

Recipient Probability. The recipient probability $Pr[r_i]$ captures any prior knowledge of the adversary about the relationship between a specific sender and a specific receiver, for example if the adversary has a prior knowledge about friendship graphs of certain senders (i.e. sender $s_1$ is twice as likely to send a message to receiver $r_1$ than to a receiver $r_2$).

C Constraints in Sampling

Depending on the network configuration as well as the adversary capabilities, some samples states are not possible therefore are thrown away in the Metropolis Hastings algorithm. In order for our model to be accurate we incorporate two categories of these impossible states:

Ghost Messages: In prior work using the Metropolis-Hasting algorithm [4], the authors acknowledge that one of the limitation of their model is assuming that the adversary starts observing the network when the all mixes are empty. We argue however that this is not realistic. Instead the adversary starts observing the network when there are already messages inside the mixes and those message contribute in hiding an item of interest. We model this scenario by ghost messages. Not to be confused with dummy or cover traffic, ghost messages gm are an output message whose inputs are outside the observation of the adversary and therefore are not items of interests but they do play a role in hiding an item of interest. We therefore add vertices to the subgraph associated with the matrix.

Routing: When an adversary is monitoring or compromising a mix, not only do the have knowledge about the input and output messages of that mix but also the destination and source mixes of those messages. We model this by a list of rules. Any sampled state that is the result of a violations of these rules will be thrown away.

D Table of Notation

Table 1. Summary of notation