A simple introduction to mixnets

I work for Nym, an internet privacy company. One of our technologies, a mixnet, can defend users against even very strong adversaries, like governments or large companies. Here’s how it works, described in a non-technical way.

We have already put out quite a bit of technical documentation about mixnets and privacy, and with the upcoming release of our whitepaper there will be a lot more. Probably the easiest half-hour introduction to the technical guts of a Loopix mixnet is this Usenix presentation video, if you’re a security nerd and want to have a look at that.

But so far I think there hasn’t been simple, or maybe simplistic, explanation of what a mixnet is. Here’s an attempt to boil things down to a non-technical level.

We usually present the mixnet like this:

The trouble with architectural diagrams is that they usually make total sense to the geeks that draw them, but may not help anybody else. Today, we’ll take a different approach. Let’s build a mixnet in our minds, using physical metaphors, as a thought experiment.

Think of a crowded street you know in a big city. If it’s anything like London (where I live), the street has a lot of cameras pointed at it. The surveillance camera operators are the people you’re trying to defend against.

The camera operators can see everything on the street, and also record everything for later analysis.

Next, populate the street with people. Even in a crowded street, it’s clear to the camera operators what paths they took, and who they might have spoken to, because they are recording everything in high-quality video and can play it back at leisure.

The question is, is it possible to defeat the omnipresent surveillance on the street?

Let’s try. Picture everyone wearing identical masks and clothing.

You can do anything you want in the freedom of your own mind, so have a little fun with it. They can be all in Guy Fawkes masks + minimalist black outfits, or looking fabulous in full Mardi Gras costumes. Just make sure that each individual person is indistinguishable from every other person.

Surveillance is now a lot harder. This is the magic of one of our technologies, called Sphinx. All information travelling through the mixnet (the street, in our analogy) is wrapped up in Sphinx packets. Sphinx makes it difficult to distinguish between different pieces of information because it wraps all distinguishing features under into a bland, same-ish uniform of encryption.

Here are my Sphinx packets transiting the network:

Already looking pretty hard to keep track of.

Is there anything else we need? Yes. Company.

Think of the street’s foot traffic at two times of day. First, a crowded Friday afternoon with lots of people out and about. Second, at midnight on Sunday. Almost nobody is there.

Now, if you’re the only person in the street on Sunday night, the surveillance cameras can still easily see what you did, no matter whether you’re wearing an Eyes Wide Shut getup, a riot cop uniform, or an Easter Bunny outfit. There just isn’t enough cover for you. Put another way, the anonymity set is not big enough to hide within.

But if you’re part of 100,000 people in the street on Friday afternoon, you will have lots of cover. It’ll be very difficult to pick you out of the crowd and de-anonymise you.

These sheep tell the story:

As you can see, anonymity loves company. Your anonymity in a network system is similar to the anonymity you get from being mixed up a big crowd of people who are indistinguishable from each other.

Is this all we need? Job done? No, not yet.

The surveillance camera operators can still keep track of people by timing them. Assume that all the people entering and leaving the street do it in an orderly way (one in, one out). Even if the street is crowded, and everybody is wearing identical Barney the Purple Dinosaur outfits, they can still figure out who’s who. They just need to keep an ordered count.

How can we stop this timing attack?

Back in your thought experiment, put some tents at regular intervals along the middle of the street. The surveillance cameras can’t see inside those. People periodically enter the tents, and hang out for a very short, random amount of time. Then they leave in a different order than they arrived. Now the camera operators really have no idea who is who.

The tents are your mixnodes. They shuffle, or mix together, the Sphinx packets, to ensure that the surveillance operators are unable to use timing attacks (counting packets in order) to de-anonymise users. Here’s a technical drawing of some Sphinx packets momentarily relaxing inside a beer tent in Munich, completely safe from outside surveillance:

There’s one last thing we can do. Although people are now pretty much perfectly safe from surveillance as they walk down the street, it’s still pretty clear when they enter the street, or leave the street - that is, when they start or stop using the mixnet.

This can be a problem - if you enter our imagined street at the exact time you want to counter surveillance, and leave the street as soon as you’re done, it may still be pretty obvious what actions you’re taking (depending on the real-world context of what you’re doing). So Nym’s mixnet continuously sends cover traffic: fake street traffic that real people taking real actions can blend in with.

As soon as you start a Nym application, it automatically starts sending some robots into the street on your behalf. That way, when you actually need anonymity, the actions you take are buried inside a stream of other traffic that’s already been sent from your machine.

Ok, that’s mixnets related to the real world. Let’s look back at our original mixnet architecture drawing, armed with our new physical perspective.

As we know from the Snowden revelations, various entities keep large portions of the internet under full surveillance - they are essentially recording all information flows on the internet. Those are the cameras we want to defend ourselves against. Have a look at the mixnet schematic:

Alice’s computer on the left hand side wants to send messages to Bob’s computer, through the mixnet, and evade surveillance.

As soon as Alice’s computer is turned on, it automatically starts sending Sphinx packet cover traffic through the mixnet. Each of those packets is indistinguishable at a binary level from every other packet, like a stormtrooper is indistinguishable from other stormtroopers.

The Sphinx packets get routed through mixnodes. Packets are shuffled together and emitted in a different order than they went into each node. Like stormtroopers stopping off for quick beers in Oktoberfest tents.

The Sphinx packets traverse multiple mixnodes and get delivered to Bob. Assuming there is a sufficiently large number of people using the mixnet (that we have a big anonymity set of stormtroopers, or sheep, in the street), it’s impossible for anybody watching the network to determine whether Alice was talking to Bob, talking to someone else, or just automatically sending cover traffic while she was out eating a sandwich.

So, to recap, the Nym mixnet uses the following techniques to defeat pervasive online network surveillance:

1. make all traffic look the same (so adversaries can’t follow individual traffic)
2. re-order traffic (so that adversaries can’t simply count what goes in and what comes out to statistically de-anonymise users)
3. generate fake cover traffic (so adversaries can’t know when anonymity was important)

*Photo credits: London Street | Storm Troopers