[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] Checkpoint edits to paper. We now have a complete f...
Update of /home/freehaven/cvsroot/doc/e2e-traffic
In directory moria.mit.edu:/tmp/cvs-serv13747
Modified Files:
e2e-traffic.tex e2e-traffic.bib
Log Message:
Checkpoint edits to paper. We now have a complete first draft.
arma: I'll try to get another round of editing in before I conk out,
but just in case I get tired sooner than I think, don't wait for my
stuff.
Index: e2e-traffic.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/e2e-traffic.tex,v
retrieving revision 1.22
retrieving revision 1.23
diff -u -d -r1.22 -r1.23
--- e2e-traffic.tex 24 Jan 2004 06:45:29 -0000 1.22
+++ e2e-traffic.tex 24 Jan 2004 14:44:32 -0000 1.23
@@ -16,6 +16,7 @@
\newcommand\Pobserve{P_{\mbox{\scriptsize observe}}}
\newcommand\Ponline{P_{\mbox{\scriptsize online}}}
\newcommand\Pjunk{P_{\mbox{\scriptsize junk}}}
+\newcommand\Pdelay{P_{\mbox{\scriptsize delay}}}
\newcommand\V[1]{\overrightarrow{#1}}
\newcommand\B[1]{\overline{#1}}
@@ -48,7 +49,7 @@
is a network of pool mixes, the attacker is non-global, and senders have
complex behavior including generating padding messages.
Additionally, we describe how an attacker can use extra information about
-message linkability to speed the attack.
+message distinguishability to speed the attack.
%to reduce the amount of traffic needed to link senders to recipients.
Finally, we simulate our attacks for a variety of
scenarios, focusing on the amount of information needed to link senders and
@@ -122,11 +123,11 @@
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,
-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.
+Additionally, we show how an attacker can exploit additional knowledge, such
+as distinguishability between messages, to speed up these attacks. (For
+example, the attacker can take into account whether messages are written in
+the same language or signed by the same pseudonym to partition them into
+different classes and analyze the classes independently.)
%\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
@@ -475,6 +476,9 @@
% \XXXX{ How can the attacker estimate $P_L$ for Alice? What if he can't?}
+Danezis has independently extended statistical disclosure to pool mixes
+\cite{gd-thesis}.
+
\subsubsection{Dummy traffic}
\label{subsubsec:dummy-traffic}
One strategy for reducing the impact of traffic analysis is for Alice
@@ -597,7 +601,7 @@
\subsection{Strengthening the attack}
\label{subsec:strenghtening}
Our previous extensions to the original statistical disclosure attack
-have shown how to reveal sender/recipient links in a broader range of
+have shown how to reveal sender--recipient links in a broader range of
circumstances.
In order to compensate for these circumstances (as will be shown below in
section \ref{sec:simulation}) the attacker has been
@@ -607,20 +611,21 @@
increased traffic, we discuss ways to reduce the amount of traffic required
for the attack by incorporating additional information.
-\subsubsection{Exploiting message linkability}
+\subsubsection{Exploiting message partitioning}
\label{subsubsec:full-linkability}
-The attacker's work can be greatly simplified if some messages leaving the
-system are {\it linkable}. Two messages are said to be {\it linkable} if
-they are likelier to originate from the same sender than are two randomly
-chosen messages. Messages are {\it fully linkable} if an observer can tell
-with certainty that they have the same sender, as in a
-pseudonymity service in which each sender has one or more pseudonyms and
-all delivered messages are associated with a pseudonym.
-
-% Should we call the case we handle 'parametric linkability' or something?
+The attacker's work can be greatly simplified if some leaving the system are
+{\it linkable}. Two messages are said to be {\it linkable} if they are
+likelier to originate from the same sender than are two randomly chosen
+messages. We consider a special case of linkability, in which we discover
+linkage by {\it partitioning} messages into separate classes such that
+messages in the same class are likelier to come from the same sender than two
+messages chosen at random.
-Clearly, an eavesdropper attacker who can link senders to their pseudonyms
-could trivially use this information to link senders and recipients.
+The easiest case is of partitioning is pseudonymity: in a typical
+pseudonym service, each sender has one or more pseudonyms and all
+delivered messages are associated with a pseudonym.
+Clearly, an eavesdropper attacker who can connect senders to their pseudonyms
+could trivially use this information to connect senders and recipients.
One way to do this
is by treating classes of fully linkable messages as virtual message
destinations. Instead of collecting observations $\V{o_i}$ of
@@ -631,20 +636,16 @@
elements of Alice's $\V{v}$ and the background $\V{u}$ are now
disjoint, and thus easier for the attacker to separate.
-\subsubsection{Exploiting partial message linkability}
-\label{subsubsec:partial-linkability}
-It's possible that the linkage between
-messages may not be full---the attacker may be able
-to deduce that two messages are more likely than average to have the same
-sender, without being certain that the senders are the same. For
+It's also possible that the partitioning may not be so perfect: sometimes
+many senders will send messages in the same class. For
example, two binary documents written in the same version of MS Word
are more likely to be written by the same sender than two messages
selected at random. These linkages may be more abstract: a
sophisticated attacker could check for the presence of certain
keywords and try to link messages based on their textual content.
-To exploit these partial linkages, the attacker begins as above by
-choosing a set of $c$ `linkability classes' (such as languages,
+To exploit these scenarios, the attacker begins as above by
+choosing a set of $c$ `partitioning classes' (such as languages,
patterns of usage, or so on), and assigning to each observed output
message a probability of belonging to each class. The attacker then
proceeds as before, but instead of collecting observation
@@ -656,7 +657,7 @@
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
+proceeds as before, but messages that fall in different
classes no longer provide cover for one another.
%\XXXX{ This attack seems not to exploit the fact that if Alice sends
@@ -709,16 +710,18 @@
\begin{figure}[ht]
\centering
\mbox{\epsfig{angle=0,figure=graphs/fig1,width=4in}}
-\caption{Statistical disclosure model: Rounds to guess m-1 recipients
-($90^{th}$ percentile of trial attacks)}
+\caption{Statistical disclosure model: Median rounds to guess all recipients}
\label{fig1}
\end{figure}
-We present the results of our simulations in Figure \ref{fig1}. (We found
-that the time required for the attacker to learn Alice's last few recipients
-was highly variable, especially in later simulations, so we present instead
-the $90^{th}$ percentile of number of rounds required to $m-1$ of Alice's
-recipients, across 100 trials per data point.) As expected, the attack
+We present the results of our simulations in Figure~\ref{fig1}.
+%% We don't do this next silly thing anymore. -NM
+%(We found
+%that the time required for the attacker to learn Alice's last few recipients
+%was highly variable, especially in later simulations, so we present instead
+%the $90^{th}$ percentile of number of rounds required to $m-1$ of Alice's
+%recipients, across 100 trials per data point.)
+As expected, the attack
becomes more effective when Alice sends messages to a broader group of
recipients (large $m$); when there are fewer recipients for Alice to hide
hers among (small $N$); or when batch sizes are small (small $b$).
@@ -754,49 +757,38 @@
they know.
Again, we simulated trial attacks for different values of $N$ (the number of
-recipients), $m$ (the number of Alice's recipients), and $b$ (the batch
-size). Instead of contributing one message per batch, however, Alice now
+recipients) and $m$ (the number of Alice's recipients).
+Instead of contributing one message per batch, however, Alice now
contributes messages according to a geometric distribution with parameter
$P_{M}$ (such that Alice sends $n$ messages with probability $P_m(n) =
-(1-P_M)P_M^n$). We also tried three methods for assigning Alice's
-recipients: In the `uniform/uniform' (UU) model, Alice's $m$ recipients are
-chosen uniformly from among the $N$ recipients in the graph, and Alice sends
-to each of them with uniform probability. In the `background/uniform' (BU)
+(1-P_M)P_M^n$). We also tried two methods for assigning Alice's
+recipients: In the `uniform'
model, Alice's recipients are chosen according to their connectedness (so
that Alice, like everyone else, is likelier to know people who are already
-well-known), but Alice still sends to each with equal probability. Finally,
-in the `background/background' (BB) model, not only are Alice's recipients
+well-known), but Alice still sends to each with equal probability. In the
+`weighted' model, not only are Alice's recipients
chosen according to their connectedness, but Alice also sends to them with
-probability proportional to their connectedness. We selected these three
-models to examine the attack's effectiveness against users whose behavior
-is unrelated to other users' behavior (UU), users whose behavior is
-generated with the same model as other users' (BU), and users who mimic
-the background distribution (BB).
+probability proportional to their connectedness. We selected these
+models to examine the attack's effectiveness against users whose behavior is
+generated with the same model as other users' (U), and against users who mimic
+the background distribution (W).
\begin{figure}[ht]
\centering
\mbox{\epsfig{angle=0,figure=graphs/fig2a,width=4in}}
-\caption{Unknown background ($P_M=.60$): rounds to guess $m-1$ recipients
- ($90^{th}$ percentile of trial attacks)}
+\caption{Unknown background: Median rounds to guess all recipients}
\label{fig2a}
\end{figure}
-\begin{figure}[ht]
-\centering
-\mbox{\epsfig{angle=0,figure=graphs/fig2b,width=4in}}
-\caption{Unknown background ($P_M=.90$): rounds to guess $m-1$ recipients
- ($90^{th}$ percentile of trial attacks)}
-\label{fig2b}
-\end{figure}
-
-The results are in Figures \ref{fig2a} and \ref{fig2b}. Lines that run off
-the top of the graph represent cases in which the attacks did not converge on
-$m-1$ of Alice's recipients within 1,000,000 rounds. As expected, the attack
-succeeded fastest against the UU cases for equivalent values of
-$\left<N,m,b>\right>$, followed by BU and BB. Also, Alice's message volume
-parameter $P_M$ had little effect on the attack for the range examined, other
-than to force the attacker to wait for a greater number of rounds to elapse
-before Alice has sent enough traffic.
+The results are in Figure~\ref{fig2a}, along with the results for the
+original statistical disclosure attack as reference. As expected, the attack
+succeeded easily, and finished faster against uniform senders for equivalent
+values of $\left<N,m,b>\right>$ than it did against weighted senders.
+Interestingly, the attack against 'uniform' senders was {\it faster} than the
+original statistical disclosure attack---because the background traffic is
+now more clustered about popular recipients, Alice's recipients stand out
+more than they did before.
+%XXX say more? -NM
\subsubsection{Attacking pool mixes and mix-nets}
\label{subsec:sim-complex-mixes}
@@ -805,7 +797,8 @@
that can correspond to each input message. To simulate an attack against
pool mixes and mix-nets, we abstract away the actual pooling rule used by the
network, and instead assume that the network has reached a steady state, so
-that each mix sends the same fraction of the messages in its pool every
+that each mix retains the messages in its pool with the same probability
+($\Pdelay$) every
round. We also assume that all senders choose paths of exactly the same
length.
@@ -813,8 +806,8 @@
mix receiving a fixed number $b$ of messages, but by the passage of a fixed
interval of time. Thus, the number of messages sent by the background is no
longer a fixed $b-n_a$ (where $n_a$ is the number of messages Alice sends),
-but now follows a normal distribution with mean $B$ (and standard deviation
-set arbitrarily to $B/10$).\footnote{It's hard to determine the actual
+but now follows a normal distribution with mean $BG$ (and standard deviation
+set arbitrarily to $BG/10$).\footnote{It's hard to determine the actual
standard deviation of message volumes on the currently deployed remailer
network: automatic reliability checkers that send messages to themselves
(``pingers'') contribute to a false sense of uniformity, while other users
@@ -825,20 +818,26 @@
\begin{figure}[ht]
\centering
\mbox{\epsfig{angle=0,figure=graphs/fig34,width=4in}}
-\caption{Pool mixes and mix-nets: Rounds to guess $m-1$ recipients
- ($90^{th}$ percentile of trial attacks)}
+\caption{Pool mixes and mix-nets: Median rounds to guess all recipients}
\label{fig34}
\end{figure}
To examine the effect of pool parameters, we fixed $m$ at $32$ and $N$ at
-$2^16$. The results of these simulations are presented in
-Figure~\ref{fig34}. From this, we note two interesting effects: first,
-pooling has the most effect when Alice has a very high traffic volume, and is
-only incrementally helpful when Alice has
-
-
-less effective with intermediary values. Second,
+$2^16$, and had Alice use the `uniform' model discussed above. The results
+of these simulations are presented in Figure~\ref{fig34}. Lines running off
+the top of the graph represent cases in which fewer than half of the attacks
+converged upon Alice's recipients within 1,000,000 rounds, and so no median
+could be found.
+From these, we see that increased variability in message delay slows the
+attack by increasing the number of output messages that may correspond to any
+input message from Alice, effectively `spreading' each message across several
+output rounds. More interestingly, pooling is most effective at especially
+high or especially low volumes of traffic from Alice: the `spreading' effect
+here makes it especially hard for the attacker to recognize rounds that
+contain messages from Alice (when she sends less) or to recognize
+rounds that contain more messages (when she sends more).
+% XXX can you explain this better? -NM
\subsubsection{The impact of dummy traffic}
@@ -857,31 +856,40 @@
little trouble in learning Alice's recipients.
% Are there better citations for these strategies? Are there better names?
-We evaluated the effectiveness of two padding strategies. The first
-strategy (`geometric padding') is based on the link padding strategy from
-the Mixminion design \cite{minion-design}: Alice generates a random number
-of dummy messages in each round according to a geometric distribution with
-parameter $\Pjunk$,
-independent of her number of real messages. With second strategy
-(`imperfect threshold-padding'), we assume that Alice attempts to implement
-the unbreakable threshold-padding strategy (always send $M$ messages total
-in every round, adding dummies up to $M$ as necessary), but that her
-implementation is imperfect: when she needs to send more than $M$ real
-messages, she does so anyway rather than wait for a later round; and she is
-only sometimes online (with probability $\Ponline$ each round), and cannot
-send real messages or padding when she is not. (This last deviation in
-particular will be typical for any real-world user attempting to implement
-threshold padding in a world of unreliable hardware and network
-connections.)
+The first passing strategy we evaluated (``independent geometric padding'')
+is based on the link padding strategy from the Mixminion design
+\cite{minion-design}: Alice generates a random number of dummy messages in
+each round according to a geometric distribution with parameter $\Pjunk$,
+independent of her number of real messages.
+% With the second strategy
+%(`imperfect threshold-padding'), we assume that Alice attempts to implement
+%the unbreakable threshold-padding strategy (always send $M$ messages total
+%in every round, adding dummies up to $M$ as necessary), but that her
+%implementation is imperfect: when she needs to send more than $M$ real
+%messages, she does so anyway rather than wait for a later round; and she is
+%only sometimes online (with probability $\Ponline$ each round), and cannot
+%send real messages or padding when she is not. (This last deviation in
+%particular will be typical for any real-world user attempting to implement
+%threshold padding in a world of unreliable hardware and network
+%connections.)
\begin{figure}[ht]
\centering
\mbox{\epsfig{angle=0,figure=graphs/fig5a,width=4in}}
-\caption{caption for fig5a}
+\caption{Independent geometric dummy messages: Median rounds to guess all
+ recipients}
\label{fig5a}
\end{figure}
-(Results)
+Padding slows the attack, but does not necessarily stop it. As shown in
+Figure~\ref{fig5a}, geometric padding is most helpful when the underlying
+mix-net has a higher variability in message delay to `spread' the padding
+between rounds. With lower variability, Alice needs to send far more padding
+messages in order to confuse the attacker.
+
+We are currently running our simulations on other padding models, including
+``imperfect threshold padding'' (Alice always tries to pad up to a threshold
+of $M$ messages per round, but is sometimes offline).
\subsubsection{The impact of partial observation}
\label{subsec:sim-partial}
@@ -891,50 +899,153 @@
the mix-net simulation where the attacker can only observe a few mixes, and
try to see whether a non-global observer can do so also.
-% (have we defined 'entry'?)
+% (have we defined 'entry'?) -NM
Clearly, if Alice chooses only from a fixed set of entry and exit mixes as
-suggested by (XXXX cite here XXXX), and the attacker is watching none of
+suggested by \cite{XXXX}, and the attacker is watching none of
her chosen mixes, the attack will fail---and conversely, if the attacker is
watching all of her chosen mixes, the attack proceeds as before. For our
simulation, therefore, we assume that all senders (including Alice) choose
all mixes as entry and exit points with equal probability for each message,
and that the attacker is watching some fraction $f$ of the mixes. We
simulate this by revealing each message entering or leaving the network to
-the attacker with probability $\Pobserve=f$.
+the attacker with probability $\Pobserve=f$. The attacker sees a message
+it enters {\it and} when it exits with probability ${\Pobserve}^2$.
-(Results.)
+\begin{figure}[ht]
+\centering
+\mbox{\epsfig{angle=0,figure=graphs/fig6,width=4in}}
+\caption{Partial observation: Median rounds to guess all recipients}
+\label{fig6}
+\end{figure}
-%\subsection{Attacking a nym service (full linkability)}
-%\label{subsec:sim-full-linkability}
-%%nope
-%
-%\subsection{Attacking a fragmented community (partial linkability)}
-%\label{subsec:sim-partial-linkability}
-%%nope
-%
-%\subsection{Attacking a suspicious user}
-%\label{subsec:sim-suspicion}
-%%nope
-%
-%% Not simulated: time-variant traffic, attacks against multiple
-%% senders and recipients, partitioning attack
+The results in Figure~\ref{fig6} show that the attacker can still implement a
+long-term intersection attack even when he is only observing part of the
+network. When most of the network is observed ($\Pobserve>70\%$ in our
+results), the attack is hardly impaired at all. As more of the network is
+concealed (.4<$\Pobserve$<.7) the attack becomes progressively
+harder. Finally, as as $\Pobserve$ approaches $0$, the required number of
+rounds needed approaches infinity.
%======================================================================
\section{Conclusions}
\label{sec:conclusion}
+Our results demonstrate that long-term end-to-end intersection attacks can
+succeed under a variety of mix-net designs and complicating factors. In
+closing, we offer suggestions for mix-net designs, and suggest several open
+questions for future work.
-\subsection{Implications for mix-net design}
-\label{subsec:implications}
+\subsubsection{Implications for mix-net design}
+\label{subsubsec:implications}
+If we were to design a mix network based on our findings here, what steps
+should we take in order to frustrate intersection attack?
-\subsection{Future work}
-\label{subsec:future-work}
+The first lesson is this: {\bf high variability} in message delays is
+essential. By `spreading' the effects of each incoming message over several
+output rounds, delay variability increase each message's anonymity set, and
+amplifies the effect of padding.
+
+{\bf Padding} seems to slow traffic analysis, especially as the volume of
+padding begins to approach the the volume of the sender's actual messages,
+drowning out the signal.
+
+Users should be educated about the effects of their chosen {\bf message
+volume}: sending very infrequently is safe, especially if the user doesn't
+repeat the same traffic pattern long enough for the attacker to identify
+it. Conversely, sending ``almost always'' is comparatively safe. But users
+who send messages to the same group of recipients intermittently but
+frequently, over a long period of time, are increasing their vulnerability to
+intersection attacks.
+
+The threat of non-global observers must not be ignored. Much threat analysis
+for high-latency mix-net assumes that a passive adversary must watch the
+entire network in order to threaten anonymity. We have shown this to be
+false---any attacker who can watch the bulk of the servers Alice chooses as
+entry and exit points can run an intersection attack to learn her recipients.
+Thus, mix-nets should take steps to {\bf minimize the number of messages}
+that a limited attacker can see entering and exiting the network. Possible
+approaches include encouraging users to run their own mixes; choosing
+messages' entry and exit points to cross geographical and organization
+boundaries; and (of course) increasing the number of mixes in the network.
+% We said that fixed entry/exit might help too, but I now think it
+% wouldn't. Suppose the attacker observes c nodes out of n. If I
+% choose random paths, the attacker sees (c/n)^2 of my traffic with
+% probability 1. If I choose a fixed entry, the attacker sees c/n
+% of my traffic with probability c/n. No real difference.
+%
+% In fact, a limited attacker (P_observe=.2) with a diffuse target should
+% _hope_ that people choose fixed entries. If they do, then he can
+% eventually make the intersection attack work against the ones who use him
+% as their fixed entry. But if they _don't_ choose fixed entries, he only
+% sees 4% of everyone's traffic, which is not enough to break anybody.
+%
+% Fixed entries are a good idea for low-latency systems, when a single
+% connection with an attacker on each end compromises a sender--receiver
+% link.
+
+\subsubsection{Questions for future work}
+\label{subsubsec:future-work}
+Many questions remain to be answered before the effectiveness of long-term
+intersection attacks can be considered a closed problem.
+
+% These need to get re-ordered. -NM
+
+It would be beneficial to find closed-form equations for expected number of
+rounds required to mount these attacks, as Danezis does for statistical
+disclosure \cite{statistical-disclosure}.
+
+The attacks we have discussed here assume a purely passive adversary, but
+they can easily be generalized to incorporate information gained by an active
+attacker. Past work on avoiding blending attacks (flooding, trickle, $n-1$)
+has concentrated on preventing an attacker from gaining certain knowledge of
+a Alice's recipients---but in fact, an active attack that only reveals
+slight probabilities about Alice's recipients can provide information
+to speed up the intersection attacks in this paper.
+% also: run a server, knock down nodes, improve linkability, convince Alice
+% to be vulnerable.
+
+% Is this attack better or worse than other attacks? Probably neither:
+% this attack speeds up blending attacks, and relaxes the amount of
+% information that those attacks require to succeed.
+%
+% Should we explain this someplace? -NM
+
+It seems clear that pseudonymous services will fall to intersection attacks
+far faster than anonymizing services. How strong is this effect, and can it
+be prevented? (We are currently simulating scenarios related to pseudonyms.)
+
+Our analysis has focused on the impact of Alice's actions on Alice alone.
+How do Alice's actions (for example, choice of padding method) effect other
+users in the system?
+
+There are other possible approaches to thwarting traffic analysis, including
+alternative padding regimes (as mentioned above in the discussion for
+Figure~\ref{fig5a}). These should be investigated.
+
+Although real social networks behave more like scale-free networks than like
+the original disclosure attack's model, there are still more accurate models
+for user behavior than the one we have chosen here. For example, real users
+probably do not send messages with a geometric distribution independent of
+time: most people's email habits are based on a 24-hour sleep schedule. The
+effects of this variation may be significant.
+
+Many of our simulations found ``sweet spots'' for setting such as mix pool
+delay, message volume, padding volume, and so on. Identifying those points
+of optimality in the wild would be of great practical help for users.
+
+% impact on reputation systems
+
+% better mix algorithms
+
+%
\section*{Acknowledgments}
-%Thanks also to Gerald Britton, Geoffrey Goodell, Pete St. Onge, Peter
-%Palfrader, Al Riddoch, Mike Taylor, and Dave Turner for letting us run our
-%simulations on their computers.
+Thanks go to Gerald Britton, Geoffrey Goodell, Novalis, Peter Palfrader,
+Alistair Riddoch, Pete St. Onge, and Mike Taylor for letting us run our
+simulations on their computers.
+
%======================================================================
\bibliographystyle{plain} \bibliography{e2e-traffic}
\end{document}
+
Index: e2e-traffic.bib
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/e2e-traffic.bib,v
retrieving revision 1.7
retrieving revision 1.8
diff -u -d -r1.7 -r1.8
--- e2e-traffic.bib 24 Jan 2004 06:45:29 -0000 1.7
+++ e2e-traffic.bib 24 Jan 2004 14:44:32 -0000 1.8
@@ -410,7 +410,7 @@
www_pdf_url={http://www.nd.edu/~networks/Papers/physica.pdf}
}
-@article{small-worlds,
+@article{small-world,
title = {Collective dynamics of `small-world' networks},
author = {Duncan J. Watts and Steven H. Strogatz},
journal = {Nature},
***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs in the body. http://freehaven.net/