When the packet rate of flows in a mixnet depends on the amount of transferred data, it is possible to identify which flow entering is which flow exiting the mixnet based on their shapes. We present a passive shape-based flow correlation attack against state-of-the-art mixnet Nym and a systematic evaluation of countermeasures. Assuming an adversary controlling both the entry and exit gateway-requesters selected by users to access the public Internet through Nym, our attack's artificial neural network assigns correlation scores to flow pairs based on traffic distribution similarities to accurately distinguish paired from unpaired flow tuples. From data we collected on the live Nym mixnet, we generate$ \mathbf {45}$datasets and$ \mathbf {119}$testing scenarios for different defense configurations. After one minute of attacking flow pairs on default Nym, we achieve a PR-AUC of$ \mathbf {0.9998}$at a base rate of$ \mathbf {1.9 \times 10^{-4}}$paired flow tuples. However, (combinations of) the five evaluated defense strategies indicate that the right choice and scale of countermeasure(s) can offer meaningful protection. Our evaluation also informs on the resources overhead spent on defenses. We discuss steps a mixnet such as Nym can take to make our attack both less likely and less accurate.

Mixnets provide communication anonymity against network adversaries by routing packets independently via multiple hops, delaying them artificially at each hop, and introducing cover traffic. We show that these features (particularly the use of cover traffic) significantly diminish the effectiveness of state-of-the-art flow correlation techniques developed to link the two ends of a Tor connection. In this work, we propose novel methods to determine whether a set of endpoints exchanges packets via a mixnet and demonstrate their effectiveness by applying them to the Nym mixnet. We consider Nym in both an idealized lab setup and the official live network, and propose and compare three classifiers to conduct flow matching on it. Our statistical classifier tests whether egress packet timestamps are consistent with ingress timestamps and the (known) routing delay characteristic of the mixnet. In contrast, our two deep learning (DL) classifiers learn to distinguish matched from unmatched flow pairs from collected datasets directly, rather than relying on priors that describe the delay distribution. All three classifiers use our flow merging technique, which enables testing a match for sets of communicating endpoints of any cardinality. Considering a use case where two observed endpoints communicate exclusively to exchange a file through Nym, we find that flow matching is fast and accurate in the idealized lab setup. If flow pairs are aligned using all network observations in a download, we achieve a TPR of circa 0.6 (DL) and 0.47 (statistical) at an FPR of 10^-2 after only processing 100 observations. We evaluate classifier performance under key variations of this setup: the absence of loop cover traffic, an increased or decreased average per-mix delay, larger communicating sets (three endpoints) with faster responders, and the presence of realistic network effects (live network). The classifiers' matching performance diminishes on the live network where packet losses and variable propagation delays exist, reducing DL TPR to circa 0.26 and statistical TPR to circa 0.28 at an FPR of 10^-2. Informed by the insights of our analyses, we outline countermeasures that can be deployed in mixnets such as Nym to mitigate flow matching threats.

Current Anonymous Communication Systems (ACS) lack fault tolerance and thus risk becoming unavailable when failures occur, forcing users offline or to less private messengers. In this work, we evaluate end-to-end message transmission latencies and resource demands of state-of-the-art mixnet Vuvuzela and CPIR system Pung under different network failure scenarios on an ACS test bed across four continents. We compare Vuvuzela and Pung to proof-of-concept mixnet FTMix that we equip with simple fault tolerance measures. Our analysis shows that FTMix maintains the smallest divergence of end-to-end latencies under failures from their respective baseline among all three ACS, while also achieving a balanced resource consumption trade-off. Thus, we consider fault tolerance effective in ensuring service availability and a crucial design principle for future ACS proposals.

Modern geo-replicated software serving millions of users across the globe faces the consequences of the CAP dilemma, i.e., the inevitable conflicts that arise when multiple nodes accept writes on shared state. The underlying problem is commonly known as fault-tolerant multi-leader replica- tion; actively researched in the distributed systems and database communities. As a more recent theoretical framework, Conflict-free Replicated Data Types (CRDTs) propose a solution to this problem by offering a set of always converging primitives. However, modeling non-trivial system state with CRDT primitives is a challenging and error-prone task. In this work, we propose a solution for a geo-replicated online service with fault-tolerant multi-leader replication based on CRDTs. We chose IMAP as use case due to its prevalence and simplicity. Therefore, we modeled an IMAP-CRDT and verified its correctness with the interactive theorem prover Isabelle/HOL. In order to bridge the gap between theory and practice, we implemented an open-source proto- type pluto and an IMAP benchmark for write-intensive workloads. We evaluated our prototype against the standard IMAP server Dovecot on a multi-continent public cloud. The results ex- pose the limitations of Dovecot with respect to response time performance and replication lag. Our prototype was able to leverage its conceptual advantages and outperformed Dovecot. We find that our approach is promising when facing the multitude of potential concurrency bugs in development of systems at planetary scale.