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

[Aaron Johnson]

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 at torproject.org> wrote:
> 
> 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
> _______________________________________________
> tor-dev mailing list
> tor-dev at lists.torproject.org
> https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 495 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20151002/17983bb9/attachment.sig>