[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] overhaul the intro, plus a bit of related work
Update of /home2/freehaven/cvsroot/doc/e2e-traffic
In directory moria.mit.edu:/tmp/cvs-serv31071
Modified Files:
e2e-traffic.tex e2e-traffic.bib
Log Message:
overhaul the intro, plus a bit of related work
Index: e2e-traffic.tex
===================================================================
RCS file: /home2/freehaven/cvsroot/doc/e2e-traffic/e2e-traffic.tex,v
retrieving revision 1.21
retrieving revision 1.22
diff -u -d -r1.21 -r1.22
--- e2e-traffic.tex 24 Jan 2004 03:45:07 -0000 1.21
+++ e2e-traffic.tex 24 Jan 2004 06:45:29 -0000 1.22
@@ -59,92 +59,59 @@
%======================================================================
\section{Introduction}
\label{sec:intro}
-%Since the introduction of mix-nets \cite{chaum-mix} in 1981, many
-%attacks against these anonymity systems have been proposed.
-%While some of these attacks have been
-%addressed by improved mix-net designs,
Mix networks aim to allow senders to anonymously deliver messages to
recipients. One of the strongest attacks against current deployable
-mix network designs is the \emph{long-term intersection attack}. In this
-attack, a passive eavesdropper observes a large volume of network traffic
-and notices over time that certain recipients are more likely to
-receive messages after given senders have transmitted messages. Although
-these correlations are slight, given enough time an attacker can
-deduce which senders are communicating with which recipients.
-Previously, researchers have believed that long-term intersection attacks
-can only be stopped by an impractically large amount of cover traffic
-(e.g.,
-senders send dummy messages to every possible recipient whenever they
-want to send a real message to anyone) or a set of senders
-with perfect uptimes who send messages continually (so that the attacker can
-never learn how the network behaves in the absence of particular senders).
-%
-% Either of these is sufficient:
-% Suppose that Alice sends a message to every possible recipient
-% (n^2 padding) every time she sends any messages at all. Even if
-% Alice is rarely online, all we can learn about her behavior is that
-% when she comes online, she sends a message to everybody.
-% Conversely, suppose Alice is online sending all the time, has been
-% sending since the system went online, and will send a message every
-% day till the end of time. In this case, even if Alice doesn't pad, the
-% attacker can't learn what the network looks like when she isn't
-% sending, and so can't deduce her contribution. -NM
-%
-% This is subtle, but I'm not sure I buy the second part of this as much
-% as the first. In the first case, it's obvious to me that if Alice wants
-% her anonymity, she broadcasts and that's that. But in the second case,
-% if Alice is the only sender, it seems she cannot get anonymity on her
-% own. If Alice is the only sender who behaves this way, then perhaps
-% she doesn't get much help from the other senders. And thirdly, this
-% wouldn't be a categorical defense unless *all* senders, not just 'a
-% set of senders', behaved this way; the ones who didn't wouldn't be
-% protected. -RD
-%
-Here we present several variations on a version of the long-term
-intersection attack, and examine their simulated performance. Preliminary
-results indicate that these attacks can be resisted with significantly less
-overhead than previously supposed.
+mix network designs is the \emph{long-term intersection attack}. In
+this attack, a passive eavesdropper observes a large volume of network
+traffic and notices that certain recipients are more likely to receive
+messages after given senders have transmitted messages.
+% Although these correlations are slight,
+That is, if a sender (call her Alice) maintains a fairly consistent
+behavior pattern over time, the attacker can deduce Alice's recipients.
-Kesdogan, Agrawal, and Penz propose an example of a long-term
-intersection attack in \cite{limits-open}, and expand on this attack in
-\cite{agrawal03}. Their {\it disclosure attack}
-assumes a fairly strict model of sender behavior and works against
-only a single batch mix. (A batch mix waits until it receives $b$
-messages, then reorders and retransmits them all.) Additionally, the
-disclosure attack requires an attacker to solve an NP-complete
-problem to reveal the connections between senders and recipients.
+Researchers have theorized that these attacks should be extremely
+effective in many real-world contexts, but so far it has been difficult
+to reason about when they would be successful and how long the attacks
+would take.
-Danezis presents an algorithmically simpler {\it statistical
-disclosure attack} \cite{statistical-disclosure} that requires far
-less computation. But while this attack
-is easier to describe and implement, it assumes the same
-restrictive sender and network models as the original disclosure
-attack.
+%% Put this stuff in the previous work section if you want.
+%Kesdogan, Agrawal, and Penz propose an example of a long-term
+%intersection attack in \cite{limits-open}, and expand on this attack in
+%\cite{agrawal03}. Their {\it disclosure attack}
+%assumes a fairly strict model of sender behavior and works against
+%only a single batch mix. (A batch mix waits until it receives $b$
+%messages, then reorders and retransmits them all.) Additionally, the
+%disclosure attack requires an attacker to solve an NP-complete
+%problem to reveal the connections between senders and recipients.
+%
+%Danezis presents an algorithmically simpler {\it statistical
+%disclosure attack} \cite{statistical-disclosure} that requires far
+%less computation. But while this attack
+%is easier to describe and implement, it assumes the same
+%restrictive sender and network models as the original disclosure
+%attack.
+
+Here we extend a version of the long-term intersection attack called the
+statistical disclosure attack \cite{statistical-disclosure} to work in
+real-world circumstances. Specifically, whereas the original model for
+this attack makes strong assumptions about sender behavior and works
+against only a single batch mix, we show how an attacker can learn
+Alice's regular recipients even when:
-In this paper, we extend Danezis's statistical disclosure attack to
-work in more real-world circumstances. Specifically, if a given mix-net
-sender (call her Alice) maintains a fairly consistent behavior
-pattern over time, we show how an attacker can learn Alice's regular
-recipients, even when we relax the original disclosure attack's model
-in the following ways:
\begin{tightlist}
\item Alice chooses non-uniformly among her communication partners,
and can send multiple messages in a single batch.
\item The attacker lacks {\it a priori} knowledge of the network's
average behavior when Alice is not sending messages.
\item Mixes use a different batching algorithm, such as Mixmaster's
- dynamic-pool
- algorithm \cite{trickle02,mixmaster-spec} or its
+ dynamic-pool algorithm \cite{trickle02,mixmaster-spec} or its
generalization \cite{pet2003-diaz}.
-% (Rather than
-% the ``batch'' mix behavior of relaying all messages when $b$
-% messages have arrived, these algorithms hold messages in a ``pool'' for
-% a random number of rounds based on the number of messages in the pool.)
\item Alice uses a mix network (of any topology, with synchronous or
asynchronous batching) to relay her messages through a succession of
mixes, instead of using just a single mix.
-\item Alice disguises when she is sending real messages by sending some
- traffic padding to be dropped by some mix node in the network.
+\item Alice disguises when she is sending real messages by sending
+ traffic padding to % be dropped by
+ some mix node in the network.
\item The attacker can only view a subset of the messages entering and
leaving the network, so long as this subset includes some messages
from Alice and some messages to Alice's recipients.
@@ -152,22 +119,18 @@
slowly over time. (We do not address this case completely).
\end{tightlist}
Each of these deviations from the original
-%%statistical disclosure attack
model reduces the rate at which the attacker learns Alice's recipients, and
increases the amount of traffic the attacker must observe.
-Additionally, we show how an attacker can exploit additional knowledge to
-speed up these attacks. Such knowledge includes:
-\begin{tightlist}
-\item Linkability between messages. For example, the attacker can take into
- account
- whether messages are written in the same language or signed by the
- same pseudonym.
-\item {\it A priori} suspicion of certain messages having originated
- or not originated from Alice. For example, messages written in a
- language Alice doesn't speak are unlikely to have been written
- by Alice.
-\end{tightlist}
+Additionally, we show how an attacker can exploit additional knowledge,
+such as linkability between messages, to speed up these attacks.
+Linkability between messages. For example, the attacker can take into
+account whether messages are written in the same language or signed by
+the same pseudonym.
+%\item {\it A priori} suspicion of certain messages having originated
+% or not originated from Alice. For example, messages written in a
+% language Alice doesn't speak are unlikely to have been written
+% by Alice.
The attacks in this paper fail to work when:
\begin{tightlist}
@@ -215,6 +178,8 @@
Many subsequent designs have been proposed, including Babel \cite{babel},
Mixmaster \cite{mixmaster-spec}, and Mixminion \cite{minion-design}.
% also \cite{shuffle} and \cite{abe}
+% No, we shouldn't mention either of these. The long-term intersection
+% attack is not part of their threat model. -RD
We will not address the differences between these systems in any detail: from
the point of view of a long-term intersection attack, the internals of the
network are irrelevant so long as the attacker can observe messages entering
@@ -226,8 +191,8 @@
%%learning when participannts are sending and receiving.)
Another class of anonymity designs is aimed at web browsing and other
-low latency activities \cite{web-mix:pet2000,tor-design,or-jsac98},
-but we neglect them in this paper because short-term timing and packet
+low latency activities \cite{web-mix:pet2000,freedom2-arch,tor-design,or-jsac98},
+but we do not address them in this paper because short-term timing and packet
counting attacks seem sufficient against them \cite{SS03}.
Attacks against mix networks aim to reduce the anonymity of users by
Index: e2e-traffic.bib
===================================================================
RCS file: /home2/freehaven/cvsroot/doc/e2e-traffic/e2e-traffic.bib,v
retrieving revision 1.6
retrieving revision 1.7
diff -u -d -r1.6 -r1.7
--- e2e-traffic.bib 22 Jan 2004 04:34:46 -0000 1.6
+++ e2e-traffic.bib 24 Jan 2004 06:45:29 -0000 1.7
@@ -1,3 +1,14 @@
+
+@techreport{freedom2-arch,
+ title = {Freedom Systems 2.0 Architecture},
+ author = {Philippe Boucher and Adam Shostack and Ian Goldberg},
+ institution = {Zero Knowledge Systems, {Inc.}},
+ year = {2000},
+ month = {December},
+ type = {White Paper},
+ day = {18},
+}
+
@inproceedings{SS03,
title = {Passive Attack Analysis for Connection-Based Anonymity Systems},
author = {Andrei Serjantov and Peter Sewell},
***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs in the body. http://freehaven.net/