Re: analysis of RemailerNet

[jrochkin@cs.oberlin.edu (Jonathan Rochkind)]

At 8:57 AM 01/12/95, Wei Dai wrote:
>Alice is sending mail to.  After the first day, she can
>eliminate about half of the remailer users from the list of possible
>targets, because they, like the the random user above,
>received a mail even though Alice didn't send one out during the
>collection period of that batch.  Now, since Eve can eliminate
>on average half of the list every day, Bob will be the only person left on
>that list after about (log base 2 of one million) = 20 days.
>
>Suppose Alice sent out some different numbers of cover e-mail:
[...]
>               3               log base 1 of 1,000,000 = infinity!

Yeah, I think it made sense. Let me try to rephrase what you are saying in
English rather then math, to see if it's still what you are saying.
1) Attacker Eve wants to figure out who Alice is sending mail to.
2) She can weed people out by noting 'collection periods' where Alice sends
mail, but certain people don't receive any mail, and eventually arrive at
Bob.
3) If Alice sends mail out in _ever_ collection period, perhaps just to the
bit bucket, this method won't work, because there won't be any periods
where Alice doesn't send mail out.

Hmmm. The basic idea here is simply that you should send out lots of cover
mail, at least one piece in every collection period, to prevent this kind
of attack. Best, a random number of cover pieces, but at least one every
collection period.  Several thoughts:
1) If Alice and Bob are both corresponding with many people, things get
more complicated.  I tried to model it similarly to the way you modeled
your simpler situation, but got confused quickly.  This would be a good
thing to look at.  Alice sends and receives mail to several people other
then Bob, and same with Bob.  I'm not sure how this changes things, if at
all.
2) In real life, it's more likely for an attacker to want to discover Alice
knowing Bob then it is for him to want to discover Bob knowning Alice.
It's Alice who is being anonymous here by using the anonymous RemailerNet,
of course. I don't think this changes things either, but it's something to
keep in mind.