Mix network

${\displaystyle K_{m}(R1,K_{b}(R0,message),B)\longrightarrow (K_{b}(R0,message),B)}$

To accomplish this, the sender takes the mix's public key (${\displaystyle K_{m}}$), and uses it to encrypt an envelope containing a random string (${\displaystyle R1}$), a nested envelope addressed to the recipient, and the email address of the recipient (B). This nested envelope is encrypted with the recipient's public key (${\displaystyle K_{b}}$), and contains another random string (R0), along with the body of the message being sent. Upon receipt of the encrypted top-level envelope, the mix uses its secret key to open it. Inside, it finds the address of the recipient (B) and an encrypted message bound for B. The random string (${\displaystyle R1}$) is discarded.

${\displaystyle R0}$ is needed in the message in order to prevent an attacker from guessing messages. It is assumed that the attacker can observe all incoming and outgoing messages. If the random string is not used (i.e. only ${\displaystyle (K_{b}(message))}$ is sent to ${\displaystyle B}$) and an attacker has a good guess that the message ${\displaystyle message'}$ was sent, he can test whether ${\displaystyle K_{b}(message')=K_{b}(message)}$ holds, whereby he can learn the content of the message. By appending the random string ${\displaystyle R0}$ the attacker is prevented from performing this kind of attack; even if he should guess the correct message (i.e. ${\displaystyle message'=message}$ is true) he won't learn if he is right since he doesn't know the secret value ${\displaystyle R0}$. Practically, ${\displaystyle R0}$ functions as a salt.

What is needed now is a way for B to respond to A while still keeping the identity of A secret from B.

A solution is for A to form an untraceable return address ${\displaystyle K_{m}(S1,A),K_{x}}$ where ${\displaystyle A}$ is its own real address, ${\displaystyle K_{x}}$ is a public one-time key chosen for the current occasion only, and ${\displaystyle S1}$ is a key that will also act as a random string for purposes of sealing. Then, A can send this return address to B as part of a message sent by the techniques already described.

B sends ${\displaystyle K_{m}(S1,A),K_{x}(S0,response)}$ to M, and M transforms it to ${\displaystyle A,S1(K_{x}(S0,response))}$.

This mix uses the string of bits ${\displaystyle S1}$ that it finds after decrypting the address part ${\displaystyle K_{m}(S1,A)}$ as a key to re-encrypt the message part ${\displaystyle K_{x}(S0,response)}$. Only the addressee, A, can decrypt the resulting output because A created both ${\displaystyle S1}$ and ${\displaystyle K_{x}}$. The additional key ${\displaystyle K_{x}}$ assures that the mix cannot see the content of the reply-message.

The following indicates how B uses this untraceable return address to form a response to A, via a new kind of mix:

The message from A ${\displaystyle \longrightarrow }$ B:

${\displaystyle K_{m}(R1,K_{b}(R0,message,K_{m}(S1,A),K_{x}),B)\longrightarrow K_{b}(R0,message,K_{m}(S1,A),K_{x})}$

Reply message from B${\displaystyle \longrightarrow }$A:

${\displaystyle K_{m}(S1,A),K_{x}(S0,response)\longrightarrow A,S1(K_{x}(S0,response))}$

Where: ${\displaystyle K_{b}}$ = B’s public key, ${\displaystyle K_{m}}$ = the mix's public key.

A destination can reply to a source without sacrificing source anonymity. The reply message shares all of the performance and security benefits with the anonymous messages from source to destination.

An adversary can perform a passive attack by monitoring the traffic to and from the mix network. Analyzing the arrival times between multiple packets can reveal information. Since no changes are actively made to the packets, an attack like this is hard to detect. In a worst case of an attack, we assume that all the links of the network are observable by the adversary and the strategies and infrastructure of the mix network are known.[6]

A packet on an input link cannot be correlated to a packet on the output link based on information about the time the packet was received, the size of the packet, or the content of the packet. Packet correlation based on packet timing is prevented by batching and correlation based on content and packet size is prevented by encryption and packet padding, respectively.

Inter-packet intervals, that is, the time difference between observation of two consecutive packets on two network links, is used to infer if the links carry the same connection. The encryption and padding does not affect the inter-packet interval related to the same IP flow. Sequences of inter-packet interval vary greatly between connections, for example in web browsing, the traffic occurs in bursts. This fact can be used to identify a connection.

Active attacks can be performed by injecting bursts of packets that contain unique timing signatures into the targeted flow. The attacker can perform attacks to attempt to identify these packets on other network links. The attacker might not be able to create new packets due to the required knowledge of symmetric keys on all the subsequent mixes. Replay packets cannot be used either as they are easily preventable through hashing and caching.[6]

Large gaps can be created in the target flow, if the attacker drops large volumes of consecutive packets in the flow. For example, a simulation is run sending 3000 packets to the target flow, where the attacker drops the packets 1 second after the start of the flow. As the number of consecutive packets dropped increases, the effectiveness of defensive dropping decreases significantly. Introducing a large gap will almost always create a recognizable feature.

The attacker can create artificial bursts. This is done by creating a signature from artificial packets by holding them on a link for a certain period of time and then releasing them all at once. Defensive dropping provides no defense in this scenario and the attacker can identify the target flow. There are other defense measures that can be taken to prevent this attack. One such solution can be adaptive padding algorithms. The more the packets are delayed, the easier it is to identify the behavior and thus better defense can be observed.

An attacker may also look into other timing attacks other than inter-packet intervals. The attacker can actively modify packet streams to observe the changes caused in the network's behavior. Packets can be corrupted to force re-transmission of TCP packets, which the behavior is easily observable to reveal information.[8]

Assuming an adversary can see messages being sent and received into threshold mixes but they can't see the internal working of these mixes or what is sent by the same. If the adversary has left their own messages in respective mixes and they receive one of the two, they are able to determine the message sent and the corresponding sender. The adversary has to place their messages (active component) in the mix at any given time and the messages must remain there prior to a message being sent. This is not typically an active attack. Weaker adversaries can use this attack in combination with other attacks to cause more issues.

Mix networks derive security by changing order of messages they receive to avoid creating significant relation between the incoming and outgoing messages. Mixes create interference between messages. The interference puts bounds on the rate of information leak to an observer of the mix. In a mix of size n, an adversary observing input to and output from the mix has an uncertainty of order n in determining a match. A sleeper attack can take advantage of this. In a layered network of threshold mixes with a sleeper in each mix, there is a layer receiving inputs from senders and a second layer of mixes that forward messages to the final destination. From this, the attacker can learn the received message could not have come from the sender into any layer 1 mix that did not fire. There is a higher probability of matching the sent and received messages with these sleepers thus communication is not completely anonymous. Mixes may also be purely timed: they randomize the order of messages received in a particular interval and attach some of them with the mixes, forwarding them at the end of the interval despite what has been received in that interval. Messages that are available for mixinthat tg will interfere, but if no messages are available, there is no interference with received messages.[9]