Hello,
> "To improve our algorithm and make it more robust we need to understand further what kind of path bias attacks are relevant here...What nasty attacks can this adversary do?"
An gateway adversary which can filter the network can use guards to fingerprint you. This requires connecting to tor directly through the gateway mentioned.
By watching which guards are attempted from a preexisting list of guard. If these guards are then filtered, and the client changes location, then reconnects, the client will be identifiable by the (filtered) guards it attempts to use. It's not a mitigation to only use one guard here.
> "If we can't find bad attacks here, then maybe we should stop worrying about those path bias attacks so much."
Some types of attack are unavoidable. Detecting unobfuscated tor use in the case for including at least one 80/443 guard. The only concern I have is trying no more than 80 relay at a time still leaves a lot of room for fingerprinting (if those relay persist between bootstraps). This also raises the question of false positive and proving a gateway adversary is the source of interference. A simplification might be to have the client fail faster (than 80) and be forced to try bridges.
> "...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."
A mitigation for the airport analogy posed might be to base network location on routing characteristics. I know portable NLA is hard. If the location-characteristic route changes in some way (like change from airport to coffee shop), then consider location as having changed and also consider dropping airport guard.
> "Also, an adversary that manages to own our guard using path bias attacks, then has further possibilities for biasing the rest of the circuit. What can this
adversary do?"
With modified tor software, and having already compromised the gateway, an adversary can, over-time, game the entire path selection. The adversary has at least 10 minutes in which a tor client will prefer certain nodes for types of traffic. After compromising the guard, the adversary gateway, then direct their attention to the rest of the path. They need to avoid failing too much or another guard gets chosen. So fail the occasional node selection, and end up rebiasing the chance of selecting a bad relay/exit in the favor of the adversary. How much failure is required? Doesn't that depend on the parameters maintained by a tor client?
> "Also, I was not sure what CONNECTED_THRESHOLD was useful for, and there were certain engineering issues with it (Like, if that threshold is hit, we need a
logic that will *only retry the successfully connected guards*, and not all guards).
If you try *all* guards you make the fingerprinting mentioned above easier. Although even if you try successfully connected guards you run into this problem.
> "There is no log message warning the user of path bias attacks or bad network or anything. That's because there is no way to figure out what's the problem,
and issuing an alarming log message here would confuse and panic the user."
Maybe this could be simplified to a log entry to indicate guard rotation, or a guard which was previously up is now unlisted or down. Couldn't the old guard be tested by using the first non-failing circuit that follows? If it's connectable using this circuit you can say something is amiss.
regards
--leeroy