Mix (network)

Basic functions of a mix: 1. Filter, 2. Collect, 3. Recode, 4. Re-sort the messages (colored arrows)

The concept of ( recoding ) mixes introduced by David Chaum in 1981 is used for anonymous communication within a network. Messages are not transmitted directly from the sender to the recipient, but rather passed through several intermediate stations (called mixes). The goal is to anonymize the communication relationship, which, depending on the underlying concept, leads to one of the following three characteristics:

• the recipient remains anonymous from the sender
• the sender remains anonymous from the recipient
• Sender and recipient remain anonymous to each other

The most important property, the protection of traffic information from outside third parties, is realized by all three concepts.

A mix plays the role of a message broker, similar to the function of a proxy server . He accepts messages and ensures that the messages then passed on by him cannot be related to the messages he has accepted. This additional function in turn distinguishes it from a normal proxy server.

Basic functions

So that there is no possibility for outsiders to relate messages between the input and output of a mix, this is also called bridging the mix, a mix must perform some basic functions on the messages:

• Deleting duplicates

An attacker in the electronic world always has the option of copying messages. Should two identical messages arrive at the mix, then two identical messages would also be forwarded by the mix. The mix would be bridged, since a relationship between the two identical input messages and the two identical output messages could clearly be established.

• Collecting news

Anonymity is only possible within a group of individuals. As a result, care must be taken to ensure that there is uncertainty about who a message came from. This is only possible if a sufficient number of messages have been received from different participants. The messages are then all processed together in one batch ( batch mode ). Alternatively, a message can be randomly selected for processing, while new messages are added continuously ( pool mode ).

• Recoding the messages

So that messages between the input and output of the mix cannot be related, they must also take on a different form. This is achieved by recoding using an encryption system . This means that outsiders can no longer make a simple bit-by-bit comparison between input messages and output messages.

• Rearranging the messages

It must also not be possible to infer the order in which the messages of the mix were received from the order in which the messages from the various participants were received. Therefore the messages have to be rearranged accordingly. As a result, such conclusions are no longer possible.

• further aspects

The greatest security is achieved when all messages run through the same mixes in the same order (mix cascade). The above recoding causes the shortening of the messages when going through the mixes. If no mix cascade can be guaranteed for performance or cost reasons, this shortening is problematic. An attacker could use the shortening to establish connections between incoming and outgoing messages in a mix. To counteract this, there are length-conforming procedures.

Limits

If implemented correctly using full functionality, a specific communication relationship can only be revealed through three options:

• All the mixes that a message went through work together.
• All other senders and receivers of the messages mixed simultaneously in all mixes work together.
• An attacker has unlimited computing power (attacker who is not limited in terms of complexity theory).

Recoding scheme

Recoding scheme for sender anonymity : messages shown as circles with an encryption wall

Recoding scheme for recipient anonymity: Anonymous return address shown as a square, messages shown as circles, each with an encryption wall

Recoding scheme for sender and recipient anonymity : Mix 2 is the familiar mix

The recoding of the messages is achieved by encryption or decryption, which means that the messages must either be decrypted again after receipt or encrypted before they are sent.

Sender anonymity

Some designations are required for a precise explanation:

• ${\displaystyle {\text{enc}}_{e}(m)}$… Encryption of the message with the public key ${\displaystyle m}$ ${\displaystyle e}$
• ${\displaystyle A_{i},\ e_{i}}$ … Address and public key of the mix ${\displaystyle i}$
• ${\displaystyle A_{E},\ e_{E}}$ … Address and public key of the recipient
• ${\displaystyle Z_{i}}$ ... random number

The random numbers are added to the plain text in order to achieve non-deterministic encryption. This is necessary so that messages with the same message content do not generate the same ciphertext and are therefore filtered by the mix. The random numbers can therefore be omitted for a simplified consideration. ${\displaystyle Z_{i}}$

The sender chooses a sequence of mixes through which he wants to send the message anonymously to the recipient , for example . It sends the following to the first mix: ${\displaystyle S}$ ${\displaystyle m}$ ${\displaystyle E}$ ${\displaystyle S\rightarrow {\text{Mix}}_{1}\rightarrow {\text{Mix}}_{2}\rightarrow E}$

${\displaystyle {\text{enc}}_{e_{1}}\left(Z_{1},A_{2},{\text{enc}}_{e_{2}}\left(Z_{2},A_{E},{\text{enc}}_{e_{E}}\left(m\right)\right)\right)}$

The first mix decrypts this with its private key . This gives him the address of the next mix. The random number is discarded. The first mix sends the following to the second mix: ${\displaystyle d_{1}}$ ${\displaystyle A_{2}}$

${\displaystyle {\text{enc}}_{e_{2}}\left(Z_{2},A_{E},{\text{enc}}_{e_{E}}\left(m\right)\right)}$

This decrypts again and discards the random number. This can be continued at will. The last mix gets the address of the recipient. He then sends it to. The recipient can decrypt the message with his private key . If the recipient does not have a public key, the message from the last mix must be transmitted unencrypted to the recipient. ${\displaystyle A_{E}}$ ${\displaystyle {\text{enc}}_{e_{E}}\left(m\right)}$ ${\displaystyle d_{E}}$

In general, a sender who wants to remain anonymous encrypts his message recursively as follows:

${\displaystyle m_{n+1}={\text{enc}}_{e_{E}}\left(m\right)}$

${\displaystyle m_{i}={\text{enc}}_{e_{i}}\left(Z_{i},A_{i+1},m_{i+1}\right){\text{ mit }}i=1,\dots ,n}$

Recipient anonymity

If a recipient wants to be reachable anonymously, he must first inform the sender how he should contact him. This information is known as the anonymous return address . The sender does not know which mixes the recipient has selected for transmission of the message. He only knows the first mix. After the recipient has chosen a sequence of mixes, he can send the anonymous return address to the sender. Assuming the recipient dials as above , he sends to the sender: ${\displaystyle S\rightarrow {\text{Mix}}_{1}\rightarrow {\text{Mix}}_{2}\rightarrow E}$

${\displaystyle \left(k_{S},A_{1},{\text{enc}}_{e_{1}}\left(k_{1},A_{2},{\text{enc}}_{e_{2}}\left(k_{2},A_{E}\right)\right)\right)}$

The are symmetric keys , which can be used when sending the message from sender to receiver, from the mixes for encryption. The recipient knows these keys. He receives and can decipher this. The use of asymmetric keys, as in the case of sender anonymity, is not possible here because the sender does not know the order of the mixes in this case. ${\displaystyle k_{j}}$ ${\displaystyle {\text{enc}}_{k_{2}}\left({\text{enc}}_{k_{1}}\left({\text{enc}}_{k_{S}}\left(m\right)\right)\right)}$

In general, the anonymous return address is recursively structured as follows: ${\displaystyle R_{S}}$

${\displaystyle R_{n}={\text{enc}}_{e_{n}}\left(k_{n},A_{E}\right)}$

${\displaystyle R_{j}={\text{enc}}_{e_{j}}\left(k_{j},A_{j+1},R_{j+1}\right){\text{ mit }}j=1,\dots ,n-1}$

${\displaystyle R_{S}=\left(k_{S},A_{1},R_{1}\right)}$

The recipient transmits the anonymous return address to the sender using the recoding scheme for sender anonymity. So it is

• the recipient of the message is the same as the sender of the anonymous return address and
• the sender of the message is the recipient of the anonymous return address.

The terms sender and recipient always refer to the message. The first mix is ​​always the mix on the sender side, while the last mix is ​​the one on the receiver side. In the case of the two mixes, the recipient would send the following to the last mix:

${\displaystyle {\text{enc}}_{e_{2}}\left(Z_{2},A_{1},{\text{enc}}_{e_{1}}\left(Z_{1},A_{S},{\text{enc}}_{e_{S}}\left(\underbrace {\left(k_{S},A_{1},{\text{enc}}_{e_{1}}\left(k_{1},A_{2},{\text{enc}}_{e_{2}}\left(k_{2},A_{E}\right)\right)\right)} _{\mathrm {anonyme\ R{\ddot {u}}ckadresse} }\right)\right)\right)}$

The sender now knows and . To get the message across to the recipient, he sends the following to the first mix: ${\displaystyle k_{S},\ A_{1}}$ ${\displaystyle R_{1}}$ ${\displaystyle m}$

${\displaystyle \left(R_{1},{\text{enc}}_{k_{S}}\left(m\right)\right)}$

The first mix decoded

${\displaystyle R_{1}={\text{enc}}_{e_{1}}\left(k_{1},A_{2},R_{2}\right)}$

and thereby receives and . He sends ${\displaystyle k_{1},\ A_{2}}$ ${\displaystyle R_{2}}$

${\displaystyle \left(R_{2},{\text{enc}}_{k_{1}}\left({\text{enc}}_{k_{S}}\left(m\right)\right)\right)}$

to the mix with the address . This continues until the recipient receives the message. ${\displaystyle A_{2}}$

In this case, no random numbers need to be encrypted, as the randomly selected keys are already included. The recipient knows the key because he chose it himself. As already described, he receives ${\displaystyle k_{j}}$ ${\displaystyle k_{j}}$

${\displaystyle {\text{enc}}_{k_{2}}\left({\text{enc}}_{k_{1}}\left({\text{enc}}_{k_{S}}\left(m\right)\right)\right)}$

and still has to decipher this.

Sender and recipient anonymity

In order to maintain anonymity on both sides, the recoding schemes for sender and recipient are combined. A mix in the middle serves as a turning point. The recipient sends this mix an anonymous return address using the recipient anonymity scheme. The anonymous return address is temporarily stored by the mix until the sender sends its message to this mix according to the sender anonymity scheme. This sends the message to the recipient using the anonymous return address. In order to ask the broadcaster to send a message, the mix in the middle could broadcast a request to all possible broadcasters.

In practice, the schemes described become a little more complicated, since one wants to use faster symmetric encryption for the parts in which asymmetric cryptography is used. So-called hybrid cryptosystems are the solution .

Mix channels

The system described is mainly suitable for sending individual messages of a given length (blocks). If longer data streams are to be transmitted, the concept of hybrid encryption is expanded: The symmetric keys exchanged between the mixes are not only used for the encryption of a single block, but also for all subsequent blocks. If a mix channel is to be established between sender and receiver, the sender must send a channel setup message, which has the task of distributing the symmetrical keys between the mixes. After the data transfer has ended, the channels are cleared down again with a channel clear- down message . There is a practical problem here: the channels must be set up and dismantled again within an anonymity group at the same time, since an observer of the network could otherwise bridge all mixes based on the point in time at which the channel was set up or dismantled. This problem can be circumvented by introducing a system clock and dismantling all channels with each clock and building them up again immediately if necessary ( time slice channels ).

Applications

Within real-time systems, e.g. B. Tor or JAP , which can be used for surfing the Internet, a particular problem arises: collecting messages is hardly feasible in practice. You would have to wait a long time to collect messages from as many broadcasters as possible. However, this contradicts the functionality of these systems, which aim for the shortest possible response times. As a result, the collecting step is completely omitted or kept extremely short in this type of system. Accordingly, there is also largely no need to rearrange the messages, since only individual messages or very small message groups are used. This results in restrictions on the security of these processes. The mixes can be bypassed for an attacker using the methods mentioned above in the individual steps.

The deletion of duplicates, also known as replay detection, is often not carried out in real-time systems. The reason is that a database of all messages that have already been processed must exist for such a recognition. Even if only hash values ​​of messages are stored here, these databases still grow very quickly. In addition to the required storage space, searches in these databases also take a correspondingly long time and require computing power. Time stamping procedures can help here, however, so that the databases only have to be kept for certain periods of time. Nevertheless, in real-time systems, often only the recoding step is carried out. This makes these systems easy to attack.

Protection from the mix operator

In addition to the sender of a message, the mix operator can of course assign all incoming and outgoing messages himself, since all the steps in the mix are transparent to him. For this reason, several of these mixes are used one after the other, which are controlled by different operators. The hope is that these different mix operators will not all work together. Otherwise, they could jointly uncover all message relationships as well. However, as soon as a mix operator does not cooperate, anonymity is guaranteed.

Two different methods have become established for this: the onion routing based on free routing and the use of fixed mix cascades. Both procedures differ in terms of the attacker models on which they are based. That is why they are difficult to compare, especially with regard to the practical protection of anonymity.

literature

• David Chaum: Untraceable electronic mail, return addresses, and digital pseudonyms In Communications of the ACM 4 (2), February 1981. (PDF; 420 kB)

Individual evidence

1. ^ Elke Franz, A. Graubner, A. Jerichow, Andreas Pfitzmann: Comparison of Commitment Schemes Used in Mix-Mediated Anonymous Communication for Preventing Pool-Mode Attacks . In: Information Security and Privacy . 1438, 1998.  ( Page no longer available , search in web archives )  Info: The link was automatically marked as defective. Please check the link according to the instructions and then remove this notice.  
2. ↑ ^{a b} Elke Franz, Anja Jerichow, Andreas Pfitzmann: Systematization and modeling of mixing . (PS.GZ) In: Proceedings of the GI symposium for reliable IT systems . 1997, pp. 171-190. Retrieved August 12, 2010.
3. ^ ^{A b} Jan Müller: Anonymous signaling in communication networks (PDF) pp. 19–23. February 28, 1997. Retrieved August 12, 2010.
4. ^ Andreas Pfitzmann, Birgit Pfitzmann, Michael Waidner: Telephone MIXe . (PS.GZ) In: Data protection and data security . 1989, pp. 605-622. Retrieved August 17, 2010.