[freehaven-cvs] Gah, linewrap fixes!

[rabbi@seul.org]

Update of /home2/freehaven/cvsroot/doc/mixmaster-vs-reliable
In directory moria.mit.edu:/tmp/cvs-serv31667

Modified Files:
	mixvreliable.tex 
Log Message:
Gah, linewrap fixes!


Index: mixvreliable.tex
===================================================================
RCS file: /home2/freehaven/cvsroot/doc/mixmaster-vs-reliable/mixvreliable.tex,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -d -r1.2 -r1.3
--- mixvreliable.tex	5 Feb 2004 18:44:46 -0000	1.2
+++ mixvreliable.tex	5 Feb 2004 18:49:30 -0000	1.3
@@ -28,24 +28,29 @@
 \section{Introduction}
 
 
-The Internet was initially perceived as a rather anonymous
-environment. Nowadays, we know that it can be a powerful surveillance tool:
-anyone willing to listen to the communication links can spy
-on Internet users, and search engines and data mining techniques are becoming
-increasingly powerful.  
-Privacy does not only mean confidentiality of the information;
-it also means not revealing information about who is communicating
-with whom. Anonymous remailers (also called \emph{mixes}) allow their users to
-send emails without disclosing the identity of the recipient to a
-third party. They also allow the sender of a message to stay anonymous 
-to the recipient. 
+The Internet was initially perceived as a rather anonymous environment.
+Nowadays, we know that it can be a powerful surveillance tool: anyone
+willing to listen to the communication links can spy on Internet users,
+and search engines and data mining techniques are becoming increasingly
+powerful.
+
+Privacy does not only mean confidentiality of the information; it also
+means not revealing information about who is communicating with whom.
+Anonymous remailers (also called \emph{mixes}) allow their users to send
+emails without disclosing the identity of the recipient to a third party.
+They also allow the sender of a message to stay anonymous to the
+recipient.
 
 The objective of this work was to have quantitative results on the
 anonymity actually provided by two mix software implementations in wide
- deployment, in order to test the actual anonymity provided to the users of the 
-remailer sevice, and to compare the two different designs. We evaluate anonymity in a single-node context; in order to assess the anonymity provided by the entire remailer network, additional considerations are necessary. As individual nodes are the basic component to the network of mixes, we aim to provide information to be considered when choosing this component.  We have used as 
-input real-life data gathered from a popular remailer, and simulated the 
-behaviour of the mix.
+deployment, in order to test the actual anonymity provided to the users of
+the remailer sevice, and to compare the two different designs. We evaluate
+anonymity in a single-node context; in order to assess the anonymity
+provided by the entire remailer network, additional considerations are
+necessary. As individual nodes are the basic component to the network of
+mixes, we aim to provide information to be considered when choosing this
+component.  We have used as input real-life data gathered from a popular
+remailer, and simulated the behaviour of the mix.
 
 % Summary of what we have done
 
@@ -55,43 +60,48 @@
 \label{mixes}
 
 Mixes are the essential building block to provide anonymous email
-services. A mix is a router that hides the correspondence between
-incoming and outgoing messages. The mix changes the appearance and the
-flow of the messages. In order to change the appearance of the
-messages, the mix uses some techniques, such as padding and
-encryption, thus providing bitwise unlinkability between inputs and
-outputs. Techniques like reordering and delaying messages, and
-generating dummy traffic are used to modify the flow of messages. This
-modification of the traffic flow is needed to prevent timing
-attacks that could disclose the relationship between an input and an
-output messages by looking at the time the message arrived to and left
-from the mix.
+services. A mix is a router that hides the correspondence between incoming
+and outgoing messages. The mix changes the appearance and the flow of the
+messages. In order to change the appearance of the messages, the mix uses
+some techniques, such as padding and encryption, thus providing bitwise
+unlinkability between inputs and outputs. Techniques like reordering and
+delaying messages, and generating dummy traffic are used to modify the
+flow of messages. This modification of the traffic flow is needed to
+prevent timing attacks that could disclose the relationship between an
+input and an output messages by looking at the time the message arrived to
+and left from the mix.
 
 The idea of mixes was introduced by Chaum \cite{chaum81untraceable}.  
-This first design was a \emph{threshold mix}, a mix that
-collects a certain number of messages and then flushes them. Since
-then, variants on this first design have been proposed in the
-literature. In this paper, we focus on two practical mix designs,
-which have been implemented and are part of the Mixmaster remailer
-network [ref. to Mixmaster], that has been providing anonymous email
-services since xxx. 
-
-The first design is called ``Mixmaster'' (as the remailer network)
-because it corresponds to the original design by Cottrell
-\cite{Cott94,Mix_prot}. The second desing, called ``Reliable'', uses a
-different reordering strategy.~\cite {RProcess} The details of the two remailers are
-explained in the following sections. We compare version 3.0 of the Mixmaster software and verrsion foo of Reliable.
+This first design was a \emph{threshold mix}, a mix that collects a
+certain number of messages and then flushes them. Since then, variants on
+this first design have been proposed in the literature. In this paper, we
+focus on two practical mix designs, which have been implemented and are
+part of the Mixmaster remailer network [ref. to Mixmaster], that has been
+providing anonymous email services since xxx.
 
-% Crazy thought -- might we want to throw Mixminion into this, too? I'll ask Nick if he thinks it is too early. 
-% It should be easy to adopt the Mixmaster simulations to Mixminon.
+The first design is called ``Mixmaster'' (as the remailer network) because
+it corresponds to the original design by Cottrell \cite{Cott94,Mix_prot}.
+The second desing, called ``Reliable'', uses a different reordering
+strategy.~\cite {RProcess} The details of the two remailers are explained
+in the following sections. We compare version 3.0 of the Mixmaster
+software and verrsion foo of Reliable.
 
 \subsection{Mixmaster}
 
-\footnote{Mixmaster version 3.0, as well as Reliable, also optionally support the older ''Cypherpunk'' remailer message format. For the purposes of this paper, we are assuming that the remailers are being operated without this support. As anonymity sets for the two protocols generally do not overlap, this does not impact our results. The Cypherpunk remailer protocol is known to contain numerous flaws, and should not be used if strong anonymity is required\cite{cottrell,mixminion}.}
+\footnote{Mixmaster version 3.0, as well as Reliable, also optionally
+support the older ''Cypherpunk'' remailer message format. For the purposes
+of this paper, we are assuming that the remailers are being operated
+without this support. As anonymity sets for the two protocols generally do
+not overlap, this does not impact our results. The Cypherpunk remailer
+protocol is known to contain numerous flaws, and should not be used if
+strong anonymity is required\cite{cottrell,mixminion}.}
 
 \subsection{Reliable}
-Reliable inter-operates with Mixmaster on the protocol level by using the Mixmaster 
-message format for packet transfer. Reliable uses a variant of the \emph{S-G Mix} design proposed by Kesdogan. % Explain details of Reliable's s-g.
+
+Reliable inter-operates with Mixmaster on the protocol level by using the
+Mixmaster message format for packet transfer. Reliable uses a variant of
+the \emph{S-G Mix} design proposed by Kesdogan. % Explain details of
+Reliable's s-g.
 
 \section{Dummy traffic}
 \label{dummy}
@@ -113,61 +123,74 @@
   set of subjects, the anonymity set''}.
 
 The use of the information theoretical concept of entropy as a metric for
-anonymity was simultaneously proposed by Serjantov and Danezis in 
+anonymity was simultaneously proposed by Serjantov and Danezis in
 \cite{Serj02} and by D\'{\i}az \emph{et al.} in \cite{Diaz02}. The
 difference between the two models for measuring anonymity is that in
 \cite{Diaz02} the entropy is normalized with respect to the number of
 users. In this paper we will use the non-normalized flavour of the metric.
 
-The anonymity provided by a mix can be computed for the incoming 
-or for the outgoing messages. We call this \emph{sender anonymity}
-and \emph{recipient anonymity}. 
+The anonymity provided by a mix can be computed for the incoming or for
+the outgoing messages. We call this \emph{sender anonymity} and
+\emph{recipient anonymity}.
 
-\paragraph{Sender anonymity.}
+\paragraph{Sender anonymity.} 
 In order to compute the sender anonymity, we want to know the effective
-size of the anonymity set of senders for a message output by the mix. 
+size of the anonymity set of senders for a message output by the mix.  
 Therefore, we compute the entropy of the probability distribution that
 relates an outgoing message of the mix (the one for which we want to know
-the anonymity set size) with all the possible inputs. 
+the anonymity set size) with all the possible inputs.
 
 \paragraph{Recipient anonymity.}
-If we want to compute the effective
-recipient anonymity set size of an incoming message that goes through
-the mix, we have to compute the entropy of the probability
-distribution that relates the chosen input with all possible outputs.
+If we want to compute the effective recipient anonymity set size of an
+incoming message that goes through the mix, we have to compute the entropy
+of the probability distribution that relates the chosen input with all
+possible outputs. 
 \\
 
 Note that in the two cases, the metric computes the anonymity of a
 \emph{particular} input or output message; it does not give a general
 value for a mix design and it is dependent on the traffic pattern. The
-advantage of this property is that mixes may offer information about
-the \emph{current} anonymity they are providing. The disadvantage is
-that it becomes very difficult to compare theoretically different mix
-designs. Nevertheless, it is possible to measure on real systems (or
-simulate) the anonymity obtained for a large number of messages and
-provide comparative statistics.
+advantage of this property is that mixes may offer information about the
+\emph{current} anonymity they are providing. The disadvantage is that it
+becomes very difficult to compare theoretically different mix designs.
+Nevertheless, it is possible to measure on real systems (or simulate) the
+anonymity obtained for a large number of messages and provide comparative
+statistics.
 
 
 \subsection{Attack model}
 
 
 The anonymity metric computes the uncertainty about the sender or the
-recipient of a message, given that some information is
-available. We compute the metric from the point of view of an
-attacker, whose powers must be clearly specified.
+recipient of a message, given that some information is available. We
+compute the metric from the point of view of an attacker, whose powers
+must be clearly specified.
 
 
 \section{Simulators}
 
-% Describe exactly what it was that we logged on randseed here, and for how long?
+% Describe exactly what it was that we logged on randseed here, and for
+how long?
 
 \section{Results of the simulations}
 
 \section{Other factors which influence anonymity}
 
-We have evaluated the anonymity strength provided by the mixing algorithms and dummy policies chosen for both Mixmaster and Reliable. Additional factors have a direct impact on the anonymity provided by the system. Concerns such as the security of the underlying operating system, host server integrity, proper implementation of the cryptographic functions provided by the remailer software, and likelihood of administration mistakes all contribute to the overall anonymity these software packages can provide. We assume that no active attacks against the software occurred during the development or compilation process, though additional concerns are present in that area~\cite{trusting-trust}.
+We have evaluated the anonymity strength provided by the mixing algorithms
+and dummy policies chosen for both Mixmaster and Reliable. Additional
+factors have a direct impact on the anonymity provided by the system.
+Concerns such as the security of the underlying operating system, host
+server integrity, proper implementation of the cryptographic functions
+provided by the remailer software, and likelihood of administration
+mistakes all contribute to the overall anonymity these software packages
+can provide. We assume that no active attacks against the software
+occurred during the development or compilation process, though additional
+concerns are present in that area~\cite{trusting-trust}.
 
-This paper does not aim to be an in-depth analysis of the full spectrum of host-attacks against remailer nodes; nevertheless, it is important to mention some significant differences between Reliable and Mixmaster which may affect their ability to provide adequate anonymity for their users.
+This paper does not aim to be an in-depth analysis of the full spectrum of
+host-attacks against remailer nodes; nevertheless, it is important to
+mention some significant differences between Reliable and Mixmaster which
+may affect their ability to provide adequate anonymity for their users.
 
 \subsection{Host server integrity}
 Shared access by untrusted users
@@ -176,50 +199,144 @@
 Disk attacks
 Dynamically loaded library shims
 
-Reliable is limited to operation on the Windows platform. Mixmaster is portable, and has been known to run on a wide variety of operating systems.\footnote{There have been instances of remailers based on the Mixmaster 3.0 codebase operating on SunOS, Solaris, SunOS, AIX, Irix, BeOS, MacOS X, Windows NT (natively and through the use of Cygwin), Windows 2000 (natively and through the use of Cygwin), Windows XP (through the use of Cygwin), FreeBSD, NetBSD, OpenBSD, and multiple versions of Linux.}
+Reliable is limited to operation on the Windows platform. Mixmaster is
+portable, and has been known to run on a wide variety of operating
+systems.\footnote{There have been instances of remailers based on the
+Mixmaster 3.0 codebase operating on SunOS, Solaris, SunOS, AIX, Irix,
+BeOS, MacOS X, Windows NT (natively and through the use of Cygwin),
+Windows 2000 (natively and through the use of Cygwin), Windows XP (through
+the use of Cygwin), FreeBSD, NetBSD, OpenBSD, and multiple versions of
+Linux.}
 
-Host server security is ultimately the responsibility of the remailer operator.
+Host server security is ultimately the responsibility of the remailer
+operator.
 
 \subsection {UI Issues}
 
-% Good UI is important, though server operation requires skill in general. Hobbyists will find Reliable 
-% easier to use, Mixmaster needs UI improvements, or maybe this doesn't matter because hobbyists that 
-% can't figure out Mixmaster probably can't satisfy the requirements in the above section.
+% Good UI is important, though server operation requires skill in general.
+% Hobbyists will find Reliable easier to use, Mixmaster needs UI
+% improvements, or maybe this doesn't matter because hobbyists that can't
+% figure out Mixmaster probably can't satisfy the requirements in the above
+% section.
 
-In privacy application client, an intuitive user interface is essential in order to ensure that the software is used consistently and correctly~\cite{sassaman-lisa}. A greater level of skill can safely be assumed when designing privacy software which is intended to be operated as a service, however. Most anonymity systems, including mix-net implementations, do imply a significant degree of complexity. Due to the fact that the operation of a public Internet service involves the correct configuration and maintenance of the host server, this necessary complexity is acceptable as long as the operator's skill level is sufficient. The level of skill required to properly install, configure, and operate a mix-net node should not exceed that required to properly install, configure, and operate the server itself.
+In privacy application client, an intuitive user interface is essential in
+order to ensure that the software is used consistently and
+correctly~\cite{sassaman-lisa}. A greater level of skill can safely be
+assumed when designing privacy software which is intended to be operated
+as a service, however. Most anonymity systems, including mix-net
+implementations, do imply a significant degree of complexity. Due to the
+fact that the operation of a public Internet service involves the correct
+configuration and maintenance of the host server, this necessary
+complexity is acceptable as long as the operator's skill level is
+sufficient. The level of skill required to properly install, configure,
+and operate a mix-net node should not exceed that required to properly
+install, configure, and operate the server itself.
 
-The software packages we evaluated differed with regard to their interface complexity in a number of areas.
+The software packages we evaluated differed with regard to their interface
+complexity in a number of areas.
 
 % Installation, configuration, operation, key rotation, MTA issues.
 
 \subsection{Programming language}
 
-While the most critical factor in the creation of secure code is the manner in which it is written, some languages lend themselves to greater risk of exploitable mistakes. An inexperienced or unskilled programmer will always be able to make an application insecure. The choice of programming language merely sets the bar for the required level of experience and ability necessary to develop applications in that language safely. Thus, when evaluating the likelihood of the existence of exploitable code in an application, it is worthwhile to consider the programming language used to create that application. Since neither Mixmaster nor Reliable were written by seasoned software developers, we assume a level of experience which would allow for simplistic security mistakes.\footnote{The bulk of the code for Mixmaster 3.0 was written by Ulf M\"oller as his first major software development project while completing his undergraduate computer science degree~\cite{personal-corresp-ulf}. He has since gained respect as a skilled cryptographic software developer for his open source and proprietary development projects. Reliable was authored under a pseudonym, and we can only speculate about the level of experience of its author. (There has been no known communication with the author of Reliable since February, 2000).}
+While the most critical factor in the creation of secure code is the
+manner in which it is written, some languages lend themselves to greater
+risk of exploitable mistakes. An inexperienced or unskilled programmer
+will always be able to make an application insecure. The choice of
+programming language merely sets the bar for the required level of
+experience and ability necessary to develop applications in that language
+safely. Thus, when evaluating the likelihood of the existence of
+exploitable code in an application, it is worthwhile to consider the
+programming language used to create that application. Since neither
+Mixmaster nor Reliable were written by seasoned software developers, we
+assume a level of experience which would allow for simplistic security
+mistakes.\footnote{The bulk of the code for Mixmaster 3.0 was written by
+Ulf M\"oller as his first major software development project while
+completing his undergraduate computer science
+degree~\cite{personal-corresp-ulf}. He has since gained respect as a
+skilled cryptographic software developer for his open source and
+proprietary development projects. Reliable was authored under a pseudonym,
+and we can only speculate about the level of experience of its author.
+(There has been no known communication with the author of Reliable since
+February, 2000).}
 
 %C vs. VB.
 
 
-%Possibly do binary analysis or get Matt to run them through Purify? Hmm. Maybe I should ask Matt to co-author.
+% Possibly do binary analysis or get Matt to run them through Purify? Hmm.
+% Maybe I should ask Matt to co-author.
 
 \subsection{Included libraries}
-In addition to the standard POSIX libraries foo, foo, and foo provided by the compilation OS, Mixmaster 3.0, the version of Mixmaster evaluated in this paper, requires that the zlib~\cite{zlib rfc} and OpenSSL~\cite{OpenSSL} libraries be included. Optionally, Mixmaster also links against pcre~\cite{pcre} an ncurses~\cite{ncurses}.
+In addition to the standard POSIX libraries foo, foo, and foo provided by
+the compilation OS, Mixmaster 3.0, the version of Mixmaster evaluated in
+this paper, requires that the zlib~\cite{zlib rfc} and
+OpenSSL~\cite{OpenSSL} libraries be included. Optionally, Mixmaster also
+links against pcre~\cite{pcre} an ncurses~\cite{ncurses}.
 
-Reliable requires Windows calls foo, foo, and foo, as well as Mixmaster 2.0.4, and... 
+Reliable requires Windows calls foo, foo, and foo, as well as Mixmaster
+2.0.4, and...
 
 \subsection{Cryptographic functions}
-Both Mixmaster and Reliable avoid direct implementation of cryptographic algorithms when possible. Mixmaster 3.0 relies strictly on OpenSSL for these cryptographic functions. Any attackable flaws in the cryptographic library used to build Mixmaster which affect the security if the algorithms\footnote{It is understood that flaws in the cryptographic algorithms will affect the security of software which relies upon those algorithms. However, since most attacks on cryptographic applications are due to flaws in the implementation, care must be taken when evaluating the shared cryptographic libraries.} used by Mixmaster may be a an attack against Mixmaster as well.
 
-Reliable abstracts the cryptographic operations one step further. To support the Mixmaster message format, Reliable acts as a wrapper around the DOS version of Mixmaster 2.0.4. Thus, any attack against the Mixmaster message format due to implementation flaws in Mixmaster 2.0 will work against Reliable as well. Mixmaster 2.0.4 relies on the cryptographic library OpenSSL or its predecessor SSLeay for the MD5, EDE-3DES, and RSA routines.\footnote {Prior to the expiration of the RSA patent, versions of Mixmaster 2.0 offered support for the RSAREF and BSAFE libraries as well. Use of these versions of Mixmaster is largely abandoned.} 
+Both Mixmaster and Reliable avoid direct implementation of cryptographic
+algorithms when possible. Mixmaster 3.0 relies strictly on OpenSSL for
+these cryptographic functions. Any attackable flaws in the cryptographic
+library used to build Mixmaster which affect the security if the
+algorithms\footnote{It is understood that flaws in the cryptographic
+algorithms will affect the security of software which relies upon those
+algorithms. However, since most attacks on cryptographic applications are
+due to flaws in the implementation, care must be taken when evaluating the
+shared cryptographic libraries.} used by Mixmaster may be a an attack
+against Mixmaster as well.
+
+Reliable abstracts the cryptographic operations one step further. To
+support the Mixmaster message format, Reliable acts as a wrapper around
+the DOS version of Mixmaster 2.0.4. Thus, any attack against the Mixmaster
+message format due to implementation flaws in Mixmaster 2.0 will work
+against Reliable as well. Mixmaster 2.0.4 relies on the cryptographic
+library OpenSSL or its predecessor SSLeay for the MD5, EDE-3DES, and RSA
+routines.\footnote {Prior to the expiration of the RSA patent, versions of
+Mixmaster 2.0 offered support for the RSAREF and BSAFE libraries as well.
+Use of these versions of Mixmaster is largely abandoned.}
 
 \subsection{Entropy sources}
-The quality of the entropy source plays an extremely important role in both the pool mix and S-G mix schemes. In pool mix systems, the mixing in the pool must be cryptographically random in order to mix the traffic in a non-deterministic way. The timestamps used to determine how long a message should be held by an S-G mix implementation must also be from a strong entropy source for the same reasons. In addition, the Mixmaster message format specifies the use of random data for its message and header padding.
 
-All software is dependent on its underlying operating system for a good source of entropy. Cryptographic quality entropy is a scarce resource on most systems\footnote{noise cards change this}, and therefore the entropy sources provided by most modern operating systems actually provide PRNG output which has been seeded with truly-random data.%\footnote{explaination of /dev/random , /dev/urandom , and Windows entropy.}
+The quality of the entropy source plays an extremely important role in
+both the pool mix and S-G mix schemes. In pool mix systems, the mixing in
+the pool must be cryptographically random in order to mix the traffic in a
+non-deterministic way. The timestamps used to determine how long a message
+should be held by an S-G mix implementation must also be from a strong
+entropy source for the same reasons. In addition, the Mixmaster message
+format specifies the use of random data for its message and header
+padding.
 
-Mixmaster uses OpenSSL's rand\_foo function\footnote{which draws from /dev/urandom on Unix, foo on WIndows}. With the exception of the message and header padding (which is done by the supporting Mixmaster 2.0.4 binary), Reliable uses the standard Windows system call, Rand(). The Rand() function is not a cryptographically strong source of entropy. This function uses the system time as its primary entropy seed, and previous work has demonstrated that systems which use a known seed to a deterministic PRNG are trivially attackable~\cite{daw-ian-netscape,MS-knowledgebase}.
+All software is dependent on its underlying operating system for a good
+source of entropy. Cryptographic quality entropy is a scarce resource on
+most systems\footnote{noise cards change this}, and therefore the entropy
+sources provided by most modern operating systems actually provide PRNG
+output which has been seeded with truly-random
+data.
+% \footnote{explaination of /dev/random , /dev/urandom , and Windows
+% entropy.}
+
+Mixmaster uses OpenSSL's rand\_foo function\footnote{which draws from
+/dev/urandom on Unix, foo on WIndows}. With the exception of the message
+and header padding (which is done by the supporting Mixmaster 2.0.4
+binary), Reliable uses the standard Windows system call, Rand(). The
+Rand() function is not a cryptographically strong source of entropy. This
+function uses the system time as its primary entropy seed, and previous
+work has demonstrated that systems which use a known seed to a
+deterministic PRNG are trivially
+attackable~\cite{daw-ian-netscape,MS-knowledgebase}.
 
 \subsection{Network timing attacks}
-Packet counting, deduction of pool variables by timing observation. Affects pool-mixes more than s-g mixes, possibly aids attacker in some non-host based active attacks such as $(n-1)$ attacks. The anonymity strength of a remailer should not require pool values to be hidden, and countermeasures to this class of active attacks should be taken.~\footnote{rgb-mix}
+
+Packet counting, deduction of pool variables by timing observation.
+Affects pool-mixes more than s-g mixes, possibly aids attacker in some
+non-host based active attacks such as $(n-1)$ attacks. The anonymity
+strength of a remailer should not require pool values to be hidden, and
+countermeasures to this class of active attacks should be
+taken.~\footnote{rgb-mix}
 
 \section{Conclusions and future work}
 \label{conclusions}
@@ -234,8 +351,9 @@
 Government. 
 
 The authors also want to thank Jasper Scholten for looking at the
-feasibility of some simulation algorithms, Peter Palfrader for assisting with
-the gathering of input data for our simulations, and members of The Shmoo Group for discussion of secure programming issues.
+feasibility of some simulation algorithms, Peter Palfrader for assisting
+with the gathering of input data for our simulations, and members of The
+Shmoo Group for discussion of secure programming issues.
 
 
 

***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs       in the body. http://freehaven.net/