[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[freehaven-cvs] Addressed (minimally) comment from ref1 about citing...
Update of /home/freehaven/cvsroot/doc/batching-taxonomy
In directory moria.seul.org:/home/aas23/doc/batching-taxonomy
Modified Files:
taxonomy.bib taxonomy.tex
Log Message:
Addressed (minimally) comment from ref1 about citing work from the
Dresden group. The section was far too well written for me to modify
it substantially.
I personally think (unless pushed by you very much) will ignore the
comment below:
> -some of your mixtypes are not useable in the real world, because the
> transit time in a mix can be infinite. How does a timeout change your
> analysis?
The next two comments:
>-what are the possibilities and the expense for the attacker if the
> users control the work of the mix, especially by testing packets,
> as suggested by SG-Mixes?
>
>- how affects a higher level of dummy traffic the work of the
> attacker? (i.e. batch filled dummies)
I don't understand.
This:
> at the end of your paper should be a summary/table with the
> properties of mix concepts in regard to the n-1 attacks.
I agree with, but have nto done anything about yet. Could someone add that?
> The related work section states, without adequite citational evidence,
> that active attacks have been extensively discussed in the literature, but
> not rigorously analyzed or evaluated.
Put in citations .. Maybe SG mixes is not very appropriate here.
I ignore this:
> One minor complaint: In Section 3, the paper says: "When we talk about
> anonymity, we mean sender anonymity." Don't you mean unlinkability?
I don't really know what terminology is more commonly used, would
anyone care to express an opinion?
Index: taxonomy.bib
===================================================================
RCS file: /home/freehaven/cvsroot/doc/batching-taxonomy/taxonomy.bib,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -d -r1.2 -r1.3
--- taxonomy.bib 7 May 2002 07:55:42 -0000 1.2
+++ taxonomy.bib 15 Aug 2002 15:50:44 -0000 1.3
@@ -22,6 +22,7 @@
title = {Reliable {MIX} {C}ascade {N}etworks through {R}eputation},
howpublished = {Proceedings of Financial Cryptography 2002},
note = {\newline \url{http://www.freehaven.net/papers.html}},
+ year = {2002}
}
@article{chaum81untraceable,
@@ -390,6 +391,38 @@
month = {April},
OPTorganization = {},
OPTpublisher = {},
+ OPTnote = {},
+ OPTannote = {}
+}
+
+@Proceedings{FGJP98,
+ title = {Comparison of Commitment Schemes Used in Mix-Mediated
+ ANonymous Communication for Preventinf Pool-Mode Attacks},
+ year = {1998},
+ OPTkey = {},
+ booktitle = {3rd Australasian Conference on Information Security and Privacy (ACISP'98},
+ editor = {C. Boyd and E. Dawson},
+ OPTvolume = {},
+ number = {1438},
+ series = {LNCS},
+ OPTaddress = {},
+ OPTmonth = {},
+ OPTorganization = {},
+ publisher = {Springer-Verlag},
+ OPTnote = {},
+ OPTannote = {}
+}
+
+
+@PhdThesis{Jer2000,
+ author = {Anja Jerichow},
+ title = {Generalisation and Security Improvement of Mix-mediated Anonymous Communication},
+ school = {Technischen Universitat Dresden},
+ year = {2000},
+ OPTkey = {},
+ OPTtype = {},
+ OPTaddress = {},
+ OPTmonth = {},
OPTnote = {},
OPTannote = {}
}
Index: taxonomy.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/batching-taxonomy/taxonomy.tex,v
retrieving revision 1.16
retrieving revision 1.17
diff -u -d -r1.16 -r1.17
--- taxonomy.tex 18 Jun 2002 11:49:10 -0000 1.16
+++ taxonomy.tex 15 Aug 2002 15:50:44 -0000 1.17
@@ -37,13 +37,12 @@
attacks against them by altering the traffic between the mixes. We
show that if certain mixes are used, such attacks cannot destroy the
anonymity of a particular message completely. We work out the cost of
-these attacks in terms of the messages that the attacker must
-insert into the network and the time he must spend.
-We discuss advantages and disadvantages of these mixes and the
-settings in which their use is appropriate. Finally, we look at dummy
-traffic and SG mixes as other promising ways of protecting against the
-attacks, point out potential weaknesses in existing design, and suggest
-improvements.
+these attacks in terms of the number of messages that the attacker
+must insert into the network and the time he must spend. We discuss
+advantages and disadvantages of these mixes and the settings in which
+their use is appropriate. Finally, we look at dummy traffic and SG
+mixes as other promising ways of protecting against the attacks, point
+out potential weaknesses in existing designs, and suggest improvements.
\end{abstract}
% This paper was motivated by conversations with the Mixmaster
@@ -62,10 +61,10 @@
Many modern anonymity systems are based on mixes. Chaum first
introduced the concept in 1981 \cite{chaum81untraceable}, and since
-then researchers and developers have described many mix
-variations. These have different aims and approaches, yet we still
-fail to understand the performance and anonymity tradeoffs between
-them.
+then researchers and developers have described many mix variations,
+eg. \cite{flash-mix,babel,Kesdogan98}. These have different aims and
+approaches, yet we still fail to understand the performance and
+anonymity tradeoffs between them.
In fact, some of the mixes used in well-known fielded systems such as
Mixmaster \cite{Cott94} are mentioned only briefly or not at all in
@@ -76,16 +75,17 @@
More specifically, an attacker targeting a specific message going into
a mix can manipulate the batch of messages entering that mix so the
-only unknown message in the batch is the target message
-\cite{Cott94,Babel}. This manipulation may involve delaying or
+only message unknown to him in the batch is the target message
+\cite{Cott94,babel}. This manipulation may involve delaying or
dropping all other incoming messages (a \emph{trickle} attack),
-flooding the batch with its own known messages (a \emph{flooding}
-attack), or some combination of the two which we call the blending attack.
+flooding the batch with attacker messages (a \emph{flooding}
+attack), or some combination of the two which we call the
+\emph{blending} attack.
%Chaff and winnow to be inserted here or elsewhere in the text?
We provide a rigorous analysis and comparison of several properties of
-each mix variant, including anonymity set, latency, and resistance to
+each mix variant, including anonymity, latency, and resistance to
blending attacks. We also give intuition and guidelines about which
environments and circumstances are most suitable for each mix variant.
@@ -93,45 +93,38 @@
\label{attacks}
In the past, many anonymity systems have been concerned with
-protecting their users against passive adversaries. For instance,
-Crowds \cite{reiter98crowds} is secure against a local passive
-adversary while Onion Routing \cite{goldschlag99onion} protects
-against traffic analysis by global passive adversaries in some
-configurations but not others.
-
-%[actually, onion routing is broken by a global passive adversary,
-%because he can trivially do traffic confirmation attacks. -RRD
-%*are* there any schemes that are robust against a global passive
-%adversary but not against some form of active adversary? This
-%seems an odd way to motivate. Hm. -RRD]
+protecting their users against passive adversaries, either global or
+local, ususally citing the $n-1$ or the blending attack as a
+vulnerability, with (quoting \cite{Berthold00}) ``no general
+applicable method to prevent this attack''. In this paper we discuss
+ways of reducing this vulnerability.
-%(AAS: Yes, there is the issue of traffic analysis vs traffic
-%confirmation.... Ok, it's not very good, can you think of a better
-%way to introduce this?)
+%New intro. Opinions?
Here we consider a global \emph{active} adversary who is not only able
to see the traffic on all the links, but also to delay (remove) and
insert arbitrarily many messages into the system in a short (constant)
-time. These are reasonable assumptions --- methods of logging per-packet
-data on high bandwidth links exist, as does the possibility of
-building fast hardware to insert or delay messages. We further
-assume our attacker can send messages from many different
-source addresses; indeed, infrastructures to ensure sender authentication
-have proved difficult to build.
+time. These are reasonable assumptions --- methods of logging
+per-packet data on high bandwidth links exist, as does the possibility
+of building fast hardware to insert or delay messages. We further
+assume our attacker can send messages from many different source
+addresses; indeed, infrastructures to ensure sender authentication
+have proved difficult to build. Thus, the threat of the active
+attacker comes from him having the power to log and manipulate
+messages on the links.
Note that the global active attacker can be viewed as a combination of
two separate attackers: one who can only insert messages (global
inserting attacker) and one who can only delay messages (global
delaying attacker).\footnote{In fact, in theory only insertion of
- messages is necessary given assumptions such as predictable bounds
- on network link capacities. This is because the global inserting
- adversary can insert enough messages to cause any volume or time
- delay on any traffic. This reduction also assumes that either no
- two legitimate messages appear in the same network queue or that it
- is not necessary to ever delay so as to cause a reordering of
- legitimate messages. It is more realistic to model attacks as a
- combination of delays and insertions, and we will not make further
- mention of this potential reduction.}
+messages is necessary given assumptions such as predictable bounds on
+network link capacities. This is because the global inserting
+adversary can insert arbitrarily many attacker messages between any
+two good messages. This reduction also assumes that it is never
+necessary to cause a reordering of legitimate messages. However, it
+is more realistic to model attacks as a combination of delays and
+insertions, and we will not make further mention of this potential
+reduction.}
%\framebox{\parbox{11cm}{Paul says:\\
% Note the footnote.}}
@@ -173,8 +166,7 @@
all, the mix is strongly resistant to active attacks.
\item If no blending attack can reduce the anonymity of any message
-below a constant $k$, then the mix has blending attack anonymity of
-$k$.
+below a constant $k$, then the mix has blending attack anonymity $k$.
\item If the attacker can always reduce the anonymity of a message
arbitrarily, but never to $0$, the mix is vulnerable to non-exact,
@@ -203,10 +195,9 @@
Note that Mix 1 is vulnerable only to non-exact blending attacks,
while the Mix 2 is vulnerable to exact certain attacks.
-We now analyze and categorize several mixes. We suggest their blending
-attack cost functions (both of time and space) where necessary. We
-also look at SG mixes \cite{Kesdogan98}, an approach specifically
-designed to protect against active attacks, in section \ref{SG}.
+We now proceed to analyze and categorize several mixes. We suggest
+their blending attack cost functions (both of time and number of
+messages) where necessary.
%Actual cost functions are a massive pain because it is unclear quite
%what the optimal attack is, say, ``given 500 messages''. On the other
@@ -224,25 +215,24 @@
\begin{itemize}
-\item The mixes take a constant time to fire.
+\item The mixes take a constant time to fire (send messages out).
\item The mixes have limited physical memory and so can only contain a
finite number of messages.
-
-\item Mixes will not replay messages.
-
+\item Mixes deal with message replays.
% \framebox{\parbox{11cm}{Paul says:\\
% This seemed implicit in the paper, and I think was explicit in
% our conversation. Note that even this gives some information,
% viz: in a successful n-1, I can tell if the message has been
% sent through the mix already.}}
+% AAS: Paul, I had the same comment. Where do we use ``no replays'' again?
-\item Messages might or might not arrive at a uniform rate.
+\item Messages may or may not arrive at a uniform rate.
\item In calculating the minimum anonymity we assume the global
-passive attacker. The vulnerability to the active attacker is
+passive adversary. The vulnerability to the active attacker is
described separately.
\item When we talk about anonymity, we mean sender anonymity. Similar
@@ -255,14 +245,14 @@
\paragraph*{Parameters:} $n$, threshold.
\paragraph*{Flushing Algorithm:}
-When the mix collects $n$ messages, it flushes.
+When the mix collects $n$ messages, it fires.
\paragraph*{Message Delay:}
-The minimum delay is $\epsilon$ (the message arrives when there are
-$n-1$ messages already in the mix). The maximum delay can be
-infinite (when a message arrives to a mix and no more ever
-arrive). The mean delay can be calculated if we assume a constant rate
-of arrival $r$, in which case it is $\frac{n}{2r}$.
+The minimum delay is $\epsilon$ (the target message arrives when there
+are $n-1$ messages already in the mix). The maximum delay can be
+infinite (the target arrives at a mix and no more ever arrive).
+Assuming a constant rate of arrival of messages $r$, we can calculate
+the mean delay: $\frac{n}{2r}$.
\paragraph*{Anonymity:} $n$.
We assume that all the messages in the batch are from different senders
@@ -270,17 +260,13 @@
\paragraph*{Blending Attack Behaviour:}
The attack proceeds as outlined in Section \ref{attacks} and is
-usually referred to as the $n-1$ or the flooding attack. It takes
-$\epsilon$ time as the attacker is able to insert all messages in a
-constant time and the mix takes a constant time to fire (twice if
-necessary). The attack takes a minimum of $n-1$ (if the attacker can
-detect that the mix is empty, he simply forwards the target message to
-the mix along with his $n-1$ messages to flush it out) and a maximum
-of $2n-2$ messages if the attacker cannot detect how many messages are
-in the mix and must delay the attacked message until the mix has
-fired. If there are sufficient other legitimate messages and the
-attacker allows them through one at a time until the mix fires, then
-the maximum number of attacker messages is also $n-1$.
+usually referred to as the $n-1$ or the flooding attack. It takes
+$\epsilon$ time as inserting the required messages and the (usually
+two) firings of the mix mix take a constant time. The attack takes a
+minimum of $n-1$ (the attacker waits until the mix is empty, forwards
+the target message to the mix along with $n-1$ attacker messages to
+flush it out) and a maximum of $2n-2$ messages (the attacker does not
+wait for the mix to become empty).
\paragraph*{Adversaries:}
The above attack seemingly requires both the global delaying attacker
@@ -288,7 +274,7 @@
this is not necessarily so. If the global inserting attacker is able
to insert $n-1$ of its own messages between each of the ``good''
messages going into a mix, he effectively mounts an $n-1$ attack on
-each one.
+each of them.
Another possible attack scenario is when an attacker owns a mix in a
free route mix network. He has the capability to delay all the
@@ -308,11 +294,11 @@
$t$, period.
\paragraph*{Flushing Algorithm:}
-The mix flushes every $t$ seconds.
+The mix fires every $t$ seconds.
\paragraph*{Message Delay:}
The minimum delay is $\epsilon$, which occurs if the message arrives
-just before the mix is due to be flushed. The maximum delay is
+just before the mix is due to be fire. The maximum delay is
$t-\epsilon$, which is the case when the message arrives just
after. The mean delay is $\frac{t}{2}$.
@@ -320,7 +306,7 @@
The minimum anonymity set is $0$ --- no messages arrive during the
entire time period. The maximum anonymity set is theoretically
infinite, but in practice is limited by the capacity of the mix. The
-mean anonymity set (assuming a rate of arrival of messages $r$) is
+mean anonymity set (assuming a rate of arrival of $r$ msgs/s) is
$rt$.
Note that the threshold and timed mixes are in some sense dual. If the
@@ -346,11 +332,11 @@
\paragraph*{Blending Attack Behaviour:}
The attack is exact and certain and proceeds as follows: The adversary
delays the target message for a maximum of time $t$ until the mix
-flushes. He then forwards in the target message and blocks all other
-incoming messages. After another $t$ seconds the mix flushes again
+firess. He then forwards in the target message and blocks all other
+incoming messages. After another $t$ seconds the mix fires again
producing the target message on its own. This takes a maximum of
$2t-\epsilon$ and a minimum of $\epsilon$ seconds (when the mix was
-empty and about to be flushed), and $0$ messages. The attack is
+empty and about to be fire), and $0$ messages. The attack is
usually referred to as the trickle attack.
%As opposed to the treacle attack which would just be messy!
@@ -369,7 +355,7 @@
threshold, $n$; period, $t$.
\paragraph*{Flushing Algorithm:}
-The mix flushes every $t$ seconds or when $n$ messages accumulate in
+The mix fires every $t$ seconds or when $n$ messages accumulate in
the mix.
\paragraph*{Message Delay:}
@@ -397,7 +383,7 @@
threshold, $n$; period, $t$.
\paragraph*{Flushing Algorithm:}
-A mix flushes every $t$ seconds but only when at least $n$ messages have
+A mix fires every $t$ seconds but only when at least $n$ messages have
accumulated in the mix.
\paragraph*{Message Delay:}
@@ -526,27 +512,25 @@
\paragraph*{Blending Attack Behaviour:}
In general, the blending attack has two phases: flushing the mix so
that no good messages remain inside it, then forwarding in the target
-message and flushing it out onto the network. In the past, the whole
-attack used two mix flushes. With pools, two flushes are no longer
-sufficient. Furthermore, there is now a small but non-zero
+message and flushing it out onto the network. With simple mixes, one
+flush was sufficient for each phase. With pool mixes, this is no
+longer the case. Furthermore, there is now a small but non-zero
probability that a given message (e.g. the target message) remains in
the mix for an arbitrary length of time. Intuitively, the attack
ceases to be certain. It proceeds as follows:
The attacker delays the target message, fills up the pool mix and
flushes it. If $j$ of the attacker messages don't come out, he knows that
-% critical fix -- i added a "don't". true? -RRD
-% True. Sorry. AAS.
-$f-j$ good messages remain inside the pool mix. He now delays all
-the other incoming good messages and tries to flush them out of the
-mix (he can detect all good messages coming out). Of course, this
-takes more messages than to flush out a threshold mix (see below
-for details), but the attack is still exact (if/when the attacker
-succeeds in getting all the messages to leave the mix, he knows
-it). Once the mix is flushed, he just sends in the target message, and
-flushes the mix as before until the target message comes out. Because
-the attacker is not guaranteed to flush out the mix completely or to
-flush out the target message, the attack is uncertain.
+$f-j$ good messages remain inside the pool mix. He now delays all the
+other incoming good messages and tries to flush them out of the mix
+(he can detect all good messages coming out). Of course, this takes
+more messages than to flush out a threshold mix (see below for
+details), but the attack is still exact (if/when the attacker succeeds
+in getting all the messages to leave the mix, he knows it). Once the
+mix fires, he just sends in the target message, and flushes the mix as
+before until the target message comes out. Because the attacker is not
+guaranteed to flush out the mix completely or to flush out the target
+message, the attack is uncertain.
Note that this attack crucially depends on the attacker being able to
delay messages
@@ -577,7 +561,7 @@
The average delay of a message through this mix is 1.6
rounds. Assuming the attacker targets a mix with 60 messages,
the expected number of good messages remaining in the mix falls below
-1 after 5 rounds or 500 messages.
+1 after 5 rounds or 500 attacker messages.
\end{exa}
Thus, the use of a pool mix in an anonymity system not only makes the
@@ -590,7 +574,7 @@
\paragraph*{Parameters:} $t$, period; $f$, pool; ($0$, threshold).
\paragraph*{Flushing Algorithm:}
-The mix is flushed every $t$ seconds. A pool of $f$ messages chosen
+The mix fires every $t$ seconds. A pool of $f$ messages chosen
uniformly at random is retained in the mix. The others are forwarded
on. If fewer then $f$ messages are in the mix, it does not fire.
(Thus, strictly speaking, this is a threshold and timed pool mix, for
@@ -621,9 +605,8 @@
potentially, a whole host of other features). Of course, in practice,
a record of the only last few rounds gives a good approximation.
-Assuming a threshold pool mix has a threshold larger than the pool
-size, the minimum anonymity of a timed pool mix is clearly smaller
-than that for the threshold pool mix. We note that in pool mixes the
+The minimum anonymity of a timed pool mix is clearly smaller
+than that of the threshold pool mix. We note that in pool mixes the
bulk of the anonymity comes from mixing the target message with the
batch of incoming messages, not from mixing it with the messages in
the pool. Because the timed mix does not always have this batch of
@@ -632,10 +615,10 @@
mix.
\paragraph*{Blending Attack Behaviour:}
-Two flavours of blending attack are possible on this mix.
-Because the adversary has no control over when the mix flushes, he can
-add many or just a few messages to each flush. (He prevents all
-other messages from reaching the mix).
+Two flavours of blending attack are possible on this mix. Because the
+adversary has no control over when the mix fires, he can add many or
+just a few messages to each batch. (He prevents all other messages
+from reaching the mix).
By adding as many messages as possible in one round, he maximizes the
probability that after one flush only the attacker messages will be
@@ -669,7 +652,7 @@
$t$, period; $min$, pool; $frac$, fraction; ($0$ threshold).
\paragraph*{Flushing Algorithm:}
-The mix gets flushed every $t$ seconds. A fraction $frac$ of randomly
+The mix fires every $t$ seconds. A fraction $frac$ of randomly
chosen messages inside the mix at the time remain in the mix. But if
there are $min$ or fewer messages in the pool, it outputs no messages.
@@ -813,6 +796,33 @@
attack significantly (if at all). Thus, we shall not pursue it
further.
+%\subsection{Alternative Active Attack Scenario}
+%
+%In this paper we are concerned with an adversary mounting an active
+%attack by delaying or inserting messages on the links, possibly by
+%having black boxes which log and manipulate traffic. In this case,
+%compromised mixes do not add to the power of the adversary attacking a
+%mix system (either network or cascade).
+%
+%The alternative scenario is to have the adversary own up to $m-1$
+%compromised mixes and examine the active attacks he can mount. This
+%has been explored in detail in, eg. \cite{Jer2000}. We summarise the
+%results here. If the attacker owns \emph{all} the mixes which may send
+%a message to a compromised mix, he can bridge it with a blending
+%attack. In a cascade, this amounts to owning mixes which precede all
+%the honest mixes\footnote{In theory, owning just the first mix in a
+%cascade is sufficient, but the attack of such an adversary on a
+%cascade of pool mixes will be expensive.}. In a free route mix
+%network, the adversary needs to own $m-1$ mixes. To combat this
+%attack, verification schemes have been proposed, eg.
+%\cite{chaum81untraceable}. However, systems which consist of pool
+%mixes are harder to verify -- the attacking mix can legitimately delay
+%the target message for an arbitrarily long period of time. Schemes
+%for preventing the $n-1$ attack in a system with pool mixes is
+%presented in \cite{FGJP98,Jer2000}.
+
+% AAS: A more substantial description of the other work.
+
\subsection{Resisting Blending vs Verification}
The tools that we give honest mixes to protect against these blending
@@ -827,15 +837,20 @@
hop.
Many basic mix verification schemes, such as that proposed in
-\cite{chaum81untraceable} where senders observe the batches exiting
-a mix to confirm it processed their messages, require schemes where
-the messages come out with the next mix flush. More complex
-robustness schemes \cite{flash-mix} enforce timely message processing
-if the adversary does not own a threshold of participating mixes. The
-receipt and witness scheme of \cite{mix-acc} works because a mix loses
+\cite{chaum81untraceable} where senders observe the batches exiting a
+mix to confirm it processed their messages, require schemes where the
+messages come out with the next mix flush. More complex robustness
+schemes \cite{flash-mix} enforce timely message processing if the
+adversary does not own a threshold of participating mixes. The receipt
+and witness scheme of \cite{mix-acc} works because a mix loses
reputation if it hasn't obtained a receipt from the next hop within
-the allowed timeframe. All of these systems are designed to ensure that
-messages will leave each mix predictably.
+the allowed timeframe. All of these systems are designed to ensure
+that messages will leave each mix predictably. Yet more verification
+schemes which work in a system with pool mixes are described in
+\cite{Jer2000,FGJP98}. There the authors propose a commitment scheme
+which ensures that the mix comits to a decision before he receives the
+target message, and its actions are verifiable by the sender of the
+target message.
In some topologies, such as free route mix networks, a widespread
delaying attack is difficult to perform because the adversary must
@@ -912,7 +927,7 @@
message will still stand out. A good link padding scheme may be able to
further frustrate him, but much more research remains.
-Babel \cite{Babel} introduces \emph{inter-mix detours}, a scheme where mix
+Babel \cite{babel} introduces \emph{inter-mix detours}, a scheme where mix
nodes can choose to rewrap a message and send it through a few randomly
chosen new hops --- so even the sender cannot be sure of recognizing
his message as it leaves the mix. This approach could help complicate
@@ -924,7 +939,8 @@
While active attacks have been widely cited in the literature and
methods of protection against them have been suggested informally,
-most of these have not been rigorously analysed or evaluated.
+most of these have not been rigorously analysed or evaluated
+\cite{Cott94,babel,Jer2000,Kesdogan98}.
We will concentrate our attention on one particular proposal -- Stop
and Go Mixes \cite{Kesdogan98}. The authors outline several techniques
***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs in the body. http://freehaven.net/