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 <mikepe...@torproject.org> wrote:
>
> George Kadianakis:
>> Mike Perry <mikepe...@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@lists.torproject.org
> https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
signature.asc
Description: Message signed with OpenPGP using GPGMail
_______________________________________________ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
