Stopping Silent Sneaks: Defending against Malicious Mixes with...

Thread Model

• A adversary can observe all internal states of controlled mixes and can locally drop, inject or delay traffic. The adversary’s aim is to maximize end-to-end path compromise rates.

Bow-Tie Design

• A three-step pipeline: Sampling, Placement, and Path selection
• Assume an honest-but-curious Configuration Server (CS) that periodically (re)configure the network.
• Characteristics
  • Mitigating Client Enumeration
    • In general, users will fall victim to full path compromise the more they use the system. In other words, the adversary observes at least one message from every single user eventually.
    • Mitigate this by adopting the Guard Design from Tor. But, placing guard in the middle layer, unlike Tor (that uses the first layer)
  • Accommodating Network Churn
    • Putting the most stable mix nodes into the guard layer is important
  • Good performance & Low cost
    • By modelling the placement of mix nodes into a Bin-packing problem, improve the network performance by constrainting that the total bandwidth of each layer is approximately equal. It’s important because the bottleneck comes from a layer with the minimum bandwidth.
• Description

  1. Mixnet Initialization

     • Notations
       • $P_{bw}$: The sum of the bandwidth of all nodes in the candidate pool
       • $hP_{bw}$: The total bandwidth of the active pool sampled by the sampling function $h$
       • $\frac{h}{l}P_{bw}$: The total bandwidth of each layer in a $l$-layer Mixnet
       • Epoch $i$: We discretize time into periodic epochs, where the network can be reconfigured and clients updated with the latest topology.

     

     1. Initialize the Guard Layer
        • Sample a total of $\frac{h}{l}P_{bw}$ nodes weighted by bandwidth from the candidate pool
     2. Initialize the Guard Set $G$
        • Have 3 sets to minimize client exposure by remembering which nodes were used as guard, even if they go offline for a period. That is, clients can revert to a previously used but offline guard whenever it appears online again.
          • Active Guard $AG$: All nodes in the initialized guard layer
          • Backup Guard $BG$: Sampled an additional tolerance fraction $\tau$ from the candidate pool
          • Down Guard $DG$: Empty at this stage
     3. Initialize non-Guard Layers
        • Sample a total of $\frac{(l-1)h}{l}P_{bw}$ nodes from the candidate pool, and place them using 1-D bin-packing approach with the constraint that each layer has a similar amount of bandwidth, which packs all items into a minimum number of bins while the total size of any bin is not larger than the given capacity $c$.
          • Here, the capacity $c$ is set to be slightly larger than $\frac{h}{l}P_{bw}$ because it’s difficult to aggregate several indivisible entities to a precise cumulated bandwidth value.

  2. Mixnet Maintenance (by CS)

     

     1. Guard Set Maintenance
        • Offline nodes within $AG$ and $BG$ are moved to $DG$.
        • If $bandwidth(AG \cup BG) > T_{high}$, nodes in $BG$ that have never been selected into the guard layer are dropped according to the ascending order of bandwidth $\times$ stability.
        • If $bandwidth(AG \cup BG) < T_{low}$, add nodes to $BG$ by sampling nodes from the remaining candidate pool by bandwidth $\times$ stability.
     2. Guard Layer Maintenance
        • New $AG$ is generated by inheriting online guards from the old $AG$ and guards back online from the previous epoch’s $DG$ set.
        • To minimize the number of guards users are exposed to, the CS records the number of epochs of active operation as $t_{AG}$ for all mix nodes in $G$, and selects the most stable ones based on their WMTBF values.
        • If $AG$ still doesn’t meet the minimum bandwidth threshold, the CS samples some nodes from $BG$ by bandwidth $\times$ stability.
        • In the end, all nodes in $AG$ are placed into the guard layer.
     3. Non-guard Layers Maintenance
        • Offline nodes are remove from the active pool. Some nodes are sampled from the candidate pool to make up for offline nodes removed.
        • Non-guard layers are refreshed through the same procedure as initialization.
     4. Stability Tracking: Weighted Mean Time Between Failure (WMTBF) as used by Tor

  3. Mixnet Routing

     1. Client-side guard logic
        • Client samples guards proportional to their bandwidth and adds these to their guard list. To limit its growth and reduce the user’s exposure to malicious guards, the client only adds a new guard if all existing guards in the list are offline.
        • The client tries to reuse guards from oldest to the most recent.
     2. Path selection
        • Client selects nodes from non-guard layers weighted by bandwidth for better performance and security than the random selection.
• Bandwidth Discussion
  • The simplest way to determine the bandwidths of the nodes would be for the nodes to advertise their bandwidth, but in such case, adversarial nodes could advertise false information.
  • There exists previously proposed bandwidth measurement systems but it’s out of the scope for this paper.

Methodology

Security Metrics

• Time to first compromise: The expected time it takes until a user has their first message traverse a fully compromised path.
• Compromised fraction of paths: The expected fraction of total paths in the network topology
• Guessing entropy: How many mix nodes on average an active external adversary needs to compromise until she can fully observe the complete route of the message

Reference Algorithms

• BwRand: Sample mix nodes from the active pool with the probability proportional to their bandwidth and places these mix nodes into random layers with uniform probability (like Nym which samples nodes based on their stake)
• RandRand: Sample the active pool uniformly at random and places the mix nodes into a layer uniformly at random
• RandBP: Sample the active pool uniformly at random and assign mix nodes into each layer with the bin-packing placement algorithm