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