Re: Link padding and the intersection attack

[Roger Dingledine <arma@mit.edu>]

On Fri, Aug 09, 2002 at 10:57:10AM +0100, Andrei Serjantov wrote:
> > Ian said that anything less than n^2 is equivalent to no padding.
> 
> Has he examined the "keeping connections to a constant number of OR's"
> scheme then? Maybe it provides less anonymity, but as far as attacks go --
> I don't know any new ones..

I believe Freedom was a non-clique topology. Their topology made
connections between nodes that were nearby latency-wise, to improve
latency. (Latency and jurisdictional arbitrage appear to be at odds.)

> > Adam went a step further, saying that n^2 really isn't any good either.
> 
> We can clearly come up with a very expensive scheme to protect against
> most attacks we know about -- long range user to OR padding, n^2. + Long
> term OP to cloud (not just first OR) connection. If anyone has any attacks
> on that, shout!

The same attack as before. :) See below.

> Aha. I would argue that Onion Routing does not need to protect against the
> long term intersection attack. I just don't see how the attacker can know
> that that B is talking to the same guy every time he is up.

The key is not that Alice is talking to Bob every time she's up. The
key is that when Bob gets talked to, Alice is more often online.

Scenario 1: 

Alice has a hotmail account 'foo@hotmail.com', which she logs into
periodically via the onion routing network. Our adversary (who may be
hotmail, may be colluding with hotmail, or may be monitoring the exit
connections from some of the onion routers) is also observing some of
the entry connections to the cloud. He notices connections to hotmail
which log in as foo, and records the users he can see entering the cloud
at that time.

The key here is that there are clearly-linkable events happening on the
Bob end that are probably done by the same person each time.

Scenario 1 also covers "Alice has an account on slashdot.org from which
she writes comments", "Alice uses Freedom to check her nym's mail at
the popserver", and "Alice mails a bunch of reply blocks to a Mixminion
nymserver so it can deliver her mail".

Scenario 2a:

A group of CIA agents are deployed around the world, and check back with
the cia.gov site periodically. The adversary observes as above. We don't
know which agent is named Alice and which agent is named Arnold, but we
don't much care. We build a set of the people who tend to be online when
a connection to cia.gov happens.

Scenario 2b:

Amnesty International allows anonymous story submission. Reporters risk
their lives going to rural Asian countries, and surface every so often
to submit a story, to pass back lists of contacts, etc.

Scenario 2c:

Dedicated political dissidents in the United States check an online
bulletin board for a list of upcoming peaceful protests and recent news.
When actually participating in the protests, they use masks to maintain
anonymity while exercising their rights. Our adversary observes as above,
building a set of suspects to arrest for terrorist acts.


In this scenario, our adversary does not have to be observing every
time a connection to Bob is made, and he doesn't have to observe every
connection. If he can only see a subset of the network but there's
sometimes an Alice in the subset he can see, the attack is slower but
still works.

So if the adversary can't ever see Alice and Bob at once, it doesn't look
like we have much to worry about. And if he sometimes can, then before
we have any padding system in place, I want some convincing argument
that it does something worthwhile in the above scenarios. I think some
of the items in the list from my previous post can improve the time
constant required to perform an intersection attack; but I don't know
by how much yet.

Another valid response is "Well then, don't use it like that." Then I
would be forced to come up with scenario 3, which would go something
like "Anne logs in every day and checks these 4 news sites; it would
make Anne unhappy to not be able to use our system for that".

--Roger