01-10-2012, 11:19 AM
On Flow Correlation Attacks and Countermeasures in Mix Networks
On Flow Correlation Attacks.pdf (Size: 257.23 KB / Downloads: 30)
Abstract
In this paper, we address issues related to flow correlation attacks and the corresponding countermeasures in
mix networks. Mixes have been used in many anonymous communication systems and are supposed to provide
countermeasures that can defeat various traffic analysis attacks. In this paper, we focus on a particular class of
traffic analysis attack, flow correlation attacks, by which an adversary attempts to analyze the network traffic and
correlate the traffic of a flow over an input link at a mix with that over an output link of the same mix. Two classes
of correlation methods are considered, namely time-domain methods and frequency-domain methods. Based on
our threat model and known strategies in existing mix networks, we perform extensive experiments to analyze
the performance of mixes. We find that a mix with any known batching strategy may fail against flow correlation
attacks in the sense that for a given flow over an input link, the adversary can correctly determine which output link
is used by the same flow. We also investigated methods that can effectively counter the flow correlation attack and
other timing attacks. The empirical results provided in this paper give an indication to designers of Mix networks
about appropriate configurations and alternative mechanisms to be used to counter flow correlation attacks.
Introduction
This paper studies flow correlation attacks and the corresponding countermeasures in mix networks. With the
rapid growth and public acceptance of the Internet as a means of communication and information dissemination,
concerns about privacy and security on the Internet have grown. Although it can potentially be used for malicious
purposes, Anonymity is legitimate in many scenarios such as anonymous web browsing, E-Voting, E-Banking, ECommerce,
and E-Auctions. In each of these scenarios, encryption alone cannot achieve the anonymity required
by participants [30, 31].
Since Chaum [6] proposed the mix network, researchers have developed various anonymity systems for different
applications. Although a significant amount of effort has been put forth in researching anonymous communications,
there has not been much systematic study of the performance of mix networks in terms of anonymity
degree provided and quality-of-services maintained. This paper focuses on the quantitative evaluation of mix performance.
We are particularly interested in flow-based communication, which is widely used in voice over IP, web
browsing, FTP, etc. These applications may have anonymity requirements, and the mixes are supposed to provide
countermeasures that can defeat traffic analysis attacks.
RelatedWork
Chaum [6] pioneered the idea of anonymity in 1981. Since then, researchers have applied the idea to different
applications such as message-based email and flow-based low-latency communications, and they have invented
new defense techniques as more attacks have been proposed.
For anonymous email applications, Chaum [6] proposed to use relay servers, i.e. mixes, rerouting messages,
which are encrypted by public keys of the mixes. An encrypted message is analogous to an onion constructed by
the sender, who sends the onion to the first mix. Using its private key, the first mix peels off the first layer, which is
encrypted using the public key of the first mix. Inside the first layer is the second mix’s address and the rest of the
onion, which is encrypted with the second mix’s public key. After getting the second mix’s address, the first mix
sends the peeled onion. This process proceeds in this recursive way. The core part of the onion is the receiver’s address and the real message to be sent to the receiver by the last mix. Chaum also proposed the return address
and digital pseudonyms for users to communicate with each other in an anonymous way.
Models
Mix and Mix Network
A mix is a relay device for anonymous communication. Figure 1 shows the communication between users
using one mix. A single mix can achieve a certain level of communication anonymity: The sender of a message
attaches the receiver address to a packet and encrypts it using the mix’s public key. Upon receiving a packet,
a mix decodes the packet. Different from an ordinary router, a mix usually will not relay the received packet
immediately. Rather, it collects several packets and then sends them out in a batch. The order of packets may be
altered as well. Techniques such as batching and reordering are considered to be necessary techniques for a mix
to prevent timing-based attacks.
Batching Strategies for a Mix
Batching strategies are designed to prevent not only simple timing analysis attacks but also powerful trickle
attacks, flood attacks, and many other forms of attacks ([7, 28]). Serjantov [28] summarizes seven batching
strategies that have been proposed. We will evaluate each kind of these strategies. Our results show that these
strategies may not work under certain timing analysis attacks.
These seven batching strategies are listed in Table 1, in which batching strategies from S1to S4are denoted as
simple mix, while batching strategies from S5to S7are denoted as pool mix.
From Table 1, we can see that the sending of a batch of packets can be triggered by certain events, e.g., queue
length reaching a pre-defined threshold, a timer having a time out, or some combination of these two.
Batching is typically accompanied by reordering. In this paper, the attacks focus on the traffic characteristics.
As reordering does not change packet interarrival times much for mixes using batching, these attacks (and our
analysis) are unaffected by reordering. Thus, our results are applicable to systems that use any kind of reordering
methods. As such, in the rest of this paper, we will not discuss reordering techniques further.
Summary and Future Work
We have analyzed mix networks in terms of their effectiveness in providing anonymity and quality-of-service.
Various methods used in mix networks were considered: seven different packet batching strategies and two implementation
schemes, namely the link-based batching scheme and mix-based batching scheme. We found that mix
networks that use traditional batching strategies, regardless of the implementation scheme, are vulnerable under
flow correlation attacks. By using proper statistical analysis, an adversary can always accurately determine the
output link used by traffic that comes to an input flow of a mix. The detection rate can be as high as 100% as long
as enough data is available. This is true even if heavy cross traffic exists. The experimental data collected in this
paper should give designers guidelines for the development and operation of mix networks.
The failure of traditional mix batching strategies directly leads us to the formation of a new packet control
method for mixes in order to overcome their vulnerability to flow correlation attacks. Our new method can achieve
a guaranteed low detection rate while maintaining high throughput for normal payload traffic. Our claim is validated
by extensive performance data collected from experiments. The new method is flexible in controlling the
overhead by adjusting the maximum packet delay.