Link padding and the intersection attack

Fri Aug 9 09:57:10 UTC 2002

<summary: arguing that n^2 padding as we know it now is not practical,
rather than does not work. Also clarifying a little the intersection
attack and questioning assumptions. Sorry. Fairly long post.>

> I talked to iang, adam, and jbash about link padding during Black Hat. I
> asked how to do less expensive link padding than n^2 while still getting
> some security.

> 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..

> 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! I think the security of that is not too bad, even taking
into account timing signature attacks (see Paul's last email), although no
analysis has been done yet.

I have an improved scheme, which is still expensive, but better than n^2
constant padding. Description here (I have posted it before)
http://www.cl.cam.ac.uk/~aas23/or.txt
(long)

I don't think there are any more attacks on it than the n^2 constant
padding. If anyone knows of any, please tell me.

> The basic argument is because of traffic confirmation. I've written some
> discussion/analysis below.

I include some notes presenting an alternative argument below.

> If there are lots of Alices compared to n (the number of routers), then
> it's not practical for Alice to link-pad to the cloud. Each Alice will
> want to link-pad a lot so she can get good throughput when she's actually
> using the system;

You can limit Alice to a fairly small constant bandwidth. If she wants
anonymity, better tolerate slow connections!

> but it's easy for lots of Alices to overload a node. We
> might strike an ok balance between throughput from each Alice and number
> of Alices -- but each Alice must become less happy as we add more of
> them. That's a bad trend.

I agree.

> We can help a bit by time-sharing the links (so Alice_1 can only send
> between 0 and 30 seconds after the minute, and Alice_2 can only send
> between 30 and 60, etc), but that doesn't lessen the pain significantly.
> (It also partitions anonymity sets quite nicely. I mention the
> time-sharing thing mainly because every person I've told this problem to
> proposes it as an answer.)

Absolutely.

> If the number of Alices is near n (equivalently, if many Alices run their
> own nodes), we may be in better shape. Welcome to p2p onion routing. More
> on that down the road.

Errr.. No, there is a flaw in your logic here, I think. If the number of
Alices is near n and we have p2p OR, then n^2 padding is not at all
practical.

> "If there are lots of users, padding from each Alice to the cloud is
> not practical."

Right. I would argue that given particular bandwidth constraints on each
OR, one could design a scheme to support up to A Alices and provide them
with anonymity. I also have a feeling that there exist A alices and
bandwidth constraints B on each OR such that there is no way of
configuring any arbitrary number of OR's to support the Alices having
reasonably fast connections. (though certainly, if you are willing to take
bandwidth down arbitrarily, you can, but that's a little pointless). So, I
think I will rephrase your statement to "secure n^2 padding schemes (With
Alice to 1st OR padding) do not *scale* well, but exist for small numbers
of users". It may be worhwhile to put some numbers in and see how many
users this is, but I have a feeling that number is too small.
Feel free to ask for more details if interested!

> "If this adversary can see the Alice connection and the Bob connection,
> he wins. If he cannot see both, he does not win."
>
> This is a strong statement. Am I trying to claim that if he can't see
> one of them, he doesn't know they're participating, so he can't tie them
> to the other one? Is there more to it?

I think there is nothing more. If he does not see the link, there is no
attack.

> Even regardless of link padding from Alice to the cloud, there will be
> times when Alice is simply not online. Link padding, at the edges or
> inside the cloud, does not help for this.
>
> In general, I'm talking about a time constant which describes how long
> it takes to launch a long-term intersection attack.

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.

> If Alice and Bob have a certain behavior pattern (when they're up, when
> they're down, when Alice makes requests to Bob) and we have some number
> of other users, each with activity following some distribution (eg
> poisson), how long does it take until the global passive adversary can
> be sure that Alice is talking to Bob?

He also needs:

* everyone else's activity distribution (both senders and receivers)
* some assumptions that long conversations are hugely more likely to
happen than single requests (is this even true for websurfing?) Ok, my
google and slashdot records are pretty long, but still.

Do you agree? I can do the analysis for a simple case...

> In particular, there are several factors which could improve the global
> intersection attack interval:
>
> * If there are more users, it may take longer.
> * If Alice's behavior isn't very odd (that is, if she behaves similarly
> to other users), it may take longer.
> * If other users are online more often, or Alice is online more often,
> or Bob is online more often, it may take longer.
> * If Alice sends requests to a bunch of people besides Bob, it may take
> longer (or it may not improve anything at all -- wouldn't it be neat to
> be able to show that.)
> * If Alice refrains from talking to Bob as often, then it may take longer.
> * If the other users send lots of requests, then they're more likely to
> hit Bob, which is good. If they send lots of requests but they don't
> hit Bob, do they help at all? (say, because they collide with Alice
> more often)
> * If Alice can convince somebody to send requests to Bob while she's
> offline, it may take longer. Does it help more to get random users to
> send the requests, or to get a small group to do it? What properties of
> the group help most?

Indeed. All of those weaken the attack, and are indeed the case for OR and
websurfing.

> Who wants to do some math and tell me the answers to all this? :)

Most of these look *hard*. But we need to decide what the reasonable
assumptions are first. As above.

A.

------------------
Andrei Serjantov
Queens' College
Cambridge CB3 9ET
http://www.cl.cam.ac.uk/~aas23/