-----BEGIN PGP SIGNED MESSAGE----- From: Louis Cypher (alt.anonymous.messages) In this message I will analyze message reordering in remailers, and traffic analysis in remailer webs. Remailers which immediately resend incoming messages provide no security against an attacker who is able to watch all traffic to and from the remailer. Two proposals have been suggested to solve this problem, latency and reordering. In recent discussions, the consensus was that message reordering was superior to (and the actual intent of) latency. Reordering is not sufficient, a form of latency is required to make it effective. In this analysis, I assume that the reordering is accomplished by keeping a group of n messages at the remailer, and sending a random one whenever a new message comes. This is superior to simply waiting for n messages to arrive, then sending them all at once (I will show this later). The attack on the reordering remailer is simple. The attacker sends a stream of marked messages through the remailer. After the waiting messages have been flushed out, any incoming real message will be flushed out of the remailer before more arrive, allowing it to be uniquely identified coming and going. The defense against this is to only check the group and send excess messages after a time delay. This delay should be the typical time for n real messages to arrive. A mixing of approximately n messages is ensured by this process. If there is no attack, then the mixing is not quite as good as keeping a group of 2n messages. Here is the math on the reordering schemes: 1) Wait for n messages, then mix and send them all. The message is known to be one of those 10 (duh). 2) Keep a group of n messages. Send one of the n+1 when a new one arrives. The message could be any message ever sent after arrival. That is not useful. How many messages does it take before we are 90% sure that the message has been sent? prob that the message has not been sent after x messages is (n/n+1)^x Prob that it has been sent = 1 - (n/n+1)^x Messages till 90% prob: x=ln(.1)/ln(n/n+1) For n=10, x=24, which is much better then 10 for scheme 1. 3) Accumulate b messages, then send a of them (Scheme 2 is a=1, b=n) x = ln(.1)/(ln(a) - ln(b)) This gives the largest x for a=1. In my example of how to defend against the flood attack, a=n, b=2n x = 33 This is misleading, because it will introduce twice the delay as scheme 2. Given the same delay, a=n/2, b=n, one finds that x=16.6 That is better than batching, but not as good as scheme 2. The smaller x is worth it, because a reordering of at least some minimum number of messages is ensured. Some writer proposed changing n randomly to protect against this attack. Obviously that would not work. The attack will consist of many many more than n messages. The second issue for consideration is: Given a web of perfect remailers, how easy is it to identify corespondents? Tim has been asking this one for a while. I assume that there is sufficient traffic through all remailers that any message entering the web could be any message leaving the web. This can be achieved, even with light traffic, by sending fake messages through the web to bit buckets. While they do not improve the security of the web as a whole, they help ensure that no tracking of messages within the web is possible, forcing it to be treated as a black box. I assume that no correspondents are remailers themselves, and that all communications are random (random times with random people). This assumtion that all communications are uniformly distributed is terrible but.... This analysis only applies to indistinguishable messages. Each standard packet size can be thought of as having its own black box (a good argument for message splitting and having only one packet size). To simplify the problem, I am going to treat the web as though it were clock driven. Some number of messages enter and leave the web each "tick" with no messages staying in the web between ticks. This is a reasonable approximation, with the "tick" being the mean time of passage through the web. Define "f" as the fraction of remailer using population sending a message in a given tick. This is also the probability that any individual will send a message in a given tick. The probability of a given pair of corespondents in a given tick is f^2 The probability of a pair of corespondents occurring m times in n ticks is m p= 1 - Sum [(f^2)^i (1 - f^2)^(n-i) n! / (i! (n-i)!)] i=0 Lets put some numbers in there. If people send 1 message per day on average, and one tick is 30 min., then f=1/48. If you watch the web for a month you will see 1440 ticks. If the chance probability of your sending m messages to your co-conspirator is too small then you have been nabbed. The condition for that is: p << (1/population) The results for m=0 to 12 (using the above numbers) are: m = 0 p = 4.64811E-1 m = 1 p = 1.30173E-1 m = 2 p = 2.56257E-2 m = 3 p = 3.86587E-3 m = 4 p = 4.71498E-4 m = 5 p = 4.81967E-5 m = 6 p = 4.23687E-6 m = 7 p = 3.26538E-7 m = 8 p = 2.23961E-8 m = 9 p = 1.38336E-9 m = 10 p = 7.77044E-11 m = 11 p = 4.00273E-12 m = 12 p = 1.91774E-13 So, for a remailer using population of 10,000 you had better send less than 5 messages per month to your accomplice. This only gets worse the longer you keep it up. You can not send 4 per month, month after month. Louis Cypher -----BEGIN PGP SIGNATURE----- Version: 2.6.2 iQCVAwUBLybfL6yHUAO76TvRAQFhEwP+OMBMyESk97mVPNJMsoECl0YiJY+xnOqs PHu3OT6j7igdu64NsAHxduwBLmArpgOFXEtrMBwXTkxzUZq6holJdQ+GPtQi787x WtXhV2KkipW6z67TMxzjdSN7cVluQiMpnNhTSOpGUDcM8no3JD8/Ti1ficwljVkH 5kNx6RWFEpI= =pRy3 -----END PGP SIGNATURE-----