[or-cvs] Implemented link padding and receiver token buckets

[Paul Syverson]

Hi,

Contrary to appearance, I am alive and listening.

> 
> > > But then surely, if you want to find out the bandwidth of real traffic on
> > > the network, you just attack the network and then watch the traffic in the
> > > next few seconds and it will all be real traffic. I think you have to
> > > implement another one of these random back-off schemes I proposed: as the
> > > network is songested, put in fewer and fewer dummies and then you may
> > > rearrange the order of the dummies and real traffic in a fairly random
> > > fashion as well. Should I work out the details or are we not going to
> > > bother with such things? What I said above is a fairly weak attack, so I
> > > don;t mind either way.

Sorry for being dense, everybody else seems to get this, but I don't
understand. What is the attack? What does an adversary learn from
this? He does learn that the next few seconds are all real data before
the padding kicks in again, but what does that get him? I guess one thing
is that if he manipulates data immediately after doing this, then
he knows he is attacking real data not padding. More below.

> > Ok, here's my first pass at a fix, in terms of ease of current
> > implementation.
> >
> > Whenever you queue a data cell onto an outbuf, with some probability
> > (say, 20%) you also queue a padding cell (either in front or behind the
> > data cell). If you prefer, we can flip a biased coin, and as long as it
> > comes up "padding" we add a padding cell and flip the coin again.
> 
> Wow, That's a very different solution.... You are not padding to constant
> badwidth any more as before. And you are sending a lot less dummy traffic.
> Let me just observe that you did not *need* to do the above to solve the
> problem you outlined above which I summarise as ("If network congested and
> we keep queuing dummies regardless, latency increases and our buffers
> grow"). I have a solution to this problem below. As to the properties of
> the above dummy policy, a little thought is required!
> 
> Thought: The above policy does not hide the real bandwidth as it just puts
> out some (20% of the real traffic) dummies onto the network. This does not
> seem to achieve what we want (What do we want, I assume it is to hide the
> real traffic bandwidth?)... Again, if this is the policy, then you do not
> pad links on which no data is travelling.... Serious discussion is
> required on this. All come back to the threat model... Paul?
> 

Again, I don't see how the attack we're talking about reveals true
bandwidth. For an observer of the links it will reveal that the
initial traffic after the attack is "real traffic". But, he won't
learn when it stops and when the padding begins. And, if the adversary
is made of compromised CORs, he knows this anyway.

The coin-flips may be a good idea. But, until someone explains
this attack better to me, I'm happy with Roger's scheme from Tuesday
that makes sure there is never more than one flushlen worth of
cells in the outbuf.

On a related note: We're still talking about padding/throttling to
constant bandwidth on links, yes? We have always said that this was
unacceptable, and ZKS claimed empirical evidence of that. So, what
to do about it? 

How hard would it be to have some scheme like the following:
Constant pad to some low minimum, for some links it might
only be, e.g., a hundred bytes/sec. For others that can handle
it this could be much more. Let c be the current bandwidth,
and t the rate of real traffic.

Check during each interval. 
If t < .125c, then  half c
If .125c =< t < .25c, then flip a coin and half c w/ prob p
If .25c =< t < .5c, then double c with prob p
If t >= .5 c, double c
up to c = max capacity of the link

I just made up those numbers: savvyer folks can make it more sensible
to avoid wild oscillations etc. and also say what a reasonable interval is.
 
One concern is that when the network is relatively quiescent, a
passive observer could easily track the few connections if it is
on the links they travel over. A solution to this
might be a version of something like what Mat suggested a while back.

Coupled with the above, a node could monitor its links.
If inbound c is much higher than outbound (because it is the
last COR in a route) it could raise padding on some number (at least
one) of outbound links. It could similarly balance outbound
links so that there are at least n links with the same outbound c
at all times. I'm not sure I actually like this idea, because
evil CORs automatically get information about traffic not passing
through them this way. For example, if the network is quiescent
and somebody creates a connection from A to B to C to D, then
some neighbors of A will suddenly get an upsurge of padding,
followed by neighbors of B, etc. Suppose the adversary has some
neighbors in each of these groups and can
observe the outside connections to D. Then without owning a
single COR on the route, it will know that this connection that
it knows the ultimate destination to originated at A. If this
is a local-COR connection, then presumably we have revealed the
whole route. So, I'm not sure the "solution" isn't worse than
the problem it solves.

Still got other things to do tonight, so more tomorrow.

aloha,
Paul