[minion-cvs] added a discussion of babel in the related work section

[arma@seul.org (Roger Dingledine)]

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

Modified Files:
	minion-design.tex 
Log Message:
added a discussion of babel in the related work section

added a footnote about the attack on babel timestamps

added a short section on how using mixminion with many messages
is going to be harder than we think. it needs more work; please
go fix it.

added a few more points to the conclusion. if you have anything else
on your mind as 'future directions' or 'unsolved problems', please go
add them.



Index: minion-design.tex
===================================================================
RCS file: /home/minion/cvsroot/doc/minion-design.tex,v
retrieving revision 1.37
retrieving revision 1.38
diff -u -d -r1.37 -r1.38
--- minion-design.tex	7 May 2002 06:52:50 -0000	1.37
+++ minion-design.tex	7 May 2002 11:34:51 -0000	1.38
@@ -168,14 +168,17 @@
 added message padding, message pools, and other MIX features lacking
 in the cypherpunk remailers. Note that Mixmaster does not include reply
 functionality, so deployed remailer systems still use the less secure
-long-term cypherpunk reply blocks. 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 Babel has distinguishable replies?  (_Possibly_
-% replayable and taggable ones too.)  -Nick
+long-term cypherpunk reply blocks.
 
+At about the same time, Gulcu and Tsudik introduced the Babel
+system \cite{babel}, a practical remailer design with many desirable
+features. While it provides replies, they are only indistinguishable
+from forward messages by passive observers; the MIX nodes can still
+distinguish. Babel's reply addresses are multiple-use, making them less
+secure than forward messages due to replay vulnerabilities. Babel also
+introduces \emph{inter-MIX detours}, where nodes can 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.
 
 %\subsection{Robustness}
 %
@@ -458,9 +461,9 @@
 
 For forward messages, Alice provides both legs; for anonymous replies, Alice
 uses Bob's reply block as the second leg, and generates her own path
-for the first leg.  (To send a direct reply, Alice can use an empty
+for the first leg.  To send a direct reply, Alice can use an empty
 first leg, or send the reply block and message to a MIX that can wrap
-them for her.)
+them for her.
 
 When Alice creates her message, she encrypts the second subheader
 with a hash of her payload (she also does the usual layered onion
@@ -580,6 +583,7 @@
 than the exit node), or the total length of the route.
 
 \subsection{Multiple-message tagging attacks}
+\label{subsec:multi-tagging}
 
 The above design is still vulnerable to a subtle and dangerous
 attack. If Alice sends a group of messages along the same path, the
@@ -676,7 +680,10 @@
 % I'm not sure, though, whether we want one of the cert-based ones (A)
 % or one of the the anon-server ones. (B) -Nick
 
-The purpose of link-layer encryption is to provide forward secrecy: 
+The purpose of link-level encryption is to provide forward secrecy: 
+% link-level, *not* link-layer. link-layer is a layer-2 OSI thing.
+% saying that our transport level protocol uses link-layer encryption
+% makes no sense. -RRD
 after the keys
 have been deleted, not even the
 nodes that exchange messages can decrypt or recognize messages
@@ -838,8 +845,16 @@
 the MIX has forgotten about it, the message's decryption will be exactly
 the same. Thus, Mixmaster does not provide the forward anonymity that we want.
 
-Chaum first observed this attack in \cite{chaum-mix}, but his solution
---- to include in each message a timestamp that describes when that message
+Chaum first observed this attack in \cite{chaum-mix},
+but his solution (which is proposed again in Babel\footnote{
+  Actually, Babel is vulnerable to a much more direct timestamp attack:
+  each layer of the onion is timestamped with ``the number of seconds
+  elapsed since January 1, 1970 GMT, to the moment of message composition
+  by the sender.'' Since the number of people composing a message on
+  the same second will likely be small, an adversary owning a MIX at the
+  beginning of the path and another at the end could trivially recognize
+  a message.
+}) --- to include in each message a timestamp that describes when that message
 is valid --- also has problems. Specifically, it introduces a new class
 of \emph{partitioning} attacks, where the adversary can distinguish and
 track messages based on timestamps. If messages have short lifetimes,
@@ -1004,7 +1019,7 @@
 reply blocks and block further messages from getting delivered.
 
 A more robust design uses a protocol inspired by e-mail retrieval
-protocols such as IMAP or POP \cite{IMAP,POP3}:
+protocols such as IMAP \cite{IMAP} or POP \cite{POP3}:
 messages arrive and queue at the nymserver, and the user periodically
 checks the status of his mail and sends a sufficient batch of reply
 blocks so the nymserver can deliver that mail. 
@@ -1038,19 +1053,51 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
-%\section{Maintaining anonymity sets}
-%
-%\subsection{Long-term nyms: how to choose paths for reply blocks}
-%\label{subsec:choosing-paths}
-%
-%This question is hard. We're going to have to argue about it for a
-%while more, I think.
-%
-%See subsec:batching above. --DH
-%
-%\subsection{Transmitting large files with Mixminion}
-%
-%\url{http://archives.seul.org/mixminion/dev/Apr-2002/msg00031.html}
+\section{Maintaining anonymity sets}
+
+\subsection{Transmitting large files with Mixminion}
+
+We would like to use Mixminion as a transport layer for higher-level
+anonymity applications such as anonymous publication systems
+\cite{freenet, freehaven}, but much research remains before we can
+provide security for users transferring large files over Mixminion.
+
+Alice wants to send a large file to Bob; thus she must send many Mixminion
+messages. Conventional wisdom suggests that she should pick a different
+% can I get a \cite here? -RRD
+path for every message, but an adversary that owns all the nodes in
+\emph{any} of the paths could learn her identity --- without any work
+at all. (Even an adversary owning a very small fraction of the network
+can perform this attack, since the Mixminion message size is small.)
+
+% Assuming Alice picks five nodes at random for
+%each path, at 28k of data per packet (assuming no redundancy or overhead)
+%an adversary owning only 1\% of the MIXes has a better than even chance
+%of identifying Alice as soon as she sends her fourteen packet. By the
+%time she sends message 92 (meaning her file is roughly 2.5 megabytes),
+%Alice has a less than 1\% chance of keeping her anonymity.
+
+Alice seems more likely to maintain her unlinkability by sending all the
+messages over the same path. On the other hand, a passive adversary can
+still watch the flood of messages traverse that path. We must hope the
+honest nodes will rearrange and obfuscate streams of messages enough to
+foil these attacks. The multiple-message tagging attacks described in
+Section \ref{subsec:multi-tagging} make the situation even more dangerous.
+
+A compromise approach is to pick a small number of paths and use them
+together. Still, if the messages are sent all at once, it seems clear
+we're going to need some really good cover traffic schemes before we
+can offer security.
+
+\subsection{Long-term nyms: how to choose paths for reply blocks}
+\label{subsec:choosing-paths}
+
+In fact, this same problem comes up when the owner of a pseudonym is
+downloading his mail from a nymserver.
+
+Cue for David Hopwood's discussion, somewhere around here. Feel free
+to muck this section up however it seems best.
+
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
@@ -1123,22 +1170,24 @@
 free-route attacks \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 analyze of various ways of safely choosing paths when
+attacks, and an analysis of various ways of safely choosing 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
+dummy messages.
 \item We intend to draw up a more complete specification, which can lead
 to implementation and deployment of the Mixminion design.
-\item and there are a few more
 % We'll have to get another spec cobbled together before anybody can review
 % this system thorougly.  Should we mention some place for people to
 % get a more formal spec?  I wouldn't be able to review our system at
 % the level that I'd want to without one.  -Nick 
 \end{itemize}
 
-
-
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
-\section*{Acknowledgments} Removed for anonymous review.
+%\section*{Acknowledgments} Removed for anonymous review.
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%