A. Johnson:
It seems to me that we want to defend against (at least) two different attacks here:
Sybil attack:
...
Coercion attack:
Yes, I also am currently thinking about the problem in this way.
Unfortunately, it doesn't really make sense to add two '5 day guards' in a circuit, since a Sybil adversary has equal chances to pop at the guard nearest to the HS.
Yup.
- While more hops are useless for Sybil attacks, they actually help
against coercion attacks. Unfortunately, they only add 5 days per extra hop to the time to deanonymization.
And yes again. In this model, an ultra-mega-secret HS should use a long chain of guards. Of course, at some point, it is easier to do a congestion attack to identify the first guard being used by the HS. That is still a win, though, in that such an attack takes more technical skill and effort.
I think this brings up another good point about hidden services that the "you must use a single guard forever" model causes us to ignore.
Imagine if we had k-Conflux routing, where you could pick 1-k guards, and send packets to a single exit or RP.
Under this model, congestion attacks would be more difficult, because you have to also do the combinatorics to choke out the Choose(N, k) combinations of k of N total guards. If you only choked a subset, conflux would rebalance to the remaining free paths (assuming good, responsive flow control).
- It seems that coercion attacks are noisy. At least in this case,
relays got seized (why?) and people got notified that something was going on. It would be nice if we could make coercion attacks even more noisy, so that adversaries can't do them without tipping off the whole network.
I’m not optimistic about this. Surveillance is no good if the target is aware of it, and so it can be expected to be difficult to detect.
- The more I think about this problem, the more I realize that our
solutions are quite hacky. Maybe guards are not the right layer to fix this problem, and we should try to fix the guard discovery problem in circuit establishment as Mike has been suggesting? Unfortunately, the virtual circuits idea seems hard to analyze and do securely.
What do you mean by "the guard discovery problem in circuit establishment”? Do you mean using some level of traffic padding to make it difficult to determine when your relay is directly observing an HS guard? This seems straightforward to do just by making every relay see the same type and number of cells in every non-terminal position in the circuit during circuit creation (some will have no effect, detectable only by the last relay). I do worry about how the cell RTTs could still leak your relative circuit position. Ignoring that, maybe you can make it so that the adversary either (i) has to start surveillance on an observed hop and hope that it is a relatively static guard close to the HS or (ii) has to wait until some relay is observed *multiple* times from the malicious relays to be sure that it is in some layer of guards for the targeted HS.
I think padding and other defenses against introducing active side channels are fine longer-term plans, but I think what George means is that we should re-design HS path selection specifically for this guard discovery threat, taking it as a given that the adversary is able to use *some* side channel to determine that it is in the path and knows its position.
While I find passive timing attacks skeptical at scale, I am not so crazy as to believe that it is impossible to *actively* encode a reliable side channel in a traffic pattern that you control (which is used in the HS guard discovery research). Conflux may also make these types of side channels more difficult to construct, but I suspect that just means you have to send more data as an attacker. Since you can send a bunch of data at the HS for most application layer protocols (HTTP POST comes to mind), this is probably not a huge barrier.
After reading your back-of-the-envelope calculations on node rotation and guard lifetime for multi-tiered guards in your parent reply, I think that it stands to reason that some topology like this is best (with Conflux):
HS -> Guard_1 -> Guard_2 -> Guard_3 -> RP
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).
Based on your math in your parent reply, this now does strike me as superior to what I actually proposed with "virtual circuits", since if the whole virtual circuit had a lifetime of hours, you'd still have only days before the adversary ended up in the Guard_2 position.
I would prefer if we had closed-form or code-based versions of this calculation, though, so we could play with set sizes and lifespans for the 3 hops. We also want to play with questions like "How many circuits should we use at a time?" and "How big should the set of middle nodes we choose from be?" Making all of that parameterized will help us tune it. Heck, the surface might even be plottable or traversable with gradient descent.