%% 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 %% Proceedings (finished version) due May 24 \documentclass{llncs} \usepackage{epsfig} %\newif\ifpdf %\ifx\pdfoutput\undefined % \pdffalse %\else % \pdfoutput=1 % \pdftrue %\fi \begin{document} %% Use dvipdfm instead. --DH %\ifpdf % \pdfcompresslevel=9 % \pdfpagewidth=\the\paperwidth % \pdfpageheight=\the\paperheight %\fi \title{A Reputation System to Increase MIX-net Reliability} \author{Roger Dingledine\inst{1}, Michael J. Freedman\inst{2}, David Hopwood\inst{3}, 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{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. \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. % XXX the above sentence can be greatly compressed This unreliability directly affects the number of people using the remailer network and their traffic patterns, which reduces the anonymity these networks provide. One approach to increasing reliability 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 it. 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). Currently deployed remailer reputation systems (better known as \emph{remailer statistics}) collect data independently and are treated as trusted third parties by client software. Reliable statistics servers are good targets for adversaries. Furthermore, these statistics often only measure secondary properties of the MIX-net servers, such as up-time. %XXX does the above sentence need to be there? We describe related MIX-nets and current statistics systems in Section \ref{sec:related}. Section \ref{sec:mix-design} presents 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. Section \ref{sec:reputation} introduces 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 a scorer will be less disruptive than loss of a statistics server in current reputation systems. We stress that this work does not fully solve the problem of MIX reliability. In presenting a simple reputation system, we hope to stimulate further research on reputation systems and modelling the increased reliability they provide. \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 (or MIX nodes), each of which is associated with a public key. Each MIX receives encrypted messages, which 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. That is, the \emph{view} of a passive adversary gives negliglible advantage over guessing in linking messages with their senders and receivers. Current research directions on MIX-nets 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}. Previous work primarily investigates 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. Robustness has been achieved primarily via zero-knowledge proofs of correct computation. 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. Desmedt and Kurosawa's alternate approach \cite{desmedt} requires many participating servers. Abe's MIX \cite{abe} provides \emph{universal verifiability} in which any observer can determine after the fact whether a MIX cheated, 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. 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 the problems surrounding the {\tt anon.penet.fi} service \cite{helsingius}, and by theoretical work on MIXes. Hughes wrote the first cypherpunks anonymous remailer \cite{remailer-history}; Finney followed closely with a collection of scripts which used Phil Zimmermann's PGP to encrypt and decrypt remailed messages. 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). \subsection{Remailer Statistics} Levien's \emph{statistics pages} \cite{levien} track 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. Such \emph{reputation systems} improve 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{Three Approaches to MIX-Net Reliability} We can build protocols which give specific guarantees of robustness and reliability, and prove theorems about these protocols in suitably specified adversary models. These results may be quite strong, e.g. ``this distributed MIX delivers correctly if no more than half of its participating servers are corrupt,'' yet the resulting protocols may be complicated and inefficient. % Converging on the ``right'' protocol may be %tricky; even a small misstep in a proof may invalidate all robustness %results. 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. Unlike the reliability via protocol approach, we are not likely to prove strong theorems. The goal of reputation is to make the system ``better'' without guaranteeing perfection. A third option is to create economic incentives for MIXes 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 MIXes for consistent reliability and performance in the Freedom network \cite{freedom2}. %% Cite Back? -DM XXX % 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. Reliability via protocol is the most well-studied approach, while reliability via reputations in the form of Levien statistics is the most widely used. Our work combines the two approaches: we modify the MIX-net protocol to support easy tallying of MIX failures and then specify a suitable reputation system. \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 provide a receipt for each message they receive. %The receipt represents an agreement to process the message. The sender Alice can query a MIX to see if it has proof that it attempted to follow the protocol. But the MIX might refuse to provide Alice a receipt for a particular message either because it failed to send the message, or because it was unable to obtain a receipt from the next hop. We solve the problem of pinpointing failures 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. Each witness that obtains a valid receipt sends it back to $N_i$. Any witness that doesn't will be convinced that $N_{i+1}$ is unreliable, and provides $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 node on the path failed. The above argument does not explicitly consider the possibility that several consecutive MIXes are controlled by an adversary; we cover that in Section \ref{subsec:proving}. %XXX can we remove the above paragraph, since we cover it elsewhere? While witnesses must be trusted to respond to requests, they 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 proofs of sender and receiver unlinkability that apply to traditional MIX-net protocols still hold. \subsection{Cryptographic Algorithms} %% (semantically secure => non-malleable) under CCA2, so no need to say that. We require 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$. The encryption notation explicitly includes the random value: $E_i^r(M)$ means the encryption of message $M$ and random value $r$ under the public key of $N_i$. We assume 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 notation $Sign_i(M)$ means 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 are known to all parties. Message recipients are treated as MIXes. \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}$. Alice 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, 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 that caused the failure: \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} \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. A message received by $N_i$ in the period ending at time $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 $N_{i+1}$ in the next period. 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 (within $T_{\epsilon}$ of the global time). Sending a message over a network is assumed to take $T_{comm}$ in the worst case. Therefore, a party needing to send a message by time $t$ should send 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. A party expecting a message by time $t$ should allow it to be received as late as $t + T_{\epsilon}$ according to its local clock, since its clock may be fast. The protocol requires several system-wide time constants: $T_{response}$ is the time that a MIX is allowed between receiving a message and providing a receipt. $T_{margin}$ is the length of time before the deadline at which a MIX will attempt to send a message via the witnesses, if it has not been able to obtain a receipt directly from the next node. $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 the period ending at $t$, it need only provide it if the receipt has timestamp $t - T_{retain}$ or later. This value determines the length of time for which failure claims can be directly verified. \begin{figure}[htc] \begin{center} \leavevmode \epsfbox{timing.1} \caption{Timing example} \end{center} \end{figure} Figure 2 depicts an example time line (showing only global time): \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} %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. \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 Alice's current local time, 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\newline $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 {\tt Hop-send}$(N_1, M_1, Deadline_1)$ below to resend $M_1$ to $N_1$. \end{enumerate} If 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 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\newline $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} \item Let $W$ be a set of witnesses. \item Send ``Witness: $N_{dest}, Message, Deadline$'' to each $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\newline $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. %XXX similarly, can condense 'now'? \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. %XXX similarly, can condense 'now'? \item Try to send $Message$ to $N_{dest}$ directly, waiting for a receipt. \item If a receipt $Rcpt$ is received, check that\newline $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}$, $N_{dest}$ has failed; send back a 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 to any chosen verifier (call him Victor) a claim that a MIX failed to deliver a message. Section \ref{sec:reputation} describes Victor's duty in our reputation system. Suppose that $N_i$ ($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$. 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 $M_{i+1}$ was not 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 ``I blame $N_i$, claim: $r_i, N_{i+1}, M_{i+1}, Deadline_i, Rcpt_i$'', which Victor verifies: \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\newline $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 $Ver_{i+1}(Rcpt_{i+1}, $``Receipt: $M_{i+1}, Timestamp$''$) = 1$\newline 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:} $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, assuming $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}$ might be controlled by the adversary; in this 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. 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 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. %%%XXX actually, we don't do that anymore? should we briefly here? -RD %% 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:} 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 could only hurt its own reputation via 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 MIX she controls.} \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})$, and 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$.\newline 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.} it will be exonerated. \end{itemize} A node could also be falsely accused of failure 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. Many MIX-net protocols require MIXes to refuse to pass on a message if it is a {\em replay} --- a message the MIX had already received within a given time period (see \cite{babel} for a rationale). We prevent MIXes from losing reputation because of this behavior as follows. 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}$. A MIX that receives a replayed message should delay the expiration of the earlier receipt or statements for a further $T_{retain}$ periods. %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} If Alice is posting to a public forum like Usenet, she (and any verifier) can see whether the message was posted correctly. Otherwise, if the MIX-net supports reply blocks or another method for two-way communication, Bob's software can immediately send an {\em end-to-end receipt} back through the MIX-net to Alice. %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, Alice should 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. \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 (especially if users trust an arbitrary set of witnesses chosen by a sending node) make false statements in order to frame a MIX that has not in fact failed. 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, that would be considered {\em sufficient} for the purposes of {\tt Verify-claim}. Specifying a fixed (or even slowly changing) group of witnesses is not ideal, but if the messages sent to this group are also published, other parties can duplicate their actions and gain confidence in their behavior. \section{Reputation Systems} \label{sec:reputation} Reputations have been suggested as a means of improving MIX-net reliability \cite{timmay,levien}. In layering on a reputation system, we add two more agents to the system. \emph{Raters} 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} tally observations from raters and make these tallies (or \emph{scores}) available. For simplicity, we choose to give the scorer the duties of verifier and witness as well. As in \cite{potato}, sender software must be configurable to automatically use scores. Any user of the MIX-net must be able to contribute \emph{ratings}. The scoring system must be verifiable: scorers can determine the credibility of ratings, and other users can verify that scorers are tallying ratings correctly. 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. While achieving all of these goals, the system must also maintain the level of anonymity provided by the MIX-net. \subsection{Reputation System Overview} We introduce a set of scorers, each named Sally. Each Sally keeps her own database of performance scores for MIXes. She receives, verifies, and tallies failure claims. Sally also sends test messages to distinguish reliable MIXes (few delivery failures due to good performance) from new MIXes (few delivery failures because nobody has tried them yet). % %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). If we simply count the number of messages that each MIX drops, an effective attack would be to constantly add new unreliable MIXes. Therefore scores include both a count of negative ratings, and also a ``minimum number of positive ratings'' requirement, which is a threshold configurable on the client side. Client software downloads Sally's reputation database, and allows the user to specify parameters when selecting acceptable MIX paths, such as ``expected success of transmission''. %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. If our assumptions in Section \ref{subsec:proving} 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 is exactly the point where the MIX demonstrates that it is unreliable. Causing MIXes to lose reputation in the face of \emph{successful} flooding is consistent with our scoring system goals: the scoring system measures reliability and capabilities, not intent. \subsection{Increasing Confidence in Positive Ratings} \label{sec:rep-solutions} An adversary can easily fake a positive rating by building a message which uses a MIX path entirely owned by him, and then generating a transcript which ``proves'' successful transmission. % %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. We need to make positive ratings actually reflect a MIX's ability to successfully deliver Alice's message in the future. 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$. 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. 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, Our solution emphasizes simplicity and ease of implementation and evaluation. 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 they are unbiased ratings. MIXes that 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. %% I think we definitely need to make this point. --DH It may 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. %%Agreed, this is sub-optimal. Leave it out. -rd %MIXes may provide preferential service to witnesses, just as %restaurants may provide preferential service to restaurant critics. %Witnesses may choose to send %their messages via one hop of the MIX-net as well, to hide their identity; %this complicates the protocol and timing, though. %% I don't agree. --DH Sally should expire her memories of transactions after a certain amount of time so that old failures 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 MIXes that have some minimum number of positive ratings. Out of this pool, she weights the MIXes she uses for her path based on the number of verified delivery failures observed for this MIX. This system reacts quickly to a decrease in reliability of a MIX. A MIX with high reputation will have many users routing messages through it. if it suddenly stops delivering messages, these users will quickly deliver a series of negative ratings. This negative feedback process serves to stabilize the system so scores reflect reality. For redundancy and to allow verifiability of scorers, Alice can remember which mails had a corresponding end-to-end receipt, tally her transactions, and build her own score table in which she is confident of both the positive ratings and the negative ratings. Periodically comparing her score tables with those of the available Sally's allows Alice to ``test the waters'' herself and weakens the trust requirements on scorers. 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} \label{sec:traffic} 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 also introduces new attacks. Eve could 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 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; this system tuning will be extremely complex and difficult. On the other hand, we may 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 gets through. These re-sends of the same message offer more information to traffic analyzers. 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{Conclusion and Future Directions} \label{sec:conclusion} We have described a reputation system for remailer networks, based on a MIX-net design that employs receipts for intermediate messages. There are a number of directions for future research: \begin{itemize} \item Create a ``reliability metric'' and an accompanying model which will allow us to quantify the behavior of our reputation system. For instance, we might consider as a metric the expected probability of a message making it from sender to receiver. Then we would calculate reliability with and without the reputation system in place and see whether reliability improves. 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 defend against the selective DoS attack described in Section \ref{sec:traffic}? How can we protect against adversaries who want their MIXes listed as most reliable? \item Can we make a reputation system that is both efficient and universally verifiable? Currently, only Alice can 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 remaining practical? Can we extend this so that anyone can detect a failed MIX? \end{itemize} This paper provides a foundation for further analysis of MIX-net reliability and reputations. Our reputation system is 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 thank Nick Mathewson and Blake Meike for help with the reputation system; Nick Feamster, Kevin Fu, Chris Laas, Anna Lysyanskaya, and Marc Waldman for discussions; and our anonymous reviewers for many useful comments. \bibliographystyle{plain} \bibliography{mix-acc} \end{document}