On Mon, Mar 12, 2012 at 5:38 PM, Mike Perry mikeperry@torproject.org wrote:
Thus spake Robert Ransom (rransom.8774@gmail.com):
On 2012-03-11, The23rd Raccoon the.raccoon23@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/BwAutho...
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....