An Analysis of Compromised Remailers
This came in response to Cryptome's posting of Len Sassman's comments on remailers. - From: S Subject: Re: remailers-tla.htm Compromised Remailers, December 15, 2003 Date: Mon, 15 Dec 2003 16:16:17 -0700 To: [EMAIL PROTECTED] Message-Id: [EMAIL PROTECTED] 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 718 paranoia 41 1020 futurew33 921 edo27 925 starwars 54 2935 itys7 956 italy 7 1059 bog 3 1482 freedom 3 4594 tonga 510695 liberty 2 5196 panta 3 6996 bigapple310497 metacolo3 9997 bogg1 5298 dizum 210698 jmbcv 1 5998 frell 0 34 100 randseed0 3 100 --- Sub-totals39582568 --- 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
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: http://groups.google.com/groups?selm=8eb77bbdadfd2a6d1b21efabc1e1e090%40firenze.linux.itoe=UTF-8output=gplain 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.
Re: Compromised Remailers
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
Re: Compromised Remailers
Quoting Bill Stewart [EMAIL PROTECTED]: 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? Remailers are secure if at least one remailer in a chain is _not_ compromised... A case-in-point on this is the admin of the Frog remailer in 2001. He 'outted' a user who chained a message through both of Frog admin's remailers. The admin didn't like what was said and used his logs to match the sender with the decrypted outgoing message. With sendmail and verbose Mixmaster logs, this is trivial to do. It's also not unheard of for remops to log and cooperate to 'out' a spammer. If I were remailing a message that would get me sent to prison, I would definately use a Wi-Fi hotspot and use 3-4 chained remailers with random delays. By the time the message is delivered, it will be many hours/days since the message was sent. -- Keith Ray [EMAIL PROTECTED] -- OpenPGP Key: 0x79269A12
Re: Compromised Remailers
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. The source is available for mixmaster. However, Type II does not 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. Not necessarily. You don't have to be able to read a message to determine what it is. In the case of an amphibian remailer operator (who shall remain nameless) revealing the identity of someone using his remailer, this remop ran 2 of the three remailers being used. The chain went: A - B - C - D - E where A is the sender, E the recipient, and B and D are the remailers controlled by the same person. Also, if the message to E had been encrypted it wouldn't have mattered much in identifing who what sending something to whom. The remop could tell that a message from A coming in through B always resulted in a message going to C, and that such messages always had a corresponding message from D to E. The fact that the messages were encrypted to each remailer's key, and that the middle remailers was not compromised, did not protect the user. There were a some special circumstances to this, the biggest one being that A was sending a ton of messages, all of similar size, through the exact same chain. But it does show the problem with Type I reply blocks in use by the current system. 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. Of course they can't alter the encrypted text, but it may be possible to add text after the pgp-encrypted block to make tracking the messages easier. There's also the issue of taking a reply block and replaying it with new text in order to watch where it goes. [snip] 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.) Exactly. This is the case I was mentioning above. It shows that the if one remailer is legit your messages are safe line of thinking is not necessarily true. [snip] 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!) Type II is the current, though cypherpunk (Type I) are in use. II does not allow for reply blocks. Type III (mixminion) is in active development and allows for SURBs - Single Use Reply Blocks -- that will allow for nyms without having to store a set number of reply blocks that can be replayed (a la the current type I pseudonym setup) Anyway, just a few thoughts. I'm far from an expert on this so take everything with a large grain of salt. --B
Re: Compromised Remailers
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. 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_.
Re: Compromised Remailers
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
