[minion-cvs] ongoing cleaning of section 2

[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:
ongoing cleaning of section 2


Index: minion-design.tex
===================================================================
RCS file: /home/minion/cvsroot/doc/minion-design.tex,v
retrieving revision 1.69
retrieving revision 1.70
diff -u -d -r1.69 -r1.70
--- minion-design.tex	4 Nov 2002 23:06:05 -0000	1.69
+++ minion-design.tex	5 Nov 2002 04:32:39 -0000	1.70
@@ -70,11 +70,13 @@
 
 \end{abstract}
 
-\noindent \textbf{Keywords:} anonymity, mix-net, peer-to-peer, remailer, nymserver, reply block
+\begin{center}
+\textbf{Keywords:} anonymity, mix-net, peer-to-peer, remailer, nymserver, reply block
+\end{center}
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
-\section{Introduction}
+\section{Overview}
 \label{sec:intro}
 
 Chaum first introduced anonymous remailers over 20 years ago
@@ -94,18 +96,18 @@
 less secure Cypherpunk Type I remailer design \cite{remailer-history}. We
 introduce a new primitive called a \emph{single-use reply block} (SURB),
 which makes replies as secure as forward messages. Our design goes a
-step further: in Mixminion most remailers in a path cannot distinguish
+step further: in Mixminion the remailers themselves cannot distinguish
 reply messages from forward messages. We also describe how to securely
 build higher-level systems such as nymservers using these SURBs. By
 integrating reply capabilities into Mixminion, we can finally retire
 the Type I remailer network.
 
 \item \textbf{Forward anonymity:} Mixmaster uses SMTP (normal mail) for
-transport. We use TLS over TCP between remailers; thus we can introduce
-link encryption with ephemeral keys to ensure forward anonymity for
+transport. We use TLS over TCP between remailers to encrypt the links,
+and use ephemeral keys to ensure forward anonymity for
 each message. Link encryption also makes obsolete many active and
 passive attacks on the communication links, forcing attackers to run
-corrupt nodes to perform most attacks.
+corrupt nodes for most attacks.
 
 % We also provide flexible delivery schemes ---
 %rather than just allowing delivery to mail or Usenet, we allow designers
@@ -129,12 +131,12 @@
 replays a given message, that message's decryption will be exactly the
 same. Thus replayed messages completely break the security of the mix
 \cite{chaum-mix}. Mixmaster offers rudimentary replay prevention by
-keeping a list of recent message IDs. To keep the list from getting too
-large, it expires entries after a server-configurable amount of time. But
-now the adversary simply has to wait until the mix has forgotten about a
+keeping a list of recent message IDs --- but to keep the list from
+getting too long, it expires old entries. The adversary simply has to
+wait until the mix has forgotten about a
 message before replaying it. Mixminion counters this flaw by introducing
 key rotation: a message is addressed to a given key, and after the key
-changes no messages to that key will be accepted; so the mix can forget
+changes no messages to the old key will be accepted; so the mix can forget
 about all the messages addressed to old keys. It turns out that the
 number of hashes a node needs to remember between key rotations is not
 too great a burden.
@@ -158,7 +160,7 @@
 %and part is due to the complexity of the current infrastructure ---
 %it is fairly hard to add new experimental features to the current software.
 
-We review the basic mix-net protocol in Section \ref{sec:related},
+We review mixes and mix-nets in Section \ref{sec:background},
 and then address the above list of improvements in Sections
 \ref{sec:design}-\ref{sec:nymservers}. We conclude with a list of future
 work (tasks which we should do next and feel confident we can complete),
@@ -180,35 +182,49 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
-\section{Overview and background}
-%% This is a new 'overview' section to come after the toplevel
-%% intro; with content as suggested by Roger.  I don't know what we
-%% should rename the intro to.
-%%
-%% Also, the writing here NEEDS to be cleaned up.  -NM
-%
-% What's a mix-net?
-In a mix-net, senders achieve anonymity by routing their
-messages through a path of relay servers, or `mixes.'  When Alice
-wants to send an anonymous message to Bob through the mixes $M_1$,
-$M_2$, and $M_3$, she encrypts her message successively with the
-public keys of the mixes in reverse order, and includes routing
-information for each mix, so that each mix $M_i$ receives the address
-of $M_{i+1}$ along with the payload intended for $M_{i+1}$, all
-encrypted with $M_i$'s public key.  
-% This is kind of unclear.  Maybe integrate the paragraph from below
-% that says 'mixminion uses the same general mix-net paradigm...'
-% 
-% needs references, too
+\section{Background}
+\label{sec:background}
 
-% What do mixes do?
-When a mix receives a message, it decrypts it with its public key, 
-and delays it according to some `batching rule' so that an observer
-cannot easily associate its outputs with its inputs.  It then
-extracts the address of the next mix in the path from the
-decrypted message, and passes on the contents of the message.
+Chaum introduced the concept of using relay servers, or \emph{mixes},
+for anonymous communications \cite{chaum-mix}. Each mix has a public key
+which senders use to encrypt messages to it. The mix receives a batch
+of these encrypted messages, decrypts them, and delivers them. Because
+a decrypted message looks nothing like the original encrypted message,
+and because the mix collects a batch of messages and then sends out the
+decrypted messages in a new order, an observer cannot learn which incoming
+message corresponds to which outgoing message. Chaum demonstrated the
+security of a mix against a \emph{passive adversary} who can eavesdrop on
+all communications but is unable to observe the reordering inside the mix.
 
-% XXXX Mention how this provides any anonymity!
+However, trusting a single mix is dangerous: the mix itself could be
+controlled by the adversary. Therefore users send their messages through
+several mixes: if some of the mixes are honest (not run by the adversary),
+anonymity will be preserved. In most schemes, the sender chooses the
+mixes that will make up her message's path. Specifically, when Alice
+wants to send an anonymous message to Bob through mixes $M_1$, $M_2$,
+and $M_3$, she encrypts her message successively with the public keys of
+the mixes in reverse order. She includes routing information at each hop,
+so that each mix $M_i$ receives the address of $M_{i+1}$ along with the
+message intended for $M_{i+1}$ (all encrypted with $M_i$'s public key).
+Recent research on mix networks (mix-nets) includes stop-and-go mix-nets
+\cite{kesdogan}, ...and others XXX.
+%distributed flash mixes \cite{flash-mix} and their weaknesses
+%\cite{desmedt}\cite{mitkuro}, and hybrid mixes \cite{hybrid-mix}.
+
+A mix network where Alice chooses her route freely from all mixes is known
+as a \emph{free-route} mix-net. Another approach is a \emph{cascade}
+network, where users choose from a set of fixed paths through the
+mix-net. Cascades can provide greater anonymity against an adversary
+who owns many mixes \cite{disad-free-routes}, but they are also more
+vulnerable to blending attacks \cite{batching-taxonomy} (see Section
+\ref{subsec:batching}). Further, cascade networks arguably have lower
+maximum anonymity because the number of people Alice might be confused
+with (her \emph{anonymity set}) is limited to the number of messages
+the weakest node in her cascade can handle; a free-route network on
+the other hand can create a very high anonymity set because 
+
+Mix cascade research includes real-time mixes
+\cite{realtime-mix} and web mixes \cite{web-mix}.
 
 % What's a reply block?
 When recipients want to achieve anonymity, some mix-net designs allow
@@ -218,65 +234,6 @@
 are provided by the user that eventually sends a message to the
 recipient.
 
-% How does mixminion fit in?
-Mixminion's principal difference from earlier mix-net designs is the
-mechanism it uses to support reply messages with the same processing
-machinery as non-reply messages, while at the same time resisting the
-attacks described below in REF.
-% This could be phrasesd far better
-
-\subsection{Design goals and assumptions}
-% this needs more material, and a bit less 'attitude' :)
-
-% Server requirements
-First of all, the system must be relatively simple to deploy.  Past
-systems have never found it easy to get a reliable group of mix
-operators to run long-lived servers; Mixminion must add as few
-technical barriers as possible.  Thus our protocol
-requires only loose clock synchronization (within a few minutes);
-it must achieve acceptable performance on commodity hardware; and
-it must require little coordination between servers.
-
-% Client requriements
-Furthermore, software adoption has also been a barrier to past
-systems. (REF?) Thus, we only require users who receive anonymity
-from the system to run special software --- that is, users should
-be able to receive messages from anonymous senders and send messages
-to anonymous recipients with a standard email
-client.  Users must also be able to send and receive anonymous
-messages using only commodity hardware.  Finally, although users with
-persistent network connections are necessarily more resistant to
-intersection attacks than users with intermittent connections (see
-REF below), the system must still support users with intermittent
-connections and offer them as much anonymity as possible.
-
-We assume a well-funded adversary who can
-observe all traffic on the network, who can generate, modify,
-delete, or delay traffic on the network, who can operate mixes of its
-own, and who can compromise some fraction of the mixes on the network.
-We assume that such an adversary is attempting to compromise users'
-anonymity by learning (or guessing with a reasonable probability) who
-is communicating with whom. In particular the adversary wants to use
-all information contained in the network traffic patterns to trace
-communication back or forth and gain additional knowledge about
-communicating partners.
-%What else is the adversary trying to do?
-
-The mixminion network tries to make is as hard as possible for an
-adversary observing the network to gain any additional information
-about communicating partners beyond an \emph{a-priory} belief. It does
-this by providing very little information to outside observers, and
-intermediate nodes, to avoid intersection attacks. In particular even
-intermediary nodes are not aware of the actual route length, that can
-be as long as 32 hops, or their position in the network. Furthermore
-the processing for replies is exactly the same as for normal messages
-and it is therefore difficult to partition the anonymity sets by
-distinguishing between them. 
-
-% replies: we want to avoid partitioning by having reply messages be
-%   indistinguishable from forward messages, and just as secure.  To the
-%   extent possible, a mix should not be able to learn any more from a
-%   message's contents than from the fact of the message's receipt.
 \subsection{Known attacks against mix-nets}
 
 Attacks against mix-networks aim at reducing the anonymity of users by
@@ -284,8 +241,8 @@
 out of it. These attacks either try to subvert the process of
 selecting routes or hiding the correspondance by corrupting mixes, or
 they try to use side channels containing some information that can be
-used to link messages together. Finally is none of the above are
-possible traffic analysis can take place whereby the flows of messages
+used to link messages together. Finally if none of the above are
+possible, traffic analysis can take place whereby the flows of messages
 are processed to find out the most likely recipients or senders. This
 attack can happen in conjunction with injecting traffic controlled by
 the attacker.
@@ -351,72 +308,99 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
-\section{Related Work}
-\label{sec:related}
+%\section{Related Work}
+%\label{sec:related}
 
-\subsection{Mix-nets}
+%\subsection{Deployed Remailer Systems}
 
-Chaum introduced the concept of a mix-net for anonymous communications
-\cite{chaum-mix}. A mix-net consists of a group of servers, called
-mixes (or mix nodes), each of which is associated with a public
-key. Each mix receives encrypted messages, which are then decrypted,
-batched, reordered, and forwarded on without any information
-identifying the sender. Chaum demonstrated the security of mixes
-against a \emph{passive adversary} who can eavesdrop on all
-communications between mixes but is unable to observe the reordering
-inside each mix.
+%The first widespread public implementations of mixes were produced by the
+%Cypherpunks mailing list. These ``Type I'' \emph{anonymous remailers}
+%were inspired both by the problems surrounding the {\tt anon.penet.fi}
+%service \cite{helsingius}, and by theoretical work on mixes. Hughes wrote
+%the first Cypherpunk anonymous remailer \cite{remailer-history}; Finney
+%followed closely with a collection of scripts that used Phil Zimmermann's
+%PGP to encrypt and decrypt remailed messages. Later, Cottrell implemented
+%the Mixmaster system \cite{mixmaster}\cite{mixmaster-spec}, or ``Type II'' remailers,
+%which added message padding, message pools, and other mix features lacking
+%in the Cypherpunk remailers.
 
-Recent research on mix-nets includes stop-and-go mix-nets
-\cite{kesdogan}, distributed flash mixes \cite{flash-mix} and their
-weaknesses \cite{desmedt}\cite{mitkuro}, and hybrid mixes \cite{hybrid-mix}.
+%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.
 
-One type of mix hierarchy is a cascade.
-In a cascade network, users choose from a set of fixed paths through
-the mix-net.
-Cascades can provide greater anonymity against a large adversary:
-free-route systems allow an adversary who owns many mixes to use
-intersection attacks to reduce the set of possible senders or receivers
-for a given
-% still not quite worded well. -RRD
-message \cite{disad-free-routes}. On the other hand, cascades are more
-vulnerable \cite{batching-taxonomy} to trickle attacks, where 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{mixmaster-attacks}\cite{babel}.
-Mix cascade research includes real-time mixes \cite{realtime-mix} and
-web mixes \cite{web-mix}. Even when not under attack cascades will
-provide smaller anonymity sets than networks since the least
-resourceful acts as a traffic bottleneck.
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\section{The Mix-net Design}
+\label{sec:design}
+
+Mixminion's principal difference from earlier mix-net designs is the
+mechanism it uses to support reply messages with the same processing
+machinery as non-reply messages, while at the same time resisting the
+attacks described below in REF.
+
+\subsection{Design goals and assumptions}
+% this needs more material, and a bit less 'attitude' :)
+
+% Server requirements
+First of all, the system must be relatively simple to deploy.  Past
+systems have never found it easy to get a reliable group of mix
+operators to run long-lived servers; Mixminion must add as few
+technical barriers as possible.  Thus our protocol
+requires only loose clock synchronization (within a few minutes);
+it must achieve acceptable performance on commodity hardware; and
+it requires little coordination between servers.
+
+% Client requriements
+Furthermore, software adoption has also been a barrier to past
+systems. (REF?) Thus, we only require users who receive anonymity
+from the system to run special software --- that is, users should
+be able to receive messages from anonymous senders and send messages
+to anonymous recipients with a standard email
+client.  Users must also be able to send and receive anonymous
+messages using only commodity hardware.  Finally, although users with
+persistent network connections are necessarily more resistant to
+intersection attacks than users with intermittent connections (see
+REF below), the system must still support users with intermittent
+connections and offer them as much anonymity as possible.
+
+We assume a well-funded adversary who can
+observe all traffic on the network, who can generate, modify,
+delete, or delay traffic on the network, who can operate mixes of its
+own, and who can compromise some fraction of the mixes on the network.
+We assume that such an adversary is attempting to compromise users'
+anonymity by learning (or guessing with a reasonable probability) who
+is communicating with whom. In particular the adversary wants to use
+all information contained in the network traffic patterns to trace
+communication back or forth and gain additional knowledge about
+communicating partners.
+%What else is the adversary trying to do?
+
+The mixminion network tries to make is as hard as possible for an
+adversary observing the network to gain any additional information
+about communicating partners beyond an \emph{a-priory} belief. It does
+this by providing very little information to outside observers, and
+intermediate nodes, to avoid intersection attacks. In particular even
+intermediary nodes are not aware of the actual route length, that can
+be as long as 32 hops, or their position in the network. Furthermore
+the processing for replies is exactly the same as for normal messages
+and it is therefore difficult to partition the anonymity sets by
+distinguishing between them. 
+
+% replies: we want to avoid partitioning by having reply messages be
+%   indistinguishable from forward messages, and just as secure.  To the
+%   extent possible, a mix should not be able to learn any more from a
+%   message's contents than from the fact of the message's receipt.
 
-\subsection{Deployed Remailer Systems}
 
-The first widespread public implementations of mixes were produced by the
-Cypherpunks mailing list. These ``Type I'' \emph{anonymous remailers}
-were inspired both by the problems surrounding the {\tt anon.penet.fi}
-service \cite{helsingius}, and by theoretical work on mixes. Hughes wrote
-the first Cypherpunk anonymous remailer \cite{remailer-history}; Finney
-followed closely with a collection of scripts that used Phil Zimmermann's
-PGP to encrypt and decrypt remailed messages. Later, Cottrell implemented
-the Mixmaster system \cite{mixmaster}\cite{mixmaster-spec}, or ``Type II'' remailers,
-which added message padding, message pools, and other mix features lacking
-in the Cypherpunk remailers. Note that Mixmaster does not include replies,
-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}, 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.
 
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
-\section{The Mix-net Design}
-\label{sec:design}
 
 Mixminion brings together the current best practical approaches for providing
 anonymity in a batching message-based mix environment. We don't aim
@@ -428,16 +412,6 @@
 restrict the set of options for users: we provide only one
 cipher suite, and we avoid extensions that would help an adversary
 divide the anonymity set.
-
-Mixminion uses the same general mix-net paradigm as previous work
-\cite{chaum-mix}\cite{mixmaster-attacks}\cite{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. 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
-Section \ref{subsec:delivery-modules}.
 
 % A bit more detail about what is contained in the header: -George