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

[George Kadianakis]

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
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 :(