15 December 2003. Add reader response with results of remailer tests. And Len Sassman's counter-response.
15 December 2003
From a Cypherpunks thread begun by an anonymous post:
A question for the moment might well be how many if any of the remailers are operated by TLAs?
TLA = three-letter agency, FBI, NSA, CIA, any official snoop.
Date: Sun, 14 Dec 2003 20:42:28 -0800 (PST)
From: Len Sassaman <rabbi@abditum.com>
To: Tim May <timcmay@got.net>
Cc: cypherpunks@lne.com
Subject: Re: Compromised Remailers
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 TLA 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.
http://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
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.
From: S
Subject: Re: remailers-tla.htm Compromised Remailers, December 15, 2003
Date: Mon, 15 Dec 2003 16:16:17 -0700
To: jya@pipeline.com
Thank you for posting the "Compromised Remailers" article:
http://cryptome.org/remailers-tla.htm
Over the past year, many remailer users have noticed that the reliability of the Mixmaster type II network has steadily degraded. Although it may well be the result of TLA interference, the remailer community's statistical methods of selecting a "reliable" remailer chain contribute significantly to the network's degradation.
As a former employee of the United States Army Communications Command [USACC]
Headquarters, I was amazed to stumble upon the existence of a publicly available
communications medium permitting truly anonymous communication by hampering
the government's ability at "traffic analysis," or tracking an email message
from its source to its destination. One would have to be foolish to believe
that TLAs are not hard at work trying to pierce the veil of anonymity afforded
by the Mixmaster type II, and, the yet to be released,
type III remailers.
I ran tests in September, October & November, and provided the Mixmaster developers & remail operators with the same results I've included below. My testing was extremely simple: send a bunch of messages, and note which messages arrived. [The same procedure an accountant would use in tracking a financial transaction from its origin to its destination.]
What I found was that a handful of remailers accounted for virtually all of the un-delivered email messages. Yet, these same remailers, that never delivered my email messages to the "alt.anonymous.messages" news group, where also listed as among the most reliable remailers in mixmaster stats used to select remailer chains.
I've included my recommendations to improve the network's reliability in the test results below.
-----------------------------------------------------------------------------
Mixmaster II Reliability Issues & Test Results
-----------------------------------------------------------------------------
The major issue currently plaguing the Mixmaster remailer network is the true reliability of the LAST remailer in a chain. A considerable number of these remailers habitually act like "Black Holes" for email messages destined for "alt.anonymous.messages" and other news groups.
Unfortunately, most of these "Black Hole" remailers also happen to be listed
as among the most reliable remailers in mixmaster stats, with ratings ranging
from the upper 90's to 100; consequently, it's highly probable that messages
sent to newsgroups will frequently hit one of these demon remailers, never
to
reach their intended recipient.
Over the past 2 months, I've sent & tracked over 5,124 email messages consisting of either 4 or 6 copies of 1,220 unique messages, each routed through 11 Mixmaster type II remailers, to the "alt.anonymous.messages" news group.
---------------------------------------------------------------
Last Remailer Lost Msgs Delivered Msgs % Reliability
---------------------------------------------------------------
antani 63 0 0
cripto 65 0 0
hastio 41 0 0
george 31 7 18
paranoia 41 10 20
futurew 33 9 21
edo 27 9 25
starwars 54 29 35
itys 7 9 56
italy 7 10 59
bog 3 14 82
freedom 3 45 94
tonga 5 106 95
liberty 2 51 96
panta 3 69 96
bigapple 3 104 97
metacolo 3 99 97
bogg 1 52 98
dizum 2 106 98
jmbcv 1 59 98
frell 0 34 100
randseed 0 3 100
---------------------------------------------------------------
Sub-totals 395 825 68
---------------------------------------------------------------
Total 1,220
---------------------------------------------------------------
Surprisingly - at first - I found that sending messages through chains of remailers rated, in mixmaster stats, at 98% or greater was FAR LESS reliable than sending messages through remailers rated at 50% or greater. This is because the "Black Hole" remailers were almost always rated, in mixmaster stats, at 98% or greater reliability, while the remailers that were the most successful at delivering my messages were usually rated, in mixmaster stats, at reliability ratings of 90% or lower.
For those of you yelling, "it's the broken chains, dumbass!" I strongly disagree. Messages sent through broken chains were more than twice as likely to successfully reach the intended news group than were messages that failed.
--------------------------------------------
Messages Sent Through Broken Chains
(copies of the same message)
--------------------------------------------
Copies Lost Delivered
--------------------------------------------
4 13 31
3 40 92
2 94 218
1 154 325
--------------------------------------------
Sub Total 301 666
--------------------------------------------
Total 967
--------------------------------------------
Broken chains were somewhat reliable predictors only after all the "Black Hole" remailers were removed from the remailer chains selected to send messages. Even then, the broken chain stats were marginally reliable only on the infrequent occasion that broken chains changed little from day to day.
The difference I found in the actual ability of a remailer to successfully deliver email was completely at odds with the mixmaster remailer stats and broken chain data, rendering them of little value in selecting a remailer chain that insures a successful delivery.
The remailer network screams for a testing methodology that stresses the success of actual messages delivered to their destination, as I've done in this test. Basically, the network needs to be auditable, and the current method of evaluating remailer reliability needs a complete re-think because it's not working well, at all.
Additionally, Quality of Service standards need to be established and maintained. Remailers that consistently fail to deliver messages need to be removed from the network. I consistently achieved a 95% success ratio by removing the remailers, listed above, that failed to deliver email messages less than 94% of the time.
It would also be helpful for there to be better communication between remailer operators.
Example: "Italy" abruptly stopped accepting mixmaster messages on the morning of Monday, October 20, but did send an email, that morning, to the remops mailing list announcing its action to permanently leave the mixmaster network. At least two days later, italy was still listed as a working mixmaster remailer, and not even listed as a broken chain for most remailers.
* When the "Black Hole" remailers were in the chain, but not the final remailers, they were as reliable as the rest of the remailers. I found this extremely puzzling. Thankfully, I'm not much of a conspiracy theorist...
* Fortunately, in 5 of the tests when "bogg" was randomly selected as one
of the last remailers, it posted all copies of each message to the
"alt.anonymous.messages" news group instead of only sending one copy. Thank
God for small favors. ;)
----------------------------------
Copies of Messages bogg posted
to "alt.anonymous.messages"
----------------------------------
Copies Messages
----------------------------------
4 5
3 8
2 10
1 1
----------------------------------
From the first line: for 5 separate messages, all 4 copies of the messages sent through "bogg" were posted to the "alt.anonymous.messages" news group.
As you can see from the bogg data, usually more than a single copy made it through to the last remailer for the test cycles I noted.
Using bogg as an example, I feel comfortable "jumping to the conclusion" that most of the "Black Hole" remailers, that failed to deliver messages to the alt.anonymous.messages" news group, usually received more than one copy of each message.
I hope this helps improve the reliability of a network I've come to rely upon over the years...
Keep up the good work!
-----------------------------------------------------------------------------
Mixmaster II Reliability Issues & Test Results [Final Test]
-----------------------------------------------------------------------------
183 messages [4 copies] were sent through chains of 20 remailers with an
overall & final remailer reliability of 30% or greater. This was truly
a torture test that guaranteed every message an equal probability of crossing
a broken chain.
The results of this final test were in line with my earlier testing conducted in September & October. In a nutshell: choosing a low reliability for the remailers resulted in a greater number of messages reaching their intended recipient, which, in both tests, was the "alt.anonymous.messages" news group. This is because the "Black Hole" remailers were almost always rated, in mixmaster stats, at greater reliability than remailers that were the most successful at delivering my messages.
The Mixmaster network had an overall improvement of 4% over my earlier testing, in which some batches of messages were sent through remailer chains with reliabilities of 98%, while other batches were sent through remailer chains with reliabilities of 50%. This time around, I used a reliability of +30%.
I didn't bother tracking bad chain data this time around because I found the data inconsequential in my earlier testing. In both earlier & present testing, all messages had an equal probability of encountering a bad chain, and a chain of 20 remailers, in this test, virtually guaranteed it.
Let me clarify the statement: "I found the bad chain data inconsequential in my earlier testing." It's not that the data aren't necessary in choosing a good chain. In fact, you can bet that the new Mixmaster client's ability to avoid bad chains was primarily responsible for all the 100% ratings in this testing cycle. [The developers really deserve a strong round of applause for their improvements to the Mix client & bad chain data.]
The reason the bad chain data are inconsequential to the testing is that all messages have an equal probability of encountering a bad chain that may develop over the many hours, or days, it takes for the messages to navigate 20 remailers.
My recommendations are the same as I previously outlined in my earlier test results, which I've included below...
Thanks again to all the developers & remops!
----------------------
November test results:
----------------------
(November 19, 20 & 21)
183 messages (4 copies of each)
-------------------------------------------------
Last Remailer | Sent | Arrived | % Reliability
-------------------------------------------------
antani 14 0 0
cripto 8 0 0
futurew 12 0 0
george 6 0 0
hastio 4 0 0
bunker 8 3 38
paranoia 16 14 88
bigapple 14 13 93
dizum 10 10 100
edo 12 12 100
freedom 5 5 100
frell 12 12 100
itys 15 15 100
metacolo 8 8 100
panta 15 15 100
randseed 9 9 100
starwars 9 9 100
tonga 6 6 100
-------------------------------------------------
Total 183 131 72
-------------------------------------------------
Date: Mon, 15 Dec 2003 19:13:53 -0800 (PST)
From: Len Sassaman <rabbi@abditum.com>
To: John Young <jya@pipeline.com>
Cc: cypherpunks@algebra.com
Subject: Re: An Analysis of Compromised Remailers
On Mon, 15 Dec 2003, John Young wrote:
> This came in response to Cryptome's posting of Len Sassman's
> comments on remailers.
(BTW, John -- while the threat originally started out as being about compromised remailers, my comments had little to do with that title. Perhaps "remailer security" would be a better index term for cryptome?)
> Over the past year, many remailer users have noticed that the reliability
of
> the Mixmaster type II network has steadily degraded. Although it may
well be
> the result of TLA interference, the remailer community's statistical
methods
> of selecting a "reliable" remailer chain contribute significantly to
the
> network's degradation.
There are conflicting opinions on that statement. For instance, have a look at this threat on alt.privacy.anon-server:
So, on one hand we have the claim that remailer reliability is degrading because of how we select reliable remailer chains, and on the other hand there is the claim that the reliability is increasing, because TLAs are the only entities competent to run reliable remailers. (Apparently, if you believe this theory, you also believe I work for the FBI.)
The facts are that the remailer network's reliability has increased over the past few years, largely due to the renewed development attention that Mixmaster has received.
> I ran tests in September, October & November, and provided the
Mixmaster
> developers & remail operators with the same results I've included
below. My
> testing was extremely simple: send a bunch of messages, and note which
The tests below unfortunately do not provide any really useful data. What is really being tested isn't the remailer reliability, but the "mail to news gateway" reliability. It would be much more useful for the tester to isolate which remailer/mail2news combinations are resulting in lost news, and post that data instead.
--Len.