# [minion-cvs] redid "robustness" related work section

Update of /home/minion/cvsroot/doc
In directory moria.seul.org:/home/arma/work/minion/doc

Modified Files:
minion-design.tex
Log Message:
redid 'robustness' related work section
(basically i copied it from casc-rep rather than mix-acc)

Index: minion-design.tex
===================================================================
RCS file: /home/minion/cvsroot/doc/minion-design.tex,v
retrieving revision 1.25
retrieving revision 1.26
diff -u -d -r1.25 -r1.26
--- minion-design.tex	5 May 2002 23:21:43 -0000	1.25
+++ minion-design.tex	5 May 2002 23:55:16 -0000	1.26
@@ -75,8 +75,7 @@

Chaum first introduced anonymous remailer designs over 20 years ago
\cite{chaum-mix}. The research community has since introduced many new
-designs and proofs \cite{big-chain-of-cites}, and discovered a variety
-of new attacks \cite{more-cites}, but the
+designs and proofs and discovered a variety of new attacks, but the
state of deployed remailers has changed remarkably little since Cottrell
published his Mixmaster software \cite{mixmaster-attacks} in 1994.
Part of the difficulty in expanding the deployed remailer base is
@@ -114,7 +113,6 @@

% Mention that Mixminion spec is on track for adoption as Mixmaster v3?

-
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Related Work}
@@ -159,39 +157,32 @@
PGP to encrypt and decrypt remailed messages. Later, Cottrell implemented
the Mixmaster system \cite{mixmaster}, or Type II'' remailers, which
-in the cypherpunk remailers. At about the same time, Gulcu and Tsudik
-introduced the Babel system \cite{babel}, which also created a practical
-remailer design (although one that never saw widespread use).
-
-% Mention that Type-I is vulnerable to replays, and Type II has no replies?
-% -Nick
+in the cypherpunk remailers. Note that Mixmaster did not include reply
+functionality, so deployed remailer systems still use the less secure
+Tsudik introduced the Babel system \cite{babel}, which also created a
+practical remailer design (although one that never saw widespread use).

\subsection{Robustness}

-Some previous work investigates a notion of the \emph{robustness}
-of MIX-nets in the context of a distributed MIX system
-\cite{flash-mix}. A MIX is considered robust if it survives the
-failure of any $k$ of $n$ participating servers, for some threshold
-$k$. This robustness is all or nothing: either $k$ servers are
-good and the MIX works, or they are not good and the MIX likely will
-not work.
+Previous work primarily investigates the \emph{robustness} of MIX-nets
+in the context of a distributed MIX system \cite{flash-mix}. A MIX
+is considered robust if it survives the failure of any $k$ of $n$
+participating servers, for some threshold $k$. This robustness is
+all-or-nothing: either $k$ servers are good and the MIX works, or they are
+not good and the MIX likely will not work.

-Robustness has been achieved primarily via the use of zero-knowledge
-proofs of correct computation; participants use such proofs to convince
-each other that they follow the protocol correctly without revealing secret
-information. Done na\"{\a i}vely, this incurs significant
-Jakobsson showed how to use precomputation to reduce the overhead of
-such a MIX network to about 160 modular multiplications
+Robustness has been achieved primarily via zero-knowledge proofs of
+correct computation.  Jakobsson showed how to use precomputation to reduce
+the overhead of such a MIX network to about 160 modular multiplications
per message per server \cite{flash-mix}, but the protocol was later
-found to be flawed \cite{mitkuro} by Mitsumo and Kurosawa. They
-proposed a fix for the protocol, but the efficacy of this fix remains
-to be evaluated.  A different approach was taken by Desmedt and
-Kurosawa \cite{desmedt}, but their technique requires many
-participating servers. Other work, such as Abe's MIX \cite{abe},
-provides \emph{universal verifiability} in which any observer can
-determine after the fact whether a MIX cheated or not, but
-the protocol is still computationally expensive.
+found to be flawed \cite{mitkuro} by Mitomo and Kurosawa.  Desmedt and
+Kurosawa's alternate approach \cite{desmedt} requires many participating
+servers. Abe's MIX \cite{abe} provides \emph{universal verifiability} in
+which any observer can determine after the fact whether a MIX cheated,
+but the protocol is still computationally expensive. Neff recently
+made further efficiency improvements to universally verifiable mixing
+\cite{shuffle}.

\subsection{Remailer Statistics}

@@ -225,7 +216,7 @@
anonymity set.

Mixminion uses the same general MIX-net paradigm as previous work
-\cite{chaum-mix,mixmaster-attacks,others}. The sender Alice chooses a
+\cite{chaum-mix,mixmaster-attacks,babel}. The sender Alice chooses a
path through the network. She repeatedly onion'' encrypts her message,
starting with the last
MIX in her path, and sends the onion to the first MIX in her path. Each
@@ -235,7 +226,8 @@

While Mixminion protects against known \emph{traffic analysis} attacks
(where an adversary given a message attempts to learn its sender or
+receiver \cite{rackoff93cryptographic,raymond00}), we do not fully
confirmation} attacks. In a traffic confirmation attack, the adversary
treats the MIX network as a black box and observes the behavior of
senders and receivers. Over time, he can intersect the set of senders
@@ -249,7 +241,7 @@
the same time, we provide a new feature: a reply block mechanism that
is as secure as forward messages.

-Reusable reply blocks, such as those in the cipherpunk remailer, are a
+Reusable reply blocks, such as those in the cypherpunk remailer, are a
security risk --- by their very nature they let people send multiple
messages to them. These multiple messages can be used to very quickly
trace the recipient's path: if two incoming batches both include a
@@ -312,6 +304,7 @@
messages, do not need to run any new software.

% Do we ever say how to send a reply without software? -Nick
+% Nope. We're just bluffing. Is that ok? -RRD

We divide a message's path into two \emph{legs}; thus the header is
split into two equal-size subheaders as well. Each hop contains a hash
@@ -338,8 +331,9 @@
the property that if any bit of the encrypted material is changed the
decryption will look like random bits. We can use BEAR in a mode where
decryption and encryption are equivalent, by using the same key for
-both hash steps. See Section \ref{subsec:tagging} for a discussion of
+both its hash steps. See Section \ref{subsec:tagging} for a discussion of
% Both hash steps''?  We never mention Bear's hash steps... -Nick
+% True. Does adding 'its' help? -RRD
how this all-or-nothing encryption approach helps protect against tagging.

\begin{figure}
@@ -357,6 +351,8 @@
\label{subsec:tagging}

% We never define what a tagging attack is. -Nick
+% Yes we do. This following paragraph does, give or take. Should
+% we say more? -RRD

The crossover point is critical to preventing tagging attacks. Without
it, an adversary could tag the payload of a forward message when it
@@ -513,26 +509,6 @@
sources, leading to smaller anonymity sets.}
In our current design, this information is placed
in a variable-length annex to the final header.
-%\footnote{It must be
-%prevent people from creating SURBs that can be delivered by SMTP.
-%On the one hand, under the header swap'' method described in
-%\ref{subsec:header-swap}, the all-or-nothing property of BEAR prevents
-%the generator of a reply block from putting any information in the
-%payload.  On the other hand, under the distinguish replies'' method
-%in \ref{subsec:distinguish-replies}, the delivery information would
-%create a portion of the payload that the final node could
-%distinguish from random garbage, thus allowing a tagging attack
-% See my messages of April 9 and 10 titled SMTP service'' for a more
-% detailed version of the above argument. -Nick
-%
-% Should we say _why_ it's undesirable to force reply recipients to
-% run local nodes?  [My answer is (A) that some people (such as human
-% rights activists using internet cafes) want to get replies, but
-% don't have persistant net connections, (B) that Mixmaster
-% supports it, and not doing so would be a step backwards, and (C)
-% that there's not much reason not to.]    -Nick

The types each MIX supports are described in a \emph{capability block},
which also includes the MIX's address, long-term (signing) public key,
@@ -605,7 +581,7 @@
number of available open exit nodes remains a limiting security parameter
for the remailer network.

-\subsection{Message expiration, and replay prevention, and key rotation}
+\subsection{Message expiration, replay prevention, and key rotation}

Mixmaster offers rudimentary replay prevention by keeping a list of recent
message IDs. To keep the list from getting too large, it expires entries
@@ -625,10 +601,7 @@
rare: an adversary can delay a message until near its expiration date,
then release it and trace it through the network.

-% need to read stop & go mix paper here.
-
-%More generally, these partitioning attacks arise whenever a message can be
-%very rare' and valid' at the same time.
+% need to read stop & go mix paper here. -RRD

One way of addressing this partitioning attack is to add dummy traffic
so that it is less rare for messages to arrive near their expiration date;