[tor-dev] Proposal 247 (Hidden Service Vanguards) Overhaul

[Mike Perry]

George Kadianakis:
> Mike Perry <mikeperry at 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-hs-guard-discovery.txt?h=guard_discovery_dev#n331
> >
> 
> 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




-- 
Mike Perry
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 801 bytes
Desc: Digital signature
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20150914/6b74b7d9/attachment.sig>