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.