Introduction

In this document we consider anonymity properties of a network constructed from mix nodes. We assume that queueing systems of nodes in the network delay messages. This delay is a random variable from the Geometric distribution. Furthermore, we assume that an adversary is able to observe communication links, but can not distinguish between message. Also a fraction of nodes can be corrupted by adversary but in a static and passive manner.

First, we consider a single (uncorrupted) node observed by an adversary. For this scenario we show that the temporal order of two messages which arrived at the node is preserved, with some probability, when they leave the node. We show that the probability $1/2$ is achieved for a large (average) delay per message and a small difference between the arrival times of messages. For prob. $1/2$ the temporal order of outgoing messages is unbiased and random, and hence adversary does not have advantage over the random guessing.

Second, we consider two (uncorrupted) nodes sending messages, through the path of (uncorrupted) mix nodes, to the receiver node which is corrupted by adversary. We also assume that the adversary is able to observe only communication links connecting sender nodes to the first mix node. Here in this more complicated set up, we show that the probability of preserving temporal order of messages can be $1/2$, i.e adversary does not have advantage over random guessing.

Analysis

Single node

Let us assume that messages $1$ and $2$ arrived, respectively, at a node at the time $t_1^{in}$ and $t_2^{in}$, where $t_2^{in} > t_1^{in}$. Assuming that the message $\mu\in\{1,2\}$ was delayed by $r_\mu\Delta$, where $r_\mu$ is random variable from the Geometric distribution $\mathrm{P}q(r)$, we have message $\mu$ leaving the node at time $t^{out}\mu = t^{in}\mu +r\mu\Delta$.
We are interested in the probability $\mathrm{P}(t^{out}_2>t^{out}_1\vert t^{in}_2>t^{in}1)$, i.e. the probability that the order of two messages arrived at the node is preserved. The latter, for the (rescaled) time-difference $\Delta{12}=\frac{t_2^{in} - t_1^{in}}{\Delta}$, is given by

$$ \mathrm{P}(t^{out}2>t^{out}1\vert t^{in}2>t^{in}1)%=\left[1-\frac{q}{1-(1-q)^2}\right]\mathbb{1}\left[\Delta{12}=0\right]\\ =\left[1-\frac{q(1-q)^{\Delta{12}}}{1-(1-q)^2}\right]\mathbb{1}\left[\Delta{12}>0\right]\mathbb{1}\left[\Delta{12}\in\mathbb{N}\right]\\~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~+\left[1-\frac{q(1-q)^{\lfloor\Delta_{12}\rfloor+1 }}{1-(1-q)^2}\right]\mathbb{1}\left[\Delta_{12}>0\right]\mathbb{1}\left[\Delta_{12}\in\mathbb{R}^+\setminus\mathbb{N}\right] $$

$The probability $\mathrm{P}(t^{out}_2>t^{out}_1\vert t^{in}_2>t^{in}1)$ as function of the (rescaled) time-difference $\Delta{12}=\frac{t_2^{in} - t_1^{in}}{\Delta}$, where $t_2^{in} > t_1^{in}$, plotted for $q\in\{1/4,1/2,3/4\}$.$

The probability $\mathrm{P}(t^{out}_2>t^{out}_1\vert t^{in}_2>t^{in}1)$ as function of the (rescaled) time-difference $\Delta{12}=\frac{t_2^{in} - t_1^{in}}{\Delta}$, where $t_2^{in} > t_1^{in}$, plotted for $q\in\{1/4,1/2,3/4\}$.

Two senders and a single path of mixes scenario: analysis of the FIFO attack

A detailed description of the FIFO attack is provided in the Appendix. Here we develop analysis of the FIFO attack for mix nodes with a queuing system.
We assume that messages are removed from the out-queue with probability $q$.
We assume that nodes $1$ and $2$ send messages via the same path going through $k$ nodes.
We assume that each node sends a message to the node $3$ at time $0$. A message in the node $\mu\in\{1,2\}$ is delayed by (at most) $r_\mu\Delta_\mu$, where $r_\mu$ is random variable from the Geometric distribution with parameter $q$, and it is delayed in the link to the node 3 by $d_{\mu 3}$. Hence a message from node $\mu$ arrives to node 3 at the time $t_\mu^{in}=r_\mu\Delta_\mu + d_{\mu3}$.
A message from node $\mu\in\{1,2\}$ is delayed by $\sum_{i=3}^{k+2}r^\mu_i\Delta_i+ \sum_{i=3}^{k+1}d_{ii+1}$, where $r^\mu_i$ is random variable from the Geometric distribution with parameter $q$, while travelling through the $k$ nodes. Thus a message from node $\mu$ exits the last node $k+2$ at the time

$$ t_\mu^{out}=t_\mu^{in} +\sum_{i=3}^{k+2}r^\mu_i\Delta_i+ \sum_{i=3}^{k+1}d_{ii+1}. $$

At time $0$ the nodes $1$ and $2$ send messages, via $k$ nodes, to the receiver node (red filled circle). The latter is controlled by an adversary which is also observing sender nodes.

At time $0$ the nodes $1$ and $2$ send messages, via $k$ nodes, to the receiver node (red filled circle). The latter is controlled by an adversary which is also observing sender nodes.