[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[minion-cvs] design/assumptions section ready
Update of /home/minion/cvsroot/doc
In directory moria.seul.org:/home/arma/work/minion/doc
Modified Files:
minion-design.tex minion-design.bib
Log Message:
design/assumptions section ready
Index: minion-design.tex
===================================================================
RCS file: /home/minion/cvsroot/doc/minion-design.tex,v
retrieving revision 1.73
retrieving revision 1.74
diff -u -d -r1.73 -r1.74
--- minion-design.tex 5 Nov 2002 13:58:24 -0000 1.73
+++ minion-design.tex 5 Nov 2002 19:03:54 -0000 1.74
@@ -212,11 +212,9 @@
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 schemes based on more sophisticated cryptographic
-constructs that aim at providing robustness.
-%distributed flash mixes \cite{flash-mix} and their weaknesses
-%\cite{desmedt}\cite{mitkuro}, and hybrid mixes \cite{hybrid-mix}.
+%Recent research on mix networks (mix-nets) includes stop-and-go mix-nets
+%\cite{kesdogan}, and schemes based on more sophisticated cryptographic
+%constructs that provide robustness \cite{flash-mix}.
A mix network where Alice chooses her route freely from all mixes is
called a \emph{free-route} network. Another approach is a \emph{cascade}
@@ -232,26 +230,36 @@
need to go through each mix. Mix cascade research includes real-time
mixes \cite{realtime-mix} and web mixes \cite{web-mix}.
-There are also more complex designs, that use cryprographic operations
-and zero knowledge proofs, in order to provide proofs of the correct
-functionig of the mix network and to detect and exclude misbehaving
-participants.
+More complex designs use zero-knowledge proofs and stronger assumptions
+to guarantee delivery or to detect and exclude misbehaving participants.
These include flash mixes \cite{flash-mix} and attacks against them
-\cite{mitomo00attack}, hybrid mixes
-\cite{hybrid-mix}\cite{jakobsson-optimally} and provable shuffles
-\cite{PShuffle}\cite{502000}. Altought the properties of these designs
-are appealing they are often not practical since they assume a lot of
-coordination and synchronization between the mixes, and they impose a
-heavy computational and communication overhead.
+\cite{mitkuro}, hybrid mixes \cite{hybrid-mix}\cite{jakobsson-optimally},
+and provable shuffles \cite{PShuffle}\cite{shuffle}. The properties
+of these designs are appealing, but they are often not practical since
+they assume a lot of coordination and synchronization between the mixes,
+and they impose a heavy computational and communication overhead.
-% What's a reply block?
-When recipients want to achieve anonymity, some mix-net designs allow
-them to construct \emph{reply blocks} that allow others to send
-messages to them without knowing their identities. Such a design was
-first introduced by Chaum \cite{chaum-mix} and later extended in \cite{babel}.
-A reply block contains only the routing portion of a message; the
-actual contents are appended to by the user that eventually sends a
-message to the recipient.
+Some mix-net designs allow recipients to construct \emph{reply blocks}
+that allow others to send messages to them without knowing their
+identities. A reply block contains only the routing portion of a message;
+the actual contents are appended by the user who eventually sends a
+message to the recipient. Such a design was first introduced by Chaum
+\cite{chaum-mix} and later extended in Babel \cite{babel}. However,
+Babel's replies are indistinguishable from forward messages only by
+passive observers --- the mix nodes can still distinguish. Babel's reply
+addresses are also multiple-use, making them less secure than forward
+messages due to replay vulnerabilities.
+
+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.
\subsection{Known attacks against mix-nets}
@@ -290,7 +298,7 @@
some characteristics that can be persistantly observed throughout
their journey in the network, they can be separated from rest of the
traffic and therefore confused with fewer messages. In order to
-minimize the side channels provided mixminion hides from all
+minimize the side channels provided Mixminion hides from all
intermediaries information such as their position on the path or the
length of the path (althouth there is a miximium of 32
hops). Additionally the forward and reply paths are indistingushable
@@ -327,86 +335,69 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%\section{Related Work}
-%\label{sec:related}
-
-%\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.
-
-%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}
+\section{Design goals and assumptions}
-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.
+Mixminion brings together the current best practical approaches
+for providing anonymity in a batching message-based free-route mix
+environment. We don't aim to provide low-latency connection-oriented
+services like Freedom \cite{freedom} or Onion Routing \cite{goldschlag99}
+--- while those designs are more convenient for common activities like
+anonymous web browsing, the low latency necessarily implies smaller
+anonymity sets than for slower message-based services. Indeed, we
+intentionally 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. These assumptions lead to the following design goals.
-\subsection{Design goals and assumptions}
-% this needs more material, and a bit less 'attitude' :)
+%While Mixminion protects against known \emph{traffic analysis} attacks
+%(where an adversary attempts to learn a given message's sender or receiver
+%\cite{rackoff93cryptographic}\cite{raymond00}), we do not fully address
+%\emph{traffic confirmation} attacks such as intersection 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 and receivers who are active
+%at certain times and learn who is sending and receiving which messages
+%\cite{langos02}.
% 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.
+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 uses only loose clock synchronization (within
+a few minutes), achieves acceptable performance on commodity hardware,
+requires little coordination between servers, and can automatically
+handle servers joining and leaving the system.
% 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.
+systems. Thus, only users who receive anonymity from the system must 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 can also 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, the system must offer
+the latter users 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?
+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. Our adversary tries to discover
+linkability between sender and receiver, to identify the sender or
+receiver of a given message, or to trace a sender forward (or a receiver
+backward) to any messages.
+%by learning
+%(or guessing with a reasonable probability) who is communicating with
+%whom. In particular the adversary uses the network traffic patterns to
+%trace communication backward or forward and gain additional knowledge
+%about communicating partners.
-The mixminion network tries to make is as hard as possible for an
+The Mixminion network tries to make it 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
+about communicating partners beyond an \emph{a priori} 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
+intermediary nodes are not aware of the actual route length (which 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.
@@ -418,21 +409,15 @@
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\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
-to provide low-latency connection-oriented services like Freedom
-\cite{freedom} or Onion Routing \cite{goldschlag99} --- while those
-designs are more effective for common activities like anonymous web
-browsing, the low latency necessarily implies smaller anonymity sets
-than for slower message-based services. Indeed, we intentionally
-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.
-
-% A bit more detail about what is contained in the header: -George
+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.
Headers addressed to each intermediate mix are encrypted using RSA.
%RSA-OAEP \cite{PKCS1} and are of 128 bytes each.
@@ -452,23 +437,6 @@
% material well enough to know that Alice encrypts each layer with the
% appropriate mix's public key. Is this assumption safe -Nick
-While Mixminion protects against known \emph{traffic analysis} attacks
-(where an adversary attempts to learn a given message's sender or
-receiver \cite{rackoff93cryptographic}\cite{raymond00}), we do not fully
-address \emph{traffic 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 and receivers who are active at certain
-times and learn who is sending and receiving which messages
-% Really? I thought that an intersection attack told you who was
-% talking with whom, not which messages were sent to whom. I.e., Eve
-% can learn that Alice is sending messages to Bob and Carol, but
-% can't be certain which messages were meant for whom. -Nick
-% But if we further intersect to learn that the messages on Tuesday
-% are for Bob and those on Wednesday are for Carol, ... -RRD
-\cite{langos02}. Good dummy traffic designs may eventually address such
-intersection attack, but for now it remains an open problem.
-
We choose to drop packet-level compatibility with Mixmaster and the
Cypherpunk remailer systems, in order to provide a simple extensible
design. We can retain minimal backwards compatibility by ``remixing''
@@ -502,18 +470,18 @@
\label{subsec:header-swap}
The rest of this section describes the mechanism for secure replies,
-its integration with the normal sender anonymous message delivery and
+its integration with the normal sender anonymous message delivery, and
how we defeat tagging-related attacks.
Mixminion allows Alice to send messages to Bob in one of three ways:
\begin{enumerate}
-\item \textbf{Forward} messages where only Alice remains anonymous
-($(A)^x \rightarrow B: M$.)
-\item \textbf{Direct Reply} messages where only Bob remains anonymous
-($A \rightarrow (B)^y: M$.)
+\item \textbf{Forward} messages where only Alice remains anonymous:
+$(A)^x \rightarrow B: M$
+\item \textbf{Direct Reply} messages where only Bob remains anonymous:
+$A \rightarrow (B)^y: M$
\item \textbf{Anonymized Reply} messages where Alice \emph{and} Bob
- remain anonymous ($(A)^x \rightarrow (B)^y: M$.)
+ remain anonymous: $(A)^x \rightarrow (B)^y: M$
\end{enumerate}
We denote as $(A)^x$ Alice communicating anonymously under the
@@ -705,7 +673,7 @@
% old split here.
-If the mixminion design did not require
+If the Mixminion design did not require
the crossover point, an adversary could mount a tagging
attack by modifying the payload of a forward message as
it leaves Alice, and recognizing it later when it reaches Bob.
@@ -785,7 +753,7 @@
that the second leg be at least a few hops long.
It is worth noting that while semantically secure encryption cannot be
-used directly to solve the probem of tagging attacks in mixminion, the
+used directly to solve the probem of tagging attacks in Mixminion, the
structure of the operations performed on the message as it travels
through the network is very similar to the Luby-Rackoff \cite{sprp}
structure. In particular the fact that the header depends on the body
@@ -932,7 +900,7 @@
still possible to delay messages, unless an additional
\emph{heartbeat} signal is included in the SSL tunnel. This forces a
determined adversary to run nodes or to corrupt nodes in
-order to break the anonymity of mixminion.
+order to break the anonymity of Mixminion.
The encrypted channel offers only limited protection against traffic
analysis. Encrypted links between honest nodes prevent an adversary
@@ -948,7 +916,7 @@
\label{subsec:delivery-modules}
[I think it is important to say what modules get us in comparison to
-normal client side mixminion (which servers can also use). In
+normal client side Mixminion (which servers can also use). In
particular, access to some shared key material and plug-in for
infrastructure critical services. -GD]
@@ -1511,7 +1479,7 @@
\item We need a more thorough investigation of multiple-message tagging
attacks, and an analysis of how to safely choose paths when
sending many messages. When a message to be sent is larger than the
-mixminion payload size there is a need for a strategy to fragment
+Mixminion payload size there is a need for a strategy to fragment
it and reconstruct it at the recipient's end. In case some of the
messages are lost retransmission strategies or forward error
correction codes can be used to recover the message.
@@ -1523,7 +1491,7 @@
network.
\item We need stronger intuition about how to use
dummy messages. Such messages can be inserted either at the link layer
-or the actual mixminion layer, and defend against different attacks. A
+or the actual Mixminion layer, and defend against different attacks. A
more rational approach needs to be developed on who and when to insert
such dummy messages.
%\item We intend to draw up a more complete specification, which can lead
@@ -1535,18 +1503,18 @@
\end{itemize}
As detailed in the introduction the principal aim has
-been to include in mixminion only techniques that are well
+been to include in Mixminion only techniques that are well
understood. Although some people have speculated about the positive
effects of the techniques described as open issues above we have not
yet seen a thorough enough analysis to be convinced. For this reason
-while mixminion is flexible enough to support them it does not use
+while Mixminion is flexible enough to support them it does not use
them until their effects on anonymity are better understood. As the
engineering effort to implement the specification into a robust system
proceeds, undoutedly the researchers associated or inspired by this
project will try to shine some light on the open questions above.
We invite interested developers to join the {\tt mixminion-dev}
-mailing list \cite{mixminion-dev} and examine the more detailed Mixminion
+mailing list and examine the more detailed Mixminion
specification \cite{mixminion-spec}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Index: minion-design.bib
===================================================================
RCS file: /home/minion/cvsroot/doc/minion-design.bib,v
retrieving revision 1.13
retrieving revision 1.14
diff -u -d -r1.13 -r1.14
--- minion-design.bib 5 Nov 2002 13:58:24 -0000 1.13
+++ minion-design.bib 5 Nov 2002 19:03:54 -0000 1.14
@@ -7,15 +7,9 @@
year = "1990",
url = "citeseer.nj.nec.com/pfitzmann90how.html" }
-@Misc{mixminion-dev,
- author = {Mixminion},
- title = {Mixminion: a Type {III} anonymous remailer},
- note = {\newline \url{http://mixminion.net/}},
-}
-
@Misc{mixminion-spec,
author = {Mixminion},
- title = {Type {III} ({M}ixminion) {MIX} Protocol Specifications},
+ title = {Type {III} ({M}ixminion) {M}IX Protocol Specifications},
note = {\newline \url{http://mixminion.net/minion-spec.tex}},
}
@@ -394,21 +388,7 @@
year = {2001},
isbn = {3-540-42456-3},
bibsource = {DBLP, http://dblp.uni-trier.de}
-
-
-@inproceedings{502000,
- author = {C. Andrew Neff},
- title = {A verifiable secret shuffle and its application to e-voting},
- booktitle = {Proceedings of the 8th ACM conference on Computer and Communications Security},
- year = {2001},
- isbn = {1-58113-385-5},
- pages = {116--125},
- location = {Philadelphia, PA, USA},
- doi = {http://doi.acm.org/10.1145/501983.502000},
- publisher = {ACM Press},
- }
-
-
+}
@misc{ jakobsson-optimally,
@@ -434,17 +414,6 @@
publisher = {ACM},
note = {\url{http://citeseer.nj.nec.com/jakobsson99flash.html}},
}
-
-
-
-@article{ mitomo00attack,
- author = "Masashi Mitomo and Kaoru Kurosawa",
- title = "Attack for Flash {MIX}",
- journal = "Lecture Notes in Computer Science",
- volume = "1976",
- pages = "192--??",
- year = "2000",
- url = "citeseer.nj.nec.com/mitomo00attack.html" }
@InProceedings{SK,
author = {Joe Kilian and Kazue Sako},