[tor-dev] Defending against guard discovery attacks by pinning middle nodes

Wed Nov 12 19:45:29 UTC 2014

George Kadianakis <desnacked at riseup.net> writes:

> Mike Perry <mikeperry at torproject.org> writes:
>
>> A. Johnson:
>>> >> The idea would be that Guard_3 would rotate on the order of hours,
>>> >> Guard_2 would come from a set that is rotated on the order of days
>>> >> (based on the expected duration for the adversary to become
>>> >> Guard_3), and Guard_1 would rotate on the order of months (based on
>>> >> the expected duration for the adversary to become Guard_2).
>>> > 
>>> > Why set guard 2 to expire in days? If that is less than surveillance
>>> > speed, then once the adversary had guard 3, it’s game over.
>>> 
>>> Sorry, I should have stated this more clearly as "If that is greater
>>> than the time needed for surveillance”. And I can imagine rotating
>>> guard 2 faster than guard 1 for performance reasons (faster rotation
>>> more quickly takes advantage of new capacity in the network). But the
>>> only reason that I can see treating guard 2 differently than guard 1
>>> is that you judge the “cost" of the attack starting from guard 2 to be
>>> higher, thus compensating for the increase in attack speed. That is,
>>> if guard 2 rotates to a malicious relay, the adversary still has to
>>> identify and then do a targeted compromised of guard 1, while if a
>>> malicious relay is selected as guard 1, then the target HS can be
>>> relatively easily observed directly. Such an argument is hard to
>>> evaluate carefully, because the costs in terms of added technical and
>>> legal complexity are hard to estimate. For example, at what point is
>>> it “cheaper" to run more malicious nodes and/or wait longer in hopes
>>> of obtaining guard 1 than to try and identify guard 2 but then have to
>>> perform surveillance on an identified guard 1?
>>
>
> Hello,
>
> I'm also a bit confused for similar reasons as Aaron. I think I'm
> missing something.
>
>> Well, based on your analysis, I was actually proposing a hybrid scheme
>> somewhere between "virtual circuits" (which win out for load balancing)
>> and "two layers of single guards" (which may win out for security, but
>> only if you make certain assumptions about how the adversary can
>> compromise nodes). Going back to my diagram:
>>
>> HS -> Guard_1 -> Guard_2 -> Guard_3 -> RP.
>>
>> The idea is that Guard_1 is a single node that you choose and keep for
>> O(6 months, or as long as possible), but Guard_2 actually comes from a
>> set of 3-6 or so nodes that you keep for O(weeks), and Guard_3 you
>> rotate something like O(hours).
>>
>
> Let me analyze this scheme with the simple model from here:
> https://lists.torproject.org/pipermail/tor-dev/2014-November/007728.html
> (which is closer to your "it's likely quiet and/or quick to compromise
> a node" threat model since the adversary can compromise a node in 5
> days and no one notices).
>
> Let's say that the 5% adversary starts from the RP and needs to walk
> the chain up to the HS:
>
> Guard_3 rotates fast, so Adversary does a Sybil attack against
> it. Let's say that you keep Guard_3 for a day (keeping it for less is
> even worse), a 5% Sybil adversary will have entered that circuit
> position with 50% chance after about 14 days. So now he knows Guard_2.
>
> Guard_2 rotates in weeks, so it's faster for the adversary to do a
> coercion attack that only takes 5 days. After 5 days Guard_2 is
> compromised and the adversary knows Guard_1.
>
> Another coercion attack (5 days) is enough to compromise Guard_1 and
> the adversary has deanonymized the HS. Total time: 24 days.
>
> If you check 007728.html, I suggested some rotation speeds that
> "maximize" the time to compromise in this totally arbitrary security

* just to get notation right, I meant "time to deanonymize" there.

> model. With the 5 days coercion attack time, I couldn't get it to more
> than 75 days... which is less than a summer time.
>
> BTW, this security model might be bollocks.
>
> Let's now consider another arbitrary security model where the attacker
> can't do coercion attacks and can only rely on Sybil attacks. In that
> case, rotating Guard_2 faster than Guard_1 is a bad idea, since the
> attacker will be able to penetetrate the Guard_2 circuit position faster.
>
> What is wrong with our security models and what other security models
> are there? Can you find the time to compromise of your scheme under
> _your_ security model?
>
> Like Aaron, I believe that in most (all?) security models, the final
> hop needs to rotate a tiny bit faster than the time it takes the
> adversary to do a coercion attack, so that the adversary is forced to
> do a sybil attack. However, in subsequent hops you need to do slower
> rotations because you really don't want to get Sybil'ed in the first
> or second hop.
>
>
>> The reason they then are "treated differently" in terms of rotation
>> lifespan is that this hybrid scheme naturally exposes you to more of the
>> network in a given time period in the Guard_2 position, and even more in
>> the Guard_3 position. So these two positions would have shorter
>> durations for a given probability of compromise (by selecting a
>> malicious node), simply because they rotate faster.
>>
>> In other words, these timespans are based entirely on compromise
>> probabilities over many rotation periods, and have less to do with
>> how long it takes to compromise a node once you discover it.
>>
>> The hope behind my reasoning is that if it is incredibly likely for you
>> to rotate your guard(s) before they are discovered, guard discovery
>> attacks lose their value.
>>
>> OTOH, perhaps I am reasoning about this wrong, and it is operationally
>> better to stick with a guard node in the second position for as long as
>> you stick with your first guard. In my mind, having identical rotation
>> periods is only better if you subscribe to the theory that compromising
>> a node is a noisy process, and unlikely to succeed in repeated
>> succession. In which case, you probably just want a static route of
>> exactly three (and only three) guard nodes, fixed for the lifetime of
>> your HS. At least, if you want the most security in this threat model.
>>
>> Does this make sense?
>>  
>>> So I would argue to protect guard 2 as much as guard 1, and then look
>>> for other, better understood, methods to improve performance. Some fun
>>> methods that come to mind are (i) carefully choosing number of primary
>>> and secondary guards and (ii) trying to reduce the HS path length, and
>
> It's interesting to reduce the HS path length, but that would reduce
> the length of the chain that the adversary has to walk, which is bad :/
>
> The rendezvous model is a bit restricting isn't it :(
> _______________________________________________
> tor-dev mailing list
> tor-dev at lists.torproject.org
> https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev