[tor-dev] [RFC] On new guard algorithms and data structures

[George Kadianakis]

s7r <s7r at sky-ip.org> writes:

> Hi,
>

Hello, thanks for the feedback!

I pushed some small updates to my branch based on your comments.
You can check them out here:
   https://gitweb.torproject.org/user/asn/tor.git/tree/src/or/guardlist.c?h=bug12595

> On 8/20/2015 2:28 PM, George Kadianakis wrote:
>> Hello there,
>> 
>> recently we've been busy specifying various important improvements 
>> to entry guard security. For instance see proposals 250, 241 and 
>> ticket #16861.
>> 
>> Unfortunately, the current guard codebase is dusty and full of 
>> problems (see #12466, #12450). We believe that refactoring and 
>> cleaning up the entry guard code is essential before we proceed to 
>> more advanced security improvements.
>> 
>> We've been working on new algorithms and data structures for guard 
>> nodes as part of ticket #12595.
>> 
>> In this mail I include some pseudocode for this new algorithm with 
>> the hope that it will act as a draft for implementing these 
>> changes. You can find the pseucode here:
>> 
>> https://gitweb.torproject.org/user/asn/tor.git/tree/src/or/guardlist.c?h=bug12595
>>
>>
>> 
> A short description of the algorithm is included on top, and then
>> various methods and functions are prototyped underneath to make
>> the logic more concrete.
>> 
>> Apart from the comments and XXXs on the code, here are some more 
>> thoughts on this work:
>> 
>> - This new design focuses on protecting against path bias attacks, 
>> by slightly damaging our reachability.
>> 
>> Specifically, the old design is better at recovering in filtered 
>> networks, because it will keep on adding new nodes till one 
>> succeeds. In this new design, we will not try more than 80 relays 
>> per time. So if none of them passes the filtered network, bad luck 
>> no Tor.
>> 
>
> This number looks good to me. Could you make it dynamic, so in the
> future we don't have to change this code? Being optimistic here about
> Tor's scale in the future. E.g. calculate:
> GUARDS_ATTEMPTED_THRESHOLD == 'total no of Guards in a consensus' * 0.05
> and change update it in our 'State' every time we receive a valid new
> consensus document which changes it. Should be slight updates here,
> like maybe 78, maybe 82, etc. If the result of the above calculation
> is not an even number, approximate with deduction (e.g. if result =
> 81,6, set the limit to 81).
>

I added a comment to make both GUARDS_ATTEMPTED_THRESHOLD and PRIMARY_GUARDS
consensus parameters, so that we can change them if we ever understand this
problem better.

>> While this failure mode should not happen much, it's bad news for 
>> users behind FascistFirewalls which are actually quite frequent. A 
>> quick fix here would be to always add an 80/443 guard on our list, 
>> however as it stands only 30% of the guards are 80/443 guards, so 
>> this has bad anonymity consequences.
>> 
>
> Bad idea for anonymity and also not a very good idea regarding to load
> balancing (80/443 Guards might get hammered more). We do have a torrc
> option for this, in case the should enable it so Tor will only look
> for 80/443 Guards, or use bridges.
>

I agree. However, most people don't know about the FascistFirewall torrc option. 

>> - To improve our algorithm and make it more robust we need to 
>> understand further what kind of path bias attacks are relevant 
>> here. The adversary here is a network adversary (like a gateway) 
>> that can block our connections to certain guards. What nasty 
>> attacks can this adversary do?
>> 
>> If we can't find bad attacks here, then maybe we should stop 
>> worrying about those path bias attacks so much.
>> 
>> For example a threat here with the old guard logic, is that if we 
>> used this evil gateway just for 10 minutes (in an airport), the 
>> adversary could launch a path bias attack and force us to connect 
>> to her guard node. Then even after we left that airport, we would 
>> still stick to the evil guard node which is bad.
>> 
>
> That is why we have some primary guards which we retry for some time,
> and not remove them from the list if we cannot connect to them one or
> two times. Our network could be down or the Guard's network could be
> down, etc.
>

Based on your comments, I changed the reset timer for primary guards retrying
down to 5 minutes. I could also get behind the exponential backoff idea.

>> Also, an adversary that manages to own our guard using path bias 
>> attacks, then has further possibilites for biasing the rest of the 
>> circuit. What can this adversary do?
>> 
>
> Would it make sense for Tor to change Guard if it fails more than n
> circuits at a given time? If the attacker owns our guard and wants to
> path bias attack the rest of the circuit, since the client is the one
> who selects the path, it will cause a lot of circuit failures on
> client side - we should use this as a metric to detect this
> possibility and defend against it.
>

Yes maybe. Not sure if the path bias code currently does this. 

I will consider this as an orthogonal problem for now.