Link padding discussion

[Andrei Serjantov]

Summary:

Clarification why any router and not the first COR in the route is likely
to be the point of collision and therefore bandwidth increase.

> > 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.
>
> OK - but this more than just optimisation. We may find that a totally new
> approach is needed to make it practical.

Entirely possible...

> > I don't see how you can identify which COR the connection starts at.
>
> OK there is probably a glitch in my understanding of your proposal.
> My reasoning is this, tell me where the problem is :
> We start with equal bandwidth on all links. When the traffic requirements
> increase, the entire network upgrades to a higher bandwidth.
> But this isn't done simultaneously. A passive adversary will spot which
> router is initiating the increase and know that a new circuit is being
> established that starts at that COR.

No. We start with equal bandwidth on all links. Initially, none of it on
the entire network is real traffic -- all is padding, network is empty.
First connection comes along. It can be handled without any increase --
just substitute the dummies on the appropriate links by real traffic.

Second connection arrives, say at router A. If the first connection has
used up l links, the probability that it went through A was l/m (m is the
total number of CORs). Now, even if the first connection went through
router A, there is a (m-1)/m chance that the link used by the first
connection and the second connection are different and bandwidth does not
need to be increased. Thus, the probability that the router who will call
the network to increase the bandwidth (which, as you correctly point out,
will be observable), will be the first COR of the second connection. In
fact, any other router on the second connection is as likely to be the
collision point (and therefore observed by the attacker) as the first COR
in the connection.

> > 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!
>
> Not true if my reasoning above is correct. Even with users having equal
> bandwidth we will be able to observe which COR started the increase.

Yes, but this COR will be a random one on the route. (as above)

> Also, I don't think you can rely on the fact that you only get an increase
> when there is no spare bandwidth. In a lightly loaded network you only
> need 2 circuits going through the same link to get the increase. My

Yes.

> instinct would be that there is a fair chance (>0.5) that the link will be
> full.

See above.

> > 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.
>
> OK that's another thread. I proposed a solution a while ago (Roger also
> proposed we use hashes) which hides bandwidth from CORs to some extent.
> But as Paul pointed out, this may not be enough to prevent volume
> signature attacks. But let's keep this to the other thread!

Yes, I am fully aware of this, and not thinkign about that right now.

> I haven't thought about this yet but I have a feeling we might be leaking
> too much information through such a protocol.

Ok, I will work out the details by tommorrow morning.

> > As I say, after a while, as individual routers run out of bandwidth
> >
> Yes OK but you still need a protocol to make sure the entire network is at
> the same bandwidth - or is that not important?

I'll defer answering that.

> I don't think there is need to be worried about the router being able to
> return to itself after 2 hops. It could end up anywhere in 2 hops and it
> won't be able to recognize the circular connection anyway.
>
> I think your argument is fine. Anyone else?

Ok, thanks. I hope this clarifies the point, and I will fold the above
into the document as soon as I get time.

A.

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