Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.


Share this Page URL
Help

Round 3: Bandwidth Order Selection > Defender's Strategy. - Pg. 50

50 CHAPTER 2 Game Theory for Infrastructure Security: The Power of Intent-Based Adversary Models Round 3: Bandwidth Order Selection. Defender's Strategy. Round 2 focuses on the adversary's selection of c i , and devises a defensive strategy that forces the adversary to separate the compromised nodes into two groups, with c i = 0 and 1, respectively. The adver- sary, in response, computes an optimal allocation of compromised nodes between the two groups. In Round 3, we focus on the adversary's band- width selection strategy and aim at forcing it to reduce b i and therefore settle with a smaller suc- cess probability of the entry-exit linking attacks. The key idea for the defensive strategy is to add one step after the node selections: if the entry node has higher bandwidth than the middle node, then swap the entry and middle nodes to ensure that the entry has a lower bandwidth. We call this method bandwidth order selection. The premise of bandwidth order selection is that the adver- sary is forced to reduce the bandwidth of com- promised nodes with c i = 0, because otherwise it can compromise the entry node only if all three chosen nodes have b i b L . Adversary's Strategy. Given the defender's updated strategy, what does not change for the adversary is to assign bandwidth of at least b L to all exit-eligible nodes (with c i = 1). On the other hand, the adversary has to reduce b i for an exit- ineligible node to increase its probability of being chosen as the entry node. In particular, we derive the following theorem: Theorem 8. With stratified path selection and bandwidth order selection, the optimal strategy for the adversary is to assign b = b entry , where Equation 2-31 b entry = w 0R · 100 . n A · (1 - p c ) · (1 - 2w 0R ) · 100 + 2w 0R Adversary's Strategy. What stratified path selection does not change is the optimal value of the bandwidth to assign to the compromised nodes. The adversary can still increase the suc- cess probability of its attack by choosing a band- width as large as b L for all compromised nodes. The defender's adoption of stratified path selec- tion only affects the adversary's assignments of c i . In particular, we derive the following theorem. Theorem 7. The optimal strategy of the adver- sary is to assign bandwidth b L to all n A com- promised nodes, and to assign c i = 0 to p c · n A of them, where Equation 2-30 p c = 2 2 w 1R · d 0 - w 1R · d 0 - d 0 · w 1R n A w(b L )(d 1 - d 0 ) d 1 - d 0 , where d 0 = w 0R + n A · w(b L ), d 1 = w 1R + n A · w(b L ), and w 0R = i \ A ,c i =0 w(b i ) (i.e., the total weight for all bona fide exit-ineligible nodes). As an example of the optimal strategy derived in Theorem 7, when w 1R = w 0R , the optimal strat- egy for the adversary is to specify p c = 0.5. As we shall show in the experimental evaluation sec- tion, given the current distribution of Tor node bandwidth, the derived optimal strategy yields a success probability of 1% for the attack when the adversary is capable of compromising 1% of all Tor nodes. One can see that this is significantly lower than that after Round 1 (i.e., 5%). Observation from Round 2. A key observa- tion from Round 2 is that the anonymous routing system should draw the entry and exit nodes from separate pools, such that the adversary cannot "double-dip" a compromised node by making it exit-eligible. Although the separation is done based on c i in the above discussions, it may also be conducted based on other criteria. For exam- ple, when the majority of nodes are exit-eligible (i.e., with c i = 1), the system may designate a sub- set of them as the pool for exit node selection, and use the remaining ones along with the exit- ineligible nodes to choose the entry node. We will not elaborate on this option because it does not represent the current distribution of Tor nodes. Observe from the experimental evaluation sec- tion that, given the current Tor node bandwidth distribution, an adversary with 1% compromised node now only has a success probability of less than 0.7% for launching entry-exit linking attacks. Observation from Round 3. In the first two rounds, the selection of the entry, middle, and