[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.
> >
> 
> 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
-------------- 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/e2bac652/attachment.sig>