Hi Mike,
Here are some specific comments on the proposal, most of which I didn’t mention at the session yesterday.
Sec. 2: “When a hidden service picks its guard nodes, it also picks two additional sets of middle nodes `second_guard_set` and `third_guard_set` of size NUM_SECOND_GUARDS and NUM_THIRD_GUARDS respectively for each hidden service.” appears to conflict with “When a hidden service needs to establish a circuit to an HSDir, introduction point or a rendezvous point, it uses nodes from `second_guard_set` as the second hop of the circuit and nodes from that second hop's corresponding `third_guard_set` as third hops of the circuit”. I think the former statement should be amended to describe how the third sets are chosen for each guard in the second set.
Sec. 3.1: “A Sybil attack is noisy”. “Noisy” in the sense that it isn’t perfectly accurate or “noisy” in the sense that it is observable?
Sec. 3.1: “the Sybil success is almost immediately obvious to third layer guard, since it will now be returned as a rend point for circuits for the hidden service in question”. The third-layer guard isn’t the a rendezvous point. So how it is immediately obvious to the adversary when their relay is selected as a third-layer guard?
Sec. 3.2.3: I’m not sure that FullCDF() correctly computes the rotation CDF (even approximately). It should take into account the probability of observing a previous node that has selected the given rotation time (longer rotation times are more likely to be observed). So the probability that there are exactly t days until rotation of the observed node should be proportional to \sum_{i=t}^N Pr[X=i]. After normalization to make this a probability, the expression is (\sum_{i=t}^N Pr[X=i]) / (\sum_{i=1}^N Pr[X=i]*i).
Best, Aaron
On Sep 14, 2015, at 10:47 PM, Mike Perry mikeperry@torproject.org wrote:
George Kadianakis:
Mike Perry mikeperry@torproject.org writes:
Mike Perry:
I spent some time trying to clean up proposal 247 based on everyone's comments, as well as based on my own thoughts. Please have a look if you commented on the original proposal, and complain if I've not taken your thoughts into account.
I spent yet more time thinking about the new threat model and what the adversary's expectation for how long they will have after the Sybil compromise for the third guard completes before the second Guard rotates away, and I have some awesome results. It turns out that if we make all node rotation times fully independent, then the point at which the adversary wins the Sybil attack on layer 3 will be uniformly distributed with respect to the rotation period of the layer two guards.
With the parameters I specified, this means that when you sum the total remaining rotation expectations, the adversary will have at least a 19% probability that they will have less than a day remaining before the layer two guard changes on them after they win the Sybil, and at least a 32% probability that they will have less than two days before this happens.
IMO, this is great news, as it shows that we can indeed force the adversary to risk compromising/coercing nodes that end up having no utility to them with high probability.
While this is a very interesting idea, I wonder if it can actually hold true with the parameters in the proposal.
Let's say I'm an attacker that just Sybil'ed the third hop. I can trivially verify my success by doing a traffic confirmation attack. Since I own the third hop, I now learn the second hop.
I don't know how much time is left before the second hop rotates but I know that I have to compromise it somehow. So I start preparing my compromise attack which might take a few hours or days (by writing my exploit, getting a warrant, or ordering my goons to visit the data center).
As an attacker, before launching my compromise attack (actually launching the exploit, or entering the data center), I would again run my confirmation attack to ensure that the second hop hasn't rotated.
If the second hop has rotated in the meanwhile, tough luck. As the attacker, I will need to rerun my Sybil attack and start from scratch.
However, if the second hop has not rotated, then I can launch my compromise attack, which usually takes a few minutes to hours to complete. Those minutes or hours *are* the moments of uncertainty for the attacker, since if the hop rotates during that time the attacker is screwed (they just compromised something useless).
Unfortunately, I think that with the values in our proposal, I don't think we can rely that the second hop will rotate during those crucial minutes/hours.
What I'm trying to say is that only _very_ unlucky or stupid attackers will end up compromising something useless. What I consider more likely is that if it takes a while to prepare the attack (like write a whole exploit), then maybe the second hop rotates during the preparation time, but that won't expose the attacker.
I think you're right here. The attacker doesn't so much risk compromising something useless as they risk doing whatever prep work against a specific node for no reason. They only risk compromising something useless if the side channel attack *after* compromise takes a significant amount of time, but I think you're right in suspecting that it will not (my own guess is that such a side channel will probably take an hour or less). I'll update the proposal prose to clarify this.
Also note that the CDF I calculated is also an approximation based on discrete 1 day time values. In reality though, it turns out that basically every unit of time that goes while the adversary prepares their attack means an increasing probability that the node they are targeting will have rotated away during this prep time.
Again, as an approximation, the 1-day-resolution CDF tells us that the probability of the node having less than or equal to 1 day remaining in its rotation period is 19%. The rate of additional probability accumulation is not linear, but at least for that first day, basically every hour that goes by, a little less than 1% probability that the node is now useless has been added (give or take).
I debated trying to calculate the actual accumulation of probability per hour, but decided against it because it was too cumbersome and confusing to switch time units. I can still try to do this if we think it might help us choose parameters? Who knows, maybe different rotation parameters (such as a minimum of 0.5 days?) will accumulate more probability for the initial hours than others, and knowing that might help guide us (because as you state, those initial few hours are the most important ones).
Let me know what you think about this, and if it is worthwhile or would just confuse things further.
-- Mike Perry _______________________________________________ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev