%% Accountability in MIX-nets from Free Haven %% Info Hiding Workshop 2000 %% Draft was due Dec 12 %% Camera-ready copy for pre-proceedings due Mar 22 \documentclass{llncs} \usepackage{epsfig} \textwidth16cm \textheight20.5cm \topmargin0mm \oddsidemargin2.5mm \evensidemargin2.5mm \begin{document} \title{A Reputation System to Increase MIX-net Reliability} \author{Roger Dingledine\inst{1} \and Michael J. Freedman\inst{2} \and David Hopwood\inst{3} \and David Molnar\inst{4}} \institute{Reputation Technologies, Inc. \email{$<$arma@reputation.com$>$} \and Massachusetts Institute of Technology \email{$<$mfreed@mit.edu$>$} \and Independent consultant \email{$<$david.hopwood@zetnet.co.uk$>$} \and Harvard University \email{$<$dmolnar@hcs.harvard.edu$>$}} \maketitle \pagestyle{plain} %\pagestyle{empty} \begin{abstract} We describe a design for a reputation system that increases the reliability and thus efficiency of remailer services. Our reputation system uses a MIX-net in which MIXes give receipts for intermediate messages. Together with a set of witnesses, these receipts allow senders to verify the correctness of each MIX and prove misbehavior to the witnesses. We suggest a simple model and metric for evaluating the reliability of a MIX-net, and show that our reputation system improves over randomly picking MIX paths while maintaining anonymity. \end{abstract} \section{Introduction} Anonymous remailers are the most common method of anonymous e-mail communication. Despite wide use of the current global remailer network, this network is generally considered unreliable. Messages are often dropped, and the newsgroup {\tt alt.privacy.anon-server} contains many examples of a message being sent two or three times in the hope that one instance will reach the destination. This unreliability directly affects the number of people using the remailer network and their traffic patterns, which in turn reduces the anonymity these networks provide. Several approaches to the problem of unreliability are possible. One approach is to write more reliable software \cite{RProcess}. Another approach is to build MIX protocols that give provable robustness guarantees \cite{desmedt,flash-mix,mitkuro}. Our approach is to build a reputation system to track MIX reliability, and to modify the MIX protocol to support this system. Because users choose paths based on the published scores for each MIX, this reputation system improves both reliability (fewer messages get routed through dead MIXes) and efficiency (the system dynamically rebalances the load based on available reliable resources). %Reputation systems for MIX-nets have been discussed at an informal level for %several years, but we are aware of very little work on their properties. Currently deployed remailer reputation systems (better known as \emph{remailer statistics}) collect data independently and are treated as trusted third parties by client software. Since shutting down a remailer statistics server means that its statistics are no longer available, reliable servers are good targets for adversaries. Furthermore, these statistics often measure secondary properties of the MIX-net servers, such as up-time, which do not necessarily translate to reliability, especially with regard to Byzantine failure. We present a MIX-net design that allows the sender of a message, along with a collection of weakly trusted third party \emph{witnesses}, to prove that a MIX failed to process a message correctly. We introduce a new set of agents called \emph{scorers}, who tally failure proofs and serve them to client software. Because each failure can be proven to any number of scorers, loss of any individual scorer will be less disruptive than loss of a statistics server in current reputation systems. We go on to describe a simple metric for evaluating the reliability of a MIX-net or remailer system, and then show that our reputation system improves over randomly picking MIX paths. Our metric is the expected probability of a message successfully being sent through the MIX-net. We specify a simple probability model for a MIX-net and then give an example of how to evaluate our metric on a MIX-net where no reputation system is specified. Then we do the same analysis with a reputation system in place and show that a message's chance of surviving improves. We stress that this work does \emph{not} provide a fully satisfactory solution to the problem of MIX reliability. In particular, our reliability model is too simple to take into account active adversaries. As such, it is not clear what effect our reputation system will have against an active adversary. Our main goal is to show a reasonable initial reputation system, to stimulate further research on reputation systems and on modelling the increased reliability they provide. We describe related MIX-nets and current statistics systems in Section \ref{sec:related}. In Section \ref{sec:mix-models} we present a model for describing reliability of a MIX-net. Section \ref{sec:mix-design} presents our MIX-net design, describes specifically how to send a message in this MIX-net, and then argues security of the overall network. In Section \ref{sec:reputation}, we describe the design and motivation for the reputation scoring system, and the implications of deploying this system. In Section \ref{sec:quantify} we introduce the notion of a \emph{reliability metric} and propose such a metric for MIX-nets. We apply this metric to measure reliability in a MIX-net with randomly chosen paths, and then show that a reputation system can improve reliability, in a drastically simplified model. Finally, we close in Section \ref{sec:conclusion} with a discussion of possible directions for future research. \section{Related Work} \label{sec:related} \subsection{MIX-nets} Chaum introduced the concept of a MIX-net for anonymous communications \cite{chaum-mix}. A MIX-net consists of a series of servers, called MIXes, each of which is associated with a public key. Each MIX receives encrypted messages. These messages are then decrypted, batched, their order permuted, and forwarded on after stripping the sender's name and identifying information. Chaum also proved security of MIXes against a \emph{passive adversary} who can eavesdrop on all communications between MIXes but is unable to observe the permutation inside each MIX. Another way of saying this is to note that the \emph{view} of a passive adversary gives negliglible advantage over guessing in linking messages with their senders and receivers. Work on MIX-nets is ongoing. Current research directions include ``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}. %The reliability and efficiency of MIXes have been relatively recent %concerns. We believe increasing reliability and efficiency would have %a direct positive impact on the anonymity provided by a MIX-net. In %order to properly conceal the identity of their users, MIXes %traditionally require large amounts of traffic. Unreliable MIX-nets %require users to re-send messages; MIX-nets which often choose slow MIXes %in MIX paths are inefficient. These problems will discourage most users. %Addressing reliability issues will draw more users, increase traffic in %the MIX-net, and achieve better anonymity overall. Previous work primarily investigates a notion of the \emph{robustness} of MIX-nets in the context of a distributed MIX system \cite{flash-mix}. A MIX is considered robust if it survives the failure of any $k$ of $n$ participating servers, for some threshold $k$. This robustness is all or nothing: either $k$ servers are good and the MIX works, or they are not good and the MIX likely will not work. % It's not real clear how the above definition of robustness intersects % with use of zero-knowledge proofs etc. below. At least, to me. -sb % The idea is that the ZKPs are used by each of the participating servers % to convince each other that ``everything is OK.'' -DM Robustness has been achieved primarily via the use of zero-knowledge proofs of correct computation; participants use such proofs to convince each other that they follow the protocol correctly without revealing secret information. Done na\"{\a i}vely, this incurs significant overhead. Jakobsson showed how to use precomputation to reduce the overhead of such a MIX network to about 160 modular multiplications per message per server \cite{flash-mix}, but the protocol was later found to be flawed \cite{mitkuro} by Mitsumo and Kurosawa. They proposed a fix for the protocol, but the efficacy of this fix remains to be evaluated. A different approach was taken by Desmedt and Kurosawa \cite{desmedt}, but their technique requires many participating servers. Other work, such as Abe's MIX \cite{abe}, provides \emph{universal verifiability} in which any observer can determine after the fact whether a MIX cheated or not, but the protocol is still computationally expensive. Our notion of reliability differs from robustness in that we do not try to ensure that messages are delivered even when some nodes fail. Instead, we focus on improving a sender's long-term odds of choosing a MIX path that avoids failing nodes, and we attempt to quantify this improvement. %Our hope is %that this approach will produce systems which are less susceptible to %catastrophic failure and potentially more efficient. We note that the two approaches can be composed: a distributed MIX with robustness guarantees can be considered as a single node with its own reputation in a larger MIX-net. \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 theoretical work on MIXes and by the problems surrounding the {\tt anon.penet.fi} service \cite{helsingius}. Hughes wrote the first cypherpunks anonymous remailer \cite{remailer-history}; Finney followed closely with a collection of scripts which used Phil Zimmerman's PGP to encrypt and decrypt remailed messages. While these ``Type I'' remailers did not include crucial MIX features, such as reordering or batching of messages, they provided a better approximation of MIXes than had been generally available. Later, Cottrell implemented the Mixmaster system \cite{mixmaster}, 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}, which also created a practical remailer design (although one that never saw widespread use). Producing properly formatted remailer messages by hand is a difficult and error-prone task. The program Private Idaho \cite{pidaho}, developed by McNamara, was one of the earliest and best known means of automatically formatting remailer messages. The program is no longer maintained, but many different splinter versions exist. Currently, Potato Software's Jack B. Nymble and Reliable remailer software offer a range of features, including the ability to configure user preferences for picking remailer nodes \cite{potato}. %% Not a mix-net: %Recently, Zero-Knowledge Systems began providing commercial anonymity %services including anonymous mail \cite{freedom2}. \subsection{Remailer Statistics} After the deployment of the original cypherpunk remailers, the next major step was Levien's development of remailer \emph{statistics pages}. Statistics consist of both remailer capabilities, such as what kinds of encryption the remailer supports, and remailer \emph{up-times}, observed by pinging the machines in question and by sending test messages through each machine or group of machines. Levien statistics are an example of what we will call a \emph{reputation system}. Section \ref{sec:reputation} will discuss this in more detail. Reputation systems offer a means of improving the reliability of MIX-nets by allowing users to avoid choosing unreliable MIXes. The Jack B Nymble 2 remailer client \cite{potato} allows users to import statistics files and can then pick remailers according to that data. Users can specify minimum reliability scores, decide that a remailer should always or never be used, and specify maximum latency. \subsection{Approaches to MIX-Net Reliability} There are at least three approaches to MIX-net reliability: \begin{enumerate} \item {\bf Reliability via Protocol} We can build protocols which give specific guarantees of robustness and reliability, and prove theorems about these protocols in suitably specified adversary models. %The benefit of this approach is that we can build the protocol in %order to prove things about it. In addition, the results we can prove These results may be quite strong, e.g. ``this distributed MIX delivers correctly if no more than half of its participating servers are corrupt.'' The drawback of this approach is that the resulting protocols may be complicated, and efficient protocols with provable properties even more so. Converging on the ``right'' protocol may be tricky; even a small misstep in a proof may invalidate all robustness results. \item {\bf Reliability via Reputations} Instead of engineering the MIX-net protocol directly to provide reliability, we can make use of reputations to track MIX performance. In this approach, we specify a set of behaviors which characterize a ``good'' or ``bad'' MIX, then rate MIXes in a system according to their behavior. Unlike the reliability via protocol approach, we are unlikely to prove theorems such as ``messages are always delivered if a majority of MIXes are good.'' Instead, the goal of a reputation system is to make delivery ``better'' without guaranteeing perfection. \item {\bf Reliability via Economics} We can create economic incentives for MIX nodes to stay reliable, or ensure that an adversary who wishes to compromise reliability must spend a large amount of resources. Currently, Zero-Knowledge Systems is exploring this approach by paying MIX nodes for consistent reliability and performance in the Freedom network \cite{freedom2}. %% Cite Back? -DM % Preliminary reports suggest that this has not significantly helped the % reliability of the Freedom network\cite{back}. Another variant on this approach is to introduce the use of payments for each message sent through a MIX. \end{enumerate} Reliability via protocol is the most well-studied approach, while reliability via reputations in the form of Levien statistics is the most widely used approach. Our work explores a combination of the first two approaches. We modify the MIX-net protocol to support easy tallying of MIX failures and then specify a reputation system that makes use of this support. \section{MIX Models} \label{sec:mix-models} In order to speak about MIX-nets, we first must set out a model of what MIX-nets are. We will actually specify two models. The ``general'' model will be with respect to an adversary which aims at breaking the anonymity of the MIX-net. Then we will introduce a model for an adversary that aims at breaking the reliability of the MIX-net. Unifying these two adversaries is a topic for future work. \subsection{General MIX Model} \label{sec:general-model} A MIX-net consists of participating servers called \emph{MIXes}. These MIXes are connected by communication channels. There also exist one or more \emph{senders}, who wish to use the MIX-net to anonymously send messages to one or more \emph{receivers}. To send a message, a sender picks an ordered collection of MIXes called a \emph{MIX path} to stand between it and the receiver. We will also refer to MIXes as ``MIX nodes'' or simply ``nodes.'' The MIX-net also has an \emph{adversary}, whose goal is to link messages passing through the MIX-net with their senders and receivers. We will be most concerned with passive adversaries and the view such adversaries have of the MIX-net. A \emph{passive adversary} is an adversary which may eavesdrop on all communication between MIXes, but it may not modify or inject messages. The \emph{view} of a passive adversary is the collection of all messages that the adversary may see; in other words, the complete transcript of all messages passed between MIXes. This is the model of adversary for which Chaum designed the initial MIX-net protocol. An \emph{active adversary}, in contrast, may send messages of its own, block messages, or intercept and change messages. \subsection{MIX Reliability Model} \label{sec:reliability-model} In section \ref{sec:quantify}, we specify a reliability metric for MIX-nets. First, we will specify a suitable model of a MIX-net, which will concern \emph{only} an adversary interested in minimizing the reliability of the MIX-net. %Further, we assume a constant upper %bound on the number of senders and receivers of the MIX-net at any %point in order to simplify computation. Let $\mbox{\it MIXes}$ be the set of $m$ participants making up the MIX-net. Let the set of senders be $S$, and the set of receivers be $R$. Let $\mbox{\it Paths} \subset \mbox{\it MIXes}^*$ be the set of valid \emph{MIX paths}, that is, the set of sequences of MIXes allowed as paths by the MIX-net protocol. Senders first choose a receiver and then choose an ordered sequence of MIXes. Both choices are random variables. For each sender $s \in S$, we define the random variables $R_s$ corresponding to $s$'s choice of receiver given its knowledge about the MIX-net, and $\mbox{\it Path}_{s,r}$ corresponding to $s$'s choice of MIX paths when sending to receiver $r$. The fundamental operation in our MIX-net model is \emph{sending a message}. To send a message, a sender $s \in S$ picks a recipient $r \in R$ according to the distribution $R_s$, and then picks a MIX path, $path \in Paths$. The sender then sends the message along $path$ to $r$. We say a message \emph{survives} the MIX-net if none of the MIXes in $path$ fail. We say that the message is \emph{dropped} by the MIX-net if any of the MIXes along the path fail. The goal of the sender %%our goal as protocol designers -- %% commented out per waldman -DM is to minimize the number of dropped messages. \section{A MIX-net With Witnessed Failures} \label{sec:mix-design} Verification of transactions in cryptographic protocols is commonly supported either by performing the transaction publicly, or by using digitally signed receipts. We use the latter notion to develop a design in which MIXes normally provide a receipt for each message that they receive. %The receipt represents an agreement to process the message. % Do we want to say anything about transaction publicly? i.e., ledger % idea and what that gets you? Or just stay away from this? -mjf % we're already over our space limit. i suggest we ignore it. -rd The na\"{\a i}ve use of receipts is not sufficient to be able to pinpoint failures. A MIX could refuse to provide a receipt for a message that it was supposed to send to the next MIX because it failed to send it; alternatively, it might have been following the protocol but unable to obtain a receipt from the next hop. We solve this problem as follows: each message has a {\em deadline} by which it must be sent to the next MIX. A MIX $N_i$ first tries to send a message directly to the next node, $N_{i+1}$. If $N_i$ has not received a valid receipt by a specified period before the deadline, it enlists several {\em witnesses}, who will each independently try to send the message and obtain a receipt. For each witness who succeeds in obtaining a valid receipt, the witness sends it back to $N_i$. Any witness that fails will be convinced that $N_{i+1}$ is unreliable, and provides MIX $N_i$ with a signed {\em statement} to that effect. \begin{figure}[htc] \begin{center} \leavevmode \epsfbox{msg-flow2.1} \caption{Message flow example} \end{center} \end{figure} Thus for each message a MIX sends, it will either have a receipt showing that it processed the message in the time allowed, or statements signed by any witnesses it chooses, asserting that the next MIX did not follow the protocol. We will describe a protocol which uses these receipts and statements to allow the sender of a failed message to demonstrate that a particular MIX on the path failed. The above argument does not explicitly take into account the possibility that several consecutive MIXes are controlled by an adversary; we cover that in Section \ref{subsec:proving}. Note that the witnesses need not be trusted to preserve anonymity, since the messages sent to them are no more than the view of a passive adversary with complete network access. Therefore, the security proofs that apply to traditional MIX-net protocols still hold: we retain unlinkability between sender and receiver due to the batching and reordering that each MIX performs internally. In general, a system to verify transactions should provide verification of both successful and failed transactions. However, due to the pseudonymous nature of a MIX-net, successful transactions can easily be spoofed (via pseudospoofing, as described in Section \ref{sec:rep-solutions}) and thus the ability to prove that a transaction succeeded would not provide an accurate evaluation of MIX reliability. \subsection{Cryptographic Algorithms} %% (semantically secure => non-malleable) under CCA2, so no need to say that. We require two public key schemes: a public-key encryption scheme, which should be semantically secure under adaptive chosen ciphertext attack (equivalent to IND-CCA2 in the definitions of \cite{pk-relations})\footnote{ As is common in MIX-net protocols, the encryption scheme should pad plaintexts to a constant length on decryption. The IND-CCA2 notion may need to be modified slightly to take this into account. %but how to do that is beyond the scope of this paper. }, and a public-key signature scheme, which should be existentially unforgeable under adaptive chosen message attack. The encryption scheme is modelled as a key pair generation algorithm $G_E$, a randomized encryption algorithm $E$, and a deterministic decryption algorithm $D$. In our notation, we will explicitly include the random value used in the encryption, so $E_i^r(M)$ means the encryption of message $M$ and random value $r$ under the public key of $N_i$. We assume the usual correctness property that if $N_i$'s key pair is valid (i.e. was generated by $G_E$), $D_i(E_i^r(M)) = M$ for any plaintext $M$ and random value $r$. The signature scheme is modelled as a key pair generation algorithm $G_S$, a signing algorithm $Sign$, and a verification algorithm $Ver$. %The signing algorithm may also be randomized, although %in this case we do not need to include the random value in the notation. $Sign_i(M)$ is the signature of $M$ under the private key of $N_i$, and $Ver_i(Sig, M) = 1$ if $Sig$ is a valid signature by $N_i$ on $M$, or $0$ otherwise. If $N_i$'s key pair is valid (i.e. was generated by $G_S$), then $Ver_i(Sign_i(M), M) = 1$ for any message $M$. We also assume that authentic, distinct encryption and verification public keys for each MIX node are known to all parties. Recipients of messages are treated as nodes. \subsection{Overall MIX-net design} Alice wants to send Bob a message anonymously. She chooses a path through the network consisting of $k-1$ MIXes, $N_1 \dots N_{k-1}$. We denote Alice as $N_0$ and Bob as $N_k$. Alice then repeatedly ``onion'' encrypts her message, and sends the onion to the first MIX in her path. That MIX returns a receipt, processes the onion, and passes the unwrapped-by-one-layer onion to the next MIX in the path, which repeats these steps. If the message does not reach Bob, the transaction has failed. (Section \ref{subsec:end-to-end} shows how to use ``end-to-end receipts'' to ensure that Alice knows when this has occurred.) Our system should be able to identify the MIX in the path that caused the transaction to fail. %Further, the system should not be vulnerable to %attacks to confuse or mislead. We have two goals: \begin{itemize} \item{Goal 1, {\bf Identify failure}:} If $N_i$ fails to pass on a well-formed message within the allowed time to the next node $N_{i+1}$, then Alice can prove to any third party that $N_i$ was the failing MIX (the completeness property). \item{Goal 2, {\bf Reject false claims}:} No participant (including Alice) can claim that $N_i$ failed to pass on a well-formed message to $N_{i+1}$ in time, unless it really did fail (the soundness property). \end{itemize} Since these goals involve timing constraints, we first describe the timing model that we use. Then we proceed to show the specifics of constructing and sending a message, and how we can fulfil the completeness and soundness goals. \subsection{Timing Model} We consider time to be split into periods, each of length one time unit, corresponding to batches of messages sent by MIXes. The period numbered $t$ lasts from time $t-1$ to time $t$. A message received by node $N_i$ in period $t$ will have timestamp $t$ on the corresponding receipt signed by $N_i$. If $N_i$ is not the final recipient, the message must be sent to the next node $N_{i+1}$ in period $t+1$. That is, the {\em deadline} for sending it to $N_{i+1}$ is $t+1$. All parties (MIXes, witnesses, senders of messages, and verifiers of failure claims) have clocks that are loosely synchronized, to within $T_{\epsilon}$ of the global time. Sending a message over a network is assumed to take $T_{comm}$ in the worst case. Therefore, whenever a party needs to send a message by time $t$, it should attempt to do it before $t - T_{\epsilon} - T_{comm}$ according to its local clock, because its local clock may be slow, and because it must allow time for the network communication. If a party is expecting a message to be sent to it by time $t$, then it should allow it to be received as late as $t + T_{\epsilon}$ according to its local clock, since that clock may be fast. We include these timing considerations in the protocol descriptions. The protocol requires several system-wide time constants: \begin{itemize} \item $T_{response}$ is the time that a node is allowed between receiving a message and providing a receipt. \item $T_{margin}$ is the length of the interval before the deadline, during which a node will attempt to send a message via the witnesses, if it has not been able to obtain a receipt directly from the next MIX. \item $T_{retain}$ is the time (number of periods) for which receipts are retained by MIXes. That is, if a MIX is asked for a receipt in period $t$, it need only provide it if the receipt has timestamp $t - T_{retain}$ or later. This will also determine the length of time for which failure claims can be directly verified. \end{itemize} \begin{figure}[htc] \begin{center} \leavevmode \label{fig-timing-example} \epsfbox{timing.1} \caption{Timing example} \end{center} \end{figure} Figure 2 depicts an example time line: \begin{itemize} \item time A is the point at which $N_i$ stops trying to send to $N_{i+1}$ directly. \item time B is when a witness $w$ tries to contact $N_{i+1}$. \item time C is the latest time at which $N_{i+1}$ can respond to $w$ with a receipt (this could also be before the deadline t+1). \end{itemize} Only global time is shown in the figure. Unfortunately the timing constraints, although important to the correctness of the protocol, tend to obscure the description of how it works. You may wish to ignore them on an initial reading. \subsection{Transmitting a Message} This section describes the protocol for transmitting a message from Alice to Bob, using our MIX-net design with verifiable failures. \subsubsection{Procedure {\tt Transmit}$(Alice, Bob, Plaintext)$:} \begin{enumerate} \item Alice chooses $k-1$ MIXes $N_1$, $\dots$ $N_{k-1}$ to form a ``MIX path''. Let $N_0$ be Alice, and let $N_k$ be Bob. \item Alice picks $k$ random seed values $r_1, r_2, \dots r_k$. \item Alice creates an initial packet $M_1$, defined as \begin{displaymath} M_1 = E_1^{r_1}(N_2, E_2^{r_2}(N_3, \dots E_{k-1}^{r_{k-1}}(Bob, E_k^{r_k}(Plaintext))\dots)) \end{displaymath} \item Let $now$ be the current time according to Alice's local clock, and let $Deadline_1 = \lceil now \rceil$. \item Try to send $M_1$ and $Deadline_1$ directly to $N_1$, waiting for a receipt. \item If a receipt $Rcpt$ is received, check that $Ver_{dest}(Rcpt, $``Receipt: $M_1, Deadline_1$''$) = 1$; if so, stop. \item If no receipt is returned, set $Deadline_1 := Deadline_1 + 1$, and use the procedure\newline {\tt Hop-send}$(N_1, M_1, Deadline_1)$ below to send $M_1$ to $N_1$. \end{enumerate} Under normal circumstances (i.e. assuming that all parties follow the protocol), the message will then be processed by $N_1, \dots N_{k-1}$ as follows: \begin{itemize} \item $N_1$ reads $M_1$ from Alice, and processes it according to the procedure \newline {\tt Hop-receive}$(Alice, N_1, M_1, Deadline_1)$. \item $N_1$ decrypts $M_1$ to give $(N_2, M_2)$, where \begin{displaymath} M_2 = E_2^{r_2}(N_3, \dots E_{k-1}^{r_{k-1}}(Bob, E_k^{r_k}(Plaintext))\dots) \end{displaymath} \item Let $Deadline_2 = Deadline_1 + 1$. \item $N_1$ uses the procedure {\tt Hop-send}$(N_2, M_2, Deadline_2)$ to send $M_2$ to $N_2$. \item This process is repeated by $N_2$, which sends $M_3$ to $N_3$, and so on for $N_3$, $N_4$, $\dots$, $N_{k-1}$. \item Eventually, $E_k^{r_k}(Plaintext)$ is sent to Bob. Bob can decrypt this message, so for this case, the plaintext has successfully been transmitted. \end{itemize} \subsubsection{Procedure {\tt Hop-send}$(N_{dest}, Message, Deadline)$:} \begin{enumerate} \item Try to send $Message$ and $Deadline$ to $N_{dest}$ directly, waiting for a receipt. \item If a receipt $Rcpt$ is received, check that $Ver_{dest}(Rcpt, $``Receipt: $Message, Deadline$''$) = 1$. \item If a valid receipt is not received before $Deadline - T_{margin} - T_{\epsilon}$ (by the sending node's local clock), \begin{enumerate} %% FIXME: do we care how these are picked? feamster asked -mjf %% subsec:witness-trust covers that. --DH \item Let $W$ be a set of witnesses. \item Send ``Witness: $N_{dest}, Message, Deadline$'' to each witness $w \in W$ (causing {\tt Witness} to be called on each $w$). Wait for any $w$ to send back a receipt. \item If a receipt $Rcpt$ is received, check that $Ver_{dest}(Rcpt, $``Receipt: $Message, Deadline$''$) = 1$. \item If no valid receipt is received, store any statements returned by the witnesses. \end{enumerate} \end{enumerate} Note that an imposter witness or MIX may send fake receipts to the sender in order to try to confuse it. The sender should ignore any receipts that are not valid. If the sender receives more than one valid receipt, it need only store one (chosen arbitrarily). \subsubsection{Procedure {\tt Hop-receive}$(N_{src}, N_{dest}, Message, Deadline)$:} \begin{enumerate} \item Let $now$ be the current time. \item If $now > Deadline + T_{\epsilon}$ or $now < Deadline - 1 - T_{\epsilon}$, drop the message and respond with an error. \item Otherwise, decrypt $Message$, and queue for transmission in the next period by {\tt Hop-send}. \item Send back the receipt $Sign_{dest}($``Receipt: $Message, Deadline$''$)$ to $N_{src}$. \end{enumerate} \subsubsection{Procedure {\tt Witness}$(N_{src}, N_{dest}, Message, Deadline)$:} \begin{enumerate} \item Let $now$ be the current time. \item (The witness must be sure that $N_{dest}$ has time to respond:) If $now > Deadline - T_{comm} - T_{\epsilon}$ or $now < Deadline - 1 + T_{\epsilon}$, drop the message and respond with an error. \item Try to send $Message$ to $N_{dest}$ directly, waiting for a receipt. \item If a receipt $Rcpt$ is received, check that $Ver_{dest}(Rcpt, $``Receipt: $Message, Deadline$''$) = 1$. If so, send it back to $N_{src}$. \item If a valid receipt is not received before $Deadline + T_{response} + T_{\epsilon}$, conclude that $N_{dest}$ failed, and send back the statement ``Failed: $N_{dest}, Message, Deadline$'', signed by the witness, to $N_{src}$. \end{enumerate} \subsection{Identifying and Proving Failed Transactions} \label{subsec:proving} This section describes the method by which Alice proves the failure of a specific MIX to deliver a message, as well as the protection our protocol offers against a malicious Alice who either sends ill-formed messages or provides false claims. Alice can prove her claim of failure to any chosen verifier (call him Victor). We will describe the duty of the verifier in our reputation system in Section \ref{sec:reputation}. Suppose that $N_i$, where $1 \leq i < k$, is the first node on the path that does not follow the protocol, i.e., it fails to handle a message $M_i$ that $N_{i-1}$ sends to it, within the allowed time. Alice wants to prove to Victor that $N_i$ failed to process this message (which she might discover by a binary search over her MIX path). Because $N_{i-1}$ behaved according to protocol, it will have a receipt $Rcpt_i$ for the message $M_i$ with deadline $Deadline_i$, where \begin{displaymath} M_i = E_i^{r_i}(N_{i+1}, E_{i+1}^{r_{i+1}}(\dots E_{k-1}^{r_{k-1}}(Bob, E_k^{r_k}(Plaintext))\dots)) \end{displaymath} As Alice knows all the random padding values, she can compute the message that $N_i$ is supposed to send to $N_{i+1}$: \begin{displaymath} (N_{i+1}, M_{i+1}) = D_i(M_i) = (N_{i+1}, E_{i+1}^{r_{i+1}}(\dots E_{k-1}^{r_{k-1}}(Bob, E_k^{r_k}(Plaintext))\dots)) \end{displaymath} She suspects that this message was not actually sent to $N_{i+1}$, so she prepares a claim by obtaining the $Rcpt_i$ from $N_{i-1}$, and calculating $M_{i+1}$ as above. Then Alice sends Victor ``I blame $N_i$, claim: $r_i, N_{i+1}, M_{i+1}, Deadline_i, Rcpt_i$'', which he verifies as follows: \subsubsection{Procedure {\tt Verify-claim}$(N_i, r_i, N_{i+1}, M_{i+1}, Deadline_i, Rcpt_i)$:} \begin{enumerate} \item Check that $N_i$ and $N_{i+1}$ refer to valid MIXes, and $M_{i+1}$ is the correct length for an intermediate message. \item Calculate $M_i = E_i^{r_i}(N_{i+1}, M_{i+1})$, and check that $Ver_i(Rcpt_i, $``Receipt: $M_i, Deadline_i$''$) = 1$. \item Let $now$ be the current time. If $Deadline_i + 1 < now - T_{retain} + T_{\epsilon}$, then it is too late for the claim to be verified, since $N_i$ may legitimately have discarded its receipt; the claim is therefore rejected. \item Send ``Receipt request: $N_{i+1}, M_{i+1}$'' to $N_i$. \item If ``Receipt response: $Rcpt_{i+1}, Timestamp$'' is received from $N_i$ within time $T_{response}$, such that\newline $Ver_{i+1}(Rcpt_{i+1}, $``Receipt: $M_{i+1}, Timestamp$''$) = 1$ and $Timestamp \leq Deadline_i + 1$, then reject the claim. \item If statements ``Failed: $N_{i+1}, M_{i+1}, Timestamp$'' signed by a sufficient set of witnesses are received, for some $Timestamp \leq Deadline_i + 1$, conclude that $N_i$ made a reasonable attempt to send the message, and reject the claim. (See Section \ref{subsec:witness-trust} for discussion of trust requirements on witnesses.) \item Otherwise, conclude that $N_i$ failed -- either because it did not process the original message, or because it did not respond to the receipt request. \end{enumerate} \subsubsection{Proving that a delivery failure results in a proper claim} \paragraph{Sketch} $N_{i+1}$ will only give out a receipt for which $Ver_{i+1}(Rcpt_{i+1}, $``Receipt: $M_{i+1}, Deadline_i + 1$''$) = 1$, if it received the message $M_{i+1}$ by time $Deadline_i + 1$. If it did not receive $M_{i+1}$ by then, and under the assumption that $N_{i+1}$'s signatures cannot be forged, $N_i$ will not be able to provide such a signature. Thus, Victor will conclude that it failed. Node $N_{i+1}$ may possibly be controlled by the adversary; in that case, it might provide a receipt on $M_{i+1}$ in order to exonerate $N_i$, even though $M_i$ was not actually processed. However, Alice can then use this receipt in the same protocol to attempt to prove that $N_{i+1}$ failed. Therefore, the adversary will be able to choose which of the contiguous MIXes it controls can be proven unreliable. However, since there are only $k-2$ other nodes on the path, Alice will be able to prove that some node failed, after at most $k-1$ iterations of the protocol. Because Alice can always prove that some MIX failed if it did in fact fail, we satisfy Goal 1, being able to identify failures in the MIX-net. We note that knowledge of the fact that $N_i$ and $N_{i+1}$ are part of Alice's chosen path is \emph{not} part of the view of a passive adversary in a normal MIX-net protocol. The closer $N_{i+1}$ is to the end of the path, the more likely it is that this additional information will allow an adversary to link Alice with Bob (since the remaining path is effectively shortened to $k-(i+1)$ hops). In the worst case $N_{i+1}$ may be Bob, which would reveal directly the fact that Alice was attempting to send a message to him. In order to avoid giving away this information, Alice may send all the messages needed for the failure proof over the MIX-net. When requesting receipts she can include a reply block, so that the node will be able to send back the receipt while Alice remains anonymous. It may seem circular to rely on the MIX-net to send messages needed for a failure proof, when the goal of the proof protocol is to improve MIX-net reliability. However, since these messages are only used to prove failure and do not convey any other information, it is not critical that all of them are successfully transmitted. Alice can repeat any attempts to obtain receipts and to send the claim message to Victor as often as necessary, using random independent paths for each attempt. This will succeed quickly provided that the probability of a message making it through the MIX-net (from Alice) is not too small. %% Make this more precise. Can we handwave that if the system is not 'too' %% unreliable initially, its reliability stabilises at a high level? %% We do that later, so no need to do it here. %% Does the extra traffic over a short period pose a significant risk to %% Alice's anonymity? No, I don't think it does, unless the mix-net is %% broken for other reasons. --DH \subsubsection{Proving that false claims are rejected} \paragraph{Sketch} We wish to show that no participant can claim that $N_i$ failed to pass on a well-formed message sent by Alice to $N_{i+1}$, unless it really did fail to send such a message. Without loss of generality, we will consider the adversary to be Alice. Recall that Alice's claim to Victor is of the form ``I blame $N_i$, claim: $r_i, N_{i+1}, M_{i+1}, Deadline_i, Rcpt_i$''. Victor then calculates $M_i = E_i^{r_i}(N_{i+1}, M_{i+1})$. Decrypting both sides, we obtain $D_i(M_i) = (N_{i+1}, M_{i+1})$, assuming $N_i$'s key pair is valid.\footnote{ We can assume that $N_i$'s public key is valid because it is chosen by $N_i$, who would have no incentive to generate an invalid key. We omit consideration of an $N_i$ controlled by Alice that purposely chooses an invalid key, because then Alice only damages the reputation of a node she controls.} %% General note on fixme's: the more timing constraint floating %% around, the less readable it becomes to me -mjf %% Considering the timing constraints in the proof, rather than %% separately, is the only way to make it rigorous. --DH \begin{itemize} \item Suppose Alice caused the message $M_i$ to be sent to $N_i$ by time $Deadline_i$, and then tried to claim that $N_i$ failed. A well-behaving $N_i$ will decrypt $M_i$ to give the next hop and intermediate message $(N_{i+1}, M_{i+1})$. It will then try to send $M_{i+1}$ to $N_{i+1}$ using {\tt Hop-send}. Either $N_i$ will obtain a receipt for this message (signed by $N_{i+1}$ and having the timestamp $Deadline_i + 1$), that refutes Alice's claim, or it will have signed statements from a sufficient set of witnesses (see Section \ref{subsec:witness-trust}) saying that $N_{i+1}$ refused to provide a receipt when it was obliged to do so. In either case, $N_i$ will be exonerated. \item Suppose Alice did not cause $M_i$ to be sent to $N_i$ by $Deadline_i$. In order to make a credible claim, Alice needs a receipt $Rcpt_i$ such that $Ver_i(Rcpt_i, $``Receipt: $M_i, Deadline_i$''$) = 1$ (since Victor will check this). However, if $N_i$ did not receive $M_i$, it will not have given out any such receipt, and so assuming that $N_i$'s signatures cannot be forged,\footnote{ We take the position that if $N_i$'s private key has been compromised, it should be considered to have failed, and so it does not matter that an adversary who knows the private key can ``prove'' that $N_i$ failed to pass on any message.} it will be exonerated. \end{itemize} Another way in which a node could be falsely accused of failure, is if there are ``sufficient'' witness statements against it as defined in Section \ref{subsec:witness-trust}. We assume that this does not occur, because the adversary is not able to subvert witnesses in the core group. Therefore, we satisfy Goal 2. Note that the above argument covers the case in which Alice attempts to send messages to $N_i$ that either do not decrypt, or decrypt to ill-formed plaintexts, since we have proven that for Alice's claim to be accepted, $N_i$ must have received a message with a well-formed $(N_{i+1}, M_{i+1})$ pair as the plaintext. The above discussion does not take into account replay attacks. Many MIX-net protocols require MIX nodes to refuse to pass on a message if it is a {\em replay}, that is if the MIX had already received that message within a given time period (see \cite{babel} for a rationale). We do not want nodes to lose reputation because of this behavior. Our protocol is able to handle this case because when a MIX receives a replayed message (using {\tt Hop-receive} as normal), it will already have a receipt from the previous time it sent that message (or else witness statements showing that it tried to send it). Steps 5 and 6 of {\tt Verify-claim} show that it can provide the earlier receipt or statements when challenged with a failure claim. We define the length of time for which replays are remembered to be the same as $T_{retain}$. To make sure that it is able to respond to future claims, whenever a node receives a replayed message, it should record that it needs to store the receipt or statements that were obtained for the earlier message, for a further $T_{retain}$ periods. %% Not doing this allows N_i to be falsely accused: %% - send a message M to N_i in period t %% - send a replay of M to N_i in period t+k (getting a second receipt R on M) %% - wait until period t+T_retain, for N_i to expire its receipt on M from %% N_{i+1} %% - use R to accuse N_i of failure, before time t+k+T_retain. %Note that a message should be considered a replay if its plaintext has %been seen before, not just its ciphertext. This is because there may %be many ciphertexts that decrypt to a single plaintext. If these were %not considered replays, Alice would be able to prepare two ciphertexts %decrypting to the same plaintext, and send both to $N_i$. %% On second thoughts I don't think this causes a problem. All that %% happens is that $N_{i+1}$ receives a replay, but it should still %% send back a receipt, so $N_i$ is OK (and $N_{i+1}$ is OK because it %% has its earlier receipt from $N_{i+2}$). --DH \subsection{End-to-End Receipts} \label{subsec:end-to-end} The protocol described above assumes that Alice has some way of determining whether her message has failed. In some cases, such as posts to a public forum like Usenet, Alice (and any verifier) can easily see whether the message was posted correctly. For the remaining cases, if we use a MIX-net design that supports reply blocks or another method for two-way communication, it is possible for Bob's software to immediately send an {\em end-to-end receipt} back through the MIX-net to Alice, as soon as he receives a message. Note that reply blocks used for end-to-end receipts only need to be used once, and the receipt is sent immediately. This allows some of the security problems otherwise associated with reply blocks, pointed out in \cite{babel}, to be eliminated. Since a failure can also occur on the return path, we would like Alice to be able to prove these failures as well. That is, if Alice does not get an end-to-end receipt within a specific time, she will be able to prove one of three cases: a MIX on the forward path failed; a MIX on the reply path failed; or Bob failed to send a receipt. With careful design of message formats, it is possible to make receipt messages indistinguishable from forward messages to nodes on the reply path. In that case, the same protocol used to claim failures in sending forward messages will be applicable to reply messages. That is, the path can be treated as a loop from Alice to Bob, then back to Alice. However, we do not attempt to explain details of message formats in this paper. \subsection{Trust Requirements for Witnesses} \label{subsec:witness-trust} Dishonest witnesses do not compromise anonymity, but they can compromise reliability. Witnesses could either refuse to give a statement or receipt for a MIX that has failed, or make false statements in order to frame a MIX that has not in fact failed. If users of the MIX-net were prepared to trust an arbitrary set of witnesses chosen by a sending node, then it would be easy for an adversary to perform the latter attack. Therefore, we suggest defining a core group of witnesses who are relatively widely trusted. If some threshold number of this core group provide statements implying that a node $N_{i+1}$ has failed (and that its predecessor on the path $N_i$ has not), that would be considered {\em sufficient} for the purposes of {\tt Verify-claim}. This solution is not ideal, because specifying a fixed (or even slowly changing) group of witnesses runs counter to the goals of a truly decentralised protocol. If the messages sent to this group are also published, though, then it is possible for other parties to duplicate their actions, thus gaining confidence that they are behaving honestly. \section{Reputation Systems} \label{sec:reputation} Reputations have been suggested as a means of improving MIX-net reliability \cite{timmay,levien}. To date, discussions of reputation systems in the context of MIX-nets have been vague. We now specify what we mean by a reputation system in the context of a MIX-net, and investigate a specific design to help solve the reliability problem. As stated earlier, the major parties in the overall MIX-net system are Alice (the sender), Bob (the recipient), and the MIX nodes. In layering on a reputation system, we add two more agents to the system. \emph{Raters} are entities who make observations about the performance or honesty of MIXes. In our case, the raters are both the sender Alice and any MIXes that make use of the witnesses. \emph{Scorers} are entities who tally observations from raters and make these tallies (or \emph{scores}) available. For convenience and simplicity, we choose to give the scorer the duties of verifier and witness as well. \subsection{Requirements for Our Reputation System} We have a variety of goals for developing a reputation scoring system for a MIX-net. Senders must be able to configure their software to automatically take into account the scores for each MIX; indeed, current client software such as \cite{potato} already includes this support. Any user of the MIX-net must be able to contribute \emph{ratings} (observations about MIX behavior). The system must resist attempts of any adversaries to influence scores in a way that does not ``reflect reality''; but at the same time, to maintain efficiency, security, and reliability, no single server should be a bottleneck anywhere in the protocol. The scoring system must be verifiable. That is, scorers need some way to determine the credibility of ratings, and other users need some way to verify that scorers are tallying ratings correctly. The scores themselves must be accurate --- clients must be able to draw conclusions from scores that lead to ``good'' predictions. The overall scoring algorithm must be dynamic, recognizing and reflecting recent trends in MIX performance. %For %example, a MIX that has behaved well for a long time but suddenly goes %downhill should be quickly recognized and no longer trusted. While achieving all of these goals, the system must also maintain the level of anonymity provided by the MIX-net. \subsection{Reputation System Overview} Section \ref{sec:mix-design} outlined a technique by which Alice can confirm the failure of a specific MIX to forward her message, and communicate this knowledge to some third party verifier. We introduce a set of scorers, each named Sally. Each of these scorers keeps her own database of performance scores for MIXes in the system. When she receives a failure claim as detailed in Section \ref{sec:mix-design}, she verifies it, and updates her score database if necessary. Scorers also send test messages to distinguish reliable MIXes (few delivery failures because they actually deliver messages well) from new MIXes (few delivery failures because nobody has sent any messages through them yet). Sally makes available her database of MIX reputations, so that Alice's client software can download it and use it to automatically choose paths. Client software can be configured to only choose MIXes with a minimum number of successful tests; after that, MIXes are rated by the number of verified delivery failures. %We would like to develop a flexible scoring system, modelling the %actual scoring process as arbitrary reputation functions. The inputs %to Sally are success or failure claims; she outputs some probabilistic %reputation distribution for each node (the variance of this %distribution reflects her confidence). Thus client software can %specify parameters when selecting acceptable MIX paths, such as %``expected success of transmission''. If we simply count the number of messages that each MIX drops, an effective attack would be to constantly add new unreliable MIXes. Instead, we describe scores as two numbers: the first is the count of negative ratings as described above, and the second is a ``minimum number of positive ratings'' requirement, which is a threshold configurable on the client side. \subsection{Tallying negative ratings} As we showed in Section \ref{subsec:proving}, each negative rating really does represent a failed delivery. That is, if a valid message onion is sent to $N_i$, then it really is $N_i$'s fault if he doesn't either deliver the decrypted onion to $N_{i+1}$ within the allowed time window, or get statements from credible witnesses saying that $N_{i+1}$ was down. Anybody who is able to demonstrate that it was a valid onion is either that MIX or the onion's author; the MIX has no incentive to publicize that it failed at a transaction. Thus, if our assumptions hold, there is no way to spoof negative ratings. Note that an adversary may be able to force negative ratings on a MIX, while goal 2 still holds: if he floods that MIX's incoming bandwidth (either directly or via witnesses), the MIX will no longer be able to sustain the load. However, this point is exactly the point where the MIX is demonstrating the fact that it is unreliable. %it is unable to handle its current load of messages. Causing MIXes to lose reputation in the face of \emph{successful} flooding is consistent with our scoring system goals; after all, the scoring system measures reliability and capabilities, not intent. \subsection{Tallying positive ratings} Positive ratings differ from negative ratings in that they can be easily faked. Specifically, an adversary can make up a set of messages, each using a MIX path entirely owned by him, and then simply generate transcripts for those messages from the same machine that built each onion. Algorithms that consider the number of positive ratings (either by adding positive and negative ratings, % as eBay does, or by taking the ratio of positive ratings to negative ratings) are generally going to be vulnerable to this sort of shilling attack. However, using only the number of negative ratings to calculate reputation score gives a perfect score to completely untested MIXes. %Specifically, %reducing the reliability of the overall system is as easy as getting a %new bad MIX added to Sally's list. We need some way to confirm that positive ratings actually reflect a MIX's ability to successfully deliver Alice's message in the future. \subsection{Approaches to increase confidence in positive ratings} \label{sec:rep-solutions} One approach to making positive ratings more reliable (and thus more meaningful) is to build a graph based on rater credibility %that addresses reputation transitivity, such as that employed by Advogato \cite{advogato}. Similar to the PGP web of trust, this technique builds a directed graph where edge weights represent trust that one vertex places in the other; in our case, each vertex would be a MIX. Calculating maximum flow from some node $A$ in the graph to some node $B$ shows how much trust $A$ places in $B$, even if $A$ never directly rated $B$. The Advogato trust metric aims to reduce the damage that an adversary can cause by \emph{pseudospoofing} -- creating a multitude of identities each controlled by that adversary. At first, each of the new nodes is connected only to itself in the graph. Even after the pseudospoofing nodes begin to form connections with the rest of the graph, there will still be ``trust bottlenecks'' that limit the amount of trust arriving at any of the pseudospoofing nodes. Another approach is to treat reputation as a probability: an estimate of the expected outcome of a transaction with that MIX. Scores might simply be the sum of ratings, normalized and weighted by the credibility of raters. %% Don't want to slam other systems as ``complex'' without understanding %% what it is that they do -DM %% I thought this was making an important point, so I've put most of %% it back. --DH Other designs employ neural networks or data clustering techniques to apply non-linear fitting and optimization systems to the field of reputation. However, such complex solutions may not be easily understood or verified by the users of the reputation score. Moreover, to our knowledge these more statistical approaches to aggregating reputation values have never been studied in the context of adversaries who understand and attempt to exploit the algorithm. Such evaluation techniques which are intended for ``clean'' environments can introduce serious vulnerabilities and complications, which in turn require rater credibility tracking systems to track which raters are providing ``good'' data. %Rather than developing a complex and brittle rater credibility system, We solve the positive rating credibility problem by having each Sally produce positive ratings herself --- after all, if Sally sends the test messages herself, she knows that they are unbiased ratings. MIXes that reliably and correctly process her message will earn positive ratings that Sally knows to be accurate. In order to ensure that positive ratings are accurate, test messages should be indistinguishable from real messages (otherwise, an adversary could behave reliably for test messages, but unreliably for real messages). In addition, nodes should not be able to determine that the sender of a message is a rater; otherwise the MIX could decide to behave well only for a small set of senders and badly for everyone else. This is similar to the problem restaurant critics face when attempting to determine a restaurant's ``real'' level of service. It will normally be possible for an adversary to guess whether a message has been received directly from a sender (i.e. the adversary is the first hop on the path, $N_1$), or if it is being sent to the final recipient (i.e. the adversary is $N_{k-1}$). Unfortunately, it is difficult to produce simulated messages that are completely indistinguishable from real messages in these cases. We do not have a fully satisfactory solution to this for positive ratings; instead, we rely on negative ratings to expose an adversary that behaves unreliably only when it is the first or last hop. Sally should expire her memories of transactions after a certain amount of time so that failures in the distant past do not haunt a MIX forever. Similarly, MIXes need to have a threshold of recent successes in order to stay ``in the running''. Alice configures her client software to choose only among MIXes that have a specified minimum number of positive ratings. Out of this pool, she weights the MIXes that she chooses for her path based on the number of verified delivery failures that have been observed for this MIX. %Because the client software simply requires a minimum number of successful %deliveries, Sally has a lot of flexibility. Her only real goal is to weed %out the systems that are not able to deliver any messages --- that is, %systems that are not ``real'' MIXes. Beyond that, the count of message failures %will be the differentiator between a reliable MIX and an unreliable one. %Indeed, this system has the property that it reacts quickly to a This system reacts quickly to a decrease in reliability of a MIX. If a MIX has a high reputation, it is likely that there are many users routing messages through it. If it suddenly stops delivering messages, these users will notice these failures, and a series of negative ratings will quickly arrive. This negative feedback process serves to stabilize the system and help the scores reflect reality. \subsection{Redundancy and verifiability of scorers} %Alice can use whichever Sally she happens to like. Some Sally's might add %value simply by combining the reputation scores from other Sally's --- %that is, they would not verify failure proofs themselves. If Alice keeps a tally herself of her transactions (and she can, by remembering which mails had a corresponding end-to-end receipt), then she can build her own score table in which she is confident of both the positive ratings and the negative ratings. Every so often she might compare her score tables with those of the available Sally's. % and start using the most closely matching Sally as her primary score % provider. This process allows Alice to ``test the waters'' herself and weakens the trust requirements on scorers -- Sally is more accountable for her scores because Alice can also compute scores and compare. Indeed, if claims for dropped messages are published, anybody can verify them. Thus Alice might keep track of negative ratings for a few weeks, then compare with Sally to determine if Sally's scores are actually reflecting all of the negative ratings. \subsection{Implications for Traffic Analysis} %Virtually any extension or variant of a MIX-net protocol has %implications for traffic analysis. As there is no real accepted %framework for considering traffic analysis attacks and defenses, %however, it is difficult to analyze the results of any protocol %changes. We present a few questions and some approaches to %resolving these issues. The addition of witnesses to the protocol may introduce new attacks. Direct communications between nodes can use link encryption, but encrypting the messages to witnesses would have little benefit (and would be incompatible with publishing these messages, as suggested in Section \ref{subsec:witness-trust}). So if an adversary can force the witnesses to be used instead of direct communication, this may weaken the security of the network. On the other hand, link encryption of messages between nodes is not strictly necessary to achieve anonymity in a MIX-net; it is only a ``belt-and-braces'' measure. %% A lot of context is needed to describe marking attacks properly - %% I'll leave it to another paper, maybe. --DH The reputation system introduces new attacks as well. For instance, Eve might gain a high reputation and thus get more traffic routed through her MIX, in order to make traffic analysis easier. In a system without reputations, the way to purchase more traffic to analyze is not so clear; now it is simply a matter of maintaining a reliable MIX. In addition, the adversary now has incentive to degrade or sabotage the performance of other nodes in order to make his relative reputation higher. This kind of attack was described by RProcess as ``selective denial of service'': the bad guys want traffic to go through their nodes, so they ensure that all other nodes are less reliable \cite{RProcess}. As recent distributed denial of service attacks demonstrate, crippling an Internet host can be easy. Scorers must expire ratings promptly enough to prevent an adversary from easily tarnishing the reputations of all other MIXes. On the other hand, we may well be making the system \emph{more} anonymous by making it more reliable. Currently, users may have to send a message many different times, through many different paths, before it successfully arrives at its destination. These re-sends of the same message offer more information to traffic analyzers. %Reducing the number of repeated messages %may be an effective measure for increasing the anonymity offered by the %overall remailer system. A better theoretical framework for traffic analysis needs to be established before we can make any quantifiable statements about the implications of the proposed protocol. \section{Quantifying MIX Reliability} \label{sec:quantify} We now turn our attention to quantifying MIX reliability in order to measure the improvement in reliability provided by reputation systems. It seems intuitively clear that using Levien-style statistics to pick remailers gives a message a better chance of reaching its destination safely. Why would we need to introduce a formal way of quantifying this information and its result? There are at least three answers to this: \begin{enumerate} \item To confirm our intuition. Cryptography, especially anonymous systems, is a surprising field. \item To offer a means to compare two different proposals for MIX-nets based on a quantitative measure of the reliability improvement they provide. \item To better understand why and how reputation systems work. In particular, to gain insight into what could happen if a reputation system provides incorrect reputations (through stupidity or malice). \end{enumerate} We now present a model and metric which will fulfil the first of these goals. The second and third are left for future work. %\subsection{Reliability Metrics} % %\begin{enumerate} % %\item A higher value should correspond to a more ``reliable" MIX-net. % %\item Given that users pick MIX paths so as to maximize the likelihood of success, %the metric reflects the probability of successful transmission. % %\item The metric should be easy to evaluate, at least in a model where we %specify an adversary's range of possible behavior. % %\end{enumerate} \subsection{A Proposed Reliability Metric} A \emph{reliability metric} is a quantitative measure of the reliability of a MIX-net. We now propose a reliability metric that is the expected value of the probability that a message reaches its intended receiver. Recall from section \ref{sec:reliability-model} that to send a message, a sender $s \in S$ picks a recipient $r \in R$ according to the distribution $R_s$, and then picks a MIX path, $path \in {Paths}$ according to the distribution ${Path}_{s,r}$. For simplicity, we restrict ourselves to a single receiver at a time with MIX paths that are exactly $k$ nodes long; this means that $R_s$ takes on single values $r \in R$ while ${Path}_{s,r}$ takes on values that are sequences of length $k$ in ${Paths}$. We consider an adversary that corrupts MIXes and causes them to fail. Every $mix \in \mbox{\it MIXes}$ is either \emph{good} or \emph{bad}. Good MIXes work normally (but may fail due to error), and bad MIXes are controlled by an adversary. Good MIXes have probability of failure $p_{good}$ and bad MIXes have probability of failure $p_{bad}$, where ``failure'' means that a message fails to be passed on to the next hop. An \emph{adversary} then controls the subset $\mbox{\it BAD} \subset \mbox{\it MIXes}$. We note that as stated here, the adversary does not have a memory and does not adapt to previous behavior; both of these are major simplifying assumptions which should be removed in future work. We use the simple metric that the reliability of the MIX-net is the expected probability of $V$ defined as the event ``a message survives the MIX-net'' -- that is, the probability that none of the nodes on the MIX path picked by the sender fail. We further define $V_s$ for ``a message from sender s survives the MIX-net'' and $V_{s,r}$ for ``a message from sender s to recipient r survives the MIX-net.'' We can evaluate the expected probability of $V$ by using the law of total expectation: \begin{displaymath} E(V) = E(E(V_s) | \texttt{sender} = s ) = E(E(E(V_{s,r}) | R_s = r) | \texttt{sender} = s) \end{displaymath} That is, we can compute $E(V)$ by first computing the probability of survival for a single message sent from a sender to a receiver, then averaging and summing over all senders and all receivers. \subsection{MIX Reliability With No Reputation System} \label{subsec:withoutrep} We now compute the reliability metric on a sample MIX-net with no reputation system whatsoever. We assume that there is no information available on which MIXes are good and which are bad, and so each client picks MIXes randomly (with replacement\footnote{ Picking MIXes with replacement is not an ideal strategy from the point of view of maintaining anonymity, because it gives a slightly increased probability that all or nearly all of the MIXes are controlled by an adversary, compared to picking $k$ distinct MIXes. There is little difference if the number of MIXes $m$ is large, however. }); that is, for all $s$ and $r$, ${Path}_{s,r}$ is a discrete uniform random variable. We make the simplifying assumption that senders choose from all receivers uniformly at random, so for all $s$, $R_{s}$ is a discrete uniform random variable. Finally, we set $p_{good} = 0$ and $p_{bad} > 0$; this corresponds to the simplifying assumption that good nodes are always reliable, while bad nodes have some constant probability of failure. Suppose the adversary controls a randomly chosen subset ${BAD}$ of the $m$ MIXes, with $|\mbox{\it BAD}| = q$. Then when picking a MIX path to a receiver, a sender has chance $\frac{q}{m}$ each time it picks a MIX of picking a bad MIX. The probability that each MIX it chooses will fail is $p_{bad} \cdot \frac{q}{m} + p_{good} \cdot (1-\frac{q}{m}) = p_{bad} \cdot \frac{q}{m}$. Therefore, the chance of picking no MIXes that will fail is $(1 - p_{bad} \cdot \frac{q}{m})^k$, since the sender picks $k$ MIXes. Because a message survives the MIX-net if and only if no MIXes on the path fail, this gives us $E(V_{s,r}) = (1 - p_{bad} \cdot \frac{q}{m})^k$. Given that every receiver has the same $E(V_{s,r})$ and that receivers and senders are picked uniformly, we also have $E(V) = E(V_s) = (1 - p_{bad} \cdot \frac{q}{m})^k$. %% Too trivial --DH %\begin{eqnarray*} %V_s & = & \Sigma^{|R|}_{i = 1} \frac{1}{|R|} E(V_{s,r}) \\ %V_s & = & \Sigma^{|R|}_{i = 1} \frac{1}{|R|} (1 - p_{bad} \cdot \frac{q}{m})^k \\ %V_s & = & (1 - p_{bad} \cdot \frac{q}{m})^k %\end{eqnarray*} % %We want $E(V)$, which we can compute by taking %$E(E(V_s))$ to find $E(V) = (1 - p_{bad} \cdot \frac{q}{m})^k$. Notice that, assuming $p_{bad} > 0$ and $q > 0$, the reliability of the MIX-net drops off exponentially as the number of hops in the MIX path increases. \subsection{MIX-net Reliability with Reputation Systems} \label{subsec:withrep} We now show that a reputation system improves the reliability of a MIX-net in our model. The only quantities that change are the distributions ${Path}_s$. A reputation system will give each sender $s$ some information about which MIXes are good and which are bad. If all goes well, $s$ can then adjust its choice of MIX paths to avoid the bad MIXes. In order to study this adjustment, we make several simplifications. First, time is divided into two phases called the ``observe phase'' and the ``advice phase.'' In the observe phase, the raters send test messages, such that each MIX node is queried at least $n \geq 1$ times by an honest rater. The information from these queries is collected and made available by the scorer. Then in the advice phase, we assume that all senders adjust their choice of MIXes based solely on the advice of the scorer. In the observe phase, we assume that raters make queries independently of each other by sending test messages through the network. If a test message survives, the rater should make a {\em positive report} for all the MIXes on that path. If the test message is dropped, the rater should determine which MIX failed as described in Section \ref{subsec:proving}, and make a {\em negative report} for that MIX. After the queries are complete, the scorer makes the reports available to all senders. Each sender restricts consideration to MIXes that have at least a given number of positive reports, and from those picks the MIXes with the least number of negative reports. In our example situation where $p_{good} = 0$, all negative reports will be for bad MIXes. We assume that $n$ positive reports are sufficient to satisfy the minimum requirement, so that all the %good %% We actually assume all the bad mixes will satisfy the min requirement as well. %% Is that right? --DH MIXes will be used. A single query to an adversary-controlled MIX is enough to establish a negative report and disqualify it from MIX path selection. If $n$ queries are made to each MIX, then the probability of each bad MIX remaining without any negative reports is $(1-p_{bad})^n$. (However, it can be argued that such a MIX is not really ``bad'' at that point, since it has not yet failed.) Recall that we found the chance that a sender picks a good MIX path to be $(1 - p_{bad} \cdot \frac{q}{m})^k$. Now in the ``advice phase,'' instead of $q$ bad MIXes picked from a pool of $m$, an expected $q \cdot (1-p_{bad})^n$ bad MIXes will be picked from a pool of $m - q + q \cdot (1-p_{bad})^n$. Following the analysis in the previous section, we see that $E(V)$ becomes $(1 - \frac{p_{bad} \cdot q \cdot (1-p_{bad})^n}{m - q + q \cdot (1-p_{bad})^n})^k$. Provided that at least one bad MIX was eliminated and $q < m$, this is an improvement. %% FIXME: How much of an improvement? Give example. --DH Therefore we have shown in this simplified model that honest reports yield an improvement in MIX-net reliability. Note that the first part of this paper is precisely about how to ensure reports are honest, so that we can assume honest reports at this point. There are several directions we could go from here to make this a more realistic analysis: \begin{itemize} \item Investigate other reliability metrics that may be more natural or precise. \item Investigate the cases when $p_{good} \neq 0$, and where $p_{bad}$ is different for the first or last hop of a path. \item Investigate non-uniform distributions for each of the random variables involved. \item Investigate a unifying probability of failure $p_f$ for all nodes, instead of having disjoint ``good'' and ``bad'' subsets. Furthermore, investigate the general case of some probabilistic distribution for failures with non-zero variance, for system-specific reputation functions. \item Bring the adversary model closer to reality. \item Treat anonymity and reliability simultaneously, with an eye to ``how many people use the service to provide cover.'' One way to model this might be to set the number of users as a function of the reliability of the MIX-net. \end{itemize} \section{Network Flow Analysis for MIX-nets} \label{sec:networkflow} We have just described a simple metric for measuring MIX-net reliability on a per-node basis. In reality, a reputation system provides a feedback mechanism to account for dynamic network reliability. As users engage in the MIX-net protocol and report failures accordingly, reputations are continually revised based on this ongoing accountability mechanism. Therefore, this feedback provides an element of learning for path selection. From a graph theoretic standpoint, the MIX path selection process can be modelled as a multicommodity unsplittable flow problem. % \cite{multi-flow}. % FIXME - need a cite here! -rd Multicommodity flow generalizes a maxflow problem by allowing multiples sources and sinks, which can transmit arbitrary types of flow, called {\em commodities}. The problem is complicated in that our flows are {\em unsplittable} -- flows are onion-encrypted messages, sent along paths pre-defined by the sources and thus must be transmitted as integral units. While finding an exact solution to fractional multicommodity flow is in P, obtaining {\em integral} solutions is NP-hard. Furthermore, network flow problems generally require global, exact knowledge and centralized control of flows. This is not realistic for a decentralized MIX-net. We must contend with imperfect knowledge of bandwidth (edge capacity) and the costs associated with an edge. We may approximate the cost of an edge $(s,t)$ as equal to its destination's probability of failure $p_f(t)$; still, reputation measurements may lag behind current network state. We turn to approximation algorithms to solve such multicommodity UFP in {\em practically} efficient polynomial time. A classic technique, Raghavan's rounding algorithm \cite{raghavan87randomized}, may be used for this general class of flow problems, provided that maximum demands %Leighton et al \cite{leighton91fast} solves multiple maxflow computations; are logarithmically smaller than the minimum capacity of a path. For client-selected MIX paths, the users themselves could solve individual flow problems, with scorers' reputations only serving as an input to their calculations. This decentralized solving mechanism offers a challenge for traditional multicommodity flow problems. We leave this for future work. \section{Conclusion and Future Directions} \label{sec:conclusion} We have described a more robust reputation system for remailer networks, based on a MIX-net design that employs receipts for intermediate messages. This reputation system improves the reliability of the overall network over a random MIX path, and is less susceptible to service denial than other remailer reputation solutions such as statistics pages. There are a number of directions for future research: \begin{itemize} \item The protocol as we have described it is still very rough; actual deployment and testing of the MIX extension and reputation system would let us see how well it really works. \item More analysis of our model and our reliability metric, as described in the previous section, could lead to better reputation systems. Indeed, a parallel model characterizing efficiency of a MIX network might be very enlightening, especially from a network flow optimization viewpoint. \item Can we achieve some further measure of reliability (or resource management) through the use of electronic cash or similar accountability measures? % self-cite O'Reilly P2P chapter? Indeed, the NymIP group \cite{nymip} has a long list of similar improvements that need to be further analyzed and developed. \item Can we make a reputation system that is both efficient and universally verifiable? Currently, only Alice can claim and prove that a message did not reach its destination. Can we apply zero-knowledge proofs so that Alice does not leak any information about the next hop while claiming failure, yet remain practically efficient? Can we extend this so that anyone can detect a failed MIX node? \end{itemize} This paper provides a foundation for further analysis of MIX-net reliability and reputations. Our model and reputation system are designed to be simple and easily extensible. Much work remains in a wide variety of directions before a reliable, secure, and ubiquitous remailer network can be put in place. \section*{Acknowledgements} We'd like to thank Nick Mathewson and Blake Meike for their help with the reputation system; Dave Andersen and Robert Zeithammer for interesting discussions concerning the network flow problem; Anna Lysyanskaya, Chris Laas, Nick Feamster, and Mark Waldman for various intelligent discussions; and our anonymous reviewers for their many useful comments. \bibliographystyle{plain} \bibliography{mix-acc2} \end{document}