# [minion-cvs] patches to tighten. now 15pages + conclusion

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

Modified Files:
minion-design.tex
Log Message:
patches to tighten. now 15pages + conclusion
close enough :}

Index: minion-design.tex
===================================================================
RCS file: /home/minion/cvsroot/doc/minion-design.tex,v
retrieving revision 1.49
retrieving revision 1.50
diff -u -d -r1.49 -r1.50
--- minion-design.tex	8 May 2002 05:43:21 -0000	1.49
+++ minion-design.tex	8 May 2002 06:24:59 -0000	1.50
@@ -142,8 +142,8 @@
communications between MIXes but is unable to observe the reordering
inside each MIX.

-Recent research on MIX-nets includes stop-and-go'' MIX-nets
-\cite{kesdogan}, distributed flash MIXes'' \cite{flash-mix} and their
+Recent research on MIX-nets includes stop-and-go MIX-nets
+\cite{kesdogan}, distributed flash MIXes \cite{flash-mix} and their
weaknesses \cite{desmedt,mitkuro}, and hybrid MIXes \cite{hybrid-mix}.

One type of MIX hierarchy is a cascade.
@@ -173,8 +173,8 @@
PGP to encrypt and decrypt remailed messages. Later, Cottrell implemented
the Mixmaster system \cite{mixmaster,mixmaster-spec}, or Type II'' remailers,
-in the Cypherpunk remailers. Note that Mixmaster does not include reply
-functionality, so deployed remailer systems still use the less secure
+in the Cypherpunk remailers. Note that Mixmaster does not include replies,
+so deployed remailer systems still use the less secure

At about the same time, Gulcu and Tsudik introduced the Babel
@@ -244,7 +244,7 @@
\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
+MIX in her path, and sends the onion to the first MIX. Each
MIX unwraps a single layer of the onion, pads the message to a fixed
length (32 Kbytes in our current design), and passes the result to the
next MIX. We describe the behavior of the last MIX in
@@ -337,9 +337,9 @@
authenticate the whole message at every hop.  For forward messages,
derived deterministically, so that it is possible to calculate
-authentication tags for the whole message at each hop.  However,
+authentication tags for the whole message at each hop.  But
the situation becomes more complicated when reply messages are
-introduced, because the message and the reply block are
+introduced --- the message and the reply block are
created by different users.

\subsection{Replies}
@@ -378,7 +378,7 @@
\begin{enumerate}
\item \textbf{Forward} messages where only Alice remains anonymous.
\item \textbf{Direct Reply} messages where only Bob remains anonymous.
-\item \textbf{Anonymized Reply} messages where both Alice and Bob
+\item \textbf{Anonymized Reply} messages where Alice \emph{and} Bob
remain anonymous.
\end{enumerate}

@@ -585,9 +585,9 @@
so even if the adversary tags a subset of the messages he doesn't know
(unless he owns the whole cascade) where the tagged messages went.
}
-an adversary who wants to match a tag signature with certainty would
+to match a tag signature with certainty an adversary would
have to own all $k$ crossover points.  (And even then, it seems harder
-because the subsets of her messages would overlap with subsets of
+as the subsets of her messages would overlap with subsets of
messages from other senders.)

% The argument above seems a little handwavy to me.  We should either
@@ -602,7 +602,7 @@
the message to the second leg. Therefore, if the adversary doesn't own
most of the crossover points that Alice chooses, a successful
multiple-message tagging attack seems infeasible.  We leave a security
-analysis of this multiple-paths approach to future work; but see
+analysis of multiple-paths idea to future work; but see
Section \ref{sec:maintaining-anonymity}.

\section{Related design decisions}
@@ -773,7 +773,7 @@
One important entry in a node's capability block is its \emph{exit
policy}. Exit abuse is a serious barrier to wide-scale remailer deployment
--- rare indeed is the network administrator tolerant of machines that
-potentially deliver hate mail to the U.S. President.
+potentially deliver hate mail. % to the U.S. President.

On one end of the spectrum are \emph{open exit} nodes that will
deliver anywhere; on the other end are \emph{middleman} nodes that
@@ -1075,16 +1075,12 @@
%[This subsection is draft/experimental/controversial. Don't pay much
%attention to it yet.]

-How a MIX-net design groups messages into batches, and how paths are
-chosen, has a large effect on the degree of anonymity it can provide.
-A possible definition of ideal anonymity for a MIX-net is as follows:
-
-\begin{quote}
-Ideal anonymity is achieved when each message leaving (resp. entering)
-the network could correspond with uniform probability to any message
-entering (resp. leaving) the network, during a period approximately
-equal to the maximum network latency.
-\end{quote}
+A MIX-net design groups messages into batches and chooses paths; the
+approaches it uses affect the degree of anonymity it can provide. We
+might define ideal anonymity for a MIX-net to be when each message leaving
+(resp. entering) the network could correspond with uniform probability
+to any message entering (resp. leaving) the network, during a period
+approximately equal to the maximum network latency.

This ideal is not achieved by protocols like Mixmaster that use random
delays: if the maximum latency of such a network is $t$, then the
@@ -1098,9 +1094,10 @@
leave the network at any time) and uses free routes, it is subject to
the attacks described in Section 4 of \cite{disad-free-routes}.
% Should really summarise them, but I don't have time :-(
-One possible approach that we want to explore using Mixminion is a
-strategy called {\em synchronous batching}, that prevents these
-attacks even when free routes are used, as well as improving the
+We would like to explore a
+%One possible approach that we want to explore using Mixminion is a
+strategy called {\em synchronous batching}. This approach prevents these
+attacks even when free routes are used, and improves the

The network has a fixed {\em batch period}, $t_\mathrm{batch}$, which is closely
@@ -1117,8 +1114,9 @@

The latency is between $\ell t_\mathrm{hop}$ and $t_\mathrm{batch} + \ell t_\mathrm{hop}$, depending on when the message was submitted.
-Typically we would have $t_\mathrm{hop} < t_\mathrm{batch}/n$, so the
-latency is at most $2t_\mathrm{batch}$, independent of the path length
+Typically we would have $t_\mathrm{hop} < t_\mathrm{batch}/n$, where
+$n$ is the number of MIXes in the network, so the
+latency is at most $2t_\mathrm{batch}$ independent of the path length
$\ell$.

%The set of messages sent to a node in a given hop period is called a
@@ -1168,20 +1166,15 @@
%however it gives users no choice in the set of nodes used.

In practice, several considerations have to be balanced when choosing
-a batching strategy and network structure:
-
-\begin{enumerate}
-\item maximising anonymity sets, i.e. both batch sizes through each
-      node, and the overall anonymity sets of users,
-\item bandwidth considerations,
-\item reliability,
-\item enabling users to choose nodes that they trust,
-\item interactions with the reputation system.
-\end{enumerate}
+a batching strategy and network structure. These include maximising
+anonymity sets (both batch sizes through each node and the overall
+anonymity sets of users); bandwidth considerations; reliability;
+enabling users to choose nodes that they trust; and interactions with
+the reputation system.

-Further analysis of the trade-offs will be needed before choosing a
+Further analysis of is needed before we can choose a
final network structure. Note that a planned structure, where each
-users' software follows the plan consistently when constructing
+user's software follows the plan consistently when constructing
routes, will generally be able to achieve stronger and more easily
analysed security properties than less constrained approaches.

@@ -1250,19 +1243,18 @@
design to peripheral design choices, need more attention:

\begin{itemize}
-\item We need to analyze the proposed defense against the multiple-message
-tagging attack.
+%\item We need to analyze the proposed defense against the multiple-message
+%tagging attack.
\item We need more research on batching strategies that resist trickle
and flooding attacks \cite{batching-taxonomy} as well as intersection
attacks on asynchronous free routes \cite{disad-free-routes}.
-% help, say that last phrase better -RRD
\item We need a more thorough investigation of multiple-message tagging
-attacks, and an analysis of various ways of safely choosing paths when
+attacks, and an analysis of how to safely choose paths when
sending many messages.
\item We claim that we use conservative techniques, but an all-or-nothing
variable-length block cipher is pushing it. Can we keep indistinguishable
forward messages and replies using a simpler design?
-\item We need stronger intuition about how to improve security via
+\item We need stronger intuition about how to use
dummy messages.
\item We intend to draw up a more complete specification, which can lead
to implementation and deployment of the Mixminion design.