The Differences Between Onion Routing and Mix Networks
12 Apr 2013 16:52:00 EST

This blog post originally appeared on crypto.is. We've since shut down that website, so I have copied the blog post back to my own for archival purposes.

As was pointed out in a recent comment on the first blog post, I had used the terms "mix network" and "onion routing" almost interchangeably. In actuality I had fallen into a trap that a fair number of people familiar with the space have fallen into: using those terms without a solid differentiation. This blog post aims to correct that.

Firstly, I must give credit where credit is due - Paul Syverson (one of the original authors of Tor) wrote the paper that cemented this in my head most clearly, and I will quote it, and then restate it with pictures:

Mix networks get their security from the mixing done by their component mixes, and may or may not use route unpredictability to enhance security. Onion routing networks primarily get their security from choosing routes that are difficult for the adversary to observe, which for designs deployed to date has meant choosing unpredictable routes through a network. And onion routers typically employ no mixing at all. This gets at the essence of the two even if it is a bit too quick on both sides. Mixes are also usually intended to resist an adversary that can observe all traffic everywhere and, in some threat models, to actively change traffic. Onion routing assumes that an adversary who observes both ends of a communication path will completely break the anonymity of its traffic. Thus, onion routing networks are designed to resist a local adversary, one that can only see a subset of the network and the traffic on it.

- Paul Syverson - Why I'm not an Entropist

Onion Routing

Onion Routing gets its security from the fact (or assumption) that it is difficult for an adversary to position itself on networks such that it is able to view all the nodes in the route. Practically speaking, if I built a route from my job in China, to a server in Australia, to a server in Russia, to a server in Sweden, and then visit a webpage in France - there are a number of adversaries who could see part of this path. For example: my employer, my employer's Internet Service Provider, the Chinese, Australian, Russian, Swedish, and French Governments, the website operator and their Internet Service Provider. But none of those entities are able to see the entire path (we hope!) because they do not own, control, or have direct influence over every network link I'm using. In this instance, Onion Routing can provide some security.

Onion Routing Attacked

But if an adversary is able to see the entire path, Onion Routing loses its security. I recently used a crowd of people in a real-life demonstration of this. Alice puts a message into an opaque film canister, and passes it to an onion routing node, who passes it to another, who passes it to another, who takes the message out of the canister, and hands it to the recipient Bob. Everyone in the room can clearly see that it was Alice who passed a message to Bob, and even if there were multiple messages being passed, anyone could focus on an individual, and watch where the film canister passed wound up.

There's been rumors and talks in the past of China or Iran cutting themselves off from the Internet, and making their own national Internet. If they did, we could not just stand up a Tor network inside the country: it would provide no security because the government would be able to see the entire path.

There is another scenario where Onion Routing is known to fall down. If the adversary can see one node (A), and later another node (C) - even if there is an unseen or unknown number of nodes between A and C, an attacker can correlate the traffic. A specific instance of this means if an attacker can see you, and can see the website you're visiting, even if you create a path outside the adversary's control - they will still be able to correlate the traffic and learn you are visiting the website. This clearly raises concerns about using Onion Routing to visit a company website or websites related to your own government.

Mix Networks

Mixing; however, is specifically designed to provide security even if an adversary can see the entire path. To demonstrate this to a crowd of people I had Alice, Bob, and Carol each submit messages, in opaque film canisters, into my mix node (my backpack). With all three film canister messages in my bag, I shook it, and distributed each message to a new mix node, each of which also had a couple of messages in their bags already. Then those nodes distributed messages to 6 more mix nodes, and those mix nodes opened the messages and distributed them to recipients. Although everyone was able to see all of the messages that were passed around - it's impossible to tell who got Alice's, Bob's, or Carol's specific message. The mixing, in backpacks, creates uncertainty for the attacker they are not able to overcome.

Mixing isn't perfect. An adversary can still conduct long term correlation attacks, and if no one or almost no one uses the mix network along with you - it's even easier to attack. Furthermore, just because mix networks provide stronger security against a stronger adversary does not mean they provide better security in general. If you'd like to learn why, you can wait a while until I post about it, or just skip the middle man and read Sleeping dogs lie on a bed of onions but wake when mixed by Paul Syverson.

More Differences

A Mix Node must collect more than one message before sending any out - otherwise the node is behaving as an onion router node with a time delay. The more messages collected, the more uncertainty is introduced as to which message went where. The specific mixing algorithms employed (often calling pooling algorithms) will be a subject of a future blog post, but it's clear there must be multiple messages, which means the collected messages will generally sit in a mix node until 'sufficient' messages are collected (for some definition of sufficient). This introduces latency. If a mix node waits six hours to collect messages - well that's up to six hours of latency. Accordingly, mix networks are often casually referred to as 'high latency' and onion routing networks as 'low latency'. But the latency doesn't impart security - it's the mixing.

Tor is an Onion Routing network. It employs no mixing, and barring normal system task scheduling and processing, messages are sent as soon as they are received. The attacks described against onion routing above can and have been shown to work against Tor. While there is no evidence a government has resorted to performing the types of statistical attacks described in Academic papers - they have done rudimentary correlation involving physical surveillance. Specifically: they watched a suspect arrive home, they watched some Tor traffic originate from his home, and they watched as the nickname they suspected was him appeared in the IRC channel. If you're curious, you can read more about that over here. Although Tor is a powerful tool, it is possible to distinguish Tor traffic from normal traffic, and it is possible to perform correlation-based attacks to de-anonymize your use of it.

Something to keep in mind is that deployed mix networks (Mixmaster, Mixminion) are not designed to disguise the fact that you are using a mix network. If an adversary can simply lock you up for using anonymity tools, you need to disguise your use of anonymity tools, which is a whole other topic. Similarly, these tools are relatively obscure, and if an adversary can simply look across a large quantity of email traffic looking for someone who has received a Mixmaster message, who had not previously, simple correlation may also be possible.

Add a comment...
required, hidden, gravatared

required, markdown enabled (help)
you type:you see:
[stolen from reddit!](http://reddit.com)stolen from reddit!
* item 1
* item 2
* item 3
  • item 1
  • item 2
  • item 3
> quoted text
quoted text
Lines starting with four spaces
are treated like code:

    if 1 * 2 < 3:
        print "hello, world!"
Lines starting with four spaces
are treated like code:
if 1 * 2 < 3:
    print "hello, world!"