Breaking and (Partially) Fixing Onion Routing with Fragmentation
Daniel Schadt (Paper author · Karlsruhe Institute of Technology), Christoph Coijanovic (Paper author · Karlsruhe Institute of Technology), Thorsten Strufe (Paper author · Karlsruhe Institute of Technology)
Privacy Enhancing Technologies Symposium (PETS) 2026 · Day 2 · Alpaca
Overview
Anonymous communication systems, such as mix networks, are crucial for protecting user privacy, especially for sensitive interactions like whistleblowing. However, maintaining anonymity becomes challenging when transmitting large messages, as these often require fragmentation into smaller packets. In their talk, "Breaking and (Partially) Fixing Onion Routing with Fragmentation," Daniel Schadt, Christoph Coijanovic, and Thorsten Strufe from Karlsruhe Institute of Technology delve into a practical attack that exploits fragmentation and retransmission mechanisms in mix networks to deanonymize senders.

Key moments
- 0:00 Anonymous communication challenges with message fragmentation
- 2:00 Testing fragmentation attack in practice with Nym
- 3:40 Three conditions required for the fragmentation attack
- 4:28 First mitigation: all-or-nothing transform for fragments
- 5:55 Second mitigation: per-message acknowledgements and retransmissions
- 6:20 Analyzing latency trade-offs of the proposed mitigation
- 8:00 Conclusion: attack works, mitigation, and future challenges
Breaking and (Partially) Fixing Onion Routing with Fragmentation
Speakers: Daniel Schadt (Paper author, Karlsruhe Institute of Technology); Christoph Coijanovic (Paper author, Karlsruhe Institute of Technology); Thorsten Strufe (Paper author, Karlsruhe Institute of Technology)
Conference: PETS
YouTube: https://www.youtube.com/watch?v=0ei0-l8amxk
Overview
Anonymous communication systems, such as mix networks, are crucial for protecting user privacy, especially for sensitive interactions like whistleblowing. However, maintaining anonymity becomes challenging when transmitting large messages, as these often require fragmentation into smaller packets. In their talk, "Breaking and (Partially) Fixing Onion Routing with Fragmentation," Daniel Schadt, Christoph Coijanovic, and Thorsten Strufe from Karlsruhe Institute of Technology delve into a practical attack that exploits fragmentation and retransmission mechanisms in mix networks to deanonymize senders.
The researchers demonstrate how a malicious recipient can detect and confirm a sender's identity by observing patterns in message completion times, particularly when packets are dropped. They present a concrete attack against Nym, a commercially available mix network that incorporates transparent fragmentation and reliable transport. Beyond merely identifying the vulnerability, the team proposes a novel mitigation strategy involving a new packet format based on an all-or-nothing transform (AONT) and a modified retransmission policy, aiming to restore sender anonymity while acknowledging inherent performance trade-offs. This work underscores the need for a holistic approach to mix network security, particularly as these systems evolve to handle diverse traffic types.
Background
▶ Watch: Anonymous communication challenges with message fragmentation (0:00)
The fundamental goal of a mix network is to enable anonymous communication between parties. In such a system, a sender (Alice) routes her message through a series of intermediate nodes, known as "mixes." Each mix shuffles incoming messages, delays them, and then forwards them to the next hop, effectively obscuring the link between the sender and the recipient. A critical requirement for traditional mix networks is that all messages must conform to a uniform size. If messages varied in length, an adversary could potentially re-identify them by their unique size, thereby compromising anonymity.
However, the modern internet often demands the transmission of larger data payloads, such as documents, images, or video streams. To accommodate this, mix networks frequently employ fragmentation, where a large message is split into multiple smaller parts, each of which is then sent independently through the network. The recipient (Bob) is responsible for reassembling these fragments to reconstruct the original message. While fragmentation solves the size constraint, it introduces new vectors for attack, particularly when coupled with mechanisms for reliable transport, which typically involve acknowledgements (ACKs) and retransmissions of lost packets, similar to TCP.
Prior research has touched upon related vulnerabilities. Nick Matthewson and George Danezis discussed multi-message tagging attacks, noting the potential for deanonymization when multiple related messages are sent, but left the practical implications for future work. Similarly, Funan et al. explored dropping bounds and performance characteristics in anonymous communication systems, highlighting the impact of packet loss. Despite these insights, a practical demonstration of how fragmentation-based attacks could be leveraged in real-world mix networks, and effective countermeasures, remained underexplored. This gap motivated the current research, which specifically investigates whether such an attack is feasible in practice and, if so, how it might be prevented. The team chose to focus on Nym, a prominent mix network that natively implements transparent fragmentation and reliable retransmission mechanisms, making it an ideal candidate for their practical evaluation.
Key Findings
▶ Watch: Three conditions required for the fragmentation attack (3:40)
The research yielded several critical findings regarding fragmentation-based attacks on mix networks and potential mitigations:
Firstly, the study definitively concluded that the proposed attack, which exploits fragmentation and reliable transport mechanisms, works in practice. By conducting experiments on a simulated Nym network, the researchers demonstrated that a malicious recipient can reliably detect a sender experiencing packet loss, thereby compromising their anonymity. This practical validation highlights a significant vulnerability in current mix network designs that incorporate fragmentation without adequate safeguards.
Secondly, the team identified three specific conditions that must be met for this fragmentation-based attack to be successful:
- Adversary's ability to link dropped packets: The adversary (e.g., a malicious recipient) must be able to drop packets and link these drops back to the sender. In their model, this is often implicitly possible once the sender initiates communication with the adversary.
- Recipient's ability to detect missing packets: The recipient must be able to discern when a packet or fragment is missing. This is typically achieved through explicit identifiers (like sequence numbers) or implicitly by observing an incomplete message (e.g., a corrupted image or video).
- Derivation of the final recipient from a subset of packets: From the fragments that are not dropped, the adversary must be able to determine the final recipient. This condition is crucial because in current systems, each fragment is often individually addressed to the ultimate destination.
Thirdly, the researchers proposed a novel mitigation strategy designed to break the third condition of the attack. This strategy involves two main components: a new packet format utilizing an all-or-nothing transform (AONT) and a revised retransmission policy based on per-message acknowledgements. This combined approach aims to prevent an adversary from gaining meaningful information from partial message receipts or observing retransmission patterns.
Finally, while the proposed mitigation effectively hides the deanonymizing signal, it comes with a notable trade-off: increased latency. The requirement for all fragments to arrive before decryption, coupled with retransmitting entire messages, significantly delays message delivery, especially under higher packet loss conditions. However, the study suggests that for small, more realistic packet loss rates, the latency impact remains acceptable, while crucially eliminating the observable variation that signals an attack.
Technical Deep Dive
▶ Watch: First mitigation: all-or-nothing transform for fragments (4:28)
The core of the fragmentation-based deanonymization attack lies in the observable signal generated by a sender's client when packets are lost and subsequently retransmitted. In a typical mix network like Nym, large messages are fragmented, and each fragment is routed individually. If some of Alice's fragments are dropped (either by network conditions or a malicious intermediary/recipient), her client's reliable transport mechanism will trigger retransmissions. A malicious recipient (Bob) can exploit this.
Bob initiates contact with Alice and then selectively drops some of her incoming fragments. Because Nym uses a per-fragment acknowledgement strategy, Alice's client will retransmit only the missing fragments. Bob observes the time it takes to receive the first fragment of a message and then the time until the entire set of fragments for that message is complete. For unaffected clients, this "message completion time" is relatively constant. However, for Alice, who is experiencing packet loss and retransmissions, this time significantly increases and becomes highly variable. This distinct pattern acts as a side channel, allowing Bob to confirm that Alice is the sender experiencing issues, thus breaking her anonymity.
The researchers formalized this attack by outlining three critical conditions:
- Adversary can drop linkable packets: This is assumed possible, especially if the adversary is the recipient and can identify packets destined for them from a specific sender.
- Recipient can detect missing packets: This is inherent to reliable transport protocols. Fragments carry identifiers, or the absence of a complete message signals missing parts.
- Recipient can derive final recipient from a subset of non-dropped packets: Crucially, if Bob receives even a single fragment, he knows it's intended for him. This allows him to associate the observed retransmission patterns with his interaction with Alice.
To mitigate this attack, the proposed solution focuses on breaking the third condition: preventing any entity from deriving meaningful information or the final recipient from a partial set of fragments. This is achieved through a two-pronged approach:
New Packet Format with All-or-Nothing Transform (AONT)
The first component is a novel packet format incorporating an all-or-nothing transform (AONT). An AONT is a cryptographic primitive that ensures that a message cannot be decrypted or revealed unless all of its transformed parts are collected. The process is as follows:
- Pre-fragmentation Transformation: Instead of fragmenting the original message directly, Alice first takes her entire message and the recipient's identifier. She then applies an AONT to this combined data.
- AONT Output Fragmentation: The output of the AONT is then fragmented into multiple smaller parts.
- Routing to Meeting Nodes: Each of these AONT fragments is routed individually through the mix network. However, instead of being addressed directly to Bob, they are addressed to a common "meeting node" (or a set of nodes at the same logical "height" within the mix network architecture).
- Collective Decryption: Only when all AONT fragments arrive at this designated meeting node can the AONT be undone. At this point, the original message and the true final recipient (Bob) are revealed. The meeting node then forwards the complete, decrypted message to Bob.
This mechanism ensures that no intermediate node, nor Bob himself, can learn the message content or even the final recipient if they only receive a subset of the fragments. The information is cryptographically locked until complete assembly. This effectively breaks the third attack condition, as a partial collection of fragments yields no useful information about the destination or content.
Modified Retransmission Strategy: Per-Message Acknowledgements
The AONT addresses the issue of partial information leakage, but it doesn't fully solve the retransmission pattern problem. Even if an intermediate node can't decrypt individual fragments, it might still observe a pattern of retransmissions for a specific set of AONT fragments, potentially inferring communication activity. To counter this, the researchers propose a shift from per-fragment acknowledgements to per-message acknowledgements.
Under this new strategy:
- End-to-End Acknowledgment: Alice only considers a message successfully delivered and acknowledged when Bob acknowledges the entire message (i.e., all its AONT fragments have been successfully reassembled and delivered to him).
- Full Message Retransmission: If Alice does not receive an acknowledgment for the complete message within a timeout period, she will retransmit all fragments of that message, but crucially, she will do so under a fresh identifier. This means the retransmitted set of fragments appears to be entirely new, making it extremely difficult for an adversary to link them back to a previous, potentially dropped, attempt.
This strategy significantly enhances anonymity by obscuring retransmission patterns. However, it introduces a substantial performance overhead. With per-fragment acknowledgements, only the few lost fragments need to be retransmitted. With per-message acknowledgements, if even a single fragment is lost, the entire set of fragments must be resent. This means that for a message to be successfully delivered, there must be "one lucky attempt" where all fragments survive the network path without loss.
As evaluated in the paper, this per-message retransmission strategy indeed leads to a much higher latency compared to per-fragment acknowledgements, especially as packet loss rates increase. For example, the talk's results show that for increasing packet loss, the per-message strategy is "way worse" in terms of message arrival time. However, for small packet losses, which are more typical in a healthy network not under active attack, the latency increase is described as "still okay." Critically, from Bob's perspective, this strategy "removes all the variation" in message completion time, even for high packet loss. This is the desired outcome, as it eliminates the deanonymizing signal. The computational overhead of the AONT and new packet format was also evaluated and detailed in the full paper.
Demo / Proof of Concept
▶ Watch: Analyzing latency trade-offs of the proposed mitigation (6:20)
To validate the practical feasibility of the attack and the efficacy of their proposed mitigations, the researchers constructed a dedicated test environment. The core of their experimental setup involved using the Shadow network simulator, a discrete-event network simulator that allows running real applications (like Nym) within a controlled, emulated network topology. They utilized slightly modified Nym binaries to facilitate their measurements and interventions.
The experimental scenario was designed to mimic a realistic mix network interaction while isolating the variables under investigation. It consisted of three senders communicating with one recipient (Bob). A key aspect of the setup was that one of these senders, designated as Alice, was subjected to simulated packet loss. This allowed the researchers to observe how Bob perceived the communication from Alice compared to the unaffected clients.
The primary metric observed from Bob's perspective was the time elapsed between receiving the first segment of a message and successfully completing the fragment set that constitutes the entire message.
The initial results, demonstrating the attack's effectiveness, showed a clear distinction:
- For the unaffected clients, the message completion time remained very constant, indicating smooth and predictable delivery.
- For Alice, as the researchers introduced progressively more packet loss, the time to complete the message significantly increased. This was because Bob had to wait for the dropped fragments to be retransmitted before he could fully reassemble the message. This observable increase and variation in completion time served as the clear, deanonymizing signal for Bob, confirming that the attack works in practice.
Subsequently, the researchers evaluated their proposed mitigation strategy. When the system was configured with the new packet format (AONT) and the per-message retransmission strategy, the results were striking. Even under conditions of high packet loss for Alice, the time Bob measured between the first and last fragment of a message showed no variation. This demonstrated that the mitigation successfully achieved its goal of hiding the observable signal, making it impossible for Bob to distinguish Alice's communication from that of other, unaffected senders based on retransmission patterns. While the overall latency for message delivery increased, the critical deanonymizing signal was effectively suppressed.
Defensive Implications
▶ Watch: Conclusion: attack works, mitigation, and future challenges (8:00)
The findings from this research carry significant implications for developers, operators, and users of mix networks and other anonymous communication systems. The demonstrated practical attack highlights a critical vulnerability that arises when transparent fragmentation and reliable transport mechanisms are implemented without considering their potential for side-channel leakage.
For mix network developers and operators, the primary defensive implication is the urgent need to review and potentially redesign their fragmentation and retransmission strategies. Systems like Nym, which offer built-in fragmentation, must incorporate robust countermeasures against such timing attacks. The proposed solution, involving an all-or-nothing transform (AONT) for message packing and per-message acknowledgements with fresh identifiers for retransmissions, provides a concrete blueprint. Implementing AONT ensures that no partial information is leaked, while per-message retransmissions mask the tell-tale patterns of packet loss from adversaries.
However, it's crucial to acknowledge the limitations of the proposed fix. As explicitly stated in the talk, the mitigation primarily addresses scenarios where an adversary can drop packets. It does not inherently solve issues arising from an adversary's ability to delay packets. Packet delays can also introduce timing variations that might be exploited for deanonymization. Therefore, mix network designs must integrate this specific mitigation with other, complementary techniques that address packet delays, such as padding, traffic shaping, or more sophisticated timing randomization strategies. A multi-layered defense is essential for comprehensive anonymity.
Beyond specific technical fixes, the research strongly advocates for a holistic view of mix network security. The speakers argue that mix networks should be treated as a "paved administration layer," providing a foundational level of anonymity. Any additional features or layers built on top, such as authentication, must be meticulously designed and evaluated to ensure they do not inadvertently introduce new side channels that could compromise anonymity. The risk is that seemingly benign features, if not carefully implemented with anonymity in mind, could allow adversaries to re-identify users or traffic, effectively undoing the core privacy guarantees. Defenders must adopt a security-by-design approach, where anonymity considerations are paramount throughout the system's lifecycle, from architecture to implementation and deployment.
Key Takeaways
- Fragmentation is a Deanonymization Risk: Transparent fragmentation combined with reliable transport mechanisms (ACKs, retransmissions) can create observable timing side channels that a malicious recipient can exploit to deanonymize a sender.
- Attack Works in Practice: The attack was practically demonstrated against Nym, showing that a malicious recipient can identify a sender experiencing packet loss by observing increased and variable message completion times.
- Three Conditions for Attack: The attack relies on an adversary's ability to drop linkable packets, the recipient's ability to detect missing packets, and the ability to derive the final recipient from a subset of non-dropped fragments.
- All-or-Nothing Transform (AONT) for Packet Format: A new packet format using AONT prevents partial information leakage and hides the final recipient from intermediate nodes, breaking the third attack condition.
- Per-Message Retransmissions for Anonymity: Switching to per-message acknowledgements with fresh identifiers for retransmissions effectively hides the deanonymizing signal of packet loss patterns, though at the cost of increased latency.
- Holistic Security is Crucial: Mix network security must be viewed holistically, with careful consideration of how additional features (e.g., authentication) might introduce new side channels. The proposed fix is limited to packet drops and requires combination with delay mitigations.
About the Speaker(s)
The talk "Breaking and (Partially) Fixing Onion Routing with Fragmentation" was presented by Daniel Schadt, who is one of the paper's authors. Daniel Schadt, along with Christoph Coijanovic and Thorsten Strufe, are affiliated with the Karlsruhe Institute of Technology. Their work focuses on enhancing the security and privacy aspects of anonymous communication systems, particularly mix networks, addressing practical vulnerabilities and proposing robust countermeasures.
Reviews
Dr. Zero (Offensive Security Researcher) — SOLID
Schadt and the KIT crew finally weaponized the fragmentation leak researchers have theorized about for years, proving it practically against Nym. It's a sharp, elegant attack that proves reliable transport is the natural enemy of anonymity. The proposed fix is computationally brutal, but the offensive research here is undeniable.
Heather Calloway (CISO) — PASS
Unless you are building commercial privacy tools or running infrastructure for dissidents, your leadership team does not need to see this. It is a competent academic breakdown of timing attacks in mix networks, but it falls completely outside the enterprise risk register.
→ Top-rated talks at Privacy Enhancing Technologies Symposium (PETS) 2026
All talks from Privacy Enhancing Technologies Symposium (PETS) 2026