Compromised Remailers

[Tim May]

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