mixnet

Mixnet over CloudProxy

A mixnet router facilitates anonymous communications among a set of peers. Alice wants to send Msg to Bob; she encrypts, authenticates, and sends the message (Msg, Bob) to Molly, a mixnet router. Molly waits until she has n-1 more messages from n-1 other peers, then transmits the messages to their respective destinations simultaneously, thus anonymizing Alice among a set of n peers. Such a service is only useful if Molly can be trusted to not divulge the link (Alice, Bob). This document specifies a simple mixnet built on the CloudProxy platform that reduces this trust to the knowledge of a public key and trust in the owner of that key.

Security goals and threat model

There are three principals in our protocol: the sender, recipient, and the policy owner. Our goal is to design a protocol that provides anonymity for senders without requiring the recipient to execute the protocol. The policy owner controls the root policy private key that is used to attest to the instantiation of mixnet routers using the CloudProxy platform. CloudProxy exposes the code to the users, as well as the operating system in which it is running. To instantiate a mixnet router, a TPM coupled with the hardware platform generates a public key, which is attested to by the policy owner by signing it with the private policy key. When the machine boots, the OS is measured and generates a private/public key pair, which is attested to by the TPM; finally, the mixnet code itself is measured and generates a private/public key pair, which is attested to by the OS. Hence, trust in the mixnet routers to faithfully carry out the protocol is reduced to correct provisioning of the policy key.

We consider a global passive adversary who observes all communications between senders and mixnet routers, mixnet routers and other mixnet routers, and mixnet routers and recipients. The adversary may also send messages on channels it observes. Since the service is anonymous, the adversary is allowed to control any number of senders or recipients. The effect is that the state of that peer is exposed, including any and all cryptographic keys. We assume that the policy key was correctly provisioned; if the code implements the protocol correctly and is properly isolated during its execution, we claim this precludes the possibility of exposing a router’s state. (This is a strong claim offered here without proof. CloudProxy provides assurance that the expected program is running; assuming the code does not contain any bugs that allow it to be comprimised, a formal treatment of our protocol should reduce the adversary's control of the routers to standard cryptographic assumptions: in particular, CDH on elliptic curves, as well as the integrity and confidentiality of the cipher suite underyling TLS.)

The intended property of communications over the mixnet is unlinkability in the sense of [1]. Consider a set of senders S where |S| = n and a set of recipients T. Each sender chooses one recipient as well as a message to send so that M : S → T is an onto mapping. The messages are transmitted to their respective recipients over the mixnet; the adversary succeeds if it outputs (s, t) such that M(s) = t, unless it controls both s and t. We say that communication over the mixnet is unlinkable if for any adversary the probability of success is less than 1/n plus some negligible value.

Alternative definition: as above, except the adversary chooses the messages to be sent. This change may make it easier to analyze the unlinkability of a particular protocol. However, this would require the recipients to participate in the protocol, since messages exiting the mixnet must be encrypted.

For a protocol to achieve security in this sense, the messages must all have the same length; of course, this is not always reasonable in practice. Mixnets address this by splitting messages into fixed-length cells. Senders split messages into cells (zero-padding the last cell as needed) and send them to the first router where they are added to a queue. At each round the router waits until there are m cells in the queue from m distinct senders and transmits these simultaneously to achieve anonymity.

Extending the definition of unlinkability to a mixnet that divides messages into cells and transmits at rounds is challenging: the presence of variable-length messages exposes traffic patterns to the adversary. One way to mitigate this problem is to zero-pad all messages to the length of the longest message. This achieves a property called unobservability [1] which is too expensive for our purposes.

Another appraoch is to weaken the security model to one in which the adversary may only observe a fraction of the network at any one time; relaying messages over circuits of routers may make it more difficult to perform traffic analysis. This is the case for the design of the Tor onion-routing protocol [2]. We will consider extending our protocol to a network of routers to achieve security in this model. This approach may have the added benifit of reducing latency of messages traversing the mixnet.

Design Overview

Our mixnet design consists of two major component, router and proxy, and one administrative component, directory. A router (mixnet_router), or a mix, shuffles and routes users' messages, and a proxy (mixnet_proxy) accepts any TCP connections via a SOCKS5 proxy from a user and relays the packets through the mixnet. A directory (mixnet_directory) acts as a synchronization point, and manages a list of available routers in the mixnet currently for other routers and proxies to use.

At a high level, our design is, at least at the moment, an asynchronous free-flow mixnet. Unlike cascade-mixnets, a free-flow mixnet allows different messages to be routed through different paths through the network of mixes. It is also asynchronous in the sense that each mix makes their own routing decisions without coordinating with rest of the mixes in the network.

A typical messaging session for two end-to-end users, Alice and Bob, works as follows.

1. Proxy accepts a connection from Alice, and receives a message to send to Bob.

2. Proxy picks an entry mix. It then establishes a one-way authenticated TLS connection with the entry (the mix attests that it is running CloudProxy), and requests to establish a circuit to Bob. A circuit is a path of mixes in the network the messages for this particular end-to-end connection will be routed through.

3. The entry mix selects random mixes to form a circuit. It establishes a two-way authenticated TLS connection to the next mix in the circuit, and it relays the circuit creation request to the next hop. The next mix does the same until the circuit reaches the exit mix.

4. Once the circuit is established, the proxy sends the message over to the entry mix. Every packet exchanged between a mix and a proxy, called a cell, is of fixed length. If the message is shorter than a cell, then the message is padded to the fixed length. If the message is longer, then it is broken down into multiple cells.

5. Once enough cells from different proxies are available at the entry mix, it permutes the cells, and sends the cells to the next mix in the circuit. Similarly, the intermediate mixes in circuits wait for enough cells from different circuits, and permute the cells, and send the cells to the next hops. The exit mix reconstructs the message from cells, and send the message to Bob.

6. Bob can respond to the message, and the message will traverse the mixnet using the same circuit in reverse.

Note that in step 3, the entry mix picks the circuit through the network, not Bob. This is because the entry mix, which is CloudProxy authenticated, is assumed to be secure, and disabling malicious users (who are not authenticated) from selecting the path will likely enable better security.

The design also made several design decisions that trades-off security and performance. For instance, it may result in less latency to allow a mix in step 5 to treat connections from proxies and other routers the same way, and thus requires less connections from proxies. This, however, could reduce the anonymity set size of the proxies. Such design choices may change as we analyze the security of the system further.

Code Overview

Some of the important files are

• queue.go: Implements the batching and mixing functionality for cells.
• router.go Handles connections from/to proxies, routers, and end points. Uses a queue from queue.go to maintain 3 different queues for (1) cells sent from proxies, (2) cells sent to proxies, and (3) cells to/from other routers. This is required to be run in CloudProxy environment.
• socks5.go: Implements a simple SOCKS5 proxy that proxy uses to listen to end users.
• proxy.go: Uses socks5 to receive messages from end-users, breaks the messages into cells, and handles communication with the entry mix.
• conn.go, listener.go, circuit.go: Used to manage different network connections and circuits.
• mixnet.proto: Specifies the directives (e.g., creating/destroying circuits) used by proxies and routers.

Parameters

There are server system wide parameters that impact the security and performance of the system.

• Batch size (batchsize): This determines how many cells from different circuits or proxies a router needs to collect before mixing and sending them to the next hop in the circuit.

• Hop length: Currently, the default number of hops in the circuit is set to 3. Longer circuits will likely provide better anonymity, at the cost of increased latency, and vice-versa. The hop count also need not be fixed for all circuits, but we assume it is for simpler design and analysis.

• Cell size: Each cell is fixed at 1024B currently. This should be at most 65KB, the maximum packet length for TCP.

Tests

mixnet_test.go and other test files contain unit tests and integration tests that can be run natively in Go. The largest integration test uses 20 proxies, 6 routers, and there are four paths through the routers used by 20 proxies. The messages are then echoed back to the proxies by a simple server at the end of the circuit.

The scripts in scripts runs a full Tao test (currently with soft-tao). It implements essentially the same integration test as the one in mixnet_test.go, except it runs it with real Tao (though SoftTao at the moment). The script assumes that CloudProxy is installed already. Please take a look at the README in the scripts directory for instructions to run the scripts.

References

[1] Andreas Pfitzman, 2010. A terminology for talking about privacy by data minimization: Anonymity, Unlinkability, Undetectability, Unobservability, Pseudonymity, and Identity Management. https://dud.inf.tu-dresden.de/literatur/Anon_Terminology_v0.34.pdf

[2] Tor specification. https://svn.torproject.org/svn/projects/design-paper/tor-design.pdf

[3] SOCKS Protocol Version 5. http://tools.ietf.org/html/rfc1928