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.
I've added these results to Section 3.2.3 of the proposal in my remote, and also added the full python script used to generate all tables as Appendix A.
Here's the new piece of Section 3.2.3: https://gitweb.torproject.org/user/mikeperry/torspec.git/tree/proposals/247-...
Hm. how come the CDF is defined this way?
Specifically, why do we do the following?
For durations d greater than t days, we take the fraction of that rotation period's selection probability and multiply it by t/d and add it to the density. In other words:
I'm more familiar with the CDF definition used in commit acf86d7 but changed afterwards.
In an attempt to clarify this, we're not "doing" anything new. As the XXX comment in acf86d7 hints at, the new CDF is a more accurate representation of the probability that a certain time remains after the Sybil is successful, but before the second-level guard rotates.
Consider the single question: "What happens if the second-level guard was chosen with a 30 day lifespan? What is the probability in that single case of only 1 day remaining after a Sybil wins when the second-level guard has a 30 day lifespan?"
The answer to this single case is 1/30, because the Sybil has a uniform probability of winning at any given time point in that 30 day lifespan, that means that the probability of there being less than or equal to 1 day remaining at the point of Sybil success is 1/30 of that 30 day lifespan.
The CDF comes from summing up all of this fractional probability for rotation periods greater than 1 day, and adding the entire selection probability for 1 day.
Does this make any more sense, or less? Not really sure how to clarify the proposal text to explain this. Here is the original text again:
Because the Sybil attack on the third node is expected to complete at any point in the second node's rotation period with uniform probability, if we want to know the probability that a second-level Guard node will still be in use after t days, we simply sum up the fractional probability density for all rotation durations. For rotation durations less than t days, we add the entire probability mass for that period to the density function. For durations d greater than t days, we take the fraction of that rotation period's selection probability and multiply it by t/d and add it to the density. In other words:
def FullCDF(N, ProbFunc, t): density = 0.0 for d in xrange(N): if t >= d: density += ProbFunc(N, d) # The +1's below compensate for 0-indexed arrays: else: density += ProbFunc(N, d)*(float(t+1))/(d+1) return density