Chapter 7. Mixmaster Remailers

Adam Langley, Freenet

Remailers are one of the older peer-to-peer technologies, but they have stood the test of time. Work done on them has helped or motivated much of the current work in the P2P field. Furthermore, they can be valuable to users who want to access many of the systems described in other chapters of this book by providing a reasonable degree of anonymity during this access, as explained in Chapter 15.

Anonymous remailers allow people to send mail or post to newsgroups while hiding their identities. There are many reasons why people might want to act anonymously. Maybe they fear for their safety if they are linked to what they post (a concern of the authors of the Federalist Papers), maybe they think people will prejudge what they have to say, or maybe they just prefer to keep their public lives separate from their private lives. Whatever the reason, anonymous posting is quite difficult on the Internet. Every email has, in its headers, a list of every computer it passed through. Armed with that knowledge, an attacker could backtrack an email to you. If, however, you use a good remailer network, you make that task orders of magnitude harder.

Mixmasters (also known as Type 2 remailers) are the most common type of remailer. The Type 1 remailers are technically inferior and no longer used, though Mixmasters provide backward compatibility with them. The first stable, public release of Mixmaster was on May 3, 1995, by Lance Cottrell. The current version is 2.0.3, released on July 4, 1996. Don’t be put off by the old release date; Mixmasters are still the best remailers.

A simple example of remailers

In order to demonstrate the basics of remailers, I’ll start with the Type 1 system. The Type 2 system builds on it, adding some extra assurances that messages cannot be traced.

If you wanted to mail something anonymously to alice@world.net, you could send the following message to a Mixmaster remailer:

::
Anon-To: alice@world.net
Latent-Time: +1:30

I have some important information for you. I hope you understand
why I've taken the precautions I have to keep my identity a secret.

The remailer would hold this message for one and a half hours—to throw off track anyone who might be sniffing traffic and trying to match your incoming message to the remailer’s outgoing message—and then strip all the headers except the subject and forward the mail to Alice. Alice would see that the mail had come from the remailer and would have no idea who actually sent it.

However, this system does have problems. First, the remailer knows the destination and source of the message and could be compromised. Second, while your message is in transit to the remailer, anyone with privileged access to your local area network or an intervening mail hub can see that you are sending anonymous messages to Alice. Finally, Alice has no easy way to reply to you.

In order to hide the fact that you are sending anonymous messages to Alice, you can encrypt the message to the remailer. This assumes that you know the public key of the remailer, and while these public keys are widely known, key management is always a weak spot.

Encryption stops anyone who views the message in transit to the remailer from seeing the message and destination. (It should be noted that this doesn’t hide the fact that you are sending anonymous messages, and even that snippet of information could land you in trouble in some places.) To anyone who saw it, the message would look like this:

::
Encrypted: PGP

-----BEGIN PGP MESSAGE-----
Version: 5
Comment: The following is encrypted data

mQGiBDmG74kRBACzWRoHjjbTrgGxp7275Caldaol72oWkPgj6xxHl2KNnDyvSyNi
D+PDQUk0W86EXTr9fR8mi8V8yDzSuUQCthoD8UPf7Kk/HtR//lCGWRhoN81ynrsm
FLVhGSR5n4lgf6oNUeIObKYYOWmXzjtKCkgAUtbsImOd8/5hm7zKCQl/LwCgveTW
3bcbQ+A02SMlrxUZcx4qCfUD/1RRuZsdsJFsX9N/tBDLclqtepGQbtwJG02QSCMa
ut8ls+WEytb+l/jqBP/qN9Rry3YUtuRXmjjiYFQ8l3JWA5kd4VxzKP6nBTZfggEW
6BrGB8wDuhqTVL7SqivqrDdgB7S3WQIuZz17Vs1A1wzc37vDmHkw50wshTuvT0Pw
-----END PGP MESSAGE-----

This also solves the third problem of Alice needing to reply. You can give Alice a block, encrypted to the remailer, which contains your email address. If Alice then puts the encrypted block at the top of her reply and sends it to the same remailer, the remailer can decrypt it and forward it back to you. Alice can send messages to you without any way of knowing where they actually go. Thus, she has no way of tracing you.

That leaves the second problem, namely that the remailer is the weak link. If Alice, or anyone else, can compromise it, the whole project falls apart. The solution is a simple extension of the basic idea. Instead of the remailer sending the message to Alice, it sends it to another remailer. That remailer then sends it to another, and so on, until the last remailer in the chain sends it to Alice. Thus, no remailer in the chain knows both the source and the destination of the message.

Onion routing

If any remailer reads the contents of your message, it will know who is receiving it at the end. The solution to this involves a series of encryptions that hide the information from remailers in the middle.

Thus, when you send your message, you add an instruction to send it to alice@world.net, but you encrypt this recipient information using a key from the last remailer in the chain. So only this last remailer can determine her address. You then add instructions to send the mail to the last remailer and encrypt that information so that only the second-to-last remailer can read it, and so on. You thus form an “onion” of messages. Each remailer can remove a skin (one layer of encryption) and send the message to the next remailer, and no remailer knows anything more than what is under the skin they can remove. The layers are illustrated in Figure 7.1.

Figure 7-1. An onion of encrypted messages

You construct a reply block for Alice in the same fashion, an onion of encrypted messages. Alice, or anyone else, would then need to compromise every remailer in the chain in order to remove every skin of the onion and trace you.

How Type 2 remailers differ from Type 1 remailers

Type 2 remailers were designed to fix some of the problems with the Type 1 system above. Even though the Type 1 system seems very good, there are a number of weaknesses that a powerful attacker could use. Most of these weaknesses come from being able to do traffic analysis.

Traffic analysis means capturing the bits that cross a communications channel so as to see every packet that passes around a network—where it came from and where it’s going. It is not necessary for the snooper to be able to read the contents of every packet; a lot of useful information can be gathered just from TCP and IP headers sent in the clear, or, as you will see, just from incidental characteristics such as the length of a message.

In order to hide the connection between your incoming message and the Mixmaster’s outgoing message, each message must appear to the attacker exactly the same as every other message in the system. The most basic difference between messages is their length. (Remember that the message is multiply encrypted, so the contents don’t count.) If an attacker can see a certain sized message going into a remailer and then see a message of a very similar size going out again, he or she can follow the message. Even though the message changes size at each remailer because a skin is peeled off, this doesn’t provide much protection. The change in size as the skins are removed is small and easily calculated.

In order to make all messages the same size and frustrate traffic analysis, every Mixmaster message is the same length. This is done by breaking the message into pieces and adding padding to the last part to make it the same size. Each part is sent separately and has enough information for the last remailer in the chain to reassemble them. Only the last remailer in the chain knows what messages go together, because the information is only on the last skin. To every other remailer, each part looks like a different message.

The next identifying mark that needs to be removed is the time. If a message enters a remailer and another leaves immediately after, an attacker knows where the message is going and can trace it. This is a more difficult problem to solve than it seems at first. Simply reordering messages, or delaying them for a time, doesn’t work. If the number of other messages is low, or if the attacker can stop other messages from reaching the remailer, your message will still stand out.

Mixmasters try to solve this problem by sending out a random selection of messages periodically, while always keeping a certain sized pool of messages. This makes it very difficult to match up outgoing messages with incoming ones, but still not impossible. However, if the traffic on the Mixmaster network is high enough, tracing the message over the whole chain of remailers becomes a massive challenge for an attacker.

Finally, an attacker can capture your message and attempt to replay it through a remailer. Since your message has the encrypted address of the next remailer, by sending many copies of it an attacker can watch for an unusually large number of outgoing messages to a certain address. That address is likely to be the next remailer in the chain (or the final destination). The attacker can then repeat this for each remailer in the chain.

To stop this, every skin has a random ID number. A remailer will not forward a message with the same ID number twice, so all the cloned messages will be dropped and no extra traffic will come out. An attacker cannot change the ID number of a message because it is encrypted along with everything else.

General discussion

Mixmasters have taken remailing to a fine art and are very good at it. They are an interesting study in peer-to-peer networks in which security is the absolute priority. Unlike many peer-to-peer networks, the Mixmaster user must have knowledge of the network in order to build the onion. This means that Mixmaster nodes are publicly known. It is possible to have a private remailer by simply not telling anyone about it, but this would leave the traffic level very low and thus reduce security.

Unfortunately, Mixmasters themselves are often the target of attacks by people who, for one reason or another, disagree that people have a right to anonymity. It has been known for people to send death threats to themselves to try to get remailers shut down. The public nature of remailers makes such attacks easier.

Life can be very hard for a Mixmaster administrator, because he has to explain to angry people why he can’t give them the email address of someone who has used his remailer. This goes some way to explaining why there are only about 20-30 active Mixmasters and serves as a warning to other peer-to-peer projects that provide anonymity.