The Loopix Anonymity System

Ania Piotrowska Jamie Hayes Tariq Elahi

University College London University College London KU Leuven
Sebastian Meiser George Danezis
University College London University College London
arXiv:1703.00536v1 [cs.CR] 1 Mar 2017

Abstract posing such meta-data leads to significant privacy risks.

Since 2004, Tor [19], a practical manifestation of
We present Loopix, a low-latency anonymous com-
circuit-based onion routing, has become the most popu-
munication system that provides bi-directional ‘third-
lar anonymous communication tool, with systems such
party’ sender and receiver anonymity and unobservabil-
as Herd [32], Riposte [10], HORNET [9] and Vu-
ity. Loopix leverages cover traffic and brief message de-
vuzela [42] extending and strengthening this circuit-
lays to provide anonymity and achieve traffic analysis re-
based paradigm. Message-oriented architectures, based
sistance, including against a global network adversary.
on mix networks, have become unfashionable due to per-
Mixes and clients self-monitor the network via loops of
ceived higher latencies, that cannot accommodate real-
traffic to provide protection against active attacks, and
time communications. However, unless cover traffic is
inject cover traffic to provide stronger anonymity and a
employed, onion routing is susceptible to traffic analy-
measure of sender and receiver unobservability. Service
sis attacks [6] by an adversary that can monitor network
providers mediate access in and out of a stratified net-
links between nodes. Recent revelations suggest that ca-
work of Poisson mix nodes to facilitate accounting and
pabilities of large intelligence agencies approach that of
off-line message reception, as well as to keep the num-
global passive observers—the most powerful form of this
ber of links in the system low, and to concentrate cover
type of adversary.
traffic.
We provide a theoretical analysis of the Poisson mix- However, it is not sufficient to provide strong
ing strategy as well as an empirical evaluation of the anonymity against such an adversary while providing
anonymity provided by the protocol and a functional im- low-latency communication. A successful system addi-
plementation that we analyze in terms of scalability by tionally needs to resist powerful active attacks and use an
running it on AWS EC2. We show that a Loopix relay efficient, yet secure way of transmitting messages. More-
can handle upwards of 300 messages per second, at a over, the system needs to be scalable to a large number
small delay overhead of less than 1.5 ms on top of the de- of clients, which makes classical approaches based on
lays introduced into messages to provide security. Over- synchronized rounds infeasible.
all message latency is in the order of seconds – which For this reason we reexamine and reinvent mix-based
is low for a mix-system. Furthermore, many mix nodes architectures, in the form of the Loopix anonymity sys-
can be securely added to a stratified topology to scale tem. Loopix is resistant against powerful adversaries
throughput without sacrificing anonymity. who are capable of observing all communications and
performing active attacks. We demonstrate that such a
mix architecture can support low-latency communica-
1 Introduction tions that can tolerate small delays, at the cost of using
some extra bandwidth for cover traffic. Delay, cover and
In traditional communication security, the confidential- real traffic can be flexibly traded-off against each other
ity of messages is protected through encryption, which to offer resistance to traffic analysis. Loopix provides
exposes meta-data, such as who is sending messages to ‘third-party’ anonymity, namely it hides the sender-
whom, to network eavesdroppers. As illustrated by re- receiver relationships from third parties, but senders and
cent leaks of extensive mass surveillance programs1 , ex- recipients can identify one another. This simplifies the
1 See
EFF’s guide at https://www.eff.org/files/2014/05/ design of the system, prevents abuse, and provides secu-
29/unnecessary_and_disproportionate.pdf rity guarantees against powerful active adversaries per-

1
forming (n − 1) attacks [38]. 2 Model and Goals
Loopix provides anonymity for private email or instant
messaging applications. For this reason, we adopt and In this section, we first outline the design of Loopix.
leverage an architecture by which users of Loopix are Then we discuss the security goals and types of adver-
associated with service providers that mediate their ac- saries which Loopix guarantees users’ privacy against.
cess to a stratified anonymity system. Such providers
are only semi-trusted2 , and are largely present to ensure 2.1 High-level overview
messages sent to off-line users can be retrieved at a later
time, maintain accounting, and enforce rate limiting. To Loopix is a mix network [7] based architecture allow-
provide maximal flexibility, Loopix only guarantees un- ing users, distinguished as senders and receivers, to route
reliable datagram transmission and is carried over UDP. messages anonymously to each other using an infrastruc-
Reliable transport is left to the application as an end-to- ture of mix servers, acting as relays. These mix servers
end concern [36]. are arranged in a stratified topology [20] to ensure both
horizontal scalability and a sparse topology that concen-
Contributions. In this paper we make the following con- trates traffic on fewer links [11]. Each user is allowed to
tributions: access the Loopix network through their association with
• We introduce Loopix, a new message-based anony- a provider, a special type of mix server. Each provider
mous communication system. It allows for a tun- has a long-term relationship with its users and may au-
able trade-off between latency, genuine and cover thenticate them, potentially bill them or discontinue their
traffic volume, to foil traffic analysis. access to the network. The provider not only serves as an
• As a building block of Loopix we present the Pois- access point, but also stores users’ incoming messages.
son Mix, and provide novel theorems about its prop- These messages can be retrieved at any time, hence users
erties and ways to analyze it as a pool-mix. Pois- do not have to worry about lost messages when they are
son mixing does not require synchronized rounds, off-line. In contrast to previous anonymous messaging
can be used for low-latency anonymous communi- designs [42, 10], Loopix does not operate in determinis-
cation, and provides resistance to traffic analysis. tic rounds, but runs as a continuous system. Additionally,
• We analyze the Loopix system against a strong, Loopix uses the Poisson mixing technique that is based
global passive adversary. Moreover, we show that on the independent delaying of messages, which makes
Loopix provides resistance against active attacks, the timings of packets unlinkable. This approach does
such as trickling and flooding. We also present a not require the synchronization of client-provider rounds
methodology to estimate empirically the security and does not degrade the usability of the system for tem-
provided by particular mix topologies and other se- porarily off-line clients. Moreover, Loopix introduces
curity parameters. different types of cover traffic to foil de-anonymization
• We provide a full implementation of Loopix and attacks.
measure its performance and scalability in a cloud
hosting environment.
2.2 Threat Model
Loopix assumes sophisticated, strategic, and well-
Outline. The remainder of this paper is organized as resourced adversaries concerned with linking users to
follows. In Section 2, we present a brief, high-level their communications and/or their communication part-
overview of Loopix and define the security goals and ner(s). As such, Loopix considers adversaries with three
threat model. In Section 3, we detail the design of Loopix distinct capabilities, that are described next.
and describe Poisson mixes, upon which Loopix is based Firstly, a global passive adversary (GPA) is able to ob-
and introduce their properties. In Section 4, we present serve all network traffic between users and providers and
the analysis of Loopix security properties and discuss the between mix servers. This adversary is able to observe
resistance against traffic analysis and active attacks. In the entire network infrastructure, launch network attacks
Section 5, we discuss the implementation of Loopix sys- such as BGP re-routing [3] or conduct indirect observa-
tem and evaluate the performance. In Section 6, we sur- tions such as load monitoring and off-path attacks [24].
vey related works and compare Loopix with recent de- Thus, the GPA is an abstraction that represents many dif-
signs of anonymity systems. In Section 7, we discuss ferent classes of adversaries able to observe some or all
remaining open problems and possible future work. Fi- information between network nodes.
nally, we conclude in Section 8. Secondly, the adversary has the ability to observe all
of the internal state of some corrupted or malicious mix
2 Details about the threat model are in Section 2.3 relays. The adversary may inject, drop, or delay mes-

2
sages. She also has access to, and operates, using the online honest senders S1 , S2 and honest receivers R1 , R2
secrets of those compromised parties. Furthermore, such of the adversary’s choice.
corrupted nodes may deviate from the protocol, or inject Loopix provides strong sender-receiver third-party
malformed messages. A variation of this ability is where anonymity against the GPA even in collaboration with
the mix relay is also the provider node meaning that corrupt mix nodes. We refer to Section 4.1.3 for our
the adversary additionally knows the mapping between analysis of the unlinkability provided by individual mix
clients and their mailboxes. We say that the provider is nodes, to Section 4.3 for a quantitative analysis of the
corrupt, but is restricted to being honest but curious. In sender-receiver third-party anonymity of Loopix against
Loopix, we assume that a fraction of mix/provider relays the GPA and honest-but-curious mix nodes and to Sec-
can be corrupted or are operated by the adversary. tion 4.2 for our discussion on active attacks.
Finally, the adversary has the ability to participate in
Sender online unobservability. Whether or not senders
the Loopix system as a compromised user, who may de-
are communicating should be hidden from an unautho-
viate from the protocol. We assume that the adversary
rized party. We define sender online unobservability as
can control a limited number of such users—excluding
the inability of an adversary to decide whether a specific
Sybil attacks [21] from the Loopix threat model—since
sender S is communicating with any receiver {S →} or
we assume that honest providers are able to ensure that at
not {S 6→}, for any concurrently online honest sender S
least a large fraction of their users base are genuine users
of the adversary’s choice.
faithfully following all Loopix protocols. Thus, the frac-
Loopix provides strong sender online unobservability
tion of users controlled by the adversary may be capped
against the GPA in collaboration with an insider and even
to a small known fraction of the user base. We further as-
against a corrupt provider. We refer to Section 4.1.2 for
sume that the adversary is able to control a compromised
our analysis of the latter.
user in a conversation with an honest user, and become a
Note, that sender online unobservability directly im-
conversation insider.
plies the notion of sender anonymity where the adver-
An adversary is always assumed to have the GPA ca-
sary tries to distinguish between two possible senders
pability, but other capabilities depend on the adversary.
communicating with a target receiver. Formally, {S1 →
We evaluate the security of Loopix in reference to these
R, S2 6→} or {S1 6→, S2 → R} for any concurrently online
capabilities.
honest senders S1 and S2 and any receiver of the adver-
sary’s choice. Loopix provides sender anonymity even
2.3 Security Goals in light of a conversation insider, i.e., against a corrupt
receiver.
The Loopix system aims to provide the following secu- Receiver unobservability. Whether or not receivers are
rity properties against both passive and active attacks— part of a communication should be hidden from an unau-
including end-to-end correlation and (n − 1) attacks. thorized party. We define receiver unobservability as
These properties are inspired by the formal definitions the inability of an adversary to decide whether there is
from Anoa [2]. All security notions assume a strong ad- a communication from any sender to a specific receiver
versary with information on all users, with up to one bit R {→ R} or not {6→ R}, for any online or offline honest
of uncertainty. In the following we write {S → R} to de- receiver R of the adversary’s choice.
note a communication from the sender S to the receiver
Loopix provides strong receiver unobservability
R, {S →} to denote that there is a communication from S
against the GPA in collaboration with an insider, under
to any receiver and {S 6→} to denote that there is no com-
the condition of an honest provider. We show in Sec-
munication from S to any receiver (S may still send cover
tion 4.1.2 how an honest provider assists the receiver in
messages). Analogously, we write {→ R} to denote that
hiding received messages from third party observers.
there is a communication from any sender to the receiver
Note, that receiver unobservability directly implies the
R and {6→ R} to denote that there is no communication
notion of receiver anonymity where the adversary tries to
from any sender to R (however, R may still receive cover
distinguish between two possible receivers in communi-
messages).
cation with a target sender. Formally, {S → R1 , 6→ R2 }
Sender-Receiver Third-party Unlinkability. The or {6→ R1 , S → R2 } for any concurrently online honest
senders and receivers should be unlinkable by any unau- sender S and any two honest receivers R1 , R2 of the ad-
thorized party. Thus, we consider an adversary that versary’s choice. 3
wants to infer whether two users are communicating. We 3 If the receiver’s provider is honest, Loopix provides a form of
define sender-receiver third party unlinkability as the in- receiver anonymity even in light of a conversation insider: a corrupt
ability of the adversary to distinguish whether {S1 → R1 , sender that only knows the pseudonym of a receiver cannot learn which
S2 → R2 } or {S1 → R2 , S2 → R1 } for any concurrently honest client of a provider is behind the pseudonym.

3
 Users’ loop cover traffic
Symbol Description generates traffic
in two directions
N Mix nodes
P Providers
λL Loop traffic rate (user)
λD Drop cover traffic rate (user)
Storage Storage
λP Payload traffic rate (user)
l Path length (user)
µ The mean delay at mix Mi
λM Loop traffic rate (mix) Storage Storage
Providers offer Mixes can detect
Table 1: Summary of notation offline storage n-1 attacks
when user is offline

Figure 1: The Loopix Architecture. Clients pass the messages

Non-Goals. Loopix provides anonymous unreliable to the providers, which are responsible for injecting traffic into
datagram transmission, as well as facilities the reply of the network. The received messages are stored in individual
sent messages (through add-ons). This choice allows inboxes and retrieved by clients when they are online.
for flexible traffic management, cover traffic, and traffic
shaping. On the downside, higher-level applications us-
ing Loopix need to take care of reliable end-to-end trans-
3.2 Format, Paths and Cover Traffic
mission and session management. We leave the detailed Message packet format. All messages are end-to-end
study of those mechanisms as future work. encrypted and encapsulated into packets to be processed
The provider based architecture supported by Loopix by the mix network. We use the Sphinx packet de-
aims to enable managed access to the network, support sign [15], to ensure that intermediate mixes learn no ad-
anonymous blacklisting to combat abuse [26], and pay- ditional information beyond some routing information.
ments for differential access to the network [1]. How- All messages are padded to the same length, which hides
ever, we do not discuss these aspects of Loopix in this the path length and the relay position and guarantees un-
work, and concentrate instead on the core anonymity fea- linkability at each hop of the messages’ journey over the
tures and security properties described above. network. Each message wrapped into the Sphinx packet
consists of two separate parts: a header H, carrying the
layered encryption of meta-data for each hop, and the
3 The Loopix Architecture encrypted payload ρ of the message. The header pro-
vides each mix server on the path with confidential meta-
In this section we describe the Loopix system in detail— data. The meta-data includes a single element of a cyclic
Figure 1 provides an overview. We also introduce the group (used to derive a shared encryption/decryption
notation used further in the paper, summarized in Sec- key), the routing information and the message authenti-
tion 3. cation code. We extend the Sphinx packet format to carry
additional routing information in the header to each in-
termediate relay, including a delay and additional flags.
3.1 System Setup
The Loopix system consists of a set of mix nodes N and
providers P. We consider a population of U users com-
municating through Loopix, each of which can act as Path selection. As opposed to onion routing, in Loopix
sender and receiver, denoted by indices Si , Ri , where i ∈ the communication path for every single message is cho-
{1, . . . ,U} respectively. Each entity of the Loopix infras- sen independently, even between the same pair of users.
tructure has its unique public-private key pair (sk, pk). In Messages are routed through l layers of mix nodes, as-
order for a sender Si , with a key pair (skSi , pkSi ), to send sembled in a stratified topology [11, 20]. Each mix node
a message to a receiver R j , with a key pair (skR j , pkR j ), is connected only with all the mix nodes from adjacent
the sender needs to know the receiver’s Loopix network layers. This ensures that few links are used, and those
location, i.e., the IP address of the user’s provider and an few links are well covered in traffic; stratified topolo-
identifier of the user, as well as the public encryption key gies mix well in few steps [20]. Providers act as the first
pkR j . We assume this information can be made available and last layer of mix servers. To send a message, the
through a privacy-friendly lookup or introduction system sender encapsulates the routing information described
for initiating secure connection [31]. This is out of scope above into a Sphinx packet which travels through their
for this work. provider, a sequence of mix servers, until it reaches the

4
 Event i − 1 Event i + 1
receiver’s provider and finally the receiver. For each of
those hops the sender samples a delay from an exponen-
Pool i − 1 Pool i Pool i + 1
tial distribution with parameter µ, and includes it in the
routing information to the corresponding relay. Event i Event i + 2

Figure 2: The Poisson Mix strategy mapped to a Pool mix

Sending messages and cover traffic. Users and mix
strategy. Each single message sending or receiving event leads
servers continuously generate a bed of real and cover to a new pool of messages that are exchangeable and indistin-
traffic that is injected into the network. Our design guar- guishable with respect to their departure times.
antees that all outgoing traffic sent by users can by mod-
eled by a Poisson process.
To send a message, a user packages their message into Message storing and retrieving. Providers do not for-
a mix packet and places it into their buffer—a first-in- ward the incoming mix packets to users but instead buffer
first-out (FIFO) queue that stores all the messages sched- them. Users, when online, poll providers or register their
uled to be sent. online status to download a fixed subset of stored mes-
Each sender periodically checks, following the expo- sages, allowing for the reception of the off-line mes-
nential distribution with parameter λ1P , whether there is sages. Recall that cover loops are generated by users
any scheduled message to be sent in their buffer. If there and traverse through the network and come back to the
is a scheduled message, the sender pops this message sender. Cover loops serve as a cover set of outgoing and
from the buffer queue and sends it, otherwise a drop incoming real messages. Whenever a user requests mes-
cover message is generated (in the same manner as a sages, their provider responds with a constant number of
regular message) and sent (depicted as the the four mid- messages, which includes their cover loop messages and
dle blue arrows in Figure 1). Cover messages are routed real messages. If the inbox of a particular user contains
through the sender’s provider and a chain of mix nodes to fewer messages than this constant number, the provider
a random destination provider. The destination provider sends dummy messages to the sender up to that number.
detects the message is cover based on the special drop
flag encapsulated into the packet header, and drops it.
Thus, regardless of whether a user actually wants to send 3.3 The Poisson Mix Strategy
a message or not, there is always a stream of messages Loopix leverages cover traffic to resist traffic analysis
being sent according to a Poisson process Pois(λP ). while still achieving low- to mid-latency. To this end
Moreover, independently from the above, all users Loopix employs a mixing strategy that we call a Pois-
emit separate streams of special indistinguishable types son Mix, to foil observers from learning about the cor-
of cover messages, which also follow a Poisson process. respondences between input and output messages. The
The first type of cover messages are Poisson distributed Poisson Mix is a simplification of the Stop-and-go mix
loops emitted at rate λL . These are routed through the strategy [28]. A similar strategy has been used to model
network and looped back to the senders (the upper four traffic in onion routing servers [13]. In contrast, recall
red arrows in Figure 1), by specifying the sending user as that in Loopix each message is source routed through an
the recipient. These “loops” inspire the system’s name. independent route in the network.
Users also inject a separate stream of drop cover mes- The Poisson Mix functions as follows: mix servers
sages, defined before, following the Poisson distribution listen for the incoming mix packets and received mes-
Pois(λD ). Additionally, each user sends at constant time sages are checked for duplication and decoded using the
a stream of pull requests to its provider in order to re- mix node’s private keys. The detected duplicates are
trieve received messages, described in Section 3.2. dropped. Next, the mix node extracts a subsequent mix
Each mix also injects their own loop cover traffic, packet. Decoded mix packets are not forwarded immedi-
drawn from a Poisson process with rate Pois(λM ), into ately, but each of them is delayed according to a source
the network. Mix servers inject mix packets that are pre-determined delay di . Honest clients chose those de-
looped through a path, made up of a subset of other mix lays, independently for each hop, from an exponential
servers and one randomly selected provider, back to the distribution with a parameter µ. We assume that this pa-
sending mix server, creating a second type of “loop”. rameter is public and the same for all mix nodes.
This loop originates and ends in a mix server (shown as
the lower four green arrows in Figure 1). In Section 4 we
examine how the loops and the drop cover messages help
protect against passive and active attacks. Mathematical model of a Poisson Mix. Honest
clients and mixes generate drop cover traffic, loop traf-
fic, and messaging traffic following a Poisson process.

5
Aggregating Poisson processes results in a Poisson pro- 4 Analysis of Loopix security properties
cess with the sum of their rates, therefore we may model
the streams of traffic received by a Poisson mix as a Pois- In this section we present the analytical and experimental
son process. It is the superposition of traffic streams from evaluation of the security of Loopix and argue its resis-
multiple clients. It has a rate λn depending on the number tance to traffic analysis and active attacks.
of clients and the number of mix nodes.
Since this input process is a Poisson process and each 4.1 Passive attack resistance
message is independently delayed using an exponential
distribution with parameter µ, the Poisson Mix may be 4.1.1 Message Indistinguishability
modeled as an M/M/∞ queuing system – for we have Loopix relies on the Sphinx packet format [15] to provide
a number of well known theorems [4]. We know that bitwise unlinkability of incoming and outgoing messages
output stream of messages is also a Poisson process with from a mix server; it does not leak information about the
the parameter λn as the the input process. We can also number of hops a single message has traversed or the
derive the distribution of the number of messages within total path length; and it is resistant to tagging attacks.
the Poisson Mix [33]: For Loopix, we make minor modifications to Sphinx
to allow auxiliary meta-information to be passed to dif-
Lemma 1. The mean number of messages in the Poisson ferent mix servers. Since all the auxiliary information is
Mix with input Poisson process Pois(λ ) and exponential encapsulated into the header of the packet in the same
delay parameter µ at a steady state follows the Poisson manner as any meta-information was encapsulated in the
distribution Pois (λ /µ). Sphinx design, the security properties are unchanged. An
external adversary and a corrupt intermediate mix node
or a corrupt provider will not be able to distinguish real
Those characteristics give the Poisson Mix its name. messages from cover messages of any type. Thus, the
This allows us to calculate the mean number of messages GPA observing the network cannot infer any information
perfectly mixed together at any time, as well as the prob- about the type of the transmitted messages, and interme-
ability that the number of messages falls below or above diate nodes cannot distinguish real messages, drop cover
certain thresholds. messages or loops of clients and other nodes from each
The Poisson Mix, under the assumption that it approx- other. Providers are able to distinguish drop cover mes-
imates an M/M/∞ queue is a stochastic variant of a pool sage destined for them from other messages, since they
mixing strategy [39]. Conceptually, each message send- learn the drop flag attached in the header of the packet.
ing or receiving leads to a pool within which messages Each mix node learns the delay chosen by clients for this
are indistinguishable due to the memoryless property of particular mix node, but all delays are chosen indepen-
the exponential delay distribution. dently from each other.

Lemma 2 (Memoryless property [33]). For an exponen- 4.1.2 Client-Provider unobservability

tial random variable X with parameter µ holds Pr[X >
In this section, we argue the sender and receiver un-
s + t|X > t] = Pr[X > s].
observability against different adversaries in our threat
model. Users emit payload messages following a Pois-
Intuitively, any two messages in the same pool are son distribution with parameter λP . All messages sched-
emitted next with equal probability – no matter how long uled for sending by the user are placed within a first-in-
they have been waiting. As illustrated in Figure 2, the first-out buffer. According to a Poisson process, a single
receiving event i − 1 leads to a pool of messages i − 1, message is popped out of the buffer and sent, or a drop
until the sending event i. From the perspective of the ad- cover message is sent in case the buffer is empty. Thus,
versary observing all inputs and outputs, all messages in from an adversarial perspective, there is always traffic
the pool i−1 are indistinguishable from each other. Only emitted modeled by Pois (λP ). Since clients send also
the presence of those messages in the pool is necessary to streams of cover traffic messages with rates λL for loops
characterize the hidden state of the mix (not their delay and λD for drop cover messages, the traffic sent by the
so far). Relating the Poisson mix to a pool mix allows client follows Pois (λP + λL + λD ). Thus we achieve per-
us to compute easily and exactly both the entropy metric fect sender unobservability, since the adversary cannot
for the anonymity it provides [37] within a trace (used in tell whether a genuine message or a drop cover message
Section 4.1.3). It also allows us to compute the likelihood is sent.
that an emitted message was any specific input message When clients query providers for received messages,
used in our security evaluation. the providers always send a constant number of messages

6
 l additional messages arrive at the mix before any mes-
sage leaves, and the pool now mixes k + l messages. The
adversary then observes exactly one outgoing message
Inbox I m and tries to correlate it with any of the n + l messages
Inbox II which she has observed arriving at the mix node.
The following lemma is based on the memoryless
Inbox III
property of the Poisson mix. It provides an upper bound
on the probability that the adversary A correctly links the
outgoing message m with one of the previously observed
Figure 3: Provider stores messages destined for assigned arrivals in observation on,k,l .
clients in a particular inbox. When users pull messages from
the mix node, the provider generates cover messages to guar- Theorem 1. Let m1 be any of the initial n messages in
antee that the adversary cannot learn how many messages are the mix node in scenario on,k,l , and let m2 be any of the l
in the users inbox. The messages from the inbox and dummies messages that arrive later. Then
are indistinguishable. k
Pr(m = m1 ) = , (1)
n(l + k)
to the client. If the number of messages in client’s inbox 1
Pr(m = m2 ) = . (2)
is smaller than a constant threshold, the provider gen- l +k
erates additional dummy messages. Thus, the adversary Note that the last l messages that arrived at the mix
observing the client-provider connection, as presented on node have equal probabilities of being the outgoing mes-
Figure 3, cannot learn how many messages were in the sage m, independently of their arrival times. Thus, the
user’s inbox. Note that, as long as the providers are hon- arrival and departure times of the messages cannot be
est, the protection and receiver unobservability is perfect correlated, and the adversary learns no additional infor-
and the adversary cannot learn any information about the 1
mation by observing the timings. Note that l+k is an
inbox and outbox of any client. upper bound on the probability that the adversary A cor-
If the provider is dishonest, then they are still uncer- rectly links the outgoing message to an incoming mes-
tain whether a received message is genuine or the result sage. Thus, continuous observation of a Poisson mix
of a client loop – something that cannot be determined leaks no additional information other than the number
from their bit pattern alone. However, further statistical messages present in the mix. We leverage those results
attacks may be possible, and we leave quantifying exact from about a single Poisson Mix to simulate the informa-
security against this threat model as future work. tion propagated withing a the whole network observed by
the adversary (c.f. Section 4.3).
We quantify the anonymity of messages in the mix
node empirically, using an information theory based met-
4.1.3 Poisson mix security ric introduced in [37, 17]. We record the traffic flow
for a single mix node and compute the distribution of
We first show that a single honest Poisson mix provides a probabilities that the outgoing message is the adversary’s
measure of sender-receiver unlinkability. From the prop- target message. Given this distribution we compute the
erties of Poisson mix, we know that the number of mes- value of Shannon entropy (see Appendix A), a measure
sages in the mix server at a steady state depends on the of unlinkability of incoming to outgoing messages. We
ratio of the incoming traffic (λ ) and the delay parameter compute this using the simpy package in Python. All
(µ) (from Section 3.3). The number of messages in each data points are averaged over 50 simulations.
mix node at any time will on average be λµ . However, an Figure 4 depicts the change of entropy against an in-
adversary observing the messages flowing into and out creasing rate of incoming mix traffic λ . We simulate the
of a single mix node could estimate the exact number of dependency between entropy and traffic rate for differ-
messages within a mix with better accuracy – hindered ent mix delay parameter µ by recording the traffic flow
only by the mix loop cover traffic. and changing state of the mix node’s pool. As expected,
We first consider, conservatively, the case where a mix we observe that for a fixed delay, the entropy increases
node is not generating any loops and the adversary can when the rate of traffic increases. Higher delay also re-
count the exact number of messages in the mix. Let us sults in an increase in entropy, denoting a larger potential
define on,k,l as an adversary A observing a mix in which anonymity set, since more messages are mixed together.
n messages arrive and are mixed together. The adversary In case the mix node emits loop cover traffic, the ad-
then observes an outgoing set of n − k messages and can versary with observation on,k,l , tries to estimate the prob-
infer that there are now k < n messages in the mix. Next, ability that the observed outgoing message is a particular

7
 16 to the indistinguishability of messages and the memory-
= 0.02 less property of the Poisson mixing strategy. We now in-
14
12 = 0.2 vestigate how Loopix can protect users’ communications
10 against active adversaries conducting the (n − 1) attack.
Entropy

8 =2
6 = 20 4.2.1 Active attacks
4
2 = 200 We consider an attack at a mix node where an adversary
0
100 150 200 250 300 350 400 450 500 blocks all but a target message from entering in order
Rate of incoming traffic ( ) to follow the target message when it exits the mix node.
This is referred to as an (n-1) attack [38].
Figure 4: Entropy versus the changing rate of the incoming A mix node needs to distinguish between an active at-
traffic for different delays with mean µ1 . In order to measure tack and loop messages dropped due to congestion. We
the entropy we run a simulation of traffic arriving at a single assume that each mix node chooses some public param-
Loopix mix node. eter r, which is a fraction of the number of loops that
are expected to return. If the mix node does not see this
fraction of loops returning they alter their behavior. In
target message she observed coming into the mix node. extremis such a mix could refuse to emit any messages
An outgoing message can be either input message or a – but this would escalate this attack to full denial-of-
loop message generated by the mix node – resulting in service. A gentler approach involves generating more
additional uncertainty for the adversary. cover traffic on outgoing links [16].
Theorem 2. Let m1 be any of the initial n messages in To attempt an (n-1) attack, the adversary could simply
the mix node in scenario on,k,l , and let m2 be any of the block all incoming messages to the mix node except for a
l messages that arrive later. Let λM denote the rate at target message. The Loopix mix node can notice that the
which mix node generates loop cover traffic. Then, self-loops are not returning and deduce it is under attack.
Therefore, an adversary that wants to perform a stealthy
k µ attack has to be judicious when blocking messages, to
Pr(m = m2 ) = · ,
n (l + k)µ + λM ensure that a fraction r of loops return to the mix node,
µ i.e. the adversary must distinguish loop cover traffic from
Pr(m = m1 ) = .
(l + k)µ + λM other types of traffic. However, traffic generated by mix
loops is indistinguishable from other network traffic and
We refer to Appendix A for the proof. We conclude they cannot do this better than by chance. Therefore
that the loops generated by the mix node obfuscate the given a threshold r = λsM , s ∈ R>1 of expected returning
adversary’s view and decrease the probability of success- loops when a mix observes fewer returning it deploys ap-
fully linking input and output of the mix node. In Sec- propriate countermeasures.
tion 4.2 we show that those types of loops also protect We analyze this strategy: since the adversary cannot
against active attacks. distinguish loops from other traffic the adversary can do
no better than block traffic uniformly such that a fraction
4.2 Active-attack Resistance R = λs = λR +λs
M
enter the mix, where λR is the rate of
incoming traffic that is not the mix node’s loops. If we
Lemma 1 gives the direct relationship between the ex-
assume a steady state, the target message can expect to
pected number of messages in a mix node, the rate of in- λR
coming traffic, and the delay induced on a message while be mixed with s·µ messages that entered this mix, and
λM
transiting through a mix. By increasing the rate of cover µ loop messages generated at the mix node. Thus, the
traffic, λD and λL , users can collectively maintain strong probability of correctly blocking a sufficient number of
anonymity with low message delay. However, once the messages entering the mix node so as not to alter the be-
volume of real communication traffic λP increases, users havior of the mix is:
can tune down the rate of cover traffic in comparison 1 sµ
to the real traffic, while maintaining a small delay and Pr(x = target) = =
λR /s · µ + λM /µ sλM + λR
be confident their messages are mixed with a sufficient
number of messages. Due to the stratified topology, providers are able to dis-
In the previous section, we analyze the security prop- tinguish mix loop messages sent from other traffic, since
erties of Loopix when the adversary observes the state of they are unique in not being routed to or from a client.
a single mix node and the traffic flowing through it. We This is not a substantial attack vector since mix loop
showed, that the adversary’s advantage is bounded due messages are evenly distributed among all providers, of

8
which a small fraction are corrupt and providers do not 1.0
learn which mix node sent the loop to target it.
0.8

Likelihood difference
0.6
4.3 End-to-End Anonymity Evaluation 0.4

We evaluate the sender-receiver third-party unlinkability 0.2

of the full Loopix system through an empirical analysis
0.0
of the propagation of messages in the network. Our key 2.0 1.8 1.6 1.4 1.2 1.0 0.8 0.6 0.4 0.2
Rate of the delay ( )
metric is the expected difference in likelihood that a mes-
sage leaving the last mix node is sent from one sender
in comparison to another sender. Given two probabilities Figure 5: Likelihood difference ε depending on the delay pa-
rameter µ of mix nodes. We use λ = 2, a topology of 3 layers
p0 = Pr[S0 ] and p1 = Pr[S1 ] that the message was sent by
with 3 nodes per layer and no corruption.
senders S0 and S1 , respectively, we calculate

ε = |log (p0 /p1 )| . (3) 1.0

0.8

Likelihood difference
To approximate the probabilities p0 and p1 , we pro-
0.6
ceed as follows. We simulate U = 100 senders that gen-
erate and send messages (both payload and cover mes- 0.4
sages) with a rate λ = 2. Among them are two challenge 0.2
senders S0 and S1 that send payload messages at a con-
0.0
stant rate, i.e, they add one messages to their sending 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
buffer every time unit. Number of layers (l)
Whenever a challenge sender S0 or S1 sends a payload
message from its buffer, we tag the message with a la- Figure 6: Likelihood difference ε depending on the number of
bel S0 or S1 , respectively. All other messages, including layers of mix nodes with 3 mix nodes per layer. We use λ = 2,
messages from the remaining 98 clients and the cover µ = 1, and no corruption.
messages of S0 and S1 are unlabeled. At every mix we
track the probability that an outgoing message is labeled
4.3.1 Results
S0 or S1 , depending on the messages that entered the mix
node and the number of messages that already left the We compare our metric for different parameters: depend-
mix node, as in Theorem 1. Thus, messages leaving a ing on the delay parameter µ, the number of layers in our
mix node carry a probability distribution over labels S0 , topology l and the percentage of corrupted mix nodes in
S1 , or ‘unlabeled’. Corrupt mix nodes, assign to outgoing the network. All of the below simulations are averaged
messages their input distributions. The probabilities nat- over 100 repetitions and the error bars are defined by the
urally add up to 1. For example, a message leaving a mix standard deviation.
can be labeled as {S0 : 12%, S1 : 15%, unlabeled : 73%}.
In a burn-in phase of 2500 time units, the 98 senders
Delay. Increasing the average delay (by decreasing pa-
without S0 or S1 communicate. Then we start the two
rameter µ) with respect to the rate of message sending
challenge senders and then simulate the network for an-
λ immediately increases anonymity (decreases ε) (Fig-
other 100 time units, before we compute the expected
ure 5). For µ = 2.0 and λ /µ = 1, Loopix still provides a
difference in likelihood metric. We pick a final mix node
weak form of anonymity. As this fraction increases, the
and using probabilities of labels S0 and S1 for any mes-
log likelihood ratio grow closer and closer to zero. We
sage in the pool we calculate ε as in Equation (3).
consider values λ /µ ≥ 2 to be a good choice in terms of
This is a conservative approximation: we tell the ad-
anonymity.
versary which of the messages leaving senders S0 and S1
are payload messages; and we do not consider mix or
client loop messages confusing them. 4 However, when Number of layers. By increasing the number of layers
we calculate our anonymity metric at a mix node we as- of mix nodes, we can further strengthen the anonymity of
sume this mix node to be honest. Loopix users. As expected, using only one or two layers
4 The soundness of our simplification can be seen by the fact that we
of mix nodes leads to high values of adversary advantage
could tell the adversary which messages are loops and the adversary
ε. An increasing number of layers ε approaches zero
could thus ignore them. This is equivalent to removing them, as an (Figure 6). We consider a number of 3 or more layers
adversary could also simulate loop messages. to be a good choice. We believe the bump between 5–8

9
 10 300
All traffic

Messages processed per sec

8 250 Payload traffic
Likelihood difference

200
6
150
4
100
2 50
0 00 20 40 60 80 100 120 140 160
0 10 20 30 40 50 60 70 80 90 100
Rate of sending per client ( ) per minute
Percentage of corrupt mix nodes

Figure 7: Likelihood difference ε depending on the percentage Figure 8: Overall bandwidth and good throughput per second
of (passively) corrupted mix nodes. We use λ = 2, µ = 1 and for a single mix node.
a topology of 3 layers with 3 nodes per layer.

on a PID controller and we drop messages when the size

layers is due to messages not reaching latter layers within of the queue reaches a (high) threshold.
100 time units, however results from experiments with
increased duration do not display such a bump.
Experimental Setup. We present an experimental per-
formance evaluation of the Loopix system running on
Corruption. Finally, we analyze the impact that cor-
the AWS EC2 platform. All mix nodes and providers
rupt mix nodes have on the adversary advantage ε (Fig-
run as separate instances. Mix nodes are deployed on
ure 7). We assume that the adversary randomly corrupts
m4.4xlarge instances running EC2 Linux on 2.3 GHz
mix nodes. Naturally, the advantage ε increases with the
machines with 64 GB RAM memory. Providers, since
percentage of corrupt mix nodes in the network. In a
they handle more traffic, storage and operations, are de-
real-world deployment we do not expect a large fraction
ployed on m4.16xlarge instances with 256 GB RAM.
of mix nodes to be corrupt. While the adversary may
We select large instances to ensure that the providers are
be able to observe the entire network, to control a large
not the bottleneck of the bandwidth transfer, even when
number of nodes would be more costly.
users send messages at a high rate. This reflects real-
world deployments where providers are expected to be
5 Performance Evaluation well-resourced. We also run one m4.16xlarge instance
supporting 500 clients. We highlight that each client runs
Implementation. We implement the Loopix system as a separate process and uses a unique port for trans-
prototype in 4000 lines of Python 2.7 code for mix porting packets. Thus, our performance measurements
nodes, providers and clients, including unit-tests, de- are obtained by simulating a running system with inde-
ployment, and orchestration code. Loopix source code pendent clients8 . In order to measure the system per-
is available under an open-source license5 . We use the formance, we run six mix nodes, arranged in a stratified
Twisted 15.5.0 network library for networking; as well topology with three layers, each layer composed of two
as the Sphinx mix packet format6 and the cryptographic mix nodes. Additionally, we run four providers, each
tools from the petlib7 library. We modify Sphinx to serving approximately 125 clients. The delays of all
use NIST/SEGS-p224 curves and to accommodate ad- the messages are drawn from an exponential distribution
ditional information inside the packet, including the de- with parameter µ, which is the same for all mix servers
lay for each hop and auxiliary flags. We also optimize its in the network. All measurements are take from network
implementation leading to processing times per packet of traffic dumps using tcpdump.
less than 1ms.
The most computationally expensive part of Loopix
is messages processing and packaging, which involves Bandwidth. First, we evaluate the maximum band-
cryptographic operations. Thus, we implement Loopix width of mix nodes by measuring the rate at which a
as a multi-thread system, with cryptographic processing single mix node processes messages, for an increasing
happening in a thread pool separated from the rest of the overall rate at which users send messages.
operations in the main thread loop. To recover from con- We set up the fixed delay parameter µ = 1000 (s.t.
gestion we implement active queue management based the average delay is 1 ms). We have 500 clients actively
5 Public Github repository URL obscured for review. 8 Other works, e.g. [41, 42], report impressive evaluations in terms
6 http://sphinxmix.readthedocs.io/en/latest/
of scale, but in fact are simple extrapolations and not based on empirical
7 http://petlib.readthedocs.org results.

10
 4.0 Gamma distribution fit
0.6
3.5
Latency Overhead (ms)

3.0 0.5
2.5
2.0 0.4

Frequency
1.5
1.0 0.3
0.5 0.2
0.0
0 50 100 150 200 250 300 350 400 450 500 0.1
Number of clients
0.00 1 2 3 4 5 6 7
Figure 9: Latency overhead of the system where 50 to 500 Latency (s)
users simultaneously send traffic at rates λP = λL = λD = 10
per minute and mix nodes generate loop cover traffic at rate
λM = 10 per minute. We assume that there is not additional Figure 10: End-to-end latency histogram measured through
delay added to the messages by the senders. timing mix node loops. We run 500 users actively commu-
nicating via Loopix at rates λP = λL = λD = 60 per minute and
λM = 60 per minute. The delay for each hop is drawn from
Exp(2). The latency of the message is determined by the as-
sending messages at rate λ each, which is the sum of pay-
signed delay and fits the Gamma distribution with mean 1.93
load, loop and drop rates, i.e., λ = Pois(λL + λD + λP ). and standard deviation 0.87.
We start our simulation with parameters λL = λD = 1
and λP = 3 messages per minute for a single client. Mix
nodes send loop cover traffic at rate starting from λM = 1.
is dominated by the scalar multiplication of an elliptic
Next, we periodically increase each Poisson rate by an-
curve point and symmetric cryptographic operations. For
other 2 messages per minute.
the end-to-end measurement, we run Loopix with a setup
In order to measure the overall bandwidth, i.e. the where all users have the same rates of sending real and
number of all messages processed by a single mix node, cover messages, such that λP = λD = λL = 10 messages
we use the network packet analyzer tcpdump. Since per minute and mix servers generate loops at rate λM =
real and cover message packets are indistinguishable, we 10 messages per minute. All clients set a delay of 0.0
measure the good throughput by encapsulating an addi- seconds for all the hops of their messages – to ensure
tional, temporary, typeFlag in the packet header for this we only measure the system overhead, not the artificial
evaluation, which leaks to the mix the message type— mixing delay.
real or cover—and is recorded.
Figure 9 shows that increasing the number of online
Figure 8 illustrates the number of total messages and
clients, from 50 to 500, raises the latency overhead by
the number of payload messages that are processed by
only 0.37 ms. The variance of the processing delay in-
a single mix node versus the overall sending rate λ of a
creases with the amount of traffic in the network, but
single user. We observe that the bandwidth of the mix
more clients do not significantly influence the average
node increases linearly until it reaches around 225 mes-
latency overhead. Neither the computational power of
sages per second. After that point the performance of
clients nor mix servers nor the communication between
the mix node stabilizes and we observe a much smaller
them seem to become bottlenecks for these rates. Those
growth. We highlight that the amount of real traffic in the
results show that the increasing number of users in the
network depends on the parameter λP within λ . A client
network does not lead to any bottleneck for our parame-
may chose to tune up the rate of real messages sent, by
ters. The measurements presented here are for a network
tuning down the rate of loops and drop messages – at
of 6 mix nodes, however we can increase the system ca-
the potential loss of security in case less cover traffic is
pacity by adding more servers. Thus, Loopix scales well
present in the system overall. Thus, depending on the
for an increasing number of users.
size of the honest user population in Loopix, we can in-
crease the rate of goodput. We also investigate how increasing the delays through
Poisson Mixing with µ = 2 affects the end-to-end la-
tency of messages. We measure this latency through tim-
Latency Overhead & Scalability. End-to-end latency ing mix heartbeat messages traversing the system. Fig-
overhead is the cost of routing and decoding relayed mes- ure 10 illustrates that when the mean delay 1/µ sec. is
sages, without any additional artificial delays. We run higher than the processing time (∼ 1 ms − 2 ms), the end-
simulations to measure its sensitivity to the number of to-end latency is determined by this delay, and follows
users participating in the system. the Gamma distribution with parameter being the sum of
We measure the time needed to process a single packet the exponential distribution parameter over the number
by a mix node, which is approximately 0.6 ms. This cost of servers on the path. The good fit to a gamma distribu-

11
tion provides evidence that the implementation of Loopix users write their messages into a database, without re-
is faithful to the queuing theory models our analysis as- vealing the row into which they wrote to the database
sumes. server. Riposte enjoys low communication-overhead and
protects against traffic analysis and denial of service at-
tacks, but requires long epochs and a small number of
6 Related Work clients writing into the database simultaneously. In con-
trast to Loopix, it is suitable for high-latency applica-
All anonymous communication designs share the com- tions.
mon goal of hiding users’ communication patterns Dissent [8], based on DC-networks [8], offers re-
from adversaries. Simultaneously minimizing latency silience against a GPA and some active attacks, but at sig-
and communication overhead while still providing high nificantly higher delays and scales to only several thou-
anonymity is challenging. We survey other anonymous sand clients.
systems and compare them with Loopix (a summary is Riffle [30] introduces a new verifiable shuffle tech-
provided in Table 2). nique to achieve sender anonymity. Using PIR, Rif-
fle guarantees receiver anonymity in the presence of an
Early designs. Designs based on Chaum’s mixes [7] active adversary, as well as both sender and receiver
can support both high and low latency communication; anonymity, but it cannot support a large user base. Riffle
all sharing the basic principles of mixing and layered also utilizes rounds protect traffic analysis attacks. Riffle
encryption. Mixmaster [34] supports sender anonymity is not designed for Internet-scale anonymous communi-
using messages encryption but does not ensure receiver cation, like Loopix, but for supporting intra-group com-
anonymity. Mixminion [14] uses fixed sized messages munication.
and supports anonymous replies and ensures forward Finally, Atom [29] combines a number of novel tech-
anonymity using link encryption between nodes. As a niques to provide mid-latency communication, strong
defense against traffic analysis, but at the cost of high- protection against passive adversaries and uses zero
latencies, both designs delay incoming messages by col- knowledge proofs between servers to resist active at-
lecting them in a pool that is flushed every t seconds (if tacks. Performance scales horizontally, however latency
a fixed message threshold is reached). comparisons between Loopix and Atom are difficult due
In contrast, Onion routing [25] was developed for low- to the dependence on pre-computation in Atom. Un-
latency anonymous communication. Similar to mix de- like Loopix, Atom is designed for latency tolerant uni-
signs, each packet is encrypted in layers, and is decrypted directional anonymous communication applications with
by a chain of authorized onion routers. Tor [19], the only sender anonymity in mind.
most popular low-latency anonymity system, is an over-
lay network of onion routers. Tor protects against sender- 7 Discussion & Future Work
receiver message linking against a partially global adver-
sary and ensures perfect forward secrecy, integrity of the As shown in Section 4.1, the security of Loopix heavily
messages, and congestion control. However, Tor is vul- depends on the ratio of the rate of traffic sent through the
nerable to traffic analysis attacks, if an adversary can ob- network and the mean delay at every mix node. Opti-
serve the ingress and egress points of the network. mization of this ratio application dependent. For appli-
Recent designs. Vuvuzela [42] protects against both cations with small number of messages and delay toler-
passive and active adversaries as long as there is one ance, a small amount of cover traffic can guarantee secu-
honest mix node. Since Vuvuzela operates in rounds, of- rity.
fline users lose the ability to receive messages and all Loopix achieves its stated security and performance
messages must traverse a single chain of relay servers. goals. However, there are many other facets of the de-
Loopix does not operate in rounds, allows off-line users sign space that have been left for future work. For in-
to receive messages and uses parallel mix nodes to im- stance, reliable messages delivery, session management,
prove the scalability of the network. and flow control while all avoiding inherent risks, such as
Stadium [41] and AnonPop [23] refine Vuvuzela; both statistical disclosure attacks [12], are all fruitful avenues
operating in rounds making the routing of messages de- of pursuit.
pendent on the dynamics of others. Stadium is scalable, We also leave the analysis of replies to messages as
but it lacks offline storage, whereas AnonPop does pro- future work. Loopix currently allows two methods if
vide offline message storage. Loopix also provides both the receiver does not already know the sender a priori:
properties, and because it operates continuously avoids we either attach the address of the sender to each mes-
user synchronization issues. sage payload, or provide a single-use anonymous reply
Riposte [10] is based on a write PIR scheme in which block [14, 15], which enables different use-cases.

12
 Low Low Communication Scalable Asynchronous Active Offline Resistance
Latency Overhead Deployment Messaging† Attack Resistant Storage* to GPA
Loopix X X X X X X X
Dissent [43] X X
Vuvuzela [42] X X X
Stadium [41] X X X X
Riposte [10] X X X
Atom [29] X X X X
Riffle [30] X X X X
AnonPoP [23] X X X X
Tor [19] X X X X

Table 2: Comparison of popular anonymous communication systems. By *, we mean if the design intentionally incorporates
provisions for delivery of messages when a user is offline, perhaps for a long period of time. By †, we mean that the system
operates continuously and does not depend on synchronized rounds for its security properties and users do not need to coordinate
to communicate together.

The Loopix architecture deliberately relies on estab- best-of-breed techniques: we provide definitions inspired
lished providers to connect to and authenticate end-users. by AnoA [2] for our security properties; improve the
This architecture brings a number of potential benefits, analysis of simplified variants of stop-and-go-mixing
such as resistance to Sybil attacks, enabling anonymous as a Poisson mix [28]; we use restricted topologies
blacklisting [26] and payment gateways [1] to mitigate to promote good mixing [20]; we deploy modern ac-
flooding attacks and other abuses of the system, and pri- tive attack mitigations based on loops [16]; and we use
vacy preserving measurements [22, 27] about client and modified modern cryptographic packet formats, such as
network trends and the security stance of the system. All Sphinx [15], for low information leakage. Our design,
of this analysis is left for future work. security and performance analysis, and empirical eval-
It is also apparent that an efficient and secure pri- uation shows they work well together to provide strong
vate lookup system, one that can deliver network state security guarantees.
and keying information to its users, is necessary to sup-
The result of composing these different techniques –
port modern anonymous communications. Proposals
previously explored as separate and abstract design op-
of stand-alone ‘presence’ systems such as DP5 [5] and
tions – is a design that is strong against global net-
MP3 [35] provide efficient lookup methods, however,
work level adversaries without the very high-latencies
we anticipate that tight integration between the lookup
traditionally associated with mix systems [34, 14].
and anonymity systems may bring mutual performance
Thus, Loopix revitalizes message-based mix systems and
and security benefits, which is another avenue for future
makes them competitive once more against onion rout-
work.
ing [25] based solutions that have dominated the field
of anonymity research since Tor [19] was proposed in
8 Conclusion 2004.

The Loopix mix system explores the design space fron-

tiers of low-latency mixing. We balance cover traffic
and message delays to achieve a tunable trade-off be-
tween real traffic and cover traffic, and between latency Acknowledgments We thank Claudia Diaz and Mary
and good anonymity. Low-latency incentivizes early Maller for the helpful discussions. In memory of Len
adopters to use the system, as they benefit from good Sassaman. This work was supported by NSERC through
performance. Moreover, the cover traffic introduced by a Postdoctoral Fellowship Award, the Research Coun-
both clients and mix servers provides security in the pres- cil KU Leuven: C16/15/058, the European Commis-
ence of a smaller user-base size. In turn this promotes sion through H2020-DS-2014-653497 PANORAMIX,
growth in the user-base leading on one hand to greater the EPSRC Grant EP/M013-286/1, and the UK Govern-
security [18], and on the other a tuning down of cover ment Communications Headquarters (GCHQ), as part of
traffic over time. University College London’s status as a recognised Aca-
Loopix is the first system to combine a number of demic Centre of Excellence in Cyber Security Research.

13
References Symposium on Security and Privacy (2015), IEEE,
pp. 321–338.
[1] A NDROULAKI , E., R AYKOVA , M., S RIVATSAN ,
S., S TAVROU , A., AND B ELLOVIN , S. M. PAR: [11] DANEZIS , G. Mix-networks with restricted routes.
Payment for Anonymous Routing. In Privacy En- In International Workshop on Privacy Enhancing
hancing Technologies, 8th International Sympo- Technologies (2003), Springer, pp. 1–17.
sium, PETS 2008, Leuven, Belgium, July 23-25,
2008, Proceedings (2008), pp. 219–236. [12] DANEZIS , G. Statistical disclosure attacks. In
Security and Privacy in the Age of Uncertainty.
[2] BACKES , M., K ATE , A., M ANOHARAN , P., Springer, 2003, pp. 421–426.
M EISER , S., AND M OHAMMADI , E. AnoA: A
Framework for Analyzing Anonymous Communi- [13] DANEZIS , G. The Traffic Analysis of Continuous-
cation Protocols. In Computer Security Founda- Time Mixes. In Privacy Enhancing Technologies,
tions Symposium (CSF), 2013 IEEE 26th (2013), 4th International Workshop, PET 2004, Toronto,
IEEE, pp. 163–178. Canada, May 26-28, 2004, Revised Selected Papers
(2004), pp. 35–50.
[3] BALLANI , H., F RANCIS , P., AND Z HANG , X. A
study of prefix hijacking and interception in the In- [14] DANEZIS , G., D INGLEDINE , R., AND M ATHEW-
ternet. In ACM SIGCOMM Computer Communica- SON , N. Mixminion: Design of a type III anony-
tion Review (2007), vol. 37, ACM, pp. 265–276. mous remailer protocol. In Security and Privacy,
2003. Proceedings. 2003 Symposium on (2003),
[4] B OLCH , G., G REINER , S., DE M EER , H., AND IEEE, pp. 2–15.
T RIVEDI , K. S. Queueing networks and Markov
chains: modeling and performance evaluation with [15] DANEZIS , G., AND G OLDBERG , I. Sphinx: A
computer science applications. John Wiley & Sons, compact and provably secure mix format. In Se-
2006. curity and Privacy, 2009 30th IEEE Symposium on
(2009), IEEE, pp. 269–282.
[5] B ORISOV, N., DANEZIS , G., AND G OLDBERG , I.
DP5: A private presence service. Proceedings on [16] DANEZIS , G., AND S ASSAMAN , L. Heartbeat traf-
Privacy Enhancing Technologies 2015, 2 (2015), fic to counter (n-1) attacks: red-green-black mixes.
4–24. In Proceedings of the 2003 ACM workshop on Pri-
[6] C AI , X., Z HANG , X. C., J OSHI , B., AND J OHN - vacy in the electronic society (2003), ACM, pp. 89–
SON , R. Touching from a distance: Website finger-
93.
printing attacks and defenses. In Proceedings of the
[17] D IAZ , C., S EYS , S., C LAESSENS , J., AND P RE -
2012 ACM conference on Computer and communi-
NEEL , B. Towards measuring anonymity. In In-
cations security (2012), ACM, pp. 605–616.
ternational Workshop on Privacy Enhancing Tech-
[7] C HAUM , D. Untraceable Electronic Mail, Re- nologies (2002), Springer, pp. 54–68.
turn Addresses, and Digital Pseudonyms. Commun.
ACM 24, 2 (1981), 84–88. [18] D INGLEDINE , R., AND M ATHEWSON , N.
Anonymity Loves Company: Usability and the
[8] C HAUM , D. The dining cryptographers problem: Network Effect. In WEIS (2006).
Unconditional sender and recipient untraceability.
Journal of cryptology 1, 1 (1988), 65–75. [19] D INGLEDINE , R., M ATHEWSON , N., AND
S YVERSON , P. Tor: The second-generation onion
[9] C HEN , C., A SONI , D. E., BARRERA , D., router. Tech. rep., DTIC Document, 2004.
DANEZIS , G., AND P ERRIG , A. HORNET: High-
speed Onion Routing at the Network Layer. In Pro- [20] D INGLEDINE , R., S HMATIKOV, V., AND S YVER -
ceedings of the 22nd ACM SIGSAC Conference on SON , P. Synchronous batching: From cascades to
Computer and Communications Security, Denver, free routes. In International Workshop on Privacy
CO, USA, October 12-6, 2015 (2015), pp. 1441– Enhancing Technologies (2004), Springer, pp. 186–
1454. 206.

[10] C ORRIGAN -G IBBS , H., B ONEH , D., AND M AZ - [21] D OUCEUR , J. R. The sybil attack. In Interna-
IÈRES , D. Riposte: An anonymous messaging tional Workshop on Peer-to-Peer Systems (2002),
system handling millions of users. In 2015 IEEE Springer, pp. 251–260.

14
[22] E LAHI , T., DANEZIS , G., AND G OLDBERG , I. Computer Communication Review (2015), vol. 45,
Privex: Private collection of traffic statistics for ACM, pp. 639–652.
anonymous communication networks. In Proceed-
[33] M ITZENMACHER , M., AND U PFAL , E. Proba-
ings of the 2014 ACM SIGSAC Conference on Com-
bility and computing: Randomized algorithms and
puter and Communications Security (2014), ACM,
probabilistic analysis. Cambridge university press,
pp. 1068–1079.
2005.
[23] G ELERNTER , N., H ERZBERG , A., AND L EI -
BOWITZ , H. Two Cents for Strong Anonymity:
[34] M ÖLLER , U., C OTTRELL , L., PALFRADER , P.,
AND S ASSAMAN , L. Mixmaster Protocol-Version
The Anonymous Post-office Protocol. Cryptology
ePrint Archive, Report 2016/489, 2016. http: 2. Draft. July, available at: www. abditum.
//eprint.iacr.org/2016/489. com/mixmaster-spec. txt (2003).

[24] G ILAD , Y., AND H ERZBERG , A. Spying in the [35] PARHI , R., S CHLIEP, M., AND H OPPER , N. MP3:
dark: TCP and Tor traffic analysis. In Interna- A More Efficient Private Presence Protocol. arXiv
tional Symposium on Privacy Enhancing Technolo- preprint arXiv:1609.02987 (2016).
gies Symposium (2012), Springer, pp. 100–119. [36] S ALTZER , J. H., R EED , D. P., AND C LARK , D. D.
[25] G OLDSCHLAG , D., R EED , M., AND S YVERSON , End-to-end arguments in system design. ACM
P. Onion routing. Communications of the ACM 42, Transactions on Computer Systems (TOCS) 2, 4
2 (1999), 39–41. (1984), 277–288.

[26] H ENRY, R., AND G OLDBERG , I. Thinking inside [37] S ERJANTOV, A., AND DANEZIS , G. Towards an
the BLAC box: smarter protocols for faster anony- information theoretic metric for anonymity. In In-
mous blacklisting. In Proceedings of the 12th ACM ternational Workshop on Privacy Enhancing Tech-
workshop on Workshop on privacy in the electronic nologies (2002), Springer, pp. 41–53.
society (2013), ACM, pp. 71–82. [38] S ERJANTOV, A., D INGLEDINE , R., AND S YVER -
[27] JANSEN , R., AND J OHNSON , A. Safely Measuring SON , P. From a trickle to a flood: Active attacks
Tor. In Proceedings of the 2016 ACM SIGSAC Con- on several mix types. In International Workshop on
ference on Computer and Communications Secu- Information Hiding (2002), Springer, pp. 36–52.
rity, Vienna, Austria, October 24-28, 2016 (2016), [39] S ERJANTOV, A., AND N EWMAN , R. E. On the
pp. 1553–1567. anonymity of timed pool mixes. In Security and
[28] K ESDOGAN , D., E GNER , J., AND B ÜSCHKES , Privacy in the Age of Uncertainty. Springer, 2003,
R. Stop-and-go-mixes providing probabilistic pp. 427–434.
anonymity in an open system. In International [40] S HANNON , C. E. A mathematical theory of com-
Workshop on Information Hiding (1998), Springer, munication. ACM SIGMOBILE Mobile Computing
pp. 83–98. and Communications Review 5, 1 (2001), 3–55.
[29] K WON , A., C ORRIGAN -G IBBS , H., D EVADAS ,
[41] T YAGI , N., G ILAD , Y., Z AHARIA , M., AND Z EL -
S., AND F ORD , B. Atom: Scalable Anonymity Re-
DOVICH , N. Stadium: A Distributed Metadata-
sistant to Traffic Analysis. CoRR abs/1612.07841
Private Messaging System. Cryptology ePrint
(2016).
Archive, Report 2016/943, 2016. http://
[30] K WON , Y. H. Riffle: An efficient communication eprint.iacr.org/2016/943.
system with strong anonymity. PhD thesis, Mas-
[42] VAN D EN H OOFF , J., L AZAR , D., Z AHARIA , M.,
sachusetts Institute of Technology, 2015.
AND Z ELDOVICH , N. Vuvuzela: Scalable private
[31] L AZAR , D., AND Z ELDOVICH , N. Alpenhorn: messaging resistant to traffic analysis. In Proceed-
Bootstrapping secure communication without leak- ings of the 25th Symposium on Operating Systems
ing metadata. In Proceedings of the 12th Sympo- Principles (2015), ACM, pp. 137–152.
sium on Operating Systems Design and Implemen-
[43] W OLINSKY, D. I., C ORRIGAN -G IBBS , H., F ORD ,
tation (OSDI), Savannah, GA (2016).
B., AND J OHNSON , A. Dissent in numbers:
[32] L E B LOND , S., C HOFFNES , D., C ALDWELL , W., Making strong anonymity scale. In Presented as
D RUSCHEL , P., AND M ERRITT, N. Herd: A Scal- part of the 10th USENIX Symposium on Operat-
able, Traffic Analysis Resistant Anonymity Net- ing Systems Design and Implementation (OSDI 12)
work for VoIP Systems. In ACM SIGCOMM (2012), pp. 179–182.

15
A Appendix remaining delays of all n0 messages in the mix as fresh
random samples from the same exponential distribution.
A.1 Incremental Computation of the En-
tropy Metric Pr [m 6= loop] = 1 − Pr [m = loop]
= 1 − Pr [X < d1 ∧ X < d2 ∧ . . . ∧ X < dn0 ] (7)
Let X be a discrete random variable over the finite set X
= 1 − Pr [X < min{d1 , d2 , . . . dn0 }]
with probability mass function p(x) = Pr(X = x). The
Shannon entropy H(X) [40] of a discrete random vari- We know, that di ∼ Exp(µ) for all i ∈ {1, . . . , n0 } and
able X is defined as X ∼ Exp(λM ). Moreover, we know that the minimum
H(X) = − p(x) log p(x). (4) of n independent exponential random variables with rate
∑ µ is an exponential random variable with parameter
x∈X
0
∑ni µ. Since all the delays di are independent expo-
Let on,k,l be an observation as defined in Section 4.1.3
nential variables with the same parameter, we have for
for a pool at time t. We note that any outgoing message
Y = min{d1 , d2 , . . . dn0 }, Y ∼ Exp(n0 µ). Thus, we obtain
will have a distribution over being linked with past input
the following continuation of Equation (7).
messages, and the entropy Ht of this distribution is our
anonymity metric. Ht can be computed incrementally Pr [m 6= loop] = 1 − Pr [X < Y ]
given the size of the pool l (from previous mix rounds) Z ∞
and the entropy Ht−1 of the messages in this previous = 1− Pr [X < Y |X = x] Pr [X = x] dx
pool, and the number of messages k received since a mes- Z0 ∞
sage was last sent: = 1− Pr [x < Y ] λM e−λM x dx
  0
Z ∞
k l 0 (8)
Ht =H , = 1− e−n µx λM e−λM x dx
k+l k+l 0
(5)
k l λM
+ log k + Ht−1 , = 1−
k+l k+l λM + nµ
for any t > 0 and H0 = 0. Thus for sequential obser- n0 µ
= 0
vations we can incrementally compute the entropy met- n µ + λM
ric for each outgoing message, without remembering the
Since the probability to send a loop depends only on the
full history of the arrivals and departures at the Poisson
number of messages in a mix, but not on which messages
mix. We use this method to compute the entropy metric
are in the mix, this probability is independent of the prob-
illustrated in Figure 4.
ability from Theorem 1. Theorem 2 follows directly by
combining Theorem 1 and Equation (8), with n0 = k + l.
A.2 Proof of Theorem 2 We get for messages m1 that previously were in the mix,
Let us assume, that in mix node Mi there are n0 mes- Pr [m = m1 ] = Pr [m 6= loop] · Pr [m = m1 |m 6= loop]
sages at a given moment, among which is a target mes-
sage mt . Each message has a delay di drawn from the ex- (k + l)µ k
= ·
ponential distribution with parameter µ. The mix node (k + l)µ + λM n(k + l)
generates loops with distribution Pois(λM ). The adver- k µ
= · .
sary observes an outgoing message m and wants to quan- n (k + l)µ + λM
tify whether this outgoing message is her target message.
The adversary knows, that the output of the mix node can Analogously, we get for m2 ,
be either one of the messages inside the mix or its loop
Pr [m = m2 ] = Pr [m 6= loop] · Pr [m = m2 |m 6= loop]
cover message. Thus, for any message mt , the following
holds (k + l)µ 1
= ·
(k + l)µ + λM k + l
Pr [m = mt ] = Pr [m 6= loop] · Pr [m = mt |m 6= loop] (6) µ
= .
We note that the next message m is a loop if and only if (k + l)µ + λM
the next loop message is sent before any of the messages This concludes the proof.
within the mix, i.e., if the sampled time for the next loop
message is smaller than any of the remaining delays of all
messages within the mix. We now leverage the memory-
less property of the exponential distribution to model the

16