Compromised Remailers

Len Sassaman rabbi at abditum.com
Sun Dec 14 20:42:28 PST 2003


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.





More information about the cypherpunks-legacy mailing list