"A. Johnson" aaron.m.johnson@nrl.navy.mil writes:
As I've suggested before, I really really think you should also analyze an I2P-like scheme where HSs try really hard to maintain path persistence to their RPs for some fixed time period on the order of an hour (but which can be parameterized and analyzed to give the expected time for guard discovery).
...
In other words: instead of making many fresh RP circuits that can be destroyed, you pick a few RP paths, and maintain them for all circuits for a while, regardless of the activity that your HS sees, and also keep retrying these paths regardless of any circuit failure/teardown you experience. These RP paths would still have guards that last on the order of several months (or whatever duration matches the expected Guard discovery time from the analysis above), but the adversary would lose the ability to move up the chain by causing your circuits to fail from the client end or by driving a ton of activity at you.
I agree that it would be an improvement to remove the ability of an adversary to force the selection of new paths to the RP. For security purposes, it seems the same as adding additional layers of “guards” that have shorter expiration times. And that does suggest one benefit of *shorter* lifetimes for secondary or tertiary guards: you may make expiration faster than an adversary can begin surveillance. The trick is to make the expiration time just under the speed of surveillance. If expiration is too fast, the adversary can just as well wait for you to choose one of his relays.
Suppose the third hop from the HS was changed every hour, and the adversary controlled 1% of all consensus weight. Then it would take a little over 4 days in expectation to choose an adversarial relay and thereby expose the second hop. Assuming the second and first hops rotate slower than surveillance speed, the adversary can at that point move up the chain via surveillance to identify the HS. If the HS can hold onto that third hop for as long as a day, then it would take a little over 14 weeks in expectation for an adversarial relay to be selected.
These number don’t seem great to me, but they do seem like an improvement.
Good thoughts!
It seems to me that we want to defend against (at least) two different attacks here:
Sybil attack:
We want to defend against a Sybil attack where attackers sign up relays to the network so that they eventually become the guards (or second/third guards) of HS circuits. The suggested way to deal with this attack is to rotate guards slowly.
We currently rotate guards every 2-3 months, but we are considering changing this to 9 months or so according to proposal 236
Coercion attack:
However, we also want to defend against "coercion" attacks, where attackers can compromise (pwn/seize/etc.) guards of HS circuits. A way to solve this, assuming that compromising Tor relays takes non-trivial time, would be to rotate guards fast. The idea is that by the time the attacker has compromised a guard, the HS has already rotated that guard and moved to another one.
Let's say that compromising a relay takes 5 days. Then a good strategy would be to rotate every guard layer every 5 days.
The obvious problem here is that if you assume an attacker that can pull off both attacks, the proposed solutions are incompatible. A system that defends against one attack is left open to the other.
And I guess that's why the last few posts are suggesting to combine the two defences. They suggest having long-term guards (anti-sybil) near the HS, and short-term guards (anti-coercion) near the RP.
Ignoring all sorts of load balancing and bandwidth issues, let's consider the following circuit:
HS -> 3 months guard_1 -> 3 months guard_2 -> 5 days guard_3 -> RP
and see how an adversary would attack it:
The adversary starts off as being the RP, and hence learns the identity of guard_3 [0].
To learn the next hop, and since it doesn't have enough time to do a coercion attack, it has to do a sybil attack. A 5% adversary (like CERT) starts getting over 50% probability of becoming your next hop after about 13 rotations. So after about 2 months (13*5 days), the adversary will become your guard_3, and hence learn the identity of guard_2.
From that point, he just needs to walk the coercion chain for two
hops. So basically, after 5 days he compromises guard_2 and then after 5 more days he compromises guard_1. Total time to deanonymization is 75 days. Not good. FWIW, using the same model, the time to deanonymization with the current HS circuits is just 5 days, that is a single coercion attack.
Some notes:
* It seems that the only reason it took 75 days to the adversary is because the first hop took him 65 days to crack: Sybil attacks are slow in this case.
Unfortunately, it doesn't really make sense to add two '5 day guards' in a circuit, since a Sybil adversary has equal chances to pop at the guard nearest to the HS.
* While more hops are useless for Sybil attacks, they actually help against coercion attacks. Unfortunately, they only add 5 days per extra hop to the time to deanonymization.
* It seems that coercion attacks are noisy. At least in this case, relays got seized (why?) and people got notified that something was going on. It would be nice if we could make coercion attacks even more noisy, so that adversaries can't do them without tipping off the whole network.
* The more I think about this problem, the more I realize that our solutions are quite hacky. Maybe guards are not the right layer to fix this problem, and we should try to fix the guard discovery problem in circuit establishment as Mike has been suggesting? Unfortunately, the virtual circuits idea seems hard to analyze and do securely.
[0]: It seems to me that in all low-latency anonymity schemes based on rendezvous, the adversary is able to trivially learn the first hop of a chain that eventually leads to the HS.