Breaking and (Partially) Fixing Onion Routing with Fragmentation
Authors: Daniel Schadt (Karlsruhe Institute of Technology), Christoph Coijanovic (Karlsruhe Institute of Technology), Thorsten Strufe (Karlsruhe Institute of Technology)
Volume: 2026
Issue: 4
Pages: 272–289
DOI: https://doi.org/10.56553/popets-2026-0120
Artifact: Available, Functional, Reproduced
Abstract: 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.
Keywords: message fragmentation, mix network, onion routing
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution 4.0 license.
