Link padding discussion

Andrei Serjantov aas23 at
Tue Jul 23 10:59:59 UTC 2002

> I've read you proposal and I have some questions ... i've thought about
> this for a bit but I warn you that I may be thick :)

No, they are good comments.

> OK so we'll consider link padding and connection padding (long range
> dummies, whatever the correct way of calling it is) separately - the two
> techniques guard against different types of attacks/adversaries.

Indeed. My thinking is that we do not do the connection padding right now
to make the whole thing actually practical.

> We also assume that the OP->COR connection is padded (for now) to constant
> bandwidth, with the possibility of that connection being fairly permanent
> to make timing attacks more difficult. Several circuits can then be
> multiplexed over that connection. The "constant" bandwidth can even be
> made adaptive to make it less expensive but let's leave that for now (in
> fact the problem of padding the OP->COR connection is then pretty similar
> to the one of padding COR->COR connections isn't it?)
> Is this the sort of thing you were assuming?

Yep. This is exactly what I was trying to say in the 3d paragraph of

> OK so you propose a discrete increase in bandwidth on the entire network
> as soon as current bandwidth requirements are exceeded on any part
> of the network.

Yep. I don't consider it a good solution (a continuous soultions
"feels" better), but let's stick with it for now.

> I don't quite understand what sort of quantum of bandwidth we are talking
> about. Users will have different bandwidth requirements and restricting
> them all to say 56kb/s is perhaps not practical, when some are on 1gb/s
> pipes.

Perhaps not. For the moment I do -- I really want to find a design which
is in some sense secure, and then we can optimise it from there.

> And as soon as we have different OP->COR bandwidths, we'll have to
> use different "quanta" when increasing network bandwidth.
> But then again, does this leak any more information? My first thought is
> no - the attacker will (again) just know that a new connection is going
> through and which COR it starts at.

I don't see how you can identify which COR the connection starts at.

Ah, in the case I proposed the attacker just knows that there is a new
connection, but not which COR it starts at (he just knows the COR at
which the first collision occurs).

If we let users have different bandwidths, you are restricting the
anonymity set to those with the same bandwidth. i.e. attacker sees network
load going up by 60k, therefore a user with 60k OP to COR connection has
initiated. (He could be "attached" to any COR).

> Say a user has a 1mb/s OP->COR connection to some COR which it uses as
> its first hop. Assume that there is no real traffic on that connection
> (so all padding gets killed at the COR). Now when we get a new circuit
> from that user, we'll increase the bandwidth on the COR->COR connections
> and the attacker will know that some real traffic is now going through
> the connection.

Not necessarily. Only if you hit a link on which there is no spare
bandwidth, the padding will increase from this COR. This is not much of a
problem if all users have the same connection bandwidth, but yes, if you
are trying to connect at 1mbit (and the COR is clearly not going to have
1bit of free padding on any one link), you are a bad boy!

> And he will be able to perform an intersection attack and do traffic
> confirmation without even compromising the first COR. If we don't leak
> this information the attacker would have to compromise the COR to
> observe that a new circuit is being established by the user. Does this
> make sense?

Sure. As I said to Rachel, because we are not mixing and our only tool for
protection is short-range dummies, we are not very secure against
compromised CORs. I propose to leave that for now.

> How do you propose the network backs off from the extra padding when the
> load decreases?

Yes, good point. We need a consensus protocol which allows CORs to spot
when there are no $n$ coincident connections on the entire network and we
can drop the bandwidth by one (or more) discrete chunks. I propose to run
it every few minutes rather than as soon a connection disappears.

> We also need to make sure that we prevent counting to infinity.

As I say, after a while, as individual routers run out of bandwidth

> George - is your work available for reading yet (sorry if I've
> missed a previous pointer to it)?

George is not around on this list I don't think. See my short paragraph in
the updated document and tell me if you agree.


Andrei Serjantov
Queens' College
Cambridge CB3 9ET

More information about the tor-dev mailing list