Mix networks are a cornerstone of anonymous communication, protecting users' relationships by relaying their messages through a series of mix nodes. To accommodate large payloads, deployed systems rely on message fragmentation, but this seemingly benign feature unwittingly opens a subtle door for adversaries. In this paper, we show that fragmentation enables adversaries to tag messages by suppressing single fragments and thereby break sender-recipient unlinkability, striking at the core privacy guarantee of mix networks. We demonstrate the practicality of this attack on Nym, a real-world deployed mix network. To address this threat, we design a lightweight mitigation that incurs only little overhead in both packet size and processing time. We provide a formal model of fragmentation in mix networks and prove that our mitigation restores unlinkability in this model.

Mix networks allow communication with strong anonymity guarantees. In theory, mix networks can scale indefinitely, as additional nodes can be added to the network to support new users. However, one factor that limits scalability in current designs is the need for all clients to know both the identity and the key of every available mix node. In circuit-based onion routing, a mechanism that does not require this knowledge to be globally available exists, but it relies on the interactivity of the circuit construction to keep its security guarantees. We therefore set out to investigate whether we can transfer such a mechanism to the context of message-based mix networks. In this paper, we propose Aimless Onions, the first mix format that enables clients to create onions in a mix network without knowing which nodes are available. Rather than downloading topology information, clients only need to acquire constant-size public parameters. Thus, Aimless Onions overcomes an important scalability limitation in mix networks, while retaining the same security guarantees as the state of the art. Using Aimless Onions, clients sending 25 messages per hour save 74% of bandwidth compared to using Spinx packets and topology information download, even at today's network sizes.

Mix networks are a well-known technique to hide communication metadata, but incur a high overhead especially in group communication settings. This hinders their adoption in real-world usage, as group communication makes up a big part of modern communication patterns. In this paper, we introduce "PolySphinx", a mix format that is a step towards efficient anonymous multicasting and allows a mix node to replicate the message payload to multiple recipients. We prove that PolySphinx does not compromise on the anonymity offered to users, while considerably reducing the latency of group messages: In a group with 25 members, the average latency drops from 6.1s using the state-of-the-art Rollercoaster approach to 4.1s using PolySphinx.