Re: Link padding discussion

[Matej Pfajfar <badbytes@freehaven.net>]

> > 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
> "Problem".
Cool.

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

OK - but this more than just optimisation. We may find that a totally new 
approach is needed to make it practical.

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

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.

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

True.

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

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.
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 
instinct would be that there is a fair chance (>0.5) that the link will be 
full.

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

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!

> > 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.
> 
I haven't thought about this yet but I have a feeling we might be leaking 
too much information through such a protocol.

> > 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
> 
Yes OK but you still need a protocol to make sure the entire network is at 
the same bandwidth - or is that not important?

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

Here's the paragraph :
> Now we do the following: allow each router to connect to c > SQRT(m)
> other routers (m is the total number of routers) and arrange the
> topology of the connections in such a way that there is a path from
> any node to any node via only one COR (including back to itself!)
> \footnote{Graph theorists should be able to prove that this is
> possible. The intuition is that each router is connected to SQRT(m)
> other routers and can therefore get to those. I am a little worried
> about being able to return to itself in 2 hops}. Now, an incoming
> connection having passed through 2 CORs is equally likely to end up at
> any COR. Just as in the full padding case, an incoming connection
> would be equally likely to end up at any COR after 1 hop. So, just
> double your route length to retain anonymity. (I am a little
> embarassed about this argument, it may be total rubbish, I have not
> checked it properly).

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?

Mat
-- 
Matej Pfajfar

GPG Public Keys @ http://matejpfajfar.co.uk/keys