[tor-dev] high latency hidden services

[grarpamp]

On Thu, Dec 11, 2014 at 8:26 AM, Michael Rogers
<michael at briarproject.org> wrote:
> * Which links should carry chaff?

First you need it to cover the communicating endpoints entry links
at the edges.
But if your endpoints aren't generating enough traffic to saturate
the core, or even worse if there's not enough talking clients to
multiplex each other through shared entry points densely enough,
that's bad.
So all links that any node has established to any other nodes
seem to need chaffed.

> We can't send chaff between every
> pair of relays, especially as the network grows.

Right, a full mesh is not necessary, only chaff the established links.
Whether that includes today's idle prebuilt paths, or only
upon actual user traffic, no idea yet.

> * How much chaff should we send on each link?

Today, all nodes have an idea that the most bw you're ever going
to get out of the system anyways is up to your pipe capacity,
whether you let it free run, or you set a limit... all within
your personal or purchased limits. So you just decide
how much you can bear, set your committed rate, and
fill it up.

> At present, relays don't
> divide their bandwidth between links ahead of time - they allocate
> bandwidth where it's needed.
> The bandwidth allocated to each link
> could be a smoothed function of the load

This sounds like picking some chaff ratio (even
a ratio function) and scaling up the overall link bandwidth
as needed to carry enough overall wheat within that.
Not sure if that works to cover the 'first, entries, GPA watching
there' above. Seems too user session driven bursty at those places,
or the ratio/scale function is too slow to accept fast wheat demand.
So you need a constant flow of CAR to hide all style wheat demands in.
I scrap the ethernet thinking and recall clocked ATM. You
interleave your wheat in place of the base fixed rate chaff of the
link as needed. You negotiate the bw at the switch (node).

> but then we need to make
> sure that instantaneous changes in the function's output don't leak
> any information about instantaneous changes in its input.

This is the point of filling the links fulltime, you don't see
any such ripples. (Maybe instantaneous pressure gets
translated into a new domain of some nominal random
masking jitter below. Which may still be a bit ethernet-ish.)

> That isn't trivial.

What needs work is the bw negotiation protocol between nodes.
You've set the CAR on your box, now how to divide it among
established links? Does it reference other CARs in the consensus,
does it accept subtractive link requests until full, does it span just one
hop or the full path, is it part of each node's first hop link extension
relative to itself as a circuit builds its way through, are there PVCs,
SVCs, then the recalc as nodes and paths come and go, how far
in does the wheat/chaff recognition go, etc? Do you need to drop
any node that doesn't keep up RX/TX at the negotiated rate as
then doing something nefarious?

> * Is it acceptable to add any delay at all to low-latency traffic? My
> assumption is no - people already complain about Tor being slow for
> interactive protocols.

No fixed delays, because yes it's annoyingly additive, and you
probably can't clock packets onto the wire from userland
Tor precisely enough for [1]. Recall the model... a serial bucket
stream. Random jitter within an upper bound is different from
fixed delay. Good question. [1 There was something I was trying
to mask or prevent with jitter, I'll try to remember.]

> So we'd still need to mark certain circuits as
> high-latency, and only those circuits would benefit from chaff.

High latency feels more like a class of service... not tied to
selective chaffing on/off. I'll try to reread these parts from you.

> Once you fill in those details, the chaffing approach looks pretty
> similar to the approach I suggested: the relay treats low-latency
> circuits in the same way as now, allocates some bandwidth to
> high-latency traffic, and uses that bandwidth for data or padding
> depending on whether it has any data to send.


>> I can't see any other way to have both low latency and hide the
>> talkers other than filling bandwidth committed links with talkers.
>> And when you want to talk, just fill in your voice in place of the
>> fake ones you'd otherwise send. That seems good against the GPA
>> above.
>
> The alternative to filling the link with talkers is mixing the talkers
> - - i.e. preventing the adversary from matching the circuits entering a
> relay with the circuits leaving it.

Well, there's the packet switched routing approach (mixed talking
in that regard) vs. circuit switched. You can do chaff with either.
But as way at the top, when you are the last hop and/or the net's
not busy, you've no one to mix with, and must flood chaff.

> But as I said above, when you get
> down to the details these approaches start to look similar - perhaps
> they're really just different ways of describing the same thing.

Perhaps.

> Some papers on this topic that I haven't read for a while:
>
> http://acsp.ece.cornell.edu/papers/VenkTong_Anonymous_08SSP.pdf
> http://www.csl.mtu.edu/cs6461/www/Reading/08/Wang-ccs08.pdf
> https://www.cosic.esat.kuleuven.be/publications/article-1230.pdf

I'll look to see if what I'm thinking is described.