[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] Revise previous work section
Update of /home/freehaven/cvsroot/doc/e2e-traffic
In directory moria.mit.edu:/tmp/cvs-serv22640
Modified Files:
e2e-traffic.tex
Log Message:
Revise previous work section
Index: e2e-traffic.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/e2e-traffic/e2e-traffic.tex,v
retrieving revision 1.12
retrieving revision 1.13
diff -u -d -r1.12 -r1.13
--- e2e-traffic.tex 21 Jan 2004 02:09:41 -0000 1.12
+++ e2e-traffic.tex 21 Jan 2004 03:23:29 -0000 1.13
@@ -200,18 +200,31 @@
\section{Previous work}
\label{sec:previous-work}
\label{subsec:mix-nets}
+Chaum \cite{chaum-mix} proposed hiding the correspondence between sender and
+recipient by wrapping messages in layers of public-key cryptography, and
+relaying them through a path composed of \emph{mixes}. Each mix in turn
+decrypts, delays, and re-orders messages, before relaying them toward their
+destinations. Chaum proved the security of a mix against a \emph{passive
+ adversary} who eavesdrops on all communications but is unable to observe
+the reordering inside the mix. Because some mixes might be controled by an
+adversary, Alice may direct her messages through a sequence or `chain' of
+mixes in a network, so that no single mix can link her to her recipient.
-Chaum \cite{chaum-mix} proposed hiding the correspondence between sender
-and recipient by wrapping messages in layers of public-key cryptography,
-and relaying them through a path composed of \emph{mixes}. Each mix
-in turn decrypts, delays, and re-orders messages, before relaying them
-toward their destinations.
+Many subsequent designs have been proposed, including Babel \cite{babel},
+Mixmaster \cite{mixmaster}, and Mixminion \cite{mixminion}.
+% XXX also cite \cite{shuffle} and \cite{abe}
+We will not address the diferences 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
+and leaving the network, and can guess when a message entering the network is
+likely to leave.
-% Must say something about mixnets here.
+%%(Some designs, such as DC-nets \cite{chaum-dc}, Herbivore \cite{herbivore},
+%%and whats-this-called \cite{k-anonymous}, seek prevent eavesdroppers from
+%%learning when participannts are sending and receiving.)
-% terms to possible define: mixmaster, mixminion, anonymity set.
-% mention that there are a bunch of mix network designs, but they're
-% all the same to us.
+% Mention that there are low-latency systems, but that they are too easy
+% to break with short-term end-to-end confirmation attacks.
% talk about how we're only concerned here with systems where the
% senders and receivers are distinct from the mix servers. in those
@@ -221,23 +234,23 @@
linking anonymous senders with the messages they send, by linking
anonymous recipients with the messages they receive, or by linking
anonymous messages with one another. For a detailed list of attacks,
-consult \cite{back01,raymond00}. Attackers may
+consult \cite{back01,raymond00}. Attackers can
trace messages through the network by observing network
traffic, compromising mixes, compromising keys, delaying messages
so they stand out from other traffic, or altering messages
-in transit. They may learn a given message's destination
+in transit. They can learn a given message's destination
by flooding the network with messages, replaying multiple copies
of a message, or shaping traffic to isolate the target message from
-other unknown traffic \cite{trickle02}. Attackers may
+other unknown traffic \cite{trickle02}. Attackers can
discourage users from using honest mixes by making them unreliable
-\cite{back01,casc-rep}. They may analyze intercepted message text to
+\cite{back01,casc-rep}. They can analyze intercepted message text to
look for commonalities between otherwise unlinked senders
\cite{rao-pseudonymity}.
\subsection{The intersection attack}
Even if all the above attacks are foiled, an adversary can
-mount a long-term \emph{intersection attack} to correlate the times at
+mount a \emph{long-term intersection attack} to correlate the times at
which senders and receivers are active \cite{disad-free-routes}.
Researchers have provided a variety of countermeasures to increase
@@ -245,13 +258,13 @@
\cite{stop-and-go} provides probabilistic anonymity by letting users
specify message latencies -- essentially broadening the range of times
messages might emerge from the mix network. Similarly, batching strategies
-\cite{trickle02} in Mixmaster and Mixminion use message
+\cite{trickle02} as in Mixmaster and Mixminion use message
pools to spread out the possible exit times for messages.
Rather than expanding the set of messages that might have
been sent by a suspect sender, other designs expand the set of
senders that might have sent a suspect message. A sender who
-participates as a node in the mix network can conceal whether a
+also runs a node in the mix network can conceal whether a
given message originated at her node or was relayed from another node
\cite{bennett:pet2003,tarzan:ccs02,crowds:tissec}. But even in these
designs, the adversary can observe whether certain traffic patterns are
@@ -261,17 +274,22 @@
A sender can also conceal whether she is currently active by consistently
sending decoy (dummy) traffic. Pipenet \cite{pipenet} conceals
traffic patterns by constant padding on every link. Unfortunately, a
-single user can shut down the network simply by not sending. Backing
-off even a little bit from this constant-padding scheme is thought to
-allow the
-above intersection attack, and in some systems may even introduce
-conspicuous gaps in traffic that can be followed through the network
-\cite{defensive-dropping}.
-%possibly take out the above sentence -RD
+single user can shut down the network simply by not sending.
+%%Backing
+%%off even a little bit from this constant-padding scheme has been thought to
+%%allow the
+%%above intersection attack, and in some systems may even introduce
+%%conspicuous gaps in traffic that can be followed through the network
+%%\cite{defensive-dropping}.
+%
+% I might be wrong, but doesn't the cite suggest that 'backing off even a
+% little' is actually kinda safe?
+%
Berthold and Langos aim to increase the
difficulty of intersection attacks with a scheme for preparing plausible
-dummy traffic and having other nodes send it for you while you're offline
-\cite{langos02}; but their design has many practical problems.
+dummy traffic and having other nodes send it on Alice's behalf when she is
+offline
+\cite{langos02}, but their design has many practical problems.
Finally, note that while the adversary can perform this long-term
intersection attack entirely passively, active attacks can help him
@@ -331,36 +349,29 @@
a round $i$ where Alice has send a message, each element of $\V{o_i}$ will
have value $1/b$ if it corresponds to a recipient who has received a message,
and $0$ if it does not.
-Taking the arithmetic mean $\B{O}$ of a large set of the observation
+Taking the arithmetic mean $\B{O}$ of a large set of these observation
vectors gives (by the law of large numbers):
\[\B{O} = \frac{1}{t}\sum_{i=i}^{t} \V{o_i} \approx
\frac{\V{v} + (b-1)\V{u}}{b} \]
-From this, the attacker estimates
+From this, the attacker estimates Alice's behavior:
\[\V{v} \approx b\frac{\sum_{i=1}^t \V{o_i}}{t} - (b-i)\V{u}\]
-% XXXX Maybe add a simple example?
-
-\XXXX{Should we report George's findings on preconditions and
- required time to succeed?}
-
-\XXXX{mention that this doesn't take much space or time.}
+Danezis also derives a precondition that the attack will only succeed when
+\( m < \frac{N}{b-1} \), and is expected to take
+\[t > \left[ ml \left(\sqrt{\frac{m-1}{m}} +
+ \sqrt{\frac{N-1}{N^2}(b-1)} \right) \right]^2 \]
+rounds to succeed with $95\%$ confidence for $l=2$ and $99\%$ confidence for
+$l=3$.
%======================================================================
\section{Extending the statistical disclosure attack}
\label{sec:extending}
-
-\XXXX{All the math in this section is kinda fishy; we need a
- good stats person to phrase this right. I may be weighting when
- I shouldn't, modeling things strangely, and so on. I am convinced,
- empirically, that the attacks {\it work}---but I don't know whether
- my explanation of them is correct. ---Nick.}
-
\subsection{Broadening the attack}
\label{subsec:broadening}
In this subsection, we examine ways to extend Danezis's Statistical
Disclosure Attack to systems more closely resembling real-world mix-nets. In
-section \ref{sec:simulation}, we discuss the additional time and information
-required for each attack to succeed.
+section \ref{sec:simulation}, we examine the time and information
+requirements for these attacks against simulated networks.
\subsubsection{Complex senders, unknown background traffic}
\label{subsubsec:complex-senders}
***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs in the body. http://freehaven.net/