Stopping Silent Sneaks: Defending against Malicious Mixes with Topological Engineering

Mixnets are a fundamental type of anonymous communication system and recent academic research has made progress in designing Mixnets that are scalable, have sustainable communication/computation overhead, and/or provable security. We focus our work on stratified Mixnets, a popular design with real-world adoption. The security of many designs rely on the anytrust assumption where at least one server in the user's path must be honest. We identify the critical role Mixnet topological configuration algorithms play for user anonymity, and propose Bow-Tie, a performant topological engineering design for Mixnets that further ensures the anytrust assumption holds realized by introducing guard mixes. To draw actionable conclusions, we perform an analysis of the best realistic and resource-bounded adversarial strategies against each of the studied algorithms, and evaluate security metrics against each best adversarial strategy. Moreover, we highlight the need for a temporal security analysis and develop routesim, a simulator to evaluate the effect of temporal dynamics and user behaviors over the Mixnet. The resulting security notions are complementary to the state-of-the-art entropic definitions. The simulator is designed to help Mixnets developers in assessing the devil in the details resulting from design decisions. Ultimately, our results suggest strong potential improvements to current designs and guidance for shaping Mix networks.