This document contains frequently asked questions about the Type III remailer protocol, and about Mixminion, the reference implementation of that protocol. This is not a FAQ about remailers or anonymity in general.
Nick Mathewson maintains this document; email nickm@freehaven.net with comments or suggestions. All entries are by me unless otherwise noted.
"Type III" is the name for an improved anonymous remailer design. It was designed to address known flaws in earlier deployed remailers, and to resist all known anonymity-breaking attacks as well as possible.
"Mixminion" is the name for the project that designed the type III protocol, and is also the name for the reference implementation of the protocol. (The protocol used to be named "Mixminion" too, but when the Mixmaster team decided to use the "Mixminion" protocol as the basis for Mixmaster version 4, we changed the name of the protocol to be more project neutral.)
When you communicate on the Internet, even when you use encryption, anybody receiving or intercepting your communication can tell which addresses are talking to which addresses. By "anonymous communication system", we mean a system in which it is difficult for anybody—even the people communicating with each other—to tell who is talking to whom.
How difficult? Mix-net designs attempt to prevent an adversary from learning who is talking to whom, even if the adversary:
Mix-nets also try to provide unlinkability: that is, to prevent an adversary from learning that two messages were sent by the same person.
(This usage isn't universal. Some projects use "anonymous" to describe any system that doesn't record your name. This kind of "anonymity" is easy to achieve, and we won't mention it any further.)
Back in 1981, David Chaum wrote a paper describing an anonymity server called a "mix." In Chaum's design, users encrypt messages to a mix's public key, and send those messages to the mix. The mix delays and re-orders the messages in order to prevent an eavesdropper from correlating messages entering and exiting. When it's time to deliver a message, the mix decrypts it, removes any information identifying its sender, and relays it to its recipient.
In order to prevent a single malicious mix from revealing the sender's identity, senders route each of their messages through a sequence (or "chain") of mixes. This way, if even a single mix in the sender's chain is honest, that mix prevents an attacker from linking the sender to the recipient. The complete set of intercommunicating mixes is called a "mix-net."
The term 'remailer' comes with a more application-oriented pedigree. It originally referred to anonymity servers that accepted messages via email and delivered them via email, without necessarily supporting encryption, batching, or chaining. Later generations of remailer added these features, and thus have become true mixes.
(You might argue that since Type III doesn't use email for its underlying mix-to-mix communications, it shouldn't really be called a 'remailer' protocol. On the other hand, since 'mail' is an abstract concept, you might argue that Type III's store-and-forward design is close enough to email as to make it a 'remailer'. Finally, you might decide that 'remailer' has become the generic term for 'high-latency anonymity server,' thus making Type III a remailer regardless.)
That depends on how paranoid you are. The Type III mix design is almost certainly secure for most kinds of users, against most adversaries. It is in many respects more secure than currently deployed mix-nets.
In my opinion, which could well be wrong, users of Type III mixes will probably be secure against anybody without the resources of a major telecom or government. People who only use the system occasionally are (I think) probably secure against telecoms and governments too, but that's harder to quantify.
On the other hand, you should be aware of a certain class of long-term intersection attacks that are effective against all currently known practical mix-net designs: if you send enough traffic to the same people over a long enough time, and if an adversary with a little mathematical ability is eavesdropping on you and your recipients, that adversary can statistically deduce whom you're communicating with. (These attacks require a lot of traffic—on the order of hundreds of messages.) Quantifying the severity of these attacks is an area of active research.
There are currently two widely deployed mix protocols: the Type I or "Cypherpunks" protocol, and the Type II or "Mixmaster" protocol.
Starting in 1992, Eric Hughes, Hal Finney, and others wrote the first Type I remailers. Type I uses email for a transport, and PGP for its encryption. Later implementations of the Type I protocol added new features in an attempt to mitigate some of the protocol's weaknesses, with limited success. Lance Cottrell's Type II (1995) software fixed most of Type I's insecurities, but dropped support for reply blocks.
The following table outlines the feature-differences and security differences between the three protocols. Parenthesis indicate partial support for a feature; or partial resistance to an attack. (Note: Type I is not formally specified, and exists in several versions. Claims for Type I below refer to the state of the art in Type I, such as it is.)
| Feature | Supported by | ||
|---|---|---|---|
| Forward delivery | 1 | 2 | 3 |
| Reply blocks | 1 | 3 | |
| (Multiple-use reply blocks) | 1 | ||
| (Single-use reply blocks) | 3 | ||
| Nymservers | 1 | 3 | |
| Automatic directory retrieval | 3 | ||
| Distributed, coordinated directories | 3 | ||
| Automatic server key rotation | 3 | ||
| Loss-tolerant message fragmentation | 3 | ||
| Forward-secure encrypted transfer protocol | 3 | ||
| Attack | Resisted by | ||
| Forward message replay | (1)a | 2 | 3 |
| Trace messages by size | b | 2 | 3 |
| Distinguish among message formats sent by different clients | 2 | 3 | |
| Distinguish forward packets from reply packets before delivery | n/a | 3 | |
| Distinguish encrypted forward packets from reply packets | n/a | 3 | |
| Reply block flooding | n/a | 3 | |
| Path distinguishability based on client knowledge | 3 | ||
| Compromise keys later to read traffic recorded today | 3 | ||
| Run a directory server and mislead specific users | 3 | ||
| Parameter | Value | ||
| Public key length (bits) | Variable | 1024 | 2048 |
| Payload lengthc | Variable | 10K | 28K |
| Packet lengthc | Variable | 20K | 32K |
| Maximum path length | None | 20 | ~30d |
| Ciphers used | as in PGP | RSA 3DES | RSA AES |
XXX What else?
Unlike 'low-latency' anonymity systems such as Freedom, Onion Routing, Anonymizer, Crowds, Web Mixes, and the Java Anon Proxy (???), Type III mixes sacrifice latency for higher anonymity. Low-latency systems aim to provide fast enough end-to-end connectivity to support interactive web browsing (and sometimes other protocols such as SSH). This property, however, makes it fairly easy for an attacker observing or controlling both ends of the communication to correlate the timing of data sent along the channel.
Unlike 'single-hop' anonymity systems like Anonymizer, various anonymous web-email forms, and the now-defunct penet.fi, mix-nets route messages through a chain of relays. Using a single-hop system depends on a single trusted anonymity provider to keep you anonymous. With a chain of mixes, if any mix in the chain is honest, the connection between sender and recipient remains hidden.
XXX what else?
(The systems in this section are listed as "research" or "theoretical" because they are better known through the research literature than via any widely deployed implementation.)
Gülcü and Tsudik's Babel mix design (1996) addresses Type I's size-correlation and PGP issues, while adding multiple-use reply blocks. Unlike Babel, Type III's reply blocks are single-use, and are not vulnerable to end-to-end replay attacks. Also, in Babel, non-exit mixes can distinguish forward messages from reply messages, whereas in Type III they cannot. Babel has a neat feature in which mixes can insert inter-mix detours into the reply path. A limited version of this technique is possible in Type III, but cannot extend beyond adding single-mix detours.
[XXX Mention stop-and-go mixes, flash mixes, DC nets, and so on.]
Check out the Mixminion website for information on joining the mixminion-dev mailing list.
This section answers questions related to the design of the type III protocol.
"SURB" stands for "single-use reply block": In Type III, reply blocks can only be used once.
All multiple-use reply block designs that we're aware of suffer from a common problem: anybody who gets ahold of a MURB can use it to send an arbitrary pattern of traffic to the recipient. An eavesdropper or compromised exit remailer can use this property to trace a MURB's recipients with end-to-end traffic analysis.
Some MURB designs (such as Type I) have additional vulnerabilities to replay attacks and flooding attacks.
Older remailer designs use SMTP not only for delivering messages to their recipients, but also for transferring packets from one remailer to the next. Type III, however, uses MMTP (a simple TLS-based protocol) when transferring packets to or from remailers. This has several advantages, including:
There are, however, a few drawbacks to not using SMTP for relaying messages. We believe that they are outweighed by the benefits of a uniform, integrated, encrypted protocol, but we list them for completeness:
The relevant quote (from p. 65) is:
A 128-bit key would be great except for one problem: collision attacks. Time and time again we find systems that can be attacked by a birthday attack or a meet-in-the-middle attack. We know these attacks exist. Sometimes designers just ignore them, and sometimes they think they are safe but somebody finds a new, clever way of using them. Most block cipher modes allow meet-in-the-middle attacks of some form. We've had enough of this race, so here is one of our design rules.
Design rule 3. For a security level of n bits, every cryptographic value should be at least 2n bits long.
Because of this principle, Ferguson and Schneier recommend AES-256 as a block cipher and double-SHA-256 as a digest function. The current type III specification, on the other hand, calls for 128-bit AES and 160-bit SHA1: if there were a way to exploit birthday or meet-in-the-middle attacks against our protocol, then instead of 128 bits of security, we would only have 64 or 80.
(Collision attacks exploit the property that "If an element can take on N different values, then you can expect the first collision after choosing about SQRT(N) random elements." Thus, one only needs to perform about 2^80 SHA-1 operations to find two different strings that hash to the same value.)
We do not now believe that there are any useful collision attacks against the Type III protocol. Here's why:
First, we can exclude attacks where an attacker waits for collisions in AES128 keys or SHA1 digests: to do so, the attacker would need at least 37 zettabytes (!) of storage to store just a single-leg 2K header for each message. Thus, the attacker's best hope is to find collisions on their own and then somehow exploit them. But even if an attacker does know a set of collisions, they could at worst use them to send packets of their own which would interfere with each other, not to compromise others' anonymity.
F&S also recommend double-SHA (that is, SHA(SHA(x))) as a digest algorithm, since SHA has the regrettable property that SHA(x|y) can be deduced from SHA(x) and y. We use variable-length SHA in 6 places, all of which we believe to be safe:
So there doesn't seem to be any need to move to AES-256 and double-SHA-256 right now.
(XXXX list a bunch of features.)
Changes since the publication of the original design paper are:
Features in the specification not described in the original design paper are:
Features described in the original paper but not yet fully specified are:
You can always find a link to the latest release of the code at http://mixminion.net/.
If you want to access the CVS repository, there's a regularly updated sandbox with anonymous pserver access. To use it, run:
So far as we know, the code works fine. As of 15 December 2003, there are 27 servers running, including 11 with exit support.
It depends how anonymous you need to be. For casual use, Mixminion may meet your needs.
For the moment, however, we do not recommend using Mixminion for messages that require real anonymity. This is for the following reasons:
So in summary, feel free to play with Mixminion and use it for casual anonymity, but don't count on it for strong anonymity yet.
Right now, the requirements to build and run a Mixminion client on a Unix-like operating system are:
If you're using Solaris, be aware that some versions of Solaris come installed with mis-compiled versions of Python that don't have networking support. Don't worry—compiling your own Python installation is dead easy. Go to python.org and start from there. A basic Python installation should take 20-30 MB of disk space.
To run Mixminion on Windows, you'll need:
To build and run a Mixminion server, your system must meet the requirements listed above for building and running a client. Additionally, you'll need all of the following to run a server:
There are instructions in each version of the release notes. (That's the file entitled "README" in the Mixminion distribution.)
Not yet. The only client is the built-in CLI client.
Right now, you have two options:
The Mixmaster team currently plans for Mixmaster version 4 to include a C library to support Type III messages. This code, however, is not yet written.
Actually, no. Mixminion is written in a mixture of Python and C for portability, rapid development, and robustness. For more information about Python's advantages, peruse the documentation at python.org.
As for speed concerns: If Mixminion were written entirely in Python, it would indeed be slow. Fortunately, the application's performance-critical sections are almost entirely concentrated in cryptography and I/O, and by using C for these operations, we get close to ideal performance.
(For example, RSA decryption is so slow that the other operations a server performs when decrypting and processing a Mixminion packet take less than 5% of the CPU resources expended per packet. Assuming that OpenSSL's (C) implementation of RSA is already close to optimal, we would expect no more than a 5% performance improvement from rewriting packet processing in C.)
This is a general case of the 90/10 rule: programs usually spend about 90% of their time in 10% of their code. Optimizing this code is sufficient to optimize the application; further optimization gives diminishing returns. (This is just a rule of thumb, but oddly enough, it turns out that 11.3% of the code in Mixminion 0.0.5 is written in C.)
The TODO file in the CVS repository has a tentative schedule for features to appear in future releases.
The schedule in the TODO file is tentative—and so are all other statements that anybody makes, ever, about dates and features for future releases. This is a volunteer project, and progress depends heavily on how much spare time Nick has from week to week.
With that in mind, the historical wait between releases has been:
| From first CVS commit to 0.0.1 | ~6.5 months |
| From 0.0.1 to 0.0.2 | ~21 days |
| From 0.0.2 to 0.0.3 | ~1.5 months |
| From 0.0.3 to 0.0.4 | ~3.75 months |
| From 0.0.4 to 0.0.5 | ~2.75 months |
| From 0.0.5 to 0.0.6 | ~3 months |
Nick says that he's trying to shoot for a two month release cycle, but this may be too ambitious.
Preferably, go to the Mixminion bugzilla page at bugs.noreply.org.
If this isn't feasible, send email to the list at mixminion-dev@freehaven.net, or to Nick Mathewson at nickm@freehaven.net.
When reporting a bug, please include all of the following:
The Mixmaster team plans to include Type III support in Mixmaster version 4.
Others have expressed interest in writing Type III client libraries in C, but no announcements have been made and code has yet been publicly released.
There is no backdoor in the Mixminion code. The code is publicly available, so anybody who reads Python can check for themselves.
I will never willingly add a backdoor in the Mixminion code. (Exceptions: Any testing infrastructure that endangers anonymity will be labeled as such, and will be removed before the first beta release. The code will cause any testing servers running in non-anonymous configurations to advertise themselves as such.)
Of course, if I'm legally compelled to add a backdoor, I probably won't be allowed to tell you about it. Continue to review the diffs between releases, and don't trust any release that doesn't come with source.
Also, you should probably get worried if this question disappears from the FAQ. :)
—Nick