[tor-dev] Analysis of the Relative Severity of Tagging Attacks

[The23rd Raccoon]

On Mon, Mar 12, 2012 at 5:38 PM, Mike Perry <mikeperry at torproject.org> wrote:
> Thus spake Robert Ransom (rransom.8774 at gmail.com):
>
>> On 2012-03-11, The23rd Raccoon <the.raccoon23 at gmail.com> wrote:
>>
>> > The crypto-tagger achieves amplification by being destructive to a
>> > circuit if the tagged cell is not untagged by them at the exit of the
>> > network, and also by being destructive when a non-tagged cell is
>> > "untagged" on a circuit coming from a non-tagging entry. It transforms
>> > all non-colluding entrances and exits into a "half-duplex global"
>> > adversary that works for the tagger to ensure that all traffic that he
>> > carries goes only through his colluding nodes.
>>
>> I wonder what the 'bandwidth authorities' would think of exits that
>> close circuits which They don't control:
>> https://gitweb.torproject.org/torflow.git/blob/HEAD:/NetworkScanners/BwAuthority/README.spec.txt
>
> I've been worried about various types of path biasing/circuit failure
> attacks for a while

Sorry, but path biasing is also a different class of attack than tagging.

> That said, the bandwidth authorities will actually compensate for this
> attack if the bwauthcircs=1 consensus parameter is set. Right now, the
> parameter is not set, because it is part of the PID feedback experiment
> that is currently disabled. Circuit failure statistics are still being
> recorded for posterity though. There are some high capacity relays
> exhibiting high rates of circuit failure right now, but that could also
> be CPU overload.

Here, let me help you out by scrawling some ascii-art drawings to
calculate what constitutes excessive amounts of circuit failure. In
the path biasing attack, we've got three nodes. Let's call the nodes
A, B, and C. I'll label the links to the nodes 0, 1 and 2. Let's
assume as usual that the adversary controls c/n of path selection. The
< symbols indicate a node choice opportunity on the part of clients.

--- 0< --- A --- 1< --- B ---- 2< ---- C -------

Each point 0, 1, and 2 is a point where the adversary can alter your
path choice. Let's just assume 0 is a safe route for now, and does not
bias node selection.

If node A (or node A's ISP) is biasing choice of B on link 1, node A
must fail 1 - c/n of the circuits that go through it in order to
ensure that B is chosen from colluding nodes. It can only allow c/n of
the circuits to get through to B (since B is represented by any of the
adversary's c/n nodes).

Similarly, node B must fail an additional 1 - c/n of the circuits that
attempt to extend through it. It too, can only allow c/n of the
circuits to get through to C.

That means that the adversary has to fail 1 - (c/n)^2 of client
circuits that attempt to use node A, and it's middle nodes B must fail
1 - c/n of clients circuits to ensure colluding node C is chosen. So
node A has to fail a lot of circuits. Even for a c/n = 20% adversary,
node A has to fail 96% of all circuits that attempt to use it.

However, in tagging, the adversary has a direct communication channel
to node C via the tag.

----0< ---  A ---- 1< ---- C -----

In this case (ignoring link 0), the adversary only has to close c/n of
the circuits that attempt to use it, giving a total circuit failure
rate of just 1 - c/n. For an adversary that controls 20% of the
network, this means failing 80% of the circuits that attempt to use
node A.

So, if you have a way to measure circuit failure reliably, you can in
fact detect the tagging attack, up to a point. It will be
significantly easier to detect full 3-hop path bias than 2. It would
be a good idea to solve tagging for this reason.

> I can turn the bwauthcircs=1 parameter back on independent of the PID
> feedback and see what happens, but if we could solve this with crypto,
> that would be better I think.

Is this even possible without revising the circuit level protocol? We
looked through the spec and didn't see anything that allows the
network to migrate to alternate cipher choices easily..

How quickly can the migration be done?

Otherwise, I suggest everybody start keeping track of their circuit
failure rates though major nodes....