# [minion-cvs] patches before i dig in to the real patching

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

Modified Files:
minion-design.tex
Log Message:
patches before i dig in to the real patching

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

-Current research directions on MIX-nets include stop-and-go'' MIX-nets
+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}.

@@ -289,8 +289,8 @@
Cypherpunk remailer systems, in order to provide a simple extensible
design. We can retain minimal backwards compatibility by remixing''
Type II messages to be Type III messages, thus increasing the anonymity
-set of the Type III network. Type II messages, when travelling between
-remailers capable of understanding both Type II and III, are treated
+set of the Type III network. Type II messages travelling between
+Type III remailers are treated
as plaintext and encrypted to the next remailer in the chain using its
Type III key. The message is sent as a Type III encrypted message, but
it decrypts to reveal the Type II message.
@@ -358,7 +358,8 @@
\subsection{Indistinguishable replies}

-By making forward messages and replies indistinguishable, we prevent an
+By making forward messages and replies indistinguishable even to MIXes,
+we prevent an
adversary from dividing the message anonymity sets into two classes. In
particular, if replies are infrequent relative to forward messages,
an adversary who controls some of the MIXes can more easily trace the
@@ -440,7 +441,7 @@
\end{itemize}

To fulfill the above requirements we use a large-block cipher; that
-is, a cipher that acts as a permution on a block the size of its
+is, a cipher that acts as a permutation on a block the size of its
include LIONESS \cite{BEAR-LIONESS} and SPC \cite{SPC}.
The cryptographic property required is that of a super-pseudo-random
@@ -449,7 +450,7 @@
replays limits the number of oracle queries to 1; this will need
further analysis.  In that case the simpler BEAR construction
\cite{BEAR-LIONESS} could be used instead of LIONESS.}
-This ensures that if any bit of
+Thus if any bit of
the encrypted material is changed, the decryption will look like random
bits.  An SPRP is also equally secure in the encryption and decryption
directions.  See Section \ref{subsec:tagging} for a
@@ -515,7 +516,7 @@

We briefly considered introducing \emph{cover-trash} to frustrate
these tagging attacks; but that problem is as complex as the dummy
crossover point to prevent the attacker from learning information from
tagging attacks.  Specifically, our solution falls into several cases:

@@ -550,11 +551,13 @@
that the recipient is one of the local addresses.} and so we recommend
that the second leg be at least a few hops long.

-Replies are indistinguishable at every hop from forward messages. Even the
-crossover point cannot know whether it is processing a reply or forward message.
-The protocol doesn't allow a MIX to know its location in the path (other
-than the exit node), or the total length of the route.
-% FIXME we need to resolve this paragraph
+No MIX except the crossover point can distinguish forward messages from
+replies --- even the crossover point cannot be sure whether it is processing
+a reply or forward message, but it may be able to guess that crossover
+points are more frequent on forward paths than direct replies or
+%The protocol doesn't allow a MIX to know its location in the path (other
+%than the exit node), or the total length of the route.

\subsection{Multiple-message tagging attacks}
\label{subsec:multi-tagging}
@@ -1087,7 +1090,7 @@
delays: if the maximum latency of such a network is $t$, then the
anonymity set of a message leaving the network may be much smaller
than all messages that entered over a time $t$.
-% This is handwaving, and the problem is more that the distribtion
+% This is handwaving, and the problem is more that the distribution
% isn't uniform rather than the actual size of the anonymity set.
% It'll do for the time being. -DH

@@ -1100,7 +1103,7 @@
attacks even when free routes are used, as well as improving the

-The network has a fixed {\em batch period}, $t_{batch}$, which is closely
+The network has a fixed {\em batch period}, $t_\mathrm{batch}$, which is closely
related to the maximum desired latency; a typical value could be 3--6 hours.
Messages entering the network in each batch period are queued until
the beginning of the next period. They are then sent through the MIX-net
@@ -1112,10 +1115,11 @@
period in which it must be received, so that it cannot be delayed by an
attacker (which would be fatal for this design).

-The latency is between $\ell t_{hop}$ and $t_{batch} + \ell t_{hop}$, depending
-on when the message was submitted.
-Typically we would have $t_{hop} < t_{batch}/n$, so the latency is at
-most $2t_{batch}$, independent of the path length $\ell$.
+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
+$\ell$.

%The set of messages sent to a node in a given hop period is called a
%mini-batch, to distinguish it from the set of messages being sent