Hidden Service (Time-Based) Path Selection
Summary / TL;DR
As the name suggests, time-based path selection is basically a strategy to select a path for mix packets that aims to reduce exposure to a fully malicious path over some period of timeT. This would be most useful for hidden services over mix. For more context, see previous posts on: hidden services over mix, and mix path selection. In here, we study and experiment with strategies that protect services from powerful adversaries, i.e., those that are able to perform Sybil attacks or compromise/coerce mix nodes in order to de-anonymize these services.
We consider threat models similar to Tor’s, and we use the vanguard strategy (proposal, spec, simulator) as a baseline on which we build and experiment with more complex strategies. Using the simulator with the current Tor vanguard strategy and its defined parameters gives about 0.19 (19%) probability of de-anonymization considering only the sybil attack and >0.8 (80%) considering the other powerful adversary models.
After experimentation with different strategies and parameters, two designs were especially promising in the mix setting (not as useful for Tor). The first is sampling complete paths and defining rotation per-path instead of per-node on the path. 4-hop paths with \max(X,X), X\sim U(1,48) hour lifetimes produced 0.0111 (1.11%) 30-day probability for Sybil only, 5-10% for other adversary models. The second strategy involves a fixed topology of potentially trusted nodes with a rotating set of active paths. We considered sparse topologies with different degrees. This strategy is more suited to services which can define their own set of nodes that they trust. Degrees 2 and 3 sparse topologies appear to be the most practical choices. Degree 2 limits exposure, whereas degree 3 provides greater path diversity, availability, and load distribution at a higher security cost. For a 5-5-5-5 degree-3 topology with 5 active paths, the 30-day rates were 0.62% for Sybil only and 20-40% for powerful adversary models.
These results are preliminary and will be tested again using our mix hidden service simulator with scripts/docs to make the results reproducible. Additionally, the mix path selection specification is currently being defined based on the outcome of this research.
Baseline strategy
To limit exposure to a malicious path, the simplest approach is to fix a few nodes on the path. However, to allow more flexiablity and probably better bandwidth, we would need to have a set of node for each fixed position so the hidden service would have more path options to choose from and possibly benefit from better bandwidth. This starting approach is based on the Vanguard spec and is adapted and used for session path selection.
The paths with fixed hops and sets would look like this:
Sender -> [L1] -> [L2] -> [L3] -> ... -> R -> receiver
where the size of these set is:K1, K2, and K3. R is a random mix node. The choice of the number of hops and the size of each set would result in different probabilities of de-anonymization. We will refer to this as the topology and use the notation x-x-...-x, where x is the size of the set. e.g., 5-5-5 would mean 3 hops, with each having 5 possible nodes to select from.
Threat model and assumptions
We could use this same strategy as is, however, the session-based strategy limits exposure during one bounded session. A hidden service has a different problem: it keeps the same anonymous identity across many sessions, peers and paths. Therefore, it has to survive longer than any one transport session. This makes it vulnerable to different issues:
- nodes on the fixed path, while supposed to be somewhat stable, might go offline.
- A powerful adversary can now “walk” along the path, starting from the client end to the service end, compromising each node in the path as it walks. This is bacause the nodes on the path are fixed and are vulnerable to compromise or concersion by strong adversaries.
- A problem with fixed paths in general is that nodes on these paths will know (to some degree) that they are part of some fixed path because of the high number of packets coming from one (or a small number of nodes) and going to one (or a small number of nodes). The degree of certainty depends on the size of traffic for the hidden service. The same problem was discussed in the Tor vanguard proposal. It is much worse for Tor since they have circuits while in Mix we have cover traffic which add some confusion. Note that while fixed paths are used for session as well, the adversary can detect that it is part of hidden service path (not a session) by the duration of the fixed path.
- Another problem with fixed paths is that one must be careful with path constraints i.e. which nodes cannot be placed in the path. For example, allowing the client to choose an arbitrary rendezvous point to be included as the last hop would result in the service not being able to create a path IF that rendzvous point is already a fixed node on the path. Tor is trying to deal with this issue in different ways (see tor proposal 354), but fortunately this doesn’t apply to our version of the rendzvous protocol. It is also a problem when some fixed hops on the path have much faster rotation time than other positions, then the adversay can detect that some nodes are never present in this fast-rotating position, therefore, it is likely that they are part of the other fixed path positions.
Therefore, for time-based path selection, we must make additional assumptions about the adversary:
- the adversary controls a percentage of mix nodes including trusted node although it is expected to be less for trusted nodes. Then the adversary can launch a Sybil attack easily against a service so that it can be placed in the path used by the service. We can assume that this attack is easy to perform. Note that by “Sybil attack” we just mean that the adversary controls a percentage of mix nodes and, as a result, has a chance to control all nodes on the path for a fraction of the mix traffic.
- the adversary is able to compromise/coerce nodes into becoming malicious, however, the cost of this is much more than Sybil attacks and also carries the risk of discovery.
Questions
Given these assumptions and adversary models, we must add an additional parameter to this strategy, which is the rotation time r for nodes in each hop position. This needs to be slow enough to lower exposure to malicious nodes, and fast enough to avoid giving a powerful adversary enough time to compromise/coerce the nodes on the path.
Therefore, we need to answer the following questions:
- how many fixed hops/layers are needed?
- how many nodes are in each layer (i.e., the set size)?
- what is the rotation time
rfor nodes in each layer? and is that rotation time different for each layer and fixed for all? - how to balance the anonymity requirement with other requirements e.g., availability, path diversity, and load distribution?
- what are the optimal parameters to be used for short (less than a day), medium (1-7 days), and long (15-30 days) hidden service lifetimes?
Game simulation
Tor’s Full Vanguards proposal uses a simulator to find an optimal topology for use in onion services. Their conclusion is that the best approach is to try to “incentivize” the attacker to launch a sybil attack first on L3 (since it is cheaper for an attacker) and then 2 compromise attempts on L2 and L1. This buys the service enough time to operate and end the service before the expected attack completion time. Therefore, the Vanguard proposal sets a long rotation time for L1 and L2, but a short rotation time for L3 to incentivize sybil attacks on L3. The Vanguard simulator tries to define concrete values for these rotation times and the sizes for each set in these layers.
Note that in order to estimate how long it takes for a powerful attacker to compromise/coerce a node, Tor uses different models, all based on a random number of days with different expected ranges:
| Model | behavior |
|---|---|
none |
Sybil only |
basic |
50% chance of compromise within 15 days, otherwise never |
APT |
75% within 15 days and 100% by 30 days |
FVEY |
50% within 2 days, 75% within 7 days, otherwise never |
rubberhose1 |
50% between 2 and 14 days, otherwise never |
rubberhose2 |
50% between 7 and 21 days, otherwise never |
We can attempt to answer our previous questions by considering a simulation game in the mix setting similar to Tor’s simulator. The simulation game is between the hidden service and the adversary (one of the above models). The adversary tries to win by de-anonymizing the service using any strategy it can i.e., a Sybil attack, a compromise, or a combination of them, whichever finishes first. The services uses the defined path selection strategy with given params. The simulation starts at time 0, time ticks every 100 sec, and it ends when the service lifetime ends or when the adversary wins.
Considering the fixed path strategy with sets (as mentioned above), we can define the adversary winning the game as:
- At least one malicious path exists in the current set of possible paths that the service samples from.
- The attacker walks the path, e.g., for 3-fixed-hops:
- Sybil attack on R
-> compromise OR Sybil on L3
-> observe active L2 candidates
-> compromise OR Sybil L2
-> observe active L1 candidates
-> compromise OR Sybil L1
-> service identity linked to network address
Compromise requires some time to pass before moving to the next level which depends on the adversary model.
Note: in Tor they add another condition for adversary win which is the guard node being malicious, however, for mix, a single malicious node on the path even if it is the guard/first hop doesn’t mean a direct de-anonymization because we have random delay and cover traffic.
Note2: the above is simplified win condition. In reality, walking the path is more difficult for the adversary to complete in the mix setting. Suppose the adversary tries to compromise L2 nodes, then by the time it controls it, it is likely that its L3 has rotated and now the adversary must wait to sybil L3 again so that it can discover the L1 nodes on the path. This is mainly because of delay and cover traffic in Mix (unless adversary uses some side-channel attacks of course)
Experiments
Ok now we can experiment with different parameters and simulate the results. As a reference, we can see the following results from running Tor’s vanguard simulator:
| model | Success by 30 days | median lifetime |
|---|---|---|
none (Sybil only) |
19.22% | > month |
basic |
77.68% | 10.64 days |
APT |
99.50% | 5.36 days |
FVEY |
94.82% | 1.54 days |
rubberhose1 |
75.92% | 12.62 days |
rubberhose2 |
66.58% | 22.77 days |
The parameters they use are:
| Parameter | Value |
|---|---|
| simulation runs | 5,000 |
| Duration | 30 days |
| Topology | 2-4-8 |
| L1 | 2 Tor entry guards |
| L2 | 4 second-layer Vanguards |
| L3 | 8 third-layer Vanguards |
| Malicious fraction | 10% in every layer |
| L1 lifetime | 90–120 days |
| L2 lifetime | \max(X,X), X\sim U(30,60) days |
| L3 lifetime | \max(X,X), X\sim U(1,48) hours |
It is obvious that with these parameters and all models, hidden services lifetime is expected to be much less than a month unless you consider only Sybil attacks. These params are also constrained to work under the Tor threat model. So we need to experiment with different approaches and params:
- We can experiment with different sizes for the sets and we don’t need to restrict the size of the first hop. The small (2 guards) is mainly a Tor requirement and we can experiment with any size for mix. we can possibly set the same size for all sets or reverse the sizes i.e. small set in L3 and large in L1.
- Tor path selection considers mesh-like connections between each layer. However, we can experiment with different degree of connections, e.g. sparse graphs, or fixed independent paths (basically a degree-1 topology).
- Experiment with rotation being independent for each hop and compare with complete path rotation (we fix paths, not hops).
Strategy 1: fixed paths
After lots of trials and errors, the most promising approach we observed seems to be:
- fix the size of all layers to equal to some constant
mi.e.,|L1| = |L2| = |L3| = m. The value ofmwill be configured based on the required availability and anonymity requirements. - every node in one layer is connected to only
dnodes on the next layer. i.e., producing a degreedsparse graph.dneeds to be small to get a low probability of selecting a malicious path. Best would bed=1making the connections look like 5 disjoint paths. - to construct a path, you sample a node from
L1and then follow its connection toL2if there is more than one option, you sample again and so on. - rotation time needs to be set for each whole path independently of other path. Setting a rotation time per node would result in some overlap which gives the malicious path more chance to be selected. i.e. a controlled outer node reveals only the next node on the same path, instead of exposing a complete set. It also limits the ability for an adversary to “walk” the path since the whole path rotates and the adversary must start over or complete the attack within a single rotation time.
Some promising parameter choices:
5 nodes per layer, 4 hops, d=1 (results in 5 paths), \max(X,X), X\sim U(1,48) hours rotation/lifetime:
Hidden service paths:
+-- Path A: A1 -> A2 -> A3 -> A4
+-- Path B: B1 -> B2 -> B3 -> B4
+-- Path C: C1 -> C2 -> C3 -> C4
+-- Path D: D1 -> D2 -> D3 -> D4
+-- Path E: E1 -> E2 -> E3 -> E4
| Model | Success by day 30 |
|---|---|
| Sybil only | 1.111% |
| Basic | 2.712% |
| APT | 5.006% |
| FVEY | 29.463% |
| Rubberhose 1 | 1.109% |
| Rubberhose 2 | 1.109% |
There is still room to increase the number of possible paths if needed for availability or path diversity:
| Adversary | 1 path | 5 paths | 8 paths | 9 paths | 10 paths |
|---|---|---|---|---|---|
| Sybil only | 0.223% | 1.111% | 1.772% | 1.991% | 2.210% |
| Basic | 0.548% | 2.712% | 4.304% | 4.829% | 5.350% |
| APT | 1.022% | 5.006% | 7.888% | 8.830% | 9.761% |
| FVEY | 6.704% | 29.46% | 42.68% | 46.61% | 50.21% |
| Rubberhose 1 | 0.223% | 1.109% | 1.768% | 1.987% | 2.206% |
| Rubberhose 2 | 0.223% | 1.109% | 1.768% | 1.987% | 2.206% |
We can try to write a formula to compute an estimate.
Let:
- m: number of complete paths kept active at any time
- L: number of fixed hops in each path
- \beta: probability that a sampled node is malicious
- T: hidden-service lifetime
- \tau: lifetime of one complete path
- N(T): total number of path generations sampled by time T.
Over time T, each path is expected to rotate 1+\frac{T}{\tau} times. With m active paths, the number of paths sampled is:
A complete L-hop path is malicious only when all L nodes are malicious:
The probability that one path sampled is not malicious is:
If the service samples n independent paths, the probability that none are malicious is:
Taking the complement gives the probability of at least one malicious path:
Using the expected number of paths from N(T) gives the approximation:
If we try to plug in the params from before:
- m=5 active paths
- L=4 fixed hops
- \beta=0.10
- T=30 days =720 hours
- \tau \approx 32.33 hours (this is the expected value when using \max(X,X), X\sim U(1,48) hours rotation)
then we get:
The simulation produced 1.111%, which is close to this approximation.
Strategy 2: fixed sparse topology
An alternative approach with more restrictive path selection: we can fix the topology with L layers and m nodes per layer, then configure the degree d based on the required anonymity and availability. Example:
Fixed 5-5-5 topology, degree d=2
L1 L2 L3
[A1] ───────────────► [B1] ───────────────► [C1]
└─────────────────► [B2] ───────────────► [C2]
[A2] ───────────────► [B2] ───────────────► [C2]
└─────────────────► [B3] ───────────────► [C3]
[A3] ───────────────► [B3] ───────────────► [C3]
└─────────────────► [B4] ───────────────► [C4]
[A4] ───────────────► [B4] ───────────────► [C4]
└─────────────────► [B5] ───────────────► [C5]
[A5] ───────────────► [B5] ───────────────► [C5]
└─────────────────► [B1] ───────────────► [C1]
Increasing the degree would increase the number of possible paths and limit a single failed node on the path to render that path unusable. If we consider these topologies:
5-5-5: three fixed layers/hops each containing 5 nodes5-5-5-5: four fixed layers/hops each containing 5 nodes
Then increasing the degree would give us:
| Topology | Degree 1 | Degree 2 | Degree 3 | Degree 4 | Degree 5 |
|---|---|---|---|---|---|
5-5-5 |
5 | 20 | 45 | 80 | 125 |
5-5-5-5 |
5 | 40 | 135 | 320 | 625 |
or we can just compute the number of paths:
where:
- m is the number of nodes in each layer
- L number of layers
- d degree
Once we have a set of nodes (possibly ones we trust), we can then restrict our path selection by fixing the number of active paths we can pick from this fixed topology. At any time we only have a pool of active paths sampled from the fixed topology, e.g. 5 active paths. Each path has an independent rotation time sampled as usual with \max(X,X), X\sim U(1,48) hours. Running the simulation shows this:
- The 5-5-5 topology (30-days):
| Adversary | Degree 1 | Degree 2 | Degree 3 | Degree 4 | Degree 5 |
|---|---|---|---|---|---|
| Sybil only | 0.52% | 1.91% | 3.6% | 4.385% | 5.41% |
| Basic | 14.42% | 28.16% | 33.48% | 34.5% | 35.4% |
| APT | 35.09% | 39.5% | 40.88% | 40.07% | 40.49% |
| FVEY | 26.1% | 38.35% | 40.22% | 41.0% | 40.66% |
| Rubberhose 1 | 14.53% | 27.94% | 33.76% | 34.70% | 35.24% |
| Rubberhose 2 | 10.96% | 20.28% | 24.83% | 26.02% | 25.92% |
- The 5-5-5-5 topology (30-days):
| Adversary | Degree 1 | Degree 2 | Degree 3 | Degree 4 | Degree 5 |
|---|---|---|---|---|---|
| Sybil only | 0.03% | 0.32% | 0.62% | 0.88% | 0.96% |
| Basic | 7.45% | 17.98% | 19.96% | 19.64% | 19.49% |
| APT | 27.06% | 36.90% | 36.67% | 37.28% | 37.09% |
| FVEY | 21.04% | 37.09% | 39.25% | 40.05% | 40.39% |
| Rubberhose 1 | 7.50% | 16.93% | 17.88% | 17.25% | 17.35% |
| Rubberhose 2 | 2.67% | 6.69% | 7.35% | 7.42% | 7.68% |
Note that here we fix the topology and only 5 pick paths from the fixed nodes. i.e. we don’t keep adding new nodes over time, but rather pick new paths over time from the fixed topology. This gives much less probability because we are not exploring the global mix network and are restricting our paths to this smaller “network” topology which is made up of nodes we possibly trust.
As can be seen above, degrees 2 or 3 would be good choices. Degree 5 is basically a mesh with the same probability as selecting random paths from a set of trusted nodes. The main improvement is in restricting the connections between the topology layers and the number of active paths. In addition, rotation being per-path instead of per-node prevents path walking and forces the adversary to restart (or compromise a larger number of nodes, risking itself being discovered). This allows us to use more nodes in our topology, therefore preventing/making it difficult for the adversary to compromise the larger set of possible nodes.
We can compute the probability of de-anonymization for a fixed topology in the same way as we did in the previous research post for the K/M strategy since both approaches fix a set of nodes for each layer and do not rotate them. Though we expect the probability to be much less for degrees below 5 here, so that formula can be considered an upper bound.
Availability
The availability can be estimated if we have some expected uptime for the nodes we pick. Tor does this by measuring what they call “Weighted Fractional Uptime (WFU)”. A similar measurement can be done or mix nodes. If we assume nodes on the path have WFU of about 95%, then we can estimate the availability of the hidden service over a month for varying number of paths:
Assuming that each node has an independent WFU value equal to a, L is the number of hops/layers, and m is the number of nodes in each layer. Then, one path is online with probability:
All m paths are offline with probability:
Therefore, expected service availability is:
| Paths m | Expected availability |
|---|---|
| 1 | 81.450625% |
| 2 | 96.559207% |
| 3 | 99.361754% |
| 4 | 99.881609% |
| 5 | 99.978039% |
| 6 | 99.995927% |
| 7 | 99.999245% |
| 8 | 99.999860% |
| 9 | 99.999974% |
| 10 | 99.999995% |
We can see that 5 gives a good balance of availability and de-anonymization probability, but this depends on the expected availability for each node in our active paths or fixed topology.