On Dec 14, 2003, at 12:40 AM, Bill Stewart wrote:

At 06:49 PM 12/13/2003 +0100, some provocateur claiming to be Anonymous wrote:

...

A question for the moment might well be how many if any of the remailers are operated by TLAs?

The TLAs have proposed running various anonymizers for China and other countries that have oppressive eavesdroppers.

China has proposed to run remailers for use by citizens of nations with laws allowing bureaucrat search warrants (not judges, just civil servants), Patriot Acts, no-knock raids, and concentration camps at Gitmo.

If you go look at past remailer discussions (probably starting with Tim's Cyphernomicon or some of the remailer docs), you'll be reminded that just using one remailer isn't enough if you're worried about it being compromised, though it's usually fine for trolling mailing lists :-)

Remailers are secure if at least one remailer in a chain is _not_ compromised, so you not only want to be sure that some of the remailers you chain through are run by good people, but that their machines are likely not to have been cracked, and ideally you use remailers in multiple legal jurisdictions because that reduces the ability of any one government to put pressure on the remailer operators, and increases the chances that if all of the remailers are compromised, at least one of them isn't compromised by someone who's interested in _you_.

I haven't carefully looked at the current source code (if it's available) for things like "Type II Mixmaster" remailers, things which offer reply-blocks. Certainly for the canonical Cypherpunks remailer, the store-and-forward-after-mixing remailer, the fact that the nested encryption is GENERATED BY THE ORIGINATOR means that interception is useless to a TLA. The most a TLA can do is to a) not forward as planned, resulting in a dropped message, or b) see where a particular collection of random-looking (because of encryption) bits came from and where they are intended to next go. In particular, a TLA or interceptor or corrupted or threatened remailer operator CANNOT insert new text or new delivery instructions into packets received by his node BECAUSE HE CANNOT OPEN ANY PAYLOAD ENCRYPTED TO THE NEXT NODE. Anything he adds to the payload bits (which he can see of course, though not decrypt or make sense of) will of course make the next node see only garbage when he tries to decrypt the payload. This process continues, in a recursive fashion. Now of course there are some boundary conditions. If every remailer is compromised, then complete "visibility" is ensured. The sender and receiver are in a fishbowl, a panopticon, with everything visible to the TLA or attackers. And if even a fraction of the remailers are compromised, then with collusion they can map inputs to outputs, in many cases. (How many they can and how many they can't are issues of statistics and suchlike.) Another boundary condition is when a remailer network is lightly used, or when correlations between sent messages, received messages, and actions take place. A signal recovery problem, perhaps akin to some military sorts of problems. (Note that this "few users" problem is essentially isomorphic to "compromised remailers." And if the TLAs are the dominant users of remailers, sending dummy messages through, they get the same benefits as when their are few users or compromised remailers. For example, if the typical mix "latency" is 20 messages, and TLAs account for 98% of the traffic through remailers, then it's easy to calculate the Poisson probability that they can trace the only message that is NOT theirs. And so on.) Most of these problems go away when the number of remailers is large, the number of independent users is large, and the remailers are scattered in multiple jurisdictions, making it hard for the TLAs to enforce or arrange collusion. Another "trick" of use in _some_ of the boundary conditions is to "BE A REMAILER." This gives at least one node, namely, oneself, which is presumably not compromised (modulo black bag attacks, worms, that sort of stuff). And one could pay others to operate remailers with trusted code. (No disk Linux computers, for example, as discussed by several here over the years..) Finally, most of these issues were obvious from the very beginning, even before Cypherpunks. When I proposed the "quick and dirty" remailers in the first Cypherpunks meeting, the ones we emulated in our Games, it was with the full awareness of David Chaum's "untraceable e-mail" paper of 1981 (referenced in the handout at the first meeting). And of his later and more robust DC Net paper of 1988, further developed by the Pfitzman team around that time. The Chaum/Pfitzman/et. al. DC-Net addresses the collusion problem with novel methods for doing, effectively, zero knowledge proofs that some bit has bit been entered into a network without any traceability as to who entered it. (Chaum uses 3 people at a restaurant, using a scheme involving coins and parity and selective disclosure with some neighbors to show that it can be proved that one of a group paid the bill, but not which one.). Adding reply-block capability significantly raises the risks for traceability, in my opinion. I am not casting doubt on the Anonymizer and on Mixmaster Type N (whatever is current), but I have not seen much detailed discussion here on the Cypherpunks list, and I am unaware of peer-reviewed papers on the cryptographic protocols being used. (If they exist, pointers here would be great to have!) When I did the BlackNet demonstration, conventional Cypherpunks remailers were used for the sending of a message to a recipient, who might be a true name, might be a nym, whatever. Replies were handled with message pools, i.e., sending another message via remailers to a place that is widely visible (a Democracy Wall sort of thing) such as a Usenet newsgroup. The newsgroup alt.anonymous.messages was created around that time, as I recall, and served well. This was not a "reply-block" approach, just the basically clean approach of nesting payloads, a la conventional encrypted Cypherpunks remailers. For a significant fraction of messages through remailers, replies are not even needed. When replies are needed, message pools. Note: From 1988-93 I bought the Crypto Proceedings, some of the Eurocrypt proceedings, etc. I even attended some of the conferences. I followed who was doing what. For various reasons, my interest in the guts of crypto declined. Others were following developments, fortunately. But I haven't looked at a Crypto Proceedings volume in several years, so I'm out of touch with what researchers are publishing about mixes and untraceability. I'm relatively confident that the points above are general enough to be unchanged, whether the Newest Name is "Onion Routing" or "Crowds" or whatever. --Tim May

On Sun, 14 Dec 2003, Tim May wrote:

I haven't carefully looked at the current source code (if it's available) for things like "Type II Mixmaster" remailers, things which offer reply-blocks.

Yes, it is available. You can download it via ftp from mixmaster.anonymizer.com, or view the SVN tree at https://source.mixmaster.anonymizer.com/ (We believe that keeping the source tree and commit list open is important, as it should help prevent a situation like that which happened to JAP not too long ago. Changes to the code should all be made in public.) Also it's important to note that Type II does not support reply blocks, while "Type I" remailers do. (Perhaps the first cut of Cypherpunk remailers, i.e. those running Hal's scripts did not, but the Cypherpunk nym servers that use reply blocks are built on top of Type I.)

Certainly for the canonical Cypherpunks remailer, the store-and-forward-after-mixing remailer, the fact that the nested encryption is GENERATED BY THE ORIGINATOR means that interception is useless to a TLA. The most a TLA can do is to a) not forward as planned, resulting in a dropped message, or b) see where a particular collection of random-looking (because of encryption) bits came from and where they are intended to next go.

For most TLS adversaries that may be correct. However, there are a number of subtle attacks on Chaum systems that Type I is susceptible to -- tagging and timing attacks in particular, as well as replay attacks, and various other attacks which all strive to narrow the anonymity set.

In particular, a TLA or interceptor or corrupted or threatened remailer operator CANNOT insert new text or new delivery instructions into packets received by his node BECAUSE HE CANNOT OPEN ANY PAYLOAD ENCRYPTED TO THE NEXT NODE. Anything he adds to the payload bits (which he can see of course, though not decrypt or make sense of) will of course make the next node see only garbage when he tries to decrypt the payload.

Ideally. There are ways to flip bits in PGP encrypted messages which will not result in a failed decryption, however. (The property you describe is essential for protecting against tagging attacks. Type II does better than PGP-based systems, but is still not as good at this as Type III. The Mixminion design paper covers these concerns in detail: http://mixminion.net/minion-design.pdf

This process continues, in a recursive fashion.

Now of course there are some boundary conditions. If every remailer is compromised, then complete "visibility" is ensured. The sender and receiver are in a fishbowl, a panopticon, with everything visible to the TLA or attackers.

And if even a fraction of the remailers are compromised, then with collusion they can map inputs to outputs, in many cases. (How many they can and how many they can't are issues of statistics and suchlike.)

Right. The claim that "there only needs to be one trustworthy remailer in a chain" fails to recognize the power of statistical analysis of a network's traffic. Certainly, having k number of remailers in a network under your control makes such analysis easier.

Another boundary condition is when a remailer network is lightly used, or when correlations between sent messages, received messages, and actions take place. A signal recovery problem, perhaps akin to some military sorts of problems.

Yes. And as you look at this problem more closely (as I have been doing ever since our conversation about this problem at the Cypherpunks meeting in Santa Cruz a while back), the solutions become more elusive. The big problems arise when the adversary has the ability to observe messages in the network over time. Partitioning attacks and long-term intersection attacks likely mean that the original Cypherpunk remailer system is transparent to any entity which is able to view the traffic on the entire network. (The attacks are passive, though they can be optimized with some active interference.) Big weak spots: client version information, statistics distribution, and key rotation. In a system like Type I which relies on an external program for the layered crypto, information about the user's software distinguishes him from other users. Likewise, a user's choice of remailer nodes in a selected chain may vary based on which "pinger" service he is using, and whether he has updated his remailer keys after the remailer has gone through a key rotation also gives away valuable information. These and other distinguishing factors allow an attacker to partition the main anonymity set into smaller sets. Over time, the attacker may be able to plot the intersection of these sets such that he is able to identify a given user based on his usage patterns and the information he is leaking. Type III goes a long way to address many of these, but still falls short of perfect. The particularly troubling issue at the moment is how to distribute information about the reliability (as well as key information) of remailers in the network such that every client is using the same set of data in the same way. (If pingers, or reputation servers, could be assumed to never disagree, this would be much easier. Unfortunately experience and common sense tells us they cannot.) There are some detailed discussions of this on the Mixminion list. www.mixminion.net.

(Note that this "few users" problem is essentially isomorphic to "compromised remailers." And if the TLAs are the dominant users of remailers, sending dummy messages through, they get the same benefits as when their are few users or compromised remailers. For example, if the typical mix "latency" is 20 messages, and TLAs account for 98% of the traffic through remailers, then it's easy to calculate the Poisson probability that they can trace the only message that is NOT theirs. And so on.)

Right. The simplistic demonstration of this problem is the "n-1" attack, discussed in detail on this list many times over the last decade. George Danezis and I recently published a paper on an optimized method of detecting and thwarting these attacks. http://www.abditum.com/p125_danezis.pdf (Note that this does presume that there exists a good userbase, and the n-1 attack conditions are a result of the attack, and not simply present because of a significant shortage of users.)

Most of these problems go away when the number of remailers is large, the number of independent users is large, and the remailers are scattered in multiple jurisdictions, making it hard for the TLAs to enforce or arrange collusion.

I never assume that the location of nodes in multiple jurisdictions protects a network against a global observer. I view it as an important way of deterring forced collusion, but simple espionage passive is still very possible irrespective of borders.

Another "trick" of use in _some_ of the boundary conditions is to "BE A REMAILER." This gives at least one node, namely, oneself, which is presumably not compromised (modulo black bag attacks, worms, that sort of stuff). And one could pay others to operate remailers with trusted code. (No disk Linux computers, for example, as discussed by several here over the years..)

Indeed. The greatest point of attack on the Type II or stronger remailer systems is the end points -- sender or receiver. If an attacker can correlate one user's act of sending a message with another person's receipt of an anonymous message (and can confirm this over time), the remailer network can be treated as a black box, and needs no further analysis of its internals in order to compromise its anonymity. This is probably the greatest of the intersection attacks, and is made significantly harder to conduct if a user is able to inject messages into the remailer network unobserved. The best way to do this is to send your remailer mail from the same server that runs an active remailer.

Adding reply-block capability significantly raises the risks for traceability, in my opinion.

This is very true. And yet, users demand reply functionality. When Lance Cottrell originally wrote Mixmaster, he designed it in a way which made reply blocks impossible (as a side effect of protecting against replay attacks.) Unfortunately, because of this there are still many users of the Cypherpunk remailer system, and many remailers still operating that protocol. (Even worse, one of the dominant implementations of Type I remailers eschews the pool mix method in favor of a variation on Kesdogan's S-G Mixes, and then uses the Windows Rand() function for determining the time delay at each node. Ugh!) Type III has a very clever way of doing replies, which I think is sound from a security standpoint. I have come to believe that reply blocks are not the best way of doing anonymous message receipt for a number of other reasons, however, and am pursuing different methods based on PIR schemes.

I am not casting doubt on the Anonymizer

Anonymizer is an entirely different beast, and suitable for a different set of threats. If you have an adversary who is able to watch and analyze the Internet in real time, a single trusted proxy is not your solution.

and on Mixmaster Type N (whatever is current), but I have not seen much detailed discussion here on the Cypherpunks list, and I am unaware of peer-reviewed papers on the cryptographic protocols being used. (If they exist, pointers here would be great to have!)

They do; there has been much work done by the academic researchers in this area in the past few years. I've spent the last couple of years making them aware of the Cypherpunks -- perhaps I should be doing the opposite as well. Roger Dingledine keeps a nice bibliography of anonymity papers on his site: http://www.freehaven.net/anonbib/

When I did the BlackNet demonstration, conventional Cypherpunks remailers were used for the sending of a message to a recipient, who might be a true name, might be a nym, whatever. Replies were handled with message pools, i.e., sending another message via remailers to a place that is widely visible (a Democracy Wall sort of thing) such as a Usenet newsgroup. The newsgroup alt.anonymous.messages was created around that time, as I recall, and served well.

This was not a "reply-block" approach, just the basically clean approach of nesting payloads, a la conventional encrypted Cypherpunks remailers. For a significant fraction of messages through remailers, replies are not even needed. When replies are needed, message pools.

I believe this is the right approach for replies. However, message pools don't scale. (In order to protect against many attacks, each user would have to download all messages. In order to work well, they must be a "send everything everywhere" system.) Private Information Retrieval is effectively an optimization on this approach that allows it to scale while preserving the anonymity and reliability properties. I have a draft of a paper that I am writing (with Bram Cohen) about such a system. I will post a link to it here after I spend the next few days correcting some minor mistakes. As for sender anonymity systems, it would be great if you and other Cypherpunks were to read the recent papers on the subject. We'd all benefit from your input. It is also worth noting that high-latency systems, like Mixmaster, face a different set of threats than low-latency systems, like Freedom or Onion Routing. There is overlap, but it is important to discuss these systems in the context of their latency requirements, to make it known which set of attacks are present. (An aside -- The Onion Router has finally been open sourced. You can read about it here: http://www.freehaven.net/tor/ or see the presentation on TOR at CodeCon '04.) Pointers to important papers: Andreas Pfitzmann's paper on terminology is a good primer for those reading who may not know the specific vocabulary of anonymity: http://freehaven.net/anonbib/papers/Anon_Terminology_v0.14.pdf Here's a paper about the nym.alias.net nym server (based on cpunk reply blocks) : ftp://cag.lcs.mit.edu/pub/dm/papers/mazieres:pnym.pdf Here's some work that's been done on measuring the strength of an anonymity system: http://www.esat.kuleuven.ac.be/~cdiaz/papers/tmAnon.ps.gz http://www.cl.cam.ac.uk/~aas23/papers_aas/set.ps http://www.esat.kuleuven.ac.be/~cdiaz/papers/DS03.ps.gz This is a good paper on remailer attacks, as well as the different pool mix schemes: http://freehaven.net/doc/batching-taxonomy/taxonomy.pdf Of course, the Mixminion paper: http://www.freehaven.net/anonbib/cache/minion-design.pdf (This is just a selection of papers I have found important. There are a number of other papers that are also very worth reading linked from the http://www.freehaven.net/anonbib/ site as well.) --Len.

This came in response to Cryptome's posting of Len Sassman's comments on remailers. -----