[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] More tightening
Update of /home/freehaven/cvsroot/doc/e2e-traffic
In directory moria.mit.edu:/tmp/cvs-serv29470
Modified Files:
e2e-traffic.tex
Log Message:
More tightening
Index: e2e-traffic.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/e2e-traffic.tex,v
retrieving revision 1.50
retrieving revision 1.51
diff -u -d -r1.50 -r1.51
--- e2e-traffic.tex 2 May 2004 23:18:34 -0000 1.50
+++ e2e-traffic.tex 2 May 2004 23:45:42 -0000 1.51
@@ -354,9 +354,8 @@
\label{subsec:broadening}
Here we examine ways to extend Danezis's statistical
disclosure attack to systems more closely resembling real-world mix networks.
-We will examine the time and information requirements for several of these
-attacks in Section~\ref{sec:simulation} below, by running them against
-simulated networks.
+We will simulate the time and information requirements for several of these
+attacks in Section~\ref{sec:simulation} below.
\subsubsection{Complex senders, unknown background traffic:}
% \label{subsubsec:complex-senders}
@@ -408,16 +407,16 @@
% \label{subsubsec:complex-mix} can't usefully label subsubsections.
Most designs have already abandoned fixed-batch mixes in
favor of other algorithms that better hide the relation
-between senders and recipients. Such improved algorithms include
+between senders and recipients. Such algorithms include
timed dynamic-pool mixes, generalized mixes, and randomized versions of
each \cite{pet2003-diaz,trickle02}. Rather than reordering and
-relaying all the messages whenever a fixed number $b$ arrive,
+relaying all messages whenever a fixed number $b$ arrive,
these algorithms store received messages in a {\it pool}, and at fixed
-intervals relay a {\it fraction} of the pooled messages, based on the pool's
+intervals relay a {\it fraction} of the pooled messages based on the pool's
current size.
When attacking such a mix, the attacker no longer knows for certain
-which batches of recipients contain messages from Alice. Instead,
+which batches contain messages from Alice. Instead,
the attacker can only estimate, for each batch of output messages,
the probability that the batch includes one or more of Alice's messages.
@@ -428,9 +427,10 @@
of a round have an equal probability of being included in that round's batch.
Thus, we can characterize the mix's pooling algorithm as a probability
function $\PMIX(b|s)$---the probability that the mix relays $b$ messages
-when it has $s$ messages in the pool. Clearly, $\forall s,
-\sum_{b=0}^{s}\PMIX(b|s) = 1$: the mix will always relay between $0$
-and $s$ messages.
+when it has $s$ messages in the pool.
+%Clearly, $\forall s,
+%\sum_{b=0}^{s}\PMIX(b|s) = 1$: the mix will always relay between $0$
+%and $s$ messages.
%In the case of a timed dynamic-pool mix, this distribution is:
%\[ P_{TDP}(b|s) =
@@ -457,16 +457,16 @@
%Dummy messages can hamper these techniques to an extent discussed
%in \cite{dummy-msgs}.
Now, when Alice sends a message in round
-$i$, the attacker observes rounds $i$ through some later round $i+k$,
+$i$, the attacker observes round $i$ through some later round $i+k$,
choosing $k$ so that $\sum_{j=k+1}^{\infty} P_R^i(j)$ is negligible.
The attacker then uses $P_R$ to
-compute $\B{O_w}$, the mean of the observations from all of these rounds,
+compute $\B{O_w}$, the mean of the observations from these rounds,
weighted by the expected number of messages from Alice exiting in each
round:
\[ \B{O_w} = \sum_i \sum_{r=0}^k P_R^i(r) \cdot m_i \cdot \V{o_{i+r}}
\approx \frac{\B{m} \cdot \V{v} + (\B{n}-\B{m})\V{u}}{\B{n}} \]
-To solve for Alice's behavior $\V{v}$, the attacker now needs a good estimate
+To solve for Alice's behavior $\V{v}$, the attacker now needs an estimate
for the background $\V{u}$. The attacker gets this by
averaging observations $\V{u_i}$ from batches with a negligible probability of
including messages from Alice. Such batches, however, are not
@@ -480,17 +480,15 @@
\[\V{u} \approx \frac{1}{1-\delta_a}
\left[ \B{n} \cdot \B{U'} - \delta_a \cdot \V{v} \right] \]
-Senders can also deviate from the original model
-by directing their messages through multi-hop paths
-in a network of mixes. While using a mix network increases the effort an
-attacker must spend to observe all messages leaving the system, it
+Senders can also direct their messages through multi-hop paths
+in a network of mixes. While using a mix network increases the effort
+needed to observe all messages leaving the system, it
has no additional effect on intersection attacks beyond changing the
-delaying characteristics $P_R$ of the anonymity system.
-
-Assume for the sake of simplicity that all mixes have the same
-delay distribution $P_R$, and that Alice chooses a path of length $\ell_0$.
+system's delaying characteristics.
+Assume (for simplicity) that all mixes have the same
+delay distribution $P_R$, and that Alice chooses paths of length $\ell_0$.
The chance of
-the message being delayed by a further $d$ rounds is now
+a message being delayed by a further $d$ rounds is now
\[ P_R'(\ell_0+d) = \binom{\ell_0+d-1}{d} (1-P_D)^{\ell_0} P_D^d \]
%If Alice chooses her path length probabilistically according to
%$P_L(\ell)$, we have
@@ -561,6 +559,7 @@
that deliver messages to recipients. (Typically, not all mixes do
so. For example, only about one third of current Mixminion servers support
delivery.)
+%For Mixmaster, it's about one half.
A non-global attacker's characteristics depend on which parts of the
network he can observe. If the attacker
@@ -661,11 +660,11 @@
written by the same sender than two messages selected at
random.\footnote{Encrypting all messages end-to-end would address most of
these attacks, but is often difficult in practice. Most recipients do not
- run anonymity software, and many don't even have support for encrypted
+ run anonymity software, and many don't have support for encrypted
email or encrypted SMTP links. Thus, many messages still leave today's mix
- networks in plaintext. Furthermore, today's most popular email encryption
+ networks in plaintext. Furthermore, today's most popular encryption
standards (such as PGP and SMIME) have enough variation for an attacker to
- narrow down which implementations could have generated a given message.}
+ tell which implementations could have generated a given message.}
%Linkages may be more abstract: a
%sophisticated attacker could check for the presence of certain
@@ -674,9 +673,9 @@
To exploit these scenarios, the attacker
chooses a set of $c$ partitioning classes (such as languages or
-patterns of use), and assigns to each observed output
-message a probability of belonging to each class. The attacker then
-proceeds as before, but instead of collecting observation
+patterns of use), and assigns each observed output
+message a probability of belonging to each class. Instead of collecting
+observation
vectors with elements corresponding to recipients, the attacker now
collects observation vectors whose elements correspond to number of
messages received by each
***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs in the body. http://freehaven.net/