[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] Clarify a few points
Update of /home/freehaven/cvsroot/doc/e2e-traffic
In directory moria.mit.edu:/tmp/cvs-serv11718
Modified Files:
e2e-traffic.tex
Log Message:
Clarify a few points
Index: e2e-traffic.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/e2e-traffic.tex,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -d -r1.3 -r1.4
--- e2e-traffic.tex 6 Aug 2003 05:22:24 -0000 1.3
+++ e2e-traffic.tex 6 Aug 2003 19:30:42 -0000 1.4
@@ -20,7 +20,7 @@
\centerline{\LARGE\bf *DRAFT* --- not for publication}
%======================================================================
\begin{abstract}
-We extend earlier work on end-to-end long-term traffic analysis.
+We extend earlier work on long-term end-to-end traffic analysis.
Whereas earlier work addressed cases in which a global eavesdropper
was trying to learn sender-receiver connections at a single batch mix
whose senders had known behavior patterns, this paper describes how an
@@ -30,10 +30,10 @@
Each weakening of earlier assumptions increases the time over which
the attacker must observe the mix-net, but has little effect on the
attacker's storage or computational requirements. Additionally, we
-describe how such an attacker can exploit additional information about
+describe how such an attacker can exploit extra information about
message linkability in order to reduce the number of rounds required
to link senders to recipients. We present analysis of the amount of
-information needed to mount each of these attacks, and provide
+information needed to mount each of these attacks along with
experimental results from mounting these attacks on a simulated
mix-net. Finally, we propose a few mechanisms for resisting these
attacks.
@@ -42,68 +42,76 @@
%======================================================================
\section{Introduction}
\label{intro}
-Since the introduction of mix-nets \cite{chaum-mix} in 1981, a variety
-of attacks against such anonymity systems has been proposed and
+Since the introduction of mix-nets \cite{chaum-mix} in 1981, many
+attacks against such anonymity systems have been proposed and
discussed. While some of these attacks have been partially addressed
by advancements in mix-net designs \cite{???}, broad classes of
attacks remain effective against current mix-net designs.
-One such class of attacks are the {\it long-term intersection attacks}
+One such class of attacks are {\it long-term intersection attacks}
wherein an eavesdropper observes a large volume of network traffic,
and notices over time that certain recipients are more likely to
receive messages when given senders are transmitting messages.
Categorical defenses against this attack tend to require either an
-impractically large amount of cover traffic, or a set of senders with
-near-perfect uptimes.
+impractically large amount of cover traffic or a set of senders with
+perfect uptimes.
% i would argue they require both? if you do great cover traffic but
-% aren't online much, you lose; and if you're online but not sending
-% much, you also lose.
+% aren't online much, you lose; and if you're online but not sending
+% much, you also lose. -RD
+%
+% No. 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
An example of a long-term intersection attack is proposed by Agrawal,
Kesdogan, and Penz \cite{limits-open}. Their {\it disclosure attack}
-assumes a fairly strict model of sender behavior, and works against
+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 mount a computationally
-difficult and algorithmically complex attack in order to reveal the
-connections between senders and recipients.
+disclosure attack requires an attacker to solve a complex NP-complete
+problem in order to reveal the connections between senders and
+recipients.
Danezis presents an algorithmically simpler {\it statistical
disclosure attack} \cite{statistical-disclosure} that requires far
less computational effort on the behalf of the attacker. This attack
-is far easier to describe and implement, but it assumes the same
+is easier to describe and implement, but it assumes the same
restrictive sender and network models as the original disclosure
attack.
In this paper, we extend Danezis's original statistical disclosure
attack to work in less restricted circumstances. Specifically, if a
-given mix-net sender maintains a consistant behavior pattern over
-time, we show how an attacker can learn that sender's regular
-recipients, even when:
+given mix-net sender (hereinafter called ``Alice'') maintains a
+consistant behavior pattern over time, we show how an attacker can
+learn Alice's regular recipients, even when:
\begin{itemize}
-\item The target sender chooses non-uniformly among their
+\item Alice chooses non-uniformly among her
communication partners, send multiple messages at once, and has
- some non-repeated recipients.
+ some recipients.
\item The attacker lacks {\it a priori} knowledge of the network's
- average behavior in the sender's absence.
-\item Mixes in the system use a better batching algorithm, such as
- the timed dynamic-pool algorithm \cite{trickle02} used by
- Mixmaster \cite{mixmaster-spec}, or the generalized mix algorithm
- proposed by \cite{pet2003-diaz}.
-\item The sender uses a path through a mix network, instead of just a
+ average behavior when Alice is not sending messages.
+\item Mixes use a better batching algorithm, such as the timed
+ dynamic-pool algorithm \cite{trickle02} used by Mixmaster
+ \cite{mixmaster-spec}, or the generalized mix algorithm proposed by
+ \cite{pet2003-diaz}.
+\item Alice uses a path through a mix network instead of just a
single mix.
-\item The sender sends some dummy traffic, delivered to no particular
+\item Alice sends some dummy traffic delivered to no particular
recipient.
\item The attacker can only view a subset of the messages entering and
- leaving the network, but this subset includes some messages from
- the sender and some messages to the sender's recipients.
-\item The behavior of the cover traffic generated by other senders
- changes continuously over time. (We do not address this case
- completely).
+ leaving the network, so long as this subset includes some messages
+ from Alice and some messages to Alice's recipients.
+\item The cover traffic generated by other senders changes
+ continuously over time. (We do not address this case completely).
\end{itemize}
-Each of these variations increases the amount of time the attacker
-must spend observing traffic in order to learn the sender's regular
-recipients.
+Each of these variations increases the amount of traffic the attacker
+must observe in order to learn Alice's regular recipients.
Additionally, we show how an attacker can exploit additional
knowledge about the anonymity system (or external to it) to speed up
@@ -117,30 +125,32 @@
are pseudonymous, all messages from the same pseudonym are almost
certainly written by a single sender.
\item {\it A priori} suspicion of certain messages having originated
- or not originated from the target sender. For example, messages
- written in a language the sender doesn't speak are unlikely to have
- been written by the sender.
+ or not originated from Alice. For example, messages written in a
+ language the sender doesn't speak are unlikely to have been written
+ by the sender.
\end{itemize}
The attacks in this paper fail to work when:
\begin{itemize}
-\item The sender's behavior is not consistent over time. If the
- sender does not maintain a group of regular recipients for the
- required duration, the attacker cannot learn the sender's behavior.
+\item Alice's behavior is not consistent over time. If Alice does not
+ produce enough traffic with the same group of regular recipients,
+ the attacker cannot learn Alice's behavior.
\item The attacker cannot observe the network's steady-state (cover)
- behavior. If
- the sender always sends the same number of messages, the attacker
- may not be able to get a view of the network's exit behavior in the
- sender's absence. % Awkwardly phrased!
+ behavior. If Alice
+ always sends the same number of messages, the attacker
+ may not be able to get a view of who receives messages in Alice's
+ absence. % Awkwardly phrased!
+ % Also, is it right to call this ``steady state'' behavior? It's
+ % really `The network's behavior when Alice isn't around'.
\item The attacker cannot tell when the sender is originating
messages. This may be the case if the sender is running her own mix
- node and injecting messages to it directly.
+ node and injecting messages into it directly.
\end{itemize}
We begin in section \ref{previous-work} by presenting a brief
background overview on mix-nets, traffic analysis, the disclosure
attack, and the statistical disclosure attack. In section
-\ref{extending}, we then present our enhancements to the statistical
+\ref{extending}, we present our enhancements to the statistical
disclosure attack. We analyze the effectiveness of these enhancements
in section \ref{analysis}, and present simulated experimental results
in section \ref{simulation}. We close in section \ref{conclusion}
@@ -168,7 +178,7 @@
$b-1$ messages in each batch are chosen at random from the set of $N$
possible recipients.
-The attacker observes the messages leaving the mix in each batch, and
+The attacker observes the messages leaving the mix in each batch and
constructs sets $R_i$ of recipients receiving messages in batch $i$.
The attacker then performs an NP-complete computation to identify $m$
mutually disjoint recipient sets $R_i$, so that each of Alice's
@@ -182,12 +192,13 @@
\subsection{The statistical disclosure attack}
In 2003, Danezis presented the statistical disclosure
-attack\cite{statistical-disclosure}, which makes the same assumptions
+attack\cite{statistical-disclosure}, which makes the same operational
+assumptions
as the original disclosure attacks, but is far easier to implement in
terms of storage, speed, and algorithmic complexity.
In the statistical disclosure attack, we model Alice's behavior as an
-unknown vector $\vec{v}$ with elements corresponding to the
+unknown vector $\vec{v}$ whose elements correspond to the
probability of Alice sending a message to each of the $N$ recipients
in the system. Of these elements, $m$ will be $1/m$, and $N-m$ will
be $0$. We model the behavior of the cover traffic as a known
@@ -196,11 +207,12 @@
The attacker derives from each output round $i$ an observation vector
$\vec{o_i}$, each of whose elements corresponds to the probability of
Alice's having sent a message to a particular recipient in that round.
-Taking the arithmetic mean $\bar{O}$ of a large set of $vec{o_i}$
+Taking the arithmetic mean $\bar{O}$ of a large set of $\vec{o_i}$
gives (by the law of large numbers):
-\[\frac{\vec{v} + (b-1)\vec{u}}{b} \]
+\[\bar{O} = \frac{1}{t}\sum_{i=i}^{t} \vec{o_i} \approx
+ \frac{\vec{v} + (b-1)\vec{u}}{b} \]
From this, the attacker estimates
-\[\vec{v} = b\frac{\sum_{i=1}^t \vec{o_i}}{t} - (b-i)\vec{u}\]
+\[\vec{v} \approx b\frac{\sum_{i=1}^t \vec{o_i}}{t} - (b-i)\vec{u}\]
\XXXX{Should we report George's findings on preconditions and
required time to succeed?}
@@ -216,8 +228,8 @@
I shouldn't, modeling things strangely, and so on. ---Nick.}
\subsection{Broadening the attack}
-In this subsection, we examine ways in order to extend this attack to
-models more closely resembling real mix-nets.
+In this subsection, we examine ways to extend Danezis's Statistical
+Disclosure Attack to systems more closely resembling real mix-nets.
\subsubsection{Complex sender behavior}
First, we relax the requirements related to sender behavior. In this
@@ -226,13 +238,13 @@
remove the assumption that the attacker has full knowledge of the
distribution $\vec{u}$ of cover traffic.
-We model Alice's behavior as a probability distribution $p_n(n)$ of
-% p_i(n)? Why _n? For that matter, why (n)? -RD
-the number of messages she sends each round, and a non-uniform
-behavior vector $\vec{v}$ of the recipients to which Alice sends.
-Thus, Alice's expected contribution to each round is $p_n(n)\vec{v}$.
+We model Alice's behavior with a probability distribution $p_m$ such
+that in every round Alice sends $n$ messages with a probability
+$p_m(n)$, and with a behavior vector $\vec{v}$ of the recipients to
+which Alice sends. Thus, Alice's expected contribution to each round
+is $\vec{v} \sum_{n=0}^{\infty} n p_m(n)$.
-To mount the attack in this case, the attacker first obtains an
+To mount the attack, the attacker first obtains an
estimate of $\vec{u}$ by observing a large number $t'$ of batches to
which Alice has {\it not} contributed any messages. For each such
batch $i$, the attacker constructs a vector $\vec{u_i}$ containing the
@@ -247,7 +259,7 @@
gives us
\[\bar{O} = \frac{\vec{o_i}}{\sum t}
\approx
- \frac{\bar{m}\vec{v} + (b-\bar{m)}\vec{u}}{b}
+ \frac{\bar{m}\vec{v} + (b-\bar{m})\vec{u}}{b}
\mbox{\ where\ } \bar{m} = \frac{1}{t}\sum{m_i} \]
From this, the attacker estimates Alice's behavior as
@@ -276,7 +288,7 @@
In the case of a timed dynamic-pool mix, this distribution is:
\[ P_{TDP}(b|s) =
\left\{ \begin{array}{l}
- 1 \mbox{\ for\ } if s>\mbox{min-pool},
+ 1 \mbox{\ if\ } s>\mbox{min-pool},
b = min(s-\mbox{min-pool}, \left\lfloor s*\mbox{rate} \right\rfloor) \\
0 \mbox{\ otherwise} \end{array} \right. \]
For a binomial timed dynamic-pool mix,
@@ -294,7 +306,7 @@
We denote by $P_R(r)$ the probability of a message leaving the mix $r$
rounds after it has arrived. In future discussion, we assume for the
sake of simplicity that the mix has reached a steady state, so that
-$P_R(r) = P_D^r$ where $P_D$ is the probability of a message in the
+$P_R(r) = {P_D}^r$ where $P_D$ is the probability of a message in the
mix's pool being deferred in any given round.\footnote{The
attacker can estimate $\bar{P_R}$ by
sending occasion test messages through the mix, or by counting the
@@ -321,7 +333,7 @@
into the earlier equation for $\bar{O}$ and again solve for $\vec{v}$.
\subsubsection{Mix-nets}
-Another way senders behave differently from the model of the
+Another way senders behave differently from the model of the original
disclosure attack is by directing their messages through a chosen path
in a network of mixes. While using a mix-net increases the effort an
attacker must spend to observe all messages leaving the system, it
@@ -344,8 +356,9 @@
\label{dummy-traffic}
One strategy for reducing the impact of traffic analysis is for Alice
to periodically send messages into the network that arrive at no
-recipient; or to periodically send messages into the network that
-arrive at recipients other than those she wants to communicate with.
+recipient, or to periodically send messages into the network that
+arrive at recipients other than those with whom she wants to
+communicate.
In the first case, the change is trivial: Alice's behavior vector
$\vec{v}$ no longer adds to $1$, since there is now a probability that
@@ -365,7 +378,7 @@
cover messages are chosen from a distribution vector $\vec{v_c}$.
Now, instead of converging on Alice's true pattern of recipients
$\vec{v}$, the attacker instead learns
-\[ \vec{v'} = (1-P_c)\vec{v} + P_c\vec{v_c} \].
+\[ \vec{v'} = (1-P_c)\vec{v} + P_c\vec{v_c} \]
In other words, although the attacker cannot deduce which recipients
receive messages from Alice, he can instead learn a superset of
Alice's recipients.
@@ -377,7 +390,7 @@
messages to {\it every} participant in the system --- potentially as
many recipients as there are active email addresses. Such a padding
regime results in traffic quadratic in the number of participants in
-the system, and thus scales prohibitively poorly.
+the system, and thus scales poorly.
\XXXX{say more here. Dummy policies other than N-squared may help a
little.}
@@ -405,7 +418,7 @@
Alternatively, an attacker who eavesdrops on a fraction of the {\it
users} in the system receives {\it all} of the messages sent to or
-from those users, but no messages sent to or from other users. So long as
+from those users but no messages sent to or from other users. So long as
one of these users is Alice, the attack can still proceed: To such an
attacker, the network is as if the messages sent by Alice to
unobserved recipients were dummy messages. Now the attack converges
@@ -429,8 +442,7 @@
average behavior of the network during a comparatively shorter
duration of time. Now the attacker observes $\vec{o_i}$ as before and
computes the average of $\vec{o_i} - \vec{u_i}$, as before. Now,
-\[ \frac{1}{t}\sum_{i=1}^t \vec{o_i} - \bar{u_i}
- \propto \vec{v}
+\[ \vec{v} \propto \frac{1}{t}\sum_{i=1}^t \vec{o_i} - \bar{u_i}
\]
So if an attacker can get good local estimates to $\vec{u}$, the
intersection attack proceeds as before.
@@ -455,14 +467,14 @@
\subsection{Strengthening the attack}
Our previous extensions to the original statistical disclosure attack
-have broadened the original method in order to reveal sender-recipient
+have shown how to reveal sender-recipient
links in a broader and increasingly complex range of circumstances.
In order to compensate for these circumstances, the attacker has been
forced to observe an increasingly large number of rounds of traffic.
In this section, rather than broadening the attack at the expense of
increased difficulty, we discuss ways to strengthen the attack by
-adding additional information the attacker may have.
+incorporating additional information the attacker may have.
\subsubsection{Exploiting full message linkability}
The attacker's work can be greatly simplified if some messages leaving
@@ -470,7 +482,7 @@
fully linkable} if an observer can tell, with certainty, that they
originate from the same sender. One example of a system with fully
linkable messages would be a pseudonymity service in which each sender
-has one or more pseudonyms, and all delivered messages can be linked
+has one or more pseudonyms and all delivered messages can be linked
to a pseudonym.
Clearly, the attacker in such a system can trivially link senders to
@@ -490,7 +502,6 @@
\subsubsection{Exploiting partial message linkability}
% subsumes \subsubsection{Exploiting partitioning attacks}
-%In the linkability case above,
It's possible that the linkage between
messages may not be full. In other words, the attacker may be able
to deduce that two messages are more likely than average to have the same
@@ -508,23 +519,24 @@
\XXXX{This section is really about distinguishability, perhaps.}
To exploit these partial linkages, the attacker begins as above by
-choosing a set of `linkability classes' (such as languages, patterns
-of usage, etc.), and assigning to each observed output message a
-probability of belonging to each class. The attack then collects
-observations, noting the number of messages received in each round by
-each $\left<\mbox{recipient},\mbox{class}\right>$ tuple. (If a
-message might belong to multiple classes, the attacker sets the
-corresponding element of each possible class to the possibility of the
-message's being in that class.)
-% i don't understand. you mean just add the tuple to all the classes
-% it could possibly be in? -RD
+choosing a set of $c$ `linkability classes' (such as languages,
+patterns of usage, etc.), and assigning to each observed output
+message a probability of belonging to each class. The attacker then
+proceeds as before, but instead of collecting $N$-element observation
+vectors with elements corresponding the recipients, the attacker now
+builds $cN$-element vectors whose elements correspond to number of
+messages received in each round by each
+$\left<\mbox{recipient},\mbox{class}\right>$ tuple. (If a message
+might belong to multiple classes, the attacker sets the corresponding
+element of each possible class to the probability of the message's
+being in that class.)
The statistical disclosure attack
proceeds as before, but messages sent to different linkability
classes no longer provide cover for one another.
\XXXX{ This attack seems not to exploit the fact that if Alice sends
to $<$Word6, Bob$>$, she is more likely to send to $<$Word6,
- Carol$<$ than to $<$Word2K, Carol$>$.}
+ Carol$>$ than to $<$Word2K, Carol$>$.}
Other opportunities for partitioning include:
\begin{itemize}
@@ -541,7 +553,7 @@
about astrophysics.
To exploit this knowledge, an attacker can (as suggested in the
-original Statistical Disclosure paper \cite{statistical-disclosure}),
+original Statistical Disclosure paper \cite{statistical-disclosure})
modify the estimated probabilities in $\vec{o_i}$ of Alice having sent
each delivered message. For example, if 100 messages are sent in a
round, and the attacker judges that 50 of them are twice as likely to
***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs in the body. http://freehaven.net/