[tor-dev] [RFC] On new guard algorithms and data structures
desnacked at riseup.net
Fri Aug 21 10:24:41 UTC 2015
s7r <s7r at sky-ip.org> writes:
Hello, thanks for the feedback!
I pushed some small updates to my branch based on your comments.
You can check them out here:
> 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:
> 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
>> 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.
More information about the tor-dev