\newcommand{\NODE}[1]{ $node_{#1}$ } \section{Anonymity networks} \label{sec:anon} \subsection{The onion router} We can't talk about anonymity networks without talking about The Onion Router\cite{goldschlag1999onion} or TOR for short. It's a free software project that provides access to an anonymity network based on Onion Routing. Tor works by users selecting a path trough the tor network consisting of 3 nodes. When a user wants to send a message it has to encrypt its message with the key of the last node in the network. This yields a result, which needs to be encrypted with the key of the middle node. This results needs to be encrypted with the key of the first node and then can be send out the first node. The first node can peel off the outer layer of encryption and send it to the second node which in turn can peel of the new outer layer. The last node removes the last layer of encryption and reveals the plaintext. This plaintext can be sent to the original destination. This simplified view of TOR reveals that the sender of a certain message remains anonymous so long as at least one of your 3 nodes is not compromised. And you use End to End encryption because the last node will see your plaintext. Unfortunately some information is leaked, and this is exploited by a correlation attack\cite{Johnson:2013:UGR:2508859.2516651}. This is an attack where the attacker sees incoming traffic of your first node and the outgoing traffic of the last node. It can then try to correlate the entry times, exit times, origin, destination and size of the packets. An attacker can use this data to correlate a packet entering and exiting the network and therefore link a user and a destination with a certain probability. Therefore de-anonymizing the traffic. This attack is highly probabilistic, but could flag users for further targeted investigation. Therefore we really want to prevent this attack from being possible. This attack would be mitigated by the another type of anonymity network called a Mix net. \subsection{Mix networks} The first mix network was proposed and developed by David Chaum \cite{chaum1981untraceable}. this mix network consists of $N$ nodes. Each of these nodes have a public/private key pair. Users that want to use the mix network have to package their message as follows, it prepends the identifier of the destination to the message and encrypts it with the public key of \NODE{N-1}. It then prepends the identifier of \NODE{N-1} and encrypts it with the public key of \NODE{N-2}. The client does this for all the nodes in the network working backwards and sends it to the first node. This first node can now unpack the message it receives and retrieve an identifier for the next node and a encrypted message which only \NODE{N+1} can decrypt. The last node can decrypt the original message which contains its destination and sends it the end user. Up until this point this is roughly how the TOR anonymity network operates, but there is a difference. The first node in the \cmix network does not immediately send out the messages it receives. The node first collects up to $P$ messages. When this threshold is achieved it will decrypt all the messages and randomly shuffle the order they were in, otherwise known as mixing. It then sends them to the next node. Another subtle difference is that each message within one mix operation should have the same length, However it is possible to choose a large enough message size and pad all the messages to this length. This mixing and delaying in the first node causes an arbitrary amount of delay on client connection messages. Furthermore, an outsider analyzing the input and output of the nodes cannot see which packet went where in the mixing operation. So it cannot keep track of a specific message. This is what grants the additional anonymity within mix networks, as it mitigates the correlation attack possible on TOR. The introduction of Re-encryption mix nets by Park et all \cite{park1993efficient} introduces the usage of ElGamal encryption in mix nets. Using it's homomorphic properties to no longer de-encrypt each incoming message but rather just re-encrypt the message which makes it faster to run. It also has the effect that the ciphertext no longer lengthens in the order of the amount of nodes in the mix network. Which does happen in the classic Chaum mix network and in TOR. The network operates by each node having a public and private ElGamal key. It publishes its public key and a user can use all of the public keys of all of the nodes en encrypt his message. Each node can re-encrypt the message with it's private key. After the last nodes successfully re-encrypts the value the plain text is revealed. In the original paper this is used as a voting scheme and therefore no mention is made of a Receiver as it just needs to aggregate in one place. But is of course extensible to support sending messages to specific recipients. A major downside of these classic mix network is the amount of public key operations the client and nodes need to do when sending single message. This may not be an issue on modern day desktop computers and or low volume traffic, but it is an issue for mobile phones' battery life and low-power devices. This is were the precomputation and use of ElGamals homomorphic properties come in to play. \section{\cmix} \label{sec:cmix} \cmix is a new anonymity mix network\cite{cMix}. Just like any other mix network it aims to provide anonymity by hiding timing information of messages. This means hiding the difference in time between a message leaving the client and arriving at its destination. A \cmix network is a fixed network consisting of $N$ nodes. This means there is a fixed network order and all clients know which computer represents each node in the network. It uses ElGamal encryption. And it relies heavily on the homomorphic properties of ElGamal. The \cmix network operates in 3 phases. Initialization, precomputation and realtime. During the initialization phase only some key setup is done. This is the only time clients need to do public key operations as they have to establish a shared key with every node using Diffie-Hellman key exchange. This is why all communications between the nodes and from client to node have to be authenticated. One way to accomplish this is by using SSL connections for all communications within the network. Remember that the focus of this network is not encrypted traffic, recall that the last nodes sees all the plaintexts, but rather to hide timing information from an attacker. \subsection{Initialization phase} During the initialization phase the first node sends his public key to the next node, which multiplies his own public key with the value he received and sends it to the next. The last node sends it back to the first node which stores this final value and sends it on the next node which also stores this value. Now all nodes have the product of all the nodes' public keys. $$ E = \prod_N d_i $$ \vspace{-1em} where: \begin{itemize}[label=] \item $d_i$ is the public key of node $i$ \item $E$ is the shared key between nodes \end{itemize} When a client connects, the client agrees upon a key using Diffie-Hellman key-exchange with each node. These keys will be used to send messages into the network, which will happen during the realtime phase $$ K_c = \{k_0, k_1,\ldots, k_{N-1}\} $$ \vspace{-1em} where: \begin{itemize}[label=] \item $k_i$ shared key between client and node $i$ \item $K_c$ The vector of Keys stored by the client \end{itemize} During any part of the protocol a client may send a message into the network. When using multiplicative group ElGamal, It does this by multiplying a plaintext message with the shared keys in $K_c$. Then it sends this result to the first node. When using elliptic curve however the group elements, such as messages and shared keys, and need to be added. Note that $\cdot$ means combining 2 values, meaning multiplication for multiplicative groups and addition for elliptic curves. For now as the original paper referenced multiplicative group the rest of this description of \cmix will refer to this operation as multiplication. \begin{equation} Message = M \cdot k_0 \cdot k_1 \cdot ... \cdot k_{N-1} \label{form:message} \end{equation} \vspace{-1em} where: \begin{itemize}[label=] \item $K_c$ The shared key between client and node $i$ \item $M$ The plaintext message \end{itemize} \subsection{Precomputation phase} The precomputation phase can be started as soon as $P$, the minimum number of messages to have accumulated in \NODE{0}, is known. The first node generates $P$ random values $R$ and $S$. $R$ is a vector of $P$ values as is $S$. When encrypting or multiplying these vectors the component-wise encryption or multiplication is implied. It also generates a random permutation function $\pi$ which can randomly shuffle $P$ messages. The precomputation can be split up into 3 phases. In the first phase the first node encrypts his $R$ with the key $E$ and sends it to the $node_{next}$. $Node_{next}$ also generates $P$ random values $R$ and $S$ and encrypts his $R$ with the key $E$. $Node_{next}$ multiplies it's encryption result with the values received by the first node, and by the homomorphic encryption property of ElGamal the result of this multiplication is the encryption of the multiplication of the two original $R$ vectors. It then sends the result of the multiplication to the next node which also encrypts his $R$ and multiplies it with his input and sends it on. $$ \mathcal{E}_E(R_0 \cdot R_1) = \mathcal{E}_S(R_0) \cdot \mathcal{E}_S(R_1) $$ \vspace{-1em} where: \begin{itemize}[label=] \item $\mathcal{E}_E$ is ElGamal encryption under key $E$ \item $R_i$ is the R vector of node $i$ \end{itemize} Whenever the result reaches the first node again phase 2 of the precomputation starts. this is a mix phase. It uses its permutation function $\pi$ on the incoming vector of values and multiplies that result with the encryption of $S$. It sends its result to the next node which does the same. The last node gets the following result. \begin{align} &\mathcal{E}_E( \nonumber \\ &\hspace{1em}\pi_{N-1}( ... \nonumber \\ &\hspace{2em}\pi_{1}( \nonumber \\ &\hspace{3em}\pi_{0}(R_{0} \cdot ... \cdot R_{N-1}) \cdot S_0 \nonumber \\ &\hspace{2em}) \cdot S_1 \nonumber \\ &\hspace{1em} ... ) \cdot S_{N-1} \label{form:EPiRS} \nonumber \\ &) \end{align} \vspace{-1em} where: \begin{itemize}[label=] \item $\mathcal{E}_E$ is ElGamal encryption under key $E$ \item $R_i$ is the R vector of node $i$ \item $S_i$ is the S vector of node $i$ \item $\pi_i$ is the permutation function of node $i$ \end{itemize} The third part of the precomputation, is about decrypting this final value. Each node can perform part of the decryption with his private key part of $E$. in combination with the encryption specific random value which is used in ElGamal it is called the decryption share. When it multiplies the above value with the decryption share you remove your part of the encryption. So when passing your result to the next node each node can multiply it's decryption share with their input. After the last node performs this action the last nodes has the decrypted value of equation \eqref{form:EPiRS}. It stores this for use in the realtime phase. \subsection{Realtime phase} \label{sec:realpre} Whenever the first node received $P$ messages as described in formula \eqref{form:message}, and the precomputation has ended, the realtime phase can begin. The realtime phase can also be split into 3 different stages. In the first stage each node multiplies the message with the inverse of the key it agreed upon in the initialization phase. It then multiplies that result with $r_i$, where $i$ is the position of the message in the buffer, replacing $K_c$ with the corresponding value in $R$. The result is not yet permuted so the messages stay in the same place. The result gets passed to the next node which does the same steps. So for all the messages in the input we do. \[ M_{out} = M_{in} \cdot K_{ci}^{-1} \cdot R_j \] \vspace{-1em} where: \begin{itemize}[label=] \item $M_{in}$ is one of the input messages \item $R_j$ the corresponding r of $M_{in}s$ position \item $K_{ci}$ Is the shared key of $M_{in}s$ position \end{itemize} The second phase is similar to the second phase of the precomputation, A node takes the message buffer, swaps around the messages according to its permutation function $\pi$ it then multiplies it by $S$, each node does this step. \begin{align} &M_{out} = \pi_{N-1}( \ldots \nonumber \\ &\hspace{1em}\pi_{1}( \nonumber \\ &\hspace{2em}\pi_{0}(R_{0} \cdot \ldots \cdot R_{N-1} \cdot M_{in}) \cdot S_0 \nonumber \\ &\hspace{1em}) \cdot S_1 \nonumber \\ & \ldots ) \cdot S_{N-1} \label{form:PiMRS} \nonumber \\ \end{align} \vspace{-1em} where: \begin{itemize}[label=] \item $\pi_i$ is the permutation function of node $i$ \item $R_i$ is the R vector of node $i$ \item $S_i$ is the S vector of node $i$ \end{itemize} The last phase is to remove the R and S vectors from the input. The last node stored decryption of formula \ref{form:EPiRS}. The last node calculates the inverse of this group element and multiplies it with the result of \ref{form:PiMRS}. This will cancel out all permuted R and S values, and the last node will be left with $M$. Very critical to see is that during the realtime phase no public-key cryptography is being used, only some multiplications. And the clients, outside of the initialization phase, never have to do any public-key cryptography. It is also possible for client and servers to update the shared keys $K_c$ using the old key as a seed. So in theory a client only needs to do the key agreement once per network. \subsection{Advantages of \cmix} The fact that \cmix minimizes the amount of public-key cryptographic operations for the client, makes it more appealing for low power devices. So devices that cannot draw high amounts of power all the time due to battery constrains or NFC power limits. Mobile phones of which you want to conserve battery power. Another advantage is that in theory the latency of the actual messages during the realtime phase should be lower than other mix networks. Again due to the lack of public-key cryptography during this phase.