Mix network
Encyclopedia
Digital mixes were invented by David Chaum
in 1981. Digital mixes create hard-to-trace communications by using a chain of proxy servers. Each message is encrypted to each proxy using public key cryptography; the resulting encryption is layered like a Russian doll (except that each "doll" is of the same size) with the message as the innermost layer. Each proxy server strips off its own layer of encryption to reveal where to send the message next. If all but one of the proxy servers are compromised by the tracer, untraceability can still be achieved against some weaker adversaries.
Some anonymous remailers (such as Mixmaster
) and onion routing
(including Tor
) are based on this idea.
There is another kind of mix net that consists of re-encryption operations. In these mixnets each mix node re-encrypts the set of received messages and the decryption is done in a single step. Homomorphic encryption
schemes allow that.
Participant A prepares a message for delivery to participant B by appending a random value to the message, sealing it with the addressee's public key 
, appending B’s address, and then sealing the result with the mix's public key 
.
M opens it with his private key, now he knows B’s address, and he sends
to B.
To accomplish this, the sender takes the mix’s public key (
), and uses it to encrypt an envelope containing a random string (
), 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 (
), 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 (
) is discarded.
A solution is for A to form an untraceable return address
where 
is its own real address, 
is a public one-time key chosen for the current occasion only, and 
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
to M, and M transforms it to 
.
This mix uses the string of bits
that it finds after decrypting the address part 
as a key to re-encrypt the message part 
. Only the addressee, A, can decrypt the resulting output because A created both 
and 
.
The additional key
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
B:
Reply message from B
A:
Where:
= B’s public key, 
= 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.
By routing through numerous mixes in the network, determining who is talking to who is made even more difficult.
David Chaum
David Chaum is the inventor of many cryptographic protocols, including blind signature schemes, commitment schemes, and digital cash. In 1982, Chaum founded the International Association for Cryptologic Research , which currently organizes academic conferences in cryptography research...
in 1981. Digital mixes create hard-to-trace communications by using a chain of proxy servers. Each message is encrypted to each proxy using public key cryptography; the resulting encryption is layered like a Russian doll (except that each "doll" is of the same size) with the message as the innermost layer. Each proxy server strips off its own layer of encryption to reveal where to send the message next. If all but one of the proxy servers are compromised by the tracer, untraceability can still be achieved against some weaker adversaries.
Some anonymous remailers (such as Mixmaster
Mixmaster anonymous remailer
Mixmaster is a Type II anonymous remailer which sends messages in fixed-size packets and reorders them, preventing anyone watching the messages go in and out of remailers from tracing them. Mixmaster was originally written by Lance Cottrell, and was maintained by Len Sassaman Peter Palfrader is the...
) and onion routing
Onion routing
Onion routing is a technique for anonymous communication over a computer network. Messages are repeatedly encrypted and then sent through several network nodes called onion routers. Like someone unpeeling an onion, each onion router removes a layer of encryption to uncover routing instructions, and...
(including Tor
Tor (anonymity network)
Tor is a system intended to enable online anonymity. Tor client software routes Internet traffic through a worldwide volunteer network of servers in order to conceal a user's location or usage from someone conducting network surveillance or traffic analysis...
) are based on this idea.
There is another kind of mix net that consists of re-encryption operations. In these mixnets each mix node re-encrypts the set of received messages and the decryption is done in a single step. Homomorphic encryption
Homomorphic encryption
Homomorphic encryption is a form of encryption where a specific algebraic operation performed on the plaintext is equivalent to another algebraic operation performed on the ciphertext. Depending on one's viewpoint, this can be seen as either a positive or negative attribute of the cryptosystem....
schemes allow that.
How it works
, appending B’s address, and then sealing the result with the mix's public key .M opens it with his private key, now he knows B’s address, and he sends
to B.Message format
To accomplish this, the sender takes the mix’s public key (
), and uses it to encrypt an envelope containing a random string (), 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 (), 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 () is discarded.Return Addresses
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
where is its own real address, is a public one-time key chosen for the current occasion only, and 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
to M, and M transforms it to .This mix uses the string of bits
that it finds after decrypting the address part as a key to re-encrypt the message part . Only the addressee, A, can decrypt the resulting output because A created both and .The additional key
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
B:Reply message from B
A:Where:
= B’s public key, = 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.
Goals
The purpose of a mix is to hide the correspondences between the items in its input and those in its output. (Note: if just one item is repeated in the input and allowed to be repeated in the output, then the correspondence is revealed for that item).By routing through numerous mixes in the network, determining who is talking to who is made even more difficult.
Further reading
- Email Security, Bruce SchneierBruce SchneierBruce Schneier is an American cryptographer, computer security specialist, and writer. He is the author of several books on general security topics, computer security and cryptography, and is the founder and chief technology officer of BT Managed Security Solutions, formerly Counterpane Internet...
(ISBN 0-471-05318-X) - Computer Privacy Handbook, Andre Bacard (ISBN 1-56609-171-3)